80-bit security?

[Perry E. Metzger]

Brandon Enright <bmenrigh at ucsd.edu> writes:
> This is surprising accurate.  As Sandy Harris pointed out,
> http://www.copacobana.org/ is selling about $10k worth of FPGA
> technology to crack DES in about 6.4 days:
[...]
> Now, even assuming 64 bits is within reach of modern computing power,

FPGAs are fairly slow and large. Using full custom designs, one could
easily get sufficient speedup on individual cracking units and a
sufficient increase in the number of cracking units because of the
reduction in area chip area for each unit that one could easily make up
for the 256x increase in cracking time between a 56 bit and 64 bit
cipher. There is therefore no question that 64 bits is in easy range at
this point.

> I still think it is naive to assume that computing power will continue to
> grow to 80 or more bits any time soon.  The energy requirements for
> cycling a 80 bit counter are significant.  We are likely to get to a
> point where the question is not "how parallel a machine can you afford
> to build?" but rather "how much heat can you afford to dissipate?".

One can easily get more bang per watt by clocking things slower. Power
dissipation is (quite) non-linear in clock rate. Since this problem is
embarrassingly parallel, I suspect that power vs. parallelism tradeoffs
are quite easily made, and I'm sure that, given the scale of such a
project, it would be quite easy to optimize the cost of power vs. the
cost of hardware to find the cheapest possible spot on the curve.

If you had access to an ultra-modern process -- 45nm with High K
dielectrics, etc., -- I think you could get quite impressive densities
of cracking units on a single die.

That said, the expense of a cracker that could go through an 80 bit
space is not insignificant. Naive back of the envelope calculations,
even assuming substantial cost benefits from fully custom design, give
me the impression that a cracker that can do 80 bits in a week is still
a billion dollar proposition -- worthwhile for a large nation-state with
very high value targets, but not worthwhile for anyone else.

(Can anyone else try the back of the envelope and say if mine is more or
less right?)

The other problem is, of course, that it isn't obvious what the target
of such a cracking cluster would be at this point.  3DES and AES are
beyond the capabilities of such a cluster.  Presumably an nation state
would have to need to attack specialized algorithms used by opponents
who are stupid enough to use short key lengths but smart enough not to
use algorithms that are themselves weak and thus attacked without
exhaustive search.

Perry
-- 
Perry E. Metzger		perry at piermont.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com