2
$\begingroup$

I have a Windows 10 laptop with an algorithm that creates a random number using the PRNG CryptGenRandom. According to Wikipedia:

Because CryptGenRandom is the de facto standard CSPRNG in Win32 environments, its security is critical for Windows users.

However,

The specifics of CryptGenRandom's algorithm have not been officially published. As with any unpublished random number generation algorithm, it may be susceptible to theoretical weaknesses including the use of outdated algorithms, and a reliance for entropy gathering on several monotonically-increasing counters that might be estimated or controlled to an extent by an attacker with local access to the system.

I would like to know if I can predict new values of the algorithm on my own laptop. Here the idea is that I know what future values will be, without having actually run CryptGenRandom to generate the values.

Is it possible to predict future values of the algorithm? Or at least make predictions that are better than chance?

Improve this question
$\endgroup$
3
  • $\begingroup$ This comment since link only answers are discouraged. See NOBUS and delve deeper. $\endgroup$
    – Paul Uszak
    Aug 10 at 16:29
  • $\begingroup$ Maybe there is an exploit of CryptGenRandom on the grey market? $\endgroup$
    – Riemann
    Aug 10 at 17:40
  • $\begingroup$ There is quite a lot of information to be found here (although outdated) and it is possible to request access to Windows source. The Wikipedia page also contains a lot of information, similarly outdated maybe. It does use a NIST algorithm; as long as you don't learn the state you won't be able to predict the random values it produces. $\endgroup$
    – Maarten Bodewes ♦
    Aug 10 at 20:53

1 Answer 1

Reset to default
2
$\begingroup$

A useful reference is Niels Ferguson's The Windows 10 random number generation infrastructure, October 2019, despite that

it should not be interpreted to be a commitment on the part of Microsoft, and Microsoft cannot guarantee the accuracy of any information presented after the date of publication.

That tells CryptGenRandom

use ProcessPrng function to produce random bytes

and about ProcessPrng:

This is the primary interface to the user-mode per-processor PRNGs. It is implemented in BCryptPrimitives.dll.

and

All PRNGs in the system are SP800-90 AES_CTR_DRBG with 256-bit security strength using the df() function for seeding and re-seeding (see SP 800-90 for details). (…) The Basic PRNGs are not used directly, but rather through a wrapping layer that adds several features.

  • A small buffer of random bytes to improve performance for small requests.
  • A lock to support multi-threading.
  • A seed version.

(…) The buffering is straightforward. There is a small buffer (currently 128 bytes). If a request for random bytes is 128 bytes or larger, it is generated directly from AES_CTR_DRGB. If it is smaller than 128 bytes it is taken from the buffer. The buffer is re-filled from the AES_CTR_DRBG whenever it runs empty. So, if the buffer contains 4 bytes and the request is for 8 bytes, the 4 bytes are taken from the buffer, the buffer is refilled with 128 bytes, and the first 4 bytes of the refilled buffer are used to complete the request, leaving 124 bytes in the buffer.

If my understanding is correct that this buffer is in user space, and nothing prevents the process using CryptGenRandom to access it, then the program that uses CryptGenRandom to generate 4 bytes can be written so that it "predicts" the 124 bytes that it will later obtain from CryptGenRandom, merely by peeking at these bytes in memory. A debugger would allow the same.

Further, if my understanding of other parts of the document is correct, administrative privileges or breaching some other barrier (e.g. by exploiting a kernel-trusted device driver or some data leak enabled by a CPU cache/branch predictor) would allow to predict more (but I believe not indefinitely many) bytes that have not been generated yet, and also would allow other processes to predict what CryptGenRandom will supply in a process they spy.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Doesn't Mr. Ferguson work for u$oft? Have you been able to decompile this part of windows to confirm what he says? $\endgroup$
    – Paul Uszak
    Aug 10 at 21:20
  • $\begingroup$ @PaulUszak: I don't know the exact relation of Niels Ferguson with Microsoft, but everything points to Microsoft endorsing and publishing his work. I have not decompiled (the two different instances of) BCryptPrimitives.dll (which is supposed to perform most or all of what I discuss), but I could, and other may have done it. I have no idea about the lower layers. I see reasons not to trust an entity that once supplied Dual_EC_DRBG, which the document that I quote suggests, and other sources affirm. $\endgroup$
    – fgrieu ♦
    Aug 10 at 21:30
  • 1
    $\begingroup$ @fgrieu, I edited my question to make clear that this answer matches the requirements. I also asked on Stackoverflow whether this is indeed possible: stackoverflow.com/questions/76882746/… $\endgroup$
    – Riemann
    Aug 11 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.