# Related Key Attack Cryptanalysis Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

We present new related-key attacks on the block ciphers 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA. Differential related-key attacks allow both keys and plaintexts to be chosen with specific differences. Our attacks build on the original work, showing how to adapt the general attack to deal with the difficulties of the individual algorithms. We also give specific design principles to protect against these attacks.

## Introduction

Related-key cryptanalysis assumes that the attacker learns the encryption of certain plaintexts not only under the original (unknown) key K, but also under some derived keys K0 = f(K). In a chosen-related-key attack, the attacker specifies how the key is to be changed; known-related-key attacks are those where the key difference is known, but cannot be chosen by the attacker. We emphasize that the attacker knows or chooses the relationship between keys, not the actual key values. These techniques have been developed in.

Related-key cryptanalysis is a practical attack on key-exchange protocols that do not guarantee key-integrity-an attacker may be able to flip bits in the key without knowing the key-and key-update protocols that update keys using a known function: e.g., K, K + 1, K + 2, etc. Related-key attacks were also used against rotor machines: operators sometimes set rotors incorrectly. If the operator then corrected the rotor positions and retransmitted the same plaintext, an adversary would have a single plaintext encrypted in two related keys . Hash functions built from block ciphers can also be vulnerable to a related-key attack against the block cipher.

## New Differential Related-Key Attacks

## 3-WAY

3-WAY is an 11-round cipher on 96-bit blocks. Ignoring trivialities such as the input and output transformations, the 3-WAY round function F (x) has an equivalent representation as:

y = N(x); z = L(y); F (x) = z âŠ• K âŠ• Ci

Where N is a fixed nonlinear layer built out of 32 parallel 3-bit permutation S-boxes, L is a fixed linear function, K is the 96-bit master key, and Ci is a fixed, round-dependent public constant.

3-WAY is vulnerable to a simple related-key differential attack. It is trivial to find a differential characteristic for one S-box with probability 1/4, so we can construct a characteristic âˆ† x â†’ âˆ† y with probability 1=4 for the non-linear layer N by using only one active S-box. By linearity we see that âˆ† yâ†’ âˆ† z = L(âˆ† y) with probability 1 under the linear layer L. If we pick âˆ†K = âˆ† xâŠ• âˆ† z, then âˆ† xâ†’ âˆ† x by F with probability 1/4, which is a one-round iterative differential characteristic. In this way we can derive a 9-round characteristic with probability 2-18 to cover rounds 1-9, and apply a 2R analysis to the last two rounds. This breaks 3-WAY with one related-key query and about 222 chosen plaintexts.

## DES-X

DES-X is a DES variant proposed by Rivest to strengthen DES against exhaustive attacks. The DES-X encryption of P with key (K1, K2, K3) is simply

C = K1âŠ•DESK2 (K3âŠ•P)

Where K3 is the pre-whitening key and K1 is the post-whitening key. DES-X has many complementation properties. Furthermore, every DES-X key (K1; K2; K3) has another equivalent key (K1, K2, K3). Therefore, DES-X cannot be used in a Davies-Meyer-like hash function construction.

This complementation property leads to an attack which requires roughly 256+64 n trial encryptions when 2n chosen plaintexts are available. Note that Kilian and Rogaway have proven that this attack is theoretically approximately optimal when DES is viewed as a black box, so any better (non-related-key) attack would have to take advantage of the internal structure of DES. However, their proof doesn't deal with related-key attacks. We give a related-key differential attack on DES-X, using key differences modulo 264 and plaintext differences modulo 2. The attack requires 64 chosen key relations to recover the key, with one plaintext encrypted under each new key.

We start with a simple intuition. Suppose we have some unknown number Z. We are allowed to add any number we like modulo 264, and then XOR it with another number of our choosing. We are told whether or not the result of our calculation is equal to Z. Thus, we choose T and U, and test whether

(Z + T mod 264) âŠ• U = Z

It is clear that we can learn the value of Z with enough queries. This is essentially the position we are in with DES-X. We can add T to K1, and XOR U into our plaintext block or vice-versa. If the resulting cipher text block is the same as the cipher text that results from encrypting the unaltered plaintext block under the unaltered DES-X key, then we can restrict the list of possible values for K1. With enough such restrictions, we recover all of K1 except for its high-order bit. This then allows attacks against the remainder of DES-X.

The simplest version of this attack uses T and U values each with the same single bit on. For each bit except the high-order bit, we try a T; U pair with the same bit on. If this results in the same cipher text as resulted when T = U = 0, then we learn that that bit in K1 was a zero. If it results in a different cipher text, then we learn that that bit in K1 was a one.

Some have suggested using a DES-X variant which replaces the XOR pre- and post-whitening steps by addition modulo 264:

C = K1 + DESK2 (K3 + P).

From the discussion above, it should be clear that this would be vulnerable to a related-key attack very similar to the one that works against regular DES-X. recommends a method of deriving DES-X keys from a single starting key, using SHA-1. This method seems to defend against related-key attacks.

## CAST

CAST is a Feistel cipher whose key schedule uses nonlinear S-boxes.1 The key schedule for 8 round CAST with a 64 bit master key is as follows:

(k1, k2, , , , , , k8) = Master Key

(k'1, k'2, k'3, k'4) = (k1, k2, k3, k4) âŠ• S5 [k5] âŠ• S6 [k7]

(k'5, k'6, k'7, k'8) = (k5, k6, k7, k8) S5[k'2] âŠ•S6[k'4]

K1= (k1,k2) K2= (k3, k4) K3= (k5, k6) K4= (k7, k8)

K5= (k'4, k'3) K6= (k'2, k'1) K7= (k'8, k'7) K8 = (k'6, k'5)

(Kr,1 , Kr,2) = Kr r = 1,â€¦.., 8

skr = S5[Kr,1] âŠ• S6[Kr,2] r = 1,â€¦â€¦, 8.

where S5 and S6 are different 8-bit to 32-bit S-boxes. The r-th round sub key, skr, is XORed into the input of the F function as is conventional for Feistel ciphers.

CAST is an interesting example of a cipher designed to resist Biham's rotational related-key cryptanalysis, but not differential related-key cryptanalysis. We apply a key-difference to the master key which changes only the byte k1; this will lead to a difference only in round sub keys sk1 and sk6. When âˆ† k1 is known, there are only 256 possible differences for âˆ†sk1; by encrypting 216 chosen plain-texts under each key, we can ensure that the first round is bypassed for some pair. Cover rounds 2-5 with the trivial differential characteristic of probability 1, and use a 2R attack. Note that sk7 and sk8 have only 32 bits of entropy in total, so we can try all 232 possibilities for them, decrypt the last two rounds, and recognize correct guesses by 32 zero bits in the block difference. We recover the rest of the key with 216 offline guesses by auxiliary techniques. In the end, we can recover the entire CAST master key with a total of about 217 chosen plaintexts, one related-key query, and 248 offline computations.

## Biham-DES

Biham and Biryukov have suggested strengthening DES against exhaustive at-tacks by using extra key bits to modify the F -function slightly. One of their modifications uses 5 key bits to select from 32 possible reorderings of the 8 DES S-boxes. We consider related keys which differ only in those 5 bits, and we apply related-key differential cryptanalysis. Specifically, suppose one key uses ordering 15642738 and another uses ordering 75642138 (both are from the 32 suggested reorderings listed in). The only difference between the two F -functions is that S-boxes 1 and 7 have been swapped. Observe that:

Prx (S1[x] âŠ• S7[x âŠ• 2] = 0) = 14/64:

The input differential 2 appears only in the middle input bits of the S-box, and will not spread to neighboring S-boxes. Hence, we can construct a one-round characteristic with probability (14/64)2.

This leads to a 13-round iterative characteristic with probability ( 14/64 )12 = 2-26. The differential techniques of Biham and Shamir will break Biham-DES with 227 chosen plaintexts when this special related-key pair is available.

If two related keys allow the above attack (i.e. differ only in the key orderings as defined above), we call them partners. There is a 161 chance that a randomly chosen key will have a partner; if it does, this can be detected with one related-key probe. Furthermore, we can always obtain one useful pair of related-key partners from any starting key after 32 related-key queries. Therefore, when using Biham-DES with the 32 recommended DES S-box reorderings, we have a 1/61 probability of success when 227 chosen plaintexts and one related-key query are available; success is nearly guaranteed with 231 chosen plaintexts and 32 related-key queries.

Biham and Biryukov also mention the possibility of using 215 reorderings of the s3-DES S-boxes. They don't present the recommended reorderings, so it is impossible to present any specific results. Still, in general, increasing the number of reorderings gives the cryptanalyst more degrees of freedom to find more efficient attacks. Therefore, using this variant is not expected to increase security against our attack.

## TEA

TEA is a Feistel block cipher with a 128-bit master key, K[0,3], and a simple key schedule: odd rounds use K[0,l] as the round sub key, and even rounds use K[2,3]. Two rounds of TEA applied to the block Yi; Zi consists of:

c = c +Î´ Yi+1 = Yi + F (Zi, K[0, 1], c) Zi+1 = Zi + F (Yi+1, K[2, 3], c) where the round function F is defined by

F (z, K[I, j], c) = (SL4(z) + K[i]) âŠ• (z + c) (SR5(z) + K[j]):

Here SL4(z) denotes the result of shifting (not rotating) z to the left by 4 bits, and SR. (.) denotes a shift to the right. In this description, c is a value which perturbs the F function so that it is different in each round.4 Before each cycle, c is incremented by a fixed constant Î´ =[b(âˆš5-1)231]; c is initially 0. The designers of TEA mention that 32 Feistel rounds (i.e. 16 cycles) may be enough, though they recommend using 64 rounds (32 cycles).

TEA admits several related-key attacks which arise from the severe simplicity of its key schedule.

Attack One For a differential related-key attack, consider the effect of simultaneously flipping bit 30 (the next most significant bit) of K[2] and K[3]. With probability nearly 1/2 , the output of the F function in the even rounds will remain the same. This immediately yields a 2-round iterative differential characteristic with probability 1/2 , and thus a 60-round characteristic with probability 2 -30. Our analysis indicates that a 4R differential related-key attack can break 64-round (32-cycle) TEA with one related-key query and about 234 chosen plaintexts. This is only one of several of this type of characteristic.

Attack Two The second differential related-key attack is very similar in spirit to the first. We request the encryption of (Y,Z) under key K[0..3] and the encryption of (Y,ZâŠ• 231) under key K [0..3] = K[0..3] (0, 231 âŠ• 226, 0, 0). Examining the three terms of F (Z, K[0, 1], c) when bit 31 of Z is flipped along with bits 26 and 31 of K[1], we see

SL4(Z) + K[0] Neither change has any effect.

Z + c The high bit is always changed.

SR5(Z) + K[1] Half the time, only the high bit is changed.

This gives us a one-cycle (2-round) iterative differential characteristic with probability 12 , when we can choose one key difference. We can pass 30 rounds with probability 2-30.

Attack Three The third attack is complicated. Therefore, we briefly point out the approach and intuition behind the attack, leaving the technical details of the full attack to be described in Appendix A. We write Pj to represent the value of the block after j rounds of encryption, and write Kj to represent the round sub key value used to compute Pj+1 from Pj, the block is enciphered with a round function F as Pj+1 = F (Kj, Pj), where (P0; P64) represents a plaintext/ciphertext pair for 64-round TEA.

In Biham's standard key rotation attack [Bih94], we succeed when

K'j = Kj+1 P'j = Pj+1 j = 0,â€¦â€¦, 63:

This condition is achieved by choosing suitable related keys K, K' and searching over P0, P'0 to find a pair with P'0 = P1, the birthday paradox ensures that a match will occur with a reasonable number of known texts. Note that

P'j+1 = F (K'j; P'j) = F (Kj+1, Pj+1) = Pj+2 (1)

for all j, so by induction we see that a match P'0 = P1 will propagate down to the ciphertexts, where we can recognize it.

Our extended attack combines the ideas of both rotational and differential related-key attacks. We require that

K'j = Kj+1 + âˆ† Kj+1 P'j = Pj+1 + âˆ†Pj+1 j = 1; : : : ; 63:

In the extended attack, we need a generalization of (1) to hold

P'j+1 = F (K'j, P'j) = F (Kj+1 +âˆ† Kj+1, Pj+1 + âˆ† Pj+1)

= F (Kj+1, Pj+1) + âˆ†Pj+2 = Pj+2 + âˆ†Pj+2

with significant probability pj+2; this generalization has a strong differential feel to it. Suppose the 63-round differential related-key characteristic that is patched into the rotational attack has probability p = âˆj pj. In the extended attack, we search for about 1/p matches P'Â0 = P0 + âˆ†P1 with the birthday paradox. Each such match has a probability p of leading to a right pair that is recognizable from the known ciphertexts, so we expect to see one right pair.

Specifically, in our third attack on TEA, we take âˆ†Pj+1 to be a fixed constant (Î´,0) independent of j, set Kj = Kj mod 2, and choose âˆ†K 0,1 to maximize p. We can thus obtain a full 63-round characteristic of probability p = ( 25/32 )31 â‰ˆ2-11 by repeating a 2-round iterative characteristic many times.

This improved attack combines ideas from both Biham's key-rotation attack and differential related-key cryptanalysis to break TEA with just 223 chosen plaintexts and one related-key query.

## Prudent Rules of Thumb for Key-Schedule Design

There is much overlap between the requirements for strong key schedules and cryptographic hash functions. Firstly, key schedules should be hard to invert| given some of the round keys, it should be difficult to recover any new information about other bits of the key and hash functions are supposed to be one-way. Secondly, to avoid equivalent keys, key schedules should possess some form of collision-freedom; collision-freedom is a standard hash function property as well. Finally, it should not be possible to produce controlled changes in the round keys. The key schedules of Blowfish and SEAL were designed according to this principle.

One should typically avoid generating round subkeys as a ( fixed, public) linear transformation of the seed. While some cryptosystems have successfully incorporated linear key schedules (e.g. DES), designing this type of key schedule appears to be a subtle and difficult task. Many ciphers' linear key schedules have been shown to be quite weak: we have cryptanalyzed TEA, 3-WAY, and GOST , and others have cryptanalyzed LOKI , LOKI91,Lucifer , and SAFER.

To protect against the known related-key attacks, we propose several attack-oriented design goals. To avoid the "subkey rotation" attacks [Bih94], round subkeys should be generated differently, so that each key bit affects nearly every round, but not always in the same way. Key schedules should be specifically de-signed to resist differential related-key attacks. And, when related-key queries are cheap, the master key should be long enough to avoid generic black box attacks, as the key length is effectively halved under these attacks.

Avoid dead spots; ensure that every key bit is about equally powerful in terms of its effect on the round keys. Beware of equivalent representations, for they can expose new avenues of attack to an adversary. Our analysis of 3-WAY bears witness to this recommendation.

Avoid independent round subkeys. It has commonly been assumed that a cipher's key length (and strength) can be increased by allowing round keys to be specified independently, but we have shown that this dramatically lowers the cipher's resistance to related-key attacks. In general, when independent

round subkeys are in use, the strength of a cipher against related-key attacks will be approximately proportional to the strength of one round standing on its own. Additionally, avoid multiple encryption with independent keys; a construction like is much more secure.

And finally, protocol designers should be aware of related-key attacks. Key-exchange protocols should exchange a short master key rather than exchanging expanded keys. Design tamper-resistant devices so that it is not possible to change the subkeys without such changes being detected.