BabyDES-Intro.mws

Baby DES - 1

İ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.  For ease of terminology we will refer to it as Baby DES.

We would like a worksheet that computes Baby DES for us.  We first walk through the procedure step by step before creating a procedure to do the encryption in a single step.
Baby DES uses a message string of 12 bits and a key string of 9 bits.

Baby DES done step by step

The first approach is to walk through the procedure step by step.  You should check all the computations here by hand to be sure you understand what is being done.

We start with a sample message and key.
Baby DES uses a message string of 12 bits and a key string of 9 bits.

>    keyString := "110110001";
messageString := "101101111001";
length(keyString);
length(messageString);

keyString :=

messageString :=

9

12

We want a function to make round keys.  The round key for the ith round starts with the ith bit of the key string and continues for 8 bits wrapping around if necessary.

>    roundKeyMaker := proc(keystring, i)
   local startBit:
   startBit := ((i-1) mod 9) +1:
   substring(cat(keystring, keystring), startBit..(startBit+7)):
   end:

>    seq([i,roundKeyMaker(keyString, i)], i=1..3);

[1,

The first part of each round is to break the message in half and expand one of the right half from 6 to 8 bits by a fixed pattern.  We create functions to do these steps.

>    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)):

At each step we compute our example to verify it has the desired action.

>    L0 := leftHalf(messageString);
R0 := rightHalf(messageString);
ER0 := expander(R0);
k1 := roundKeyMaker(keyString, 1);

L0 :=

R0 :=

ER0 :=

k1 :=

The next step in each round is to XOR the expanded right half with the round key, producing the input for the S boxes.  We create functions to XOR a single bit, and one to use it on longer strings.

>    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)):

>    SInput := xorNbits(ER0, k1,8);

SInput :=

We need to construct the S boxes.  It will be convenient to make the S boxes into tables with the entries indexed by the 4 bit strings used for addresses.  We need a function that converts integers to 4 bit binary strings.  (Our function adds 16 before converting and then strips off the leading bit of the 5 bit string.  This eliminate problems with leading zeroes.)

>    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"]:
indexS1 := x -> substring(convert(convert(x+16, binary),string),2..5):
S1 := table([seq(indexS1(i-1)=SBoxa[i],i=1..16)]):
S2 := table([seq(indexS1(i-1)=SBoxa[i+16], i=1..16)]):

It is also useful to see the S boxes written as an ordered matrix.  Thus we create a procedure for turning a table with the 4 bit binary strings as index values into a matrix.

>    indexList := matrix([[seq(indexS1(i),i=0..7)],[seq(indexS1(8+i),i=0..7)]]);
showAsMatrix := table -> map(y->table[y],indexList):

indexList := matrix([[

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

S1box = matrix([[

S2box = matrix([[

Now we can look up the appropriate values in the S boxes and concatenate them together.  This result is the output of the f function.

>    Soutput := cat(S1[substring(SInput,1..4)],S2[substring(SInput,5..8)]);

Soutput :=

This value is XORed with the old left, then concatenated with the new left which is the old right.

>    L1 := R0;
R1 := xorNbits(L0,Soutput,6);
End1 := cat(L1, R1);

L1 :=

R1 :=

End1 :=

We combine the functions into a single procedure that does one round of Baby DES.

>    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:

>    SingleRound(messageString, keyString,1);

Now we produce a procedure that does Baby DES with a specified number of rounds.

>    BabyDES := proc(messString, keyString, numberRounds)
    local temp, i:
    temp := messString:
    for i from 1 to numberRounds do
        temp := SingleRound(temp, keyString,i) od:
  end:

This lets us see the results round by round

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

Exercise

1)  Do a three round Baby DES encryption on a single 12 bit message with your favorite 9 bit key by hand.  Verify your work with this worksheet.

>   

Baby DES in a single execution group.

While the step by step approach is useful to understand what is going on, we want to put everything into a single block of code that can be copied and executed to enable BabyDES.

>    roundKeyMaker := proc(keystring, i)
   local startBit:
   startBit := ((i-1) mod 9) +1:
   substring(cat(keystring, keystring), startBit..(startBit+7)):
   end:
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"]:
indexS1 := x -> substring(convert(convert(x+16, binary),string),2..5):
S1 := table([seq(indexS1(i-1)=SBoxa[i],i=1..16)]):
S2 := table([seq(indexS1(i-1)=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:

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

We would also like to store the commands in a file so that we can recall them in future sessions.  The file will be called BabyDES.m and will be created in the current directory.

>    save roundKeyMaker, leftHalf, rightHalf, expander, XOR,
     xorNbits, S1, S2, SingleRound,BabyDES, `BabyDES.m`:
currentdir();

Differential Cryptanalysis for three round Baby DES.

We would now like to look at Differential Cryptanalysis for three round Baby DES.

We start with a key and 4 words to encrypt.

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

keyString :=

mess[1] :=

mess[2] :=

mess[3] :=

mess[4] :=

We compute three round keys.  The method will produce the three round key.

>    for i from 1 to 3 do roundKeyMaker(keyString,i) od;

For each word we want to produce 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
    mess[i];
    code[i] := BabyDES(mess[i], keyString,3);
    R3L0[i] := xorNbits(leftHalf(mess[i]),rightHalf(code[i]),6);
    EL3[i] := expander(leftHalf(code[i]));
 od;

code[1] :=

R3L0[1] :=

EL3[1] :=

code[2] :=

R3L0[2] :=

EL3[2] :=

code[3] :=

R3L0[3] :=

EL3[3] :=

code[4] :=

R3L0[4] :=

EL3[4] :=

For each pair of words we want to XOR the expanded left halves of the cipher text.  These will be the difference in inputs to the S boxes.  We also want to XOR the R3L0 words.  These will be 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]);
od; od;

[1, 2],

[1, 3],

[1, 4],

[2, 3],

[2, 4],

[3, 4],

Time to repeat a technical detail.  I want to switch between the integers 0-15 and the binary strings "0000" to "1111" without losing leading zeroes.

>    indexS1 := x -> substring(convert(convert(x+16, binary),string),2..5):

To use the differentials, I need routines that will XOR the S boxes with themselves shifted an appropriate amount.

>    S1hatted := hatstring -> table([seq(indexS1(i)=
  xorNbits(S1[indexS1(i)],S1[xorNbits(indexS1(i),hatstring,4)],3),i=0..15)]):
S2hatted := hatstring -> table([seq(indexS1(i)=
  xorNbits(S2[indexS1(i)],S2[xorNbits(indexS1(i),hatstring,4)],3),i=0..15)]):

Test the code by XORing S1 with itself shifted by "1000" (subtract rows) and S2 with itself shifted by "0001" (adjacent pairs of columns).

>    S1hat := S1hatted(substring("10000001",1..4)):
S2hat := S2hatted(substring("10000001",5..8)):
S1box = showAsMatrix(S1);
S1hat = showAsMatrix(S1hat);
S2box = showAsMatrix(S2);
S2hat = showAsMatrix(S2hat);

S1box = matrix([[

S1hat = matrix([[

S2box = matrix([[

S2hat = matrix([[

We now want to examine the hatted S boxes for the correct output values.  The locations with these values will be shifted by the appropriate half of the expansion of L3 to give possibilities for half of the round key.

>    goodSvals := proc(hattedSBox, hatVal)
    local goodValues, i, j:
    goodValues :={}:
    for i from 1 to 16 do
      if (hattedSBox[indexS1(i)] = hatVal) then
         goodValues := goodValues union {indexS1(i)} end if:
    end do:
    goodValues;
end:
shiftedVals := (goodValues, shiftVal) ->
   map(x->xorNbits(x,shiftVal,4), goodValues):

We can plug in the pairs of words to see which 4 bit string shows up for each pair.

>    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));
print(S1hat = [[seq(S1hat[indexS1(i)],i=0..7)],[seq(S1hat[indexS1(8+i)],i=0..7)]]);
print(S2hat = [[seq(S2hat[indexS1(i)],i=0..7)],[seq(S2hat[indexS1(8+i)],i=0..7)]]);
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;

S1hat = [[
S1hat = [[

S2hat = [[
S2hat = [[

[1, 2,
[1, 2,

S1hat = [[
S1hat = [[

S2hat = [[
S2hat = [[

[1, 3,
[1, 3,

S1hat = [[
S1hat = [[

S2hat = [[
S2hat = [[

[1, 4,

S1hat = [[
S1hat = [[

S2hat = [[
S2hat = [[

[2, 3,
[2, 3,

S1hat = [[
S1hat = [[

S2hat = [[
S2hat = [[

[2, 4,

S1hat = [[
S1hat = [[

S2hat = [[
S2hat = [[

[3, 4,

Looking at the (1,4) and (2,4) pairs we see that the first 4 bits are 0110.  Using the same two pairs of words the second four bits must be 0011.

We can automate the comparison process.

>    S1hat := S1hatted(substring(Ehat[1,2],1..4));
S2hat := S2hatted(substring(Ehat[1,2],5..8));
good1 := shiftedVals(goodSvals(S1hat, substring(RLhat[1,2],1..3)),     
    substring(expander(leftHalf(code[1])),1..4));
good2 := shiftedVals(goodSvals(S2hat, substring(RLhat[1,2],4..6)),     
    substring(expander(leftHalf(code[1])),5..8));
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));
good1 := good1 intersect s1:
print([i,j],` first bytes left `, good1);
good2 := good2 intersect s2:
print([i,j],` second bytes left `, good2);
end do;
end do;

S1hat := TABLE([
S1hat := TABLE([
S1hat := TABLE([
S1hat := TABLE([
S1hat := TABLE([

S2hat := TABLE([
S2hat := TABLE([
S2hat := TABLE([
S2hat := TABLE([
S2hat := TABLE([

good1 := {

good2 := {

[1, 2], ` first bytes left `, {

[1, 2], ` second bytes left `, {

[1, 3], ` first bytes left `, {

[1, 3], ` second bytes left `, {

[1, 4], ` first bytes left `, {

[1, 4], ` second bytes left `, {

[2, 3], ` first bytes left `, {

[2, 3], ` second bytes left `, {

[2, 4], ` first bytes left `, {

[2, 4], ` second bytes left `, {

[3, 4], ` first bytes left `, {

[3, 4], ` second bytes left `, {

Exercise:

2)  Using a three round Baby DES system someone has generated the following four pairs of plaintext words and cipher text words.  Find the key.

["011011001011", "010001010100"]

["111011001011", "001001010111"]

["011111001011", "110010001101"]

["011010001011", "010101110100"]

>   

>   

>