Consider a variant of DES algorithm, called DES-WEAK. In DES-WEAK,
there is no permutation P in a round and all the S-boxes are replaced. The new S-boxes are all
identical and defined as follows. Let b0, . . ., b5 represent the six input bits to an S-box and a0,
a1, a2, and a3 the four output bits. Then, a0 = b3 ⊕ b0b1b5, a1 = b0 ⊕ b1b3b5, a2 = b1 ⊕ b2b3b5,
and a3 = b2 ⊕ b4 ⊕ b1b3b5.
• Design an algorithm to break 16-round DES-WEAK as efficiently as possible.
We have approached this design like the way I have mentioned below..
We use differential cryptanalysis to recover the key. Consider the
differ- ential 000100 going into the S-box S2. Let one of the two
inputs with the given differential
be b0b1b2b3b4b5 and the corresponding output be a0a1a2a3. Let the
output for second input (= b0b1b2b2(b3 ⊕ 1)b4b5) be a 0 0 a 0 1 a 0 2
a 0 3 . Then, a0 ⊕ a 0 0 = 1, a1 ⊕ a 0 1 = b1b5, a2 ⊕ a 0 2 = b2b5
and a3 ⊕ a 0 3 = b1b5. Hence the output differential is 1000 on the
given input differential with
probability 1 2 + 1 2 · 1 4 = 5 8 (either b5 is zero or b5 is one and
both b1, b2 are zero).
The problem with this differential output is that, in the next round,
after expansion, two S-boxes will get non-zero differential. Assume
that, in the first round, the differential into S1 is 000000 and the
left half differential is also all zeroes. Then, in the next round,
differential into S1 would be 000001 and into S2 would be 010000. Let
us analyze both. First consider S1. With the same notation for first
input and the two outputs (now the second input is b0b1b2b3b4(b5 ⊕
1)), we get a0 ⊕ a 0 0 = b0b1, a1 ⊕ a 0 1 = b1b3, a2 ⊕ a 0 2 = b2b3
and a3 ⊕ a 0 3 = b1b3. Hence the output
diffrential is 0000 with probability 1 2 · 3 4 + 1 2 · 1 4 = 1 2
(either b3 is zero and one of b0, b1 is zero or
b3 is one and both b1, b2 are zero). Consider S2. Now the second input
is b0(b1 ⊕ 1)b2b3b4b5, and so we get a0 ⊕ a 0 0 = b0b5,
a1 ⊕ a 0 1 = b3b5, a2 ⊕ a 0 2 = 1 and a3 ⊕ a 0 3 = b3b5. Hence the
output diffrential is 0010 with
probability 1 2 + 1 2 · 1 4 = 5 8 (either b5 is zero or b5 is one and
both b0, b3 are zero). In the next round, after applying expansion,
the differential into these two S-boxes becomes 000000 000100 which is
exactly the same differential that went into the first round into
these two! Using this analysis, we can now derive a charecteristic
with high probability as follows. Let Z stand for zero differential on
32 bits, P stand for differential 0000 0010 0000 0000 0000 0000 0000
0000
, and Pˆ stand for differential
0000 1000 0000 0000 0000 0000 0000 0000
. The above analysis shows the following transformation sequence of
differentials: [P, Z] p=1 −−→ [Z, P] p= 5 8 −−−→ [P, Pˆ] p= 5 16 −−−→
[P , Z ˆ ] p=1 −−→ [Z, Pˆ] p= 5 16 −−−→ [P , P ˆ ] p= 5 8 −−−→ [P, Z].
The overall probability of the above charecteristic is 5 4 2 14 .
Iterating this once again, and then taking only the first two rounds
of this, we get a fourteen round charecteristic with probability 5 9 2
31 ≈ 9 × 10−4
. Hence using a few thousand plaintext pairs, DES-WEAK can be broken.
Now we have a new challenge and are stuck in it. The below mentioned design is a slight modification of the above mentioned question that we have worked upon. The design goes as follows..
Consider a variant of DES algorithm in which all the S-boxes are
replaced. The new S-boxes are all identical and defined as follows.
Let b1, b2, · · · , b6 represent the six input bits to an S-box. Its
output is b1 ⊕(b2 · b3 · b4), (b3 · b4 · b5) ⊕ b6, b1 ⊕ (b4 · b5 ·
b2), (b5 · b2 · b3) ⊕ b6. Here ‘⊕’ is bitwise XOR operation, and ‘·’
is bitwise multiplication. Design an algorithm to break 16-round DES
with new S-boxes as efficiently as possible.
In this design the permutation operation is still present and S-box output is different. So how can we approach this like the one we have done above, given that the Permutation Box is still there.
