Monday, October 24, 2016

Why cannot S-box of DES cipher be linear?

We cannot specify any S-box in DES cipher. One of the rules to choice of S-box is that, it cannot be linear. How do we understand it? Below is my explanation, but I'm not sure it is correct.

The Stanford on-line course, Cryptography I, describes that, if S-box is chosen as linear, the DES cipher would be linear.

DES(k, m) = B x |m  |= c    (statement 1)
                |k1 |
                |k2 |
                |.  |
                |.  |
                |.  |
                |k16|

where:
|m| = |c| = 64 (bits)
|ki| = 48 (bits)
B is a 64x832 matrix.

The course describes that, "You just need 832 input output pairs, and you'll be able recover the entire secret key." How to explain the description? We can use a simple example:

Lets
B is 2 x 4 matrix.
|m| = |c| = |k| = 2 (bits)

We transform the statement 1 as below.

|b1 b2 b3 b4| x |m1| = |c1|
|b5 b6 b7 b8|   |m2|   |c2|
                |k1|
                |k2|

We give the below statement.

b1m1 xor b2m2 xor b3k1 xor b4k2 = c1    (statement 2)
b5m1 xor b6m2 xor b7k1 xor b8k2 = c2    (statement 3) 

We assume that, we don't know any b and any k, but we know the input m and output c.

For statement 2, the number of unknown variables is 4. They are,
b1, b2, b3k1, b4k2.

For statement 3, the number of unknown variables is 4. They are,
b5, b6, b7k1, b8k2.

Total number of unknown variables is 8. Therefore we need 8 equations to derive all values of b and k.

Because,

|m| = |c| = 2

Each input/output pair has 2 equations. That is why we need 8/2 = 4 pairs of  input/output to derive all values of b and k.

-Count

No comments:

Post a Comment