3
$\begingroup$

The Windows RNG infrastructure is specified in this article. On page 4, it states that the PRNG called AES_CTR_DRBG is used (with 256-bit security strength).

According to Wikipedia, this PRNG has security problems when used with certain parameters.

Specifically:

When AES is used as the underlying block cipher and more than 128 bits are taken from this pseudorandom number generator, then the resulting security level is limited by the block size instead of the key size and therefore the actual security level is much less than the security level implied by the key size.

The source for this text on Wikipedia is this article.

In my understanding, pseudorandom number generators are often used to produce thousands of random bits before reseeding, and thus many more than 128. Does this mean that the Windows RNG is unsafe?

Update

I edited the phrasing of the Wikipedia page.

$\endgroup$
4
  • $\begingroup$ I see some weird things such as using "ECB" where I expect "permutation" in the paper that Wikipedia references. It would be interesting if somebody could go over the paper, my math skills are again failing me on some of the text. $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 13:28
  • $\begingroup$ By the way, the NIST reference on Wikipedia is way out of date, here is the latest version... $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 14:03
  • $\begingroup$ The recent edit to Wikipedia added "There is currently no known method to exploit this issue". I concur with that for 128-bit block cipher and a reseeding much before $2^{64}$ blocks, as is the case in Windows. But the text above the addition mentions triple DES, a 64-bit block cipher. It's feasible to detect the issue with triple DES, and whether it's possible to exploit it hinges on the definition of exploit. E.g. if one produces random files with the resulting RNG and pretend they are encrypted video, that could conceivably be disproved! $\endgroup$
    – fgrieu
    Jul 26, 2023 at 15:57
  • $\begingroup$ Ok I changed it again. $\endgroup$
    – Riemann
    Jul 26, 2023 at 22:26

3 Answers 3

2
$\begingroup$

Although the output size of the block cipher is only 128 bits that doesn't mean that the state is only 128 bits; as far as I can see the state is at least keysize + blocksize (K + V). However, more importantly, the Wikipedia page certainly does not indicate that you can only pull 128 bits out of the RNG. It seems to claim that the security offered by the RNG isn't as high as indicated by NIST when the entire output of encrypting the counter block is put into the state. That doesn't mean that the output should be limited to one time the block size.

What I see is that the output of the block cipher is a permutation and that you may create a distinguisher (with a non-neglectable probability) if the full output is used because the 128 bit output will never repeat. This is unlikely to be a practical issue though, you would need a lot of output before the distinguisher can be made, and even then that would not constitute a problem. It is unlikely anyway that you can gather enough data before the RNG decides to reseed (once an hour after it is running for some time).

Here we get into the nitty-gritty of security margins:

  • Is the security 128 bits or less? Yes, because of the distinguisher.
  • Do we ever request enough random data for this to become a problem? No.
  • Would it even be a problem if such a distinguisher can be build? Probably also no.

Would you think it was a problem that you would never win the lottery again with the same number that you used to win it? Well, possibly after you'd won it. Now repeat that same question if the chance is one in $2^{128}$ at best, even if you allow for a lot of lottery winners that may complain.

$\endgroup$
5
  • $\begingroup$ A distinguisher with non-neglectible probability is a bit of a pleonasm I suppose, if it was neglectible it wouldn't be a distinguisher :) $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 13:34
  • $\begingroup$ So if I understand correctly: for AES-256 as the underlying cipher you would expect that a brute force attack costs $O(2^{256})$ time, but actually it costs only $O(2^{128})$ time? And that still seems impossible to me $\endgroup$
    – Riemann
    Jul 26, 2023 at 13:37
  • 1
    $\begingroup$ Brute force to do what? To build a distinguisher or to get the full state? The latter is probably even harder than that - not that it matters at that point of course. In general you should probably worry more about the entropy provided by the system than the DRBG algorithm. Microsoft seems to claim a security level of 256 bits for what that's worth; the whitepaper seems professional enough to me... $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 13:55
  • $\begingroup$ Yes so I can trust the Microsoft RNG. Now the strange part is that the Wikipedia page says ‘and more than 128 bits are taken from this pseudorandom number generator’. Isn’t that a misleading phrase? Maybe it should say ‘and the key size is larger than 128’ $\endgroup$
    – Riemann
    Jul 26, 2023 at 14:23
  • $\begingroup$ No, I think that they mean that if you take say 256 bits then there is no repetition between the first 128 bits and the second 128 bits. If there are 384 bits then there are no repetitions for the three blocks of 128 bits. That means that a distinguisher can be build earlier than after 2^128 blocks. But that will never be a problem even if it lowers security to less than 128 bits. See fgrieu's answer for some calculations. $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 14:41
3
$\begingroup$

Does this mean that the Windows RNG is unsafe?

No. This would be drawing incorrect conclusions from the correct facts stated in a misleading way by the Wikipedia article as it stands now.

Truth is, the combination of the whitepaper and the paper given as reference show that it may exist a mean to distinguish a huge block of data generated by a Windows RNG in a single call, from a truly random block of data, even so slightly better than at random. There is no risk whatsoever that it degenerates into an exploitable vulnerability.

The root of the (non-)issue is that, unless the whitepaper leaves some detail unstated, large blocks of randomness generated by a single call are the output of AES in CTR mode, thus no 128-bit sub-block repeats; when that could happen in true random data.

That's a distinguisher, but it's far from exploitable when we take into consideration that there are limits to the size of data blocks that can be generated in one invocation of the DRBG.

If we assume a 4TiB block (Windows 11 Entreprise can have 6TiB RAM installed), that's $2^{37}$ sub-blocks, thus the probability that a sub-block repeats is close to $2^{2\cdot37-1-128}=2^{-55}$. Thus after $2^{22}$ (>4 million) such attempts with a true RNG, we have probability close to $2^{-33}$ (one against the number of humans now on earth) there is at least one repeat in at least one of the experiments. But that probability is zero if we use the Windows RNG (and it works as I understand from the description).

So if we did that experiment (which would hog many expensive computers for a ridiculous amount of time),

  • If we do not see any repeated block, we should be as surprised as we should be to NOT be picked in a random draw among all humans on the planet. Which is, not surprised at all, and entirely unable to draw any useful conclusion from the expensive experiment.
  • Otherwise, we can safely conclude that the Windows RNG does not work as I thought it does, or that the computer that spotted the match had a failure, or there's some subtle mistake in the code that detects identical sub-blocks (which takes much longer and a little more RAM than generating them).

In either case, there's not the slightest practical security implication when it comes to Window's use of CTR_DRBG, because it uses a 128-bit cipher and reseeds the counter so much before $2^{64}$ blocks are generated.


The paper used as reference aims to show a certificational weakness of NIST's CTR_DRBG, and that NIST was wrong about how it certified it. It's not about drawing any operational conclusion. Except perhaps to not trust NIST recommendations when it comes to random number generator. But that's common sense for one that looks at the volume of these recommendations, or/and at the DUAL_EC_DRBG debacle.

$\endgroup$
0
$\begingroup$

I'm very certain it's a editorial error. Typical CTR-DRBGs instantiated with an 128-bit blockcipher use 32-bit counter, and lets you pull out 4 GiB of data safely before needing to reseed.

$\endgroup$
3
  • $\begingroup$ Would that then be an error in the linked article, or did the Wikipedia editor misinterpret the article? $\endgroup$
    – Riemann
    Jul 26, 2023 at 9:25
  • $\begingroup$ @Riemann I don't see any obvious error in the Microsoft article. Some Wikipedian made the mistake, but it's unknown what the source of the error is. $\endgroup$
    – DannyNiu
    Jul 26, 2023 at 12:26
  • $\begingroup$ The table in NIST SP90A rev 1 has significantly higher values for maximum output; it splits between number of bits per request & number of requests (which makes sense as the output is generated using a separate call to the counter it seems). Personally I would keep well away from those kind of numbers. Windows 10 seems to periodically reseed including calls to RDSEED when available. I don't see any maximum output size, but that's probably OK. $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 13:50

Your Answer

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

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