[Cryptography] A Likely Story!

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
```