Random number generators play a crucial role in cryptographic security. Image: agaudin/Flickr
So assuming that there is, indeed, an NSA backdoor in DUAL_EC_DRBG, what does that mean for the security of the systems that use it?
It’s a bit nuanced, so stick with me here.
First the good news: Given the public specification, the secret parameters of the “Q”-based backdoor are hard to find if you didn’t actually generate Q yourself.
It’s not that it’s hard to see that that there might be secret backdoor parameters. What’s hard to find is their actual values so you can exploit it yourself. How hard? As hard as the underlying problem, called EC Discrete Logarithm, which is believed to be infeasible to solve in practice. So that means that “only” the NSA, or whoever selected Q, is likely to have the secret required to break it, unless they’ve shared these values with someone else. (You only have to do the hard calculation once, but it’s believed to be a very hard problem, even for an entity with vast resources.)
Also, even if you know the secret behind Q (as NSA is presumed to) — not every system that uses DUAL_EC_DRBG is automatically vulnerable. Exploiting the backdoor requires that the system expose a certain number of bits of output in the “clear”. Many cryptographic systems do this, but not all do. It depends on the specifics of the protocol and its implementation, which varies widely.
Which brings us to several pieces of rather bad news.
