1
$\begingroup$

We used to use CRCs to check the integrity of files. For safety analysis we could associate a probability for detecting a corrupted bit in a large file. Now we are using an RSA Signed SHA-3 hash for authentication.

Are there any methods to calculate the probability two files of the same size to have the same SHA-3 hash? I am assuming that the probability is 1.

How about associating a probability based on the number of changed bits or even 1?

$\endgroup$
4
$\begingroup$

Are there any methods to calculate the probability two files of the same size to have the same SHA-3 hash?

Collision resistance is generally bound by the birthday bound, which equates to half of the output size. So finding two files (or input messages really) takes about $2^{h / 2}$ where $h$ is the output size of the (SHA-3) hash. And that's assuming you have enough storage, which is unlikely.

However, if you've two files that haven't been pre-selected or pre-computed then the chance of selecting two depends on the full output size: one in $2^{h}$, which is negligible.

For more information you can try and learn about pre-image resistance.

I am assuming that the probability is 1.

The probability that there are inputs that hash to the same hash is 1 (or very close to 1 for large files of limited size), assuming that the hash output is well distributed - which is rather likely.

If you have messages of, say 1MiB each and a hash of 256 bits then each hash value will should be valid for many messages; this is called the pigeonhole principle: you will get crowded cages if you try and fit 100 doves in 10 holes after all. For all possible 1MiB files you'd have $2^{2^{23}}$ values distributed over $2^{256}$ possible hash values, which means that about $2^{8388352}$ messages would result in the same hash on average!

However, finding such messages is where the complexity comes in: cryptographic hashes are one way hashes that cannot be reversed: there is no easy calculation to create messages that hash to a certain value other than hashing messages. Of course, looping trough all $2^{8 \cdot 2^{20}} = 2^{2^{23}}$ messages (for all possible files of 1MiB in size) is infeasible.

How about associating a probability based on the number of changed bits or even 1?

The probability of finding two files with identical hashes is the same: negligible. However, there is one thing to remember: the change of the hash value itself is not taken into account. Cryptographic hashes are not designed to resist changes of the file and hash value together. CRC's may even have better properties in scenarios where errors are limited to a segment which is not wider than the CRC, or where the random error is occurs in a limited, possibly larger segment of the message.


However, if the hash is part of a signature then it cannot change. If you change bits of a signature then the verification will fail with very high certainty. So verifying the hash value as part of signature verification is perfectly fine.

To dig a bit deeper: where chance or an adversary can flip any bits of the hash without signature, you need the private key to generate the a signature based on a hash. If you change any bits of a signature then either verification fails before the hash is compared (RSA) or when the - now randomized - hash is compared (indirect comparison for ECDSA).

The chance that a signed file has been changed and the signature verifies is negligible, in other words. As long as the hash remains unchanged or if the hash bits are all flipped with about $0.5$ chance it will be computationally infeasible to find another file that hashes to the same value.

So replacing a CRC with a signature is perfectly fine. The chances that another file verifies is negligible. Not even malicious changes to the file will make the signature verify, given a secure hash function such as SHA-3. This is a distinct advantage over CRC's.

Beware that swapping files together with their signature is still perfectly possible, something that is often overlooked. Signatures will also not help against removal or duplication by themselves. As always, just applying crypto doesn't secure your system by itself.

|improve this answer|||||
$\endgroup$
0
$\begingroup$

I am assuming that the probability is 1.

I think you either you don't really understand what probability is. Or by probability 1 you mean something other.

If we use the 512 bit variant of SHA-3, the hash has length of 64 bytes. It means if you take all possible files of size let say 65 bytes, there will be guaranteed collisions, as @Maarten Bodewes explained. If you mean the probability of such collisions, then sure, it is 1. But how many files you need to get a guaranteed collision? For 512 bit hash you need more than 2^512 ~= 10^154 files. Even if you could generate 1 000 000 files per second, you would need 10^140 years to generate this number of files. That's why the probability that you can create a file that produces the same hash as a given one, is 0, not 1.

What is the probability that any two files of the same size give the same hash? The distribution of SHA-3 is considered even. It means that the probability that two arbitrary files of the size containing random data produce the same hash is 1/2^512 = 2^(-512) ~= 10^(-154). In the reality the most files (video, audio, PDF document, etc.) have some structure and values of many parts of them are not quite random. Even considering this, the probability of collision is very small, almost 0.

That's why your statement about probability 1 is not correct.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Please comment on my understanding. I am using an RSA signed SHA3 hash of a file for authentication and was wondering what credit I can for the file integrity as in a quantitative safety analysis. In other words what is the probability of a corrupted file producing the same hash as the original file. A 1 kB file has 2 ^(2^13) possible values. The number of collisions for each possible value of a 256 bit hash will be 2 ^ (7936) assuming a uniform distribution. The probability of a corrupted file producing the same hash as the original is 1/ (2^256) regardless of the number of collisions. $\endgroup$ – Sal Navidi Feb 18 at 18:05
  • $\begingroup$ Yes, the probability of collision is 1 l (2^256). But in the 2nd paragraph of your question you wrote I am assuming that the probability is 1, which is not correct, you contradict to your recent comment. $\endgroup$ – mentallurg Feb 18 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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