[Cryptography] A Likely Story!

[Peter Fairbrother]

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