A function (in this context almost always a one-way function) is said to be collision resistant if it is “hard” to find different inputs that are mapped to the same value. Especially in the case of cryptographic hash functions, this is a common requirement, the break of which is usually considered to be a break of the complete hash function. Collision resistance is a property of cryptographic hash functions, wherein it is computationally infeasible to find two distinct inputs that produce the same output hash value. In other words, a hash function is considered collision-resistant if it is highly improbable for two different messages to result in the same hash digest.
This property is crucial for ensuring the security and integrity of various cryptographic applications, including digital signatures, message authentication codes (MACs), and data integrity verification. Without collision resistance, an attacker could exploit hash collisions to forge digital signatures, create fraudulent data with the same hash value as legitimate data, or undermine the security of cryptographic protocols.
Background of Collision Resistance
Cryptographic hash functions are an important primitive in numerous practical applications, especially in the context of digital signatures in the context of the “hash-then-sign” paradigm. Obviously, it is desirable that no one is able to obtain a valid signature for a message.
---
Somewhat less obvious is the stronger demand for (strong) collision resistance, which prevents the detection of any collisions: here, in order to forge a signature, it is generally no longer sufficient to find an existing one, instead the owner of the secret key must be persuaded to sign a message chosen by the attacker. This may seem rather implausible at first glance, especially since most of the practically findable collisions do not seem to have any meaningful content at first. However, by exploiting various properties of common file formats (e.g. PDF) and typical constructions of most hash functions, it is possible to create two almost freely selectable documents that only appear suspicious when examined by experts. A conceivable scenario in this case would be, for example, that a politician is induced to sign a specially prepared document with supposedly harmless content (digitally), which creates a real signature that an attacker can also use for another document with (superficially) almost arbitrarily different content.
Background of Collision Resistance
A one-way function is said to be weak (in the sense of “easier to reach”) collision-resistant if no attacker is able to find a second one to a given type that is mapped to the same value. The term “second-preimage-resistance” is also common here. Practical attacks against this property in common hash functions are comparatively rare.
Strong collision resistance is usually understood to mean that it is practically impossible to create two different types. Due to the birthday paradox, it is usually much easier to find arbitrary collisions than second archetypes, which is why the output length of most hash functions corresponds to twice the length of the desired security level: If a hash function is supposed to provide about 128 bits of security against collisions.
However, this has changed with the development of SHA-3 and the associated “sponge” design in such a way that it is now possible to lower the resistance to finding first and second archetypes in a defined way to match that of strong collision resistance, allowing for higher performance. However, this doesn’t change the required double length of the output, it just reduces security elsewhere.
In contrast to the relatively unspectacular security history of archetype resistances, the collision resistance of many established and practically used hash functions such as MD5 or SHA-1 has been practically broken. Since these breaks were partly attributed to the Merkle-Damgård construction most commonly used in those functions, which was also the basis of SHA-2, NIST launched the SHA3 competition, the aim of which was to develop a new hash function with ideally a different structure in order to have a ready-made alternative in the event of a break of SHA2 (which has not yet occurred and is now considered rather unlikely).
Tagged With tonight54x