Cruising the stacks and finding stuff
Allen
netsecurity at sound-by-design.com
Wed Apr 23 00:11:27 EDT 2008
Hi,
I find it odd that the responses all seem to focus on pure brute
force when I did mention three other factors that might be in
play: a defect in the algorithm much like the attack on MD5 which
reduces it to an effective length of about 80 bits, if I recall
correctly, and/or a different analytical tool/approach much like
differential analysis has had an affect on cryptanalysis as a
whole, and a purpose built machine.
As to using DES as a measuring stick, it was first cracked in
1997 using a software approach which was state as not being as
fast as a hardware solution. In the process of straight brute
force Rock Verser came up with a faster method:
http://www.cs.cmu.edu/~dkindred/des/rocke-alg.html
which uses some of the weaknesses of DES to speed the crack
At the end of the original challenge they were trying about 7
billion keys per second when the time that the solution was found
in June 1997. Granted this was a whole bunch of low end machines
working in parallel.
Then there is a table at:
http://www.interhack.net/projects/deschall/what.html
Then they say, "So, while it's infeasible for DESCHALL to crack a
72 bit key, it seems that 64 might be within reach, by adding
more machines. (We probably used between 15,000 and 20,000
machines.) Consider that the RC5-32/12/5 (40 bits) key crack took
three and a half hours. The distributed computer we put together
could do it in about 78 seconds.
The RC5-32/12/6 (48 bits) key crack took 13 days. A
DESCHALL-sized effort could do it in 5 hours."
They have a table that estimates that a $300 million AISC machine
could crack DES in 38 seconds back in 1995!
In 1998 DESIII did it in less than 24 hours.
http://www.distributed.net/des/
The key point is: "Despite the immense power of the EFF Deep
Crack, distributed.net's thousands of deployed clients still
surpassed the EFF hardware by more than a factor of 2 in speed."
So Moore's law since then, 9 years 3 months: 111 months, say
about 64 times as powerful (actually it is more but let's stick
with a strict Moore's Law) and now factor in drop in prices at
the same time. If we assume the same factor as Moore's law, and
divide the price by 64, let's say 60 for simplicity. So not even
counting 1995 to 1999, the machine would take about a half second
on a <$5 million dollar machine today. Probably both less time
and money.
Today running the RSA-72 DNETC on a single 2.8G dual core machine
that is almost three years old it is getting 13^6/second with a
software program, not hardware.
Also the largest known group of cryptanalysts is at NSA with a
big budget to find weaknesses so I would not assume none will be
found, just not made public. Sure, it took 400 years to figure
out an answer to Fermat's Last Theorem. But we know more today
and have more tools so progress (if we can call it that) is
faster now.
Given all of this, I'm not sure of the value of arguing 128 bit
is good enough when 256 is not all that much harder to implement
and with in a couple of years will be just as fast in processing
while even now, for the size of files being protected, such as
credit card data and such, is small enough that the wait time
probably wouldn't be noticed in network latency.
I see the argument as much like the way the Titanic was built.
The double hull stopped short of the waterline and the breach was
above it. Total fluke, but it the double hull had been about 8
feet higher up the side we wouldn't have had so many stories to
tell and adventures to watch in awe on the tube. The reality is
it was not the technology that failed, but rather human error in
not going further to meet the risk than was seen at the time. The
bizarre thing is the same basic error was the cause of the Exon
Valdez disaster. Not protecting against a well know risk, drunk
captains. Funny how almost all tankers have double hulls now. But
that still didn't prevent the Busan from spilling 58,000 gallons
of bunker oil in the San Francisco Bay. If they hadn't had a
double hull, how much would the have spilled?
Oh, well, given how risk adverse we tend to be it is odd the
choices we make.
Best,
Allen
Leichter, Jerry wrote:
> | ...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 3-d 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 brute-force
> 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 100-light-year diameter sphere that exists for 200
> years. This is a bounded piece of space-time, 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 100-year computation, a 128-bit key
> is just barely attackable; a 256-bit key is way out of the realm of
> possibility. Given all the hand-waving in my calculation, I didn't
> try to determine where in that range the cut-over 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 side-channel or any of a variety of other
> intelligent attacks....
> -- Jerry
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
>
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list