Hacker News Reader

As Thomas is not sure what I'm "trying to say here that" his "comment doesn't already say," he actually wrote: "All extended_random_value does is add, to the random_bytes value in the TLS handshake, another variable-length blob of random data."

It sounds smallish "just another random-data blob." It's actually huge "up to additional 65365 bytes from the generator added to the default 28" before the encryption even starts.

Thomas also wrote "The ostensible idea behind the extension is that there are protocols that want randomness proportional to key sizes."

The biggest ECC key is 571 bits which fit in just 72 bytes and this thing provides up to 65535 bytes. Again, fully different impression. I quoted the draft to show the actual number. The numbers matter here. Hadn't I looked at the draft directly, I'd get the fully different impression only reading Thomas' comment.

I think you're missing the part where people can make credible arguments that twenty eight bytes of random state (the protocol as standardized) is already a problem. The difference between 10 and 60,000 extra bytes seems to make a big difference to you, and, fair enough I guess, but the underlying problem isn't the size of the random state.

Read the Dual_EC exploit paper that just came out; the authors used minimal compute resources and standard TLS to exploit a model Dual_EC problem.

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.

Incidentally, here are the original requirements that these drafts were intended to satisfy:

   In a number of United States Government applications, 
   it is desirable to have some material with the following 
   properties:

   1.  It is contributed both by client and server.
   2.  It is arbitrary-length.
   3.  It is mixed into the eventual keying material.
   4.  It is structured and decodable by the receiving party.

(Amusingly, this comment got downvoted.)

That is what they appeared to satisfy then (2006-2009). We know now that if implemented it would allow them almost real-time or even real-time decryption of communication of whoever uses it, as we discussed here:

https://news.ycombinator.com/item?id=7503287

We also know extended_random_value is actually implemented in RSA's BSAFE library, as the paper http://dualec.org/DualECTLS.pdf shows.

And we know http://security.stackexchange.com/questions/43164/which-prod...

"the RSA BSAFE library uses Dual_EC_DRBG (...) by default (...)

I can easily find (hint: use your favourite search engine to search for the terms "This product includes" "RSA BSAFE") implementations, oddly skewed towards imaging and gaming devices: surprisingly many printer/copier/fax devices use BSAFE, though for unknown purposes.

Including Ricoh, Minolta, Océ/Canon, Brother, Fuji/Xerox, Epson ...

Your Playstation (PDF), PSP, or your Nintendo DS wifi (PDF)

Software from Adobe, Hitachi, Oracle and HP Some Nokia phones(PDF)"

Which of those products do you know to actually be using Dual_EC at all?

At least, every product which uses defaults of the library? You know, "leave the hard choices to the experts who know more."

Can we name one of them that uses Dual_EC, and has been shown to do so? I know a little about BSafe, and my impression is that most programs that use it don't use it to get TLS, which their OS already provides. Feel free to correct me if you've got more BSafe experience than I do.

This is obviously a rehash of an argument that recurs on HN a lot, but just to be fair to what I'm trying to say here: that argument has (as far as I can tell) never been resolved.

So who needs, apart from the spies from other countries and TPtacek more precise list of the possibly vulnerable products than the one already here? I don't think many people see the benefits in making the list more precise. The companies mentioned have all the incentives to remain silent.

All things being equal I'd rather know more than less.

Remember, I'm not asking how many vendors keep the BSAFE default. I'm asking how many use BSAFE in a way where the RNG matters.

Isn't your company's business to discover the security flaws? I believe the fact that you don't know the details means that there isn't much interest, at least in your part of the world, to fund such a research. There are no incentives for academia to make it too. All that doesn't mean the list doesn't exist, only that there is no economic reason to publish it.

No. My company provides an engineering service for vendors to find security flaws in specific pieces of software before (and sometimes after) that software ships. You should think of us as part of the development process.

If you gave us a piece of software that used BSAFE, you could reasonably expect detailed mitigation advice on not having a PKRNG exposed in your system.

No process in the market compensates us for acquiring a Ricoh printer and digging into its firmware to find how any why it's using BSAFE. It's not an especially interesting research project either.

I'm not surprised we don't know which products actually use Dual_EC, and I don't find the fact that we don't particularly telling. I'm saying something different: that I have worked with software that used BSAFE, and it used BSAFE for idiosyncratic reasons that didn't much implicate Dual_EC. I would not, for instance, be at all surprised to find an embedded device that used BSAFE for some goofy thing, but used OpenSSL as its TLS library.

The only "process in the market" for this kind of work is individuals or companies breaking random things in public to build their reputation as auditors (e.g. homokov), or selling vulns. But as you point out it's only really awesome when you follow the Cryptography Research model: find a new class of attack, develop the countermeasure, package (potentially patent) the countermeasure, then make scary demos of the attack to get responsible parties to buy your countermeasure.

In this case the mitigation is so simple ("don't use PKRNG; avoid RSA, Inc. going forward.") that it's not monetizable, so it's really only for reputation points.

This is almost certainly not true given the fact that ECDRBG is chronically slow (think orders of magnitude). Any developers working on implementations which generate a reasonable amount of random data switch to HMAC very quickly.

So "it's not true that companies who use default use default because if they use default they will measure the speed and then not use default?" Too much reading Catch 22?

In fact, the companies who use default simply use it. Period. And they use default in spite of it being slower than something else.

I think that's a very long bow to draw... Especially seeing as the trouble shooting guide for bsafe libraries has a section dedicated to speeding up the toolkit which advises switching to HMAC.

I'm not sure about you, but when I see a chronic change in performance I look into it, and if there is a vendor recommended suggestion, I usually try it.

This is particularly true for the Java tools as it is trivial in the extreme to compare the bsafe performance with the standard oracle crypto performance.

Basically, as tptacek points out, there is a lot of information we aren't privy to and there is no point assuming every bsafe customer is using ec .

When the company uses the default in the product, it uses it. There's nothing "to draw." It's a true statement, not a hypothesis.

And it has nothing to do with what you do when you "see a chronic change in performance." If somebody uses something and not something else, there's no "change" at all. Nobody ever claimed "every customer uses Dual_EC."

The claim is: there are a lot of famous customers and products using BSAFE and the Dual_EC is the default in BSAFE.

Interestingly, Dual_EC can still be negotiated in other implementations too. Poisoning the standards sets leaves some possibilities as long as the dangerous implementations are present.

The big problem with the claim that "lots of famous customers and products use BSAFE" is that the statement by itself doesn't mean much. Does BSAFE provide the TLS library for Cisco IOS? Neither of us probably has a ready answer, but if you'd like to put some money on which way this will go, I'm game.

For awhile during the late 1990s, some products used BSAFE because there were patent concerns with using any public key encryption in a commercial product, and BSAFE was an innoculation. Also, some products have codebases that date back before credible open-source crypto libraries. But those same products tend to have crypto features that were implemented later.

Like I said, we do a lot of casual reversing, and we look at a lot of random products that big F500 companies deploy, because F500s pay us to do that. I see a lot of OpenSSL. After that, I see a lot of Windows Cryptography API. Next in line is probably cryptopp, and then Bouncycastle. I see BSAFE once in a blue moon.

The more I think about it, the more interesting the research project of working out exactly why different products depend or don't depend on BSAFE actually starts to sound.

This is interesting in that regard: http://dualec.org/. If this research is true, it seems that a number of servers use it.

There's an extra dimension to what might or might not have been known in 2005: Known to whom?

Given that the standards in question are already widely believed (to put it mildly) to have been deliberately weakened by the NSA, which still has quite a bit of nonpublic crypto knowledge, you really have to keep that in mind as well.

In addition, "requested by the Department of Defense" strikes me as a big warning.

It was known to the NSA that it was bad before it was known to the public, obviously.

Right, that's true. I think I pointed that out because I'm knee-jerk waiting for the horrible "Eric Rescorla is an NSA plant" arguments --- which, as it turned out, never really came.

Is there a safe generator (CS-PRNG) where more state disclosure does NOT compromise the generator?

What if you needed to disclose 1MB of state. What about 1TB?

The problem with Dual_EC is that you're disclosing state at all; most RNG designs don't do that.

draft-rescorla-tls-extended-random says: "A cryptographically secure PRNG [RFC4086] SHOULD be used."

RFC 4086 Section 6.2: "The correct technique is to start with a strong random seed, to take cryptographically strong steps from that seed [FERGUSON, SCHNEIER], and not to reveal the complete state of the generator in the sequence elements."

In other words, you should not reveal the complete state of your PRNG regardless of how many values you disclose, and the authors explicitly warned against using a PRNG that does so (in practice every PRNG with finite state will cycle at some point, at which point all future values become predictable, but good designs have cycle lengths in the range of 2^(several thousand), so 1 TB of random data is no problem).