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

a guest
Aug 26th, 2020
78
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # # AES 1 round 1 data attacks
2.
3. # First, AES boilerplate and generate subkeys, plaintext and ciphertext.
4.
5. from sage.all import *
6. from aes import AES
7. from hashlib import md5
8.
9. def transpose(s):
10.     return [s[4*j+i] for i in range(4) for j in range(4)]
11.
12. A = AES()
13. key = list(md5(b"key key").digest())
14. expkey = A.expandKey(key, 16, 32)
15. rk1 = transpose(expkey[:16])
16. rk2 = transpose(expkey[16:32])
17. rkp = A.mixColumns(rk2[::], True)
18.
19. pt = list(md5(b"plaintext").digest())
20.
21. ct = list(pt)
23. ct = A.subBytes(ct[::], False)
24. ct = A.shiftRows(ct[::], False)
25.
26. if 0: # equivalent
28.     ct = A.mixColumns(ct[::], False)
29. else:
30.     ct = A.mixColumns(ct[::], False)
32.
33. print("pt", pt)
34. print("key", key)
35. print("ct", ct)
36. print("rk1", rk1)
37. print("rk2", rk2)
38.
39. ctp = A.mixColumns(ct[::], True)
40.
41.
42. # Useful functions for attacks: propagation through SB relation, xor of vectors, MC shenanigans.
43.
44. def backward(i):
45.     y = i // 4
46.     x = (i + y) % 4
47.     j = y*4 + x
48.     k[j] = A.rsbox[ctp[i] ^^ kp[i]] ^^ pt[j]
49.
50. def forward(i):
51.     y = i // 4
52.     x = (i - y) % 4
53.     j = y*4 + x
54.     kp[j] = A.sbox[pt[i] ^^ k[i]] ^^ ctp[j]
55.
56. def xor(a, b):
57.     return [aa ^^ bb for aa, bb in zip(a, b)]
58.
59. R.<x> = GF(2)[]
60. F = GF(2**8, name='a', modulus=x^8+x^4+x^3+x+1)
61. 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]])
62.
63. def MC_permuted(perm):
64.     C = copy(identity_matrix(F, 4).augment(~MC))
65.     C.permute_columns(Permutation([i + 1 for i in perm]))  # sage permutations indexed from 1! argh
66.     return copy(C.echelon_form())
67.
68. def mat_mul(mat, v):
69.     v = [F.fetch_int(a) for a in v]
70.     v = mat * vector(v)
71.     v = [a.integer_representation() for a in v]
72.     return v
73.
74.
75. # Method: guess \$k'_1\$ and one extra byte (5 total) to work with \$k_0\$ and \$w\$.
76.
77. # precompute magic matrices
78. M1 = MC_permuted([0, 1, 4, 7,  2, 3, 5, 6])[:,4:]
79.
80. # precomputation from pt/ct
81. # cond 1: x + a * y = b
82. # cond 2: S[y] ^ t = Sinv(z ^ ctp[ci]) ^ pt[pi]
83. from collections import defaultdict
84. fa = F.fetch_int(11)
85. precomp = defaultdict(list)
86. for b in range(256):
87.     fb = F.fetch_int(b)
88.     xys = []
89.     for y in range(256):
90.         fy = F.fetch_int(y)
91.         fx = fb - fa * fy
92.         x = fx.integer_representation()
93.         xys.append((x, y))
94.     for x, y in xys:
95.         t = A.rsbox[x ^^ ctp[7]] ^^ pt[4] ^^ A.sbox[y]
96.         precomp[b,t].append((x, y))
97.
98. print("precomp ok")
99.
100. # subkey recovery progress
101. k = [None] * 16
102. kp = [None] * 16
103.
104. # guesses (5 bytes)
105. kp[::4] = rkp[::4]
106. kp[3] = rkp[3]
107.
108. # work out
109. # step 1: use single S-Boxes
110. backward(0)
111. backward(3)
112. backward(4)
113. backward(8)
114. backward(12)
115.
116. # step 2: use K0 and w relation
117. k0t = A.mixColumn(kp[::4], False)
118.
119. k[7] = A.rsbox[k[0] ^^ k0t[0] ^^ 1]
120. k[8] = A.sbox[k[15]] ^^ k0t[2]
121. k[12] = A.sbox[k[3]] ^^ k0t[3]
122. forward(7)
123. forward(8)
124. forward(12)
125.
126. # step 3: guess 1 and filter 1 at the same time via precomp
127. fb  = F.fetch_int(9) * F.fetch_int(k[3])
128. fb += F.fetch_int(14) * F.fetch_int(k[7])
129. fb += F.fetch_int(13) * F.fetch_int(k[15])
130. fb += F.fetch_int(kp[6])
131. b = fb.integer_representation()
132.
133. for x, y in precomp[b,k0t[1]]:
134.     print("x fixed", x, "y", y)
135.     k[11] = y
136.     k[4] = A.sbox[k[11]] ^^ k0t[1]
137.     kp[7] = x
138.     forward(4)
139.     forward(11)
140.     backward(7)
141.
142.     delta_kp23 = A.mixColumn([k[3], k[7], k[11], k[15]], True)
143.
144.     kp[2] = delta_kp23[0] ^^ kp[3]
145.     assert kp[7] == delta_kp23[1] ^^ kp[6]
146.     kp[11] = delta_kp23[2] ^^ kp[10]
147.     backward(2)
148.     backward(11)
149.
150.     sol = mat_mul(M1, [kp[8]^^kp[9], kp[12]^^kp[13], k[5], k[9]])
151.     kp[1] = kp[0] ^^ sol[0]
152.     kp[5] = kp[4] ^^ sol[1]
153.     k[13] = sol[3]
154.     backward(1)
155.     backward(5)
156.     forward(13)
157.     if k[1] != sol[2]:  # filter
158.         continue
159.     kp[15] = delta_kp23[3] ^^ kp[14]
160.     backward(15)
161.     break
162. else:
163.     print("failed")
164.     raise
165.
166. assert k == rk1
167. assert kp == rkp
168.
169. print("WIN!")
RAW Paste Data