Re: Migrating away from SHA-1?

[Theodore Ts'o <tytso@mit.edu>]

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.  The second has
to contain whatever security backdoor the attacker is going to try to
introduce into the git tree.  Ideally this is also should pass muster
by humans who are inspecting the code, but if the attack is targetted
against a specific victim which is not likely to look at the code, it
might be okay if something like this:

#if 0  /* this is needed to make the hash collision work */
aev2Ein4Hagh8eimshood5aTeteiVo9hOhchohN6jiem6AiNEipeeR3Pie4ePaeJ
fo8eLa9ateeKie5VeG5eZuu2Sahqu1Ohai9ohGhuAevoot5OtohQuai7koo4IeTh
ohCefae4Ahkah0eiku2Efo0iuHai8ideaRooth8wVahlia0nuu1eeSh5oht1Kaer
aiJi4chunahK9oozpaiWu7viee5aiFahud6Ee2zieich1veKque6PhiaAit1shie
#endif

... was hidden in the middle of the replacement blob.  One would
*hope*, though, that if something like this appeared in a blob that
was being sent to the upstream repository, that even a sloppy github
pull request reviewer would notice.

That's because in this scenario, the attacker needs to be able to get
the first blob into the git tree first, which means they need to be
trusted enough to get the first blob in.  And so the question which
comes to mind is if you are that trusted (or if the git pull review
process is that crappy), might it not be easier to simply introduce an
obfuscated code that has a security weakness?  That is, something from
the Underhanded C contest, or an accidental buffer overrun, hopefully
one that isn't noticed by static code checkers.  If you do that, you
don't even need to figure out how to create a SHA-1 collision.

Does that mean that we shouldn't figure out how to migrate to another
hash function?  No, it's probably worth planning how to do it.  But we
probably have a fair amount of time to get this right.

Cheers,

					- Ted