Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

duo.com

Post reply on HN
Print view View original

151–160 of 210 posts

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

#151

Post by sirclueless »

noway421 wrote: post #64
y4mi wrote: post #60

Earlier quoted context omitted.

What is the thread model though? I don't think it's possible to create a collision that's also executeable code which adds a security hole or anything. So what exactly would they achieve with the collision? And how do they push these gigantic files that have the hash collisions to a server? The upload time would be significant.

The possible attack is to prepare 2 versions of a commit, both resulting in the same commit id. Then later on, after the project is successful/etc, swap out the commit with the second version, while keeping the other commits intact. Granted, the file that the commit touches would need to be not touched in other commits. That's not out of question in a typical software project - maybe a file in the utils folder which…

> Granted, the file that the commit touches would need to be not touched in other commits.

That's not how git works. The commit contains the entire tree. You could prepare two separate repositories such that `git checkout deadbeef0001deadbeef` in one checks out the linux kernel and in the other checks out ILOVEYOU.exe.

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

#152

Post by zzo38computer »

dec0dedab0de wrote: post #65
cletus wrote: post #25

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 abo…

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…

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.

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

#153

Post by ploxiln »

cletus wrote: post #25

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 abo…

> 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.)

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

#154

Post by garmaine »

simpleguitar wrote: post #134

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?

> 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.

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

#155

Post by zzo38computer »

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.)

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

#156

Post by rezonant »

CobrastanJorji wrote: post #137
kragen wrote: post #123

Earlier quoted context omitted.

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.

Just to nitpick, I don't think that formula is valid. We're primarily interested in "unrelated" wolf attacks, but it counts the total fatalities, not the total number of fatal incidents. If we count each fatal attack as only one incident, regardless of the casualties, we get 2^-258 instead. But of course we also need to take into account where the 6-member team lives. If they all live in West Bengal, India, the consi…

i laughed so hard i cried, thank you for this

(to everyone involved)

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

#157

Post by zzo38computer »

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).

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

#158

Post by noway421 »

sirclueless wrote: post #151
noway421 wrote: post #64

Earlier quoted context omitted.

The possible attack is to prepare 2 versions of a commit, both resulting in the same commit id. Then later on, after the project is successful/etc, swap out the commit with the second version, while keeping the other commits intact. Granted, the file that the commit touches would need to be not touched in other commits. That's not out of question in a typical software project - maybe a file in the utils folder which…

> Granted, the file that the commit touches would need to be not touched in other commits. That's not how git works. The commit contains the entire tree. You could prepare two separate repositories such that `git checkout deadbeef0001deadbeef` in one checks out the linux kernel and in the other checks out ILOVEYOU.exe.

You're right. Commit id points to a commit object, that points to a tree object and subsequently to individual blob objects. Then it is sufficiently harder, you need to find a collision between 2 blob objects, both of which are executable and don't look suspicious.

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

#159

Post by throwaway984393 »

cletus wrote: post #25

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 abo…

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

The name literally means stupid person.

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

#160

Post by perl4ever »

CobrastanJorji wrote: post #137
kragen wrote: post #123

Earlier quoted context omitted.

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.

Just to nitpick, I don't think that formula is valid. We're primarily interested in "unrelated" wolf attacks, but it counts the total fatalities, not the total number of fatal incidents. If we count each fatal attack as only one incident, regardless of the casualties, we get 2^-258 instead. But of course we also need to take into account where the 6-member team lives. If they all live in West Bengal, India, the consi…

There was an organization devoted to reintroducing wolves to the northeastern US, but I don't believe they found it politically feasible.

However, I have seen (and photographed) something I called a coyote, but others insisted was a wolf.

It has been asserted that coyotes tend to evolve to resemble wolves, when there are none in an ecosystem.

Post reply on HN