Differential Cryptanalysis on SDES

Hiu Nam Cheung

CS265

April 4, 2004

Differential Cryptanalysis on SDES

SDES Overview

SDES is a simplified version of DES with 16 bits block and key sizes, 12 bits sub-key, 4 rounds, 2 S-boxes (left and right S-box), and a round function F such that F(right half, sub-key) equals S-box(expand(right half) Å sub-key). Since SDES is linear except S-boxes, we can then focus our attack on the S-boxes.

General Idea: Chosen Plaintext Attack

Recall that a S-box has 6 bits input and 4 bits output. For any 6 bits value X, there are 64 possible distinct value pairs Y and Z such that their difference is X. If a person feeds each such Y and Z into a S-box and studies the outcomes, he might find some clues on the unknown key since the output distribution has biases.

In SDES, consider two 6 bits values Y and Z, differ only at the second bit (001000), then outcomes of the right S-box will differ by (0010) with probability 3/4. In another words, if Y and Z are input for the right S-box and Y Å Z = 001000, then with 3/4 chance the output difference will equal to 0010.

However, attacker does not have direct access to S-boxes and there are multiple rounds. In addition, each round before the right half goes into S-boxes, it first has to be expanded to 12 bits and xor with the sub-key.

Extend Attack To One And More Rounds

Suppose r represents original 8 bits and x represents resulting 12 bits, the expansion permutation will look like:

x0x1x2x3x4x5 x6x7x8x9x10x11 = r4r7r2r1r5r7 r0r2r6r5r0r3

As one might see, if two 8 bits values Y and Z differ at the 6-bit (0000 0010), then the expanded results will differ by (000000 001000). Since the first six expanded result bits are identical, inputting them into any S-box will get the same output. Meanwhile, the last six bits of the result have a difference of (001000), thus outputs from the right S-box will differ by (0010) with probability 3/4. As a result, if a person feeds such expanded result into S-boxes, outputs will differ by (0000 0010) with probability 3/4.

Recall that the round function F = S-box(expand(right half) Å sub-key), and anything xor with the same thing twice will cancel out the effect. Thus, if inputs Y and Z have a difference of (0000 0010), then F(Y, sub-key) Å F(Z, sub-key) will still equal to (0000 0010) with probability 3/4, regardless of what the sub-key is.

Consider all facts stated above, input difference is the same as output difference with probability 3/4, and attacker can then chain through multiple rounds.

Look Inside The Encryption Process

Recall that SDES has block size of 16 bits. Suppose there are two plaintext blocks P1 and P2, we can minimize the number of active S-boxes by selecting a P2 such that it is identical to P1 except the second last bit. In another words, choose P1 and P2 such that P1 Å P2 = 0x0002.

Difference chain through multiple rounds:

Note: K is the sub-key, and K1 means the sub-key of round one

Source: Dr. Mark Stamp’s cs265 course note

Let’s examine the first round in detail. Since SDES is a Feistel cipher, plaintext is divided into left and right halves, P = (L, R). The old right half is the new left half, and the old left half Å F(old right, sub-key) is the new right half. After the first round, the two new left halves’ difference is (0000 0010) since they are the old right halves, and we choose P1 and P2 with 0x0002 difference. For the two new right halves, since both L0 are identical, output difference will only depend on F(R0, K1). Recall that if Y Å Z = (0000 0010), then F(Y, sub-key) Å F(Z, sub-key) will also equal to (0000 0010) with probability 3/4. Therefore, two new right halves will differ by (0000 0010), and the complete output will have a difference of 0x0202. We will repeat the same process until we reach the fourth round, and our final output will have a difference of 0x0202 with probability down to (3/4)3.

Algorithm To Find The Rightmost 6 Bits Of K4

By looking at the pervious example, we know that if P1 Å P2 = 0x0002, then C1 Å C2 = 0x0202 and

R4 = L3 Å F(R3, K4). In order to solve the equation, we need to know L3 and R3 but we only know L4 and R4. Since old right half is new left half in Feistel cipher, we can replace R3 with L4 and get a new equation R4 = L3 Å F(L4, K4). In addition, we rearrange the equation to L3 = R4 Å F(L4, K4).

Base on the fact that (L3, R3) Å (L3, R3) = 0x0002, we know both L3 are identical. Therefore, if we can find any key K that make R4 Å F(L4, K) == R4 Å F(L4, K) always hold true, we are likely to find the correct sub-key K4.

Since we choose P1 and P2 only differ at the 14-bit, we can focus only on the right most 4 bits of R4 and the rightmost 6 bits of K4. Since 26 = 64, there are 64 possible keys to try. We can count the number of times each such key satisfies the condition R4 Å F(L4, K) = R4 Å F(L4, K), then all keys with maximum count are possible partial sub-keys.

Consider the fact that the rightmost 6 bits of K4 is k13k14k15k9k10k11 of the original key, we know this 6 bits group is in the set of all possible partial sub-keys.

Conclusion

Notice differential attack on SDES does not guarantee a solution. Although differential attack only suggests the k13k14k15k9k10k11 bit of the correct key K, attacker can still use this information to take advantage and get a reasonable guess on K.