SHA1 collisions proven possisble

Vincent Bernat bernat at luffy.cx
Fri Feb 24 17:00:30 UTC 2017


 ❦ 23 février 2017 19:28 -0500, Jon Lewis <jlewis at lewis.org> :

>>> cost! However this in no way invalidates SHA-1 or documents signed by
>>> SHA-1.
>>
>> We negotiate a contract with terms favorable to you.  You sign it (or more
>> correctly, sign the SHA-1 hash of the document).
>>
>> I then take your signed copy, take out the contract, splice in a different
>> version with terms favorable to me.  Since the hash didn't change, your
>> signature on the second document remains valid.
>>
>> I present it in court, and the judge says "you signed it, you're stuck with
>> the terms you signed".
>>
>> I think that would count as "invalidates documents signed by SHA-1", don't you?
>
> Depends on the format of the document.  As was just pointed out, and I
> almost posted earlier today, that there are collisions in SHA-1, or
> any hash that takes an arbitrary length input and outputs a fixed
> length string, should be no surprise to anyone.  Infinite inputs
> yielding a fixed number of possible outputs.  There have to be
> collisions.  Lots of them. The question then becomes how hard is it
> find or craft two inputs that give the same hash or one input that
> gives the same hash as another? Doing this with PDFs that look
> similar, which can contain arbitrary bitmaps or other data is kind of
> a cheat / parlor trick.
>
> Doing it with an ASCII document, source code, or even something like a
> Word document (containing only text and formatting), and having it not
> be obvious upon inspection of the documents that the "imposter"
> document contains some "specific hash influencing 'gibberish'" would
> be far more disturbing.

The collision is contained in about 128 bytes. It is easy to hide this
collision in almost any document. You need a common prefix between the
two documents, the collision, then anything you want (you still need a
lot of processing power to get the collision matching your document). It
is a weakness specific to SHA-1. Another same-length hash (like
RIPEMD-160) is not affected.
-- 
The man who sets out to carry a cat by its tail learns something that
will always be useful and which never will grow dim or doubtful.
		-- Mark Twain



More information about the NANOG mailing list