This is another rekindled item from the past. As again it has been updated to try and address new thinking and to fix some of the language.
When we think of cryptography and where we follow the principle that security is in the key and the key alone then the length of the key is an important consideration. However possibly more important is the concept of randomness of the key. If keys are not random then an attacker has a greater chance of finding the key.
Cryptographic security is non-trivial and requires an understanding of a number of concepts and two of them are entropy and randomness, and these are strongly linked. In communications security there is often an assumption that any transmitted message will have some variation to all other transmitted messages, however in some communications systems there may be very strong levels of commonality between transmitted messages that may be exploited. A goal of cryptography is to mask the similarity between messages and commonly this is referred to as maximizing the entropy of a transmitted message. If a message is to be encrypted and the message has low entropy the cryptographer has to raise the entropy prior to encryption or as part of the encryption process. There are a number of examples of messages with inherently low entropy:
- Short text messages.
- Telematics status messages.
- Call setup messages.
Message entropy is discussed in a number of mathematical sources but at the root is Shannon’s “A Mathematical Theory of Communication”. Essentially if the attacker knows or guesses that the message can take a small set of values the probability of correctly guessing bit N+1 after receiving bit N tends towards 1 whereas for a random binary alphabet the probability of a correct guess should always be 0.5. In a cryptographic context, where Alice is sending a message m to Bob in the form of a binary string the rule of thumb is that the bigger the entropy of the message m the more guesses required by an attacker to guess m. After encryption of message m to generate message c the entropy of c should be as high as possible.
The rule of thumb for randomness is that if an attacker that can get access to all the historic random elements (all N values) this has to give zero information to correctly guess the value of the (N+1)th element. If this condition is met then the element can be considered as having a random value – but only with respect to the previous elements. However we also need to determine if we can emulate the randomness so that even if prior knowledge gives no greater likelihood of guessing the (N+1)th element we have to be assured that knowledge of the context does not allow us to guess the (N+1)th element. The source of entropy in a system that seeds the random number generator has to be good and many of them are poor, and further, are unsuited to standalone devices. For example sources for entropy may include movement of the mouse (not available in embedded and virtual systems with no GUI), the amount of free memory (not always practical in a virtualised environment where the VMs have fixed memory allocations), CPU temperature readings (in server farms this will be load balanced and trimmed to work in a very small and optimised range with very high load factors in many VM environments too). If our sources of entropy are random over only a small range then their value is reduced to that range – so we should not rely on achieving 128-bit security when our randomness is only within (say) a 4-bit range.
Thus the ability for a system to generate random numbers is central to most forms of modern cryptography. Typically cryptographic suites, such as OpenSSL, rely on operating system-provided methods for sourcing random numbers. Examples include /dev/(u)random on *nix and rand_s() on Windows . None of these methods provide truly-random numbers – that would require a physical source of randomness. Instead they are seeded by sources of entropy within the system and subsequently updated periodically . Typically when an operating system is restarted a pseudo-random seed is written to disk and this seed is used as an additional source of entropy when the operating system starts back up again. This ensures that the machine will not boot in the same entropy-state that it has booted in previously. Systems providing insufficient randomness have been shown to have compromised the integrity of security suites running on them, examples include the breaking of Netscape’s implementation of SSL  and the ability to predict Java session-ids .
Analysing PRNGs is a difficult task. The Linux PRNG , for example, is a part of the kernel so any modifications to enable introspection require that the kernel be re-compiled (such as those described in “Not-so-Random Numbers in Virtualized Linux and the Whirlwind RNG”). This kernel re-compilation may affect kernel-provided entropy sources in such a way that the experimentation no longer represents what would happen on an un-modified kernel. Gutterman, Pinkas and Reinman get around this problem by using a user-mode simulator of the Linux RNG for their experimentation, however producing this simulator is no mean feat. They also comment that although the source code for the RNG is available, it is poorly documented and what documentation there is is not up-to-date.
Good randomness that leads to high entropy, or sources of entropy that lead to true randomness, cannot be ignored. If the underlying source of randomness is weak (i.e. not really random or random over a very small range) then any dependent security function is going to be weakened. The attacker is not going to be stupid and try and break the crypto engine and the protocols if he can use weak randomness as an attack vector.