SHA-1 [was Re: code validation?]

From: Jeff Almeida <spud_at_spudzeppelin_dot_com>
Date: Wed Feb 23 2005 - 15:47:32 CST

Also Sprach laird popkin:
>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.

What the developers did was nothing particularly extraordinary: we're
guaranteed by the Fundamental Theorem of Algebra a hashing functions
will have a kernel, or restated, that there will be a computably
large-sized collision domain for a given hash. All they did was
demonstrate a way to "work backwards" and generate another element in the
collision domain for a particular value.

That said, unless someone can demonstrate that the elements of the
collision domain are dense, it remains a valid method for hashing code for
alterations, because there is still no ability to readily generate a code
sample meeting the following criteria:

* Binary application in the same format as the original.

* Original functionality sufficiently duplicated to escape immediate
  detection.

* New (exploitive) functionality successfully introduced.

What it DOES rule out SHA-1 being used for is validating the authenticity
of data that was random-looking to begin with, such as using SHA-1 to sign
cryptographic key data (a common application); there is nothing to
otherwise distinguish one element of the collision domain with another!

jeff :)

-- 
******************************************************************************
"Modern technology is already in use that makes electronic voting possible, 
 with accurate and almost immediate tabulation and with paper ballot printouts 
 so all voters can have confidence in the integrity of the process." -J.Carter
******************************************************************************
Jeff D. "Spud (Zeppelin)" Almeida                              Corinth, TX, US
_______________________________________________
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:12 2005

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