Re: code validation?

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Tue Feb 22 2005 - 15:11:29 CST

> I noticed this weekend that the most popular hash, SHA-1 has been
> broken. It now can be cracked in about 2 days on reasonably affordable
> equipment. Given the non-transient nature of voting software we will
> need to go to a different hash like SHA-256 or SHA-512.

Fred (fortunately) enormously overstates the attack on SHA-1. But in
crypto: attacks only get better, never worse. I read one comment that
"Now is the time to walk, but not *run*, to the exits on using SHA-1."
SHA-256 and SHA-512 LOOK good on the surface, but they have not been as
thoroughly studied as SHA-1, so weaknesses are conceivable (brute-force
block length is never the whole question, as the recent attack shows).

Specifically, the attack by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu
lets you find a collision in 2^69 steps rather than in 2^80 steps that
brute force requires. That's 2000 times easier than it used to be, but
still not quite *easy*.

A more realistic idea of what the attack means is that it is now
possible to construct a highly-specialized $30 million machine that can
find collisions in less than a month. Not 2 days, and not what I would
call "commodity hardware." Also, finding a collision between two
simultaneously constructed strings is FAR easier than finding a false
string that hashes to a pre-specified hash value. Under the "birthday
paradox" the former takes about the square root of the number of steps
as the latter.

So suppose that OVC pre-publishes a hash of its software. And
stipulate that the Wang, et al. attack extends to constructing a
forgery of a known hash target. That means it's likely to take an
attacker 2^138 steps to create forged OVC software. That difficulty is
FAR, FAR more than is now possible (or will ever be possible in this
little universe of ours, count the number of particles in the galaxy
and the like).

But like I said, attacks get better, not worse. Other cryptographers
will run with Wang, et al.'s work in the future. Their work is
unquestionably profound, important, and brilliant... but we don't need
to get carried away about it's significance quite yet.

OVC discuss mailing lists
Send requests to subscribe or unsubscribe to
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
Received on Sun Feb 27 17:17:10 2005

This archive was generated by hypermail 2.1.8 : Sun Feb 27 2005 - 17:17:13 CST