Hacker News Reader

Comment by ak217 | Hacker News Reader

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.

View on HN

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.

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.

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

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.

Specifically, I wrote a program to search for single-bit-flip collisions in sha1 truncated to 16 bits. The program didn't need to search for long before finding two messages with the same 16-truncated sha1 with a single bit flip at bit 1 of byte 171 of a 256-byte message. 376 1 171 be44b935e7ecfc81d1fe2cddcd7c1d7e04338fd83fa994cd6a877732ca5d8db83346bd9ccbfc4c8770682bd307c782421a512a80a106be87825d5c13f3156e23ffaacdfc1651f88f775507d1175542def2ccf084271ebd4ead175c8a448be0d50b26f59d970301ebc5a7f672d3ea870d9a1e02f8f5fd01c38297b8aa264a3f07fec32f9a91aa359784d2d9ce0e4649465c705f50feed23dcbefc0a726cfadb5e47ee577ed45203f90d6e2e650d42ddb10cba49d06bd4cdad4e6eaf5cfcb062de2539fc847ce0c104f2e667369080eaaab5934ae5f7f1ba733c3d1bfbda87bfa72ef12475b9ff0edc4deb99e6a5cf387c7f6b9c71ea62b4db4bb67c92d36460dd be44b935e7ecfc81d1fe2cddcd7c1d7e04338fd83fa994cd6a877732ca5d8db83346bd9ccbfc4c8770682bd307c782421a512a80a106be87825d5c13f3156e23ffaacdfc1651f88f775507d1175542def2ccf084271ebd4ead175c8a448be0d50b26f59d970301ebc5a7f672d3ea870d9a1e02f8f5fd01c38297b8aa264a3f07fec32f9a91aa359784d2d9ce0e4649465c705f50feed23dcbefc0a726cfadb5e47ee577ed45203f90d6e2e640d42ddb10cba49d06bd4cdad4e6eaf5cfcb062de2539fc847ce0c104f2e667369080eaaab5934ae5f7f1ba733c3d1bfbda87bfa72ef12475b9ff0edc4deb99e6a5cf387c7f6b9c71ea62b4db4bb67c92d36460dd

https://gist.github.com/jepler/96d1e779dc95b8941b208887e10a8...

On the other hand, any CRC will detect all such errors; a well-chosen one such as CRC32C will detect all messages with up to 5 bits flipped at this message size.

This is quite appropriate for the error model in data transmission, of uncorrelated bit errors. https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koop... is a pretty good paper, though there are probably better ones for readers without an existing background in how CRC works.

You are not testing a crypto hash. "Crypto hash" means it is cryptographically strong, not truncated to 16 bits. For example ZFS with checksum=sha256 will use the full 256-bit hash for detecting data corruption.

Yup, you're right. if you use a full size cryptographic hash then the number of undetected errors can be treated as 0 regardless of hamming distance. On the other hand, it has 8x the storage overhead of a 32-bit CRC.

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.

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.

Posts like this are what keep me coming back to HN.

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

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.

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.

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.

Reply on news.ycombinator.com