Differential Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 181

7.16.1 Related-Key Attack on GOST
Sometimes the related-key attack can be carried out with a normal differential attack. In Reference [8], the au-
thors exploit a key scheduling weakness in the GOST 28147-89 cipher, a Soviet cryptosystem [6]. The key
schedule they specify takes a 256-bit key and breaks it into eight 32-bit subkeys, K 0 , ... , K 7 , generating subkeys
(sk i ) for use in the 32 rounds by

We can use this key schedule in a clever manner.
Say that we have an interesting differential for the plaintext on this algorithm, Ω. Since the keys (in most
ciphers, actually) are directly XORed in at some point, we should be able to choose a related key to the original
that will counteract the Ω for the first round. This could be done simply by taking K 0 = K 0 ⊕ Δ, for some ap-
propriate value of Δ.
Note that the subkeys for the next seven rounds ( i = 1, ... , 7) don't rely on K 0 . This means that the difference
for each of these rounds from the original plaintext is zero! The differences will then start with the eighth round.
In essence, we skipped the first eight rounds of the cipher and can instead mount a much simpler 24-round at-
tack.

7.16.2 Related-Key Attack on 3DES
A very interesting use of a related-key attack is on 3DES, using three separate keys [8]. We recall that 3DES
uses the standard DES encryption function three times in succession, each time with a different key. (The de-
cryption, naturally, decrypts with the keys in the exact opposite fashion.) This allows us to virtually triple the
total key space, while not changing the underlying structure of DES at all.
Assume that we have a DES encryption of a plaintext P to a ciphertext C , using keys K a , K b , and K c as fol-
lows. Let the E -function represent DES encryption, and the D -function represent DES decryption. Then,

Now, assume that we have a related key, with . We select to have the original C decrypted to

give us a new plaintext, P ′, or

Note that the decryption to P is

That is, the decryption to P and P ′ differs only in the last step, allowing us to write

We can then treat this as a known-plaintext attack and attack it via an exhaustive search, for 2 56 work, deriving
K a in the process.
Once we have K a , we can then obtain allowing us to look at it, along with C , as a known plain-
text-ciphertext pairofdoubleDES.WemayrecallthatdoubleDESissusceptibletoameet-in-the-middle attack
with 2 57 work.
With a related-key attack, we have then broken 3DES to be no better than normal DES. Note, however, that
this works only when all three keys are independent. The most common form of 3DES, with the first and third