A new hash algorithm for Git [LWN.net]

A new hash algorithm for Git

Posted Feb 3, 2020 22:02 UTC (Mon) by Cyberax (✭ supporter ✭, #52523) [Link] (4 responses)

The best attacks on SHA-1 reduce complexity from 2^80 (still unfeasible to brute-force) to 2^68 (just barely feasible). That's about 2^12 times speedup.

SHA-256 has 2^128 collision probability to start with, any realistic attacks won't lower the complexity below 2^100 (WAY outside of possible attacks).

A new hash algorithm for Git

Posted Feb 4, 2020 2:47 UTC (Tue) by wahern (subscriber, #37304) [Link] (3 responses)

The recently published SHAttered attack (https://shattered.it/) took ~2^63 computations. That said, AFAIU none of the recent SHA-1 attacks carry over to SHA-256. And other than length extension attacks, I don't think the Merkle–Damgård construction is considered fundamentally broken; it's just well analyzed.

A new hash algorithm for Git

Posted Feb 4, 2020 11:32 UTC (Tue) by heftig (subscriber, #73632) [Link] (2 responses)

Since Git prefixes an object with its length before hashing it, does length extension still apply?

A new hash algorithm for Git

Posted Feb 5, 2020 9:19 UTC (Wed) by bmenrigh (subscriber, #63018) [Link] (1 responses)

Well no (and yes). Depending on the specific details of the length prefix you may be able to extend the hash with a longer message whose length is interpreted using part of the start of the existing message. In this way you would be limited to only certain pre-determined lengths only. I don’t know the details of the how git does things to comment further.

A new hash algorithm for Git

Posted Feb 5, 2020 15:02 UTC (Wed) by johill (subscriber, #25196) [Link]

I don't think this is possible - git prefixes with e.g. "blob 1234\0" (yes, the ascii text) for a 1234-byte blob. It then looks for the first \0 and you can't get it to treat that as a valid length digit.

A new hash algorithm for Git

Posted Feb 4, 2020 2:16 UTC (Tue) by KaiRo (subscriber, #1987) [Link] (8 responses)

For signed commits or other signatures, the other question is quantum-safety of the signatures themselves, which is also probably not ensured right now. I'm actually a bit more worried about switching to quantum-safe async crypto than about those hash collisions, but both are somewhat worrisome.

A new hash algorithm for Git

Posted Feb 4, 2020 2:22 UTC (Tue) by mirabilos (subscriber, #84359) [Link] (7 responses)

Quantum what?

I was just wondering because the signature is over the SHA-1 hash.

A new hash algorithm for Git

Posted Feb 4, 2020 2:39 UTC (Tue) by KaiRo (subscriber, #1987) [Link] (6 responses)

"Signature" usually means that you sign some arbitrary data (in this case a SHA-1 hash) using some async crypto key material (in this case usually some RSA variant). RSA and other async crypto algorithms used commonly nowadays are not safe from being cracked by quantum computers once we have some with enough capacity. That puts all signatures, identification and encryption based on those algorithms at risk once we have those kinds of quantum computers, so where we use those we will need to find solutions for that (quantum-safe algorithms are in development or testing right now but not finalized AFAIK). The common hash algorithms have no big issues with that, so it doesn't affect git itself directly, but it certainly does or will affect the signatures of signed commits.

A new hash algorithm for Git

Posted Feb 4, 2020 19:57 UTC (Tue) by mirabilos (subscriber, #84359) [Link] (5 responses)

I know what a signature is and all that, but I absolutely don’t get where you are going with this.

When I currently have a signed commit…

-----BEGIN cutting here may damage your screen surface-----
$ git cat-file -p HEAD
tree 937122472a792ada03309a60b7a31e02a29aa764
parent 53861b4a1544c7c8825f1414c37c9694c84c5d92
author mirabilos <m@mirbsd.org> 1580771045 +0100
committer mirabilos <mirabilos@evolvis.org> 1580771470 +0100
gpgsig -----BEGIN PGP SIGNATURE-----
Comment: ☃ ЦΤℱ—８　☕☂☄

iQIcBAABCQAGBQJeOKiPAAoJEIlQwYleuNOzSzYP/3xowIYpxJwuHfdP8oRekbSZ
eVI9mO5g8KC+SUe5oGCbocH478pBUp5AOYlFGL0awetklijRmF+EeYp+a1IluCww
GD2pSPFCpxSjScERlED5YYpfaaw1XEutoGHYQNMAUQhlRMzS8NwhGJjTuoIbvE4X
hMntoMtDM7sPJ3CIADIoYzXIcdaqsELvqptuvNdo9S/PIyR6OFWhpF68Qn+SILqk
N+fOA/KpgQLsRmMEVy3YtqmMdToYXoP3m4ec0/QSoN90QVrO9ZnVG2+0f9yeEiVn
xEWiaSSsz5vtniBLzOvQ6FeE0h08ZsQi9dcTj8aq3tDtUJb2sQi6q79Gl5StmfHI
8HN9q8ZQP/Vh8kIT5z3lcuNnb3y7sc90ZzY5i7Q2YwfKNbJ5mAEMvSgzBxcrDflR
/kjUJcXJg98IzJsWbE3k9gRc9yatqKQii0GiaxID13fCfl++4klJrFMEyoTdhta4
5a7vGa6OuHr+MWsT+35yQsR6Mt1DnMY2oNArTgWG3DfNQK8zb7rIExPbuV6pLP2O
X67ZCVSHwRTrLWnDHjSuQH4Hfoibq96Ga9wJwEjw0+sWKzg4CgvQH6L+UiXIZO0/
2+hhF507WUCKh8Uit2nrRsGhVnXJrI5QZsD857oAifcBFslbTLwTCkj+3gccHxwH
A/BAeG4zN0JrdvMzx0pN
=9w0P
-----END PGP SIGNATURE-----

erm yes, the symlink…
-----END cutting here may damage your screen surface-----

… or tag…

-----BEGIN cutting here may damage your screen surface-----
$ git cat-file -p mksh-57-6
object 3ece4d6c67f32b8e2b9b00900d05cc06c658fc87
type commit
tag mksh-57-6
tagger mirabilos <mirabilos@evolvis.org> 1580771932 +0100

mksh (57-6) unstable; urgency=low
-----BEGIN PGP SIGNATURE-----
Comment: ☃ ЦΤℱ—８　☕☂☄

iQIcBAABCQAGBQJeOKpdAAoJEIlQwYleuNOzE3EP/1Qu6w3ZnelCbTcR0/lR1QaH
qisRANlIKYq0MVDOmhzGZ4m6/ri9b2njI16x0R3otaIT2QfG2ldj8U/Sq7Vpm6Xb
uTpMluMzFj6sungPYOCvgbDVcVqt4+qCAwtFL5Lt2gpfN45KwYO0RdrSCY8wFD3N
TO3Wq7M3DXt99F9mMY/L+XfvbpDAMzjCEK0tgTAal4QWnnb7V2Y1bVnZjos5XZTV
hWW4kJMqBp2Hf99KLqnjijfPgZkqbSMYKy14Nsqo1cSujwPpOH2MgDbyuun1SuSA
K6U0JT1iyIsL/ixkCx8vi6ejIGGQXXpGEq4K4RA3Wc4ALB/FWC9Y2MrCEExG0wEV
tDkto90sbD6Nymnii1apG2Q7aSyDNDjsiRT2tzYN2S5EzItYtV0V8ZXoxiYk/c/Z
ttAcdXxh8R4+5p3yNYwAjTSzZe8ohvgHFXoAUGVpk7g9oArlNiJmqkrW3BGdFrCb
gH0h4UpiXr3pgnlPi247alGT18Xly5cBX3CbjORGDNsUDZoGPLlVuyW46PaRel3V
P8BODtOoFkoK7JyFCRP70Z97vQig+L9nbN5tf50haYlxhO7oOSU7RzQJxgv2tLza
AT0bg6Wfs4I9VV/MjocIirwrbihZY1gMgURgad5PdoNjoyNy+vd6OKMFQm1i/eUF
hGIwKngrue1A9RMKPaCG
=JPiZ
-----END PGP SIGNATURE-----
-----END cutting here may damage your screen surface-----

… these hardcode the SHA-1 hashes. These are, thus, needed to verify the signature. This also cannot be rewritten.

As a user, I’d expect that, after full git conversion to a new hash, I’ll still be able to verify these. That was the question.

A new hash algorithm for Git

Posted Feb 5, 2020 9:50 UTC (Wed) by geert (subscriber, #98403) [Link] (2 responses)

So you have to keep the translation table from SHA-1 to SHA-256 for all old objects.

Cfr. " To address this issue, one can imagine that the Git developers may eventually add a mode where translations for old SHA‑1 hashes remain in the repository, but no SHA‑1 hashes for new objects are added.".

A new hash algorithm for Git

Posted Feb 13, 2020 23:57 UTC (Thu) by floppus (guest, #137245) [Link] (1 responses)

But to verify a signature, you don't just need a translation table for all the old objects, you actually need the old objects themselves (or be able to somehow reconstruct the original objects, byte for byte.)

Otherwise, assuming you trust the person who generated the signature but you don't trust the contents of the git repository, you have no way of knowing that the commit you're looking at actually corresponds to the same source tree that the person signed.

A new hash algorithm for Git

Posted Feb 14, 2020 1:20 UTC (Fri) by excors (subscriber, #95769) [Link]

Perhaps the translation table should be signed. After the repository is converted to SHA-256, someone trusted (e.g. Linus Torvalds) can run a tool that scans through the translation table, fetches the object corresponding to each SHA-256, computes its SHA-1, verifies the translation table says the same SHA-1, then signs the translation.

Then a regular user can verify a commit (identified by its SHA-256) by using the signed translation table to find the corresponding SHA-1 and checking the committer's signature of that SHA-1. That avoids the performance cost of having to fetch the entire object from disk to compute its SHA-1 before checking the signature, while avoiding the danger of a falsified translation table that tries to link the signed SHA-1 to a totally different commit that doesn't actually match that SHA-1.

As a bonus, if SHA-1 gets completely broken in the future, I think the repository would remain secure. If a future attacker can manufacture a commit whose SHA-1 matches an old signed commit, they could try to insert that commit into the repository with a valid translation table entry (containing the colliding SHA-1 and a new non-colliding SHA-256) and reuse the old commit's signature on their new commit (since it's only signing the SHA-1). If the translation table was unsigned, the attacker could succeed. But if it was signed, there's no way to insert the new translation table entry without tricking Linus into signing the new table. And Linus can avoid being tricked if he simply stops signing any new translation tables beyond the point when SHA-1 gets completely broken (which should be many years away).

A new hash algorithm for Git

Posted Feb 5, 2020 19:40 UTC (Wed) by KaiRo (subscriber, #1987) [Link] (1 responses)

The problem is that with quantum computers, you can actually forge signatures, i.e. you actually _can_ rewrite those things and/or make something, e.g. a git commit, look like it could be verified to be from someone despite it being from someone else - at least using the current (RSA) mechanisms. We need to use new, quantum-safe signatures in the future. Unfortunately, the security community has not settled on what the widely-accepted algorithms for that may be, though there are developments in this area.

The actual hash that is signed is a different topic. You should be able to verify those signed hashes as long as the original hash is available (part of what the original article is about) and the signature can be trusted (which may not be the case forever, as I was pointing to).

A new hash algorithm for Git

Posted Feb 6, 2020 15:40 UTC (Thu) by luto (subscriber, #39314) [Link]

There are several excellent hash-based signature algorithms that appear to be fully secure against quantum attack. They don’t extend to encryption or to key exchange, so they are not full RSA replacements.

Maybe Skip SHA-3

Posted Feb 4, 2020 8:19 UTC (Tue) by tialaramex (subscriber, #21167) [Link]

Adam Langley suggests sticking with the SHA-2 family while things shake out in the relatively new frontier that is Keccak-style algorithms.

https://www.imperialviolet.org/2017/05/31/skipsha3.html

SHA-3 is significantly slower than SHA-2 which is already very slow for a hash (if we didn't need a crypto hash there are lots of very very fast hashes used elsewhere) so it's a big penalty when you aren't buying say, future proofing, which you aren't because SHA-3 was agreed way before the dust settled on how to do this style of hash, there are currently half a dozen like it, all seemingly secure, most faster, none standardised. This isn't like AES where the rough direction is understood and now you're buying hardware that accelerates it, so that not doing AES ends up slower because you lose hardware assist.

Langley recommends SHA-512/256 (note for those unfamiliar this is literally the name of the hash, not two different hashes you can pick from) if you care about length extension attacks and otherwise SHA-256 is fine. The reason for SHA-512/256 is that the output isn't the entire internal state, it's only half the state, meaning a length extension fails, and it only needs the same size structure to store the hash as SHA-256 (but it is slower).

A new hash algorithm for Git

Posted Feb 4, 2020 10:41 UTC (Tue) by epa (subscriber, #39769) [Link] (1 responses)

Also, I wonder, will I be able to verify old signed commits and tags after the transition is complete?

Perhaps you would be able to verify them slowly by recomputing the SHA-1 hashes of each object from scratch, even if they aren't stored in the repository.

A new hash algorithm for Git

Posted Feb 5, 2020 17:06 UTC (Wed) by droundy (subscriber, #4559) [Link]

That's my impression from the article, and why the compatibility mode is slow.

A new hash algorithm for Git

Posted Feb 5, 2020 8:26 UTC (Wed) by bluss (subscriber, #47454) [Link]

> By then, SHA-256 will be broken as well. SHA-2 uses the same underlying structure as SHA-1 and is almost only more secure due to its length

It's true the structure and construction is the same, but SHA-2 is has a bigger state and much more involved mixing steps per round, and those are the biggest difference versus SHA-1, not the digest length.