Hacker News Reader

Comment by newscracker | Hacker News Reader

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 deduplicate data across all their users (expanding the footprint for collisions)? Are there any research papers/articles/investigations about this?

View on HN

It depends on how the deduplication is configured, and the risk tolerance of the organization running it, I suppose.

ZFS, for example, has a dedup setting option that forces the file system to do a byte-for-byte verification for any deduped data: https://docs.oracle.com/cd/E19120-01/open.solaris/817-2271/g...

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.

In my generic question above, I wasn't referring to someone intentionally causing collisions, but about random collisions that could occur because of these data chunks coming from a large pool of data (say a system with tens or hundreds of millions of users with several hundred GB each of varied data among them). AFAIK, chunking methods usually do not use additional metadata (like a file timestamp or size or name) that could help do a more comprehensive comparison instead of relying on a hash alone. Are the chosen chunks very small (which means the number of hashes would be quite large, making deduplication take longer when looking for exact matches)? I'd be interested in writings from real systems online that explore the choices they have taken and how they pre-empt random collisions (as much as they can design it into the system).

are there any systems that do sha-1 for dedup? I am only aware of sha-256.

Git?

git computes the sha1 checksum over the header that includes the length + the file data; also checks the length in the header as well as the the hash; Linus says that it would be less practical to find a collision that has the same length as the original data; I guess at some stage even that might become possible.

Subversion's dedup was broken by the http://shattered.io/ SHA-1 collision in 2017 https://medium.com/@hyrum/shattered-subversion-7edea4ba289c

bup does. Even worse: rsync relies on md5 for finding duplicate blocks.

at least rsync does that only when --checksum is specified as option; otherwise it assumes that files with the same date/time/size are the same (which is probably not too bad as a default).

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.

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.

The filesystem removes a document, but you can't expect it will be the right one more than 50% of the time.

An attacker may be able to control the way it happens.

It may be repeatable to always remove the first or the last. If it's online dedup, it'll always be the last.

Or the attacker can provide many copies of the document you want to still have a copy of, and one copy in the middle of the one that should be vanished.

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

>SHA1 is vulnerable to preimage attacks.

From your linked article:

>All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks. In general, a collision attack is easier to mount than a preimage attack, as it is not restricted by any set value (any two values can be used to collide).

SHA-1 (and SHA-256 and many other hash functions) are subject to length extension, which is how the 2017 shattered attack works: find a pair of short prefixes that work as PDF headers and that have colliding hashes; then append a common suffix such that the different headers display different parts of the suffixes. Once the collision has been found you can easily make your own colliding PDFs - https://alf.nu/SHA1

This breaks anything that dedups on just the SHA-1 hashes of raw files

What does "for hashes" mean? For a hash table? Of course it's fine for a hash table (but probably too slow). Hash tables don't need collision resistance. If you need collision resistance then SHA-1 is broken.

Reply on news.ycombinator.com