DES - Diffusion testing \302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edu restart; read `DES.m`: with(Statistics): 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 3-BabyDES-StatAnal.mws 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.

Recall, that 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 64 trials, each of which has a .5 chance of success. We expect to get 32 = 64*.5, but will get a variety of answers with 32 being most common. We expect the standard deviation of this measure to be sqrt(64*.5*.5) or 4. Consider what happens if we take 400 such fake samples and do basic descriptive statistics on the set of values. R64 := RandomVariable(Binomial(64,.5)); SampleList := Sample(R64,400); DataSummary(SampleList); T1 := Tally(SampleList); "Mean"=Mean(SampleList); Histogram(SampleList,discrete=true,frequencyscale=absolute); "Mode"=Mode(SampleList,type=sample); It is useful to sort the tally of the list. sort(T1,(x,y)->lhs(x)<lhs(y)); We expect 95% of the samples to be within 1.96 standard deviations of the mean. In the case above we expect 380 o the 400 samples to be between 24.08 and 39.92. (In counting, an instance at x should be thought of as being evenly distributed between x-.5 and x+.5.) We can construct a confidence interval for the mean in a case like this. Thus if our sample is random, the observed mean should be within 1.96 standard deviations of the true mean 95% of the time. If we are looking at a large sample as above the standard deviation for the average of the means (the standard error) of n samples is sqrt(64*.5*.5/(2*n)). Thus in the case above with 400 samples, the observed mean should be within .28 of 32.0 for 19 out of 20 tries. sqrt(64*.5*.5/(2*400))*1.96; We will be interested in taking the mean of 64 samples. (We change each bit and look at the results.) In that case the confidence interval is 32 plus or minus .693. sqrt(64*.5*.5/(2*64))*1.96;

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 zero word 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: numBitsBinString := bitList -> add(i,i=bitList): countBits := hexstring -> numBitsBinString(hexStringToBitList(hexstring)): countBits(cipher1); We recall that in constructing our DES functions we produced a function for XORing two hex words. cipher1; "Bitcount in original cipher" = countBits(cipher1); xor64hex(cipher1,lowBit); "Bitcount withlow bit changed" = countBits(xor64hex(cipher1,lowBit)); xor64hex(cipher1,highBit); "Bitcount with high bit chaanged" = countBits(xor64hex(cipher1,highBit));

Following the procedure we used in 3-BabyDES-StatAnal.mws 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): "Base Cipher Word"= qdDEShex(zeroword,key); print("Plaintext","Ciphertext","Difference","Bits Changed"); for intVal from 0 to 63 do mess1 := oneBitIn64(intVal): cipher := qdDEShex(mess1,key): diffHex := xor64hex(cipher1,cipher): numBitsChanged := numBitsBinString(hexStringToBitList(diffHex)): print(mess1, cipher, diffHex, numBitsChanged): bitChangeList[intVal+1] := numBitsChanged: end do: T1 := Tally(bitChangeList); "Sorted Tally"=sort(T1,(x,y)->lhs(x)<lhs(y)); Note that changing one input bit from the zero message and the zero key 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. DataSummary(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. 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 := numBitsBinString(hexStringToBitList(diffHex)): bitChangeList[intVal+1] := numBitsChanged: end do: bitChangeList; end: We now want to try this with a random plaintext and key. intToHexString := intVal -> substring(convert(convert(intVal+2^64,hex),string),2..17): plainStart := intToHexString(rand(2^64)()); key := intToHexString(rand(2^64)()); bitChangeList := sort(bitChangeCounter(plainStart, key)); DataSummary(bitChangeList); We can check a number of random words to see a pattern of behavior. print(cat("Base word, Key used, ", " Bit Change mean, Bit Change SD")): for i from 1 to 10 do plainStart := intToHexString(rand(2^64)()): key := intToHexString(rand(2^64)()): bitChangeList := sort(bitChangeCounter(plainStart, key)); listMean := Mean(bitChangeList); listSD := StandardDeviation(bitChangeList): print(plainStart, key, listMean, listSD); end do:

1) Do the analysis above on 20 randomly chosen pairs of plaintexts and keywords. What is the 95% confidence interval for the means of number of bits changed? In how many of the 20 cases does the mean fall in the confidence interval?

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). Mean(bitCountList); 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); Mean(bitCountList); StandardDeviation(bitCountList); We can also try this with a series of randomly chosen pairs of plaintexts and keys to look for patterns of behavior. print(cat("Base word, Key used, ", " Bit Count mean, Bit Count SD")): for i from 1 to 10 do plainStart := intToHexString(rand(2^64)()): key := intToHexString(rand(2^64)()): bitChangeList := sort(bitCounter2(plainStart, key)); listMean := evalf(stats[describe, mean](bitChangeList)); listSD := evalf(stats[describe, standarddeviation](bitChangeList)): print(plainStart, key, listMean, listSD); end do:

2) Do the analysis above on 20 randomly chosen pairs of plaintexts and keywords. What is the 95% confidence interval for the means of number times a bit is on? In how many of the 20 cases does the mean fall in the confidence interval?

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.