2

If we use SHA-256 checksum to detect corruptions to a file, what is its capability in terms of missed errors?

For example, reading the page about error correction and detection here, under the section of an CRC example it states:

For a burst error of length n – 1, the probability of error detecting is 100 % .

A burst error of length equal to n + 1 , the probability of error detecting reduces to 1 – (1/2)n-1 .

A burst error of length greater than n – 1 , the probability of error detecting is 1 – (1/2)n .

Is there any research of the similar capabilities for SHA-256?

Improve this question
9
  • In short, you will never get a natural collision with SHA-256. Even if you filled every hard drive in the world with small random files, the chance that any two differing files will have matching SHA-256 hashes is effectively nil.
    – forest
    Nov 20, 2018 at 1:20
  • 1
    See also crypto.stackexchange.com/q/39641/54184
    – forest
    Nov 20, 2018 at 2:19
  • Quite relevant links to the two other articles. Though, I guess to prove "you will never get a natural collision with SHA-256", it needs to show a upper bound of the collision probability. The 2nd link says it gives only the lower-bound. Its original words say that it is "the minimum probability of collision with no hypothesis on the hash". Or am I missing something?
    – minghua
    Nov 20, 2018 at 6:44
  • 1
    There is no way to prove that SHA-256 will never be broken. As it is however, there are absolutely no known attacks against the full 64-round SHA-256. Until we discover such an attack, the upper bound is going to be very high. Discovering such an attack would reduce the upper bound even if the attack is not practical. Since there is none, collisions are expected at 2^128 inputs (half of 256 due to the birthday paradox). At maximum, it would be only after 2^256 inputs, but that is obscenely unlikely.
    – forest
    Nov 21, 2018 at 2:21
  • 1
    See Wikipedia for a list of known attacks against hashes in the SHA-2 family. Note that the only attacks that can be considered against the full hash if they work on every round (e.g. 64/64 for those with 64 rounds, or 80/80 for those with 80 rounds). In particular, the best practical attack only works against SHA-256 reduced to 28 rounds. Real SHA-256 uses 64. The best known collision period only works on 31 rounds, yet requires an impractical amount of computing power. It doesn't work on all 64 rounds, so SHA-256 is secure.
    – forest
    Nov 21, 2018 at 2:25

1 Answer 1

Reset to default
2

Is there any research of the similar capabilities for sha256?

Sort of. SHA-256 is not designed to deal with burst errors, so you cannot compare the burst error detection properties of a CRC to a hash like SHA-256. Such a comparison simply isn't possible. However, you can compare the error detection capabilities of CRC32 with a hash like SHA-256.

With an algorithm like CRC32, certain types of changes to the input are guaranteed to result in a different checksum value. Using a good polynomial (a value intrinsic to a CRC's ability to detect modifications) allows more common types of changes to be detected. With a cryptographic hash like SHA-256 (which attempts to model a random oracle) on the other hand, there is no such guarantee. Detection of changes to input is entirely probabilistic. A cryptographic hash is as likely to detect a change to a single bit as it is to detect the entire input being replaced with something entirely different.

The thing to remember is that, unlike a CRC where certain types of input are more or less likely to result in a collision (with certain types of input having a 0% chance of causing a collision), the actual probability of collisions for input to a cryptographic hash is a function of only the length of the hash.

So, what are these different types of algorithms used for? A CRC is good for efficient, fast detection of accidental changes (corruption, etc.), with single-bit changes being detected with 100% probability. A cryptographic hash is used when the input set is large enough that the birthday bound may be reached and a small hash size is likely to result in some collisions, or when an attacker might intentionally try to craft input to collide (for example when generating certificates or signing a document).

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .