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

231–240 of 369 posts

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

#231

Post by femto113 »

noja wrote: post #218
femto113 wrote: post #156

Earlier quoted context omitted.

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.

So should we do that, as well as keep finding new algorithms?

Concatenating two hashes is an algorithm. Mathematically concatenating two 128 bit hashes is not any stronger than a single 256 bit hash (and is likely weaker), but if it’s all you have (or all you can afford to compute) two weak hashes is definitely much better than one.

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

#232

Post by xmprt »

rakoo wrote: post #223
baddox wrote: post #198

Earlier quoted context omitted.

> Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. When has that happened? Public key cryptography and symmetric key cryptography are still doing fine as far as I'm aware, and the latter doesn't even seem to be vulnerable to quantum computing. Moreover, SHA-1 has been considered insecure for, what, at least 10 years? The fact that a cryptographic ha…

"Public/symmetric key cryptography" is just the name of the practice, of course it's doing fine. What's not doing fine is picking a particular set of ciphers/hash functions/signature scheme and expecting to not fail in 40 years.

Encrypting is still better than not encrypting and if you care about keeping your data private then you can take additional measures to ensure that. Nothing will last forever but that's not a good reason to be nihilistic.

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

#233

Post by im3w1l »

knorker wrote: post #186
mlyle wrote: post #157

Earlier quoted context omitted.

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.

This doesn't sound crazy farfetched. I bet a lot of people have files in their dropbox that were created by someone else.

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

#234

Post by gist »

SAI_Peregrinus wrote: post #214
gist wrote: post #204

Earlier quoted context omitted.

The way I see it, this is what is bad: > We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Many in the 'security industrial complex' make as if they are doing god's work by their 'research' but from a common sense, man/woman on the street, and layman point of view that is not what appears to be going on at all. What the…

We typically assume that organizations like the NSA, FSB, Mossad, MSS, and the like already know of such attacks.

The percentage of people that are impacted by NSA et al is exceedingly small compared to the pain and impact on everyday citizens and companies by disclosures. Not all disclosures and for sure an upside but it's out of control and has been for a long time.

The government (in the US) does not have the resources to go after everyone who commits a crime and that would assume they are actually scooping up info and know of the crimes (they aren't and they don't). They don't even have the resources to audit tax returns (other than a very small percentage). This idea that you are being watched all the time is fantasy. In the US. Other countries? Unfortunate when that's the case but that does not mean as a US citizen I can't view it as detrimental to me that this type of security disclosure makes it so easy for hackers to do a better job (and it does nobody is going to dispute that fact, right?).

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

#235

Post by nickpsecurity »

Skunkleton wrote: post #183
PeterisP wrote: post #97

Earlier quoted context omitted.

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

Other declassified documents of the past showed they were years ahead on hardware, too. The NRE costs got so high that commodity hardware got preferable in the general case. That said, they can still throw money at ASIC's, FPGA's, semi-custom versions of Intel/AMD CPU's, maybe same for GPU's, and so on.

They have access to better and more hardware than most threat actors.

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

#237

Post by mehrdadn »

saurik wrote: post #229
mehrdadn wrote: post #171

Earlier quoted context omitted.

> something P != NP might imply can be done... hashing algorithms just have this problem where if you glance at the information theory you would have guessed they couldn't be possible until someone shows you one that seems to work I'm confused what you mean by this? Why does the info theory suggest hashing wouldn't be possible? Also, you can easily derive a secure hash function from a secure symmetric cipher and vice…

1) The premise of a hash function is that you are going to take a large set of inputs and map it to a small set of outputs such that you don't find collisions, with the use case that the result is somehow so unique that the input file can be henceforth named by its hash and looked up in some giant dictionary of everything we have so far ever bothered to hash. The hash is this tiny bit of information, and somehow is e…

1) Oh I see what you mean now. Yeah I guess it depends on your intuition.

2) I mean, I'm not sure how correct your premise that symmetric ciphers are more secure than hash functions is, but it literally is something that is done. You can read more about it in [1], including the possible pitfalls. The transformation should provide more than enough intuition to see why both are equally plausible, which was the point of my reply. Whether or not it's best to actually implement them that way in practice is a separate question which I'm not trying to answer here.

[1] https://crypto.stackexchange.com/a/6476

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

#238

Post by gist »

jodrellblank wrote: post #216
gist wrote: post #204

Earlier quoted context omitted.

The way I see it, this is what is bad: > We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Many in the 'security industrial complex' make as if they are doing god's work by their 'research' but from a common sense, man/woman on the street, and layman point of view that is not what appears to be going on at all. What the…

The idea behind your complaint is " if we tell good people about risks, then bad people will know about them. If we keep them secret from good people, then bad people won't find out about them ". Or, " if we don't make a list of open doors, then bad people can't find which doors are open ". Which is .. not true. Bad people will already be making their own list of open doors, and sneaking through them without being no…

> "if we tell good people about risks, then bad people will know about them. If we keep them secret from good people, then bad people won't find out about them". Or, "if we don't make a list of open doors, then bad people can't find which doors are open".

You are not recognizing the nuance which is typically the case with people who supports practically any and all disclosure and thinks it's good plain and simple. With almost no downside at all (not the case).

In particular this: "then bad people won't find out about them"

My point is that disclosure makes it simpler for more bad people to find and learn and inflict damage damage. Unclear to me how you could think that isn't what has and is happening. If someone say publishing how to create a card skimmer at a gas station then more people (who are bad actors) will then have what they need to give it a try. If not there will be people who have figured it out and people who will put the effort into figuring it out but you must realize vastly less will do that, right? The disclosure removes a great deal of friction.

The amount of effort and friction and the amount of 'bad people' that can be actors is many magnitudes larger (I would argue) as a result of disclosure.

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

#240

Post by velosol »

Skunkleton wrote: post #183
PeterisP wrote: post #97

Earlier quoted context omitted.

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

They may have been though - there's talk of liquid helium tens+ of gigahertz (8-bit) processors being purpose built (in 2002). The National Cryptologic Museum next door to NSA HQ is a fascinating place and has some very cool displays to include a large disk changer and a piece of a cooling system. There's a PDF at [1] but the discussion at [2] I think might give a better idea.

[1]: https://www.nitrd.gov/pubs/nsa/sta.pdf [2]: https://it.slashdot.org/comments.pl?sid=485458&cid=22736288

Post reply on HN