BabyDES-DiffCrypt.mws

Baby DES-2

Differential Cryptanalysis

İMike May, S.J., 2002, maymk@slu.edu

>    restart;

To understand how to do DES, our book (by Trappe and Washington) uses a simplified DES-like system which we refer to as Baby DES.  This worksheet assumes that you have already worked through the first worksheet on Baby DES.

Baby DES recalled.

We recall the code from the first BabyDES worksheet that we need for implementing Baby DES.

>    indexS1 := x -> substring(convert(convert(x+16, binary),string),2..5):
indexList1 := [seq(indexS1(i),i=0..15)]:
indexList := matrix([[seq(indexS1(i),i=0..7)],[seq(indexS1(8+i),i=0..7)]]):
showAsMatrix := table -> map(y->table[y],indexList):
roundKeyMaker := (keystring, i)
     -> substring(cat(keystring, keystring), i..(i+7)):
leftHalf := String -> substring(String, 1..6):
rightHalf := String -> substring(String, 7..12):
expander := String ->  cat(substring(String,1..2),
    substring(String,4), substring(String,3..4),
    substring(String,3), substring(String,5..6)):
XOR := (a,b) -> if (a=b) then "0" else "1" fi:
xorNbits := (a,b,N) ->
  cat(seq(XOR(substring(a,i), substring(b,i)),i=1..N)):
SBoxa :=
    ["101", "010", "001", "110", "011", "100", "111", "000",
     "001", "100", "110", "010", "000", "111", "101", "011",
     "100", "000", "110", "101", "111", "001", "011", "010",
     "101", "011", "000", "111", "110", "010", "001", "100"]:
S1 := table([seq(indexList1[i]=SBoxa[i],i=1..16)]):
S2 := table([seq(indexList1[i]=SBoxa[i+16], i=1..16)]):
SingleRound := proc(messString, keyString, round)
    local roundKey, startL, startR, expandR, SInput, SOutput:
    roundKey := roundKeyMaker(keyString, round):
    startL := leftHalf(messString):
    startR := rightHalf(messString):
    expandR := expander(startR):
    SInput := xorNbits(expandR, roundKey,8):
    SOutput :=
        cat(S1[substring(SInput,1..4)],S2[substring(SInput,5..8)]):
    cat(startR, xorNbits(SOutput, startL,6));
  end:
BabyDES := proc(messString, keyString, numberRounds)
    local temp, i:
    temp := messString:
    for i from 1 to numberRounds do
        temp := SingleRound(temp, keyString,i) od:
  end:

>    keyString := "110110001";
messageString := "101101111001";

keyString :=

messageString :=

>    seq(BabyDES(messageString, keyString,i), i=1..4);

A Second Look at Differential Cryptanalysis for three round Baby DES.

In the first worksheet on Baby DES we looked at Differential Cryptanalysis for three round Baby DES.  

We used 4 words of chosen plaintext with the same right half to generate 6 pair of words with the same right half.  For each pair of words we found possible third round keys.  We then selected the round key that worked with all pairs.  

In a second variation, we want to count the number of pairs with which a half of a round key can possibly work.  We want to choose the half round key that works for the maximum number of pairs.

(Since the correct key works for all pairs, this method will give the correct answer.  The advantage of the second method is that it generalizes to 4 round Baby DES where we need to do some guessing.)

We start with a key and 4 words to encrypt.

Preliminary work with pairs of chosen plaintext

We start with the words that will be used for pairs.

>    keyString := "110110001":
mess[1] := "101101111001":
mess[2] := "101100111001":
mess[3] := "101111111001":
mess[4] := "100101111001":

For each chosen plaintext word we produced the encrypted word, the XOR of the left half of the plain text with the right half of the cipher text, and the expanded left half of the cipher text.

>    for i from 1 to 4 do
    code[i] := BabyDES(mess[i], keyString,3):
    R3L0[i] := xorNbits(leftHalf(mess[i]),rightHalf(code[i]),6):
    EL3[i] := expander(leftHalf(code[i])):
 end do:

For each pair of chosen plaintext words we also XORed the expanded left halves of the cipher text to produce the difference in inputs to the S boxes.  We also XORed the R3L0 words to produce the difference in outputs.

>    for i from 1 to 3 do
for j from i+1 to 4 do
Ehat[i,j] := xorNbits(EL3[i], EL3[j],8);
RLhat[i,j] := xorNbits(R3L0[i], R3L0[j], 6);
print([i,j], Ehat[i,j], RLhat[i,j]);
end do:
end do:

[1, 2],

[1, 3],

[1, 4],

[2, 3],

[2, 4],

[3, 4],

>   

Recall the functions created in the last worksheet that let us XOR the S boxes with themselves shifted by the appropriate half of Ehat[i,j].  We also recall the function that collected the locations in the hatted S boxes that have the desired value, then shifted them by the appropriate half of L3 to give possibilities for the round key.

>    S1hatted := hatstring -> table([seq(indexList1[i]=
  xorNbits(S1[indexList1[i]],S1[xorNbits(indexList1[i],hatstring,4)],3),i=1..16)]):
S2hatted := hatstring -> table([seq(indexList1[i]=
  xorNbits(S2[indexList1[i]],S2[xorNbits(indexList1[i],hatstring,4)],3),i=1..16)]):
goodSvals := proc(hattedSBox, hatVal)
    local goodValues, i, j:
    goodValues :={}:
    for i from 1 to 16 do
      if (hattedSBox[indexList1[i]] = hatVal) then
         goodValues := goodValues union {indexList1[i]} end if:
    end do:
    goodValues;
end:
shiftedVals := (goodValues, shiftVal) ->
   map(x->xorNbits(x,shiftVal,4), goodValues):

For each of the 6 chosen plaintext pairs we then made a list of possible first and second halves of the third round key.

>    for i from 1 to 3 do
for j from i+1 to 4 do
S1hat := S1hatted(substring(Ehat[i,j],1..4));
S2hat := S2hatted(substring(Ehat[i,j],5..8));
s1 := shiftedVals(goodSvals(S1hat, substring(RLhat[i,j],1..3)),
                substring(expander(leftHalf(code[i])),1..4));
s2 := shiftedVals(goodSvals(S2hat, substring(RLhat[i,j],4..6)),
                substring(expander(leftHalf(code[i])),5..8));
print([i,j, Ehat[i,j], RLhat[i,j]], s1, s2);
end do;
end do;

[1, 2,

[1, 3,
[1, 3,

[1, 4,

[2, 3,
[2, 3,

[2, 4,

[3, 4,

The last step was to intersect the sets of allowable halves of the round key to find the round key.
Looking at the (1,4) and (2,4) pairs we see that the first 4 bits are 0110.  Using the same pair of pairs the second four bits must be 0011.

This time we would like to look at the number of pairs of chosen plaintext allow a given half of the round key.  Obviously the correct key halves will show up all 6 times and the incorrect key halves will show up less often.

>    half1Count := table([seq(indexList1[i]=0,i=1..16)]):
half2Count := table([seq(indexList1[i]=0,i=1..16)]):
for i from 1 to 3 do
for j from i+1 to 4 do
S1hat := S1hatted(substring(Ehat[i,j],1..4));
S2hat := S2hatted(substring(Ehat[i,j],5..8));
s1 := shiftedVals(goodSvals(S1hat, substring(RLhat[i,j],1..3)),     
    substring(expander(leftHalf(code[i])),1..4));
for k from 1 to nops(s1) do
half1Count[s1[k]]:= half1Count[s1[k]]+1 end do:
s2 := shiftedVals(goodSvals(S2hat, substring(RLhat[i,j],4..6)),     
    substring(expander(leftHalf(code[i])),5..8));
for k from 1 to nops(s2) do
half2Count[s2[k]]:= half2Count[s2[k]]+1 end do:
end do;
end do;
half1Count = showAsMatrix(half1Count);
half2Count = showAsMatrix(half2Count);

half1Count = matrix([[3, 3, 3, 3, 3, 3, 6, 3], [3, 1, 3, 1, 1, 3, 1, 2]])

half2Count = matrix([[1, 1, 0, 6, 1, 1, 1, 0], [1, 1, 2, 1, 1, 1, 1, 1]])

Once again we conclude that the first half of the round key is 0110 and the second half of the round key is 0011.

Differential Cryptanalysis with randomly chosen pairs of plaintext.

When we look at four round Baby DES we will want to use a collection randomly chosen pairs of plaintext with specified differences between the words.  For three round Baby DES the condition on the pair of words is that the the second halves should the same.  Thus we want to generate random pairs of plaintext words with the second half the same.  This simplifies to being able to generate random 6 bit strings that we put together appropriately.

>    rand6Bits := () -> substring(convert(convert(rand(64)()+64,binary),string),2..7):
rand6Bits();

>    randPair1 := proc()
    local left1, left2, right:
    left1 := rand6Bits():
    left2 := rand6Bits():
    right := rand6Bits():
    [cat(left1, right), cat(left2, right)];
end:
randPair1();

[

For each such random pair, we want the plaintext words, the ciphertext words, and the values we referred to as EL3hat and R3L0hat.

>    SboxPair := proc(wordpair, keystring)
    local wordA, wordB, codeA, codeB, R3L0A, R3L0B,
         EL3A, EL3B, Ehat, RLhat:
    wordA := wordpair[1];
    wordB := wordpair[2];
    codeA := BabyDES(wordA, keystring,3);
    codeB := BabyDES(wordB, keystring,3);
    R3L0A := xorNbits(leftHalf(wordA),rightHalf(codeA),6):
    R3L0B := xorNbits(leftHalf(wordB),rightHalf(codeB),6):
    EL3A := expander(leftHalf(codeA));
    EL3B := expander(leftHalf(codeB));
    Ehat := xorNbits(EL3A, EL3B,8);
    RLhat := xorNbits(R3L0A, R3L0B, 6);
    [wordA, codeA, wordB, codeB, Ehat, RLhat];
end:

>    for i from 1 to 2 do
SboxPair(randPair1(),keyString)
end do;

[

[

We can now test this method of cryptanalysis by running it 5 times on 20 randomly chosen pairs of plaintext with where the second half of words in a pair are the same.

>    for j from 1 to 5 do
  half1Count := table([seq(indexList1[i]=0,i=1..16)]):
  half2Count := table([seq(indexList1[i]=0,i=1..16)]):
  for i from 1 to 20 do
      randSboxPair := SboxPair(randPair1(),keyString):
      S1hat := S1hatted(substring(randSboxPair[5],1..4)):
      S2hat := S2hatted(substring(randSboxPair[5],5..8)):
      s1 := shiftedVals(goodSvals(S1hat, substring(randSboxPair[6],1..3)),     
          substring(expander(leftHalf(randSboxPair[2])),1..4));
      for k from 1 to nops(s1) do
          half1Count[s1[k]]:= half1Count[s1[k]]+1 end do:
      s2 := shiftedVals(goodSvals(S2hat, substring(randSboxPair[6],4..6)),     
          substring(expander(leftHalf(randSboxPair[2])),5..8));
      for k from 1 to nops(s2) do
          half2Count[s2[k]]:= half2Count[s2[k]]+1 end do:
  end do:
  print(half1Count = showAsMatrix(half1Count));
  print(half2Count = showAsMatrix(half2Count));
end do:

half1Count = matrix([[7, 7, 7, 6, 12, 11, 20, 8], [2, 4, 4, 3, 6, 5, 6, 4]])

half2Count = matrix([[3, 3, 4, 20, 3, 3, 6, 6], [3, 1, 3, 7, 2, 3, 7, 8]])

half1Count = matrix([[4, 5, 5, 5, 11, 13, 20, 7], [5, 4, 8, 4, 7, 6, 6, 6]])

half2Count = matrix([[7, 7, 3, 20, 7, 2, 4, 9], [6, 3, 5, 3, 5, 3, 7, 5]])

half1Count = matrix([[8, 8, 8, 7, 9, 14, 20, 10], [4, 5, 5, 5, 6, 7, 7, 7]])

half2Count = matrix([[8, 5, 7, 20, 8, 5, 7, 7], [6, 8, 7, 7, 5, 6, 11, 9]])

half1Count = matrix([[9, 11, 11, 10, 11, 16, 20, 12], [4, 4, 3, 5, 5, 2, 4, 5]])

half2Count = matrix([[6, 3, 1, 20, 4, 2, 2, 5], [3, 2, 4, 2, 6, 4, 4, 2]])

half1Count = matrix([[8, 6, 6, 5, 8, 7, 20, 9], [7, 5, 7, 5, 5, 6, 4, 4]])

half2Count = matrix([[6, 3, 3, 20, 3, 2, 5, 6], [4, 6, 8, 3, 7, 2, 6, 6]])

In each case we see that the first half of the round key is 0110 and the second half is 0011.

>   

Exercise:

1)  Use the techniques above to find the third round key for a three round Baby DES encryption when the key is 011001110.

>   

Differential Cryptanalysis for four round Baby DES

We are ready to turn our attention to four round Baby DES.  We will modify the procedure used above to find the most likely 4th round key.

>    keyString := "101100101";
R4Key := roundKeyMaker(keyString,4);

keyString :=

R4Key :=

Here we want to use a weakness in the S boxes to give us pairs of plaintext words where the end of the first round gives a pair of words that should be useful for differential cryptanalysis with three round Baby DES.

>    S1 = showAsMatrix(S1);
S2 = showAsMatrix(S2);

S1 = matrix([[

S2 = matrix([[

The book notes that the differences in the S box outputs are easiest to predict if the differences in the S box inputs are 0011 and 1100 respectively, with the most likely answer being 011010 which occurs 3/8 of the time rather than the predicted 1/64 of the time.

>    S1hat := S1hatted("0011"):
S2hat := S2hatted("1100"):
S1hat = showAsMatrix(S1hat);
S2hat = showAsMatrix(S2hat);

S1hat = matrix([[

S2hat = matrix([[

Since we want the differences in the R1s to be 000000, we want the differences in the L0s to be 011010.  We also want the expansion of the difference in the R0s to be 00111100 to have the desired action in shifting the S boxes.  Thus we want the differences in the R0s to be 001100.  Thus we need to be able to produce random pairs of plaintext with the specified difference in halves.

>    randPair2 := proc(shift1, shift2)
    local left1, right1:
    left1 := rand6Bits():
    right1 := rand6Bits():
    [cat(left1, right1),
     cat(xorNbits(left1,shift1,6), xorNbits(right1,shift2,6))];
end:

>    randPair2("011010", "001100");

[

>    SboxPair2 := proc(wordpair,L1shift, keystring)
    local wordA, wordB, codeA, codeB, R4L1A, R4L1B,
         EL4A, EL4B, Ehat, RLhat:
    wordA := wordpair[1];
    wordB := wordpair[2];
    codeA := BabyDES(wordA, keystring,4);
    codeB := BabyDES(wordB, keystring,4);
    R4L1A := xorNbits(rightHalf(codeA),"000000",6):
    R4L1B := xorNbits(rightHalf(codeB),L1shift,6):
    EL4A := expander(leftHalf(codeA));
    EL4B := expander(leftHalf(codeB));
    Ehat := xorNbits(EL4A, EL4B,8);
    RLhat := xorNbits(R4L1A, R4L1B, 6);
    [wordA, codeA, wordB, codeB, Ehat, RLhat];
end:

>    for i from 1 to 2 do
SboxPair2(randPair2("011010", "001100"),"001100",keyString)
end do;

[

[

Now we are ready to test 100 pairs of words to see the most likely halves for the fourth round key.

>    half1Count := table([seq(indexList1[i]=0,i=1..16)]):
half2Count := table([seq(indexList1[i]=0,i=1..16)]):
for i from 1 to 100 do
      randSboxPair := SboxPair2(randPair2("011010", "001100"),"001100",keyString):
      S1hat := S1hatted(substring(randSboxPair[5],1..4)):
      S2hat := S2hatted(substring(randSboxPair[5],5..8)):
      s1 := shiftedVals(goodSvals(S1hat, substring(randSboxPair[6],1..3)),     
          substring(expander(leftHalf(randSboxPair[2])),1..4));
      for k from 1 to nops(s1) do
          half1Count[s1[k]]:= half1Count[s1[k]]+1 end do:
      s2 := shiftedVals(goodSvals(S2hat, substring(randSboxPair[6],4..6)),     
          substring(expander(leftHalf(randSboxPair[2])),5..8));
      for k from 1 to nops(s2) do
          half2Count[s2[k]]:= half2Count[s2[k]]+1 end do:
end do:
print(half1Count = showAsMatrix(half1Count));
print(half2Count = showAsMatrix(half2Count));

half1Count = matrix([[4, 3, 7, 6, 6, 3, 4, 4], [33, 58, 37, 31, 50, 39, 40, 35]])

half2Count = matrix([[23, 11, 5, 12, 8, 12, 41, 13], [11, 11, 18, 17, 8, 16, 8, 20]])

Picking the most common 4 bit sting for each half we guess a fourth round key of 10010110.

Exercise:

2)  Use the techniques above to find the third round key for a three round Baby DES encryption when the key is 110001110.

>   

>   

>