[REVS] Cryptanalysis of the Random Number Generator of the Windows Operating System

The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
- - promotion

The SecuriTeam alerts list - Free, Accurate, Independent.

Get your security news from a reliable source.

- - - - - - - - -

Cryptanalysis of the Random Number Generator of the Windows Operating


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.


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.

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.


The information has been provided by Leo Dorrendorf and Zvi Gutterman and
Benny Pinkas.
The original article can be found at: <http://eprint.iacr.org/2007/419>


This bulletin is sent to members of the SecuriTeam mailing list.
To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@xxxxxxxxxxxxxx
In order to subscribe to the mailing list, simply forward this email to: list-subscribe@xxxxxxxxxxxxxx


The information in this bulletin is provided "AS IS" without warranty of any kind.
In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.

Relevant Pages

  • [Full-disclosure] Raising Robot Criminals
    ... identity theft and robot-driven attack propagation. ... security as well as on Sql Injection, this text is not yet another one. ... security numbers - are opened for remote penetration. ...
  • [Full-disclosure] STEP Security
    ... Internet-Drafts are working documents of the Internet Engineering ... security in otherwise insecure environments. ... APT (Another Possible Threat) ... of a cyber attack before more terabytes of data are exfiltrated from ...
  • =?windows-1252?Q?Re=3A_Lahore=2DTerror_Attacks=3A_RAW=92s_Guerilla_Warfare?=
    ... security forces have been martyred in foiling three separate terrorist ... attacks by killing 9 terrorists at FIA Building, ... suicide attack in Kohat. ... been waging a guerilla warfare in Pakistan through its well-trained ...
  • [NT] DCE RPC Vulnerabilities New Attack Vectors Analysis
    ... Get your security news from a reliable source. ... These new attack methods were found while researching exploitation ... They might also apply to other vulnerabilities such as the DCE RPC DCOM ...
  • Risks Digest 24.91
    ... ACM FORUM ON RISKS TO THE PUBLIC IN COMPUTERS AND RELATED SYSTEMS ... Adi Shamir's bug attack ... Security company e-mail undercuts user education ...