5 ms·

One of the vulnerabilities was already discovered by researchers in 2007: http://rump2007.cr.yp.to/15-shumow.pdf http://rump2007.cr.yp.to/15-shumow.pdf At the

by lambda 13y ago

One of the vulnerabilities was already discovered by researchers in 2007: http://rump2007.cr.yp.to/15-shumow.pdf http://rump2007.cr.yp.to/15-shumow.pdf At the time, it wasn't clear if this was a deliberate backdoor or an accident, but it was proven that there there was a possibility that there was a secret key that would allow someone to predict future values of a pseudo random number generator based on previous values. Now it looks pretty clear that it was a deliberate backdoor. This really reduces trust in US based cryptographic standards. And US based cryptographic hardware, as they mention in the article that they convinced hardware manufacturers to insert backdoors for hardware shipped overseas.

tptacek 13y ago
This is almost definitely not "one of the vulnerabilities" implicated in the story today, because nobody uses CSPRNGs based on Elliptic Curve.
- andrewcooke 13y ago
  so what was the vulnerability found by ms in 2007 that they are referring to? (search for 2007 in single page version at http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?_r=0&pagewanted=all http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet...) edit: reading in more detail around there, i am pretty sure that section of the article is referring to the CSPRNG vulnerability above. the article covers a lot of ground and not all of it is about problems with ssl. that particular section seems to be arguing that the nsa is trying to put backdoors into standards wherever it can.
  - tptacek 13y ago
    I don't know. I'm just saying, weakening a CSPRNG design that nobody uses or is ever likely to use (it's extremely expensive) is not a particularly meaningful action.
    - stingraycharles 13y ago
      Not a crypto expert at all, but did they knew in advance that nobody would use it? Otherwise it could just be a failed attempt.
      - tptacek 13y ago
        I don't know what they expected, but Dual-EC is self-evidently noncompetitive.
    - lambda 13y ago
      It sounds an awful lot like that's the one the New York times was describing. Can you think of any other standard that was published in 2006 by NIST which two Microsoft researchers discovered a flaw in in 2007? That sounds exactly like Dual_EC_DRBG > Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method. > Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology, the United States’ encryption standards body, 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.” > “Eventually, N.S.A. became the sole editor,” the memo says. Now, that may not have been an effective technique, as you point out it's so slow that no one is ever going to use it, and this vulnerability was discovered not long after it was published. So, that's obviously not a vulnerability that they are actively exploiting. If they are actively exploiting a vulnerability that they introduced, it must be something else. It wasn't clear from the article that that's actually the case; it may be that the vulnerabilities they are exploiting are ones they've found, not introduced deliberately. But it does appear to be an example of a vulnerability that they were able to get standardized, in the hopes of being able to exploit it. Until now, it has been only speculation that it was a deliberate vulnerability, but it now seems clear that it was.
- rst 13y ago
  Nobody uses them because they came out of the NSA with little precedent in the open literature, and independent analysis quickly uncovered this vulnerability.
  - tptacek 13y ago
    Also nobody used it because it's a CSPRNG that requires bignum multiplication.
- mindslight 13y ago
  A RNG that is reducible to a different believed-hard problem has possible features, so it's not like there could never be a reason for someone to choose this generator. What we could be seeing is the discovery of one failed attempt of a shotgun approach to promulgate insecure primitives. It's hard to know what will happen to become commercially successful, so spray and pray. Something this blatant does seem like a severe misstep, but perhaps what led to discovery of this case is the wide body of public knowledge on number theoretic crypto. The energy of the public sphere seems mostly devoted to studying problems with interesting mathematical structure. Symmetric crypto has been around a lot longer, and is sufficient for state security purposes, so one would expect the NSA to have a deep analytic understanding of it (hence the differential analysis olive branch). It's not hard to imagine that they'd have ways of creating trapdoor functions out of bit primitives, generating favorable numbers with plausibly-impartial explanations, etc.
  - wfunction 13y ago
    > A RNG that is reducible to a different believed-hard problem has possible features I think you got it backwards... shouldn't you reduce hard problems down to the problem whose difficulty you're trying to understand?
    - mindslight 13y ago
      Yep, I misspoke. I simply meant 'is based on', and shouldn't have used big words so cavalierly.

by lambda 13y ago

tptacek 13y ago

This is almost definitely not "one of the vulnerabilities" implicated in the story today, because nobody uses CSPRNGs based on Elliptic Curve.

andrewcooke 13y ago
so what was the vulnerability found by ms in 2007 that they are referring to? (search for 2007 in single page version at http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?_r=0&pagewanted=all http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet...) edit: reading in more detail around there, i am pretty sure that section of the article is referring to the CSPRNG vulnerability above. the article covers a lot of ground and not all of it is about problems with ssl. that particular section seems to be arguing that the nsa is trying to put backdoors into standards wherever it can.
- tptacek 13y ago
  I don't know. I'm just saying, weakening a CSPRNG design that nobody uses or is ever likely to use (it's extremely expensive) is not a particularly meaningful action.
  - stingraycharles 13y ago
    Not a crypto expert at all, but did they knew in advance that nobody would use it? Otherwise it could just be a failed attempt.
    - tptacek 13y ago
      I don't know what they expected, but Dual-EC is self-evidently noncompetitive.
  - lambda 13y ago
    It sounds an awful lot like that's the one the New York times was describing. Can you think of any other standard that was published in 2006 by NIST which two Microsoft researchers discovered a flaw in in 2007? That sounds exactly like Dual_EC_DRBG > Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method. > Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology, the United States’ encryption standards body, 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.” > “Eventually, N.S.A. became the sole editor,” the memo says. Now, that may not have been an effective technique, as you point out it's so slow that no one is ever going to use it, and this vulnerability was discovered not long after it was published. So, that's obviously not a vulnerability that they are actively exploiting. If they are actively exploiting a vulnerability that they introduced, it must be something else. It wasn't clear from the article that that's actually the case; it may be that the vulnerabilities they are exploiting are ones they've found, not introduced deliberately. But it does appear to be an example of a vulnerability that they were able to get standardized, in the hopes of being able to exploit it. Until now, it has been only speculation that it was a deliberate vulnerability, but it now seems clear that it was.
rst 13y ago
Nobody uses them because they came out of the NSA with little precedent in the open literature, and independent analysis quickly uncovered this vulnerability.
- tptacek 13y ago
  Also nobody used it because it's a CSPRNG that requires bignum multiplication.
mindslight 13y ago
A RNG that is reducible to a different believed-hard problem has possible features, so it's not like there could never be a reason for someone to choose this generator. What we could be seeing is the discovery of one failed attempt of a shotgun approach to promulgate insecure primitives. It's hard to know what will happen to become commercially successful, so spray and pray. Something this blatant does seem like a severe misstep, but perhaps what led to discovery of this case is the wide body of public knowledge on number theoretic crypto. The energy of the public sphere seems mostly devoted to studying problems with interesting mathematical structure. Symmetric crypto has been around a lot longer, and is sufficient for state security purposes, so one would expect the NSA to have a deep analytic understanding of it (hence the differential analysis olive branch). It's not hard to imagine that they'd have ways of creating trapdoor functions out of bit primitives, generating favorable numbers with plausibly-impartial explanations, etc.
- wfunction 13y ago
  > A RNG that is reducible to a different believed-hard problem has possible features I think you got it backwards... shouldn't you reduce hard problems down to the problem whose difficulty you're trying to understand?
  - mindslight 13y ago
    Yep, I misspoke. I simply meant 'is based on', and shouldn't have used big words so cavalierly.