2
$\begingroup$

What I know so far

Fact 1) I know that all cryptographic hash functions have the following properties

  • They are many-to-one in nature

  • They produce fixed size outputs

  • Given an output x it is infeasible to find the original message m such that H(m) = x

Fact 2) I know that certain cryptographic hash functions are "stronger", but more "expensive" to compute than others - in the sense that trying to overcome their (Property 3) is a lot harder and time consuming/resource intensive.

sha512(m) is harder to crack than sha256(m) which is in turn harder to crack than sha224(m)

Fact 3) I also know that certain cryptographic hash functions perform worse on verifying a message's integrity than a simple CRC checksum. (According to the following stackexchange post)

A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't. The CRC is geared towards reliably detecting error patterns that commonly occur in transit, so it will do better on those kinds of errors and worse on others. The short hash does optimally over all inputs, and as a result does worse than CRC on the inputs CRC is good at dealing with.

What I want to know

Question 1) What common hash functions are worse than CRC checksums, and which are better than them in verifying integrity? (e.g. file corruption/changes).

Question 2) Is it the case that the stronger the cryptographic hash function, the better it is at verifying integrity? (e.g. sha512 will be able to detect file changes better than sha256).

Improve this question
$\endgroup$
4
  • $\begingroup$ It does NOT hold that "sha256(m) (is) harder to crack than sha224(m)" w.r.t. an attack that attempts to "find the original message m such that H(m) = x". If a human uses m as password, a very practical brute force attack (e.g. with a GPU farm) has excellent chances to succeed, and there's no difference in difficulty. Also, if there was some cryptanalytical weakness in SHA-256 (we have no reason to believe that), and for m random of suitable size (say 8 to 16 random bytes), it would be likely that the truncation at the end of SHA-224 mitigates that weakness. $\endgroup$
    – fgrieu ♦
    Dec 12, 2019 at 5:42
  • $\begingroup$ @fgrieu Do you think you could elaborate and justify your claim of "there's no difference in difficulty."? $\endgroup$
    – AlanSTACK
    Dec 12, 2019 at 5:50
  • $\begingroup$ My policy is to answer questions that are asked, and comment on incorrect statements they might contain, so that the question can be improved. The present questions states as goal "verifying integrity" of the message, which SHA-256 and friends are good at if integrity of the hash is assured. My point is that making it hard to "find the original message" is a very different goal, which SHA-256 and SHA-224 meet equally as poorly if message is a password. That's because testing a password is equally fast, and the narrower SHA-224 is still large enough to make false positives unlikely. $\endgroup$
    – fgrieu ♦
    Dec 12, 2019 at 6:12
  • $\begingroup$ You need to specify, what you mean with integrity. Your question and the quoted question make a connection to error detection for unintentional changes and communication errors. That is a very different thing than considering a malicious adversary. In general, in cryptography you should always consider the second one. And against a smart adversary, a CRC is completely irrelevant. Accidential changes have nothing to do with cryptography. Therefore: Your 3rd 'Fact' does not deal with a goal in cryptography. $\endgroup$
    – tylo
    Dec 12, 2019 at 23:04

2 Answers 2

Reset to default
2
$\begingroup$

1) All common cryptographic hash functions are better than CRC, even MD5. This is due to the fact that they are designed to detect malicious tampering, whereas CRC is not. MD5 is still crackable, but CRC can be trivially manipulated.

2) hash function collision resistance determines how "good" they are at integrity verification, as there are more possible unique outputs, bigger is better, however even 64-bit collision resistance is enough to detect non-malicious data corruption in most cases unless you are dealing with large files. SHA256 has 128-bit collision resistance, which is a lot, that is 340 billion billion billion billion, which is more atoms than contained in all of the human beings on the planet combined. The collision resistance of a 512-bit function such as SHA512 is just nuts, almost matching the amount of atoms in the entire universe.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hey, thanks for the response. Before I accept your answer, could you speak on the quote "A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't...". Does the quote not contradict your claim "All common cryptographic hash functions are better than CRC..." $\endgroup$
    – AlanSTACK
    Dec 12, 2019 at 5:16
  • 1
    $\begingroup$ @AlanSTACK: your quote "..CRC won't" is correct, assuming the message is less than a certain length, which depends on selection of the CRC polynomial. Changes of 1 or 2 bits are the most likely accidental message changes in a telecom context (for 1 bit per symbol at least, which used to be the norm and still has relevance). Richie Frame's statement is in a cryptographic context (since we are on Crypto.SE), thus adversaries are assumed to act to the best of their interest and there is no reason to believe that an adversary who can change 1 or 2 bits in a message is unable to change more. $\endgroup$
    – fgrieu ♦
    Dec 12, 2019 at 6:58
  • $\begingroup$ @AlanSTACK a severely truncated hash has less collision resistance, and is also no longer " a common cryptographic hash function" due to such truncation $\endgroup$
    – Richie Frame
    Dec 13, 2019 at 1:47
1
$\begingroup$

1) What common hash functions are worse than CRC checksums, and which are better than them in verifying integrity? (e.g. file corruption/changes).

All cryptographic hash functions are better (ie. More secure) than CRC checksums. As the first answer from this question states:

A checksum (such as CRC32) is to prevent accidental changes. If one byte changes, the checksum changes. The checksum is not safe to protect against malicious changes; it is pretty easy to create a file with a particular checksum.

2) Is it the case that the stronger the cryptographic hash function, the better it is at verifying integrity? (e.g. sha512 will be able to detect file changes better than sha256).

Oh yes. The collision resistance of SHA-256, is $2^{256} \gg 64^{36}$. That's a very$^{very^{very}}$ big number:

For comparison, as of January 2015, Bitcoin was computing 300 quadrillion SHA-256 hashes per second. That's 300×1015300×1015 hashes per second. Let's say you were trying to perform a collision attack and would "only" need to calculate 21282128 hashes. At the rate Bitcoin is going, it would take them $3.6 \times 10^13$ years. In comparison, our universe is only about $13.7 \times 10^9$ years old. Brute-force guessing is not a practical option.

(Quote trimmed: see here for full answer)

SHA-512 has an even bigger collision resistance, and is more secure for checksums. The bigger the collision resistance and output, the more secure.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Do you think you could comment on the quote "A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't." - Does it not contradict the claim that "All cryptographic hash functions are better"? $\endgroup$
    – AlanSTACK
    Dec 12, 2019 at 5:39
  • $\begingroup$ @AlanSTACK "The checksum is not safe to protect against malicious changes; it is pretty easy to create a file with a particular checksum". And where did you get that quote from? I believe it's incorrect. $\endgroup$
    – Legorooj
    Dec 12, 2019 at 5:41
  • $\begingroup$ The confusion stems from another stackexchange post which I have linked to on my original question. The gist of the other response is that "CRC is good at detecting certain things that cryptographic hash functions don't handle so well". I was wondering how to properly interpret this claim through the lens of your answer. $\endgroup$
    – AlanSTACK
    Dec 12, 2019 at 5:48
  • $\begingroup$ @AlanSTACK CRC is designed for error checking, ie random transmission noise, not intentional errors. As I quoted in the answer, it's much easier to find two different files with the same CRC32 checksum. With CRC32 the output must be one of $2^{32}$ values. At $10000$ checksums a second (I could do that for less than $500 worth of hardware) it'd take not quite 5 days at the most to find a collision. Therefore, the quote is wrong. $\endgroup$
    – Legorooj
    Dec 12, 2019 at 6:34
  • $\begingroup$ The collision attack on SHA-256 has $\mathcal{O}(\sqrt{2^{128}})$-time complexity not $\mathcal{O}(\sqrt{2^{256}})$ $\endgroup$
    – kelalaka
    Dec 12, 2019 at 8:35

Your Answer

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

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