Collision resistance

As collision safety or collision resistance is referred to in the context of cryptography, a property of hash functions, protection against certain attacks on the process to offer.

Motivation

A hash function provides to a document seen as arbitrarily long sequence of bits, a bit sequence of fixed (of dependent ) length. If two documents and different hash, it is certain that the documents are different ( ). However, the converse is not true, because there are many more different possible documents as possible hash values ​​. Two documents are referred to as collision. If the area of ​​the ( permissible ) documents is not restricted, a hash function so it can not be genuine collision. To what extent it is nevertheless justified at least in the practical application of the same hash values ​​close to the same documents, depends on the hash function used.

Definition

The hash function is referred to as weak collision- safe if it is impractical to find a given document, a second document ( the so applies ) collides with.

The hash function is called collision- safe as (strong) if it is impracticable, even a collision, ie two arbitrary (but different ) to find.

Comments

In the definitions of the notion of practical feasibility emerges. Since there are only finitely many possible hash values ​​, but an infinite number of documents, it is in principle possible to find by continuously trying out a collision. If the hash bits long, the hash must be calculated in order to find a given document is a collision (second - preimage attack) of about documents. If both archetypes may be freely chosen, a collision is typically found even after only experiments ( collision attack ) due to the birthday paradox. It is so much easier to break the collision resistance, than the weak collision resistance. Where is sufficiently large, the computational complexity of this method of trial still exceeds every limit of practicability. If no method is known, which is much faster, a collision, the search is regarded as practically impossible after a collision.

It should be noted that a first can be "cracked" as collision- safe -respected processes through the development of new algorithms and then no more is collision secure. In cryptographic applications, only those hash functions should be used, which are considered according to current state of research as collision- safe.