10 ms·
Did NSA Put a Secret Backdoor in New Encryption Standard? (2007)
- delinka 14y ago"In the meantime, both NIST and the NSA have some explaining to do." Not happening. Hasn't yet, nor will it. NSA just keeps quite and watches for someone to use their particular algorithm. We should assume malicious intent and take Schneier's advice: "My recommendation, if you're in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances." And if you "don't have anything to hide," then I propose you've given up already and cryptography is useless to you.
- lmm 14y agoNot entirely. While the best cryptography is that which is secure against everyone (duh), there are a vast number of perfectly legitimate use cases for cryptography where it doesn't matter if the NSA can read your encrypted data.
- tych0 14y agoAre there? If I knew something had a backdoor, I'd always wonder who else has figured it out.
- delinka 14y agoI'd rather err on the side of keeping them in the dark all the time. Encrypting data differently based on whether I mind if NSA sees it leaks information. Specifically, that this data doesn't matter but that data does and NSA should focus their efforts on breaking that data or analyzing that social graph affiliated with the data.
- nathan_long 14y agoI can't imagine any legitimate use case for crappy cryptography, and any crypto with a backdoor is crappy. If the door is there, anyone with the key can open it. How can you be sure who will get the key, or what their motives will be? Good, modern cryptography offers a level of security unparalleled in the physical world, and at a processing cost which any computer can handle. Why would you intentionally choose something inferior?
- lmm 14y ago>How can you be sure who will get the key, or what their motives will be? You can never be infinitely certain, but nor can you be certain your non-backdoored crypto is secure. There are cases where "the NSA leaks their top-secret backdoor to the internet" is a vanishingly small threat vector compared to other possibilities (e.g. rubber hoses). >Good, modern cryptography offers a level of security unparalleled in the physical world, and at a processing cost which any computer can handle. Why would you intentionally choose something inferior? You wouldn't. But if it later turns out the NSA has a backdoor in the algorithm you happened to pick, and for whatever reason you're unable or unwilling to change algorithms now, that still doesn't mean "you've given up already and cryptography is useless to you".
- nathan_long 14y ago> You can never be infinitely certain, but nor can you be certain your non-backdoored crypto is secure. True. But "is this algorithm crackable?" is a question that can be answered with experimentation and math. "Has the NSA lost its keys or its scruples, and if not, will they ever?" cannot be answered at all until you know you've been hacked. > But if it later turns out the NSA has a backdoor in the algorithm you happened to pick, and for whatever reason you're unable or unwilling to change algorithms now, that still doesn't mean "you've given up already and cryptography is useless to you". Maybe not, but it does mean you value something else more than you value security. Yes, everyone makes cost/benefit decisions about security. But if your answer to "whoops, whoever knows this trick can see all our bank transactions" is "meh, it would take like, a week to fix that," you're placing a pretty low value on security.
- DanBC 14y agoThe example often given is "MILITARY GRADE ENCRYPTION" - if tank driver Bob is given commands to shell a target those commands only need to be secret for a short length of time. It doesn't matter if the enemy can decrypt them by taking a week's time, because Bob will have attacked the target and gone by then. This is, obviously, a really old example, because modern hardware makes encrypting things quick and easy, and decrypting things quick and easy. But imagine strong encryption in the 1980s - you had to balance strength with time with size and then try to cram it into low-specced hardware.
- tptacek 14y agoYou don't have to take Schneier's advice in order to not end up with an elliptic curve random number generator. Nobody does that anyways.
- NegativeK 14y agoCan you elaborate on why?
- _exec 14y agoI'm curious as well. Why not?
- tptacek 14y ago'pbsd gave a much better answer than I could have.
- pbsd 14y ago1 - Very slow 2 - A nightmare to implement securely 3 - Only exists for the sake of provable security 4 - The same standard defines a much better alternative pseudorandom generators based on hashes and/or block ciphers.
- marshray 14y agoWhich raises the question of why such a useless thing was even standardized in the first place.
- fusiongyro 14y agoFrom that perspective, one wonders if they are instead aware of attacks on the other three and designed the fourth to withstand those attacks (but look suspicious and be unappealingly slow). Overall, the mental game is quite taxing, so I'm going to plead "bureaucracy."
- 14y ago
- lucaspiller 14y agoInteresting... Was there any code written to demonstrate the attack?
- delinka 14y agoThat's a good question. I suspect if so, it was alongside an academic paper and this stuff just doesn't get attention from journalists. I'd be curious to find out but I don't have the skills to pore over the material myself.
- danielweber 14y agoDo you really think "academic finds back door in NSA's random number generator" wouldn't get headlines? Remember how people freaked over the mere mention of the name of "NSAKEY" freaked everyone out?
- pbsd 14y agoNo. The backdoor relies on the generator of the parameters (presumably the NSA) knowing a discrete logarithm ahead of time. Anyone outside the NSA would have to break a rather large discrete logarithm, which is just not gonna happen anytime soon.
- gmoore 14y agoNot exactly current - the article is something like 5 years old....
- delinka 14y agoYou'll notice the "[2007]" in the post title.
- jimktrains2 14y agoApparently the mods added it later. There really should be some way to tell what the mods have and haven't done.
- SquareWheel 14y agoSomething like mouse-over for original title would be great.
- antidoh 14y agoExcellent idea. I just submitted the feature request: https://news.ycombinator.com/item?id=4580886 https://news.ycombinator.com/item?id=4580886
- camiller 14y agoYeah, I started reading it and thought gee this sounds familiar.
- tptacek 14y agoNobody used this random number generator.
- javert 14y agoPerhaps the government required defense contractors to use this one in products sold to other countries? I don't have any evidence for that, just speculation on one reason the NSA might insist on including something like this in the spec.
- anonymouz 14y agoThis is quite interesting, as the NSA on the one hand needs to provide secure algorithms for the public to use, but on the other hand has an interest in being able to break algorithms. IIRC, during the standarization of DES, the NSA has also modified some S-Boxes without giving any explanation. Only later, when differential cryptoanalysis became known to the public, it was clear that this was to strengthen DES against this particular attack (which was already known to the NSA). The case here is more interesting though: It seems like you need to know some secret numbers (a sort of "private key" if you will) to be able to attack the PRNG. So it seems that the NSA could place a "safe" backdoor that even an attacker with the same cryptography knowledge as they have cannot break unless he himself possesses the "private key".
- tptacek 14y agoWhat sense does it make to backdoor an RNG that no normal system is ever going to use, and to do so in a public standard, and further to do so by using deliberately broken curve parameters? It was an interesting story because it was so weird. But even had Dual EC not become known to the world exclusively as "the CSPRNG with the backdoor in it", nobody would have used it anyways.
- anonymouz 14y agoYeah that is rather weird. A botched attempt maybe?
- tptacek 14y agoNo.
- Nikker 14y agoSince many of these procedures are implemented in hardware directly, maybe it could be utilized as a conditional fall-back? An example might be a MITM attack that indicates an invalid hand shake or shows that an insufficient random pool is detected so it would attempt to connect using each alternative in order till it gets to the weak link. Technically speaking this would be ideal since the government and ISP's that carry these messages are so intertwined that the breadth would cover every citizen in their own country and likely many others.
- danielweber 14y agoBack when DES was being designed, IBM had a bunch of values in their S-boxes. NSA told them "don't use those values; use these values instead." People freaked that it was a backdoor the NSA put in. About 15 years later, differential cryptoanalysis was publicly discovered. The original S-box values would have been very vulnerable to the attack, but the ones the NSA used were resistant, suggesting that NSA knew about differential cryptoanalysis way ahead of time and were suggesting ways to protect the public against its eventual discovery. It is possible that there is still some magic in there to let the NSA magically defeat DES, but we still haven't found it. Similarly, it's possible that this random number generator exists for some nefarious purpose, but we have no evidence for it. Also, this article is 5 years old (the headline didn't say so when I first read this). Schneier was in pretty big self-promotion mode at that time.
- Nikker 14y agoDon't forget that IBM actually designed Lucifer which was 128bits but it was the (edit:s/NSA/NHIS) that truncated it to 56bits and named it DES. So maybe this is an example of "6 of one or half a dozen of the other"?
- tptacek 14y agoAnd don't forget that Eli Biham smote Lucifer with differential cryptanalysis, found more than half of the keys insecure, reduced its security to 235, and published a journal article concluding that NSA strengthened the cipher design; DES was better than Lucifer.
- Nikker 14y agoMaybe 3 decades after it was released according to this paper; http://scholar.google.ca/scholar_url?hl=en&q=http://59.127.136.65/crypto/biham.pdf&sa=X&scisig=AAGBfm2hvYp0XLUMppevbSUagUxH60-pPw&oi=scholarr&ei=aYJkUOCbAof50gG5-ICwDA&ved=0CBsQgAMoADAA http://scholar.google.ca/scholar_url?hl=en&q=http://59.1... Even if the NSA appointed S-Boxes did improve Lucifer then decreasing the block size does not really improve on your point.
- joeycfan 14y agoThe weird fact that we let the codebreakers pick the code we use is wrong. They have a conflict of interest.