Weaknesses in the Windows 2000 random number generator
An analysis of the pseudo random number generator (PRNG) in Windows 2000 has brought to light weaknesses which cause some concern. Israeli researchers have succeeded in reverse engineering the unpublished algorithm from its executable binary code and subjecting it to analysis. They have developed attacks against the generator which allow calculation of previous values or prediction of future values for the random numbers generated. It is not known to what extent the research can be applied to the random number generators in Windows XP and Vista.
The predictability of a computer system's pseudo random numbers has implications, some of them serious, for cryptographic applications running on systems such as encryption programs, banking software, DRM systems and SSL. Using these numbers, it may in some cases be possible to calculate the secret keys with which such programs protect data from unauthorised access. A PRNG such as that used by Windows 2000 performs various calculations on its own internal state registers, thereby modifying the state of these registers each time it is called. A small portion of the new state data is returned to the calling program - usually after running multiple internal cycles - in the form of the requested random number.
The researchers' most significant finding was that once the internal state is known, it is possible to calculate previous values of the pseudo-random sequence with an attack complexity of 223. This can, in their opinion, be ascribed to flaws in the design of the random number generator. Attacks of this complexity can generally be performed in a short time using standard PC hardware. On top of this, the generator runs in user mode, rather than in kernel mode as is usually the case on other systems. This makes attacks which read the PRNG's internal state, for example by means of a buffer overflow vulnerability in the target application, considerably easier.
The researchers also discovered a further weakness in the insecure initialisation of the state registers. Apparently, each program's initial PRNG state is partially determined by the values present in the program's stack memory.The values on the stack may, however, be predictable.
Furthermore, the researchers state that the internal PRNG state is refreshed too infrequently with system generated entropy data (from, for example, mouse movements, hard disk jitter or network delays). Only after generating 128 kbytes of random data is unpredictable entropy data fed into the state registers. This means that all random numbers within this 128 kbyte window can be calculated from a single known internal state.
Inital reports of a buffer overflow in other media by means of which attackers may be able to penetrate Windows systems could not be confirmed. To exploit the weaknesses discovered, an attacker would require local access to the Windows computer. The degree to which the attacks presented can be utilised in practice is also limited as they presuppose the existence of additional, known vulnerabilities in the applications being attacked or debugging options in order to read the internal PRNG state. It is relatively unlikely that specific attacks against actual applications will be able to be developed in the near future based on this work.
- Cryptanalysis of the Random Number Generator of the Windows Operating System, research paper by the Israeli researchers (PDF)