{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Times " 1 12 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE " Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 10 "Baby DES-2" }}{PARA 18 " " 0 "" {TEXT -1 26 "Differential Cryptanalysis" }}{PARA 19 "" 0 "" {TEXT -1 36 "\251Mike May, S.J., 2002, maymk@slu.edu" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 224 "To understand how to do DES, our book (by Trappe and Washingto n) uses a simplified DES-like system which we refer to as Baby DES. T his worksheet assumes that you have already worked through the first w orksheet on Baby DES. " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" } {TEXT 256 18 "Baby DES recalled." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "We recall the code from the first BabyDES worksheet that we need f or implementing Baby DES." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1704 "indexS1 := x -> substring(convert(convert(x+16, binary),string), 2..5):\nindexList1 := [seq(indexS1(i),i=0..15)]:\nindexList := matrix( [[seq(indexS1(i),i=0..7)],[seq(indexS1(8+i),i=0..7)]]):\nshowAsMatrix \+ := table -> map(y->table[y],indexList):\nroundKeyMaker := (keystring, \+ i)\n -> substring(cat(keystring, keystring), i..(i+7)):\nleftHalf \+ := String -> substring(String, 1..6):\nrightHalf := String -> substrin g(String, 7..12):\nexpander := String -> cat(substring(String,1..2), \+ \n substring(String,4), substring(String,3..4), \n substring(Str ing,3), substring(String,5..6)):\nXOR := (a,b) -> if (a=b) then \"0\" \+ else \"1\" fi:\nxorNbits := (a,b,N) -> \n cat(seq(XOR(substring(a,i), substring(b,i)),i=1..N)):\nSBoxa :=\n [\"101\", \"010\", \"001\", \+ \"110\", \"011\", \"100\", \"111\", \"000\",\n \"001\", \"100\", \+ \"110\", \"010\", \"000\", \"111\", \"101\", \"011\",\n \"100\", \+ \"000\", \"110\", \"101\", \"111\", \"001\", \"011\", \"010\",\n \+ \"101\", \"011\", \"000\", \"111\", \"110\", \"010\", \"001\", \"100\" ]:\nS1 := table([seq(indexList1[i]=SBoxa[i],i=1..16)]):\nS2 := table([ seq(indexList1[i]=SBoxa[i+16], i=1..16)]):\nSingleRound := proc(messSt ring, keyString, round)\n local roundKey, startL, startR, expandR, \+ SInput, SOutput:\n roundKey := roundKeyMaker(keyString, round):\n \+ startL := leftHalf(messString):\n startR := rightHalf(messString) :\n expandR := expander(startR):\n SInput := xorNbits(expandR, r oundKey,8):\n SOutput := \n cat(S1[substring(SInput,1..4)],S 2[substring(SInput,5..8)]):\n cat(startR, xorNbits(SOutput, startL, 6));\n end:\nBabyDES := proc(messString, keyString, numberRounds)\n \+ local temp, i:\n temp := messString:\n for i from 1 to numberR ounds do\n temp := SingleRound(temp, keyString,i) od:\n end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "keyString := \"110110001 \";\nmessageString := \"101101111001\";" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*keyStringGQ*1101100016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %.messageStringGQ-1011011110016\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "seq(BabyDES(messageString, keyString,i), i=1..4);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&Q-1110010001116\"Q-000111011001F$Q-011 001110100F$Q-110100010101F$" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 " " }{TEXT 257 69 "A Second Look at Differential Cryptanalysis for three round Baby DES." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 102 "In the first \+ worksheet on Baby DES we looked at Differential Cryptanalysis for thre e round Baby DES. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 236 "We used 4 words of chosen plaintext with the same righ t 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 t he round key that worked with all pairs. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 193 "In a second variation, we want to count the number of pairs with which a half of a round key can pos sibly work. We want to choose the half round key that works for the m aximum number of pairs." }}{PARA 0 "" 0 "" {TEXT -1 200 "(Since the co rrect key works for all pairs, this method will give the correct answe r. The advantage of the second method is that it generalizes to 4 rou nd Baby DES where we need to do some guessing.)" }}{PARA 0 "" 0 "" {TEXT -1 43 "We start with a key and 4 words to encrypt." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 258 47 "Preliminary work with pai rs of chosen plaintext" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "We start with the words that will be used for pairs." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 133 "keyString := \"110110001\":\nmess[1] := \"10110 1111001\":\nmess[2] := \"101100111001\":\nmess[3] := \"101111111001\": \nmess[4] := \"100101111001\":" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 192 "For each chosen plaintext word we produced the encrypted word, th e XOR of the left half of the plain text with the right half of the ci pher text, and the expanded left half of the cipher text." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 183 "for i from 1 to 4 do\n code[i] \+ := BabyDES(mess[i], keyString,3):\n R3L0[i] := xorNbits(leftHalf(me ss[i]),rightHalf(code[i]),6):\n EL3[i] := expander(leftHalf(code[i] )):\n end do:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 217 "For each pair o f 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 a lso XORed the R3L0 words to produce the difference in outputs." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 183 "for i from 1 to 3 do\nfor j from i+1 to 4 do\nEhat[i,j] := xorNbits(EL3[i], EL3[j],8);\nRLhat[i,j ] := xorNbits(R3L0[i], R3L0[j], 6);\nprint([i,j], Ehat[i,j], RLhat[i,j ]);\nend do: \nend do:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\" #Q)001010116\"Q'100001F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\" \"$Q)001010016\"Q'100111F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\" \"\"%Q)100101016\"Q'000110F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\" #\"\"$Q)000000106\"Q'000110F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\" \"#\"\"%Q)101111106\"Q'100111F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$ \"\"$\"\"%Q)101111006\"Q'100001F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 338 "Recall the \+ functions created in the last worksheet that let us XOR the S boxes wi th themselves shifted by the appropriate half of Ehat[i,j]. We also r ecall 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." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 619 "S1hatted := hatstring -> table([seq(indexList 1[i]=\n xorNbits(S1[indexList1[i]],S1[xorNbits(indexList1[i],hatstrin g,4)],3),i=1..16)]):\nS2hatted := hatstring -> table([seq(indexList1[i ]=\n xorNbits(S2[indexList1[i]],S2[xorNbits(indexList1[i],hatstring,4 )],3),i=1..16)]):\ngoodSvals := proc(hattedSBox, hatVal)\n local go odValues, i, j:\n goodValues :=\{\}:\n for i from 1 to 16 do\n \+ if (hattedSBox[indexList1[i]] = hatVal) then \n goodValues := goodValues union \{indexList1[i]\} end if:\n end do:\n goodV alues;\nend:\nshiftedVals := (goodValues, shiftVal) ->\n map(x->xorN bits(x,shiftVal,4), goodValues):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "For each of the 6 chosen plaintext pairs we then made a list of p ossible first and second halves of the third round key. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 449 "for i from 1 to 3 do\nfor j from i +1 to 4 do\nS1hat := S1hatted(substring(Ehat[i,j],1..4));\nS2hat := S2 hatted(substring(Ehat[i,j],5..8));\ns1 := shiftedVals(goodSvals(S1hat, substring(RLhat[i,j],1..3)), \n substring(expander(lef tHalf(code[i])),1..4));\ns2 := shiftedVals(goodSvals(S2hat, substring( RLhat[i,j],4..6)),\n substring(expander(leftHalf(code[i ])),5..8));\nprint([i,j, Ehat[i,j], RLhat[i,j]], s1, s2);\nend do;\nen d do;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7&\"\"\"\"\"#Q)001010116\"Q'1 00001F'<,Q%0000F'Q%0001F'Q%0010F'Q%0011F'Q%0100F'Q%0101F'Q%0110F'Q%011 1F'Q%1000F'Q%1010F'<$F-F2" }}{PARA 12 "" 1 "" {XPPMATH 20 "6%7&\"\"\" \"\"$Q)001010016\"Q'100111F'<,Q%0000F'Q%0001F'Q%0010F'Q%0011F'Q%0100F' Q%0101F'Q%0110F'Q%0111F'Q%1000F'Q%1010F'<(F*F-F/Q%1001F'F3Q%1100F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6%7&\"\"\"\"\"%Q)100101016\"Q'000110F'<$ Q%0110F'Q%1111F'<&Q%0011F'F*Q%1011F'Q%1110F'" }}{PARA 12 "" 1 "" {XPPMATH 20 "6%7&\"\"#\"\"$Q)000000106\"Q'000110F'<2Q%0000F'Q%0001F'Q% 0010F'Q%0011F'Q%0100F'Q%0101F'Q%0110F'Q%0111F'Q%1000F'Q%1001F'Q%1010F' Q%1011F'Q%1100F'Q%1101F'Q%1110F'Q%1111F'<$F+F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7&\"\"#\"\"%Q)101111106\"Q'100111F'<$Q%0110F'Q%1101F'<& Q%0011F'Q%0100F'Q%1010F'F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7&\"\"$ \"\"%Q)101111006\"Q'100001F'<$Q%0110F'Q%1101F'<$Q%0011F'Q%1111F'" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 240 "The last step was to intersect th e sets of allowable halves of the round key to find the round key.\nLo oking at the (1,4) and (2,4) pairs we see that the first 4 bits are 01 10. Using the same pair of pairs the second four bits must be 0011." }}{PARA 0 "" 0 "" {TEXT -1 224 "This time we would like to look at the number of pairs of chosen plaintext allow a given half of the round k ey. Obviously the correct key halves will show up all 6 times and the incorrect key halves will show up less often." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 725 "half1Count := table([seq(indexList1[i]=0,i=1. .16)]):\nhalf2Count := table([seq(indexList1[i]=0,i=1..16)]):\nfor i f rom 1 to 3 do\nfor j from i+1 to 4 do\nS1hat := S1hatted(substring(Eha t[i,j],1..4));\nS2hat := S2hatted(substring(Ehat[i,j],5..8));\ns1 := s hiftedVals(goodSvals(S1hat, substring(RLhat[i,j],1..3)), \n sub string(expander(leftHalf(code[i])),1..4));\nfor k from 1 to nops(s1) d o\nhalf1Count[s1[k]]:= half1Count[s1[k]]+1 end do:\ns2 := shiftedVals( goodSvals(S2hat, substring(RLhat[i,j],4..6)), \n substring(expa nder(leftHalf(code[i])),5..8));\nfor k from 1 to nops(s2) do\nhalf2Cou nt[s2[k]]:= half2Count[s2[k]]+1 end do:\nend do;\nend do;\nhalf1Count \+ = showAsMatrix(half1Count);\nhalf2Count = showAsMatrix(half2Count);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half1CountG-%'matrixG6#7$7*\"\"$F* F*F*F*F*\"\"'F*7*F*\"\"\"F*F-F-F*F-\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2CountG-%'matrixG6#7$7*\"\"\"F*\"\"!\"\"'F*F*F*F+7*F*F*\" \"#F*F*F*F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "Once again we c onclude that the first half of the round key is 0110 and the second ha lf of the round key is 0011." }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 67 "Differential Cryptanalysis with randomly chosen pairs of plaintext." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 446 "When we look at four round Baby DES we will want to use a collection randomly chosen pairs of plainte xt 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 w ords with the second half the same. This simplifies to being able to \+ generate random 6 bit strings that we put together appropriately." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "rand6Bits := () -> substring (convert(convert(rand(64)()+64,binary),string),2..7):\nrand6Bits();" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#Q'0110016\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 190 "randPair1 := proc()\n local left1, left2, ri ght:\n left1 := rand6Bits():\n left2 := rand6Bits():\n right \+ := rand6Bits():\n [cat(left1, right), cat(left2, right)];\nend:\nra ndPair1();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$Q-0101100010116\"Q-100 001001011F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "For each such ran dom pair, we want the plaintext words, the ciphertext words, and the v alues we referred to as EL3hat and R3L0hat." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 583 "SboxPair := proc(wordpair, keystring)\n local \+ wordA, wordB, codeA, codeB, R3L0A, R3L0B,\n EL3A, EL3B, Ehat, \+ RLhat:\n wordA := wordpair[1];\n wordB := wordpair[2];\n code A := BabyDES(wordA, keystring,3);\n codeB := BabyDES(wordB, keystri ng,3);\n R3L0A := xorNbits(leftHalf(wordA),rightHalf(codeA),6):\n \+ R3L0B := xorNbits(leftHalf(wordB),rightHalf(codeB),6):\n EL3A := \+ expander(leftHalf(codeA));\n EL3B := expander(leftHalf(codeB));\n \+ Ehat := xorNbits(EL3A, EL3B,8);\n RLhat := xorNbits(R3L0A, R3L0B, 6);\n [wordA, codeA, wordB, codeB, Ehat, RLhat];\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "for i from 1 to 2 do\nSboxPair(rand Pair1(),keyString)\nend do;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7(Q-000 0000001016\"Q-101100100100F%Q-001010000101F%Q-011000100000F%Q)11101000 F%Q'001110F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7(Q-1010001000016\"Q-0 10010000011F%Q-100001100001F%Q-110100001101F%Q)10101010F%Q'000111F%" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 167 "We can now test this method of \+ cryptanalysis by running it 5 times on 20 randomly chosen pairs of pla intext with where the second half of words in a pair are the same." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 911 "for j from 1 to 5 do\n ha lf1Count := table([seq(indexList1[i]=0,i=1..16)]):\n half2Count := ta ble([seq(indexList1[i]=0,i=1..16)]):\n for i from 1 to 20 do\n r andSboxPair := SboxPair(randPair1(),keyString):\n S1hat := S1hatt ed(substring(randSboxPair[5],1..4)):\n S2hat := S2hatted(substrin g(randSboxPair[5],5..8)):\n s1 := shiftedVals(goodSvals(S1hat, su bstring(randSboxPair[6],1..3)), \n substring(expander(lef tHalf(randSboxPair[2])),1..4));\n for k from 1 to nops(s1) do\n \+ half1Count[s1[k]]:= half1Count[s1[k]]+1 end do:\n s2 := s hiftedVals(goodSvals(S2hat, substring(randSboxPair[6],4..6)), \n \+ substring(expander(leftHalf(randSboxPair[2])),5..8));\n f or k from 1 to nops(s2) do\n half2Count[s2[k]]:= half2Count[s 2[k]]+1 end do:\n end do:\n print(half1Count = showAsMatrix(half1Cou nt));\n print(half2Count = showAsMatrix(half2Count));\nend do:" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half1CountG-%'matrixG6#7$7*\"\"(F*F *\"\"'\"#7\"#6\"#?\"\")7*\"\"#\"\"%F2\"\"$F+\"\"&F+F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2CountG-%'matrixG6#7$7*\"\"$F*\"\"%\"#?F*F* \"\"'F-7*F*\"\"\"F*\"\"(\"\"#F*F0\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half1CountG-%'matrixG6#7$7*\"\"%\"\"&F+F+\"#6\"#8\"#?\"\"(7*F +F*\"\")F*F/\"\"'F2F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2Count G-%'matrixG6#7$7*\"\"(F*\"\"$\"#?F*\"\"#\"\"%\"\"*7*\"\"'F+\"\"&F+F2F+ F*F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half1CountG-%'matrixG6#7$7* \"\")F*F*\"\"(\"\"*\"#9\"#?\"#57*\"\"%\"\"&F2F2\"\"'F+F+F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2CountG-%'matrixG6#7$7*\"\")\"\"&\"\" (\"#?F*F+F,F,7*\"\"'F*F,F,F+F/\"#6\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half1CountG-%'matrixG6#7$7*\"\"*\"#6F+\"#5F+\"#;\"#?\"#77*\" \"%F1\"\"$\"\"&F3\"\"#F1F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2 CountG-%'matrixG6#7$7*\"\"'\"\"$\"\"\"\"#?\"\"%\"\"#F/\"\"&7*F+F/F.F/F *F.F.F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half1CountG-%'matrixG6#7 $7*\"\")\"\"'F+\"\"&F*\"\"(\"#?\"\"*7*F-F,F-F,F,F+\"\"%F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2CountG-%'matrixG6#7$7*\"\"'\"\"$F+\"#?F +\"\"#\"\"&F*7*\"\"%F*\"\")F+\"\"(F-F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "In each case we see that the first half of the round key \+ is 0110 and the second half is 0011." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 259 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "1) Use the techn iques above to find the third round key for a three round Baby DES enc ryption when the key is 011001110." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 50 "Differenti al Cryptanalysis for four round Baby DES" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 138 "We are ready to turn our attention to four round Baby DE S. We will modify the procedure used above to find the most likely 4t h round key." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "keyString : = \"101100101\";\nR4Key := roundKeyMaker(keyString,4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*keyStringGQ*1011001016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&R4KeyGQ)100101106\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 216 "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 pai r of words that should be useful for differential cryptanalysis with t hree round Baby DES." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "S1 \+ = showAsMatrix(S1);\nS2 = showAsMatrix(S2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%#S1G-%'matrixG6#7$7*Q$1016\"Q$010F+Q$001F+Q$110F+Q$01 1F+Q$100F+Q$111F+Q$000F+7*F-F0F.F,F2F1F*F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%#S2G-%'matrixG6#7$7*Q$1006\"Q$000F+Q$110F+Q$101F+Q$11 1F+Q$001F+Q$011F+Q$010F+7*F.F1F,F/F-F2F0F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 264 "The book notes that the differences in the S box outputs are easiest to predict if the differences in the S box inputs are 001 1 and 1100 respectively, with the most likely answer being 011010 whic h occurs 3/8 of the time rather than the predicted 1/64 of the time." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 111 "S1hat := S1hatted(\"0011 \"):\nS2hat := S2hatted(\"1100\"):\nS1hat = showAsMatrix(S1hat);\nS2ha t = showAsMatrix(S2hat);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S1hatG- %'matrixG6#7$7*Q$0116\"F*F*F*F*F*F*F*7*F*Q$010F+F-F*F*F-F-F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG-%'matrixG6#7$7*Q$0106\"F*Q$111F+Q$ 001F+F*F*Q$011F+Q$101F+7*F*F*F.F/F*F*F,F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 385 "Since we want the differences in the R1s to be 000000, w e want the differences in the L0s to be 011010. We also want the expa nsion 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 R 0s to be 001100. Thus we need to be able to produce random pairs of p laintext with the specified difference in halves." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 206 "randPair2 := proc(shift1, shift2)\n loca l left1, right1:\n left1 := rand6Bits():\n right1 := rand6Bits() :\n [cat(left1, right1), \n cat(xorNbits(left1,shift1,6), xorNb its(right1,shift2,6))];\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "randPair2(\"011010\", \"001100\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$Q-0111110101106\"Q-000101011010F%" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 577 "SboxPair2 := proc(wordpair,L1shift, keystring)\n \+ local wordA, wordB, codeA, codeB, R4L1A, R4L1B,\n EL4A, EL4B , Ehat, RLhat:\n wordA := wordpair[1];\n wordB := wordpair[2];\n codeA := BabyDES(wordA, keystring,4);\n codeB := BabyDES(wordB, keystring,4);\n R4L1A := xorNbits(rightHalf(codeA),\"000000\",6): \n R4L1B := xorNbits(rightHalf(codeB),L1shift,6):\n EL4A := expa nder(leftHalf(codeA));\n EL4B := expander(leftHalf(codeB));\n Eh at := xorNbits(EL4A, EL4B,8);\n RLhat := xorNbits(R4L1A, R4L1B, 6); \n [wordA, codeA, wordB, codeB, Ehat, RLhat];\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "for i from 1 to 2 do\nSboxPair2(ran dPair2(\"011010\", \"001100\"),\"001100\",keyString)\nend do;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7(Q-0101000011006\"Q-111100100001F%Q-0 01110000000F%Q-110111110010F%Q)00010111F%Q'011111F%" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7(Q-1000111010106\"Q-100100100000F%Q-111001100110F%Q- 111111100110F%Q)01010111F%Q'001010F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "Now we are ready to test 100 pairs of words to see the most lik ely halves for the fourth round key." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 900 "half1Count := table([seq(indexList1[i]=0,i=1..16)]): \nhalf2Count := table([seq(indexList1[i]=0,i=1..16)]):\nfor i from 1 t o 100 do\n randSboxPair := SboxPair2(randPair2(\"011010\", \"0011 00\"),\"001100\",keyString):\n S1hat := S1hatted(substring(randSb oxPair[5],1..4)):\n S2hat := S2hatted(substring(randSboxPair[5],5 ..8)):\n s1 := shiftedVals(goodSvals(S1hat, substring(randSboxPai r[6],1..3)), \n substring(expander(leftHalf(randSboxPair[ 2])),1..4));\n for k from 1 to nops(s1) do\n half1Count[ s1[k]]:= half1Count[s1[k]]+1 end do:\n s2 := shiftedVals(goodSval s(S2hat, substring(randSboxPair[6],4..6)), \n substring(e xpander(leftHalf(randSboxPair[2])),5..8));\n for k from 1 to nops (s2) do\n half2Count[s2[k]]:= half2Count[s2[k]]+1 end do:\nen d do:\nprint(half1Count = showAsMatrix(half1Count));\nprint(half2Count = showAsMatrix(half2Count));\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+ half1CountG-%'matrixG6#7$7*\"\"%\"\"$\"\"(\"\"'F-F+F*F*7*\"#L\"#e\"#P \"#J\"#]\"#R\"#S\"#N" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+half2CountG -%'matrixG6#7$7*\"#B\"#6\"\"&\"#7\"\")F-\"#T\"#87*F+F+\"#=\"# " 0 "" {MPLTEXT 1 0 0 "" }}}} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }