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

The first chosen-prefix collision for SHA-1

sha-mbles.github.io

Post reply on HN
Print view View original

181–190 of 369 posts

Re: The first chosen-prefix collision for SHA-1

#181

Post by knorker »

kibwen wrote: post #164

Out of curiosity, can anyone explain in layman's terms the differences in design that make SHA-1's successors immune to the known attacks against SHA-1? Ultimately was this the result of an apparent flaw in SHA-1 that only became obvious in retrospect, or was it something totally unforeseeable?

Partly this: Number of bits.

This attack is almost 2^64, and SHA-1 is 160 bits. All else being equal (big big if) that means sha256 is 102 bits, meaning 362703572709.30493 times more expensive. Or about $16321 trillion USD.

Re: The first chosen-prefix collision for SHA-1

#182

Post by p1mrx »

CiPHPerCoder wrote: post #131
Ajedi32 wrote: post #117

Earlier quoted context omitted.

So why would a truncated version of SHA-512 be better than SHA-512? And why is SHA-512 = SHA-256?

Truncated hash functions are not vulnerable to length-extension attacks. Length-extension attacks are relevant when you design a MAC by passing a secret and then a message to a hash function, where only the message is known. Truncating the hash (which is what SHA-512/256 and SHA-384 do to SHA-512) removes the ability to grab an existing hash H(k || m) (where k is unknown and m might be known) and append junk because…

Why do SHA-512/160 and SHA-512/128 not exist? They could be useful as drop-in replacements for SHA1 and MD5.

Re: The first chosen-prefix collision for SHA-1

#183

Post by Skunkleton »

PeterisP wrote: post #97
mehrdadn wrote: post #84

> SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Why are cryptographers always exaggerating things and so out of touch with reality? The first actual collision was like 3 years ago. It's not like the world has been on fire in the meantime, and it's not like SHA-1 is broken for every single possible usage even now. And why the nonsense with "no goo…

Past experience and documents that ceased being classified shows that serious attackers (e.g. NSA) are at least decade ahead of what's publicly known in cryptography; i.e. we know that pretty much always when new relevant groundbreaking math was published, the classified cryptographers had known that for a long, long time already. So if this attack is developed today, then you should assume that NSA has been able to…

> So if this attack is developed today, then you should assume that NSA has been able to execute this attack for at least ten years already whenever it suited them, including mass surveilance of random not-that-important people.

They might be 10 years ahead on the algorithms side, but they aren't 10 years ahead on the hardware side. Also, spending 45k today gets you a single collision. That is hardly going to be useful for mass surveillance.

Re: The first chosen-prefix collision for SHA-1

#184

Post by monktastic1 »

pathseeker wrote: post #169
gpm wrote: post #127

Earlier quoted context omitted.

If the data is shorter than the hash shouldn't it be the same data I backed up with reasonably high probability?

No. http://matt.might.net/articles/counting-hash-collisions/

Can you explain the relevance? If I put N items randomly into >> N buckets the chance of there being a second item in a particular bucket is small (as opposed to there merely being a bucket with two items, as in the birthday "paradox").

Re: The first chosen-prefix collision for SHA-1

#185

Post by Zaak »

kibwen wrote: post #164

Out of curiosity, can anyone explain in layman's terms the differences in design that make SHA-1's successors immune to the known attacks against SHA-1? Ultimately was this the result of an apparent flaw in SHA-1 that only became obvious in retrospect, or was it something totally unforeseeable?

SHA-2 is based on similar techniques to those in SHA-1, which prompted the SHA-3 competition when weaknesses in SHA-1 were first discovered (as they could conceivably have been present in SHA-2 as well). As it turns out, SHA-2 appears to be resistant to the attacks found thus far.

SHA-3 (originally named Keccak) is built on an entirely different foundation (called a sponge function), so it is unlikely that any attack against SHA-1 will be relevant to SHA-3. However, sponge functions are a relatively new idea, and weaknesses in the basic principles could conceivably be found in the future, as could weaknesses in the Keccak algorithm specifically.

Re: The first chosen-prefix collision for SHA-1

#186

Post by knorker »

mlyle wrote: post #157
upofadown wrote: post #149

Earlier quoted context omitted.

SHA1 isn't broken for hashes.

SHA1 is vulnerable to preimage attacks in reduced round variants. The findings keep steadily improving. https://en.wikipedia.org/wiki/Preimage_attack This means if a storage system just uses SHA1 to detect duplication, you can abuse the ability to create a collision to possibly do bad things to the storage system.

Yes, but for the specific concerns listed it should not be a problem. That is, if you upload to dropbox and check the sha1 when it comes back, yes you did get the same data back.

And your data can't be stolen by a hash-to-data oracle either, unless the evil attacker constructed your secret data for you.

So it depends on your threat model. Yes there are practical concerns, but not the ones listed.

Re: The first chosen-prefix collision for SHA-1

#187

Post by staticassertion »

espadrine wrote: post #99
mehrdadn wrote: post #84

> SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Why are cryptographers always exaggerating things and so out of touch with reality? The first actual collision was like 3 years ago. It's not like the world has been on fire in the meantime, and it's not like SHA-1 is broken for every single possible usage even now. And why the nonsense with "no goo…

Cryptographers rely on precise definitions to make their assessments. In particular, a primitive makes a number of useful promises. Any achievement that describes a way in which a promise is not kept makes that primitive broken , regardless of whether that achievement is theoretical or practical. (They often talk about “theoretically broken” or “practically broken” to distinguish whether it was actually done.) > it's…

Is SHA1 not still faster than 256/512? And Blake2 barely faster? I suspect with some hardware SHA1 is still going to beat all of those out - am I wrong? I would love to learn more.

Re: The first chosen-prefix collision for SHA-1

#188

Post by candu »

WorldMaker wrote: post #163
comicjk wrote: post #101

Earlier quoted context omitted.

Bridge engineers don't have to fear the progress of science working against them, but computer security is not alone here. Consider designing body armor or military aircraft and hoping that the state of the art will stay the same! An adversary who can use the progress of science against you is always dangerous. Computer security has been rather lucky so far: the asymmetry between hashing and cracking a hash, for exam…

On a long enough time scale Bridge Engineers still have to worry about decay, entropy, collisions. Some of that can even be attributed to the "progress of science", as bridges have collapsed because earlier assumptions were invalidated by larger trucks, for instance. An issue so far for computer security is less that decay and entropy happen, but that they happen so fast that the timescales are decades or even years…

This is a great point in general: sometimes the problem isn't an adversary using knowledge in your field against you, it's the unintended consequences of progress / changes in adjacent fields.

It also underscores that, when dealing with things like passwords, it's helpful to be able to seamlessly upgrade to more robust methods down the line, e.g. "if this password hash was generated using the old method, check the login using that method but rehash and update the database using the new method after authentication."

Re: The first chosen-prefix collision for SHA-1

#189

Post by [deleted] »

simias wrote: post #52
groovybits wrote: post #10

Earlier quoted context omitted.

Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack detail…

The fact that this attack is chosen prefix does weaken the first argument though, you may now find a collision even accounting for any prefixed git "header". The rest is still completely valid though. I still feel like they really should've taken this problem more seriously and earlier. The more we wait the more painful the migration will be when the day comes to move to a different hash function, because everybody k…

[deleted]

Re: The first chosen-prefix collision for SHA-1

#190

Post by SheepSlapper »

WorldMaker wrote: post #170
tambourine_man wrote: post #76

This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in t…

There's an MC Frontalot song called "Secrets from the Future" and the refrain is "You can't hide secrets from the future." It's something of a useful mantra to remind oneself that if "the future" is a part of your threat model, yes your encryption likely isn't enough because on a long enough timescale it is likely "the future" will crack it. As with any other security issue, the question is "what is your threat model…

"You can’t hide secrets from the future with math. You can try, but I bet that in the future they laugh at the half-assed schemes and algorithms amassed to enforce cryptographs in the past."

Didn't expect to see Front on HN today, what a pleasant surprise.

Post reply on HN