7

If I have a file of indeterminate length and I generate the SHA256 of that file, then generate the SHA256 of the first half and the last half, then verify all three, does that decrease the odds of a collision attack?

Basic example:

The cat is in the house.

SHA256: aa4a1ee8c29e759ca71a0945b11ef34fb123e7d38e611082f2ea37898ba5e8cc

The cat is i

SHA256: 2d04e4d86b53cbe134f0bd3c79eb60a57ef7c3d34fb2c69b772f2ef9230c093b

n the house.

SHA256: c19216e36d4df8ece789dc86fc0624fd16771843fff7fd00fb1b393ac9ad9244

What about a weaker hash that's faster? What about a smaller portion of the file?

  • Well, it's definitely not any weaker than just verifying the whole file, so it's probably stronger. But why bother? – immibis Mar 16 '16 at 5:45
  • I'm trying to determine if it's less susceptible to collision attacks. SHA256 is secure enough that I wouldn't worry about it, but a faster, more vulnerable algorithm could benefit from this. – ndm13 Mar 16 '16 at 13:57
  • Doing more hashing is no weaker, but also no stronger. Attacks are done with generalities rather than specific cases. If someone can create a collision against some input X, then they can do the same for your sub hashes. As for using a weaker hash that's faster, that gives you no additional strength, and suffers from the weaknesses of the lesser functions. You cannot determine if it's less susceptible to attacks without a deep understanding of the whole algorithm and the specific reasons why each part of it was chosen. – Omniwombat Mar 17 '16 at 7:49
1

You might be interested to read about ssdeep, a "context-triggered piecewise hash" (CTPH) used as a content-agnostic form of fuzzy hashing. Ssdeep builds hashes of pieces of a file so that similarity can be determined; say one character changes between two otherwise identical files. The checksum of the changed file parts will differ, but the checksums of all other parts will not, so the files are deemed to be highly similar.

You're essentially trying to do this but without intending to use it to measure file similarity.

I am under the impression that as long as you keep entire hashes (do not truncate them) and the segments you hash are large enough to make collisions rare (maybe 512 bytes?) then you will have a sufficient level of data integrity. It is theoretically possible that you'll have more integrity since you have a longer hash length, but there are so many areas that you have to be especially careful about in your implementation that I would not at all recommend this.

That said, you specified three sha256 hashes, including one for the whole file. As long as you're matching all three, this should be, at its weakest, as good as sha256 alone. It's likely stronger still, but you'll (probably) be just as susceptible as a single sha256 when it comes to theoretical SHA-2 vulnerabilities, so you might as well go for another algorithm such as SHA-3 or even (since you still have the full file's sha256) something faster like MD5. You can also consider storing the byte size.

256 bit SHA-2 should be sufficient for anything unless you're worried about the distant future. If that's the case, you can't take anything for granted, but I'd go with SHA2-512 and SHA3-512 and the exact file size.

If you just want more speed and aren't concerned with being attacked (i.e. you're just worried about data integrity from faulty hardware and/or crappy networks), you can start with just the file size, then calculate MD5 and SHA1 concurrently (two separate processes, one read of the file). I still wouldn't mess with cutting up a file unless you wanted to use ssdeep (which appears to use MD5 for its pieces by default).

Perhaps an attractive balance of speed and integrity could be to check the file size, then the MD5 of the first 5MB (or the whole file if under 5MB), then the real integrity check, e.g. sha256 or sha3-512. It should* be harder to create a collision and faster to detect failures (stop on the first failure) while being only negligibly slower than just the last check (it took me 0.003s to calculate the MD5 hash of a random 5MB test file). (* I'm expert in neither cryptoanalysis nor cryptographic checksums: this is not authoritative.)

I'm tempted to say that if an attack isn't suspected, you'd be fine with both file size and MD5 (you'd probably be fine with just MD5, though file size would allow you to fail faster and provide slightly better data integrity).

  • Is it more likely to find a hash collision with the same bytesize or a collision that has front and back hashes that match the originals? – ndm13 Mar 25 '16 at 0:47
  • 1
    Requiring the same byte size limits collision possibilities from an ~infinite space to a space equal to the depth of a byte times the size, which for a large file is still pretty noteworthy, though such an attack is hopefully limited in what can be changed (i.e. a payload needs to fit and/or it needs to pass quick vetting such as file magic). Piecewise hashing is probably more robust, but I'm not sure how to evaluate that. – Adam Katz Mar 25 '16 at 1:00
  • When it comes to cryptography (and this falls into that space), it's best to not roll your own; use ssdeep or hashdeep with SHA2 (sha256deep) if you want piecewise hashing. – Adam Katz Mar 25 '16 at 1:00
  • I've heard the nightmares of roll-your-own cryptography, but are the rules the same if it uses a tried-and-true algorithm and doesn't compromise the keys (like salting passwords)? – ndm13 Mar 25 '16 at 1:04
  • 1
    If you use one or more of sha256, sha3-512, and ssdeep/hashdeep, you should be fine. If you create your own system, you might miss something (this is the fundamental philosophy of security). Something like a full file sha256 plus a sha3 of the first ½ and another sha3 of the second ½ should work because you're at least using the full hash (and you're changing algorithms hopefully avoids collision vulnerabilities in SHA2), but any variation must be criticized and I'm not expert enough in cryptoanalysis or file integrity hashing to comment authoritatively. – Adam Katz Mar 25 '16 at 1:33
0

Maybe but not enough to bother with. SHA256 is very secure. There are currently no known collisions for it (or for SHA1 for that matter). You should consider SHA256 as effectively perfect. If you get lucky enough to be attacked due to a collision, publish it and become famous (at least among those who care about these things).

  • That's why I mentioned weaker algorithms at the end. While I'm not encouraging using md5 in production, how would it fare against collisions in this scenario? – ndm13 Mar 16 '16 at 13:55
0

Your logic is based on the assumption that if a collision does happen, it should not happen again based on the very nature of hash functions. But I find that logic to be faulty. You must consider how the collision happened. If one is able to generate a collision for the whole file, they should probably be able to do it for a part as well as for the whole file. The only way your idea will work is if the attacker doesn't know the way you're dividing your file. But since that is not how things work(since the 3 hash values should be known) this should not be able to improve your security. And then as you know, sha256 is still secure enough and will be for good enough period of time, so if you have it, collision is the least of your worries.

  • 1
    Can you elaborate how would an attacker use a generated collision? – techraf Mar 16 '16 at 6:47
  • For instance, I will swap an authentic download file with mine, mine being the one with the collision. It is the same file of the same exact file length but some lines have been replaced with a certain payload(a virus for example). The attacker is going to design his changes in a way that the checksum will match. You get the picture. – Ayadi Ghait Mar 16 '16 at 7:12
  • 1
    Well, actually I need more information to get the picture. So an attacker has three pieces of data that produce the same hash values as respectively the original file and two split parts of it. How would an attacker provide three different pieces of data for verification, where verification engine takes only one input? – techraf Mar 16 '16 at 7:17
  • It's not 3 pieces of data. It's 1, the other two being two parts of it. Your new data will have to adhere to these conditions: 1 having the whole data AND its first half AND its second half checksums all match the originals. It's just an AND condition added. You'd think that this can be really hard, but as I said, it depends on how the first collision happened. If the attacker had an efficient way of producing collisions he can easily adhere to multiple conditions which is difficult. Again, this won't help because no efficient way exists. you won't be using that hash function anyways. – Ayadi Ghait Mar 16 '16 at 11:58
  • Could you, please, rephrase your comment in simple and readable English? It's hard to make sense of "he can easily adhere to multiple conditions which is difficult". – techraf Mar 16 '16 at 12: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.