7 ms·

NIST reopens draft recommendation on random number generation for comment [pdf]

140 points by healsjnr1 13y ago

Wingman4l7 13y ago
For those curious (as I was) as to what the heck that title means, the press release linked deals with The National Institute of Standards and Technology (NIST) and what kind of random number generators (RNGs) they recommend using.
- seldo 13y ago
  Agreed, a rewording of the title to something a little more accessible would not go amiss.
  - nitrogen 13y ago
    The terms EC-DRBG and NIST have come up quite a bit lately on HN with regards to the NSA, so it's not unreasonable to use them to ensure a descriptive title fits in the 80 characters allotted. The other cryptic term, SP800-90a, looks like the issue number of an official standard, like ISO-8859 or EIA/TIA-568.
- deleted 13y ago
  [deleted]
lifthrasiir 13y ago
Background: https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG > Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. [...] Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor.
- clarkm 13y ago
  Which seems to be confirmed by Snowden's leaks, according to the NYT article from earlier this week. > Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members. 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." Bottom of page 3: http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=3&_r=0 http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet...
- tptacek 13y ago
  It's an awfully weird trojan horse --- or, as Daniel Franke put it on Twitter, a trojan platypus. First: NIST RNG designs aren't particularly important (unlike the curve standards); there is a broad diversity of CSPRNG designs, applications tend to "borrow" the OS's, and no OS I know of uses a design taken directly from NIST. Second: Dual EC DRBG is a CSPRNG that uses elliptic curve point multiplications; in other words, it requires bignum math. If you're unfamiliar with CSPRNG design: that's not a normal requirement. Dual EC is very slow. Nobody would willingly use it. Why would that be the big NSA standard back door? I'm not saying it isn't. Something hinky happened there. I'm just asking: what did they have to gain from trying to backdoor that standard?
  - H3g3m0n 13y ago
    > applications tend to "borrow" the OS's, and no OS I know of uses a design taken directly from NIST. Windows has support for it (although it's up to applications to choose to use it or not). If it's part of a standard then it might be required by some organisations. For example other government/military agencies and people dealing with them. They could also look to pass laws to require corporations protect their customers private data using the standard. And just have people recommend the standard to everyone, after all was designed by NIST/NSA. It's also likely to end up in software that wants to support those use cases which could have seen it filter out to other uses. And possibly hardware support. If the potential for a backdoor hadn't been discovered people wouldn't have objected/noticed. > Dual EC is very slow. Nobody would willingly use it. Which leaves the question of why it would end up in the NIST standard if it's not very good. Of course maybe they where just testing the waters.
  - anologwintermut 13y ago
    Prior to this(or maybe Crypto 2007 where the suspicions were first aired), would you have have batted an eye if you saw Dual_EC_DRBG in a code base with some configuration bit for which NIST RNG you used? Messing with the standard gets a backdoored RNG onto almost every system. Now NSA just has to convince companies to use it( and it's a NIST standard, so the company has some deniability) or surreptitiously swap it out. Microsoft's CNG api has a default random number generator. How hard would it be to detect if that default was switched to BCRYPT_RNG_DUAL_EC_ALGORITHM for say, all windows copies sent to Iran or China?
lmgftp 13y ago
It should probably be noted that this is not some sort of validation to the fact that "the NSA owns this particular DRBG". Surprisingly (to me), this is merely a signal of a government agency that takes public perception to heart and issues a vote of not-complete-confidence in standards it has previous prescribed, and today is seeking to rectify the problem by looking for nothing up my sleeve numbers [0] agreed upon by security researchers and the public at large. A smart move, no doubt a difficult one to make, as even the slightest suggestion of no-confidence in a prescribed standard is quite damaging to the reputation of an institution devoted to maintaining reliable standards. More info on nothing-up-my-sleeve: [0] http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
- semenko 13y ago
  Sure, but the Times piece /very strongly/ suggests it: http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/ http://bits.blogs.nytimes.com/2013/09/10/government-announce... (Perlroth quotes from a few unpublished, leaked memos.)
- tlrobinson 13y ago
  Somewhat off topic, but it seems like it would be better to use some future unpredictable events to really remove any "nothing up my sleeve" doubt. e.x. hash of the sum of all S&P 500 companies' closing stock prices on a specific future date.
  - rspeer 13y ago
    I assume you need some flexibility in choosing a nothing-up-my-sleeve number, in case the first number you try has properties that are bad for the algorithm. Imagine if the super-official, international standard nothing-up-my-sleeve number was 1. Any time you need consistent but arbitrary bits in a cryptographic algorithm, they must be ...000000000000001. That doesn't sound like it would work very well.
    - johnsoft 13y ago
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]
pdknsk 13y ago
This should be upvoted instead, as it provides context, and also links to this PDF (or its official announcement). https://news.ycombinator.com/item?id=6364340 https://news.ycombinator.com/item?id=6364340 Or to provide minimum context, the announcement should've been submitted instead. http://nist.gov/director/cybersecuritystatement-091013.cfm http://nist.gov/director/cybersecuritystatement-091013.cfm
cromwellian 13y ago
I doubt the NIST will ever be trusted again as any standards or specs they are in favor of will be immediately suspected of having some favorable vulnerability for the NSA. Let's say they hold a contest for people to submit next generation cryptosystems, and that Algorithms A,B, and C make it to the final. If the NIST publishes critical remarks on A and C and seems to favor B, immediate skepticism and red flags will be raised. Does B have a hidden weakness the NSA knows about? A standards organization can only run on its transparency and integrity.
- tptacek 13y ago
  First, a lot of NIST crypto standards are relatively anodyne; for instance, the NIST GCM standard basically just explains how to do multiplication in GF(2^128), and the NIST CTR mode standard just lays out a bunch of ways you can arrange your counter block. Those standards remain valuable and aren't likely to harbor backdoors. Second, it has always been the case that favorable responses from the USG in general and NSA in particular have cast a pall over proposed standards. Isn't that why there's a RIPEMD160, for instance?
  - cromwellian 13y ago
    There has always been suspicion, but nothing close to proof. Now that there is close to proof that the NSA has been inserting weaknesses for themselves (unlike the DES S-Box modifications they made which actually strengthened it) The Clipper proposal seemed to suggest the NIST/NSA was interested in strong cryptosystems with explicit, transparent backdoors, and they also had the export limitations, so many non-conspiracy theory people assumed the NSA was more interested in cryptanalyzing foreign communications and keeping our domestic cryptosystems out of foreign hands. What used to be long held cryptoanarchist conspiracy theories are no longer so far fetched, as now the NIST/NSA is more concerned with targeting the existing communication networks of friendly western democracies/domestic intercept, on which terrorists may piggyback, instead of foreign non-aligned powers. That is, the greatest threat is no longer foreign comm networks and cryptosystems, but domestic. We have become the adversary. Anyway, what do you call AES? It was selected as the winner by the NIST and it has widespread industry adoption.
marshray 13y ago
Here's my comment: This is the dumbest PRNG ever.
- mpyne 13y ago
  Look up RANDU.
  - marshray 13y ago
    RANDU didn't claim to be cryptographically secure.
    - mpyne 13y ago
      Oh. Well, in that case look up Debian's OpenSSL from a few years ago.
      - marshray 13y ago
        Debian's OpenSSL was a perfectly good PSEUDO RNG a.k.a. DRBG
        mpyne 13y ago
        But it claimed to be a cryptographically secure one. And I'm pretty sure even the NSA-adjusted EC PRNG standardized by NIST offers more than 15 bits of security.
        marshray 13y ago
        Debain's broken OpenSSL claimed to be a cryptographically secure true random number generator (CSRNG). But it ended up being seeded with only 15 bits of entropy, so it failed in the true random part. Nevertheless, the pseudorandom number generator (CSPRNG, or as NIST calls it a DRBG) part of it still sorta worked (I don't recall if you could successfully seed it manually). But regardless of how you were planning to use it, if an adversary has a backdoor in your PRNG/DRBG then it's not cryptographically secure (CS). That, and this Dual EC contraption is probably much slower than a conventional design.
brokenparser 13y ago
Can anyone provide a mirror, please?

140 points by healsjnr1 13y ago

For those curious (as I was) as to what the heck that title means, the press release linked deals with The National Institute of Standards and Technology (NIST) and what kind of random number generators (RNGs) they recommend using.

seldo 13y ago
Agreed, a rewording of the title to something a little more accessible would not go amiss.
- nitrogen 13y ago
  The terms EC-DRBG and NIST have come up quite a bit lately on HN with regards to the NSA, so it's not unreasonable to use them to ensure a descriptive title fits in the 80 characters allotted. The other cryptic term, SP800-90a, looks like the issue number of an official standard, like ISO-8859 or EIA/TIA-568.
deleted 13y ago
[deleted]

lifthrasiir 13y ago

Background: https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG > Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. [...] Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor.

clarkm 13y ago
Which seems to be confirmed by Snowden's leaks, according to the NYT article from earlier this week. > Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members. 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." Bottom of page 3: http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=3&_r=0 http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet...
tptacek 13y ago
It's an awfully weird trojan horse --- or, as Daniel Franke put it on Twitter, a trojan platypus. First: NIST RNG designs aren't particularly important (unlike the curve standards); there is a broad diversity of CSPRNG designs, applications tend to "borrow" the OS's, and no OS I know of uses a design taken directly from NIST. Second: Dual EC DRBG is a CSPRNG that uses elliptic curve point multiplications; in other words, it requires bignum math. If you're unfamiliar with CSPRNG design: that's not a normal requirement. Dual EC is very slow. Nobody would willingly use it. Why would that be the big NSA standard back door? I'm not saying it isn't. Something hinky happened there. I'm just asking: what did they have to gain from trying to backdoor that standard?
- H3g3m0n 13y ago
  > applications tend to "borrow" the OS's, and no OS I know of uses a design taken directly from NIST. Windows has support for it (although it's up to applications to choose to use it or not). If it's part of a standard then it might be required by some organisations. For example other government/military agencies and people dealing with them. They could also look to pass laws to require corporations protect their customers private data using the standard. And just have people recommend the standard to everyone, after all was designed by NIST/NSA. It's also likely to end up in software that wants to support those use cases which could have seen it filter out to other uses. And possibly hardware support. If the potential for a backdoor hadn't been discovered people wouldn't have objected/noticed. > Dual EC is very slow. Nobody would willingly use it. Which leaves the question of why it would end up in the NIST standard if it's not very good. Of course maybe they where just testing the waters.
- anologwintermut 13y ago
  Prior to this(or maybe Crypto 2007 where the suspicions were first aired), would you have have batted an eye if you saw Dual_EC_DRBG in a code base with some configuration bit for which NIST RNG you used? Messing with the standard gets a backdoored RNG onto almost every system. Now NSA just has to convince companies to use it( and it's a NIST standard, so the company has some deniability) or surreptitiously swap it out. Microsoft's CNG api has a default random number generator. How hard would it be to detect if that default was switched to BCRYPT_RNG_DUAL_EC_ALGORITHM for say, all windows copies sent to Iran or China?

lmgftp 13y ago

It should probably be noted that this is not some sort of validation to the fact that "the NSA owns this particular DRBG". Surprisingly (to me), this is merely a signal of a government agency that takes public perception to heart and issues a vote of not-complete-confidence in standards it has previous prescribed, and today is seeking to rectify the problem by looking for nothing up my sleeve numbers [0] agreed upon by security researchers and the public at large. A smart move, no doubt a difficult one to make, as even the slightest suggestion of no-confidence in a prescribed standard is quite damaging to the reputation of an institution devoted to maintaining reliable standards. More info on nothing-up-my-sleeve: [0] http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

semenko 13y ago
Sure, but the Times piece /very strongly/ suggests it: http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/ http://bits.blogs.nytimes.com/2013/09/10/government-announce... (Perlroth quotes from a few unpublished, leaked memos.)
tlrobinson 13y ago
Somewhat off topic, but it seems like it would be better to use some future unpredictable events to really remove any "nothing up my sleeve" doubt. e.x. hash of the sum of all S&P 500 companies' closing stock prices on a specific future date.
- rspeer 13y ago
  I assume you need some flexibility in choosing a nothing-up-my-sleeve number, in case the first number you try has properties that are bad for the algorithm. Imagine if the super-official, international standard nothing-up-my-sleeve number was 1. Any time you need consistent but arbitrary bits in a cryptographic algorithm, they must be ...000000000000001. That doesn't sound like it would work very well.
  - johnsoft 13y ago

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]

pdknsk 13y ago

This should be upvoted instead, as it provides context, and also links to this PDF (or its official announcement). https://news.ycombinator.com/item?id=6364340 https://news.ycombinator.com/item?id=6364340 Or to provide minimum context, the announcement should've been submitted instead. http://nist.gov/director/cybersecuritystatement-091013.cfm http://nist.gov/director/cybersecuritystatement-091013.cfm

cromwellian 13y ago

I doubt the NIST will ever be trusted again as any standards or specs they are in favor of will be immediately suspected of having some favorable vulnerability for the NSA. Let's say they hold a contest for people to submit next generation cryptosystems, and that Algorithms A,B, and C make it to the final. If the NIST publishes critical remarks on A and C and seems to favor B, immediate skepticism and red flags will be raised. Does B have a hidden weakness the NSA knows about? A standards organization can only run on its transparency and integrity.

tptacek 13y ago
First, a lot of NIST crypto standards are relatively anodyne; for instance, the NIST GCM standard basically just explains how to do multiplication in GF(2^128), and the NIST CTR mode standard just lays out a bunch of ways you can arrange your counter block. Those standards remain valuable and aren't likely to harbor backdoors. Second, it has always been the case that favorable responses from the USG in general and NSA in particular have cast a pall over proposed standards. Isn't that why there's a RIPEMD160, for instance?
- cromwellian 13y ago
  There has always been suspicion, but nothing close to proof. Now that there is close to proof that the NSA has been inserting weaknesses for themselves (unlike the DES S-Box modifications they made which actually strengthened it) The Clipper proposal seemed to suggest the NIST/NSA was interested in strong cryptosystems with explicit, transparent backdoors, and they also had the export limitations, so many non-conspiracy theory people assumed the NSA was more interested in cryptanalyzing foreign communications and keeping our domestic cryptosystems out of foreign hands. What used to be long held cryptoanarchist conspiracy theories are no longer so far fetched, as now the NIST/NSA is more concerned with targeting the existing communication networks of friendly western democracies/domestic intercept, on which terrorists may piggyback, instead of foreign non-aligned powers. That is, the greatest threat is no longer foreign comm networks and cryptosystems, but domestic. We have become the adversary. Anyway, what do you call AES? It was selected as the winner by the NIST and it has widespread industry adoption.

marshray 13y ago

Here's my comment: This is the dumbest PRNG ever.

mpyne 13y ago
Look up RANDU.
- marshray 13y ago
  RANDU didn't claim to be cryptographically secure.
  - mpyne 13y ago
    Oh. Well, in that case look up Debian's OpenSSL from a few years ago.
    - marshray 13y ago
      Debian's OpenSSL was a perfectly good PSEUDO RNG a.k.a. DRBG
      - mpyne 13y ago
        But it claimed to be a cryptographically secure one. And I'm pretty sure even the NSA-adjusted EC PRNG standardized by NIST offers more than 15 bits of security.
        marshray 13y ago
        Debain's broken OpenSSL claimed to be a cryptographically secure true random number generator (CSRNG). But it ended up being seeded with only 15 bits of entropy, so it failed in the true random part. Nevertheless, the pseudorandom number generator (CSPRNG, or as NIST calls it a DRBG) part of it still sorta worked (I don't recall if you could successfully seed it manually). But regardless of how you were planning to use it, if an adversary has a backdoor in your PRNG/DRBG then it's not cryptographically secure (CS). That, and this Dual EC contraption is probably much slower than a conventional design.

brokenparser 13y ago

Can anyone provide a mirror, please?