5

Btrfs supports crc32c, xxhash, sha256 and blake2b as checksums when storing and reading files. crc32c and xxhash are designed to detect random errors while sha256 and blake2 are considered cryptographically secure. My question is, in what scenarios do I need cryptographically secure checksums in btrfs (or other filesystems)?

Is it only in scenarios where someone intentionally can change the data (eg. hackers) or are xxhash not good enough to detect random errors in some cases?

What is the probability that some data changes on its own (random error) and at the same time has the same checksum as before the error occurred (collision)?

Also, not as important, do disk usage increase when using blake2b instead of eg. xxhash or do inode sizes remain the same? Should I even care about this?

Anyway, thanks!

Improve this question
5
  • 2
    If a hacker changes the data, they will also change the checksum to match; this will happen automatically, as the hacker will simply use the file system to make the change.
    – Erik Eidt
    Commented Dec 1, 2020 at 1:52
  • 1
    I can see that I should probably have reasoned some more before using that as an example :p however, my question still remains and now I am even further away from an answer :/
    – kjdf
    Commented Dec 1, 2020 at 2:02
  • Every hash function out there can spot some errors, and not others. Choose the one most likely to spot the kinds of errors expected for a given device operating in a given environment. Space is a different beast to terrestrial to hard drive to solid state. As for cryptographically secure this has no mean from a security perspective, they might trip up novices who physically extract the drive but that is about it.
    – Kain0_0
    Commented Dec 1, 2020 at 3:04
  • Note that, if I am not mistaken, the latter two were specifically introduced as a very first step of supporting encryption. It shouldn't be too surprising that you need cryptographically secure hashes for encryption schemes.
    – Jörg W Mittag
    Commented Dec 1, 2020 at 6:54
  • @JörgWMittag, I will investigate what you say about supporting encryption further, thank you. I read that a strong checksum would be preferred for deduplication, but I do not know enough about that to have an opinion.
    – kjdf
    Commented Dec 2, 2020 at 3:15

1 Answer 1

Reset to default
5

A question is which width of xxhash is used?

Due to the birthday paradox the chance of an accidental collision is higher than you might think. For example there's a 50% chance of an accidental collision with just 65000 different items to hash with a 32-bit CRC (based on the square-root approximation of the birthday paradox). And 50% is much higher than you'd like to risk.

Both sha256 and blake2b are much wider than this. (Or, that is, Blake2b can be.) So the chance of an accidental collision is much lower.

(In this context an "accidental collision" would be a data corruption that hashed to the same value as the original. In a file system you'd have of course many many many more than 65000 items to hash ... whether you do it by disk blocks or files ...)

So it isn't necessary to have a cryptographical secure hash - just a wide good one. But for practical purposes, the fastest generally available wide hashes are the cryptographic ones because that's where the time and effort has been spent to optimize them.

(I have no idea about how this impacts the space required by inodes, if it does at all. But in the grand scheme of things, unless you're on a really restricted-space file system in an embedded system of some kind, the different is likely negligible. But someone else could answer that.)

Improve this answer
7
  • 1
    First of all, thank you very much for your reply! on btrfs, xxhash is 64 bits and blake2b is 256 bits. I get the birthday paradox, but in this case that would mean that all blocks are corrupted in the first place which is not the case hopefully (disk is dead). Only a few percentage of the disk may be corrupted and at the same time the randomly corrupted data (not designed by an attacker) must produce the same checksum as the original data at that location. The checksum may of course collide with the checksum of some other data on the disk, but that doesn't matter either (birthday paradox).
    – kjdf
    Commented Dec 1, 2020 at 11:22
  • 3
    What matters is does it collide with itself, not if it collides with other data on the disk
    – kjdf
    Commented Dec 1, 2020 at 11:39
  • 1
    Remember that CRC is designed for checking corruption, though, so it has some guarantees: you can guarantee that a single-bit flip will change a CRC, while there's no such guarantee for SHA-1
    – Criticizing Israel not allowed
    Commented Dec 1, 2020 at 12:53
  • 1
    CRCs were designed to detect n-bit errors (n=1,2,...) in communications. Disk failures (spinning ones, not SSDs) are generally of the track loss type (physical damage) or sector loss, both of which are MANY bits. Crypto hashes are a better solution for these than CRCs. (havent looked at xxhash internals and design criteria so YMMV).
    – Ger Hobbelt
    Commented Dec 1, 2020 at 13:27
  • 1
    This answer is either a misunderstanding (or incomplete understanding) of the Birthday Paradox or simply fails to realize that it doesn't apply to the question asked. The Birthday Paradox is about the (for some people) counter-intuitive increase of the probability of collisions among multiple items when the amount of items increases. It would only apply if you use the in-filesystem checksum to look for file duplicates or use that checksum to identify the file itself against some list or database (which, to my knowledge, nobody does) and the question was not about that anyways.
    – blubberdiblub
    Commented Jan 11, 2023 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.