Preimage attack

Archetype attacks (also English. Preimage attack ) are attacks on a cryptographic hash function with a view to a given hash of an unknown message ( First-archetype attack , even English. First-preimage attack ) or to a given message itself ( Second Original image attack , also known as second pre-image attack ) to find another message that generates the same hash.

• In the first archetype attack, the goal is to find an archetype for a hash value.

Given: Hash , the message N does not need to be known Searched: so that: = ${\displaystyle S(N)}$
${\displaystyle N'}$ ${\displaystyle S(N')}$ ${\displaystyle S(N)}$

• In the case of a second archetype attack, the goal is to find a second archetype for a message that is hashed to the same value.

Given: Message , so that the hash of the message is calculable. Wanted:, so that: and = ${\displaystyle N}$ ${\displaystyle S(N)}$
${\displaystyle N'}$ ${\displaystyle N'\neq N}$ ${\displaystyle S(N')}$ ${\displaystyle S(N)}$

example

The text of a contract (“I order a coffee machine for 100 €”) is signed with the help of a hash. An attacker can now either know the hash of the signature alone or also the text of the contract. A practicable prototype attack exists for the hash algorithm used; in the first case, only a first prototype attack is possible, in the second case both attack variants are possible. The attacker can now generate texts that have the same hash as the contract. These texts will normally not be a meaningful message. The attacker therefore has to generate texts until they form a meaningful message and are suitable for his attack (“I order 200 coffee machines for € 2,000 each”).

Explanation

If passwords are encoded directly using a hash and the attacker only knows the hash, he can obtain another password through an initial archetype attack. Since this second password has the same hash, the attacker can use it to gain access.

If the attacker already has a password, for example through a first archetype attack or through previous knowledge, he can now use this additional information (and that of the previously known hash of the correct passwords) through a second archetype attack Obtain further valid passwords.

Basically, it cannot be decided whether passwords that were determined by attacks on hashes are original. Because with all common hash functions, each hash can face an unlimited number of possible passwords (non- injectivity ). No features are stored other than the actual hash itself that would allow further verification.

effort

Because more information is available with a second archetype attack than with a first archetype attack, more variables can be retained or linked to other variables when looking at equations, differential paths, etc. of the compression function of the hash function, whereby their number of degrees of freedom decreases and the necessary effort can be reduced.

After the knowledge of a suitable message from a second archetype attack, this can easily be converted into the hash required for the first archetype attack by using the hash function. With the appropriate hash of a first archetype attack, however, no suitable message can be found with less effort than a second archetype attack. So with a second archetype attack you get a first archetype attack as a gift .

Pre-image attacks are much more difficult to carry out than a collision attack, since pre-image attacks always look for a special message relating to a further special message or a scatter value, whereas a collision attack searches for any message relating to any further message. See: Birthday Paradox . For example, a collision attack with SHA-1 still needs about 2 ⁵² attempts, an archetype attack 2 ¹⁰⁴ , i.e. not twice, but 2 ⁵² times as many attempts.

Web links

• heise Security - Consequences of the successful attacks on SHA-1
• Eurocrypt 2009 - SHA-1 collisions now 2 ^ 52 (PDF; 32 kB)