BabyDES-StatAnal.html

Baby DES 3
Statistical considerations

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

> restart:
read `BabyDES.m`:

This worksheet assumes that you have already worked through the first worksheet on Baby DES. That first Baby DES worksheet creates the BabyDES.m. The BabyDES.m file should be in the current directory.

This worksheet looks at how effectively Baby DES is when measured from some statistical criteria. These criteria can be used to evaluate other symmetric ciphers.

For a block cipher to be effective it should be true that if we know all but one of the bits in the plaintext block and the key, then each bit of the cipher block should still have a 50-50 chance of being either zero or one. Obviously it is too much to ask that precisely 50 % of the bits change when we change one bit of the plaintext. We want to test if this is the average behavior and if it seems to follow a random pattern..

Shifting each single bit

The first way to test for random behavior is to ask if we start from a fixed plaintext and key, and change each bit of the plaintext one at a time, do the bits of the ciphertext behave randomly.

Counting the number of bits changed in each word

A first examination looks at how many bits of output are changed if we change each single bit of the input or of the key. Each bit of the output should be changed with a probability of .5.
To make our task easier, we want routines that will easily produce various keys or plaintext messages. Recall that for Baby DES, the input block is 12 bits and the key is 9 bits.

>    intToBitKey := i ->
  substring(convert(convert(2^9+i,binary),string),2..10):
intToBitMessage := i ->
  substring(convert(convert(2^12+i,binary),string),2..13):

> zerokey := intToBitKey(0);
zeromessage := intToBitMessage(0);

The first test is to compare the ciphertext obtained from the zerokey and zeromessage with the ciphertext obtained by encoding a message with a single bit changed. We start by looking at 2 rounds.

> numRounds := 2;
cipher0 := BabyDES(zeromessage, zerokey, numRounds);
for loc from 0 to 11 do
message := intToBitMessage(2^loc);
cipher := BabyDES(message, zerokey,numRounds);
comparison := xorNbits(cipher, cipher0, 12);
print(loc,message, cipher, comparison);
od:

Ideally we expect the comparison to be half ones and half zeroes with the ones randomly distributed. With 2 round Baby DES, we changed an average of 3 bits of output when we changed one round of input. This is enough less than the hoped for value of 6 bits that we conclude 2 rounds is not enough.

Obviously Baby DES need more than 2 rounds to be effective. Before testing more rounds we want to produce procedures that will make the results easier to analyze. We want procedures to convert a bit string into a list of digits and another procedure to count the number of ones in such a list.

> zeroList12 := [seq(0,place=1..12)]:
bitStringToList12 := bitString ->
[seq(parse(substring(bitString,place)), place=1..12)]:
addList12 := bitList -> sum(bitList[place], place=1..12):

> cipher0;
bitStringToList12(cipher0);
addList12(bitStringToList12(cipher0));

We now count the number of bits changes by individually changing each bit in the plaintext message and compute the mean and standard deviation of these results.

>    diffCount :=
   [seq(addList12(bitStringToList12(xorNbits(cipher0,
      BabyDES(intToBitMessage(2^i),zerokey,2),12))),i=0..11)];
evalf(stats[describe, mean](diffCount));
evalf(stats[describe, standarddeviation](diffCount));

If each bit was changed with a probability of .5, then we expect the entries of diffCount to look like they were produced by a random binomial probability distribution based on 12 tries with a probability of .5. The expected value is (12)*(.5)=6. The expected standard deviation is sqrt(12*.5*.5) = 1.732. Since we are modeling random behavior we don't expect 6 every time. We do however expect it to be close to the average value. (We will return to this later.)

We want to generalize the procedure above so that we can input a key, a message and a number of rounds and we look at the change caused by changing each bit of the plaintext, one at a time.

>    changeEachBitMessage := proc(message, key, rounds)
   local cipher0, diffCount, newMessage, changebits, pos:
   cipher0 := BabyDES(message, key, rounds):
   diffCount := vector(12):
   for pos from 0 to 11 do
      newMessage := xorNbits(message, intToBitMessage(2^pos), 12):
      changebits := xorNbits(cipher0, BabyDES(newMessage, key, rounds), 12):
      diffCount[pos+1] := addList12(bitStringToList12(changebits)):
   od:
   convert(diffCount,list);
end:

> count1 := changeEachBitMessage(zeromessage, zerokey,2);
evalf(stats[describe, mean](count1));
evalf(stats[describe, standarddeviation](count1));

We can try Baby DES with a variable number of rounds and see how many rounds we need for the behavior to look like bits are randomly changed.

>    for rounds from 2 to 10 do
  countList := changeEachBitMessage(zeromessage, zerokey,rounds):
  print(rounds,countList, evalf(stats[describe, mean](countList)),
      evalf(stats[describe, standarddeviation](countList))):
od:

At this first level of analysis, it looks like 5 rounds of Baby DES changes bits with a probability of about .5.

>

Random binomial distributions

If each bit is changed with a probability of .5, then the sum of a collection of bits should produce a binomial distribution. Maple lets us produce random numbers from such a distribution. We have been looking at numbers that we hope are the result of counting the number of successes in 12 trials, each of which has a .5 chance of success.

> stats[random,binomiald[12, .5]](1);
stats[random,binomiald[12, .5]](5);
[stats[random,binomiald[12, .5]](12)];

Consider the results of 10 fake lists in the form gathered in the last section

>    for counta from 1 to 10 do
fakeList := [stats[random,binomiald[12, .5]](12)]:
  print(counta,fakeList, evalf(stats[describe, mean](fakeList)),
      evalf(stats[describe, standarddeviation](fakeList))):
end do:

Compare with the results of shifting each bit of plaintext for 10 randomly chosen pairs of plaintext and key words with 5 round Baby DES.

>    for counter from 1 to 10 do
   message := intToBitMessage(rand(2^12)()):
   key := intToBitKey(rand(2^9)()):
   countList := changeEachBitMessage(message, key, 5):
   print(message, key, countList, evalf(stats[describe, mean](countList)),
     evalf(stats[describe, standarddeviation](countList))):
od:

The samples from Baby DES seem to be behaving much like the samples from the random distribution.

As a second line of analysis, we would like to collect the means from samples. This is easy to do with our fake lists.

>    meanList := list():
for count from 1 to 40 do
   fakeList := [stats[random,binomiald[12, .5]](12)];
   meanList[count] := evalf(stats[describe, mean](fakeList));
od:
meanList := convert(meanList, list):

What we have done is produce a sampling distribution. The meanList should have the same mean, 6, with a standard distribution that is the old predicted standard deviation divided by the square root of the size of the list. Thus the predicted standard deviation is sqrt(12*.5*.5/12)=.5. In that computation the first 12 is the number of bits collected in defining the binomial distribution and the second 12 is the number of sample taken with that distribution.

> meanList;
stats[describe, mean](meanList);
stats[describe, standarddeviation](meanList);

We can now do the same thing with samples obtained from the number of bits changed when changing each bit of a random message.

>    changeEachBitMessage2 := proc(message, key, rounds)
   local cipher0, diffCount, newMessage, changebits, pos:
   cipher0 := BabyDES(message, key, rounds):
   diffCount := vector(12):
   for pos from 0 to 11 do
      newMessage := xorNbits(message, intToBitMessage(2^pos), 12):
      changebits := xorNbits(cipher0, BabyDES(newMessage, key, rounds), 12):
      diffCount[pos+1] := addList12(bitStringToList12(changebits)):
   od:
   diffCount := convert(diffCount,list):
   evalf(stats[describe, mean](diffCount));
end:

>    meanList := list():
for count from 1 to 40 do
   message := intToBitMessage(rand(2^12)()):
   key := intToBitKey(rand(2^9)()):
   countList := changeEachBitMessage2(message, key, 5):
   meanList[count] := countList:
od:
meanList := convert(meanList, list);
stats[describe, mean](meanList);
stats[describe, standarddeviation](meanList);

It seems that the bits are behaving randomly from this perspective.

>

Counting the number of words for which a bit is changed

We initially asked if we change the plaintext one bit at a time, how many bits are changed in each new ciphertext. The other obvious way to arrange the data asks in how many of the ciphertexts is a particular bit changed.

>    changeEachBitMessage3 := proc(message, key, rounds)
   local cipher0, diffCount, newMessage, changebits, pos:
   cipher0 := BabyDES(message, key, rounds):
   diffCount := [seq(0,i=1..12)]:
   for pos from 0 to 11 do
      newMessage := xorNbits(message, intToBitMessage(2^pos), 12):
      changebits := xorNbits(cipher0, BabyDES(newMessage, key, rounds), 12):
      diffCount := zip(`+`,diffCount,bitStringToList12(changebits)):
   od:
   diffCount:
end:

> changeEachBitMessage3(zeromessage, zerokey,5);

If we do this for a number of words we can then accumulate these changes starting at a number of different words

>    key := intToBitKey(rand(2^9)());
countList := []:
for count from 1 to 10 do
   message := intToBitMessage(rand(2^12)()):
   countList := [op(countList), op(changeEachBitMessage3(message, key, 5))]:
od:
countList;

As above, we take the mean and standard deviation of this list. It is also useful to tally this list to see the shape of the distribution in countlist.

> evalf(stats[describe, mean](countList),3);
evalf(stats[describe, standarddeviation](countList),3);
stats[transform,tally](countList);

For comparison, we compute the probability of each value showing up randomly. For each value of i from 0 to 12, we want to know the probability that we will get i heads from 12 coin flips.

> probSeq := [seq([i, evalf(combinat[numbcomb](12,i)/combinat[numbcomb](12),3)],i=0..12)];

This lets us compute the number of times we expect each value of i to show up in our collection of 120 numbers.

> expectSeq := map(x->[x[1],x[2]*120],probSeq);

Once again, it looks like the behavior is fairly close to random on this test. To gain a better perspective, we repeat the process from 10 randomly chosen plaintexts.

>

>    for i from 1 to 10 do
key := intToBitKey(rand(2^9)());
countList := []:
for count from 1 to 10 do
   message := intToBitMessage(rand(2^12)()):
   countList := [op(countList), op(changeEachBitMessage3(message, key, 5))]:
od:
print(evalf(stats[describe, mean](countList),3),
   evalf(stats[describe, standarddeviation](countList),3),
   stats[transform,tally](countList));
od:

This does seem to be close to random behavior.

>

Clusters of plaintext blocks

A second way to test for randomness is to fix a key and a starting plaintext and look at the aggregated result of encrypting a block of plaintext words. We will look at a block of 32 words obtained by letting 5 consecutive plaintext bits vary. We start with some technical procedures for looking at a block of plaintexts.

>    makePlainBlock := proc(startPlain,shiftBits)
   local intShifts,i:
   intShifts := [seq(i*2^shiftBits,i=0..31)]:
   map(xorNbits,map(intToBitMessage,intShifts),startPlain,12):
end:

> starter :=intToBitMessage(rand(2^12)());
makePlainBlock(starter,7);

We want a procedure to take each entry in such a block, encrypt it with Baby DES, turn the ciphertext into a list of bits, and add the bits for each position.

>    testPlainBlock := proc(startPlain, key, shiftBits)
   local plainBlock, i, distList:
   plainBlock := makePlainBlock(startPlain, shiftBits):
   distList := [seq(0,i=1..12)]:
   for i from 1 to 32 do
      distList := zip(`+`,distList,bitStringToList12(BabyDES(plainBlock[i],key,5))):
   od:
   distList;
   end:

Now we can test the procedure with a randomly chosen plaintext, key and shift.

> key := intToBitKey(rand(2^9)());
startPlain := intToBitMessage(rand(2^12)());
shiftBits := rand(8)();
testPlainBlock(startPlain, key, shiftBits);

To do a better test we repeat the process from a number of randomly chosen starting points. We can take the mean and standard deviation of this distribution. We expect the distribution to have a mean of 32*.5=16 and a standard deviation of sqrt(32*.5*.5)=2.828.

> distlist := []:
for i from 1 to 10 do
startPlain := intToBitMessage(rand(2^12)());
d2list := testPlainBlock(startPlain, key, shiftBits);
print(startPlain,d2list, evalf(stats[describe, mean](d2list),3),
evalf(stats[describe, standarddeviation](d2list),3));
distlist := [op(distlist), op(d2list)]:
od:
distlist;
evalf(stats[describe, mean](distlist),3);
evalf(stats[describe, standarddeviation](distlist),3);

Once again the behavior looks fairly close to what we expect from random behavior.

>

Pairs of plaintext blocks

A final way that we will look at the random behavior is to consider pairs of plaintext words that differ by a fixed but random amount.

Counting the number of bits changed in each wor d

We start by looking at how many bits are changed between the ciphertexts of a pair of plaintexts

> key := intToBitKey(rand(2^9)());

> shiftWord := intToBitMessage(rand(2^12)());

> firstWord := intToBitMessage(rand(2^12)());
secondWord := xorNbits(firstWord, shiftWord, 12);

> cipherDiff := xorNbits(BabyDES(firstWord,key,5),BabyDES(secondWord,key,5),12);

> diffCount := addList12(bitStringToList12(cipherDiff));

Now we create a procedure to do this with a bunch of pairs

>    pairShiftCounter := proc(key, shiftWord, rounds, numPairs)
   local countList, firstWord, secondWord, cipherDiff, i:
   countList := table():
   for i from 1 to numPairs do
      firstWord := intToBitMessage(rand(2^12)());
      secondWord := xorNbits(firstWord, shiftWord, 12);
      cipherDiff := xorNbits(BabyDES(firstWord,key,rounds),
            BabyDES(secondWord,key,rounds),12);
      countList[i] := addList12(bitStringToList12(cipherDiff));
   od:
   convert(countList,list):
end:

> countList := pairShiftCounter(key, shiftWord, 5, 100);
stats[transform,tally](countList);
evalf(stats[describe, mean](countList));
evalf(stats[describe, standarddeviation](countList));

Once again, the behavior is reasonably close to what we expect from random

>

Counting the number of words for which a bit is changed

The other way of arranging the data is to look at how many pairs change a particular bit.

>    pairShiftCounter2 := proc(key, shiftWord, rounds, numPairs)
   local countList, firstWord, secondWord, cipherDiff, i:
   countList := [seq(0,i=1..12)]:
   for i from 1 to numPairs do
      firstWord := intToBitMessage(rand(2^12)());
      secondWord := xorNbits(firstWord, shiftWord, 12);
      cipherDiff := xorNbits(BabyDES(firstWord,key,rounds),
            BabyDES(secondWord,key,rounds),12);
      countList := zip(`+`,countList,bitStringToList12(cipherDiff));
   od:
   countList:
end:

> countList := pairShiftCounter2(key, shiftWord, 5, 100);

> stats[transform,tally](countList);
evalf(stats[describe, mean](countList));
evalf(stats[describe, standarddeviation](countList));

It should be noted that the expected mean with 100 pairs of plaintext is 100*.5=50 and the expected standard deviation is sqrt(100*.5*.5)=5.

>

The ways we have gathered data can obviously be adapted to other cryptographic systems.

One can also do more sophisticated statistical analyses on the gathered data.

>