The first chosen-prefix collision for SHA-1 • Hacker News Board

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

#151

Post by tptacek » Tue, Jan 07, 2020, 5:44 PM UTC

jlokier wrote: post #90

LeonM wrote: post #14

Earlier quoted context omitted.

Depends on your definition of 'better'. Theoretically SHA-512 is harder to brute force than SHA-256, but 256 bits is already extremely strong, so really there is no practical safety benefit of SHA-512 over SHA-256. On 64-bit capable processors SHA-512 has a slight performance gain over SHA-256, but only on larger inputs. However, the digest of SHA-512 is twice the size, so what you gain in processing time, you loose…

> but 256 bits is already extremely strong The strength of hashes like SHA-256 doesn't just come from the number of output bits. The 256 bits there is relevant for brute force attacks, but not more sophisticated attacks that take into account the internal structure of the hash algorithm, and in some cases "weak" values. SHA-512 performs more "rounds" of computation than SHA-256. Although it's impossible to compare tw…

Cryptographic engineers do not in fact think you should use SHA-2-512 so that you can maximize the number of times the round function is applied.

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

#152

Post by blattimwind » Tue, Jan 07, 2020, 5:44 PM UTC

vbrandl wrote: post #106

tambourine_man wrote: post #83

Earlier quoted context omitted.

I'm refering to not being able to rely on encryption in the long term.

Hashing is a separate problem from encryption. There is no proof that one way functions (the idea behind hashing) even exist (by proving this, you would actually prove P!=NP, IIRC). Encryption has a slightly better track record of being broken. AES still holds its promise and is also secure against quantum computing (you might want longer keys, but that's it). And if you want really, provably unbreakable encryption,…

The best known attack against AES reduces attack complexity by about two bits over brute force. Given the history of block ciphers, the idea that AES might not be broken in this life time is not uncommon.

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

#153

Post by jtmarmon » Tue, Jan 07, 2020, 5:47 PM UTC

comicjk wrote: post #101

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…

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…

The problem is that the expectations of software are much more akin to the expectations of a bridge than those of a bulletproof vest

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

#154

Post by Ar-Curunir » Tue, Jan 07, 2020, 5:48 PM UTC

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…

Because by shouting loudly now, we can maybe get changes into libraries within the next 5 years, before these attacks are commonplace

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

#155

Post by jlokier » Tue, Jan 07, 2020, 5:50 PM UTC

tptacek wrote: post #151

jlokier wrote: post #90

Earlier quoted context omitted.

> but 256 bits is already extremely strong The strength of hashes like SHA-256 doesn't just come from the number of output bits. The 256 bits there is relevant for brute force attacks, but not more sophisticated attacks that take into account the internal structure of the hash algorithm, and in some cases "weak" values. SHA-512 performs more "rounds" of computation than SHA-256. Although it's impossible to compare tw…

Cryptographic engineers do not in fact think you should use SHA-2-512 so that you can maximize the number of times the round function is applied.

I'm not sure what that sentence means, can you rephrase it?

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

#156

Post by femto113 » Tue, Jan 07, 2020, 5:51 PM UTC

noja wrote: post #125

Is a collision impossible with two hashes, each using a different algorithm?

Not impossible, but assuming there's not a mathematical flaw that affect both algorithms the difficulty is roughly the product of the difficulty of finding a collision in each. AFAIK no one has come up with a joint collision for MD5+SHA1 despite collisions in each being practical for several years.

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

#157

Post by mlyle » Tue, Jan 07, 2020, 5:51 PM UTC

upofadown wrote: post #149

newscracker wrote: post #133

General questions: (edit: these are indeed general questions, not just about SHA1) Has anyone else been worried about data deduplication done by storage and/or backup systems, considering that they usually use hashes to detect data blocks that are "the same" (without additional metadata) and avoid storing those "duplicate data blocks" again? Doesn't this seem far worse when you also consider that systems like Dropbox…

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.

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

#158

Post by Ar-Curunir » Tue, Jan 07, 2020, 5:53 PM UTC

mbowcutt wrote: post #107

shilch wrote: post #98

Earlier quoted context omitted.

Like computer scientist, they think binary: Either it's secure, or it's not. In reality there's a spectrum where you also have "good enough".

"good enough" relies on a threat model. Cryptography researchers work in the abstract - without a threat model you must consider cases where your attacker has unlimited resources. It's good enough for you and me, but research isn't meant to be practical, imo

What. The first thing any security paper defines is the assumed threat model. People design all kinds of schemes for different threat models.

The point with assuming conservative threat models for key primitives like hash functions is that the threat model can change rapidly even within the same application, and attackers only get stronger. So you err on the side of caution, and don't rely on luck to keep safe.

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

#159

Post by tptacek » Tue, Jan 07, 2020, 5:55 PM UTC

jlokier wrote: post #155

tptacek wrote: post #151

Earlier quoted context omitted.

Cryptographic engineers do not in fact think you should use SHA-2-512 so that you can maximize the number of times the round function is applied.

I'm not sure what that sentence means, can you rephrase it?

The analysis you have provided for why SHA-512 is superior to SHA-256 is faulty.

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

#160

Post by tialaramex » Tue, Jan 07, 2020, 5:57 PM UTC

no_flags wrote: post #36

umvi wrote: post #20

Is "a Shambles" British or something? I've always heard it as "in Shambles"

"Far be the thought of this from Henry's heart, To make a shambles of the parliament-house!" -Shakespeare (Henry VI, Part 3)

Note that in Shakespeare's time an audience would directly have understood "make a shambles" here to mean violent bloodshed in the parliament building because a "shambles" would have been a common term for somewhere you killed animals to produce meat. Which is exactly what is being described here. Henry VI part 3 is not a play about a polite disagreement settled over lunch...

Today "shambles" remains in the common vocabulary, but only in a sense of things being messy or disorganised, most English readers today probably wouldn't think of literal violence and I suppose that the people who named this website, likewise, were thinking of modern usage.