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
The first chosen-prefix collision for SHA-1
221–230 of 369 posts
Re: The first chosen-prefix collision for SHA-1
#222Earlier 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.
Re: The first chosen-prefix collision for SHA-1
#223This 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…
Re: The first chosen-prefix collision for SHA-1
#224General 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.
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
#225Re: The first chosen-prefix collision for SHA-1
#226Earlier 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".
Re: The first chosen-prefix collision for SHA-1
#227Earlier 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.
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…
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
#229Earlier 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…
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
#230This 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…