# DEStools.py David MacQuigg 11-Feb-2010 ''' Tools for working with DES. This module is intended to make simulations of DES very easy. The student is expected to focus on understanding how the DES works, not on the messy details of converting data copied from a web page, etc. The functions that students are asked to write are shown here syntactically correct, but full of subtle errors to make mindless copying and debugging more work than understanding the algorithm, and writing the functions from scratch. Raw data cut-and-paste from FIPS PUB 46-2 (http://www.itl.nist.gov/fipspubs/fip46-2.htm) Initial Permutation: 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 and its inverse: 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 E BIT-SELECTION TABLE 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 S-boxes: S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 O 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 O 6 13 S2 15 1 8 14 6 11 3 4 9 7 2 13 12 O 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 O 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 O 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 O 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 O 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 O 14 11 8 12 7 1 14 2 13 6 15 O 9 10 4 5 3 S6 12 1 10 15 9 2 6 8 O 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 O 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 The primitive function P is: 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 ~''' ''' The first step is to convert all the "raw data" to usable forms. For example, the initial permutation table is a multiline text string full of tabs, spaces and newlines. We need a simple list of ints. Python is good at these conversions. ~''' s = ''' 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 ''' IP = [int(ss) for ss in s.split()] # [58, 50, 42, 34, 26, ... 15, 7] # default for split is any whitespace IPinv = 64 * [0] # Inverse of IP for n in range(64): IPinv[IP[n] - 1] = n + 1 # [40, 8, 48, 16, 56, ... 57, 25] s = ''' 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 ''' Etable = [int(ss) for ss in s.split()] # [32, 1, 2, 3, 4, 5, 4, 5, ... 32, 1] ''' The S-boxes have a little extra twist. Some, but not all, of the zeroes in the standard as published on the Internet appear as letter upper-case O, not numeral 0. The string method "replace" will take care of this. ~''' s = ''' 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 O 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 O 6 13 ''' S1 = [int(ss) for ss in s.replace('O', '0').split()] # S-box 1 [14, 4, ... ] ''' It will also be handy to have these S-boxes in binary form, rather than lists of decimal integers. ~''' bits = [[0,0,0,0], [0,0,0,1], [0,0,1,0], [0,0,1,1], # for bit conversions [0,1,0,0], [0,1,0,1], [0,1,1,0], [0,1,1,1], [1,0,0,0], [1,0,0,1], [1,0,1,0], [1,0,1,1], [1,1,0,0], [1,1,0,1], [1,1,1,0], [1,1,1,1] ] Sb = 9 * [None] # Array to hold 8 Sboxes, S[0] not used. Sb[1] = [bits[n] for n in S1] # [[1, 1, 1, 0], [0, 1, 0, 0], ... ] # repeat for all S-boxes s = ''' 15 1 8 14 6 11 3 4 9 7 2 13 12 O 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 ''' S2 = [int(ss) for ss in s.replace('O', '0').split()] Sb[2] = [bits[n] for n in S2] s = ''' 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 O 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 ''' S3 = [int(ss) for ss in s.replace('O', '0').split()] Sb[3] = [bits[n] for n in S3] s = ''' 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 O 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 O 6 10 1 13 8 9 4 5 11 12 7 2 14 ''' S4 = [int(ss) for ss in s.replace('O', '0').split()] Sb[4] = [bits[n] for n in S4] s = ''' 2 12 4 1 7 10 11 6 8 5 3 15 13 O 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 O 14 11 8 12 7 1 14 2 13 6 15 O 9 10 4 5 3 ''' S5 = [int(ss) for ss in s.replace('O', '0').split()] Sb[5] = [bits[n] for n in S5] s = ''' 12 1 10 15 9 2 6 8 O 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 O 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 ''' S6 = [int(ss) for ss in s.replace('O', '0').split()] Sb[6] = [bits[n] for n in S6] s = ''' 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 ''' S7 = [int(ss) for ss in s.replace('O', '0').split()] Sb[7] = [bits[n] for n in S7] s = ''' 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 ''' S8 = [int(ss) for ss in s.replace('O', '0').split()] Sb[8] = [bits[n] for n in S8] # Permutation in f-function s = ''' 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 ''' Ptable = [int(ss) for ss in s.split()] # [16, 7, 20, 21, 29, ... 4, 25] ### Function Definitions ### def perm(N, bits, table): ''' Permute N bits using table. Bit numbering starts at 1. ''' return [bits[table[n] - 1] for n in range(N)] def Sbox(N, bits): ''' Given the box number and input bits, return 4 output bits. >>> Sbox(3, [1,0,0,1,0,1]) [1, 1, 0, 1] ''' row = 2*bits[0] + bits[5] col = 8*bits[1] + 4*bits[2] + 2*bits[3] + bits[4] return Sb[N][16*row + col] def E48(X): ''' Given a 32-bit input X, return a 48-bit output, using the Etable. >>> X = [i for i in range(1, 33)] # values will normally be binary >>> E48(X) # check against published table [32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15,\ 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28,\ 29, 28, 29, 30, 31, 32, 1] ''' return [X[Etable[i]-1] for i in range(48)] def pprint(X, bits=4, groups=8): ''' Pretty print bitlist X, 4 bits per group, 8 groups per row >>> pprint(X1) 1000 0000 0000 0000 0000 0000 0000 0000 1101 0000 0101 1000 0101 1011 1001 1110 ''' L = len(X) i = 0 # index in list X while i < L: # start another row row = ''; g = 1 # start a new row at group 1 gstop = i + bits while i < L: # append another digit row += str(X[i]) i += 1 if i == gstop: # group is complete if g < groups: # continue with another group g += 1 else: break row += ' ' # group separator gstop = i + bits # ready for next group print row def ppbits(B, nbits=4, groups=8): ''' Pretty print the bits from byte string B. >>> ppbits('/\xbc)\x1aW\r\xb5\xc4', 8) 00101111 10111100 00101001 00011010 01010111 00001101 10110101 11000100 ''' bitlist = [] for byte in B: n = ord(byte) # {0, 1, ... 255} q,r = divmod(n, 16) # left and right hex digits bitlist += bits[q] + bits[r] pprint(bitlist, bits=nbits, groups=groups) s1 = '/\xbc)\x1aW\r\xb5\xc4' def pp2(Bstring): bits = '' for byte in Bstring: n = ord(byte) bits += format(n, '0>8b') + ' ' return bits ### HW Problem 5 # Plaintext is all 0 except bit 57 (at index 56) XP = [0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 1,0,0,0, 0,0,0,0 ] # Key is all 0 K = [0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0 ] X0 = perm(64, XP, IP) # Initial permutation print "Plaintext:" pprint(XP) print "Initial permutation:" pprint(X0) L0 = X0[0:32] R0 = X0[32:64] L1 = R0 E = E48(R0) print "E48:" pprint(E, 6, 8) J = 48 * [0] # round key (need key schedule, use dummy for now) ### B = [E[n] ^ J[n] for n in range(48)] print "B:" pprint(B, 6, 8) C = 32 * [0] for box in range(8): boxnum = box + 1 # 1 ... 8 C[4*box: 4*(box+1)] = Sbox(boxnum, B[6*box: 6*(box+1)]) print "C:" pprint(C) f = perm(32, C, Ptable) # permute output of S-boxes print "f:" pprint(f) R1 = [L0[n] ^ f[n] for n in range(32)] print "L1R1:" X1 = L1 + R1 pprint(X1) ''' Plaintext: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1000 0000 Initial permutation X0: 0000 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 E48: 010000 000000 000000 000000 000000 000000 000000 000001 B: 010000 000000 000000 000000 000000 000000 000000 000001 C: 0011 1111 1010 0111 0010 1100 0100 0001 f: 1101 0000 0101 1000 0101 1011 1001 1110 L1R1: 1000 0000 0000 0000 0000 0000 0000 0000 1101 0000 0101 1000 0101 1011 1001 1110 >>> pprint(diff) # comparing L1R1 to X0, 16 bits are changed 1000 0000 0000 0000 0000 0000 0000 0000 0101 0000 0101 1000 0101 1011 1001 1110 ''' def round(Xin, RoundKey=48*[0]): ''' Execute one round of DES on a a 64-bit input Xin using a 48-bit key. Return the 64-bit output in the same form as Xin, ready for another round. ''' L0 = Xin[0:32]; R0 = Xin[32:64] L1 = R0 E = E48(R0) J = RoundKey B = [E[n] ^ J[n] for n in range(48)] C = 32 * [0] for box in range(8): boxnum = box + 1 # 1 ... 8 C[4*box: 4*(box+1)] = Sbox(boxnum, B[6*box: 6*(box+1)]) f = perm(32, C, Ptable) R1 = [L0[n] ^ f[n] for n in range(32)] return L1 + R1 def DES(XP, Key=64*[0]): ''' Encrypt one 64-bit block of plaintext. ''' X = perm(64, XP, IP) # initial permutation for n in range(16): # 16 rounds X = round(X) X = X[32:64] + X[0:32] # final swap Xout = perm(64, X, IPinv) # final permutation return Xout ''' >>> C = DES(XP) >>> pprint(C) 0010 1111 1011 1100 0010 1001 0001 1010 0101 0111 0000 1101 1011 0101 1100 0100 Check this against the result from PyCrypto: >>> from Crypto.Cipher import DES >>> Key = '\x00\x00\x00\x00\x00\x00\x00\x00' >>> obj = DES.new(Key) >>> plain = '\x00\x00\x00\x00\x00\x00\x00\x80' >>> ciph = obj.encrypt(plain) >>> ciph '/\xbc)\x1aW\r\xb5\xc4' # 8 bytes >>> ppbits(ciph) 0010 1111 1011 1100 0010 1001 0001 1010 0101 0111 0000 1101 1011 0101 1100 0100 ~''' ## Setup for HW problem 5, finding the diffs from one bit input change. x = X0 # test case, plaintext bit 57 = 1 Xlist = [X0] for rnd in range(8): x = round(x) Xlist.append(x) print "Round:", rnd + 1 pprint(x) Xlist1 = Xlist x = 64 * [0] # comparison case, plaintext all 0 Xlist = [x] for rnd in range(8): x = round(x) Xlist.append(x) print "Round:", rnd + 1 pprint(x) Xlist0 = Xlist def diffs(n): df = [Xlist1[n][i] ^ Xlist0[n][i] for i in range(64)] pprint(df) print df.count(1) # number of bits that differ ''' HW Problem 5: a) Inputs to S-boxes differ in two bits when bit 57 of plaintext is 1. b) The first round changes 16 bits. all but one in the right half. With all 0 plaintext: Round: 1 0000 0000 0000 0000 0000 0000 0000 0000 1101 1000 1101 1000 1101 1011 1011 1100 Round: 2 1101 1000 1101 1000 1101 1011 1011 1100 1110 0111 0011 1010 1110 1101 0100 1111 Round: 3 1110 0111 0011 1010 1110 1101 0100 1111 0101 1011 1111 1010 0110 1011 1010 0110 Round: 4 0101 1011 1111 1010 0110 1011 1010 0110 0101 1110 0100 0101 1110 0010 0101 0111 With bit 57 of the plaintext changed to 1: Round: 1 1000 0000 0000 0000 0000 0000 0000 0000 1101 0000 0101 1000 0101 1011 1001 1110 Round: 2 1101 0000 0101 1000 0101 1011 1001 1110 0010 0010 1111 0111 0011 0000 1110 1010 Round: 3 0010 0010 1111 0111 0011 0000 1110 1010 0111 0001 1101 1010 1100 0010 0100 0101 Round: 4 0111 0001 1101 1010 1100 0010 0100 0101 1001 1101 0100 1000 0010 1110 1100 1001 diffs: >>> diffs(1) 1000 0000 0000 0000 0000 0000 0000 0000 0000 1000 1000 0000 1000 0000 0010 0010 6 >>> diffs(2) 0000 1000 1000 0000 1000 0000 0010 0010 1100 0101 1100 1101 1101 1101 1010 0101 24 >>> diffs(3) 1100 0101 1100 1101 1101 1101 1010 0101 0010 1010 0010 0000 1010 1001 1110 0011 32 >>> diffs(4) 0010 1010 0010 0000 1010 1001 1110 0011 1100 0011 0000 1101 1100 1100 1001 1110 29 c) Changing bit 57 of the plaintext causes 6 bits to differ after round 1, 24 bits after round 2, 32 bits after round 3, and staying around 32 thereafter. This shows completion of the avalache effect by round 3, since a completely random choice of bits would differ, on average by 32. ~'''