Re: Migrating away from SHA-1?

["H. Peter Anvin" <hpa@zytor.com>]

On April 14, 2016 10:23:03 AM PDT, David Turner <dturner@twopensource.com> wrote:
>On Wed, 2016-04-13 at 21:53 -0400, Theodore Ts'o wrote:
>> On Tue, Apr 12, 2016 at 07:15:34PM -0400, David Turner wrote:
>> > 
>> > If SHA-1 is broken (in certain ways), someone *can* replace an
>> > arbitrary blob.  GPG does not help in this case, because the
>> > signature
>> > is over the commit object (which points to a tree, which eventually
>> > points to the blob), and the commit hasn't changed.  So the GPG
>> > signature will still verify.
>> 
>> The "in certain ways" is the critical bit.  The question is whether
>> you are trying to replace an arbitrary blob, or a blob that was
>> submitted under your control.
>> 
>> If you are trying to replace an arbitrary blob under the you need to
>> carry a preimage attack.  That means that given a particular hash,
>> you
>> need to find another blob that has the same hash.  SHA-1 is currently
>> resistant against preimage attack (that is, you need to use brute
>> force, so the work factor is 2**159).  
>> 
>> If you are trying to replace an arbitrary blob which is under your
>> control, then all you need is a collision attack, and this is where
>> SHA-1 has been weakened.  It is now possible to find a collision with
>> a work factor of 2**69, instead of the requisite 2**80.
>> 
>> It was a MD5 collision which was involved with the Flame attack.
>> Someone (in probably the US or Isreali intelligence services)
>> submitted a Certificate Signing Request (CSR) to the Microsoft
>> Terminal Services Licensing server.  That CSR was under the control
>> of
>> the attacker, and it resulted in a certificate where parts of the
>> certificate could be swapped out with the corresponding fields from
>> another CSR (which was not submitted to the Certifiying Authority)
>> which had the code signing bit set.
>> 
>> So in order to carry out this attack, not only did the (cough)
>> "unknown" attackers had to have come up with a collision, but the two
>> pieces of colliding blobs had to parsable a valid CSR's, one which
>> had
>> to pass inspection by the automated CA signing authority, and the
>> other which had to contain the desired code signing bits set so the
>> attacker could sabotage an Iranian nuclear centrifuge.
>> 
>> OK, so how does this map to git?  First of all, from a collision
>> perspective, the two blobs have to map into valid C code, one of
>> which
>> has to be innocuous enough such that any humans who review the patch
>> and/or git pull request don't notice anything wrong.  
>
>It looks like Linux contains at least some firmware which would be hard
>to audit.  One random example is:
>firmware/bnx2x/bnx2x-e1h-6.2.9.0.fw.ihex

Either way, I agree with Ted, that we have enough time to do it right, but that is a good reason to do it sooner rather than later (see also my note about freezing the cryptographic properties.)
-- 
Sent from my Android device with K-9 Mail. Please excuse brevity and formatting.