DFA还原白盒AES密钥
zsk Lv4
  2023-01-31 22:00:00 2023-01-31 22:00   2023-01-31 22:00:00    2.1k 字  9 分钟  

介绍

DFA攻击简单来说就是在倒数第一轮列混淆和倒数第二轮列混淆之间（在AES-128中也就是第8轮和第9轮之间，因为最后第10轮不做列混淆），修改此时中间结果的一个字节，会导致最终密文和正确密文有4个字节的不同。通过多次的修改，得到多组错误的密文，然后通过正确密文和这些错误密文能够推算出第10轮的密钥（加密模式下），继而能推算出原始密钥。
所以实际应用中，就需要先找准列混合的函数位置，然后在他之前去插入缺陷数据。

起始处发生故障对密文的影响

首先是初始轮密钥加，错误限于这一个字节
image然后是第一轮的字节替换，错误限于这一个字节
image然后是第一轮的循环左移，因为是第一行，所以没动。
image然后是第一轮的列混淆步骤，结果的第m行第n列的值等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和，因此结果中第一列的每一个元素都受到矩阵B（即下图左边）第一列中每个元素的影响。因而，一个字节的错误被扩散到了一整列。或者说，正常情况和故障情况在第一轮列混淆结束后，有四个字节的值不同。
image然后是第一轮的轮密钥加，它只作用用当前字节，不会将差异扩散出去。
image可以看到，在一轮循环后，一个字节的故障，被扩散到了四个字节上。继续第二轮。
第二轮的字节替换
image第二轮的循环左移，需要注意到，虽然差异还是四个字节，但被扩散到不同的四列去了。
image第二轮的列混淆，每列存在的差异扩散到整列，这导致state的全部字节都与原先有差异。
image经过第二轮一个字节的差异就已经扩散到所有字节上了。
那么 state 中一个字节的差异，不论循环多少轮，也只会带来一个字节的差异。反过来说，每一次 MixColumns ，都会让一个字节的差异变成四个字节的差异。
因为第十轮没有列混淆所以在第九轮列混淆前做故障点

通过故障密钥得到第十轮密钥

标准的AES算法的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
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
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)


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


def shiftRound(array, num):
    '''

    :param array: 需要循环左移的数组
    :param num: 循环左移的位数
    :return: 使用Python切片，返回循环左移num个单位的array
    '''
    return array[num:] + array[:num]


def g(array, index):
    '''
    g 函数
    :param array: 待处理的四字节数组
    :index:从1-10，每次使用Rcon中不同的数
    '''
    # 首先循环左移1位
    array = shiftRound(array, 1)
    # 字节替换
    array = [Sbox[i] for i in array]
    # 首字节和rcon中对应元素异或
    array = [(Rcon[index] ^ array[0])] + array[1:]
    return array


def xorTwoArray(array1, array2):
    '''
    返回两个数组逐元素异或的新数组
    :param array1: 一个array
    :param array2: 另一个array
    :return:
    '''
    assert len(array1) == len(array2)
    return [array1[i] ^ array2[i] for i in range(len(array1))]


def showRoundKeys(round_keys):
    # 将轮密钥从44*4转成11*16
    kList = [[] for i in range(11)]
    for i in range(len(round_keys)):
        kList[i // 4] += round_keys[i]
    for i in range(len(kList)):
        print("K%02d:" % i + "".join("%02x" % k for k in kList[i]))


def keyExpand(key):
    master_key = text2matrix(key)
    round_keys = [[0] * 4 for i in range(44)]
    # 规则一(图中红色部分)
    for i in range(4):
        round_keys[i] = master_key[i]
    for i in range(4, 4 * 11):
        # 规则二(图中红色部分)
        if i % 4 == 0:
            round_keys[i] = xorTwoArray(g(round_keys[i - 1], i // 4), round_keys[i - 4])
        # 规则三(图中橙色部分)
        else:
            round_keys[i] = xorTwoArray(round_keys[i - 1], round_keys[i - 4])
    showRoundKeys(round_keys)
    return round_keys


def AddRoundKeys(state, roundKey):
    result = [[] for i in range(4)]
    for i in range(4):
        result[i] = xorTwoArray(state[i], roundKey[i])

    return result


def SubBytes(state):
    result = [[] for i in range(4)]
    for i in range(4):
        result[i] = [Sbox[i] for i in state[i]]
    return result


def ShiftRows(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]
    return s


def mul_by_02(num):
    if num < 0x80:
        res = (num << 1)
    else:
        res = (num << 1) ^ 0x1b
    return res % 0x100


def mul_by_03(num):
    return mul_by_02(num) ^ num


def MixColumns(state):
    for i in range(4):
        s0 = mul_by_02(state[i][0]) ^ mul_by_03(state[i][1]) ^ state[i][2] ^ state[i][3]
        s1 = state[i][0] ^ mul_by_02(state[i][1]) ^ mul_by_03(state[i][2]) ^ state[i][3]
        s2 = state[i][0] ^ state[i][1] ^ mul_by_02(state[i][2]) ^ mul_by_03(state[i][3])
        s3 = mul_by_03(state[i][0]) ^ state[i][1] ^ state[i][2] ^ mul_by_02(state[i][3])
        state[i][0] = s0
        state[i][1] = s1
        state[i][2] = s2
        state[i][3] = s3

    return state


def state2Text(state):
    text = sum(state, [])
    return "".join("%02x" % k for k in text)


def encrypt(input_bytes, kList):
    '''

    :param input_bytes: 输入的明文
    :param kList: K0-K10
    :return:
    '''
    plainState = text2matrix(input_bytes)
    # 初始轮密钥加
    state = AddRoundKeys(plainState, kList[0:4])
    for i in range(1, 10):
        state = SubBytes(state)
        state = ShiftRows(state)
        state = MixColumns(state)
        state = AddRoundKeys(state, kList[4 * i:4 * (i + 1)])

    state = SubBytes(state)
    state = ShiftRows(state)
    state = AddRoundKeys(state, kList[40:44])
    return state


input_bytes = 0x00112233445566778899aabbccddeeff
key = 0x2b7e151628aed2a6abf7158809cf4f3c
kList = keyExpand(key)
cipherState = encrypt(input_bytes, kList)
cipher = state2Text(cipherState)
print(cipher)

上述代码的执行结果为8df4e9aac5c7573a27d8d055d6e4d64b。
接下来我们就要去构造故障了，在第九轮加密的行移位和列混合之间修改一个中间结果的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def encrypt(input_bytes, kList):
    '''
    :param input_bytes: 输入的明文
    :param kList: K0-K10
    :return:
    '''
    plainState = text2matrix(input_bytes)
    # 初始轮密钥加
    state = AddRoundKeys(plainState, kList[0:4])
    for i in range(1, 10):
        state = SubBytes(state)
        state = ShiftRows(state)
        # 在第9轮改一个字节
        if i == 9:
            j = 0
            print("修改第" + str(j) + "个")
            state[j//4][j%4] = 0x10
        state = MixColumns(state)
        state = AddRoundKeys(state, kList[4 * i:4 * (i + 1)])

    state = SubBytes(state)
    state = ShiftRows(state)
    state = AddRoundKeys(state, kList[40:44])
    return state

执行脚本，结果为daf4e9aac5c757c927d85355d637d64b，比对一下：
8d f4 e9 aa c5 c7 57 3a 27 d8 d0 55 d6 e4 d6 4b
da f4 e9 aa c5 c7 57 c9 27 d8 53 55 d6 37 d6 4b
确实有4个字节不一样。以此类推，将上述代码中j的值从0到15依次增加，会得到16个不一样的密文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
daf4e9aac5c757c927d85355d637d64b
47f4e9aac5c7577d27d8a655d61ed64b
79f4e9aac5c7572a27d89855d62ad64b
30f4e9aac5c7570b27d86555d6a5d64b
8d7de9aac8c7573a27d8d09ed6e4be4b
8d5ce9aa43c7573a27d8d04cd6e4054b
8d0de9aaddc7573a27d8d060d6e4234b
8dabe9aacac7573a27d8d009d6e4484b
8df48caac598573a62d8d055d6e4d636
8df4bbaac5f4573acdd8d055d6e4d693
8df47aaac576573ac1d8d055d6e4d61c
8df444aac5c8573a23d8d055d6e4d6fb
8df4e9e0c5c7b73a2768d055ade4d64b
8df4e9f2c5c7063a27a4d055dfe4d64b
8df4e942c5c7793a275ed05535e4d64b
8df4e98fc5c7fa3a2778d055b3e4d64b

有了这个以后我们就可以还原得到第十轮的密钥了，这里使用phoenixAES工具，先安装：

1
pip install phoenixAES

然后编写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
#!/usr/bin/env python3
import phoenixAES

with open('tracefile', 'wb') as t:
    t.write("""
8df4e9aac5c7573a27d8d055d6e4d64b
daf4e9aac5c757c927d85355d637d64b
47f4e9aac5c7577d27d8a655d61ed64b
79f4e9aac5c7572a27d89855d62ad64b
30f4e9aac5c7570b27d86555d6a5d64b
8d7de9aac8c7573a27d8d09ed6e4be4b
8d5ce9aa43c7573a27d8d04cd6e4054b
8d0de9aaddc7573a27d8d060d6e4234b
8dabe9aacac7573a27d8d009d6e4484b
8df48caac598573a62d8d055d6e4d636
8df4bbaac5f4573acdd8d055d6e4d693
8df47aaac576573ac1d8d055d6e4d61c
8df444aac5c8573a23d8d055d6e4d6fb
8df4e9e0c5c7b73a2768d055ade4d64b
8df4e9f2c5c7063a27a4d055dfe4d64b
8df4e942c5c7793a275ed05535e4d64b
8df4e98fc5c7fa3a2778d055b3e4d64b
""".encode('utf8'))
phoenixAES.crack_file('tracefile', [], True, False, 3)

一共写入了17行数据到文件，其中第一行为正确的密文，剩余16行都是故障密文，最终通过crack_file即可得到第10轮密钥：

1
2
Last round key #N found:
D014F9A8C9EE2589E13F0CC8B6630CA6

还原密文

接下来还要根据这个密钥去还原原始密钥，这里还需要用到一个工具Stark，它里面有一个aes_keyschedule.c文件，将其拷贝到本地并编译为可执行文件：

1
gcc aes_keyschedule.c -o aes_keyschedule

然后将刚才得到的第10轮密钥喂进去：

1
./aes_keyschedule 5D432583B2AA833FC22D53130FDA904C 10

执行上述命令后

1
2
3
4
5
6
7
8
9
10
11
12
./aes_keyschedule D014F9A8C9EE2589E13F0CC8B6630CA6 10
K00: 2B7E151628AED2A6ABF7158809CF4F3C
K01: A0FAFE1788542CB123A339392A6C7605
K02: F2C295F27A96B9435935807A7359F67F
K03: 3D80477D4716FE3E1E237E446D7A883B
K04: EF44A541A8525B7FB671253BDB0BAD00
K05: D4D1C6F87C839D87CAF2B8BC11F915BC
K06: 6D88A37A110B3EFDDBF98641CA0093FD
K07: 4E54F70E5F5FC9F384A64FB24EA6DC4F
K08: EAD27321B58DBAD2312BF5607F8D292F
K09: AC7766F319FADC2128D12941575C006E
K10: D014F9A8C9EE2589E13F0CC8B6630CA6

即可得到密钥为2B7E151628AED2A6ABF7158809CF4F3C，同一开始的密钥一致

更多关于加密算法的内容可以关注龙哥星球
image

DFA还原白盒AES密钥
posts/15785/
作者
zsk
发布于
2023-01-31 22:00
许可
 评论
  1. 1. 介绍
  2. 2. 起始处发生故障对密文的影响
  3. 3. 通过故障密钥得到第十轮密钥
  4. 4. 还原密文