square attack

发表于 更新于

对对称密码不是很了解，所以对着 https://www.davidwong.fr/blockbreakers/ 了解了一下 AES 和对其的square attack

square attack 首先发现于分组密码 square，其利用了分组密码加密过程中的一些奇怪特性来实施攻击。

一般来说，完全的 10 轮情况下的 AES 目前并没有任何有效的攻击方式。因此我们可以考虑研究低轮的情况，而 square attack 通过观察前 3 轮，通过扩展，可以破解掉 4、5、6 轮的情况。其中 4 轮的攻击是简单的，可以通过家用笔记本快速的实现。

AES 概述

在开始描述 square attack 之前，我们应该先简单了解一下 AES 原理。

这里仅仅讨论 AES-128

轮密钥扩展

为了完成 10 轮的加密，AES-128 需要扩展出 11 个 keys，为了完成这些操作，我们需要一个 KeyExpansion 函数，为了实现这个函数，需要如下三个子函数：

  • RotWord
  • SubWord
  • Rcon

RotWord

RotWord 特别简单，就是将 4 个 bytes 左移一位

[1234]⟹[2341]\begin{bmatrix}1\\2\\3\\4\end{bmatrix}\Longrightarrow\begin{bmatrix}2\\3\\4\\1\end{bmatrix}

SubWord

SubWord 和 RotWord 一样，也是接收 4 个字节的输入，然后根据一个表格，进行查表替换，这个表格我们称之为 Sbox，其定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Sbox = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

其中最高位表示行，最低位表示列

example:

  • 02→7702\rightarrow77
  • 31→c731\rightarrow c7
  • f8→41f8\rightarrow41

Rcon

Rcon 是轮密钥扩展中用于引入非线性的一组轮常量，形式为一个 4 字节的 word，其中只有第一个字节非零：

Rcon[i]=[xi,0,0,0]\text{Rcon}[i] = [x^i,0,0,0]

其中 xix^i 的计算在有限域 GF(28)\text{GF}(2^8) 中进行，模多项式为：

m(x)=x8+x4+x3+x+1m(x) = x^8 + x^4 + x^3 + x + 1

其也可以通过查表来代替 Rcon 的表格为

1
2
3
4
5
6
Rcon = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)

Key Expansion

有了上面三个子函数，实现 KeyExpansion 就变得相当容易了。

首先 AES-128 接收一个 16 字节的密钥，其可以排成 4 列。例如对于 0x000102030405060708090a0b0c0d0e0f，可以写作如下这样 4 列的表格。

[0481215913261014371115]\begin{bmatrix}0&4&8&12\\1&5&9&13\\2&6&10&14\\3&7&11&15\end{bmatrix}

然后我们称这为第一轮密钥，对于每一轮的密钥，我们做如下的操作：

  • 取最后一列的字节进行 RotWord 和 SubWord 操作
  • 将其和第一列进行异或
  • 然后将得到的值和 Rcon(round) 再次异或，就得到新一轮的第一列了，其中 round 为轮数。

然后对于新的一轮密钥，我们还要得到剩下的三列，方法就是将前一列和上一轮的相同列进行异或。

我们可以使用 python 来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Sbox = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

Rcon = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)

def text_to_matrix(text):
    M = [[] for _ in range(4)]
    for i in range(16):
        M[i % 4] += [(text >> 8 * (15 - i)) & 0xff]
    return M

def KeyExpansion(key):
    round_keys = text_to_matrix(key)
    for i in range(4, 4 * 11):
        if i % 4:
            round_keys += [[round_keys[-4][j] ^ round_keys[-1][j] for j in range(4)]]
        else: round_keys += [[Sbox[round_keys[-1][1]] ^ round_keys[-4][0] ^ Rcon[i // 4],
                   Sbox[round_keys[-1][2]] ^ round_keys[-4][1],
                   Sbox[round_keys[-1][3]] ^ round_keys[-4][2],
                   Sbox[round_keys[-1][0]] ^ round_keys[-4][3],]]
    return round_keys

key = 0x000102030405060708090a0b0c0d0e0f
print(KeyExpansion(key))

组件

在 AES 的加密算法中，主要用到了四个组件，分别是：

  • SubBytes
  • ShiftRows
  • MixColumns
  • AddRoundKey

对于每一块的输入，都是 16 字节，和轮密钥一样会变成一个 4×44\times4 的矩阵。对于 AES 的每轮操作如下所示

round

AES 的 10 轮都是按照这个顺序走的（除了最后一轮会跳过 MixCloumns）

SubBytes

加密中的 SubWord 和轮密钥扩展的一致，就是把每一个输入替换成 Sbox 的值

ShiftRows

ShiftRows 就是对每一行做一次左移，其中第一行不变，第二行向左移动一次，第三行两次，第四行三次。如下所示：

[0481215913261014371115]⟹[0481259131101426153711]\begin{bmatrix}0&4&8&12\\1&5&9&13\\2&6&10&14\\3&7&11&15\end{bmatrix} \Longrightarrow\begin{bmatrix}0&4&8&12\\5&9&13&1\\10&14&2&6\\15&3&7&11\end{bmatrix}

MixColumns

MixColumns 本质上是一个矩阵乘法，其将每一列乘以一个矩阵，如下所示：

[2311123111233112][a0a1a2a3]\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}\begin{bmatrix}a_0\\a_1\\a_2\\a_3\end{bmatrix}

实际上就是每一行变成：

[2a0+3a1+a2+a3a0+2a1+3a2+a3a0+a1+2a2+3a33a0+a1+a2+2a3]\begin{bmatrix}2a_0+3a_1+a_2+a_3\\a_0+2a_1+3a_2+a_3\\a_0+a_1+2a_2+3a_3\\3a_0+a_1+a_2+2a_3\end{bmatrix}

解密就是直接乘上其的逆矩阵就好了，也就是：

[1411139914111313914111113914]\begin{bmatrix}14&11&13&9\\9&14&11&13\\13&9&14&11\\11&13&9&14\end{bmatrix}

AddRoundKey

这个就很直白，把每一个值和对应位置的轮密钥进行异或就好了

Encryption

首先我们先将明文和第一组轮密钥进行异或

img

然后对后面 n-1 轮（AES-128 就是 9 轮）做之前的加密操作，也就是

round

最后一轮将舍去 MixColummns

img

这就是完整的 AES 加密了

Decryption

这个就很直接，你只要把每个组件做一次逆向就好了，然后倒着进行解密。

具体的 python 实现可以看 https://github.com/bozhu/AES-Python/blob/master/aes.py ，我这里把它改成 python3 的实现（其实就是把几个 // 改成 /）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#!/usr/bin/env python


"""
    Copyright (C) 2012 Bo Zhu http://about.bozhu.me

    Permission is hereby granted, free of charge, to any person obtaining a
    copy of this software and associated documentation files (the "Software"),
    to deal in the Software without restriction, including without limitation
    the rights to use, copy, modify, merge, publish, distribute, sublicense,
    and/or sell copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.
"""

Sbox = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

InvSbox = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)


# learnt from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


Rcon = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)


def text2matrix(text):
    matrix = [[] for _ in range(4)]
    for i in range(16):
        byte = (text >> (8 * (15 - i))) & 0xFF
        matrix[i % 4].append(byte)
    return matrix

def matrix2text(matrix):
    text = 0
    for i in range(4):
        for j in range(4):
            text |= (matrix[j][i] << (120 - 8 * (4 * i + j)))
    return text

class AES:
    def __init__(self, master_key):
        self.change_key(master_key)

    def change_key(self, master_key):
        self.round_keys = text2matrix(master_key)
        for i in range(4, 4 * 11):
            self.round_keys.append([])
            if i % 4 == 0:
                temp = [
                    self.round_keys[i - 4][0] ^ Sbox[self.round_keys[i - 1][1]] ^ Rcon[i // 4],
                    self.round_keys[i - 4][1] ^ Sbox[self.round_keys[i - 1][2]],
                    self.round_keys[i - 4][2] ^ Sbox[self.round_keys[i - 1][3]],
                    self.round_keys[i - 4][3] ^ Sbox[self.round_keys[i - 1][0]],
                ]
            else:
                temp = [
                    self.round_keys[i - 4][j] ^ self.round_keys[i - 1][j] for j in range(4)
                ]
            self.round_keys[i] = temp

    def encrypt(self, plaintext):
        state = text2matrix(plaintext)
        self.add_round_key(state, self.round_keys[:4])
        for i in range(1, 10):
            self.sub_bytes(state)
            self.shift_rows(state)
            self.mix_columns(state)
            self.add_round_key(state, self.round_keys[4*i:4*(i+1)])
        self.sub_bytes(state)
        self.shift_rows(state)
        self.add_round_key(state, self.round_keys[16:20])
        return matrix2text(state)

    def decrypt(self, ciphertext):
        state = text2matrix(ciphertext)
        self.add_round_key(state, self.round_keys[16:20])
        self.inv_shift_rows(state)
        self.inv_sub_bytes(state)
        for i in range(9, 0, -1):
            self.add_round_key(state, self.round_keys[4*i:4*(i+1)])
            self.inv_mix_columns(state)
            self.inv_shift_rows(state)
            self.inv_sub_bytes(state)
        self.add_round_key(state, self.round_keys[:4])
        return matrix2text(state)

    def add_round_key(self, s, k):
        for i in range(4):
            for j in range(4):
                s[i][j] ^= k[i][j]

    def sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = Sbox[s[i][j]]

    def inv_sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = InvSbox[s[i][j]]

    def shift_rows(self, s):
        s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
        s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
        s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

    def inv_shift_rows(self, s):
        s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
        s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
        s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]

    def mix_columns(self, s):
        for i in range(4):
            t = s[i][0] ^ s[i][1] ^ s[i][2] ^ s[i][3]
            u = s[i][0]
            s[i][0] ^= t ^ xtime(s[i][0] ^ s[i][1])
            s[i][1] ^= t ^ xtime(s[i][1] ^ s[i][2])
            s[i][2] ^= t ^ xtime(s[i][2] ^ s[i][3])
            s[i][3] ^= t ^ xtime(s[i][3] ^ u)

    def inv_mix_columns(self, s):
        for i in range(4):
            u = xtime(xtime(s[i][0] ^ s[i][2]))
            v = xtime(xtime(s[i][1] ^ s[i][3]))
            s[i][0] ^= u
            s[i][1] ^= v
            s[i][2] ^= u
            s[i][3] ^= v
        self.mix_columns(s)

square attack

3 round

现在假设我们有 256 组输入，除了第一个字符是 0~256 的排列（实际上不在第一个字符也是可以的，但是要都在同一个位置），其它全是 0

img

我们称之为 Λ-set (delta set)

我们做了一次 AddRoundKey，会发现绿色字符的仍然是 0~256 的随机排列

img

然后我们进入了 SubBytes，可以发现仍然不会变化

img

对于进入 ShiftRows，由于第一行不会变化，所以是保持不变的。

但是进入 MixColumns 就不一样了，它会把第一列都变成 Λ-set ，其余位置保持不动。

img

这是为什么呢，回顾一下 MixColumns 操作

[2a0+3a1+a2+a3a0+2a1+3a2+a3a0+a1+2a2+3a33a0+a1+a2+2a3]\begin{bmatrix}2a_0+3a_1+a_2+a_3\\a_0+2a_1+3a_2+a_3\\a_0+a_1+2a_2+3a_3\\3a_0+a_1+a_2+2a_3\end{bmatrix}

我们取出任意一行可以发现，除了 a0a_0 是会变化的，其它都是常数，所以只会导致第一列变成 Λ-set 。因此第一轮结束后会变成下图所示

img

再分析一轮的话，我们发现最后仍然是一个 Λ-set，如下图所示

img

但是到了第三轮，我们会发现 MixColumns 破坏掉了 Λ-set

img

我们得到 16 个未知的 bytes，但是这真的无法分析了嘛？实际上，我们取出 256 个加密密文的第一个字符，并且做异或

b0⊕b1⋯⊕b255b_0\oplus b_1\cdots\oplus b_{255}

然后我们记 ai,ja_{i,j} 为 MixColumns 操作前矩阵的 ii 列 jj 行，那么原式可以写作

2a0,0⊕3a0,1⊕a0,2⊕a0,3⊕2a1,0⊕3a1,1⊕a1,2⊕a1,3⊕⋮⊕2a255,0⊕3a255,1⊕a255,2⊕a255,3=2(a0,0⊕a1,0⊕⋯a255,0)⊕3(a0,0⊕a1,0⊕⋯a255,0)⊕a0,0⊕a1,0⊕⋯a255,0⊕a0,0⊕a1,0⊕⋯a255,02a_{0,0}\oplus3a_{0,1}\oplus a_{0,2}\oplus a_{0,3}\\ \oplus\\ 2a_{1,0}\oplus3a_{1,1}\oplus a_{1,2}\oplus a_{1,3}\\ \oplus\\ \vdots\\ \oplus\\ 2a_{255,0}\oplus3a_{255,1}\oplus a_{255,2}\oplus a_{255,3}\\ =2(a_{0,0}\oplus a_{1,0}\oplus\cdots a_{255,0})\\ \oplus\\ 3(a_{0,0}\oplus a_{1,0}\oplus\cdots a_{255,0}) \oplus\\ a_{0,0}\oplus a_{1,0}\oplus\cdots a_{255,0} \oplus\\ a_{0,0}\oplus a_{1,0}\oplus\cdots a_{255,0}

而 a0,0⊕a1,0⊕⋯a255,0a_{0,0}\oplus a_{1,0}\oplus\cdots a_{255,0} 中的元素都是 Λ-set，所以其为 00，那么等式最后也会等于 00

由此我们得到了 Λ-set 元素之间的关系，目前为止 AddRoundKey 对其的影响是没有的，但是到了第四轮开始，其就会开始破坏我们所构造的结构了，但也由此导致了我们的 square attack

4 round

好了，我们现在直接来进行 4 轮 AES 的分析

img

这时候我们可以发现，经过 SubBytes 之后，我们的结构完全给破坏掉了，变成了完全未知的字符。这个时候，可能大家就会觉得已经分析不了了，实则不然，我们知道一件事情，除了 AddRoundKey 需要 key 以外，其它的组件都是完全可逆的。

假如我们对最后一轮密钥的第一个字节进行猜测，那么我们就可以从密文进行倒退，回到我们红色的字符。有了红色的字符，那么我们的完美结构就回来了，仍然满足异或为 00，所以我们可以逐字符的猜测最后一轮的密钥，然后验证逆向回去的字符是否异或都为 0，然后就可以找到最后一轮的密钥了。

最后，就是如何恢复轮密钥，幸运的是，轮密钥扩展是可逆的，也就是说，如果我们有任意一轮的轮密钥，我们就可以得到最开始的密钥。具体实现可以跟着 KeyExpansion 反着进行。

现在我们来举个例子，我们使用的 AES 就是上面所说的例子，但是把轮数都改成 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import os

if __name__ == '__main__':
    kk = os.urandom(16)
    aes = AES4(bytes_to_long(kk))
    ps1 = []; ps2 = []
    for i in range(256):
        p = bytes_to_long(bytes([i]) + b"\x00"*15)
        ps1 += [aes.encrypt(p)]
        p = bytes_to_long(bytes([i]) + b"\x01"*15)
        ps2 += [aes.encrypt(p)]
    print(f'{ps1 = }')
    print(f'{ps2 = }')

为啥用了两个 Λ-set 呢，因为一个可能有多个答案，我懒得写枚举了XD

然后做上诉的操作，可以简单的写出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import long_to_bytes, bytes_to_long
from itertools import *
from AES import AES4, Sbox, InvSbox, Rcon

ps1 = ...
ps2 = ...

def find_last_key(ps):
    ct = [long_to_bytes(c, 16) for c in ps]  
    Roundkey = [[] for _ in range(16)]
    for i in range(16):
        for ki in range(256):
            t = 0
            for ind in range(256):
                t ^= InvSbox[ct[ind][i] ^ ki]
            if t == 0 :
                Roundkey[i].append(ki)
    return Roundkey

k1 = find_last_key(ps1)
k2 = find_last_key(ps2)
k = []
for i, j in zip(k1, k2):
    k += set(i) & set(j)

def recover_key(lk):
    w = [None] * 20
    for i in range(4):
        k = []
        for j in range(4):
            k += [lk[4 * j + i]]
        w[16 + i] = k
    for i in range(19, 3, -1):
        if i % 4 == 0:
            tmp = w[i-1][1:] + w[i-1][:1]
            tmp = [Sbox[b] for b in tmp]
            tmp[0] ^= Rcon[i //4 ]
            w[i-4] = [w[i][j] ^ tmp[j] for j in range(4)]
        else:
            w[i-4] = [w[i][j] ^ w[i-1][j] for j in range(4)]
    w = [j for i in w[:4] for j in i]
    o = [None] * 4
    for i in range(4):
        oo = []
        for j in range(4):
            oo += [w[4 * j + i]]
        o[i] = oo
    return b''.join([bytes(i) for i in o])

key = recover_key(k)
print(key)

至此，我们完全的分析出了 4 round 的AES。

reference

https://www.davidwong.fr/blockbreakers/