6 ms·

crc32c is not weakish, and was chosen for a reason: crc32c has widespread hardware acceleration support that remains faster than any hash, and crc32c can be com

by ak217 10y ago

crc32c is not weakish, and was chosen for a reason: crc32c has widespread hardware acceleration support that remains faster than any hash, and crc32c can be computed in parallel (unlike a hash, it has no hidden state, so you can sum independently computed block checksums to get the overall blob checksum). Bitrot detection doesn't need a cryptographic hash. You may want a hash for other purposes (like if you somehow trust your metadata volume more than your data volume), but that's a separate and slower use case.

dom0 10y ago
CRC32c -> I saw this many times fail to detect corruption on message lengths anywhere between a couple kB and a few MB. btrfs blocks are 16 kB iirc, so in range. The longer hashes of ZFS, Borg and so on mean that if it's corrupted I _definitely_ know. Not so confident with CRC32 from experience.
- ak217 10y ago
  I'm curious about the setting in which you saw these failures, could you elaborate? Unlike a plain checksum, CRC-32C is hardened against bias, which means its distribution is not far from that of an ideal checksum. This means if your bitrot is random and you're using 16KB blocks, you will need to see on the order of ((2 * * 32) * 16KB)=64TB of corrupted data to get a random failure. Modern hard drives corrupt data at a rate of once every few terabytes. TCP without SSL (because of its highly imperfect checksum) corrupts data at a rate of once every few gigabytes. Assuming an extremely bad scenario of a corrupt packet once every 1 GB, in theory you'd need to read more than a zettabyte of data to get a random CRC-32C failure. I'm not doubting that real world performance could be much worse, but I'd like to understand how.
  - planteen 10y ago
    Posts like this are what keep me coming back to HN.
  - vardump 10y ago
    > This means if your bitrot is random and you're using 16KB blocks, you will need to see on the order of ((2 * * 32) * 16KB)=64TB of corrupted data to get a random failure. No, that's what you need to generate one guaranteed failure, when enumerating different random corruption possibilities. Simply because 32-bit number can at most represent 2^32 different states. In practice, you'd have 50% probability to have a collision for every 32 TB... assuming perfect distribution. By the way, 32 TB takes just 4-15 hours to read from a modern SSD. Terabyte is just not so much data nowadays.
    - leni536 10y ago
      Just a nit: you don't get a guaranteed failure at 64TB, you get a failure with approx 1-1/e ~= 63% probability. At 32TB you get a failure with approx 1-1/sqrt(e) ~= 39% probability. I do agree that tens of TBs are not too much data, but mind that this probability means that you need to feed your checksum 64TB worth of 16KB blocks, every one of them being corrupt, to let at least one of them go trough unnoticed with 63% probability. So you don't only need to calculate with the throughput of your SSD, but the throughput multiplied with the corruption rate.
    - deleted 10y ago
      [deleted]
  - marcosdumay 10y ago
    For disk storage CRC-32C is still non-broken. You can't say the same about on-board communication protocols or even some LANs. When people started using CRC-32 it was because with the technology of the time it was virtually impossible to see collisions. Nowadays we are discussing if it's reasonable to expect a data volume that gives you 40% or 60% of collision chance. CRC32 end is way overdue. We should standardize on a CRC64 algorithm soon, or will have our hands forced and probably stick with a bad choice.
- cmurf 10y ago
  Not exactly, blocks are 4KiB so the vast majority of the CRC32C's apply to 4KiB block size; the metadata uses 16KiB nodes and those have their own checksum also. From what I see in the on disk format docs, it's a 20 byte checksum.
bascule 10y ago
Bitrot detection doesn't need a cryptographic hash. Not only is a cryptographic hash unnecessary, under certain circumstances it will actually do a worse job. Cryptographic hashes operate under a different set of constraints than error detecting code. With an error detecting code, it's desirable to guarantee a different checksum in the event of a bitflip. With a cryptographic random oracle, this is not the case: we want all outcomes to have equal probability, even potentially producing the same digest in the event of a bitflip. As an example of a system which failed in this way: Enigma was specifically designed so the ciphertext of a given letter was always different from its plaintext. This left a statistical signature on the ciphertext which in turn was exploited by cryptanalysts to recover plaintexts. (Note: a comparison to block ciphers is apt as most hash functions are, at their core, similar to block ciphers) Though the digests of cryptographic hash functions are so large it's statistically improbable for a single bitflip to result in the same digest as the original, it is not a guarantee the same way it is with the CRC family. Cryptographic hash functions are not designed to be error detecting codes. They are designed to be random oracles. Outside a security context, using a CRC family function will not only be faster, but will actually provide guarantees cryptographic hash functions can't.
- ReidZB 10y ago
  In practice, the chance of a digest collision between two messages that differ in a single bit is exceedingly small for any secure cryptographic hash function. It's so small that it's practically not worth considering. Cryptographers are incredibly careful in building and ensuring proper diffusion in cryptographic hash functions.
- mrb 10y ago
  "Not only is a cryptographic hash unnecessary, under certain circumstances it will actually do a worse job." A cryptographic hash is unnecessary, but as you point out in the next to last paragraph, it is statistically improbable that it will do a worse job. Because collisions are statistically improbable.
  - jepler 10y ago
    Less so if you assume the cryptographic hash will be truncated to 32bits so that its size matches crc32c. Furthermore, some of those collisions will be on message pairs with small hamming distance, probably including messages with a single bit flipped which CRC will always detect.

by ak217 10y ago

dom0 10y ago

CRC32c -> I saw this many times fail to detect corruption on message lengths anywhere between a couple kB and a few MB. btrfs blocks are 16 kB iirc, so in range. The longer hashes of ZFS, Borg and so on mean that if it's corrupted I _definitely_ know. Not so confident with CRC32 from experience.

ak217 10y ago
I'm curious about the setting in which you saw these failures, could you elaborate? Unlike a plain checksum, CRC-32C is hardened against bias, which means its distribution is not far from that of an ideal checksum. This means if your bitrot is random and you're using 16KB blocks, you will need to see on the order of ((2 * * 32) * 16KB)=64TB of corrupted data to get a random failure. Modern hard drives corrupt data at a rate of once every few terabytes. TCP without SSL (because of its highly imperfect checksum) corrupts data at a rate of once every few gigabytes. Assuming an extremely bad scenario of a corrupt packet once every 1 GB, in theory you'd need to read more than a zettabyte of data to get a random CRC-32C failure. I'm not doubting that real world performance could be much worse, but I'd like to understand how.
- planteen 10y ago
  Posts like this are what keep me coming back to HN.
- vardump 10y ago
  > This means if your bitrot is random and you're using 16KB blocks, you will need to see on the order of ((2 * * 32) * 16KB)=64TB of corrupted data to get a random failure. No, that's what you need to generate one guaranteed failure, when enumerating different random corruption possibilities. Simply because 32-bit number can at most represent 2^32 different states. In practice, you'd have 50% probability to have a collision for every 32 TB... assuming perfect distribution. By the way, 32 TB takes just 4-15 hours to read from a modern SSD. Terabyte is just not so much data nowadays.
  - leni536 10y ago
    Just a nit: you don't get a guaranteed failure at 64TB, you get a failure with approx 1-1/e ~= 63% probability. At 32TB you get a failure with approx 1-1/sqrt(e) ~= 39% probability. I do agree that tens of TBs are not too much data, but mind that this probability means that you need to feed your checksum 64TB worth of 16KB blocks, every one of them being corrupt, to let at least one of them go trough unnoticed with 63% probability. So you don't only need to calculate with the throughput of your SSD, but the throughput multiplied with the corruption rate.
  - deleted 10y ago
    [deleted]
- marcosdumay 10y ago
  For disk storage CRC-32C is still non-broken. You can't say the same about on-board communication protocols or even some LANs. When people started using CRC-32 it was because with the technology of the time it was virtually impossible to see collisions. Nowadays we are discussing if it's reasonable to expect a data volume that gives you 40% or 60% of collision chance. CRC32 end is way overdue. We should standardize on a CRC64 algorithm soon, or will have our hands forced and probably stick with a bad choice.
cmurf 10y ago
Not exactly, blocks are 4KiB so the vast majority of the CRC32C's apply to 4KiB block size; the metadata uses 16KiB nodes and those have their own checksum also. From what I see in the on disk format docs, it's a 20 byte checksum.

bascule 10y ago

Bitrot detection doesn't need a cryptographic hash. Not only is a cryptographic hash unnecessary, under certain circumstances it will actually do a worse job. Cryptographic hashes operate under a different set of constraints than error detecting code. With an error detecting code, it's desirable to guarantee a different checksum in the event of a bitflip. With a cryptographic random oracle, this is not the case: we want all outcomes to have equal probability, even potentially producing the same digest in the event of a bitflip. As an example of a system which failed in this way: Enigma was specifically designed so the ciphertext of a given letter was always different from its plaintext. This left a statistical signature on the ciphertext which in turn was exploited by cryptanalysts to recover plaintexts. (Note: a comparison to block ciphers is apt as most hash functions are, at their core, similar to block ciphers) Though the digests of cryptographic hash functions are so large it's statistically improbable for a single bitflip to result in the same digest as the original, it is not a guarantee the same way it is with the CRC family. Cryptographic hash functions are not designed to be error detecting codes. They are designed to be random oracles. Outside a security context, using a CRC family function will not only be faster, but will actually provide guarantees cryptographic hash functions can't.

ReidZB 10y ago
In practice, the chance of a digest collision between two messages that differ in a single bit is exceedingly small for any secure cryptographic hash function. It's so small that it's practically not worth considering. Cryptographers are incredibly careful in building and ensuring proper diffusion in cryptographic hash functions.
mrb 10y ago
"Not only is a cryptographic hash unnecessary, under certain circumstances it will actually do a worse job." A cryptographic hash is unnecessary, but as you point out in the next to last paragraph, it is statistically improbable that it will do a worse job. Because collisions are statistically improbable.
- jepler 10y ago
  Less so if you assume the cryptographic hash will be truncated to 32bits so that its size matches crc32c. Furthermore, some of those collisions will be on message pairs with small hamming distance, probably including messages with a single bit flipped which CRC will always detect.