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

A SHA-1 chosen-prefix collision attack

zdnet.com

Post reply on HN
Print view View original

51–60 of 75 posts

Re: A SHA-1 chosen-prefix collision attack

#51

Post by chias »

a1a wrote: post #31
evv wrote: post #26

Can collision attacks provide the same size of data? I suspect it would be dramatically more difficult to produce a collision of equal data-size as the original. So perhaps, the easiest way to defend against a collision attack is to transmit the size of the data alongside the checksum. Like a checksum, it is extremely lightweight and easy to check. In my data framework project (where I use sha1 to identify blocks), I…

Yes, if I interpret your suggestion correctly. How would you know that the attacker have not manipulated the size parameter? That's the best case. Worst case you end up with a memory vulernability (see heartbleed https://xkcd.com/1354/ )

> How would you know that the attacker have not manipulated the size parameter?

This scenario doesn't make a lot of sense. Say I have a goodfile that is 512 bytes long and hashes to 3d8850e1, and someone else wants to produce badfile and convince you that it's my goodfile. GP's suggestion is that I publish a size-plus-hash value "512-3d8850e1" for you to check against. If the attacker is in a position to alter the size part, they're also in a position to alter the hash part, in which case why even bother with a collision? They can just change the hash to be whatever badfile hashes to.

The true answer to GP is that if you do this, it's no longer a hash function. A hash function is defined as taking an arbitrary input and returning an n-bit output for some fixed value of n. By including the size of the input in your output, the size of your output grows logarithmically with the size of your input. This may seem pedantic, but fixed-size-output and arbitrary-size-input is extremely important for general usage of a hash function.

Re: A SHA-1 chosen-prefix collision attack

#52

Post by chias »

evv wrote: post #26

Can collision attacks provide the same size of data? I suspect it would be dramatically more difficult to produce a collision of equal data-size as the original. So perhaps, the easiest way to defend against a collision attack is to transmit the size of the data alongside the checksum. Like a checksum, it is extremely lightweight and easy to check. In my data framework project (where I use sha1 to identify blocks), I…

I included this comment in a response to a child comment, but reproducing it here to make sure you see it:

If your output includes the size of the input, then what you've got is no longer a hash function. A hash function is defined as taking an arbitrary input and returning an n-bit output for some fixed value of n. By including the size of the input in your output, the size of your output grows logarithmically with the size of your input. This may seem pedantic, but fixed-size-output and arbitrary-size-input is extremely important for general usage of a hash function.

Re: A SHA-1 chosen-prefix collision attack

#53

Post by chias »

yardstick wrote: post #17
zdw wrote: post #7

From the paper, this doesn't seem to be able to create a collision while retaining the same length of input data. It seems that checking both the hash and input length would be a very cheap way of identifying attempts at hash collisions.

This is one reason why HMAC-SHA1 is still safe.

This is incorrect, the safety of HMAC-SHA1 doesn't have anything to do with input length comparisons. HMAC-SHA1 is still safe because of how an HMAC operates:

Among other operations, HMAC begins by taking the secret key, XOR'ing it with a magic value not under your control, and using this as the first block when calculating an initial hash. In order to guard against an unlikely but potential pathological key / magic value combination, a similar operation is performed as a second round using a different magic value, and this time operating over the hash output from the first round. As such, HMAC operations are safe against chosen prefix attacks against the underlying hash function, because the first block in either round of hashing is entirely outside of your control.

See https://i.imgur.com/PPlVPr0.png for a visual reference. In this diagram, Y is the value being HMAC'ed. As you can see, any attack on the hash function which requires control of the prefix of the value being hashed is a non-starter.

Re: A SHA-1 chosen-prefix collision attack

#54

Post by yardstick »

chias wrote: post #53
yardstick wrote: post #17

Earlier quoted context omitted.

This is one reason why HMAC-SHA1 is still safe.

This is incorrect, the safety of HMAC-SHA1 doesn't have anything to do with input length comparisons. HMAC-SHA1 is still safe because of how an HMAC operates: Among other operations, HMAC begins by taking the secret key, XOR'ing it with a magic value not under your control, and using this as the first block when calculating an initial hash. In order to guard against an unlikely but potential pathological key / magic…

Thanks, I stand corrected.

Re: A SHA-1 chosen-prefix collision attack

#55

Post by hannob »

bin0 wrote: post #22
pslam wrote: post #11

Earlier quoted context omitted.

Marc Stevens quotes $500K, which is very much still a threat (even an order of magnitude more would be). Plenty of organizations would be willing to spend that much pocket change on a single attack. The game-changer is it's chosen-prefix. A vendor can produce a pair of entirely different binaries with the same hash, but most importantly, they look and behave sane except for the last few blocks of the file. This is ea…

Git isn't really designed for cryptographic security, is it? I have heard that Linus wants it mostly secure so people can verify the integrity of linux source code, but it's not its core competency, so to speak. Though I suppose a project the size of the linux kernel could be a serious target for a collision attack. Regardless, it's switching to SHA-256: https://stackoverflow.com/questions/28159071/why-doesnt-git-...

> Git isn't really designed for cryptographic security, is it?

Well, the git documentation says it is: https://git-scm.com/book/en/v2/Git-Tools-Signing-Your-Work

It is certainly not helpful that Linus at the same time says conflicting things publicly. It would be nice to have some clearly documented expected security properties of the git structure.

This confusion is all a bit unfortunate. While the attack scenarios are obscure, with a secure hash function Git would have some really nice properties to use it in other areas, it would effectively be a secure append-only log. (Some people call this something with the B word which I'll avoid, but that's effectively what it is.)

Re: A SHA-1 chosen-prefix collision attack

#56

Post by avar »

CiPHPerCoder wrote: post #45
mehrdadn wrote: post #40

Earlier quoted context omitted.

Do you know why it's said to be last-resort in the article?

Catalin was quoting me in the article, so it's only fair that I elaborate here. There are four common flavors of the SHA2 family you're likely to run into: - SHA-224 - SHA-256 - SHA-384 - SHA-512 And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail) - SHA-512/256 - SHA-512/224 These latter two don't have n…

> I think BLAKE2 is going to become the de jure SHA2 successor at least until SHA3 hardware acceleration becomes ubiquitous.

I think you mean "de facto", unless you think NIST is going to amend SHA-3 at this point to designate BLAKE over Keccak.

As someone on the sidelines, having read the linked Twitter discussion you had with Marc Stevens your summary of it honestly seems a bit disingenuous.

You mention speed prominently, but fail to mention his counterargument that raw hash speed isn't relevant for most applications.

In practice hashing speed is drowned out by other things, you're not going to have "Android/iOS devices" (as you bring up) hashing GBs of data as a common use-case, and even if you did the cycles/byte for the hash are nothing compared to other things.

For applications where hashing speed does matter (e.g. some server needing to batch-hash things) you have the option of buying hardware-accelerated SHA-256 to get on the order of 30% faster than BLAKE: https://bench.cr.yp.to/results-hash.html

Then as you note downthread your criteria of "at least as secure" only takes into account "known attacks". The absurd logical conclusion of that criteria taken at face value is that we'd all be better off if we each used our own bespoke hash function, since cryptanalysis would never be able to keep up.

Or, in other words, if the algorithm that became SHA-1 hadn't been picked by NIST in 1995 it would be a viable 160-bit hash function today, since there would likely be no known attacks against it, as it would have been obscure enough that nobody would have bothered with it.

So the criteria for a "secure" hash must consider some balance of its algorithm, as well as (or more importantly) the cumulative amount of attention cryptographers have spent on it.

Re: A SHA-1 chosen-prefix collision attack

#57

Post by justincormack »

chias wrote: post #52
evv wrote: post #26

Can collision attacks provide the same size of data? I suspect it would be dramatically more difficult to produce a collision of equal data-size as the original. So perhaps, the easiest way to defend against a collision attack is to transmit the size of the data alongside the checksum. Like a checksum, it is extremely lightweight and easy to check. In my data framework project (where I use sha1 to identify blocks), I…

I included this comment in a response to a child comment, but reproducing it here to make sure you see it: If your output includes the size of the input, then what you've got is no longer a hash function. A hash function is defined as taking an arbitrary input and returning an n-bit output for some fixed value of n. By including the size of the input in your output, the size of your output grows logarithmically with…

Sha1 and sha256 already hash the message length into the hash function and it is limited to 2^64 bits so they do not support arbitrary input size.

Re: A SHA-1 chosen-prefix collision attack

#58

Post by thomaspeyrin »

CiPHPerCoder wrote: post #45
mehrdadn wrote: post #40

Earlier quoted context omitted.

Do you know why it's said to be last-resort in the article?

Catalin was quoting me in the article, so it's only fair that I elaborate here. There are four common flavors of the SHA2 family you're likely to run into: - SHA-224 - SHA-256 - SHA-384 - SHA-512 And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail) - SHA-512/256 - SHA-512/224 These latter two don't have n…

I'm one of the co-author of the SHA-1 cryptanalysis paper. I fully agree with Marc Stevens's: you should not be using Blake2, but SHA2 or SHA3. If speed is an issue, taking reduced step SHA3 (KangarooTwelve) will do the job.

Re: A SHA-1 chosen-prefix collision attack

#59

Post by jwilk »

hannob wrote: post #55
bin0 wrote: post #22

Earlier quoted context omitted.

Git isn't really designed for cryptographic security, is it? I have heard that Linus wants it mostly secure so people can verify the integrity of linux source code, but it's not its core competency, so to speak. Though I suppose a project the size of the linux kernel could be a serious target for a collision attack. Regardless, it's switching to SHA-256: https://stackoverflow.com/questions/28159071/why-doesnt-git-...

> Git isn't really designed for cryptographic security, is it? Well, the git documentation says it is: https://git-scm.com/book/en/v2/Git-Tools-Signing-Your-Work It is certainly not helpful that Linus at the same time says conflicting things publicly. It would be nice to have some clearly documented expected security properties of the git structure. This confusion is all a bit unfortunate. While the attack scenarios…

FWIW, this isn't official Git documentation, just a book about Git.

Re: A SHA-1 chosen-prefix collision attack

#60

Post by [deleted] »

evv wrote: post #26

Can collision attacks provide the same size of data? I suspect it would be dramatically more difficult to produce a collision of equal data-size as the original. So perhaps, the easiest way to defend against a collision attack is to transmit the size of the data alongside the checksum. Like a checksum, it is extremely lightweight and easy to check. In my data framework project (where I use sha1 to identify blocks), I…

[deleted]
Post reply on HN