Of all the revelations made by Edward Snowden, I find the recent one about Dual_EC_DRBG definitely the most intriguing and possibly the most shocking – even if it wasn’t really news.
It intrigues me because it is about elliptic curves. I love elliptic curves. I studied them quite extensively when I worked as a mathematician and although I don’t use them anymore, I still feel a fondness for them.
But more importantly, it intrigues me because initially I didn’t realise what had really happened – and judging from comments and articles I’ve seen, I wasn’t the only one.
The NSA didn’t weaken a crypto standard. Rather, it put a backdoor inside the standard. There’s an important difference. As a consequence, if you use Dual_EC_DRBG, you’re still well-protected if the adversary you’re defending against isn’t the NSA. But if it is, you’re pretty much stuffed.
Dual_EC_DRBG is a pseudorandom number generator (or deterministic random bit generator; hence the name). It is one of four of its kind that were defined in the 2006 NIST standard SP 800-90A [PDF]. The standard was written with the help of some people at the NSA.
As we now know1, the NSA effectively wrote the standard.
Randomness is an essential part of any crypto system. It is also where many crypto systems have weaknesses, so if you’re implementing cryptography, it makes sense to use a standard provided by a reputable organisation like NIST.
What pseudorandom number generators do is turn a small ‘seed’ of proper random data into a constant stream of random numbers, which enables you to get such a number with arbitrarily high entropy.
Entropy is usually defined as a way to measure randomness, but here (and possibly in general) it is best to see it as a way to measure surprise to an adversary.
A high entropy means the adversary will know very little about the random numbers the system generates.
Dual_EC_DRBG uses a given elliptic curve. Elliptic curves come with an extra structure, called a group structure.
For the purpose of this post, it suffices to say that this allows you to walk along the curve but, rather than simply following the shape of the curve, your walk makes you seemingly go all over the place.
It is this all-over-the-placeness which makes them useful to generate pseudorandom numbers (and for cryptography in general).
Apart from the curve, the algorithm also uses two given points P and Q on this curve. Like the curve, they are given in an appendix to the NIST standard.
Now there exists a relationship between these points P and Q: if you start at Q and you continue walking, then, for some large number e, after e steps you end up at P.
This is not a secret: it is a simple property of the group structure of elliptic curves.
But if the curve is large (which the one used in this standard is), it will take you a long time to compute e. Think in terms of millions of years.
So no one knows e and no one can know e.
No one?
Well, if you simply choose a point P on the curve and choose a (very large) number e, you can use that to compute a point Q. If you then give out these P and Q to someone, they will still need a million years to compute e. But you know it.
And that’s exactly what the NSA did. They provided the P and the Q in the standard. They, as has become clear from Snowden’s documents, know e.
We don’t. And we can’t even compute it.
Does this matter?
It does.
In 2007, Dan Shumow and Niels Ferguson, two researchers then working for Microsoft, showed [PDF] that, if you know e, cracking the pseudorandom number generation becomes a little easier.
A little easier? Actually, it becomes almost child’s play. They effectively showed that to the NSA, your high-entropy pseudorandom number generator, generates output with very few surprises.
In practise this means that, by knowing e, can read almost all TLS-traffic (which includes HTTPS) that is encrypted using a algorithm based on Dual_EC_DRBG.
After the likely backdoor was found in 2007, NIST actually updated the standard.
It now shows you a method to choose ‘good’ P and Q yourself (for you can’t just choose arbitrary points).
But it still says that if you want your crypto to be FIPS 140-certified, you need to choose the points they’ve chosen for you. “Trust us,” you read between the lines, “we know they work.”
So why would anyone trust them, especially after it was shown that someone could likely have inserted a backdoor? That is beyond me. But the standard is used in quite a few implementations.
What makes this even more strange is that, as Matthew Green pointed out in an excellent blog post, the algorithm is pretty flawed in a number of other ways too. No wonder the crypto world suddenly finds itself in an existential crisis.
Now it would have been bad if the NSA had someone managed to make us all use weaker cryptography. Still, the playing field would have remained level, albeit with lower security for everyone.
It would have been a little worse if the NSA knew of a secret algorithm that enabled them to break cryptography. (It is possibly that one of the future revelations that Bruce Schneier hinted at will show they can do that for certain crypto standards.) Still, ultimately that is just beating your opponent by being more clever.
But what the NSA did was plain cheating.
The crypto remains secure against any of us. But they can crack it.
Because they wrote it. And they put a backdoor into it. And even though we know (and have known for some time) there was such a backdoor, it still doesn’t help us.
Cheating with the privacy of billions of internet users is nothing but very, very wrong.
(Apart from the blog post by Matthew Green, there is a Wired article on Dual_EC_DRBG that Bruce Schneier wrote back in 2007, when Edward Snowden was but a junior employee at the CIA working in Switzerland. As just about anything Schneier has written on cryptography, it is well worth a read.)
1 The NSA hasn’t owned up and it is unlikely they ever will. While no one doubts that the NSA planted a backdoor into Dual_EC_DRBG, we can’t prove it. Throughout this article, I have assumed we are sure.
It made for easier reading. And, frankly, we are quite sure.
Setting aside the hideous nature of these revelations, I'm a little disappointed that no-one is commending RSA for informing their customers that they had adopted the compromised algorithm. It would have had a profound effect on customer confidence, as well as likely impacting EMCs share price.
Looking on the NIST page (http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html#104) and searching for "Dual_EC_DRBG" reveals 65 other adopters of the same standard, the silence from those other vendors (some of which are the biggest names in the industry), is deafening…
Keep in mind the comments of the product manager at RSA who stated that the Dual_EC_DRBG was included as an option and had been done so for a specific client. From what I understood, Dual_EC_DRBG was not the defacto setting, so the exposure was only to client who chose to use Dual_EC_DRBG. Accordingly, the fact that Dual_EC_DRBG was included did not mean that it was used by all users.
While RSA's CTO has made some pretty daft remarks (such as stating that the slowness of Dual_EC_DRBG was a good thing) I agree that they should be commended for being open to their customers. (But, as Ryk pointed out, in some cases the algorithm may have been merely implemented – to comply to standards – but not used.)
so what's stopping 'e' from
being leaked?
Precisely. The assertion "if you use Dual_EC_DRBG, you’re still well-protected if the adversary you’re defending against isn’t the NSA" is nonsense — who knows what other NSA leakers acted in secret, providing the backdoor access to some corporation, foreign power, terrorist group, or whatever?
Sure. In a way, that argument could be held against any kind of public-key cryptography: if you make a secure connection to my server (using, say, HTTPS) then you're not safe if someone has obtained my private key. But you are right, it's a possibility that can't be excluded – and in this case it would be one key to rule them all, so the incentive to steal it would be all the greater.
Well written – and whilst the fine detail of the maths may be slightly beyond me, the general understanding isn't. We need more articles like this.
I remember that at the time elliptic curves were first used by Apple a lot of people wondered how Apple could bypass all the export restrictions for cryptography products with such ease.
Well, now we know.
ag.
end of the day, best is still to write yr own encryption,
only then will u know that you are truly secure
Except that the number of people who have the technical knowledge to do so is very small. I think it's important that other people can communicate securely too.
Encryption may not be the foolproof solution we want, but it's better than nothing. It will give NSA more trouble than its worth to dig into our private data without good reason. Same goes for storing files online. Get them off the cloud services and stash them in a CloudLocker (www.cloudlocker.it), which stays in your home where they still need a warrant to get inside.