`This is just a wild story, It isn't true. If we cryptographers found it`

`was true we would all be totally gobsmacked.`

The Beginning:

`Sometime in 2008 the NSA - the United States National Security Agency,`

`who employ many times more mathematicians than anyone else does -`

`discovered a new mathematical way to factorise big numbers better.`

`It wasn't a huge advance, but it would be good enough for them to`

`factorise several hundred 1024-bit-long numbers per month using some big`

`computers they wanted to build.`

`In the form of RSA public keys, these 1024-bit numbers were (and`

`sometimes still are) used to generate the session keys which encrypt and`

`protect internet traffic.`

`A session key is the key which is used to encrypt the traffic between`

`you and a website, using a normal cipher - it is a shared secret between`

`you and the website.`

`Setting up a shared secret session key, when the communications used to`

`set it up may also be intercepted, is quite difficult and involves`

`considerable tricky math. That's where RSA and factorising comes in.`

`In 2008, when you saw a little padlock in your browser, the connection`

`was almost always encrypted using a session key whose secrecy depends on`

`the inability of anybody to factorise those 1024-bit RSA numbers.`

`They change every few years, but usually each big website only uses one`

`RSA key per country - so when the NSA factorised just one of those RSA`

`keys it could easily find the session keys for all the internet sessions`

`that website had made in that country for a couple of years.`

`Now the NSA had been collecting internet traffic for years, and when the`

`big computers were built they would be able to see your past and present`

`online banking, your secret medical history, the furlined handcuffs you`

`bought online ..`

The Dilemma:

`So, did the NSA then go "Hooray, full steam ahead?" Not quite. The NSA`

`has two somewhat conflicting missions: to be able to spy on people's`

`communications, and to keep government communications secure.`

`On the one hand, if they continued to recommend that government people`

`use 1024-bit RSA they could be accused of failing their mission to`

`protect government communications.`

`On the other hand, if they told ordinary people not to use 1024-bit RSA,`

`they could be accused of failing their mission to spy on people.`

What to do? Some Background:

`Instead of using 1024-bit RSA to set up session keys, people could use a`

`different way, called ECDHE. That stands for elliptic curve Diffie`

`Hellman (ephemeral), the relevant bit here being "elliptic curve".`

`You can use any one of trillions of different elliptic curves,which`

`should be chosen partly at random and partly so they are the right size`

`and so on; but you can also start with some randomly-chosen numbers then`

`work out a curve from those numbers. and you can use those random`

`numbers to break the session key setup.`

`The other parts are: starting from the curve, you can't in practice find`

`the numbers, it's beyond the capabilities of the computers we have. So`

`those if you keep those random numbers you started with secret, only you`

`can break the ECDHE mechanism. Nobody else can.`

`And the last part - it is convenient for everybody to use the same`

`elliptic curve, or perhaps one or two curves for different purposes. So`

`if you know the secret numbers for the curve, you can break everybody's`

`key setup and get the secret session keys for all the traffic which uses`

`those curves.`

The Solution:

`Make government people use ECDHE instead of RSA, but with the NSA's`

`special backdoored elliptic curves. Ordinary people will follow suit.`

`This solves both problems - when people change to the new system the NSA`

`can still break their internet sessions, and government communications`

`are safe from other people (although the NSA can break US government`

`communications easily - but hey, that's the price of doing business, and`

`we're the NSA, right?).`

`Someone else might find the factoring improvement, but it is thought`

`infeasible that someone else would be able to find the secret backdoor.`

"Hooray, full steam ahead!" That's the story.

`The rest is just details - maybe the NSA somehow got NIST to put their`

`special backdoored curves into NIST FIPS 186-3 recommendations in 2009,`

`so people would use them rather than make up curves of their own - it is`

`usual and convenient, but not strictly necessary, for ECDHE software to`

`only be able too use a small selection of curves.`

`Maybe they asked the US Congress for several billion in extra funding in`

`the 2010 budget to run the RSA-breakers.`

`Maybe they are building a new "data center" in Utah to use the session`

`keys to decrypt the communications they have intercepted over the years.`

`Maybe they put those special backdoored curves into Suite B, their`

`official requirements for US Government secret and top secret`

`communications.`

`Or maybe they didn't. It's just a story, after all. The cryptography,`

`while incomplete, is correct, and it may all seem plausible - but of`

`course it isn't true.`

-- Peter Fairbrother _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography