1

I have been told, if I wanted to create virus signatures from infected files to use for detection in the future, I should be careful as some of them are prone to collision attacks?

0

1 Answer 1

3

A collision for a cryptographic hash function h is a pair of data elements (two sequences of bits) m and m', which are distinct from each other, but hash to the same value (mm' but h(m) = h(m')). Since a hash function accepts as input sequences of bits that can be much longer than the fixed output size, the number of possible inputs to a hash function exceeds the number of possible outputs; therefore, it is a mathematical certainty that collisions exist for any given hash function. A cryptographically secure hash function is such that actually finding a collision is computationally infeasible (we know that collisions exist, but we do not want people to be able to find them).

A collision attack is an attack that exploits the structural weaknesses of a specific hash function to produce collisions. This works only for hash function for which a weakness is known, i.e. functions that, by definition, have been demonstrated not to be cryptographically secure.


What a collision attack would allow for an attacker, in your case, is unclear. Your envisioned "virus database" stores hash values computed over sequences of bytes that have been deemed "malicious" and should be shot on sight; you want to store hash values and not the malicious sequences themselves mostly to make lookups more efficient and to keep the storage costs low. If the attacker arranges for two of his virus to hash to the same value, then this means that inclusion in the database of the (common) hash value would resulting in banning both virus in one go, which is about the opposite of what the attacker would like: the attacker wants his virus to go undetected, not to be spotted even more efficiently.

Collision attacks would be a huge problem in the case of a database of non-virus. If you make a database of "sane" executables, then the attacker would try to make a collision between a harmless executable m, and some malware m'; he would then submit m for verification, so that h(m) is added to the list of "verified harmless files". Since the attacker arranged things so that h(m) = h(m'), that collision would mean that m' (the virus) would also be declared sane.


While it is unclear what could be gained (for the attacker) from hash collisions in a virus database, it is nevertheless considered better to use a cryptographically secure hash function, just in case. The main example of a non-secure hash function is MD5: collisions can be very efficiently produced for this function. The situation of SHA-1 is less clear: no collision has been exhibited yet, but a theoretical attack has been described, which should result in collisions with a computational effort that is huge (261 evaluations of the function) but still substantially less than the efforts which would be required for a "perfect" hash function with the same output size (280).

The usual recommendation for a secure hash function is SHA-256, or, more generally, any function of the SHA-2 family (SHA-256 is one of the currently six members of that family).

2
  • Perhaps not an "attack" per se, but confusion in the database causing false positives.
    – schroeder
    Aug 31, 2015 at 17:31
  • As long as we are talking about collisions, then the false positives would be against non-virus files specially crafted by the attacker itself, so the confusion would be rather limited. If the attacker could create collisions where one of the file is a pre-existing "normal" executable, then we would be talking about second preimages, which are a lot harder to build (even with MD5 we do not know how to do that).
    – Tom Leek
    Aug 31, 2015 at 17:38

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.