Score:2

Can I predict CryptGenRandom on my own device?

pa flag

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?

Paul Uszak avatar
cn flag
This comment since link only answers are discouraged. See [NOBUS](https://en.wikipedia.org/wiki/NOBUS) and delve deeper.
Riemann avatar
pa flag
Maybe there is an exploit of CryptGenRandom on the grey market?
Maarten Bodewes avatar
in flag
There is quite a lot of information to be found [here](https://learn.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-cryptgenrandom) (although outdated) and it is possible to request access to Windows source. The [Wikipedia page](https://en.wikipedia.org/wiki/CryptGenRandom) 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.
Score:2
ng flag

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.

Paul Uszak avatar
cn flag
Doesn't Mr. Ferguson work for u$oft? Have you been able to decompile this part of windows to confirm what he says?
fgrieu avatar
ng flag
@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](https://en.wikipedia.org/wiki/Dual_EC_DRBG), which the document that I quote suggests, and other sources [affirm](https://crypto.stackexchange.com/q/61014/555).
Riemann avatar
pa flag
@fgrieu, I edited my question to make clear that this answer matches the requirements. I also asked on Stackoverflow whether this is indeed possible: https://stackoverflow.com/questions/76882746/how-can-i-access-the-buffer-of-cryptgenrandom
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.