Guest User

AES key recovery 1 round 1 data (2^40)

a guest
Aug 26th, 2020
49
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from sage.all import *
  2. from aes import AES
  3. from hashlib import md5
  4.  
  5. def transpose(s):
  6.     return [s[4*j+i] for i in range(4) for j in range(4)]
  7.  
  8. A = AES()
  9. key = list(md5(b"key key").digest())
  10. expkey = A.expandKey(key, 16, 32)
  11. rk1 = transpose(expkey[:16])
  12. rk2 = transpose(expkey[16:32])
  13. rkp = A.mixColumns(rk2[::], True)
  14.  
  15. pt = list(md5(b"plaintext").digest())
  16.  
  17. ct = list(pt)
  18. ct = A.addRoundKey(ct[::], rk1)
  19. ct = A.subBytes(ct[::], False)
  20. ct = A.shiftRows(ct[::], False)
  21.  
  22. if 0: # equivalent
  23.     ct = A.addRoundKey(ct[::], rkp)
  24.     ct = A.mixColumns(ct[::], False)
  25. else:
  26.     ct = A.mixColumns(ct[::], False)
  27.     ct = A.addRoundKey(ct[::], rk2)
  28.  
  29. print("pt", pt)
  30. print("key", key)
  31. print("ct", ct)
  32. print("rk1", rk1)
  33. print("rk2", rk2)
  34.  
  35. ctp = A.mixColumns(ct[::], True)
  36.  
  37. def backward(i):
  38.     y = i // 4
  39.     x = (i + y) % 4
  40.     j = y*4 + x
  41.     k[j] = A.rsbox[ctp[i] ^^ kp[i]] ^^ pt[j]
  42.  
  43. def forward(i):
  44.     y = i // 4
  45.     x = (i - y) % 4
  46.     j = y*4 + x
  47.     kp[j] = A.sbox[pt[i] ^^ k[i]] ^^ ctp[j]
  48.  
  49. def xor(a, b):
  50.     return [aa ^^ bb for aa, bb in zip(a, b)]
  51.  
  52. R.<x> = GF(2)[]
  53. F = GF(2**8, name='a', modulus=x^8+x^4+x^3+x+1)
  54. MC = matrix(F, 4, 4, [F.fetch_int(a) for a in [2,3,1,1,  1,2,3,1,   1,1,2,3,   3,1,1,2]])
  55.  
  56. def MC_permuted(perm):
  57.     C = copy(identity_matrix(F, 4).augment(~MC))
  58.     C.permute_columns(Permutation([i + 1 for i in perm]))  # sage permutations indexed from 1! argh
  59.     return copy(C.echelon_form())
  60.  
  61. def mat_mul(mat, v):
  62.     v = [F.fetch_int(a) for a in v]
  63.     v = mat * vector(v)
  64.     v = [a.integer_representation() for a in v]
  65.     return v
  66.  
  67. if 0: # method 1 (6 bytes guess)
  68.     # subkey recovery progress
  69.     k = [None] * 16
  70.     kp = [None] * 16
  71.  
  72.     # guesses (6 bytes)
  73.     k[2::4] = rk1[2::4]
  74.     k[3] = rk1[3]
  75.     k[11] = rk1[11]
  76.  
  77.     # precompute magic matrices
  78.     M1 = MC_permuted([7, 1, 2, 3, 4, 5, 6, 0])[:,4:]
  79.     M2 = MC_permuted([0, 1, 2, 4, 3, 5, 6, 7])[:,4:]
  80.  
  81.     # work out
  82.     # step 1: use single S-Boxes
  83.     forward(2)
  84.     forward(6)
  85.     forward(10)
  86.     forward(14)
  87.     forward(3)
  88.     forward(11)
  89.  
  90.     # step 2: use KS columns 1-2 relation
  91.     # MC(k1' + k2') = k2
  92.     delta = A.mixColumn(k[2::4], True)
  93.     kp[1] = delta[0] ^^ kp[2]
  94.     kp[6] = delta[1] ^^ kp[5]
  95.     kp[10] = delta[2] ^^ kp[9]
  96.     backward(1)
  97.     backward(6)
  98.     backward(10)
  99.  
  100.     # step 3: use KS columns 2-3 relation (tricky)
  101.     # MC(k2' + k3') = k3
  102.     v = mat_mul(M1, (k[3], k[7], k[11], kp[2] ^^ kp[3]))
  103.     k[15] = v[0]
  104.     forward(15)
  105.     kp[7] = v[1] ^^ kp[6]
  106.     kp[11] = v[2] ^^ kp[10]
  107.     kp[14] = v[3] ^^ kp[15]
  108.     backward(7)
  109.     backward(11)
  110.     backward(14)
  111.  
  112.     # step 4: use KS columns 1-2 relation again
  113.     # MC(k1' + k2') = k2
  114.     kp[13] = delta[3] ^^ kp[14]
  115.     backward(13)
  116.  
  117.     word = [A.sbox[v] for v in (k[7] ^^ 1, k[11], k[15], k[3])]
  118.     kp[4] = k[4] ^^ word[1]
  119.  
  120.     # step 5: use KS non linear word and KS columns 0-1 relation
  121.     # MC(k0') = k0 + word
  122.     word = [A.sbox[v] for v in (k[7] ^^ 1, k[11], k[15], k[3])]
  123.     v = mat_mul(M2, (kp[12], word[1] ^^ k[4], word[2] ^^ k[8], word[3] ^^ k[12]))
  124.     kp[0] = v[0]
  125.     kp[4] = v[1]
  126.     backward(0)
  127.     backward(4)
  128.  
  129.     assert k == rk1 == transpose(list(key))
  130.     assert kp == rkp
  131.     print("WIN!")
  132.  
  133.  
  134. # method 2: 5 bytes guess
  135.  
  136. # precompute magic matrices
  137. M1 = MC_permuted([0, 1, 4, 7,  2, 3, 5, 6])[:,4:]
  138.  
  139. # precomputation from pt/ct
  140. # cond 1: x + a * y = b
  141. # cond 2: S[y] ^ t = Sinv(z ^ ctp[ci]) ^ pt[pi]
  142. from collections import defaultdict
  143. fa = F.fetch_int(11)
  144. precomp = defaultdict(list)
  145. for b in range(256):
  146.     fb = F.fetch_int(b)
  147.     xys = []
  148.     for y in range(256):
  149.         fy = F.fetch_int(y)
  150.         fx = fb - fa * fy
  151.         x = fx.integer_representation()
  152.         xys.append((x, y))
  153.     for x, y in xys:
  154.         t = A.rsbox[x ^^ ctp[7]] ^^ pt[4] ^^ A.sbox[y]
  155.         precomp[b,t].append((x, y))
  156.        
  157. print("precomp ok")
  158.  
  159. # subkey recovery progress
  160. k = [None] * 16
  161. kp = [None] * 16
  162.  
  163. # guesses (5 bytes)
  164. kp[::4] = rkp[::4]
  165. kp[3] = rkp[3]
  166.  
  167. # work out
  168. # step 1: use single S-Boxes
  169. backward(0)
  170. backward(3)
  171. backward(4)
  172. backward(8)
  173. backward(12)
  174.  
  175. # step 2: use K0 and w relation
  176. k0t = A.mixColumn(kp[::4], False)
  177.  
  178. k[7] = A.rsbox[k[0] ^^ k0t[0] ^^ 1]
  179. k[8] = A.sbox[k[15]] ^^ k0t[2]
  180. k[12] = A.sbox[k[3]] ^^ k0t[3]
  181. forward(7)
  182. forward(8)
  183. forward(12)
  184.  
  185. # step 3: guess 1 and filter 1 at the same time via precomp
  186. fb  = F.fetch_int(9) * F.fetch_int(k[3])
  187. fb += F.fetch_int(14) * F.fetch_int(k[7])
  188. fb += F.fetch_int(13) * F.fetch_int(k[15])
  189. fb += F.fetch_int(kp[6])
  190. b = fb.integer_representation()
  191.  
  192. for x, y in precomp[b,k0t[1]]:
  193.     print("try x", x, "y", y)
  194.     k[11] = y
  195.     k[4] = A.sbox[k[11]] ^^ k0t[1]
  196.     kp[7] = x
  197.     forward(4)
  198.     forward(11)
  199.     backward(7)
  200.    
  201.     delta_kp23 = A.mixColumn([k[3], k[7], k[11], k[15]], True)
  202.    
  203.     kp[2] = delta_kp23[0] ^^ kp[3]
  204.     assert kp[7] == delta_kp23[1] ^^ kp[6]
  205.     kp[11] = delta_kp23[2] ^^ kp[10]
  206.     backward(2)
  207.     backward(11)
  208.    
  209.     sol = mat_mul(M1, [kp[8]^^kp[9], kp[12]^^kp[13], k[5], k[9]])
  210.     kp[1] = kp[0] ^^ sol[0]
  211.     kp[5] = kp[4] ^^ sol[1]
  212.     k[13] = sol[3]
  213.     backward(1)
  214.     backward(5)
  215.     forward(13)
  216.     if k[1] != sol[2]:  # filter, can be made stronger if needed
  217.         continue
  218.     kp[15] = delta_kp23[3] ^^ kp[14]
  219.     backward(15)
  220.     break
  221. else:
  222.     print("failed")
  223.     raise
  224.    
  225. assert k == rk1 == transpose(list(key))
  226. assert kp == rkp
  227. print("WIN!")
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×