Cryptographic Hash Function
Brute-Force Attacks: Cryptographic Hash Function
- A brute-force attack does not depend on the specific algorithm but depends only on bit length.
- In the case of a hash function, a brute-force attack depends only on the bit length of the hash value.
- A cryptanalysis, in contrast, is an attack based on weaknesses in a particular cryptographic algorithm.
- We look first at brute-force attacks.
Preimage and Second Preimage Attacks: Cryptographic Hash Function
- Adversary wishes to find a value such that H(y) is equal to a given hash value h.
- The brute-force method is to pick values of y at random and try each value until a collision occurs.
- For an m-bit hash value, the level of effort is proportional to 2m.
- Specifically, the adversary would have to try, on average, 2m-1 values of y to find one that generates a given hash value h.
Collision Resistant Attacks: Cryptographic Hash Function
- Adversary wishes to find two messages or data blocks, x and y, that yield the same hash function: H(x)=H(y).
- This turns out to require considerably less effort than a preimage or second preimage attack.
- The effort required is explained by a mathematical result referred to as the birthday paradox.
- Thus, for an m-bit hash value, if we pick data blocks at random, we can expect to find two data blocks with the same hash value within 2𝑚 = 2𝑚/2
- Yuval proposed the following strategy to exploit the birthday paradox in a collision resistant attack
- The source, A, prepared to sign a legitimate message x by appending the appropriate m-bit hash code and encrypting that hash code with A’s private key.
- The opponent generates 2m/2 variations x’ of x, all of which convey essentially the same meaning, and stores the messages and their hash values.
- Moreover, The opponent prepares a fraudulent message y for which A’s signature is desired.
- The opponent generates minor variations y’ of y, all of which convey essentially the same meaning. For each y’, the opponent computes H(y’), checks for matches with any of the H(x’) values, and continues until a match is found.
- The opponent offers the valid variation to A for signature. This signature can then attached to the fraudulent variation for transmission to the intended recipient.
Cryptanalysis: Cryptographic Hash Function
- As with encryption algorithms, cryptanalytic attacks on hash functions seek to exploit some property of the algorithm to perform some attack other than an exhaustive search.
- The way to measure the resistance of a hash algorithm to cryptanalysis is to compare its strength to the effort required for a brute-force attack.
- In recent years, there has been a considerable effort, and some successes, in developing cryptanalytic attacks on hash functions.
- To understand these, we need to look at the overall structure of a typical secure hash function, indicated in Figure.
- Cryptanalysis of hash functions focuses on the internal structure of ‘f’ and based on attempts to find efficient techniques for producing collisions for a single execution of ‘f’.
- Once that done, the attack must take into account the fixed value of IV.
- The attack on f depends on exploiting its internal structure.
- Typically, as with symmetric block ciphers, f consists of a series of rounds of processing. So that the attack involves analysis of the pattern of bit changes from round to round.