5 ms·

In case anyone's interested in how Windows behaves for the sake of comparison, see: https://aka.ms/win10rng https://aka.ms/win10rng

zinekeller 5y ago
Note that while CTR_DRBG is totally different from the similar-sounding Dual_EC_DRBG (which is widely suspected of being backdoored), CTR_DRBG has some flaws (being a counter-based design) that allows insecure or secure-but-lower-than-expected-randomness depending on the symmetric cipher used. It seems that it uses AES-256, but depending on whether it takes 224 or 256 bytes of output per round is not discussed on the document (counterintuitively, taking only 224 bytes is slightly more secure than taking the whole 256 bytes). Edit: re-reading the document, it seems to imply (considering the buffer size) that the output they are using is 128 bytes.
- mkj 5y ago
  And the author of this MS paper is who first publicised the potential Dual_EC_DRBG backdoor years before it was outed by Snowden.
  - e40 5y ago
    Outed in what way?
    - zinekeller 5y ago
      On the Possibility of a Back Door in the NIST SP800-90 Dual EC-PRNG (2007, Shumow and Ferguson, https://rump2007.cr.yp.to/15-shumow.pdf https://rump2007.cr.yp.to/15-shumow.pdf)
    - mkj 5y ago
      Outed by the memos he leaked: > Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.” From https://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption https://www.propublica.org/article/the-nsas-secret-campaign-... Or for some other discussion https://blog.cryptographyengineering.com/2015/01/14/hopefully-last-post-ill-ever-write-on/ https://blog.cryptographyengineering.com/2015/01/14/hopefull...
- Aardwolf 5y ago
  How is secure-but-lower-than-expected-randomness actually possible? I thought being indistinguishable from true random is one of the requirements of a CSPRNG
  - zinekeller 5y ago
    > I thought being indistinguishable from true random is one of the requirements of a CSPRNG It's still secure in a way that, for example a cipher that in theory gives you a security guarantee or margin of 160 bits (which means assuming no further reseeding you need around 2^160 bits before losing security guarantees) is reduced to around 128 bits (which means assuming no further reseeding you now only need around 2^128 bits before losing security guarantees). It shouldn't happen in practice (constant reseeding) but some symmetric ciphers paired with CTR_DRBG (Triple DES) makes reading its state a lot easier, especially on systems where they don't frequently reseed (note that this algorithm was invented in the late '90s, so practices now seen as obvious security blunders aren't being avoided).
- loeg 5y ago
  They use a buffer of 128 bytes for small requests. Larger requests come directly from AES_CTR_DRBG: > 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. At least, that's my read of it.
- tptacek 5y ago
  I'm not sure if any of these concerns are really practical. NIST does a great job of making CTR_DRBG sound complicated, but it's pretty close to the simplest possible CSPRNG: it's just a block cipher in CTR mode, which is pretty close to the theoretical simplest secure CSPRNG. It's true that if you use DES-EDE or something with CTR_DRBG, you have all the problems that come from use a short block with CTR mode --- but if you can reason about how to use CTR mode, you can I think reason about the limitations you'll run into with CTR_DRBG. You're not getting insecure randomness from AES CTR_DRBG.
- purkka 5y ago
  AES always has a 128 bit (16 byte) block size; AES-256, AES-192 and AES-128 only change the key size. (Also, the 128-byte buffer therefore contains 8 blocks; I believe the size is chosen more for performance than security reasons.)
belter 5y ago
I know Microsoft claims to have corrected many of the issues raised here but do they have a formal response to it? Do we even care? Cryptanalysis of the Random Number Generator of the Windows Operating System https://eprint.iacr.org/2007/419.pdf https://eprint.iacr.org/2007/419.pdf Cryptanalysis of the Windows Random Number Generator https://www.cs.huji.ac.il/~dolev/pubs/thesis/msc-thesis-leo.pdf https://www.cs.huji.ac.il/~dolev/pubs/thesis/msc-thesis-leo....
- zinekeller 5y ago
  They acknowledged that the Windows 2000 design was also used in XP (https://www.computerworld.com/article/2539986/microsoft-confirms-that-xp-contains-random-number-generator-bug.html https://www.computerworld.com/article/2539986/microsoft-conf...), but Vista and above used NIST algorithms defaulting to CTR_DRBG, although the problematic Dual_EC_DRBG (which was flagged by their own cryptographers as problematic: https://rump2007.cr.yp.to/15-shumow.pdf https://rump2007.cr.yp.to/15-shumow.pdf) was present until the Snowden revelations. Windows 10's (and 11 and probably above) implementation of CTR_DBRG is different from Vista-8 though, mainly in the entropy generation and the switch from AES-128 to AES-256.
- loeg 5y ago
  The 2007 papers predate the Win10 design linked by the grandparent comment. I haven't read the 2007 criticisms recently, but have read the Win10 design many times. I don't think there's anything objectionable in the current design. Edit: I guess the criticism about the generator running in user mode is still true, although I don't think it's the flaw the authors do. Also, I think the current design adds forward-secrecy / key erasure vs the criticism mentioned in the 2007 paper. I believe the O(2^23) attack described is gone now.
- tptacek 5y ago
  It's a good paper, but note that this is an attack on the (old) per-process RC4-based WRNG, not on CTR_DRBG. The attack essentially observes that if you get RCE on a Windows process and capture the WRNG state, you can get all previous and future states bounded by when the per-process WRNG reseeds (the seeding process reads random bytes from KSecDD, a sort of Windows equivalent of /dev/random). The Windows design is interesting in that it runs a userland CSPRNG for each process, rather than a single kernel RNG like Linux/Unix provides, but still binds those RNGs to the kernel RNG. This seems like a good idea at first, but turns out not to be: the attack wouldn't be possible if KSecDD was the entire CSPRNG interface for Windows.

zinekeller 5y ago

Note that while CTR_DRBG is totally different from the similar-sounding Dual_EC_DRBG (which is widely suspected of being backdoored), CTR_DRBG has some flaws (being a counter-based design) that allows insecure or secure-but-lower-than-expected-randomness depending on the symmetric cipher used. It seems that it uses AES-256, but depending on whether it takes 224 or 256 bytes of output per round is not discussed on the document (counterintuitively, taking only 224 bytes is slightly more secure than taking the whole 256 bytes). Edit: re-reading the document, it seems to imply (considering the buffer size) that the output they are using is 128 bytes.

mkj 5y ago
And the author of this MS paper is who first publicised the potential Dual_EC_DRBG backdoor years before it was outed by Snowden.
- e40 5y ago
  Outed in what way?
  - zinekeller 5y ago
    On the Possibility of a Back Door in the NIST SP800-90 Dual EC-PRNG (2007, Shumow and Ferguson, https://rump2007.cr.yp.to/15-shumow.pdf https://rump2007.cr.yp.to/15-shumow.pdf)
  - mkj 5y ago
    Outed by the memos he leaked: > Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.” From https://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption https://www.propublica.org/article/the-nsas-secret-campaign-... Or for some other discussion https://blog.cryptographyengineering.com/2015/01/14/hopefully-last-post-ill-ever-write-on/ https://blog.cryptographyengineering.com/2015/01/14/hopefull...
Aardwolf 5y ago
How is secure-but-lower-than-expected-randomness actually possible? I thought being indistinguishable from true random is one of the requirements of a CSPRNG
- zinekeller 5y ago
  > I thought being indistinguishable from true random is one of the requirements of a CSPRNG It's still secure in a way that, for example a cipher that in theory gives you a security guarantee or margin of 160 bits (which means assuming no further reseeding you need around 2^160 bits before losing security guarantees) is reduced to around 128 bits (which means assuming no further reseeding you now only need around 2^128 bits before losing security guarantees). It shouldn't happen in practice (constant reseeding) but some symmetric ciphers paired with CTR_DRBG (Triple DES) makes reading its state a lot easier, especially on systems where they don't frequently reseed (note that this algorithm was invented in the late '90s, so practices now seen as obvious security blunders aren't being avoided).
loeg 5y ago
They use a buffer of 128 bytes for small requests. Larger requests come directly from AES_CTR_DRBG: > 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. At least, that's my read of it.
tptacek 5y ago
I'm not sure if any of these concerns are really practical. NIST does a great job of making CTR_DRBG sound complicated, but it's pretty close to the simplest possible CSPRNG: it's just a block cipher in CTR mode, which is pretty close to the theoretical simplest secure CSPRNG. It's true that if you use DES-EDE or something with CTR_DRBG, you have all the problems that come from use a short block with CTR mode --- but if you can reason about how to use CTR mode, you can I think reason about the limitations you'll run into with CTR_DRBG. You're not getting insecure randomness from AES CTR_DRBG.
purkka 5y ago
AES always has a 128 bit (16 byte) block size; AES-256, AES-192 and AES-128 only change the key size. (Also, the 128-byte buffer therefore contains 8 blocks; I believe the size is chosen more for performance than security reasons.)

belter 5y ago

I know Microsoft claims to have corrected many of the issues raised here but do they have a formal response to it? Do we even care? Cryptanalysis of the Random Number Generator of the Windows Operating System https://eprint.iacr.org/2007/419.pdf https://eprint.iacr.org/2007/419.pdf Cryptanalysis of the Windows Random Number Generator https://www.cs.huji.ac.il/~dolev/pubs/thesis/msc-thesis-leo.pdf https://www.cs.huji.ac.il/~dolev/pubs/thesis/msc-thesis-leo....

zinekeller 5y ago
They acknowledged that the Windows 2000 design was also used in XP (https://www.computerworld.com/article/2539986/microsoft-confirms-that-xp-contains-random-number-generator-bug.html https://www.computerworld.com/article/2539986/microsoft-conf...), but Vista and above used NIST algorithms defaulting to CTR_DRBG, although the problematic Dual_EC_DRBG (which was flagged by their own cryptographers as problematic: https://rump2007.cr.yp.to/15-shumow.pdf https://rump2007.cr.yp.to/15-shumow.pdf) was present until the Snowden revelations. Windows 10's (and 11 and probably above) implementation of CTR_DBRG is different from Vista-8 though, mainly in the entropy generation and the switch from AES-128 to AES-256.
loeg 5y ago
The 2007 papers predate the Win10 design linked by the grandparent comment. I haven't read the 2007 criticisms recently, but have read the Win10 design many times. I don't think there's anything objectionable in the current design. Edit: I guess the criticism about the generator running in user mode is still true, although I don't think it's the flaw the authors do. Also, I think the current design adds forward-secrecy / key erasure vs the criticism mentioned in the 2007 paper. I believe the O(2^23) attack described is gone now.
tptacek 5y ago
It's a good paper, but note that this is an attack on the (old) per-process RC4-based WRNG, not on CTR_DRBG. The attack essentially observes that if you get RCE on a Windows process and capture the WRNG state, you can get all previous and future states bounded by when the per-process WRNG reseeds (the seeding process reads random bytes from KSecDD, a sort of Windows equivalent of /dev/random). The Windows design is interesting in that it runs a userland CSPRNG for each process, rather than a single kernel RNG like Linux/Unix provides, but still binds those RNGs to the kernel RNG. This seems like a good idea at first, but turns out not to be: the attack wouldn't be possible if KSecDD was the entire CSPRNG interface for Windows.