[193812] in North American Network Operators' Group
Re: SHA1 collisions proven possisble
daemon@ATHENA.MIT.EDU (Vincent Bernat)
Fri Feb 24 12:04:04 2017
X-Original-To: nanog@nanog.org
From: Vincent Bernat <bernat@luffy.cx>
To: nanog@nanog.org
Date: Fri, 24 Feb 2017 18:00:30 +0100
In-Reply-To: <alpine.LRH.2.02.1702231910380.3485@soloth.lewis.org> (Jon
Lewis's message of "Thu, 23 Feb 2017 19:28:44 -0500 (EST)")
Errors-To: nanog-bounces@nanog.org
=E2=9D=A6 23 f=C3=A9vrier 2017 19:28 -0500, Jon Lewis <jlewis@lewis.org>=
=C2=A0:
>>> 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 mo=
re
>> correctly, sign the SHA-1 hash of the document).
>>
>> I then take your signed copy, take out the contract, splice in a differe=
nt
>> 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 w=
ith
>> 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.
--=20
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
