5 ms·

> I think it seems crazy now, but that's because we know a lot more about the practical applications of malicious RNGs; RNGs were understood to be the lynchpin

by wahern 5y ago

> I think it seems crazy now, but that's because we know a lot more about the practical applications of malicious RNGs; RNGs were understood to be the lynchpin of secure systems for decades, including long before 2007; and it was also widely assumed both now and then that they were one of the most common vectors for attack by the NSA. Why RSA added Dual_EC_DRBG is easy to explain in dollars & cents: 1) RSA was literally paid to add it, and 2) most of RSA's revenue comes, directly or indirectly, through government contracts (e.g. FIPS compliance, etc). As for why RSA insiders didn't speak up: there are mountains of scholarship explaining why people just keep their heads down. Even if you were absolutely convinced beyond a shadow of a doubt that Dual_EC_DRBG was a backdoor, intelligent people are very good at rationalizing things. Anybody who has worked at a large company, including RSA, understands that your day-to-day work and the company's business is as a practical matter <10% technical and >90% everything else (sales, profit seeking, integration, etc, etc). More importantly, if you're a company doing business in a space dominated by U.S. government requirements and processes, or even just patriotic, the NSA having a backdoor is hardly the worse thing in the world. There are amazing cryptographers in China. Even the ones who fancy themselves world citizens and above the fray of nationalism, how many do you think would stick their head out were they in a position to identify possible formal government attempts to manipulate technology? Moreover, a backdoor doesn't necessarily mean insecure; it's not a categorical truth that any backdoor means broken security, that's just a rule of engineering thumb built on the experience that securely maintaining the keys to backdoors is supremely difficult, often more difficult than any other aspect. Nobody has yet come close to breaking Dual_EC_DRBG, AFAIU. From a purely technical perspective, Dual_EC_DRBG is still secure. The keys haven't leaked, and the algorithm remains as impenetrable as ever. At the end of the day, that's all the rationalization most people would ever need to keep their head down. The "security" of Dual_EC_DRBG is a socio-political debate, not a technical one.

tptacek 5y ago
I disagree with basically all of this. I disagree that cryptography engineers understood viscerally how good a target RNGs were or how viable a PKRNG would be (further evidence for that would be the contortions attackers have to go through to extract enough wire state from Dual EC to mount the most straightforward attacks). I think you can formulate an argument that any major cryptographic primitive is the "lynchpin", and indeed you see people doing that, for instance with the SIMON/SPECK block cipher designs --- block ciphers, after all, are the lynchpin of secure systems. I agree, obviously, that RSA added Dual EC because DOD demanded it. But most of RSA's revenue didn't come from BSAFE, or even things that relied on BSAFE. They were a crappy token company that bought RSA, then built a bunch of multi-factor authentication stuff that had more to do with IP reputation than with cryptography. I don't really buy that anybody working inside RSA was absolutely convinced that Dual EC was a backdoor. I sort of don't buy that anyone was really even seriously paying attention. I think people think of RSA as a cryptography company, but that is not at all what RSA was at the time this happened. None of this matters, really. We arrive at the same place about RSA's culpability. But if you came to HN hoping to find someone to stick up for RSA's decision here, you haven't been paying attention to the tenor of this place. All you're going to get here is hair splitting; that's the interesting conversation we can actually have. There's no viable debate about whether adopting Dual EC was defensible. Even when I was saying I doubted Dual EC was a backdoor, I still didn't think using it was defensible.
- wahern 5y ago
  > for instance with the SIMON/SPECK block cipher designs --- block ciphers, after all, are the lynchpin of secure systems. The lynchpin to ciphers are the keys. That's the very definition--proof of security reduces to the question of whether you know the key or not. Unless you exchange a database of one-time pads, you invariably need an RNG to generate keys for your ciphers. That's your lynchpin right there. The key is the lynchpin, and RNGs generate your keys. You don't need to feel it; it's cryptography 101. Granted, it's such a basic and fundamental aspect to secure systems that it usually gets lost in all the bike shedding.
- healsjnr1 5y ago
  I've got some direct personal experience in this one. A few key points from how I saw it play out inside: - there was a lot of noise made about this by the bsafe crypto team when it was first implemented (anecdotal, but I trust the people that were there and the context below helps reinforce this). From what I heard there was clear communication that adding EC drbg to the toolkits the way nsa wanted was insecure. - that happened before my time, but by the time I got there it was kind of an inside joke that EC drbg was an NSA backdoor (I think this was around 2010) - the above was tempered by the fact that it was so horrendously slow, no one could imagine it being used - even though RSA demanded it was the default RNG for the toolkit, the first part of documentation strongly suggested changing this default - my memory is that this work on EC drbg funded development bsafe SSL toolkits. So while the money may have been relatively small, it opened up a new product for BSAFE The smoking gun and the bit that made it really obvious that something was off about this came in its use as part of the TLS toolkits. There was an explicit, but unexplained, requirement that the _first 20 bytes_ of random generated during the handshake were sent unencrypted as part of the handshake. EAY led that crypto team, they knew their stuff and they knew that this was off and there was no legitimate reason for doing this. My take: this team new what was happening and they made it clear to management. As a really the people who made the decision to take NSA money knew what it was and the implication and went ahead anyway. As a foot note, when we did the cleanup on this we found that in some of the toolkits the way that the 20bytes was sent was flawed and would have meant that an attempted backdoor using this would have failed. Whether this was intentionally or not _shrug_.
AlexCoventry 5y ago
> From a purely technical perspective, Dual_EC_DRBG is still secure. I think that depends on the techniques you're thinking of. The usual way of proving such a system is secure is to reduce a break to a solution of a bedrock problem like discrete log, and according to the second reference in the OP, "Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator", no such proof was provided in this case. I would say that without such a proof, it's not "technically" secure.

by wahern 5y ago

tptacek 5y ago

I disagree with basically all of this. I disagree that cryptography engineers understood viscerally how good a target RNGs were or how viable a PKRNG would be (further evidence for that would be the contortions attackers have to go through to extract enough wire state from Dual EC to mount the most straightforward attacks). I think you can formulate an argument that any major cryptographic primitive is the "lynchpin", and indeed you see people doing that, for instance with the SIMON/SPECK block cipher designs --- block ciphers, after all, are the lynchpin of secure systems. I agree, obviously, that RSA added Dual EC because DOD demanded it. But most of RSA's revenue didn't come from BSAFE, or even things that relied on BSAFE. They were a crappy token company that bought RSA, then built a bunch of multi-factor authentication stuff that had more to do with IP reputation than with cryptography. I don't really buy that anybody working inside RSA was absolutely convinced that Dual EC was a backdoor. I sort of don't buy that anyone was really even seriously paying attention. I think people think of RSA as a cryptography company, but that is not at all what RSA was at the time this happened. None of this matters, really. We arrive at the same place about RSA's culpability. But if you came to HN hoping to find someone to stick up for RSA's decision here, you haven't been paying attention to the tenor of this place. All you're going to get here is hair splitting; that's the interesting conversation we can actually have. There's no viable debate about whether adopting Dual EC was defensible. Even when I was saying I doubted Dual EC was a backdoor, I still didn't think using it was defensible.

wahern 5y ago
> for instance with the SIMON/SPECK block cipher designs --- block ciphers, after all, are the lynchpin of secure systems. The lynchpin to ciphers are the keys. That's the very definition--proof of security reduces to the question of whether you know the key or not. Unless you exchange a database of one-time pads, you invariably need an RNG to generate keys for your ciphers. That's your lynchpin right there. The key is the lynchpin, and RNGs generate your keys. You don't need to feel it; it's cryptography 101. Granted, it's such a basic and fundamental aspect to secure systems that it usually gets lost in all the bike shedding.
healsjnr1 5y ago
I've got some direct personal experience in this one. A few key points from how I saw it play out inside: - there was a lot of noise made about this by the bsafe crypto team when it was first implemented (anecdotal, but I trust the people that were there and the context below helps reinforce this). From what I heard there was clear communication that adding EC drbg to the toolkits the way nsa wanted was insecure. - that happened before my time, but by the time I got there it was kind of an inside joke that EC drbg was an NSA backdoor (I think this was around 2010) - the above was tempered by the fact that it was so horrendously slow, no one could imagine it being used - even though RSA demanded it was the default RNG for the toolkit, the first part of documentation strongly suggested changing this default - my memory is that this work on EC drbg funded development bsafe SSL toolkits. So while the money may have been relatively small, it opened up a new product for BSAFE The smoking gun and the bit that made it really obvious that something was off about this came in its use as part of the TLS toolkits. There was an explicit, but unexplained, requirement that the _first 20 bytes_ of random generated during the handshake were sent unencrypted as part of the handshake. EAY led that crypto team, they knew their stuff and they knew that this was off and there was no legitimate reason for doing this. My take: this team new what was happening and they made it clear to management. As a really the people who made the decision to take NSA money knew what it was and the implication and went ahead anyway. As a foot note, when we did the cleanup on this we found that in some of the toolkits the way that the 20bytes was sent was flawed and would have meant that an attempted backdoor using this would have failed. Whether this was intentionally or not _shrug_.

AlexCoventry 5y ago

> From a purely technical perspective, Dual_EC_DRBG is still secure. I think that depends on the techniques you're thinking of. The usual way of proving such a system is secure is to reduce a break to a solution of a bedrock problem like discrete log, and according to the second reference in the OP, "Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator", no such proof was provided in this case. I would say that without such a proof, it's not "technically" secure.