 Chaining attacks

Chaining attacks are those which are based on the iterative nature of hash functions and, in particular, the use of chaining variables. These focus on the compression function / rather than the overall hash function h, and may be further classified as below. An example for context is first given.

9.100 Example (chaining attack) Consider a (candidate) collision resistant iterative hash function h producing a 128-bit hash-result, with a compression function / taking as inputs a 512-bit message block and 128-bit chaining variable Hi (ff0 = /V) and producing output Hi+1 = For a fixed 10-block message x (640 bytes), consider H = h(x).

Suppose one picks any one of the 10 blocks, and wishes to replace it with another block without affecting the hash H. If h behaves like a random mapping, the number of such 512-bit blocks is approximately 2512/2128 = 2384. Any efficient method for finding any one of these 2384 blocks distinct from the original constitutes an attack on h. The challenge is that such blocks are a sparse subset of all possible blocks, about 1 in 2128. □

(i) Correcting-block chaining attacks

Using the example above for context, one could attempt to (totally) replace a message x with a new message x', such that h(x) = h(x'), by using a single unconstrained “correcting” block in x', designated ahead of time, to be determined later such that it produces a chaining value which results in the overall hash being equal to target value h(x). Such a correcting block attack can be used to find both preimages and collisions. If the unconstrained block is the first (last) block in the message, it is called a correcting first (last) block attack. These attacks may be precluded by requiring per-block redundancy, but this results in an undesirable bandwidth penalty. Example 9.101 illustrates a correcting first block attack. The extension of Yuval’s birthday attack (page 369), with message alterations restricted to the last block of candidate messages, resembles a correcting last block attack applied simultaneously to two messages, seeking a (birthday) collision rather than a fixed overall target hash-value.

• 9.101 Example (correcting block attack on CBC cipher mode) The CBC mode of encryption with non-secret key (ff0 = IV II, = Ek{Hi-i®Xi)) is unsuitable as an MDC algorithm, because it fails to be one-way - the compression function is reversible when the encryption key is known. A message x of unconstrained length (say t blocks) can be constructed to have any specified target hash-value Я as follows. Let x'2,... x be t - 1 blocks chosen freely. Set H{ <- II, then for / from / to 1 compute II'_x <- Dk{H[)®x. Finally, compute arj <— Dk{H[)®IV. Then, for x = xx2 ... ay, h(x') = H and all but block x\$ (which will appear random) can be freely chosen by an adversary; even this minor drawback can be partially addressed by a meet-in-the-middle strategy (see below). Analogous remarks apply to the CFB mode. □
• (ii) Meet-in-the-middle chaining attacks

These are birthday attacks similar to Yuval’s (and which can be made essentially memoryless) but which seek collisions on intermediate results (i.e., chaining variables) rather than the overall hash-result. When applicable, they allow (unlike Yuval’s attack) one to find a message with a pre-specified hash-result, for either a 2nd-preimage or a collision. An attack point is identified between blocks of a candidate (fraudulent) message. Variations of the blocks preceding and succeeding this point are generated. The variations are hashed forward from the algorithm-specified IV (computing H, = f(H,-i,Xi) as usual) and backward from the target final hash-result (computing Hi = f~1(Hi+i,xi+i) for some Hi+1, xi+i, ideally for a:i+1 chosen by the adversary), seeking a collision in the chaining variable Hi at the attack point. For the attack to work, the attacker must be able to efficiently go backwards through the chain (certainly moreso than by brute force - e.g., see Example 9.102), i.e., mvert the compression function in the following manner: given a value Hi+1, findapair (H,,xi+1) such that f(Hi,xi+1) = Hi+X.

• 9.102 Example (meet-in-the-middle attack on invertible key chaining modes) Chaining modes which allow easily derived stage keys result in reversible compression functions unsuitable for use in MDCs due to lack of one-wayness (cf. Example 9.101). An example of such invertible key chaining methods is Bitzer’s scheme: ff0 = IV, Hi = 1(Н,-Хх) = Ek, (H,_ i) where = xx®s(Ht_ i) and s(H, L) is a function mapping chaining variables to the key space. For exposition, let s be the identity function. This compression function is unsuitable because it falls to a meet-in-the-middle attack as outlined above. The ability to move backwards through chaining variables, as required by such an attack, is possible here with the chaining variable H, computed from H,+ as follows. Choose a fixed value ki+i <- к, compute H, <— DHH,.. ), then choose as message block x,. ) <- k®Ht.
• (iii) Fixed-point chaining attacks

Afixedpoint of a compression function is a pair (Я,_1,Жг) such that /(Яг_1,ж,) = H,-X. For such a pair of message block and chaining value, the overall hash on a message is unchanged upon insertion of an arbitrary number of identical blocks xt at the chain point at which that chaining value arises. Such attacks are thus of concern if it can be arranged that the chaining variable has a value for which a fixed point is known. This includes the following cases: if fixed points can be found and it can be easily arranged that the chaining variable take on a specific value; or if for arbitrary chaining values Я,_i, blocks xx can be found which result in fixed-points. Fixed points allow 2nd-preimages and collisions to be produced; their effect can be countered by inclusion of a trailing length-block (Algorithm 9.26).

(iv) Differential chaining attacks

Differential cryptanalysis has proven to be a powerful tool for the cryptanalysis of not only block ciphers but also of hash functions (including MACs). For multi-round block ciphers this attack method examines input differences (XORs) to round functions and the corresponding output differences, searching for statistical anomalies. For hash functions, the examination is of input differences to compression functions and the corresponding output differences; a collision corresponds to an output difference of zero.