Cruising the stacks and finding stuff
Leichter, Jerry
leichter_jerrold at emc.com
Tue Apr 22 10:46:33 EDT 2008
 ...How bad is brute force here for AES? Say you have a chip that can do
 ten billion test keys a second  far beyond what we can do now. Say
 you have a machine with 10,000 of them in it. That's 10^17 years worth
 of machine time, or about 7 million times the lifetime of the universe
 so far (about 13x10^9 years).

 Don't believe me? Just get out calc or bc and try
 ((2^128/10^14)/(60*60*24*365))

 I don't think anyone will be brute force cracking AES with 128 bit
 keys any time soon, and I doubt they will ever be brute forcing AES
 with 256 bit keys unless very new and unanticipated technologies
 arise.

 Now, it is entirely possible that someone will come up with a much
 smarter attack against AES than brute force. I'm just speaking of how
 bad brute force is. The fact that brute force is so bad is why people
 go for better attacks, and even the A5/1 attackers do not use brute
 force.
Interestingly, if you add physics to the picture, you can convert "no
practical brute force attack" into "no possible brute force attack given
known physics". Current physical theories all place a granularity on
space and time: There is a smallest unit of space beyond which you
can't subdivide things, and a smallest unit of time. One place this
shows up, as an example: It turns out give a volume of space, the
configuration with the maximum entropy for that volume of is exactly a
black hole with that volume, and its entropy turns out to be the area
of the black hole, in units of square Planck lengths. So, in effect,
the smallest you can squeeze a bit is a Planck length by Planck length
square. (Yes, even in 3d space, the constraint is on an area  you'd
think the entropy would depend on the volume, but in fact it doesn't,
bizarre as that sounds.)
So suppose you wanted to build the ultimate computer to bruteforce
DES. Suppose you want your answer within 200 years. Since information
can't propagate faster than light, anything further than 100 years
from the point where you pose the question is irrelevant  it can't
causally affect the result. So you computer is (at most, we'll
ignore the time it takes to get parts of that space into the
computation) a 100lightyear diameter sphere that exists for 200
years. This is a bounded piece of spacetime, and can hold a huge,
but finite, number of bits which can flip at most a huge, but finite,
number of times. If a computation requires more bit flips than that,
it cannot, even in *physical* principle, be carried out.
I ran across a paper discussing this a couple of years back, in a
different context. The authors were the ones who made the argument
that we need to be wary of "in principle" arguments: What's
possible "in principle" depends on what assumptions you make. Given
an appropriate oracle, the halting problem is "in principle" easy to
solve.
The paper discussed something else, but I made some rough estimates
(details long forgotten) of the "in principle" limits on brute force
attacks. As I recall, for a 100year computation, a 128bit key
is just barely attackable; a 256bit key is way out of the realm of
possibility. Given all the handwaving in my calculation, I didn't
try to determine where in that range the cutover occurs. Someone
better than me at the physics should be able to compute much tighter
bounds. Even if I'm off by quite a bit, it's certain that the key
lengths we are using today are already near fundamental physical
limits. Brute force is simply not an interesting mode of attack
against decently engineered modern systems.
Of course, this says  and can say  absolutely nothing about the
possibility of analytic or sidechannel or any of a variety of other
intelligent attacks....
 Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list