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

Constructing this polynomial will not immediately yield the key, however. Given sufficient pairs, it can ac-
tually yield a polynomial that emulates the encryption function: It produces valid ciphertexts from given plain-
texts.
To actually get key bits, we instead try to find a polynomial for the plaintext and the next-to-last round of
ciphertext. Similar to the way we have done before, we decrypt some portion of the last round by guessing
the last round key. When we have done this for a sufficient number of plaintext-ciphertext pairs, we will have
enough plaintext and intermediate ciphertext pairs to attempt to construct a polynomial. We check the polyno-
mial against another value that wasn't used in the construction to test it. If the polynomial produces the correct
result, then we have guessed the key bits.
Theinterpolating attack isabitacademic innature,butitprovidesaninteresting avenueofattack. Forcertain
ciphers that provably secure against traditional differential cryptanalysis, the interpolating attack produces a
very reasonable method for deriving the key, as shown in Reference [7].
7.16 Related-Key Attack
Finally, we want to look at a completely different way of viewing differential cryptanalysis. In the previous
sections, we analyzed ciphers by examining how differences in the plaintexts and ciphertexts propagate to de-
termine key bits. This was accomplished through the use of chosen-plaintext attacks.
One avenue unexplored is that of attacking the key itself. After all, we have considered the key to be out-of-
bounds for modifications. It hasn't been part of our model to modify it, since it is what we are trying to derive.
Furthermore, doesn't the ability to change the key automatically mean that we know the value of it?
Actually, no. As Kelsey, Schneier, and Wagner [8] point out, many key exchange protocols leave themselves
vulnerable in two ways. The first way is that they do not check the integrity of the key before they start using
it to encrypt plaintext into ciphertext encrypted — meaning that, immediately after exchanging the keys, they
immediately encrypt some plaintext and send the ciphertext to the other party.
Secondly, many key exchange protocols use simple XOR structures to pass along the key. For example, as-
sume that there is a pre-shared secret key, K m . A new session key may be generated by sending a message:
This two-part message will hide the actual value of the key. However, if we have the ability to modify the mes-
sage in transit, then we could corrupt the key the first time around with a known difference. Now, one party will
send a message encrypted with one key, and the other will send a message encrypted with the key XORed with
a fixed, chosen difference.
Typically, we also address this attack as a chosen plaintext, so that both parties would attempt to encrypt the
same plaintext with the XORed keys.
Owing to the difficulty of achieving such an attack, this scenario has often been disregarded. However, the
above key-exchange scenario should provide some conjecture that the above attack is very possible.
Naturally,theXORdifference will havetobesignificant, usually toexploit aweakness inthekey-scheduling
algorithm. Attacks that rely on such weaknesses are called related-key attacks , since the attack relies on so-
called “related keys” in the schedule. Indeed, many ciphers use schedules in which key bits are copied or have
a linear relationship to many other bits.