Hash Functions: Cipher Block Chaining
- A number of proposals have been made for hash functions based on using a cipher block chaining technique, but without using the secret key. One of the first such proposals was that of Rabin.
- Divide a message M into fixed-size blocks M1, M2, … , MN and use a symmetric encryption system such as DES to compute the hash code G as
𝐻0 = 𝑖𝑛𝑖𝑡𝑖𝑎𝑙 𝑣𝑎𝑙𝑢𝑒
𝐻𝑖 = 𝐸(𝑀𝑖, 𝐻𝑖−1)
𝐺 = 𝐻𝑁
- This is similar to the CBC technique, but in this case, there is no secret key.
- As with any hash code, this scheme is subject to the birthday attack, and if the encryption algorithm is DES and only a 64-bit hash code is produced, then the system vulnerable.
- Furthermore, another version of the birthday attack can be used even if the opponent has access to only one message and its valid signature and cannot obtain multiple signings.
- Here is the scenario: We assume that the opponent intercepts a message with a signature in the form of an encrypted hash code and that the unencrypted hash code is bits long.
- Use the algorithm defined at the beginning of this subsection to calculate the unencrypted hash code G.
- Construct any desired message in the form Q1, Q2, … , QN-2.
- Compute 𝐻𝑖 = 𝐸(𝑄𝑖, 𝐻𝑖−1) for 1 ≤ 𝑖 ≤ (𝑁 − 2).
- Generate 2m/2 random blocks; for each block X, compute 𝐸(𝑋, 𝐻𝑁−2). Generate additional 2m/2 random blocks; for each block Y, compute D (Y, G), where D is the decryption function corresponding to E.
- Based on the birthday paradox, with high probability, there will be an X and Y such that 𝐸(𝑋, 𝐻𝑁−2) = 𝐷(𝑌, 𝐺).
- Form the message Q1, Q2, … , QN-2, X, Y, This message has the hash code G and therefore can use with the intercepted encrypted signature.
- Moreover, This form of attack known as a meet-in-the-middle-attack.
- A number of researchers have proposed refinements intended to strengthen the basic block chaining approach. For example, Davies and Price describe the variation:
𝐻𝑖 = 𝐸(𝑀𝑖, 𝐻𝑖−1)⨁𝐻𝑖−1
- Another variation, proposed is
𝐻𝑖 = 𝐸(𝐻𝑖−1,𝑀𝑖)⨁𝑀𝑖
- However, both of these schemes have been shown to be vulnerable to a variety of attacks.