2

Hash functions can have collisions. It's almost trivial to compute data that has a matching MD5 hash to the original. Consider critical data that must not be altered in transit and assume that only the data, and not the checksum, can be altered. Also assume that anybody can access the data.

Which of these would be a good way to go about creating a checksum of the data (Or if there's a better way, that would be great too)?

  1. Using multiple hash functions on the data and concatenating them. Surely having multiple hashes would make it hard for an attacker to generate data that causes a collision in all of the hash functions?
  2. Use HMAC with SHA512 (Key-length attack mitigation) and share the secret along with the generated hash. This secret will not change for this file, so the secret will be the same for all those who obtain it.

Thanks

  • assume that only the data, and not the checksum, can be altered Again a (nonsensical) homework, right? – deviantfan May 22 '17 at 18:00
  • If one of the hash algorithms in option 1 is SHA-512 it might be in theory a bit less secure than HMAC with SHA-512 and a known secret since this is essentially using SHA-512 twice on the message. But in practice both cannot be cracked today. If you instead only use MD2 and MD5 in option 1 then it is very insecure. – Steffen Ullrich May 22 '17 at 18:04
  • @deviantfan Not a homework, just wondering what the correct way to go about checksum'ing is. – Filon May 22 '17 at 18:23
  • @deviantfan Consider it this way: 2048 bit RSA is used on the checksum to verify the content creator, however you wouldn't hash the plaintext since RSA has a maximum size limit and you'd have to encrypt every 214 bytes of data. The data can be altered (a malicious attacker replacing it with a malicious string that happens to produce the same hash output), but the hash itself is secured with RSA. – Filon May 22 '17 at 18:32
  • @Filon ...but a signature isn't just a hash (and, btw., th the general case saying that a signature is an encrypted hash is wrong). – deviantfan May 22 '17 at 19:45
2

Two questions, really.

  1. No. Don't ever. Bad idea. Bad bad bad bad bad. Never assume that concatenating multiple insecure things causes you to be secure because, y'know, it probably should be more secure. You may gain a little security through obscurity, but remember that hashes are broken. Fundamental failures in the mathematical model providing security guarantees are found. It is not immediately clear whether any two broken algorithms can be easily broken together unless you have the mathematics background required to break crypto in the first place. Never do it this way.

    • As a trivial example, consider the following set of checksums: MD-5, CRC8-AUTOSAR, and CRC-32. By using 3 checksums I should certainly be more secure right? No. You'll find that the two CRC's add 0% more security over that of MD-5, and MD-5 is broken, so those three checksums won't do anything for you.
  2. Yes, you can use HMAC to provide hash-based message authentication codes, and then strip out the authentication bit by publishing the key. If you remove the words that wont apply, you're left with "hash code." Yes, if you hash something with a secure hashing algorithm, the result will be secure. Of course, you could save yourself a ton of time by just using the hash.

  3. Best option is the one you didn't mention: find out which hash algorithms are secure, and just use one.

Finally, focus on the weak parts of your system. You describe a case where the data can be attacked, but nobody will attack the checksum. That's a pretty strange situation. The only case I know of where that occurs is where one downloads a file from an untrusted location and then downloads its signature from a trusted location in order to minimize bandwidth required on the part of the trusted location. Make sure that the rest of your system is secure. As Bruce Schneier points out, very rarely is the crypto actually the weak part of the link!

  • 1. True, I was basing it on the fact that some websites have multiple hashes in order to allow a user to check as many as necessary due to collisions, I was wrong. 2. My reasoning for HMAC was the length extension attack, which would be a problem with the large data I'd be hashing. – Filon May 22 '17 at 20:58
  • Assuming they have the same digest size, claiming that you can reduce security by adding another, broken hash algorithm is simply incorrect. Otherwise you could just hash $secret_digest with a broken algorithm to recover it (which is obviously impossible). When using multiple hashes on top of each other, it is as strong as the strongest link, not as weak as the weakest. So unless you use a reduced digest size like sha1(crc16(sha1(data))), then there is no decrease in security by using multiple algorithms. Not that it necessarily improves security, of course... – forest Dec 28 '17 at 10:19
  • @forest I do not believe you are correct. As an intentionally extreme example, consider the case of modifying msg in such a way that verification via broken(SHA2(msg)) where broken is the hash function broken(x) = 1. It's trivial to see how easy it is to create a modified evilMsg such that we see a collision broken(SHA2(msg)) == broken(SHA2(evilMsg)). This shows that if the outermost algorithm has major problems with collisions, then the entire algorithm has major problems with collisions. – Cort Ammon Dec 28 '17 at 19:30
  • That would be reducing digest size, which I did say was one of the cases where there would be reduced security. See security.stackexchange.com/questions/83881/… and crypto.stackexchange.com/questions/270/…. TL;DR preimage resistance and collision resistance are increased when you do H1(H2(m)) or H1(m) ^ H2(m), though H1(m)||H2(m) has some caveats wrt reduced preimage resistance. Apparently H1(H2(m)||m) is even better. – forest Dec 29 '17 at 5:27
  • A function where H(m) = 1 would not be a hash function (unless it's a parity bit, aka a polynomial based on x + 1, but in that case, it's reducing the output size again). Even doing MD5(MD4(m)) would be fine (where "fine" means no worse than MD5(m)), despite MD4 being so weak that it's faster to find collisions than it is to compute MD4(m)! You would have to very carefully design a bad hash where H(H(m)) = H(H(m')) with high probability for there to be any risks (so perhaps using some types of true sums, but even a CRC isn't at risk of that). – forest Dec 29 '17 at 5:33
0

As soon as you use the phrase "share the secret along with the generated hash" you are on shaky ground. Hashes are public, anyone can generate them, and anyone can check them. "secrets" are secret. You need a secure channel to communicate them, or they aren't secret. HMACs work between parties with the secret already. Right tool for the right job.

The purpose of a hash is to detect corruption (violation of integrity), either accidental or deliberate. While it may be trivial to generate an arbitrary MD5 collision, it is still difficult to create a meaningful plain text against a specific MD5 sum.

So, what is the purpose of your hash? If it is against noise on the line (accidental corruption) md5 is just fine. If it's against an active attacker subverting your plaintext (what I assume from the question) what threat model assumes the checksum can't be altered if the plaintext can?

If your question is "would it be more difficult to find a single document that collides with two different check sum algorithms" the answer is clearly yes. But why? What are you trying to accomplish?

If you are concerned about the strength of any particular hashing algorithm, use a stronger one. You can, of course, use two or more algorithms, but to get any benefit, all of your recipients would have to check all the hashes.

I think it is likely that some client(s) (software or humans) will only check one, at which point your multi-hash isn't useful.

My recommendation would be to just use a more collision-resistant hash function.

  • Since the clients would be using the same piece of software, as well as the checks are automated by said software, there's no chance that only one hash would be checked. – Filon May 22 '17 at 20:50

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.