A new hash algorithm for Git

https://lwn.net/SubscriberLink/811068/cfeb6a67b8dfbe47/

by Tomte • 6 years ago

465 233 6 years ago

jakeogh2• 6 years ago

Is there an archive of crypto related future predictions?

How long until a specified length preimage attack can break bittorrent blocks?

I remember a paper published a ~decade ago estimating very short (well funded) ASIC sha1 collisons. Anyone have that ref?

EDIT: Should I have not said preimage? My understanding is bittorrent is broken (by DDoS, not infohash(?)) if you can make a bad block that matches the length and sha1 of a target block.

glandium• 6 years ago

How long until a specified length preimage attack can break bittorrent blocks?

Even MD5 still doesn't have a known preimage attack, so... many many years?

tialaramex6• 6 years ago

To be fair for MD5 there is a known attack, it's just impractical. It's a real attack though because the whole point of a crypto hash is that you'd have to brute force it to win, and the paper shows a slightly quicker way because MD5 is broken. It's just not quick enough that you could actually do it.

Oh wait, perhaps you actually meant preimage as you said rather than I assumed second preimage. OK yes, that isn't ever going to be possible for non-trivial inputs.

pabs32• 6 years ago

There is one for hashes:

http://valerieaurora.org/hash.html

strenholme8• 6 years ago

Not to mention this one, which covers more hash algorithms:

https://electriccoin.co/blog/lessons-from-the-history-of-att...

hannob2• 6 years ago

Preimage is really a whole different beast than collission.

It's also not particularly surprising. Just by its length SHA-1 has in its best case 80 bits of collission security and 160 bits of preimage security.

Now its important to understand that attacks usually don't cause full devastation, but they usually make attacks a bit better than optimal.

Attacks in the 60 bit range is what's possible, attacks in the 70 bit range is what's dangerous. It's easy to imagine that relatively small deviation from optimal security gets SHA-1 from 80 into the dangerous territorry (the attacks are in the low 60s range). However getting from 160 bit down to the 60/70 bit range would require massive improvements in attacks.

It's safe to say that SHA-1 is still very far from preimage attacks. Still to be clear I'd still recommend to get rid of it whereever you can. The far bigger risk is that you think you only need preimage security, while you actually need collission security for scenarios you haven't thought about.

tialaramex6• 6 years ago

EDIT: Should I have not said preimage? My understanding is bittorrent is broken (by DDoS, not infohash(?)) if you can make a bad block that matches the length and sha1 of a target block.

There are three different attacks

1. Collision, which is practical (expensive but practical) for SHA-1 today, lets somebody make two documents A and B which have the same hash. This is only useful if you can fool people somehow into accepting document B when they think it's document A because of the hash, for example with digital signatures.

2. Pre-image, which is not practical for any hashes you care about including MD5. This lets you find the document A given the hash(A) value. This is very niche, since obviously for large documents by the pigeon hole principle there will be many such pre-images and it's impossible to get the "right" one, for small inputs it can be relevant, sometimes.

3. Second Pre-image, likewise not practical. Given either document A or hash(A) which you could easily determine from document A, this lets you produce a new document A' that is different from A but hash(A') == hash(A). This would be extremely bad, and is what you'd need to attack real world Bittorrent from somebody else.

Often people say "pre-image" meaning strictly second pre-image, it's usually clear from context, and a true pre-image attack as I explained above is only rarely relevant.

Collision would only let bad guys corrupt their own purposefully constructed collision bittorrent, which like, why? So yes, Bittorrent would only really be in serious trouble if there was a second pre-image attack. But on the other hand, don't use broken cryptographic primitives. Attacks only get better, always.

SAI_Peregrinus3• 6 years ago

1.5 Chosen-prefix collision: Given a prefix A, generate two values AB and AC, where B and C differ but are both prefixed with A. (AX is A concatenated with X). This exists for SHA1. It's more powerful than a basic collision wheri you can't pick the prefix, but weaker than either type of pre-image.

dfox• 6 years ago

The reason why people mostly meand second pre-image when saying unqualified "pre-image" is that probably any imaginable method of reversing a hash function (given sufficiently long input to the hash) will with overwhelming probability produce hash input that is different from the original.

jakeogh2• 6 years ago

Thanks. Is there a name for collision with the same preimage size?

sandGorgon2• 6 years ago

does anyone know if github/bitbucket support it today ?

freddie_mercury• 6 years ago

Why would they support it? The article clearly states it is nowhere close to being useful yet.

It is untested, unstable code that can only write to repositories and not read them.

"Much of the work to implement the SHA‑256 transition has been done, but it remains in a relatively unstable state and most of it is not even being actively tested yet. In mid-January, carlson posted the first part of this transition code, which clearly only solves part of the problem:

"First, it contains the pieces necessary to set up repositories and write _but not read_ extensions.objectFormat. In other words, you can create a SHA‑256 repository, but will be unable to read it. "

sandGorgon2• 6 years ago

actually - i might have worded it confusingly.

For smaller projects (like my own), can i move to sha-256 with no expectation of backward compatibility today ?

tcharlton• 6 years ago

I can't find documentation for the command in the article:

    git convert-repo --to-hash=sha-256 --frobnicate-blobs --climb-subtrees \
    --liability-waiver=none --use-shovels --carbon-offsets

Surely some of those options aren't real...

amarshall• 6 years ago

A new version of Git can be made…with a simple command like: <command> … note that the specific command-line options may differ

Gives me the impression that it’s a construction of the article alone. Unsurprising, given the snark of the options.

buserror• 6 years ago

Of course they are ?!?!!? https://git-man-page-generator.lokaltog.net/

(never fails to amuse me)

bangboombang2• 6 years ago

Oh dear god. Because it's git related, my brain somehow still tries to make sense of that stuff because it just seems so real.

hrgiger• 6 years ago

reminds me https://projects.haykranen.nl/java/

pabs32• 6 years ago

That seems to be intended to be humour.

kzrdude4• 6 years ago

Well, I loved it, for one.

throwaway744678• 6 years ago

I believe we have here an example of Poe's law [1]

[1] https://en.wikipedia.org/wiki/Poe%27s_law

mratsim• 6 years ago

Thus, unlike some other source-code management systems, Git does not (conceptually, at least) record "deltas" from one revision to the next. It thus forms a sort of blockchain, with each block containing the state of the repository at a given commit.

Color me surprised, dropping the "blockchain" word in the middle of the introduction

AndrewDucker• 6 years ago

Git is a blockchain.

Being, as it is, a chain of signed blocks.

tonyedgecombe• 6 years ago

Git is a Merkle tree as is a blockchain.

https://en.wikipedia.org/wiki/Merkle_tree

afiori3• 6 years ago

It is still a sort of namedropping. In the sense that it is used due to the trendiness of the term.

It is entirely possible and likely that it is used for didactic purposes as many people are familiar with the blockchain structure and its use of hashes.

anaisbetts• 6 years ago

I don't understand the practical attack vector for breaking SHA1s in Git. Not only are objects checksummed by SHA1, they also encode the length. Finding a SHA1 collision is plausible, but finding a SHA1 collision that both lets you do something Nefarious, and is the length you need, seems really really unlikely

tialaramex6• 6 years ago

This makes no sense. The collision manufacture algorithm of course produces the same length output in both the A and B documents. Doing otherwise would be considerably harder in fact.

HereBeBeasties• 6 years ago

You're assuming that 100% of the source code matters, but most source code has comments. Some has a lot of comments (boilerplate headers). Delete all the comments and superfluous whitespace, add nefarious code, put in a comment in the remaining bytes for the sole purpose of causing a hash collision (likely plenty of bytes to play with).

scoutt• 6 years ago

Yes, but...

this new version would have to contain the desired hostile code, still function as a working floppy driver, and not look like an obfuscated C code contest entry

It's still plausible that one can pull a trick like that to introduce malicious code into the repo, but improbable.

est31• 6 years ago

The shattered collision attack featured two pdfs with the same sha1 and wait for it, the same length. Also note that even with normal sha1, the length is hashed into the final sha1 hash already, that's what the merkle damgard scheme is about. You can read about it on Wikipedia.

Reusing the precise collision from the shattered attack is made impossible by initializing the state with anything other than the prefix from the shattered attack. But the cost for mounting such an attack yourself is only 11k USD. However, as git uses the sha1collisiondetection library, such an attack would be detected by current git. Thus, this library is a much better protection than the length encoding.

xxs2• 6 years ago

Length actually is already part of the hash result... and the sha-1 collision uses the same length pdfs.

phaemon• 6 years ago

As mentioned, the shattered PDFs[1] have the same length, however it's worth noting that adding the Git header breaks the matching, ie. you get different SHA sums for the files in Git because of the header.

[1] https://shattered.io/

kzrdude4• 6 years ago

SHA1 is crumbling. It's being replaced because it is likely to be broken further, in practice.

upofadown• 6 years ago

To make the collision work you need to produce two different files, both with some randomish looking junk in them. So if you can do that in a way where you can substitute one of the files for the other without getting caught then you are almost for sure smart enough to also figure out a way to make the lengths the same.

acidictadpole• 6 years ago

The author does seem to concede that hitting all the checkmarks in an attack on git would be pretty tricky:

An attacker would not just have to do that, though; this new version would have to contain the desired hostile code, still function as a working floppy driver, and not look like an obfuscated C code contest entry

The whole idea is that they want to switch away before these things become likely. They are unlikely now, but SHA-1 is only getting weaker as time goes by and more research is done.

pdonis• 6 years ago

and not look like an obfuscated C code contest entry

The full quote here is even better:

"and not look like an obfuscated C code contest entry (at least not more than it already does)."

nnx• 6 years ago

Surprising they didn't go with Blake3 instead since it has much higher performance and Git's performance-oriented ethos.

Ayesh• 6 years ago

Linux also has the ethos to choose boring technology. SHA2 has been here for so long and battle tested. For the majority of us, it is the natural choice. I'm not implying anything negative about SHA3/Blake/Keccak.

dchest2• 6 years ago

BLAKE3 was released a month ago! The decision for new hash in git was made about two years ago. BLAKE2 was considered, though.

SHA-256 is fine. The biggest problem is switching to it...

fanf2• 6 years ago

They made the choice years ago and blake3 was announced last month.

nullc2• 6 years ago

Git's performance-oriented ethos

Than sha256 will likely be preferable in the long run: It's faster with SHA-NI than blake3.

If you're not developing on a system with sha-ni, get with the program. Zen2 is freeking awesome. :)

wolfgke2• 6 years ago

Zen2 is freeking awesome. :)

SHA-NI was introduced with the Intel Goldmont microarchitecture.

majewsky3• 6 years ago

Great! I can't wait to have to throw away perfectly fine systems because of a new Git version. /s

pjc50• 6 years ago

I'm waiting for Blake7.

xxs2• 6 years ago

fond memories indeed....

curben• 6 years ago

The decision was made before the release of Blake3. The article did mention the algorithm is no longer hardcoded (hence the ability to support both SHA1 & SHA256). This means it's possible to transition to Blake3 (or any other) in future, though it won't be trivial.

simias2• 6 years ago

Is a significant part of git's typical profile spent computing hashes? I'm genuinely asking because I don't know the answer. I'd expect all the diffing and (potentially fuzzy) merging to be significantly more expensive operations, at least as far as big-O is concerned.

hannob2• 6 years ago

Is a significant part of git's typical profile spent computing hashes?

No. Hashes are really cheap.

This annoys me a bit, because every discussion about hashing goes into endless bikeshedding which hash function to use. The simple truth is: SHA2, SHA3, Blake2/3 are all good enough from both a security and performance perspective that for almost any use case and the advantages and disadvantages are so minor that it really doesn't matter.

bjoli• 6 years ago

There are organisations that can only use approved crypto for various certifications and government contracts. It would be bad to drive such users away from git.

Under "feedback from git people" on https://www.mercurial-scm.org/wiki/SHA1TransitionPlan

k5hp• 6 years ago

Just in case: http://archive.is/omsjJ

GlitchMr6• 6 years ago

I wonder if it would make sense to use `concat(sha1, sha256)` hash algorithm. This wouldn't change the prefixes while improving strength of an algorithm (by including SHA256 in a hash).

dchest2• 6 years ago

Something to remember about the security of concatenated hashes: https://crypto.stackexchange.com/a/63543/291

GlitchMr6• 6 years ago

I'm well aware concatenation wouldn't necessarily improve the strength. However, the idea is, even if SHA-1 was hopelessly broken. CONCAT(SHA1(x), SHA256(x)) would be at least as strong as SHA-256 (where "at least" means it may have the same strength).

bangboombang2• 6 years ago

This is pretty interesting and shows you shouldn't try to pull any sort of stunts if you're not a crypto expert. I've actually wondered before whether md5 + sha1 would result in something stronger than those two used individually. Now I know.

timvisee• 6 years ago

Very interesting idea. But, wouldn't existing hashed be kept intact anyway.

patrec3• 6 years ago

I supposed you are advocating two distinct Merkle trees? Because otherwise the prefixes will change anyway.

But the only reason this would be attractive is because then people could keep using the existing prefixes to refer to the whole commit. But of course doing this would be insecure. So for this to make any sense at all, people would need to make good choices on when to use an insecure prefix and when to use the whole hash, because it's security relevant. This seems a bit doubtful to me.

GlitchMr6• 6 years ago

To be fair, the prefix problem would exist no matter what hash function would you pick. GitHub displays 7 characters of a hash, giving 28 bits. You could very quickly generate collisions with birthday attack in pretty much no time. Prefixes are always going to be insecure because they are so short.

In fact, https://github.com/bradfitz/gitbrute exists.

ascar• 6 years ago

I'm probably missing something, but isn't it simpler to just make both available separately and allow users to still reference by sha1, if they want to, while sha256 can be used for collision detection by git operations internally?

patrec3• 6 years ago

Correct, and I think this is what they are doing -- you can optionally keep the sha1s around.

rocqua2• 6 years ago

There is a downside that this would mean commit-prefixes remain sensitive to collisions. Hence anyone checking out a commit by a hash-prefix would still be vulnerable.

Not a dealbreaker by far, but still a slight mark against this solution.

u801e• 6 years ago

Does git have code to detect whether a hash prefix is ambiguous? I know that if you use a short prefix (which is more likely to be shared by multiple objects), git will output an error message staying that the object reference is ambiguous IIRC.

IshKebab• 6 years ago

I don't see how it would change anything. A collision of a short prefix is trivial to generate with any hash.

velox_io2• 6 years ago

Unless I'm missing something, why not just allow repositories to be upgraded to SHA2 hashes? The only problem is ensuring everyone's tooling supports it.

majewsky3• 6 years ago

This question is exactly what a major portion of the article covers.

velox_io2• 6 years ago

It isn't the easiest article to read, plus they over complicate things by talking about things such as truncating SHA2 hashes.

I don't see why changing the hashing algorithm is so problematic, hence the reason why I asked the question. Converting a repository to SHA2 should be straight forward (the only issue is everyone's tooling), you could also run the repositories side-by-side. I'm genuinely interested as I think Git & Bittorrent are quite elegant solutions to complex problems.

londons_explore• 6 years ago

I don't think it's that unreasonable to release git binaries today with sha256 support, then wait 5 years, then make all new commits use sha256.

Anyone who tries to use a git client more than 5 years old wouldn't be able to pull+push to a new repo. Sounds reasonable to me. Git clients more than a few years old are pretty broken already due to TLS changes.

Keeping around a dual hash system forever sounds like baggage and complexity that outweighs the benefits.

powerapple• 6 years ago

is it a real problem for git? Do we merge code based on hashes instead of looking at the code.

donatj2• 6 years ago

The problem is in if you can make evil code with the same hash as innocuous code, you can poison people who pull from a given repo you have access to. It would allow you to make changes to the history without merging anything or anyone being the wiser.

It makes the distributed aspect of git untrustworthy, as previously you knew if you pulled from anywhere and the hash was good, you’d pulled the correct code. With SHA1 being functionally broken that’s no longer necessarily the case.

donatj2• 6 years ago

Excuse my ignorance, but couldn’t they just add a SHA256 hash to commit objects (or some new commit-verify object) of the entire trees current concatenated content, leave everything else SHA1 and get the same benefit without rewriting the entire thing from the ground up? Git could even do that as part of the git gc step slowly over time - tag commits with a secondary hash.

Rewriting the whole thing including every git repos history seems like throwing the baby out with the bathwater, when you could just add a secondary transparent verification instead. Just seems like there has to be a better way.

kzrdude4• 6 years ago

Hashing everything in one go doesn't scale well. When making a new commit you want to only hash a proportional part of the repository, and the tree structure of git allows that, only the files and "tree" objects (directory listings) that change are hashed again.

wongarsu• 6 years ago

You can't change past commits to add that hash (without changing all commit hashes), so this method could only protect new commits. For any existing repo this would lead to a very weird security model: We admit that sha1 hashes are broken, and only guarantee that commits made by git versions newer than git x.x.x are safe from after-the-fact modification (or alternatively only commits made after date X).

arve0• 6 years ago

I’m not known with the internal data structure of git, but couldn’t you add the new hash as a commit in a new format “on the side”, leaving the original commit as is?

gregmac• 6 years ago

My inclination is that protecting only new commits might be enough, but it gets me thinking: What would a practical attack on this look like, assuming sha1 was broken? Let's say I'm trying to insert a line of code that does something nefarious, and that it's now trivial to generate "magic text" you can stick anywhere in a file (eg, inside a comment at the end of a line) to get any desired sha1 hash.

Are all the other future commits still valid, or am I going to suddenly get conflicts or garbled text? Depending on where the modification is done, that code might have gone through much more churn -- especially if there are a bunch of sha-256 commits after it (which I can't attack). I don't know enough about how git stores content blobs to answer this.

Second problem: Can I push my replacement commit to another repository (eg, github)? Would even force push work? Do I have to delete branches and re-push my own? If I already have enough permission on the repository to do this, it means I can already push whatever I want -- so does this attack even matter at all?

Assuming that's successful (or I can trick people into using my own repository), what will happen to someone that already has a clone and does a pull? Will they get my change (and will it work or be a pile of conflicts or garbled text)?

Even if only fresh clones will get the changes it could still be quite devastating -- especially if using CI -- but I'm just not clear if this attack is even theoretically possible.

tzs• 6 years ago

Couldn't they make a table that contains a list of all the old objects by SHA1 hash, for for each contains the new SHA256 hash of that object, and then commit this table in the repository?

jayd16• 6 years ago

What if we use the exploit to add the new data but keep the sha1 the same? :)

angrygoat• 6 years ago

This article is via an LWN subscriber link; a cheerful reminder that LWN are good and they are worth subscribing to :) https://lwn.net/subscribe/

john-radio2• 6 years ago

OP's link says it is "subscription-only content," but it is still publicly available. It says that it has been "made available by an LWN subscriber." How does that work?

robjan• 6 years ago

Subscribers receive a sharing link which can be used to share articles with friends. They tolerate sharing on HN because it brings in new customers.

cesarb• 6 years ago

It's a "subscriber link": https://lwn.net/op/FAQ.lwn#slinks

brobdingnagians• 6 years ago

I was interested in how fossil handled the SHA1 transition, and found this nicely explained as below:

https://fossil-scm.org/home/doc/trunk/www/hashpolicy.wiki

Tyr422• 6 years ago

Ah, so it uses "Hardened SHA1", which detects if you are trying to exploit SHA1, and then produces a longer, unambiguous hash. But otherwise Hardened SHA1 has the same output as SHA1, so it's a drop in replacement.

Then it also has a similar looking-ish migration to SHA3-256.

velcrovan4• 6 years ago

Fossil defaults to SHA3-256 since 2.10 (released in October 2019). But it has had SHA3-256 since March 2017, and generally any repos/clones managed with a Fossil version since then have been seamlessly updated to SHA3-256 in the background.

velcrovan4• 6 years ago

Fossil's main author is chiming in the discussion of this on Fossil's forums:

(https://fossil-scm.org/forum/forumpost/50a5bea5fb)

That's appalling. Fossil's implementation doesn't require a conversion.

“This is a key point, that I want to highlight. I'm sorry that it wasn't made more clear in the LWN posting nor in the HN discussion.

“With Fossil, to begin using the new SHA3 hash algorithm, you just upgrade your fossil binary. No further actions, workflow changes, disruptions, or thought are required on the part of the user.

* “Old check-ins with SHA1 hashes continue to use their SHA1 hash names.”

* “New check-ins automatically get more secure SHA3 hash names.”

* “No repository conversions need to occur”

* “Given a hash prefix, Fossil automatically figures out whether it is dealing with a SHA1 or a SHA3 hash”

* “No human brain-cycles are wasted trying to navigate through a hash-algorithm cut-over.”

“Contrast this to Git, where a repository must be either all-SHA1 or all-SHA2. Hence, to cut-over a repository requires rebuilding the repository and in the process renaming all historical artifacts -- essentially rebasing the entire repository. The historical artifact renaming means that external links to historical check-ins (such as in tickets) are broken. And during the transition period, users have to be constantly aware of whether they are using SHA1 or SHA2 hash names. It is a big mess. It is no wonder, then, that few people have been eager to transition their repositories over to the newer SHA2 format.”

seniorsassycat4• 6 years ago

The way I read the fossil's authors comments, old commits continue to use sha1 hashes. A repository will be vulnerable to sha1 collision attacks as long as there is an object in the repository that has not been hashed with the new algorithm.

For example, floppy.c could be replaced in a repo with file with the same sha1 hash as long as the last commit that modifies floppy.c used a sha1 hash.

Right?

dariusj18• 6 years ago

So if a repo has anyone commit to it using a new binary, then anyone accessing the repo will need the new binary as well?

cm2187• 6 years ago

Stating the obvious but the hash is a hex, that leaves lots of characters for a one character prefix for sha256 hashes. Like the character "s" for instance.

pkilgore• 6 years ago

I love LWN's technical writing--its worth the cost of a subscription!

throwaway-q2233• 6 years ago

Can't just take Sha 1 of Sha 256?

loeg11• 6 years ago

Nope.

ericfrederich• 6 years ago

I'll have to update my program which generates vanity hashes. I do enjoy starting projects with an obligatory "Initial Commit" with a deadbeef SHA-1

bmn__• 6 years ago

I like to start a repo with an "empty" commit, that is to say its tree is the magic 4b825dc. https://news.ycombinator.com/item?id=18342763

I wonder if it would still be practically possible to manipulate the commit id.

loeg11• 6 years ago

Yep. You can inject arbitrary metadata into the git commit object and the git cli ignores it, other than including it in the hash. E.g., https://github.com/kevinwallace/gitbrute , https://github.com/kevinwallace/gitbrute/commit/0001111 .

wyoung215• 6 years ago

Wow! I wouldn't have guessed that Git had that vulnerability. Fossil solves it easily: creating a new repo involves generating a random project code (a nonce) which goes into the hash of the first commit, so that even two identical commit sequences won't produce identical blockchains.

Fossil lets you force the project ID on creating the repo, but the capability only exists for special purposes.

PaulHoule• 6 years ago

I am not a fan of SHA-256, you are better off with SHA-386 or SHA-256/512 which resist prefix attacks and are actually a little fast on 64 bit machines.

alkonaut2• 6 years ago

I didn't get the argument against just converting? Sure some code bases are large and spread out, but any git repo needs to have one blessed central point, and everyone needs to be able to just re-clone from the central repository whenever history is rewritten for whatever reason (could be that a huge file is trimmed from the past etc). Why can't all commits in the Kernel history be rewritten to SHA256? (Other than that it would be an annoying interruption in the development)?

corbet• 6 years ago

The kernel doesn't really have the one central blessed point of which you speak. Sure you can grab mainline releases from Linus's repository, but that's not where the development actually happens. It really is a distributed project, and having to delete all those old repositories would really hurt.

alkonaut2• 6 years ago

If 2 separate copies of the same repository does the same rewrite to sha256, their histories are still compatible and equal up to the point where they diverge. So other than that the rewrite needs to happen in more places, it should still be doable. Needs to happen at more or less the same time however.

velcrovan4• 6 years ago

The whole point of git is that there doesn't need to be a blessed central point.

RichardCA• 6 years ago

Most development shops are using the traditional client-server model, or self-host using Gitlab.

I personally would never allow a repo with two hashing algorithms to exist on my watch.

If you have ever had to use a tool like BFG to prune large objects from a repo you'll see it's not that bad, but it does require users to re-clone.

I would want to use the same process for SHA256 - that is let it be the default for new projects and then convert older projects based on need.

But there needs to be a BFG style conversion tool that spits out an object id map as output.

Here's more info on BFG: https://rtyley.github.io/bfg-repo-cleaner/

strenholme8• 6 years ago

I’m already seeing a lot of discussion both here and over at LWN about which hash algorithm to use.

The Git team made the right choice: SHA2-256 is the best choice here; it has been around for 19 years and is still secure, in the sense that there are no known attacks against it.

Both BLAKE[2/3] and SHA-3 (Keccak) have been around for 12 years and are both secure; just as BLAKE2 and BLAKE3 are faster reduced round variants of BLAKE, Keccak/SHA-3 has the official faster reduced round Kangaroo12 and Marsupilami14 variants.

BLAKE is faster when using software to perform the hash; Keccak is faster when using hardware to perform the hash. I prefer the Keccak approach because it gives us more room for improved performance once CPU makers create specialized instructions to run it, while being fast enough in software. And, yes, SHA-3 has the advantage of being the official successor to SHA-2.

jayflux• 6 years ago

BLAKE is faster when using software to perform the hash

Is BLAKE 3 still faster than sha-256 when using the cpu speciliazed instructions? I think most modern desktop CPUs has built-in instructions for SHA256.

I’m guessing when people compare BLAKE 3 to SHA 256 they’re comparing software to software, but this wouldn’t be the case in reality?

strenholme8• 6 years ago

I haven’t seen any benchmarks for BLAKE3 vs. the Intel/AMD SHA extensions. My guess is that Intel hardware accelerated SHA-256 will be faster than BLAKE3 running in software for most real world uses.

I can tell you this much: It is only with Ice Lake, which was released in the last year, that mainstream Intel chips finally got native hi speed SHA-NI support. Coffee Lake and Comet Lake, which are still the CPUs in a lot of new laptops being sold right now, do not support SHA-NI.

vluft• 6 years ago

On my machine with sha extensions, blake3 is about 15% faster (single threaded in both cases) than sha256.

_verandaguy2• 6 years ago

Honest question: what are the use cases in Git where hash computation speed is a meaningful optimization?

papreclip• 6 years ago

less wasted computation means less global warming

strenholme8• 6 years ago

It’s actually not a big deal with Git, which is why SHA2-256 is the right choice.

loeg11• 6 years ago

Rewriting all repos from SHA1 to hash-next?

SQLite4• 6 years ago

My experience in developing and maintaining Fossil is that the hashing speed is not a factor, unless you are checking in huge JPEGs or MP3s or something. And even then, the relative performance of the various hash algorithms is not enough to worry about.

KMag• 6 years ago

SHA-256 is probably the right choice, but I don't think it's as obvious as you suggest, given SHA-512/256.

SHA-512/256 is a standard peer-reviewed and well-studied way to run SHA-512 with a different initial state and then truncate output to 256 bits.

This is heavy bikeshedding, but SHA-512/256 would be a more conservative choice than SHA-256. Under standard assumptions, SHA-256 is no weaker than SHA-512. The structure is extremely similar to SHA-256, but a collision on intermediate state requires a collision on all 512 bits of state instead of 256.

On most 64-bit CPUs without dedicated hash instructions, SHA-512/256 is faster for messages longer than a couple of blocks, due to processing blocks twice as large in fewer than twice as many operations.

Currently, the latest server and laptop CPUs have SHA-256 hardware acceleration but not SHA-512 acceleration. I'm not sure how many phone CPUs support sha256 but not ARMv8.2-SHA extensions (SHA-512). If it weren't for this difference in hardware acceleration, there would be few reasons to use SHA-256.

That being said, the current difference in hardware acceleration support probably makes SHA-256 the right choice here.

strenholme8• 6 years ago

SHA-512/256 is a lot newer than SHA2-256 (usually called SHA-256, but I prefer the SHA2 prefix to make it clear that it’s a very different beast than SHA3-256), and its speed on 32-bit CPUs is less than optimal, so I don’t see it as being a more conservative choice. In terms of security, it uses the same 19-year-old unbroken algorithm as SHA2-256.

I am aware of the length extension issues, but they are not relevant for Git’s use case.

In terms of support, SHA-512/256 has, as you mentioned, less hardware acceleration support, and it’s also not supported in a lot of mainstream programs like GNU Coreutils. I also know that some companies mandate using SHA2-256 whenever a cryptographic hash is needed.

Git made the right choice with SHA2-256: It’s the most widely supported secure cryptographic hash out there.

zackmorris• 6 years ago

Summary of hashing function security in bits, for convenience:

https://en.wikipedia.org/wiki/Secure_Hash_Algorithms

Since collision resistance is roughly half the number of bits, it seems unconscionable to me that anything below 256 bit hashes even exist, because 64 bits is crackable but 128 bits effectively never will be. This was well-understood even in the 90s when MD5 and SHA were first published.

Just thinking about this for the first time, I don't buy any argument about storage or performance, since those become less important as time goes on. It feels like Linus made a mistake here, and offloaded the inevitable work of upgrading repositories onto the general public (socialized the cost) which is something that all programmers should work harder to avoid.

Said as an armchair warrior who has never accomplished anything of any importance, I realize.

mathnmusic• 6 years ago

Also relevant: Multihash is a format for self-describing hashes that helps with data portability and future-proofing: https://github.com/multiformats/multihash

kazinator11• 6 years ago

There is, of course, a way to unambiguously give a hash value in the new Git code, and they can even be mixed on the command line; this example comes from the transition document:

     git --output-format=sha1 log abac87a^{sha1}..f787cac^{sha256}

> For a Git user interface this is relatively straightforward and concise

No, it isn't. It's a complete and utter user interface clusterfuck. Just say no to this insanity.

microtherion2• 6 years ago

Note the qualifier "for a Git user interface".

The average git command is along the lines of "git ph-nglui --mglw=nafh Cthulhu...R'lyeh -- wgah^nagl fhtagn"

kazinator11• 6 years ago

That cute rhetoric will not fool anyone. Common git workflows use fairly succinct git commands:

  git diff
  git commit -p
  git rebase -i HEAD~3

The command quoted in my original comment is just this we strip away the SHA256 garbage:

  git log abac87a..f787cac

(Or maybe it is:

  git log abac87a^..f787cac^

I cannot guess whether the ^ operator still has the same meaning or whether it is part of this ^{sha...} notation.)

The hashes will typically be copy and pasted, so you type just the git log, .. and spaces.

The fixed parts of convoluted git syntax can be hidden behind shell functions and aliases. But notations for referencing objects are not fixed; they will end up as arguments.

scarejunba• 6 years ago

Perhaps suggest an alternative? It may help understand why this was chosen.

loeg11• 6 years ago

One alternative would be to just do lookups in both hash databases (until SHA1 is fully migrated away from), and reject invocations that conflict. Git's CLI already rejects ambiguous short hash prefixes for SHA1, it could easily reject ambiguous prefixes between SHA1 and SHA256 and otherwise allow unique prefixes for either hash. This would be pretty ergonomic for users.

kazinator11• 6 years ago

One attractive alternative is not to do a thing.

Don't cave in to sky-is-falling bullshit regarding the existing SHA1.

Git is not a crypto system; it's just version control.

We've used version control systems just fine that had no integrity features at all. For isntance you can go into a RCS ,v file and diddle anything you want. Some BSD people are still on CVS, and their world hasn't fallen apart.

gouggoug• 6 years ago

For a Git user interface this is relatively straightforward and concise

You forgot to include the end of that sentence, that acknowledges your issue with it:

, but one can still imagine that users might tire of it relatively quickly.

hinkley3• 6 years ago

I've had this argument at work.

"Tire of it quickly" and "have an immediate gag reflex" are two completely different categories of negative reaction.

It's hard to see the sunset when you're down in the muck, and eventually 'less bad' starts to look like progress to you. It's a trap and you should be aware of it.

hinkley3• 6 years ago

When people started using the phrase "Stockholm Syndrome" with respect to git I took it as a sort of hyperbole. A rhetorical device.

But the more 'improvements' they make to it the more literal that accusation becomes in my head. And what's worse is that I've grown enough callouses now that my response is an eyeroll instead of pain. I use git all the time, but it's terrible and I need something that is better, not just sucks less. And apparently soon, because I don't know when that koolaid is going to start looking good but it's not long now.

Send help.

kazinator11• 6 years ago

I'm completely against this security theater nonsense; please keep my git SHA-1.

Please fork git for this and call it something else, like git6, and ensure that git6 cannot push to git repos.

speedgoose• 6 years ago

…a simple command like:
git convert-repo --to-hash=sha-256 --frobnicate-blobs --climb-subtrees --liability-waiver=none --use-shovels --carbon-offsets

Is it sarcasm ?

andrewflnr• 6 years ago

Yes.

sunil_saini• 6 years ago

The above article suggests that Sha-1 collision is infeasible because attacker has to come up with code that not only generate same hash but also benefit him. But can't he just add some malicious code and add some random text in comments to produce same hash?

pornel• 6 years ago

"produce same (specific) hash" is a pre-image attack, which is very very hard. So hard, that even MD5 isn't broken for pre-image, and there's only a theoretical pre-image attack against MD4.

We know only collision attacks which is "produce 2 files with the same hash, but you can't control what hash". So you can't target any existing repo. You need to use social engineering to get one of your special files into a repo.

zokier• 6 years ago

Does anyone know if a standard format for sort of tagged-union hash type, something similar as crypt format for passwords? Feels like everyone is needing to support multiple hash types at some point, and basically needs to reinvent that particular wheel again and again.

loeg11• 6 years ago

It isn't too bad to just exhaustively look up provided hashes in all your databases (at least, for Git). You should probably only support 1 primary hash at a time, and 1 additional legacy hash for migration purposes. This makes lookup twice as expensive; for git, this is not usually the slow part (the slow part is 'git status' having to compare the entire local filesystem checkout to the repo).

themaxdavitt• 6 years ago

Multihash? https://multiformats.io/multihash/

nsajko2• 6 years ago

Disappointed they went with an ARX based hash, instead of KangarooTwelve, which uses the Keccak permutation. A lot of people on this thread think that SHA2 is more secure because it is older, but it is my understanding that that is completely wrong. Keccak is not only standardized, to get to that it had to win the SHA3 competition, during and after which it received, as far as I understand, unprecedented levels of scrutiny. And not only that, but, according to what I read, the Keccak-like cryptographic constructions (including the hash) are much more amenable to mathematical/cryptographical analysis because of not using addition (word-wise, instead of bit-wise, to be more correct). The idea is that a resourceful/moneyed attacker (like the NSA or China, etc.) could create successful attacks on an ARX hash without the public being able to come to the same developments because of no researchers having access to similar levels of resources.

The sad thing is that the ARX BLAKEx functions seem to be gaining undeserved amounts of hype. I do not think they are getting comparable scrutiny from researchers, seeing as BLAKEx hashes are ARX, and also changed considerably since the SHA3 contest (so it is far from clear that the scrutiny that BLAKE did receive translates to BLAKE2 or BLAKE3).

nsajko2• 6 years ago

One thing that should also be noted is that ARX hashes are relatively less well suited to silicon implementations.

The Keccak team published a short and poignant relevant blog post back in 2017 as an answer to that notorious "Maybe skip SHA3" blog post: https://keccak.team/2017/not_arx.html

A HN commenter from 2017 explained ARX's safety downside better than I: https://news.ycombinator.com/item?id=15292103

The nuance that's being made here is that the public cryptanalytic results we have are from researchers that need to publish. However blackhats (be it government or private) have no such need. Thus, they do not care if the analysis is elegant or neat.
This means that ARX functions will have less published analysis, but may still be successfully attacked.
This isn't even a new argument they're making here. It's been well understood that simple cipher designs are better, because they are easier to understand. If you can understand it well, yet not break it, that gives confidence. If you don't understand it, it might break as soon as you do.

cestith• 6 years ago

I just want to add something the article couldn't cover. I know bmc and he's both a software geek's software geek and one of the friendliest, most helpful, and most genuine people I've ever met.

lokedhs• 6 years ago

How will rehashing work for commits that are signed? Do all the commits need to be re-signed?

A new hash algorithm for Git

Related Stories