Differential Crypto on 3-round DES

Differential Cryptonalysis on 3-round DES

Description of 3-round DES

DES is a Feistel network. The encryption is done by F-Boxs receiving sub-keys generated off on the main key. The diagram below omits the initial and final permutations and the left-right swap on exit.


    L0     R0
    |    / |
    |   / [f] -- Key1
    |  /   |
    +------+
     /     |
    L1     R1
    |    / |
    |   / [f] -- Key2
    |  /   |
    +------+
     /     |
    L2     R2
    |    / |
    |   / [f] -- Key3
    |  /   |
    +------+
     /     |
    L3     R3

Principals of Differential Cryptoanalysis

There are several interlocking ideas in differential cryptoanalysis.

One is that following the xor difference of two inputs (called the differential) allows deeper penetration into the DES computation, first by nullifying the effect of xor-addition of Li to f(Ri,Keyi), and again by nullifying the xor-addition of the key inside the the F-Box.
A second is that the round key is constrained by knowledge of the differential input and differential output of the F-box.
Thirdly (although this we do not use here), that there is an imbalance in the frequency of F-Box differential outputs that allows a probabilistic tracing of differentials when attacking more than three rounds.

Attacking 3-round DES (mini-des)

The last stage is attacked. Note that R2, the input to the last F-box, is available at the output, as L3. If we knew L2, the output to the last F-Box would be known, as R3+L2, and we could begin forcing open Key3. We don't know L2, as that would require knowledge of R1, and therefore knowledge of the output of the first F-Box. However, if we give two inputs (L0,R0) and (L0',R0') and furthermore R0=R0', then we do know L2+L2',

    L2+L2' = R1+R1' = (L0+f(R0))+(L0'+f(R0')) = L0+L0'

So we do know the differential output of the third round F-Box as well as its differential input

    R2+R2'= L3+L3'.

Given the differential input and output to an S-Box (by tracing the input and outputs to the F-Box through the E and P functions inside the F-Box, here again we use the xor jumping property of differentials), we get a list a possible input pairs: input pairs X and X' such that X+X' equals the differential input and f(X)+f(X') equals the differential output. We then compute keys which transform X and X' into R2 and R2'.

Burton Rosenberg
Created: Sat Sep 4 13:16:13 EDT 2004
Modified: Feb 29, 2016