Re: code validation?

From: laird popkin <lairdp_at_gmail_dot_com>
Date: Tue Feb 22 2005 - 18:14:12 CST

I'm not a cryptographer, but as far as I can see, the "broken" SHA-1
doesn't mean much for OVC. The attack allows one to somewhat less
slowly find some other "random" data that hashes to the same value
that the original data hashes to. The original data was a working
computer program that implements voting. The "random" data is just a
file that hashes to the same value, so it would pass the hash check,
but since it consists essentually of random numbers it probably
wouldn't actually be an executable program, much less one that looked
just like the OVC software but produced faked results (for example).
Yes, this means that the SHA-1 alone doesn't prove that the file
wasn't tampered with, but between matching the SHA-1 and a trivial
inspection of the program, it should be easy to weed out any "fake"
OVC software generated with matching SHA-1 hashes.

- LP

On Tue, 22 Feb 2005 16:11:29 -0500, David Mertz
<voting-project@gnosis.cx> wrote:
> > 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 arthur@openvotingconsortium.org
>

-- 
- Laird Popkin, cell: 917/453-0700
_______________________________________________
OVC discuss mailing lists
Send requests to subscribe or unsubscribe to arthur@openvotingconsortium.org
==================================================================
= 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