Live data from Hacker News

The first chosen-prefix collision for SHA-1

sha-mbles.github.io

221–230 of 369 posts

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

#221
post #179

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…

No, the bridge collapsed because it was never touched again after initial deployment, for 10 years. How are buildings doing in Chernobyl? Don’t neglect your data, if you want to keep it safe always. :P

A counter example are roman aqueducts

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

#222

Earlier quoted context omitted.

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

That doesn't apply here, since the birthday paradox is about the existence of a collision, not that any particular sequence collides. Most people in the room will still have unique birthdays even if one pair share theirs.

[deleted]

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

#223
post #198

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…

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

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

#224

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…

Yep, I'm afraid of that. I have no idea how they are mitigating this, and I doubt they'll ever disclose.

From what I recall when the first collision was proved it was with a PDF which is easier to craft a collision from. I also seem to recall that the collisions were from hashes of the whole file.

The dedupe engine written where I work chunks a file and hashes those chunks meaning it's somewhat harder to craft collisions (I forget where the chunking boundaries are, but it's within a range iirc). The hashing algorithm was SHA-1 last I checkee but I've never heard even company folklore of corrupted backups caused by hash collisions. I get the feeling that it's near impossible in practical terms given the size of the string being hashed. Having said that, hubris is the downfall of programmers everywhere, so I wouldn't bet all my money on it.

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

#226
post #89

Earlier quoted context omitted.

I think GP was taking about the general nature of “previously assumed to be unbreakable” methods being broken. Not sure if he has implying using a checksum also for encryption

What do you mean by "previously assumed to be unbreakable" ? SHA-1 has been known to be unsafe for a dozen years, we just went from "assumed to be breakable" to "yep, definitely breakable, here's how one exact attack will work".

But backups have existed for more than a dozen years. And its replacements today, SHA-256 and SHA-3 will also be broken if you wait long enough.

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

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

I disagree. Deduplicating filesystems often depend on hash equivalency meaning data equivalency. They may or may not have modes to validate all data before deduplication, but these suck for performance and are often turned off.

E.g. I make two things that hash to the same thing. One is a contract where I'm obligated to pay back a loan. Another is some meaningless document. I give them to a counterparty who puts them in their filesystem, which later scrubs and deduplicates data. Since they hash the same, the filesystem removes the contract and leaves my meaningless document (or never bothers to store the contract because it already exists, if deduping online, etc).

Note that this is a chosen prefix collision, which is much more demanding (and more useful!) than finding a collision in general. And this leaves aside that SHA1 is looking increasingly vulnerable to preimage attacks which further broaden the attack scenarios.

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

#228

> We note that classical collisions and chosen-prefix collisions do not threaten all usages of SHA-1. In particular, HMAC-SHA-1 seems relatively safe, and preimage resistance (aka ability to invert the hash function) of SHA-1 remains unbroken as of today. Nice to see this bit of intellectual honesty. Would be even nicer if they had explained what that means in terms of PGP keys.

It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid. For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victi…

> It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid.

I'm not really knowledgeable about the implementation details of GPG. Mind explaining how this follows?

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

#229
post #108

Earlier quoted context omitted.

FWIW, a lot of very smart people seem to think that we actually do have symmetric encryption in a state where it "works" and is "understood" and that AES is unlikely to be "broken". What we don't really feel so great about is asymmetric encryption, but at least that feels like something P != NP might imply can be done... hashing algorithms just have this problem where if you glance at the information theory you would…

> 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 expected to be sufficient to uniquely describe some arbitrarily large amount of information? That just flies in the face of the naive expectation. The only argument that it is even sort of reasonable to expect would be the idea that while there are an insane number of files very similar but not quite your file, very few of them are "interesting" to a human in any way, and so the set of "interesting" files might be super small... but it isn't like we designed the hash functions to know that.

The reality that it seemingly can be done well enough that no one notices most of the time is fascinating and surprising--the kind of thing that inspires awe and wonder at the universe if true or calls into question our hubris if it isn't--not something obvious in the way the existence of symmetric ciphers nor something reasonable to expect in the way asymmetric ciphers are: to the extent to which reality lets us pull this one off we should be thankful.

2) If one can truly "easily" derive a "secure" hash function from a secure symmetric cipher, then why don't we ever have secure hash functions, despite seemingly having secure symmetric ciphers? If this is so easy, I suggest you do it and then wait 30 years and see if someone figures out how to break it (and we can see it AES is still holding strong).

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

#230

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…

The thing to remember about cryptography is that as long as it's based around computational power, it can always be broken at some point. Especially if we're building exponentially more powerful computers every N years.
Post reply on HN