SHA-1 'fully and practically broken' by new collision (2020)

https://duo.com/decipher/sha-1-fully-and-practically-broken-by-new-collision

by ofou • 5 years ago

279 196 5 years ago

rgovostes• 5 years ago

(Jan 7, 2020)

ImJasonH2• 5 years ago

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild.

https://github.blog/2017-03-20-sha-1-collision-detection-on-...

api3• 5 years ago

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository would be indistinguishable if you're only using git hashes.

Git's uses SHA-1 for unique identifiers, which is technically okay as long as they are not considered secure. If git were designed today it would probably use SHA2 or SHA3 but it's probably not going to change due to the massive install base.

Edit: anyone know if git's PGP signing feature creates a larger hash of the data in the repo? If not maybe git should add a feature where signing is done after the computation of a larger hash such as SHA-512 over all commits since the previous signature.

throw_away• 5 years ago

Looks like there's a migration plan for git to SHA-256:

https://git-scm.com/docs/hash-function-transition/

a_t48• 5 years ago

As far as I know it only signs individual commits.

ImJasonH2• 5 years ago

Yep. GitHub is saying they would block an object that looked like it was crafted to produce a collision using SHAttered, and hasn't seen it, intentionally or otherwise, in the wild.

AnimalMuppet2• 5 years ago

Can you create an intentional collision, and also have the counterfeit have compilable code? (Or, in other circumstances, intelligible English text?)

jfrunyon2• 5 years ago

https://stackoverflow.com/questions/23584990/what-data-is-be... says git signing just signs the commit hash (plus metadata: committer, commit message, etc).

oconnore• 5 years ago

I was surprise that no one suggested truncating SHA-256 to 160 bits (same as for SHA2-256/224, or SHA2-512/256). The attacks on SHA-1 are not directly based on the length of the hash, they are based on weaknesses in the algorithm.

Even attacking SHA2-256/128 would be quite difficult as I understand it, even though it's the same length as MD5.

Truncated hashes also of course have the great property that they mitigate the length extension in Merkle-Damgard

adrian_b2• 5 years ago

It is not yet possible "to create a git commit that has the exact same hash as another git commit" in the sense that if someone else has already done a commit you can make another commit with the same hash.

What is possible now is something that is much easier: if you have enough money and time, you can create 2 commits with the same hash, which start with some different parts, which may be chosen arbitrarily, then they have to include some parts that must be computed to ensure that the hashes will match and which will be gibberish that might be disguised in some constants or some binary blob, if possible.

Then you can commit one of them and presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution.

outworlder2• 5 years ago

This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software.

You need a collision. You also need it to be syntactically correct. You need it to not raise any red flags if you are contributing a patch. And ultimately you need it to do what you want.

That's a pretty tall order.

asdfman1234• 5 years ago

Random collisions in 160-bit space are incredibly unlikely

Just for fun: to get a 5% chance of a hash collision between ANY two numbers in an 160 bit space, you'd have to generate 3.9e23 hashes.

So you'd have to generate 1000 hashes per second for *12 trillion years.*

Formula:

n = sqrt(2 * 2^160 * ln(1/(1-0.05))

https://en.wikipedia.org/wiki/Birthday_problem#Probability_o...

noway4214• 5 years ago

From a practical point of view, how would injecting malware happen? If you're trying to insert a malicious diff somewhere deep in the git history, you would need to recompute all the other commits after the injected commit - which would most certainly change their commit ids too if they are touching the same file. When other commit ids change, the malicious change becomes detectable.

There's also the case for auditing: force pushing into an existing repo triggers an event in GitHub and is logged. While the logging event can be missed, it leaves a paper trail.

With things like reproduce-able builds, this also becomes harder. Distributing (through a means of a fork, or putting it up on a website mytotallylegitgitrepos.com) source code which builds into a binary which doesn't match upstream hash is suspicious.

tialaramex• 5 years ago

The defence used by GitHub specifically defends against these intentional collisions, not some mirage of random collisions.

Basically you collide a hash like SHA-1 or MD5 by getting it into a state where transitions don't twiddle as many bits, and then smashing the remaining bits by brute force trial. But, such states are weird so from inside the hash algorithm you can notice "Huh, this is that weird state I care about" and flag that at a cost of making the algorithm a little slower. The tweaked SHA1 code is publicly available.

If you're thinking "Oh! I should rip out our safe SHA256 code and use this unsafe but then retro-actively safer SHA1" No. Don't do that. SHA-256 is safer and faster. This is an emergency patch for people for whom apparently 20 years notice wasn't enough warning.

In theory the known way to do this isn't the only way, but, we have re-assuring evidence for MD5 that independent forces (probably the NSA) who have every reason to choose a different way to attack the hash to avoid detection do trigger the same weird states even though they're spending the eye-watering sum of money to break hashes themselves not just copy-pasting a result from a published paper.

stevekemp• 5 years ago

If git were designed today it would probably use SHA2 or SHA3 but it's probably not going to change due to the massive install base.

There is some work going on to change this, but it's not an easy task:

https://lwn.net/Articles/811068/

tantalor2• 5 years ago

A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

- Scott Chacon

asdfman1234• 5 years ago

That's even true if you make your developers commute into Yellowstone National Park by ski every day

bawolff2• 5 years ago

This is stupid. The probability of any attack happening at random is close to zero. E.g. the probability of a buffer overflowing just right to give you a shell through random chance is less than being eaten by wolves.

The question is about the risk of someone intentionally performing the attack, not the probability it will accidentally happen at random.

kragen8• 5 years ago

This turns out to be wrong; for a 6-member programming team, that probability is about 2⁻²⁴⁵, which is about 2⁸⁵·³ times less likely than an accidental 160-bit SHA-1 collision: http://canonical.org/~kragen/sw/dev3/rpn-edit#3_8_0_1_0_0_0_...

Aside from being bullshit, it's also irrelevant, since we're discussing a collision being generated on purpose, not by accident.

lifthrasiir• 5 years ago

The chosen-prefix collision with a complexity of 2^63.4 (2020).

akomtu3• 5 years ago

Looks like they needed 1.5 millions GPU hours to find a collision with a random hash.

smegcicle• 5 years ago

thats it, it's over, git is finished

r0f1• 5 years ago

Obligatory link: https://shattered.io/

TravisHusky• 5 years ago

Of course it has its own website ;)

nikeee• 5 years ago

The article states that the collision found is something different than that one found by Google et al.

It's a chosen-prefix attack.

fanf2• 5 years ago

That was an earlier break; this article is about https://sha-mbles.github.io/

bjarneh• 5 years ago

The technique that the researchers developed is quite complex and required two months of computations on 900 individual GPUs.

motohagiography3• 5 years ago

I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.

fwip4• 5 years ago

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size).

You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

FartyMcFarter• 5 years ago

Compression algorithms must encode data in a reversible way, which hash functions can't do in general.

For example, SHA-1 outputs a 160 bit hash, which means some input of 161 or more bits will definitely have the same hash as some other input of the same size. Even smaller inputs may have collisions too.

tomsmeding• 5 years ago

These hashes, regardless of their actual cryptographic strength, are intended to be indistinguishable from a random generator keyed with the input, kind of. Assuming that they succeed in that, hashes should be quite well distributed. That means that that for each hash n-bit hash output, there will be about two (n+1)-bit input strings that produce that hash, about four (n+2)-bit input strings, eight (n+3)-bit input strings, etc. So while there are probably few ASCII input strings that map to one particular hash, for example, there will be loads and loads of arbitrary bitstrings that map to that hash.

Hashes are very bad compressors. :)

kazinator• 5 years ago

The compression joke evokes a misconception (as STEM jokes often do) which, in this case, is that breaking a hash means finding a way to recover the full text of a multi-megabyte document, from a 100-something byte hash.

Whereas all it means is that it's become feasible for someone to produce a fake document with the same hash as the genuine one; the attack depends on the existence of collisions, which depend on the hash being one-way, such that an infinite set of documents could be "recovered" from the hash.

Most of the documents you could "decompress" from a hash are going to be gibberish, but some of them are going to be legit. If a hash is "broken", that means it's somehow unduly easy to search that ocean of gibberish collisions to find a chosen text which goes to a certain desired hash.

Nothing quantum can redefine a function that isn't one-to-one and onto into one that is. The hashing function remains ever the mathematical object that it is: a one-way function. But calculations of or searches through that function can be faster.

In a post-quantum world, pre-quantum crypto and hashing could well turn out to be "for shit" as such, but not due to ruses like suddenly reversing irreversible functions.

Not saying that the joke isn't funny! We can imagine some hard-core computer science or math sitcom in which the fall characters say things like this, and only the very narrow target audience gets it.

asdfman1234• 5 years ago

I wonder how much money in Bitcoin they would have made if they had used those hashes to mine instead.

Speaking of which, it would be funny if they were pretending to do security research but added a secret backdoor to mine bitcoin instead, somehow exporting those hashes or using the partial results of SHA-1 calculations (BTC isn't SHA-1).

I'm just joking, but I wonder if that's possible. If anyone is Machiavellian enough for that, it's security researchers.

fsckboy• 5 years ago

mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.

garmaine5• 5 years ago

Well, they made 2.4994722 BTC directly by exploiting a smart contract on bitcoin that pays out to anyone demonstrating a SHA-1 collision.

lallysingh2• 5 years ago

Or roughly 1.3M GPU hours. Less as GPUs get upgraded. Not sure how many AWS F1 (FPGA) hours it would take.

wongarsu2• 5 years ago

So somewhere between $300,000 (running consumer GPUs cheaply) and $30 million (paying AWS on-demand prices for Tesla V100).

Even the upper bound for that seems well worth it for well-funded attackers if the target is juicy enough.

cletus2• 5 years ago

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it.

I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)?

It just seems like such a massive and foreseeable oversight that's going to cause pain for some time to come for really no reason at all.

alerighi• 5 years ago

SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine.

Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the reasons git was created was speed for large project like the Linux kernel) for no real purpose. If you want to change the algorithm, given that you will break compatibility with all existing repositories, tools, and clients, you make a fork of git because you are changing too much.

I don't see why migrating to SHA-256. The collisions are still very unlikely to generate accidentally, and sure, if you want to do damage to a repository you can create one on purpose, as you can as well commit some hooks that contains malware, or alter the git history in any way you want, so what's the point?

nybble41• 5 years ago

It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does.

Git effectively uses its hashes as a component of a digital signature scheme, in the form of signed tags and signed commits. The GPG signature covers the commit object, which identifies the content (tree) by its hash.

madars2• 5 years ago

Collisions definitely do matter for git security: many people pin explicit git hashes for their dependancies, and thus they can be tricked in running malicious forks. This requires placing a chosen commit in the git repo (so unlike second preimage break it does not mean that you could attack repos you have no control over) but that's not an unrealistic threat model overall.

cogman10• 5 years ago

And, to that point, I'm not really convinced that a cryptographic hashing algorithm is really a great choice for git.

It is nice that it checks off the boxes for even distribution of hashes, but there's a bunch of other hashing algorithms that can do that without the performance penalty inherent in crypto hashes. For example, FNV seems like a good fit for something like git.

simias3• 5 years ago

Honestly I find these rationalizations around the use of SHA-1 annoying and counter-productive. The rule is simple: don't use SHA-1. If you already use SHA-1 migrate away from it. You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique. Is it a security risk? Maybe, maybe not. I don't care to find out.

It doesn't matter until it starts mattering. If the Git devs had done the right thing over a decade ago we wouldn't be having this discussion. The longer they wait the more painful the migration will be.

SHA-2 was published in 2001, git was released in 2005 and now we're in 2021 and we're having this discussion again. The first concrete attack was released in "early 2005" according to wikipedia, so there's really no excuse.

Just do it, make a major change where you replace SHA-1 with SHA-256 and call it a day. It's going to be painful for a few months and then we'll move on.

For me these discussions demonstrate the immaturity of software engineering. In other industries regulators would've banned the use of SHA-1 and you couldn't get certified if you used it.

Do electronic engineers regularly try to argue "well ok RoHS says we can't have lead solder in this product but frankly for this one it's fine the casing is completely waterproof and there are no risks for the customer"? No, they don't. If the spec says no lead, then either it's no lead or you can't sell your product. End of story.

SHA-1 is the lead solder of software engineering. Only acceptable for military use.

lvh6• 5 years ago

SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine.

This suggests git does not rely on its hash for security properties, which seems false? What is the purpose of pinning revisions or signing git tags?

cletus2• 5 years ago

SHA-1 will still work fine for the purpose of git.

So why are they changing it? That's pretty strong evidence it's not fine. I found this Stackoverflow question, "Why does Git use a cryptographic hash function?" [1], which points to [2]. Note: pretty much every DVCS uses a cryptographic hash function. That doesn't seem like an accident.

Reading through some of these old posts and threads it seems like performance was the main factor combined with the expectation that SHA1 collisions just wouldn't be an issue. The latter I find to be surprisingly naive.

[1] https://stackoverflow.com/questions/28792784/why-does-git-us...

[2] https://ericsink.com/vcbe/html/cryptographic_hashes.html

urda• 5 years ago

SHA-1 will still work fine for the purpose of git.

So why are so many corporations, individuals, and orgs working hard to protect against it?

Hint: because it's not actually fine.

elfchief• 5 years ago

Git was not intended (AFAIK) to be cryptographically secure. Being unsuitable for crypto != being unsuitable for other uses.

wcoenen• 5 years ago

Surely signed tags and signed commits in git are supposed to be cryptographically secure? [0]

Doesn't the security of those signatures depend on the security of the SHA-1 hashes that are being signed?

[0] https://git-scm.com/book/en/v2/Git-Tools-Signing-Your-Work

formerly_proven2• 5 years ago

Git is designed around content-addressed storage and while you can cater for hash migrations, it gets pretty messy design-wise. Gits core data structures were also designed really quickly to patch a very urgent need of the kernel hackers. I doubt it has anything to do with being in love passing 20 byte strings on the stack. The fine git folks have produced a rather detailed document about the hash migration (https://git-scm.com/docs/hash-function-transition/) and it is not particularly simple to do this.

tantalor2• 5 years ago

going to cause pain

What kind of attack on a git repo are you worried about?

snovv_crash• 5 years ago

Subrepo hash substitution could enable a supply-chain attack

umvi2• 5 years ago

"We note that classical collisions and chosen-prefix collisions do not threaten all usages of SHA-1."

ori_b2• 5 years ago

For someone to be able to break your repo using sha1 collisions, they need to be able to commit to it.

If you don't trust someone, don't let them commit to your repo.

Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)?

The hashes show up everywhere. They're how every object in git is identified. They make it onto disk. They're not just commit ids.

Changing hashes changes the disk format.

lamontcg2• 5 years ago

Yeah I don't think any of these proposed attacks work without write access to the repo, at which point the game is already pretty much over already.

kragen8• 5 years ago

They might not need to commit to your repo to break it using SHA-1 collisions.

They might, for example, compute a collision, commit the malicious version to a private GitHub repository, and then send you a patch with the non-malicious version via email, or by sending you a merge request on GitLab. When you accept and merge in their changes and then push to GitHub, perhaps GitHub will recognize the hash of one of your blobs as a hash that it already knows the blob for (from the private commit), and so it will ignore whatever data you send it for that blob.

Maybe that particular scenario won't work — I haven't tried it — but there are hundreds of possible angles of attack. Fundamentally the security of Git is based on the idea that hashes don't collide.

dec0dedab0de• 5 years ago

Linus posted about it on google plus in 2017. I haven't re-read it yet, but I remember one of the ideas floating around hn at the time was to just have two hashes per commit. That is, two insecure hashes may be secure together for git's purposes. Even though we can generate collisions for md5, and sha1, it would be much more difficult to have a file generate an arbitrary collision for both at the same time.

Here is a link to Linus's post on the internet archive

https://web.archive.org/web/20170717192607/https://plus.goog...

And here are some hn posts around the same time

https://news.ycombinator.com/item?id=13733481

https://news.ycombinator.com/item?id=13719368

bawolff2• 5 years ago

That is, two insecure hashes may be secure together for git's purposes.

Generally that's not true for Merkle–Damgård (e.g. sha1, sha2) hashes - afaik the difficulty of finding a collision in the more difficult hash is the same (up to big-oh) as finding it in both hashes.

zzo38computer4• 5 years ago

In git I don't know, but in fossil, it already does that if the file that the collision is generated for is not the manifest file. The manifest file and all other files are identified by the SHA-1 hash (in newer versions SHA3-256 is also supported), although the manifest file also has a R card which is the MD5 hash of the all of the other files. This means that if there is a collision, it will be detected and the file would be rejected.

renewiltord• 5 years ago

It is a law of nature that all successful products find themselves not accounting for some predictable problems.

ploxiln• 5 years ago

I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why.

The first basically functional version of Git was created in less than a month by Linus Torvalds, immediately after Bitkeeper revoked the license/permission for linux kernel developers to use that proprietary source control tool for free. Linus took a look at Monotone and Mercurial IIRC, but they were not nearly fast enough at that time, so he created Git to just do what the linux kernel development community needed.

This isn't the first time Linus did something that academics said was a terrible mistake, and then his creation took over the freaking world, because it works so freaking well. (And it still does today, 16 years later. Maybe tomorrow it won't, I dunno. But it probably will.)

ezst• 5 years ago

Linus took a look at Monotone and Mercurial IIRC, but they were not nearly fast enough at that time

That's incorrect for Mercurial, it was started by another kernel developer (Matt Mackall) at the same time, for the same reasons (but they ended-up with different trade-offs, which makes mercurial still very interesting and relevant in a post-github world).

throwaway984393• 5 years ago

I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one.

The name literally means stupid person.

oshiar53-0• 5 years ago

FYI signed git commits and tags weren't a thing back then.

john_alan• 5 years ago

Our work show that SHA-1 is now fully and practically broken for use in digital signatures

Yet 2nd preimage resistance is intact. Zzz.

ofou2• 5 years ago

For the ones interested, you can use SHA-256 today. Warning: Still in experimental mode.

    # .gitconfig file
    [extensions]
        objectFormat = sha256

garmaine5• 5 years ago

Does GitHub support this?

ofou2• 5 years ago

Not yet [1]. "However, conversations around its implementation are ongoing and looks like it will be on the horizon."

[1] https://github.community/t/support-for-sha-256-hashes/157493...

dang• 5 years ago

Some past threads:

SHA-1 collisions now cost $45k [pdf] - https://news.ycombinator.com/item?id=23350223 - May 2020 (62 comments)

The first chosen-prefix collision for SHA-1 - https://news.ycombinator.com/item?id=21979333 - Jan 2020 (352 comments)

Abusing SHA-1 collisions for Chromium updates - https://news.ycombinator.com/item?id=20114809 - June 2019 (36 comments)

A SHA-1 chosen-prefix collision attack - https://news.ycombinator.com/item?id=19907127 - May 2019 (71 comments)

From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 [pdf] - https://news.ycombinator.com/item?id=19878917 - May 2019 (18 comments)

SHA-1 Collision Detection on GitHub.com - https://news.ycombinator.com/item?id=13917990 - March 2017 (90 comments)

Linus' reply on Git and SHA-1 collision - https://news.ycombinator.com/item?id=13719368 - Feb 2017 (262 comments)

When Will We See Collisions for SHA-1? (2012) - https://news.ycombinator.com/item?id=13719079 - Feb 2017 (1 comment)

Announcing the first SHA-1 collision - https://news.ycombinator.com/item?id=13713480 - Feb 2017 (485 comments)

How would Git handle a SHA-1 collision on a blob? - https://news.ycombinator.com/item?id=13547348 - Feb 2017 (5 comments)

Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision - https://news.ycombinator.com/item?id=10778773 - Dec 2015 (43 comments)

The Cost of Creating Collisions Using SHA-1 - https://news.ycombinator.com/item?id=8629906 - Nov 2014 (9 comments)

When Will We See Collisions for SHA-1? - https://news.ycombinator.com/item?id=4618069 - Oct 2012 (51 comments)

musicale2• 5 years ago

Old collision (2020). ;-)

1ncorrect• 5 years ago

I’ve wondered for a while if it is viable to use multiple hashes, or nested hashes, to mitigate these vulnerabilities, for example:

message+hash1(message)+hash2(message) message+hash1(hash1(message))

To my lay understanding, it would provide multiple chained validation steps, but I’m curious if there are any obvious flaws with this model.

jiggawatts• 5 years ago

This a common lay-person approach to "strengthening" cryptography, but is not as effective as using a better algorithm instead.

For example, SHA256 and SHA512 require approximately the same number of "cycles per byte" when using modern CPU instruction sets. So 2× SHA256 is 2× slower than 1× SHA512. On some processor models, 1× SHA512 is faster than 1× SHA256!

Of course, things aren't always this simple, but you get the idea.

Similarly, for some class of attacks, it's only 2× as much work to crack 2× SHA256 as it would take to crack 1×SHA256. However, for these attacks it is (2^256)× more work to crack SHA512, which takes the difficulty increase from "slightly more" to "absolutely impossible in this physical universe".

garmaine5• 5 years ago

If the hash function does its job at mixing input, this is no different than applying just the final hash.

(With the technical caveat that doing at least two serial hashes does improve the properties of the hash function by defending against length extension attacks. That's why things like HMAC do multiple chained hashes. But it does zilch for collision or preimage resistance.

simpleguitar• 5 years ago

I have a question.

Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash?

It seems all the modern, secure ones are 256 bits or larger. Is that because 160 bits is too easy to compute collisions for any algorithm, or are we just not able to fully realize the entropy that can be recorded into 160 (or even 128) bits?

garmaine5• 5 years ago

Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash?

No, it is provably not possible to do that. A N-bit hash function has maximum N/2-bits of collision resistance. So a 128-bit hash function (like MD5) has a maximum of 2^64 bits of security against a classical attacker, even if it wasn't broken in other ways (as MD5 is). A 160-bit hash function like SHA-1 would have 2^80 bits of security against collision attacks on a classical computer.

Both MD5 and SHA-1 are broken in other ways, but you could for example use SHA-2 or SHA-3 in truncated mode if you wanted a "secure" 128-bit or 160-bit hash output. Indeed there are standard operating modes for doing so, meant for when you need a drop-in replacement for MD5 or SHA-1.

But fundamentally, 64-bit or 80-bit security is too low for any except some highly specified use cases. And even then the extra bits of a stronger hash will rarely kill you, so why bother? Just use SHA-2 or SHA-3 and not worry about it.

In cases where you can demonstrate that you only care about preimage resistance and not collision resistance, then a 128-bit hash would be sufficient. However often collision attacks crop in in unexpected places or when your protocol is used in ways you didn't design for. Better to just double the hash size and not worry about it.

zzo38computer4• 5 years ago

Fortunately, Fossil can now use SHA3-256 as well as SHA-1 (even in the same repository if necessary, perhaps due to upgrading an older repository), and I think it also has a hard mode to detect if SHA-1 collisions seem likely.

(I think git doesn't allow a repository to have multiple kind of hashes; from what I understand, only a single algorithm must be used.)

Since SHA-1 and SHA3-256 have different hash length, you can tell which one it is. It doesn't work so well if the length is the same; one way to fix it would be use a multicodec prefix. (My own implementation (currently incomplete) internally uses the multicodec numbers to identify the hash algorithms, but these multicodec numbers are never stored in the repository; instead, it is only applicable for the argument for the function to compute the hash, which can also be used in other programs.)

b3n• 5 years ago

Unfortunately Fossil uses a fast SHA hash for the password hashes of user accounts in the database, rather than a key derivation function, which is disappointing.

tashbarg• 5 years ago

My fossil knowledge might be a fossil itself, but isn’t the database used for everything?

If someone gets hold of the hashes, they already have everything. So, whats the threat that is enabled by poor pw hashing?

Anyways, passwords should always be hashed with good password hashing functions (not all kdf are good for that) even if it is not strictly necessary. Just in case.

zzo38computer4• 5 years ago

My idea is a different hash construction, which is 2D construction, which has a infinite internal state and infinite output length. Each row and each column also has a sequence number input, and then there are two mixing up functions (each of which has a finite input and output of equal size than the input); part of the result is propagated horizontally and part of it vertically, so each cell has two inputs and the input includes both the message block and the sequence number, which overwrites a part of the internal state (the rest of which has been mixed with the other state). Each output block (the output blocks are vertical and the message blocks are horizontal, which is why it is slow) is then truncated and concatenated to produce the final output, after adding padding at the end of the message (including the length of the message) to mix it up even more. If the message length is m and the hash length is h, then it requires O(h) space and O(mh) time. If ChaCha20 is in use, then it is easy to see (by the kind of calculations made by ChaCha20) that if the input is zero then the output will also be zero; therefore, the initial sequence number should be 1 and not 0. You can also compute a secondary hash which must be misaligned with the first one, so that in case a collision is found in one block that the collision will not be propagated with the other blocks too (unless a collision can be found within two consecutive blocks, in which case you would hope that the extra dimension (since it is a 2D construction) can avoid the collision).

brirec• 5 years ago

Reading your post I’m sure you know far more about information theory than I do, so forgive me if this is a stupid question, but…

1. How is infinite internal state and output size possible? There has to be some actual limit for internal state, at least, right? Or else you’ll just run out of memory?

2. Wouldn’t a larger output size risk leaking data? The chance of collision becomes lower, but it also seems to toy with what I understand about why we use cryptographic hashes without ridiculous output size.

3A. What happens if you want a 1 MB hash of a 1 KB file?

3B. How predictable does a super long hash become?

At what point is it no longer a one-way hash?

zzo38computer4• 5 years ago

1. Because you will probably be truncating the output to a short finite hash, and because each block of internal state only leads in one direction (it affects all later ("up") blocks of internal state for all later ("right") message blocks, but not previous ("left" and "down")), you can optimize it by only implementing the part that you need. So, yes, an actual implementation will be limited, but if you have enough memory and enough time then the limit can be as high as you want to be. (Maybe a diagram might explain it better; I am not sure that this explanation is any good.) (SHAKE also has infinite output (but finite internal state), and when using SHAKE also you would truncate the output to a finite size.)

2. A larger output size might risk leaking data, although I would think it would be difficult.

3A. Like I described, it then needs O(1MB) space and O(1GB) time, so it will be slow. However, I do not expect you should need a hash that long.

3B. I don't know; probably about as predictable as any random number generator, if the hash is designed correctly. (I only describe a construction, and the hash algorithm design involves more than that.)

SHA-1 'fully and practically broken' by new collision (2020)

Related Stories