[tor-talk] NSA supercomputer

Fri Apr 5 23:45:57 UTC 2013

On Fri, Apr 05, 2013 at 01:51:06PM +0000, Andrew F wrote:
> I would love to see an analysis of a 128 bit AES encryption VS a 10 exoflop
> computer. How long to crack it?  Anyone got the math on this?
> 
> Andreas, your absolutely right, However we can do some estimating.
> Just keep in mind... garbage in, garbage out.. but  this is a pretty good
> guess.
> 
> So the fastest super computers use general cpus and Nvidia k20s. This is
> important to note because they scale in a linear fashion based on available
> space.   Now we know that Oak ridge national labs has about an acre of
> space, 43,560 Sq. Feet,  for its super computer, the Cray XK7 Named Titan.
> Which runs at 17.59 Pentaflops.  (yes PENTAFLOPS)
> http://www.top500.org/lists/2012/11/
> 
> According to a Cray press release Titan can scale up to 50 Pentaflops.
> 
> Now the new facility in Utah will have over 200,000 sq. feet dedicated to
> its super computer.
> 
> (
> http://www.forbes.com/sites/andygreenberg/2012/03/16/nsas-new-data-center-and-ultra-fast-supercomputer-aim-to-crack-worlds-strongest-crypto/)
> 
> 
> So If we assume, the a linear relationship between Square footage and
> computing power then we can calculate that Utah will have 4.59  time more
> space then Oak Ridge, so they will have room for at least 80.73
> pentaflops.
> 
> Several articles have stated that the center is designed to house an
> Exoflop computer.  Thats a fast computer. Thats 10 followed by 18 zeros. Or
> 1000 petaflops.
> 
> There is more.  Lets look at our growth rate.   4.5 years ago Roadrunner
> was the first super computer to brake the pentaflop barrier. Today we have
> titan at 17.59 pentaflops. So if we can assume a growth rate of 380% per
> year.  And that the center will be up graded with each new version of GPU
> from Nvidia and CPUs from Intel, We can assume that we will hit one Exoflop
> in about three years or 2015.
> 
> The power production at the new facility supports these numbers.
> 
> So what does this mean?   Any article that suggest that brute forcing
> present day encryption is not possible should be taken with a grain of
> salt.  While the article may be correct today, come September 2012, Utah
> goes on line and we will be stepping into a world that will lead to exaflop
> computers and may challenges to our present day encryptions.
> 
> AES is safe for a longtime, but other encryptions should be of concern in
> the coming years.    Don't forget about tracking and fingerprinting
> possibilities with these massive systems.
> 
> I would love to see an analysis of a 128 bit AES encryption VS a 10 exoflop
> computer. How long to crack it?  Anyone got the math on this?
> 
> The good news, no one is going to care about your stuff... unless your
> making waves.   Then the only safe encryption is a non mathematical method,
> such as a  library code run on a system that does not go on the net.

This is all just wrong.  It's wildly implausible that *any* amount of
computational power the NSA will *ever* have will attack such large
key spaces by brute force.  On average, you have to search half the key
space, so 2^127 keys, to break the cipher.  Let's be insanely overgenerous
by a factor of at least a few thousand and suppose 1 'operation' == 1 key
tested, so your 10 exaflop machine can test 10^19 keys/second.  Then it
needs (2^127)/(10^19) seconds on average to brute force a 128-bit key, or
twice that in the worst case.  That's 539 billion years.  The sun will reach
its red giant phase and engulf the Earth before it gets through even one
percent of the keyspace.

Furthermore, thermodynamic constraints apply: for every bit of non-reversible
computation output, one must expend energy 4*k*T, where k is Boltzmann's
constant and T is the absolute temperature.  The lowest you can plausibly
take T is equilibrium with the cosmic microwave background (2.73 K), since
you would need to expend more energy for cooling to maintain a lower
temperature.  Thus, every non-reversible bit of output needs at least 1.51 *
10^-22 J of input energy.  Forget cryptography for the moment; consider just
cycling a 128-bit counter through all of its possible values.  Adding one to
a number always changes 1 bit, changes another half of the time, and so on,
so we have 2^0 + 2^-1 + ... + 2^-128 = 2 * (1 - 2^-129) irreversible bit
outputs per counter value, times 2^128 values gives us 2^129 - 1 bits expended,
or 1.03 * 10^17 J.  Not a totally implausible amount of energy, but a rather
large one, roughly one day's worth of output for all the power plants in the
world - actually doing crypto ops that many times would need thousands of
times more, and current hardware is many orders of magnitude away from being
able to even approach fundamental physical limits on computational efficiency.
It also nicely demonstrates that 128-bits is about as far is it goes for
brute force even being theoretically possible within the known laws of physics;
brute-forcing a 256-bit key would consume far more energy than is available
in the observable universe.

Summarizing more concisely, there's no possible way the NSA can attack 128-
bit keys by brute force.  The more plausible dangers are that they know a
cryptanalytic attack not known in the public literature that can break ciphers
like AES more efficiently than that, and being certain of security in such
cases is very hard because proving lower bounds on computational complexity is
very hard [1], or that they're far beyond the capabilities of publicly known
hardware at building quantum computers and can apply Grover's algorithm in
a large but not impossible 2^64 operations.

[1] Since you can test whether a key is correct in polynomial time using two
blocks of ciphertext, search for keys is in NP and being able to rigorously
prove security for a block cipher would imply P != NP as a corollary.

-- 
Andrea Shepard
<andrea at torproject.org>
PGP fingerprint: 3611 95A4 0740 ED1B 7EA5  DF7E 4191 13D9 D0CF BDA5
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20130405/524f9cd7/attachment-0001.pgp>