Comment by acqq | Hacker News Reader

Comment by acqq | Hacker News Reader

Parent Full thread

About that (even a little more over 28 bytes makes the big change) we can agree: The paper http://dualec.org/DualECTLS.pdf shows that exploiting Dual EC takes hours (without additional bytes), but that RSA (intentionally or unintentionally) managed to adjust the BSAFE C implementation to enable especially easy exploits: in seconds vs more than an hour on the 16-CPU AMD cluster for other implementations (Table 1 in the PDF). The reason:

"due to the use of the requested number of bytes rather than the number of remaining bytes after pulling from the cache, the concatenation of the 32-byte session ID and the 28 pseudorandom bytes in the server random always contains a full 30-byte output block and between one and 30 bytes of a subsequent block."

So the 28 default bytes take hours, just adjusting that a little to push always continuous 58 bytes from the PRNG resulted in reducing the exploit time to seconds. The small number of bytes more, the big difference.

Paper's conclusion: "Our analysis strongly suggests that, from an attacker's perspective, backdooring a PRNG should be combined not merely with influencing implementations to use the PRNG but also with influencing other details that secretly improve the exploitability of the PRNG."

This is exactly why having the "extended_random_value" too was so convenient to the NSA.

That's offline time, isn't it? In other words: the numbers we're talking about are based on the computing resources available to these researchers. It's not as if not having extended_random_value or OpaquePRF means the NSA needs to monitor many many TLS connections, right?

To me it looks that the "just seconds" on the off-the-shelf hardware means that creating the custom chip can allow for a large-scale real-time online decryption of "many many" connections. And even if such a chip is not feasible, additional bytes do make attack much more scalable and reduce the possible response times significantly.

Maybe we're talking past each other. I'm saying, there are different kinds of complexities in implementing attacks on TLS.

The first, most obvious kind is what this paper is talking about: the amount of raw compute it takes to break whatever part of the protocol you're targeting. When this paper says it takes minutes (or seconds) to reverse model Dual_EC, they're referring to the amount of time it takes to work out the current state of the RNG from the partial state disclosed in the TLS handshake.

Another complexity is the kind we saw in the RC4 attacks, where you're exploiting a statistical bias recurring over many connections. It doesn't matter how fast your computer is, because the attack requires your victim to make large numbers of related requests to the target system. That's the "many many" I'm referring to. A TLS handshake change that took NSA from needing 2 million connections down to 1 connection would be extremely bad.

For full context, another complexity is the nature of the TLS connections we're talking about. The RC4 attacks we've seen depended on the BEAST attack model, where attackers could predetermine which connections the victim made (owing to the control HTML/JS gave them); that attack is much more difficult to carry out over other application protocols. So, similarly to the point I just made above, it would also be very bad if a protocol extension took an attack that only worked in the BEAST model and made it work in (say) the SMTP STARTTLS model.

Just to be clear: with Dual_EC, we're already in the worst-case scenario with or without TLS extensions. If a group of researchers with a straightforward hardware setup can reverse the RNG state in an hour, it's reasonable to assume that NSA (if it cares about this attack, and I think it does) can do it in real time.

Reply on news.ycombinator.com