DES-StatTest.html

DES - Diffusion testing

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

> restart;

This worksheet assumes that you have already created the DES.m file or have copied it to the current directory. It would be useful to look at the worksheet BabyDES-3 before doing this worksheet. As with that worksheet we will look at changing each bit of the plaintext, one at a time and seeing how it changes the ciphertext. The bits should change as if each bit were an independent random variable.

> read `DES.m`:

Preliminary Tools

To change the plaintext one bit at a time, it is convenient to be able to produce 64 bit hex words that are all zeroes except for a single bit. The 64 bits correspond to the powers of 2 from 0 to 63. We get the zero word with an input of 64.

> oneBitIn64 := intVal ->
substring(convert(convert(2^64+2^intVal,hex),string),2..17):
lowBit := oneBitIn64(0);
highBit := oneBitIn64(63);
zeroWord := oneBitIn64(64);

For our initial discussion, we will use the zeroWord for both the key and the message.

> keytest := zeroWord:
message := zeroWord:
key := keyexpander(keytest):
cipher1 := qdDEShex(message,key);

We would like to be able to convert a hex word to a list of 64 zeroes and ones. We would also like to count the number of ones.

>    hexStringToBitList := proc(hexString)
   local decValue:
   decValue := convert(hexString,decimal,hex):
   [seq(iquo(decValue,2^(64-i)) mod 2, i=1..64)];
end proc:
numBitsHexString := bitList -> sum(bitList[i],i=1..64):

> bitList := hexStringToBitList(cipher1);
numBits := numBitsHexString(bitList);

We recall that in constructing our DES functions we produced a function for XORing two hex words.

> cipher1;
xor64hex(cipher1,lowBit);
xor64hex(cipher1,highBit);

Counting the number of bits changed in each wor d

Following the procedure we used in BabyDES-3 we look at how bits of ciphertext change when we change each bit of the plaintext. We first look at how many bits have been changed in each word of ciphertext. In the results of the code below each line has the plaintext with a single changed bit, the new ciphertext, the XOR of the new and old ciphertexts and the number of bits changed. We also collect the number of bits changed so that we can compute the mean and standard deviations of those numbers.

>    bitChangeList := [seq(0,i=1..64)]:
key := keyexpander(zeroword):
cipher1 := qdDEShex(zeroword,key);
for intVal from 0 to 63 do
   mess1 := oneBitIn64(intVal):
   cipher := qdDEShex(mess1,key):
   diffHex := xor64hex(cipher1,cipher):
   numBitsChanged := numBitsHexString(hexStringToBitList(diffHex)):
   print(mess1, cipher, diffHex, numBitsChanged):
   bitChangeList[intVal+1] := numBitsChanged:
end do:
bitChangeList;

Note that changing one input bit always changed between 23 and 41 bits of output. If the bit changes are random, we expect the distribution above to have a mean of 64*.5=32 and a standard deviation of sqrt(64*.5*.5)=4.

> evalf(stats[describe, mean](bitChangeList));
evalf(stats[describe, standarddeviation](bitChangeList));

At a first level the bit changes seem to behave as if they are random.

We can create a procedure that will gather the same data with an arbitrary plaintext and key.

> intToHexString := intVal ->
substring(convert(convert(intVal+2^64,hex),string),2..17):

>    bitChangeCounter := proc(plaintext, key)
   local keyExpanded, bitChangeList, cipher1, i, mess1,
      cipher, diffHex, numBitsChanged, intVal:
   keyExpanded := keyexpander(key):
   bitChangeList := [seq(0,i=1..64)]:
   cipher1 := qdDEShex(plaintext,keyExpanded);
   for intVal from 0 to 63 do
      mess1 := xor64hex(intToHexString(2^intVal),plaintext):
      cipher := qdDEShex(mess1,keyExpanded):
      diffHex := xor64hex(cipher1,cipher):
      numBitsChanged := numBitsHexString(hexStringToBitList(diffHex)):
      bitChangeList[intVal+1] := numBitsChanged:
   end do:
   bitChangeList;
end:

> plainStart := intToHexString(rand(2^64)());
key := intToHexString(rand(2^64)());

> bitChangeList := bitChangeCounter(plainStart, key);

> evalf(stats[describe, mean](bitChangeList));
evalf(stats[describe, standarddeviation](bitChangeList));

>

Counting the number of words for which a bit is changed

A second way to look at the same data looks at how many words turn on each bit.

>    bitCountList := [seq(0,i=1..64)]:
key := keyexpander(zeroword):
for intVal from 0 to 64 do
   mess1 := oneBitIn64(intVal):
   cipher := qdDEShex(mess1,key):
   bitList := hexStringToBitList(cipher):
   bitCountList := zip(`+`, bitCountList, bitList):
end do:
bitCountList;

Once again we check the mean and standard deviation. We expect the number of words that use each bit to average 32.5 and have a standard deviation of sqrt(65*.5*.5), which is a little more than 4. (The expected standard deviation if each number were obtained from 65 events with probability .5 is sqrt(65/4).

> evalf(stats[describe, mean](bitCountList));
evalf(stats[describe, standarddeviation](bitCountList));

We can also test the same process starting with a randomly chosen key and message

>    bitCounter2 := proc(plaintext, key)
   local keyExpanded, bitCountList, cipher1, i, mess1,
      cipher, bitList, intVal:
   keyExpanded := keyexpander(key):
   bitCountList := [seq(0,i=1..64)]:
   for intVal from 0 to 64 do
      mess1 := xor64hex(intToHexString(2^intVal),plaintext):
      cipher := qdDEShex(mess1,keyExpanded):
      bitList := hexStringToBitList(cipher):
      bitCountList := zip(`+`, bitCountList, bitList):
   end do:
   bitCountList;
end:

> plainStart := intToHexString(rand(2^64)());
key := intToHexString(rand(2^64)());

> bitCountList := bitCounter2(plainStart, key);

> evalf(stats[describe, mean](bitCountList));
evalf(stats[describe, standarddeviation](bitCountList));

>