On the other hand, the generation of a master key requires a higher quality, such as more entropy. And in the case of one-time pads, the information-theoretic guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy, and thus any kind of pseudo-random number generator is insufficient. The encryption key is created and stored on the key management server. The key manager creates the encryption key through the use of a cryptographically secure random bit generator and stores the key, along with all it’s attributes, into the key storage database. Jun 03, 2012 For the Love of Physics - Walter Lewin - May 16, 2011 - Duration: 1:01:26. Lectures by Walter Lewin. They will make you ♥ Physics. Recommended for you. Generates a random integer between a specified inclusive lower bound and a specified exclusive upper bound using a cryptographically strong random number generator. GetNonZeroBytes(Byte) When overridden in a derived class, fills an array of bytes with a cryptographically strong random sequence of nonzero values. Applications that generate key get the randomness (entropy) from the operating system. The operating system, in turn, gets the randomness where it can find it. Ideally the OS gets randomness from a proper hardware generator, which is.
In cryptography, a key is a piece of information (a parameter) that determines the functional output of a cryptographic algorithm. For encryption algorithms, a key specifies the transformation of plaintext into ciphertext, and vice versa for decryption algorithms. Keys also specify transformations in other cryptographic algorithms, such as digital signature schemes and message authentication codes.[1]
Need for secrecy[edit]
In designing security systems, it is wise to assume that the details of the cryptographic algorithm are already available to the attacker. This is known as Kerckhoffs' principle — 'only secrecy of the key provides security', or, reformulated as Shannon's maxim, 'the enemy knows the system'. The history of cryptography provides evidence that it can be difficult to keep the details of a widely used algorithm secret (see security through obscurity). A key is often easier to protect (it's typically a small piece of information) than an encryption algorithm, and easier to change if compromised. Thus, the security of an encryption system in most cases relies on some key being kept secret.[2]
Trying to keep keys secret is one of the most difficult problems in practical cryptography; see key management. An attacker who obtains the key (by, for example, theft, extortion, dumpster diving, assault, torture, or social engineering) can recover the original message from the encrypted data, and issue signatures.
Key scope[edit]
Keys are generated to be used with a given suite of algorithms, called a cryptosystem. Encryption algorithms which use the same key for both encryption and decryption are known as symmetric key algorithms. A newer class of 'public key' cryptographic algorithms was invented in the 1970s. These asymmetric key algorithms use a pair of keys—or keypair—a public key and a private one. Public keys are used for encryption or signature verification; private ones decrypt and sign. The design is such that finding out the private key is extremely difficult, even if the corresponding public key is known. As that design involves lengthy computations, a keypair is often used to exchange an on-the-fly symmetric key, which will only be used for the current session. RSA and DSA are two popular public-key cryptosystems; DSA keys can only be used for signing and verifying, not for encryption.
Ownership and revocation[edit]
Part of the security brought about by cryptography concerns confidence about who signed a given document, or who replies at the other side of a connection. Assuming that keys are not compromised, that question consists of determining the owner of the relevant public key. To be able to tell a key's owner, public keys are often enriched with attributes such as names, addresses, and similar identifiers. The packed collection of a public key and its attributes can be digitally signed by one or more supporters. In the PKI model, the resulting object is called a certificate and is signed by a certificate authority (CA). In the PGP model, it is still called a 'key', and is signed by various people who personally verified that the attributes match the subject.[3]
In both PKI and PGP models, compromised keys can be revoked. Revocation has the side effect of disrupting the relationship between a key's attributes and the subject, which may still be valid. In order to have a possibility to recover from such disruption, signers often use different keys for everyday tasks: Signing with an intermediate certificate (for PKI) or a subkey (for PGP) facilitates keeping the principal private key in an offline safe.
Deleting a key on purpose to make the data inaccessible is called crypto-shredding.
Key sizes[edit]
![Random key encryption Random key encryption](https://image.slidesharecdn.com/cryptography-simplified-keygeneration-asymmetrickeys-160830133305/95/cryptography-simplified-key-generation-asymmetric-keys-3-638.jpg?cb=1472564279)
For the one-time pad system the key must be at least as long as the message. In encryption systems that use a cipher algorithm, messages can be much longer than the key. The key must, however, be long enough so that an attacker cannot try all possible combinations.
A key length of 80 bits is generally considered the minimum for strong security with symmetric encryption algorithms. 128-bit keys are commonly used and considered very strong. See the key size article for a more complete discussion.
The keys used in public key cryptography have some mathematical structure. For example, public keys used in the RSA system are the product of two prime numbers. Thus public key systems require longer key lengths than symmetric systems for an equivalent level of security. 3072 bits is the suggested key length for systems based on factoring and integer discrete logarithms which aim to have security equivalent to a 128 bit symmetric cipher. Elliptic curve cryptography may allow smaller-size keys for equivalent security, but these algorithms have only been known for a relatively short time and current estimates of the difficulty of searching for their keys may not survive. As early as 2004, a message encrypted using a 109-bit key elliptic curve algorithm had been broken by brute force.[4] The current rule of thumb is to use an ECC key twice as long as the symmetric key security level desired. Except for the random one-time pad, the security of these systems has not been proven mathematically as of 2018, so a theoretical breakthrough could make everything one has encrypted an open book (see P versus NP problem). This is another reason to err on the side of choosing longer keys.
Key choice[edit]
To prevent a key from being guessed, keys need to be generated truly randomly and contain sufficient entropy. The problem of how to safely generate truly random keys is difficult, and has been addressed in many ways by various cryptographic systems. There is a RFC on generating randomness (RFC 4086, Randomness Requirements for Security). Some operating systems include tools for 'collecting' entropy from the timing of unpredictable operations such as disk drive head movements. For the production of small amounts of keying material, ordinary dice provide a good source of high quality randomness.
Key vs password[edit]
For most computer security purposes and for most users, 'key' is not synonymous with 'password' (or 'passphrase'), although a password can in fact be used as a key. The primary practical difference between keys and passwords is that the latter are intended to be generated, read, remembered, and reproduced by a human user (though the user may delegate those tasks to password management software). A key, by contrast, is intended for use by the software that is implementing the cryptographic algorithm, and so human readability etc. is not required. In fact, most users will, in most cases, be unaware of even the existence of the keys being used on their behalf by the security components of their everyday software applications.
If a passwordis used as an encryption key, then in a well-designed crypto system it would not be used as such on its own. This is because passwords tend to be human-readable and, hence, may not be particularly strong. To compensate, a good crypto system will use the password-acting-as-key not to perform the primary encryption task itself, but rather to act as an input to a key derivation function (KDF). That KDF uses the password as a starting point from which it will then generate the actual secure encryption key itself. Various methods such as adding a salt and key stretching may be used in the generation.
See also[edit]
- Cryptographic key types classification according to their usage
- Diceware describes a method of generating fairly easy-to-remember, yet fairly secure, passphrases, using only dice and a pencil.
- glossary of concepts related to keys
References[edit]
- ^'What is cryptography? - Definition from WhatIs.com'. SearchSecurity. Retrieved 2019-07-20.
- ^'Quantum Key Generation from ID Quantique'. ID Quantique. Retrieved 2019-07-20.
- ^Matthew Copeland; Joergen Grahn; David A. Wheeler (1999). Mike Ashley (ed.). 'The GNU Privacy Handbook'. GnuPG. Archived from the original on 12 April 2015. Retrieved 14 December 2013.
- ^Bidgoli, Hossein (2004). The Internet Encyclopedia. John Wiley. p. 567. ISBN0-471-22201-1 – via Google Books.
Retrieved from 'https://en.wikipedia.org/w/index.php?title=Key_(cryptography)&oldid=946641234'
If you've been following recent news about technical spying by the US National Security Agency and the UK's Government Communications Headquarters you may have come across a claim that the NSA was involved in weakening a random number generator. The obvious question to ask is... why mess with random number generation?
The answer is rather simple: good random numbers are fundemental to almost all secure computer systems. Without them everything from Second World War ciphers like Lorenz to the SSL your browser uses to secure web traffic are in serious trouble.
To understand why, and the threat that bad random numbers pose, it's necessary to understand a little about random numbers themselves (such as 'what is a good random number anyway?') and how they are used in secure systems.
A Hacker News Hack
As an example of how random numbers go wrong I'll begin with a hack of the popular programming and technology web site Hacker News.
Four years ago I mentioned on the site that its random number generator was vulnerable to being used to attack the site. Not long after, and entirely independently, another contributor to the site actually carried out the attack with the permission of the site owner.
Here's how it worked. When you log into a web site you are typically assigned a unique ID for that session (the period you are logged in). That unique ID needs to be unique to you and not guessable by someone else. If someone else can guess it they can impersonate you.
In the case of Hacker News, the unique ID is a string of random
characters such as lBGn0tWMcx7380gZyrUO9B. Each logged in user has a
different string and the strings should be very, very difficult to
guess or figure out.
characters such as lBGn0tWMcx7380gZyrUO9B. Each logged in user has a
different string and the strings should be very, very difficult to
guess or figure out.
Pseudo-randomness
The IDs are generated internally using a pseudo-random number
generator. That's a mathematical function that can be called
repeatedly to get apparently random numbers. I say apparently because, as the great mathematician John von Neumann said: 'Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.' The computer scientist Donald Knuth tells a story of inventing a pseudo-random number generator himself only to be shocked at how poor it was.
generator. That's a mathematical function that can be called
repeatedly to get apparently random numbers. I say apparently because, as the great mathematician John von Neumann said: 'Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.' The computer scientist Donald Knuth tells a story of inventing a pseudo-random number generator himself only to be shocked at how poor it was.
Although pseudo-random number generators can generate a sequence of apparently random numbers they have weaknesses.
von Neumann used a simple pseudo-random number generator called the
middle square that works as follows. You start with some number (called a seed) and square it. You take the four middle digits as your random number and square them to get the next random number, and so on.
middle square that works as follows. You start with some number (called a seed) and square it. You take the four middle digits as your random number and square them to get the next random number, and so on.
For example, if you chose 4181 as a seed the sequence 4807, 1072,
1491, 2230, 9279, ... would be generated as follows:
1491, 2230, 9279, ... would be generated as follows:
This particular pseudo-random number has long since been replaced by better ones such as the Mersenne Twister whose output is harder to predict. The middle square method is trivial to predict: the next number it generates is entirely determined by the number it last produced. The Mersenne Twister on the other hand is much harder to predict because it has internal state that it uses to produce random numbers.
In the world of cryptography there are cryptographically secure pseudo-random number generators which are designed to be unpredictable no matter how many random cnumbers you ask it to generate. (The Mersenne Twister isn't cryptographically secure because it can be predicted if enough of the random numbers it generates are observed.)
For secure systems it's vital that the random number generator be unpredictable.
Starting With A Seed
And all pseudo-random number generators need to start somewhere; they need to be seeded and that's where Hacker News failed. The random number generator was seeded with the time in milliseconds when the Hacker News software was last started. By some careful work, the attacker managed to make Hacker News crash and could then predict when it restarted within a window of about one minute. From it he was able to predict the unique IDs assigned to users as they logged in and could, therefore, impersonate them. (Similar random number problems enabled one group of people to cheat at online poker.)
The full details of how the Hacker News Hack worked are here. The attack worked because once Hacker News crashed the attacker would wait for it to start and note the current time. Amusingly, the Hacker News server was willing to give out that information. The attacker then had 60s worth of possible seeds (60,000 seeds since the seed was in milliseconds).
So, the attacker would log in and look at their own unique ID. It had been generated by random numbers inside Hacker News's software. He then tried out each of the 60,000 seeds and ran the random number generation algorithm used by Hacker News until he found a match with his own unique ID. That told him which seed had been used, and it let him keep generating further unique IDs by generating the same sequence of random numbers that Hacker News was using. From that he could predict the unique IDs given out to users as they logged in and he could then impersonate them.
The Hacker News code was changed to use the Linux /dev/urandom source of random numbers which means that today unique IDs are generated with a good random number generator and without the weak seed previously used.
So, there are two ways in which pseudo-random number generation can
fail: the seed could be bad or the algorithm itself could be weak and predictable.
fail: the seed could be bad or the algorithm itself could be weak and predictable.
Random Numbers Everywhere
The Hacker News example isn't about cryptography itself, but random numbers are vital to cryptographic schemes. For example, any HTTPS session starts as follows:
- The web browser sends information to the server about which versionof SSL it wants to use and other information.
- The web server replies with similar information about SSL versionsand its SSL certificate.
- The web browser checks that the certificate is valid. If it is, it generates a random 'pre-master secret' that will be used to secure the connection.
Here's part of how a computer using WiFi establishes a secure connection to an access point using the popular WPA2 protocol:
![Random key generation in cryptography 2017 Random key generation in cryptography 2017](https://ars.els-cdn.com/content/image/1-s2.0-S004579061630619X-gr1.jpg)
- The access point generates a random nonce and sends it to the computer.
- The computer generates a random nonce and sends it to the accesspoint.
The access point and the computer continue on from there using those
random nonce values to secure the connection.
random nonce values to secure the connection.
Similarly, random numbers turn up when logging into web sites (and other systems), creating secure connections to servers using SSH, holding Skype video chats, sending encrypted email and more.
And the Achilles' Heel of the only completely secure cryptosystem, the one-time pad is that the pad itself must be completely randomly generated. Any predictability or non-uniformity in the random numbers used can lead to breaking of a one-time pad. (The other problem with one-time pads is reuse: they must be used only once.)
CloudFlare's Random Number Source
Random Key Generation In Cryptography History
At CloudFlare we need lots of random numbers for cryptographic purposes: we need them to secure SSL connections, Railgun, generating public/private key pairs, and authentication systems. They are an important part of forward secrecy which we've rolled out for all our customers.
We currently obtain most of our random numbers from either OpenSSL's random number generation system or from the Linux kernel. Both seed their random number generators from a variety of sources to make them as unpredictable as possible. Sources include things like network data, or the seek time of disks. But we think we can improve on them by adding some truly random data into the system, and, as a result, improve security for our customers.
We've embarked on a project to further improve our random numbers by providing a source of truly random numbers that don't come from a mathematical process. That can be done using things like radioactive decay, the motion of fluids, atmospheric noise, or other chaos.
Random Key Generation Algorithm
We'll be posting details of the new system when it's online.