A Likely Story!
Peter Fairbrother
zenadsl6186 at zen.co.uk
Sun Sep 8 16:19:34 BST 2013
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
More information about the ukcrypto
mailing list