6 ms·

General questions: (edit: these are indeed general questions, not just about SHA1) Has anyone else been worried about data deduplication done by storage and/o

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?

MichaelMoser123 7y ago
are there any systems that do sha-1 for dedup? I am only aware of sha-256.
- deleted 7y ago
  [deleted]
- munificent 7y ago
  Git?
  - deleted 7y ago
    [deleted]
  - MichaelMoser123 7y ago
    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.
- fanf2 7y ago
  Subversion's dedup was broken by the http://shattered.io/ http://shattered.io/ SHA-1 collision in 2017 https://medium.com/@hyrum/shattered-subversion-7edea4ba289c https://medium.com/@hyrum/shattered-subversion-7edea4ba289c
- rakoo 7y ago
  bup does. Even worse: rsync relies on md5 for finding duplicate blocks.
  - MichaelMoser123 7y ago
    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).
kemitche 7y ago
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/gjhav/index.html https://docs.oracle.com/cd/E19120-01/open.solaris/817-2271/g...
jbverschoor 7y ago
Yep, I'm afraid of that. I have no idea how they are mitigating this, and I doubt they'll ever disclose.
- onei 7y ago
  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.
  - newscracker 7y ago
    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).
upofadown 7y ago
SHA1 isn't broken for hashes.
- mlyle 7y ago
  SHA1 is vulnerable to preimage attacks in reduced round variants. The findings keep steadily improving. https://en.wikipedia.org/wiki/Preimage_attack 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.
  - knorker 7y ago
    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.
    - mlyle 7y ago
      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.
      - 7y ago

MichaelMoser123 7y ago

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

deleted 7y ago
[deleted]
munificent 7y ago
Git?
- deleted 7y ago
  [deleted]
- MichaelMoser123 7y ago
  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.
fanf2 7y ago
Subversion's dedup was broken by the http://shattered.io/ http://shattered.io/ SHA-1 collision in 2017 https://medium.com/@hyrum/shattered-subversion-7edea4ba289c https://medium.com/@hyrum/shattered-subversion-7edea4ba289c
rakoo 7y ago
bup does. Even worse: rsync relies on md5 for finding duplicate blocks.
- MichaelMoser123 7y ago
  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).

kemitche 7y ago

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/gjhav/index.html https://docs.oracle.com/cd/E19120-01/open.solaris/817-2271/g...

jbverschoor 7y ago

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

onei 7y ago
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.
- newscracker 7y ago
  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).

upofadown 7y ago

SHA1 isn't broken for hashes.

mlyle 7y ago
SHA1 is vulnerable to preimage attacks in reduced round variants. The findings keep steadily improving. https://en.wikipedia.org/wiki/Preimage_attack 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.
- knorker 7y ago
  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.
  - mlyle 7y ago
    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.
    - 7y ago