SDES

Rick Perry
24 January 2002

Table of Contents

1. SDES - Simplified DES

audio

Similar properties and structure but with much smaller parameters than DES.

As in DES, the initial and final permutations, which are fixed and independent of the key, provide no real security benefit, but make the algorithm slow if implemented in software.

2. SDES Key Schedule

audio

The 10-bit key is transformed into two 8-bit sub-keys K1 and K2.

Example: 

P10 = { 3, 5, 2, 7, 4, 10, 1, 9, 8, 6}

P8 = { 6, 3, 7, 4, 8, 5, 10, 9}

K =     10100 00010

P10     10000 01100

LS-1    00001 11000  ->  P8  ->  K1 = 1010 0100

LS-2    00100 00011  ->  P8  ->  K2 = 0100 0011

3. SDES Mangler Function

audio

In fK the rightmost 4 bits are passed through unchanged, and the leftmost 4 bits are "mangled" by the non-invertible function F: 

fK(L,R) = L XOR F(R,Ki), R    -- encrypt or decrypt

E/P = { 4, 1, 2, 3, 2, 3, 4, 1}

P4 = { 2, 4, 3, 1}

S0 =  1 0 3 2     S1 =  0 1 2 3
      3 2 1 0           2 0 1 3
      0 2 1 3           3 0 1 0
      3 1 3 2           2 1 0 3

n1n2n3n4  ->  Si[n1n4][n2n3]
Example: 
R =  1010

E/P  0101 0101

K1 = 1010 0100

XOR  1111 0001

S0[11][11] -> 10    S1[01][00] -> 10

     1010

P4   0011

4. Properties of XOR and bitwise complement

audio

  A   B    A XOR B   A' XOR B   A' XOR B'   (A XOR B)'

  0   0       0          1          0           1

  0   1       1          0          1           0

  1   0       1          0          1           0

  1   1       0          1          0           1

From the truth-table:

  A' XOR B  == (A XOR B)'

  A' XOR B' ==  A XOR B

5. (S)DES input/key complement property

audio

P3.10 (a)
Using input X' and key K', both inputs to the first XOR are complemented, therefore the XOR output, and the result of F, will be the same as using uncomplemented X and K

The second XOR has inputs L' and F, therefore its output is complemented.

P3.10 (b)
Due to the (S)DES complement property, we can get two encryptions for the price of one, since after computing Y = K{X} we know that Y' = K'{X'}. But this does not seem to reduce the work needed for a brute-force attack on a particular key K, since K' is a different key.

If (S)DES had the property Y'=K'{X} then the search space would be reduced by 1/2; you'd compute Z=K{X} and if Z==Y then K is the key, and if Z==Y' then K' is the key.

6. SDES in Java

audio

SDES.java is an implementation of SDES. The constructor takes the key and initializes the key schedule. Methods are provided to encrypt and decrypt a byte, and a static method to print a byte in binary is also provided.

Example use: Encrypt.java, Decrypt.java

Copy.java shows how to copy stdin to stdout using system calls; it works even for binary files and can easily be adapted to perform file encryption or decryption.

7. Java byte operations

audio

Although most of the operations in SDES could be performed on bytes, SDES.java mainly uses ints. That's because Java operations on bytes produce int results which would have to be cast back to byte to be stored in a byte. Using int eliminates a lot of casts.

Consider this code: 

    byte a = 1, b = 2, c;

    c = a ^ b; // a XOR b
That will not compile; the javac error message is: 
  Incompatible type for =. Explicit cast needed to convert int to byte.
    c = a ^ b; // a XOR b
      ^
1 error
To eliminate the error, use a cast: 
    c = (byte) (a ^ b); // a XOR b

8. Cipher Block Chaining

audio

Even if the same block repeats in the plaintext, it will not cause repeats in the ciphertext.

Attribution: http://www.ece.villanova.edu/~perry/ccs/des/all-sdes.html
Rick Perry, Villanova University