Re: 1000 Trillion instructions per second SuperComputer at Oak Ridge NL - time to crack AES-128?

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 11/23/03 

Date: Sun, 23 Nov 2003 05:35:18 GMT

Tim Smith wrote:
> Bryan Olson wrote:
>>Eventual brute force of a 2^128 keyspace is entirely plausible; if
>>the trend of Moore's law continues, it'll be about 100 years.
>
> That's like saying it is entirely plausible that someday the entire
> observable universe will be packed pretty much solidly with human living
> space; if the previous century's trend of population growth continues, it
> will be about 10000 years.

Where would we get the matter? Exhaustive search of a 2^128
keyspace is nothing like that. We don't know of any physical
limit that puts trying about 10^38 keys out of reach in the long
term.

> The *correct* conclusion would not be that it is plausible for humans to
> completely fill the universe, but rather that exponential growth at that
> rate cannot continue for 10000 years.

But that has nothing to do with brute force of a 2^128 keyspace.
In one strand of this thread, someone (the same person who
proclaimed a 128-bit keyspace forever inexhaustible) tried to
argue that the vastly larger 256-bit keyspace can't be exhausted
"Even if every atom in the universe were a supercomputer".
That's nonsense; the estimated number of atoms in universe is
larger than 2^256.

> Same with Moore's law (which is not a law, but rather a statement of the
> experimentally observed rate at which the technology is improving).

Right idea, wrong conclusion. It's not plausible that the trend
of Moore's law could keep going for 10000 years. But we're not
talking about 6700-bit keys here.

I remember reading that Martin Hellman had suggested symmetric
keys of 700-some bits to be immune from exhaustive search
forever. That makes a lot of sense based on what our
understanding of physics. In /Applied Cryptography/, Bruce
Schneier argued that thermodynamics rules out brute-force of
256-bit keys, but he retracted it in the errata (page 158 in the
second edition). A 128-bit keyspace is far larger than we can
exhaustively search today, but don't get dazzled by big numbers. 

-- 
--Bryan

Relevant Pages

  • Re: How are you sure that a given species is truly extinct?
    ... no elephant in my living room"; it's the general negatives ... there are also none in the rest of the universe. ... You can prove a negative by exhaustive search of whatever part of the universe is relevant. ... the size of the relevant universe and your ability to exhaustively search it vary immensely with species. ...
    (talk.origins)
  • Re: A simple proof of the Nonexistance of Black Holes.
    ... Evidence against GR is potentially evidence for the nonexistence of black holes. ... of Newtonian black holes does not come from "an exhaustive search of the Universe", but rather from a number of experiments/observations showing that space-time cannot be Newtonian. ...
    (sci.physics.relativity)
  • Re: The Zero Jeopardy of a Multiverse
    ... and the moment i lift my palm, zip, a new universe splits off from "mine" ... _both_ slits and interfered with itself. ... is that the universe "keys on the table" combined with the ...
    (rec.arts.sf.written)
  • Re: How to Jeep Exit a C-130 in Air Assualt
    ... in the entire universe of science, computers, logic, and technology ... that are silly enough use F1 keys is the idiot Government and IBM. ...
    (sci.military.naval)
  • Re: The Zero Jeopardy of a Multiverse
    ... and the moment i lift my palm, zip, a new universe splits off from "mine" ... Consider the famous single photon double-slit experiment. ... _both_ slits and interfered with itself. ... is that the universe "keys on the table" combined with the ...
    (rec.arts.sf.written)