Thread-topic: Cryptanalysis of the Random Number Generator of the Windows Operating System
> -----Original Message-----
> From: SecuriTeam [mailto:support@xxxxxxxxxxxxxx]
> Sent: Tuesday, November 13, 2007 6:23 PM
> To: html-list@xxxxxxxxxxxxxx
> Subject: [REVS] Cryptanalysis of the Random Number Generator
> of the Windows Operating System
>
>
> Cryptanalysis of the Random Number Generator of the Windows
> Operating System
>
>
>
> The pseudo-random number generator (PRNG) used by the Windows
> operating system is the most commonly used PRNG. The
> pseudo-randomness of the output of this generator is crucial
> for the security of almost any application running in
> Windows. Nevertheless, its exact algorithm was never published.
>
> We examined the binary code of a distribution of Windows
> 2000, which is still the second most popular operating system
> after Windows XP. (This investigation was done without any
> help from Microsoft.) We reconstructed, for the first time,
> the algorithm used by the pseudo-random number generator
> (namely, the function CryptGenRandom). We analyzed the
> security of the algorithm and found a non-trivial attack:
> given the internal state of the generator, the previous state
> can be computed in $O(2^{23})$ work (this is an attack on the
> forward-security of the generator, an $O(1)$ attack on
> backward security is trivial). The attack on forward-security
> demonstrates that the design of the generator is flawed,
> since it is well known how to prevent such attacks.
>
> We also analyzed the way in which the generator is run by the
> operating system, and found that it amplifies the effect of
> the attacks: The generator is run in user mode rather than in
> kernel mode, and therefore it is easy to access its state
> even without administrator privileges. The initial values of
> part of the state of the generator are not set explicitly,
> but rather are defined by whatever values are present on the
> stack when the generator is called.Furthermore, each process
> runs a different copy of the generator, and the state of the
> generator is refreshed with system generated entropy only
> after generating 128 KBytes of output for the process running
> it. The result of combining this observation with our attack
> is that learning a single state may reveal 128 Kbytes of the
> past and future output of the generator.
>
> The implication of these findings is that a buffer overflow
> attack or a similar attack can be used to learn a single
> state of the generator, which can then be used to predict all
> random values, such as SSL keys, used by a process in all its
> past and future operation. This attack is more severe and
> more efficient than known attacks, in which an attacker can
> only learn SSL keys if it is controlling the attacked machine
> at the time the keys are used.
>
>
> Conclusions
> WRNG design. The paper presents a clear description of the
> WRNG, the most frequently used PRNG. The WRNG has a complex
> layered architecture which includes entropy rekeying every
> 128 KBytes of output, and uses RC4 and SHA-1 as building
> blocks. Windows runs the WRNG in user space, and keeps a
> different instance of the generator for every process.
>
> Attacks. The WRNG depends on the use of RC4, which does not
> provide any forward security. We used this fact to show how
> an adversary which learns the state of the WRNG can compute
> past and future outputs of the generator. The attacker can
> learn future outputs in O(1) time and compute past outputs in
> O(223) time. These attacks can be run within seconds or
> minutes on a modern PC and enable such an attacker to learn
> the values of cryptographic keys generated by the generator.
> The attacks on both forward and backward security reveal all
> outputs until the time the generator is rekeyed with system
> entropy. Given the way in which the operating system operates
> the generator, this means that a single attack reveals 128
> KBytes of generator output for every process.
>
> Code analysis. Our research is based on studying the WRNG by
> examining its binary code. We were not provided with any help
> from Microsoft and were only using the binary versions of
> Windows. To verify our findings we developed a user mode
> simulator which captures WRNG states and computes future and
> past outputs of the WRNG. We validated the simulator output
> against real runs of the WRNG. WRNG versus LRNG. We compared
> between the pseudo-random generators used by Windows and
> Linux (WRNG vs. LRNG). The forward security attack on the
> WRNG is faster by a factor of O(240) compared to the attack
> on the LRNG. In addition, our findings show that the LRNG has
> better usage of operating system entropy, uses asynchronous
> entropy feedings, uses the extraction process as an entropy
> source, and shares its output between multiple processes. As
> a result, a forward security attack on the WRNG reveals
> longer sequences of generator output, compared to an attack
> on the LRNG.
>
> Recommendations
> Forward security. The most obvious recommendation is to
> change the algorithm used by the WRNG to one which provides
> forward security. This can be done by making local changes to
> the current implementation of the generator, or by replacing
> RC4 with a function which provides forward security.
> Alternatively, it is possible to use the transformation of
> [4] which transforms any standard generator to one providing
> forward security. We believe however that it is preferable to
> replace the entire algorithm used by the generator with a
> simpler algorithm which is rigorously analyzed. A good
> approach is to adopt the Barak-Halevi construction. That
> construction, suggested in [2], is a simple yet powerful
> construction of entropy based PRNGs. Its design is much
> simpler to implement than the current WRNG implementation
> and, assuming that its building blocks are secure, it
> provably preserves both forward and backward security. It can
> be implemented using, say, AES and a simple entropy extractor.
>
> Frequency of entropy based rekeys. The generator should rekey
> its state more often. We also suggest that rekeys are forced
> based on the amount of time that has passed since the last
> rekey. It is important to note that entropy based rekeys are
> required in order to limit the effect of attacks mounted by
> an adversary which obtains the state of the generator. (In a
> good generator, forward security and pseudo-randomness are
> guaranteed by the function which advances the state, and are
> ensured even if the generator generates megabytes or
> gigabytes of output between rekeys.) The risk of an adversary
> getting hold of the state seems to be more dependent on the
> amount of time the system runs, than on the length of the
> output of the generator. It therefore makes sense to force
> rekeys every some time interval, rather than deciding whether
> to rekey based on the amount of output produced by the generator.
>
>
> Additional Information:
> The information has been provided by Leo Dorrendorf and Zvi
> Gutterman and Benny Pinkas.
> The original article can be found at:
>
>
