一道卫星上AES侧信道攻击的题目，主要利用AES T-表的Cache缓存碰撞实施攻击。
题目描述
题目文件：
https://github.com/ADDVulcan/ADDVulcan/tree/master/Payload%20Modules/Leaky%20Crypto
题目有两个文件，Readme.txt文件是题目描述，大概意思是题目使用AES-128的ECB模式和前6字节为97ca6080f575的密钥加密了flag，密文是：
7972c157dad7b858596ecdb798877cc4ed4b03d6822295954e69b7ecebb704af08c054a03a374f8bdaa18ff16ba09be2b6b25f1ef73ef80111646de84cd3af2514501e056889e95c680f7d199b6531e9dd6ee599aeb23835327e6e853a9a40a9f405bd1443e014363ea46631582b97c3d3f83f4e1101da2557f9b03808a61968
test.txt文件是题目附件，其中给了100000个明文和其对应的加密时间，如：
2c86f81fdc568d631c9dd0a075ec2a35,10776
5e7b2322d8a2dabd86884d42de3748c8,10704
3ebac48a8c3b0a3b552c385eafc7f99a,10776
54f865a9cc7a3a1bcf68bad09d0b699a,10704
... ...
在Readme.txt文件中还有一点提示，最有用的是解这题需要用到侧信道攻击（Side Channel Attacks）。
搜集一下关于AES侧信道的资料，可以翻到有一种对AES的T-表进行侧信道攻击，恰好可以用来攻击这道题目。
AES、T-Table和缓存碰撞
在了解攻击前，需要知道一点前置知识。
AES的详细流程非常复杂，这里不多说，建议先去参考教科书或CTF Wiki学习学习。
简要来说的话，AES主要有以下4个操作：
-
轮密钥加，AddRoundKey -
字节替换，SubBytes -
行移位，ShiftRows -
列混淆，MixColumns
在明文P被输进AES算法后，按照顺序执行
P -> AddRoundKey ->
SubBytes -> ShiftRows -> MixColumns -> AddRoundKey ->
... (9 Rounds) ...
SubBytes -> ShiftRows -> MixColumns -> AddRoundKey ->
SubBytes -> ShiftRows -> MixColumns -> C
其中的SubBytes -> ShiftRows -> MixColumns -> AddRoundKey被称作一轮（Round）。
以上只是教科书版本的AES，实际应用时，为了加速AES的运算速度会做一些优化，比如这里的查表法。
首先SubBytes和ShiftRows 是相互独立的，即它们的操作顺序可以替换，这样的话一轮的操作就可以变成
ShiftRows -> SubBytes -> MixColumns -> AddRoundKey
然后SubBytes中的操作是通过查S-Box替换字节，MixColumns大概是一个线性的加法（异或），如果先用线性加法的系数和S-Box做预运算，生成一个叫“T-表”的表，那么在加密/解密时通过查T-表而不是S-Box，就可以省去乘法操作，从而加快运算时间。
另外，ShiftRows里面的移位顺序也是固定的，所以把这个顺序写死的话，也可以节省移位操作消耗的时间。
假设上一轮的输出中对应的每个字节是，假设在这轮的中MixColumns后的4个块为，优化后就大概可以得到：
其中就是T-表的4张表，这里因为篇幅原因我省略了很多的细节，比如是怎样生成的，想了解更多的话可以去参考相关的文献。
可以看到在的生成过程中，都会查表各一次，如果在和的生成过程中，某个表的输入都一样，那么就会触发计算机中的一个缓存机制（Cache Hits）。
缓存（Cache）大概意思是，计算机为了提高CPU的运算效率，会把常用的数据放在CPU的缓存中，如果下一次需要用到这个数据，只需要在里CPU很近的缓存中拿这个数据即可，而不用到更远/更慢的内存或外存中获取。
假设在生成时的输入是，那么计算机就会把中位置的数据放进缓存中。
-
如果在生成时的输入恰好是，就会触发一次Cache Hits，CPU只需直接拿缓存中的对应数据。 -
如果在生成时的输入不是，就会触发一次Cache Misses，CPU需要从更远的内存中获取这个数据，然后（可能会）用这个数据覆盖缓存中对应位置的数据。
显然Cache Hits时的运算会比Cache Misses时的运算更快。
PS：以上只是对教科书版本的缓存的简单介绍，实际应用时，不同的CPU的缓存设计都不尽相同，更别说卫星上的，在实际攻击时我也发现题目使用的缓存有一些特别的机制。
AES缓存碰撞攻击
回到题目，题目给了多组明文和对应的加密时间，那么就可以使用这个时间去分辨哪一组明文的加密触发了Cache Hits碰撞，然后利用这个碰撞信息去恢复密钥。
问题是，如何从碰撞中恢复密钥？
如果只看优化版本AES的第一轮操作的话，目前是：
轮密钥加 -> 查T-表 -> 轮密钥加 ...
所以假设明文的每一字节是，密钥的每一个字节是，第一轮输入的每个字节是的话，就有
假设我想要和产生碰撞，只需要
即可。
举个栗子，目前在T-表中有
如果我想要判断这两次查表是否产生碰撞，只需判断他的输入是否相等，即
由于我知道每一组明文，所以和已知，那么假设我也知道和，那么就可以根据以上关系把那一堆明文分成两组：在第一轮的生成中有产生碰撞的和没产生碰撞的。
现在题目给了密钥的前6字节，所以我可以知道，那么接下来就是一个统计学的问题，即我可以枚举，每个都用以上规则把明文分成碰撞组和无碰撞组，然后检测碰撞组的加密速度是否明显大于无碰撞组的加密速度，如果是，就说明找到（可能）正确的。
来个代码测试一下，这里我在分组后统计每一组时间的均值，然后检测它们的差是否大于一个阈值（THRESHOLD），如是则认为这个是一个可能正确的，参考代码：
THRESHOLD = 10
with open('./test.txt', 'r') as f:
raw_data = f.read()
data = []
for d in raw_data.split('n')[:-1]:
tmp = d.split(',')
tmp[0] = bytes.fromhex(tmp[0])
tmp[1] = int(tmp[1])
data += [tmp]
key = bytes.fromhex('97ca6080f575')
def mean(l):
assert isinstance(l, list)
return sum(l) / len(l)
def check(i, j, ki, kj):
col = []
ncol = []
for di in range(len(data)):
p, t = data[di]
if p[i] ^ ki == p[j] ^ kj:
col += [t]
else:
ncol += [t]
r = mean(ncol) - mean(col)
if r < THRESHOLD:
return None
return r
def test(i, j):
ki = key[i]
for kj in range(256):
r = check(i, j, ki, kj)
if r:
print((i, j), hex(kj), r)
if __name__ == '__main__':
test(4, 8)
'''
(4, 8) 0xe4 24.571021646042936
(4, 8) 0xe5 20.58349909921526
(4, 8) 0xe6 23.138921452926297
(4, 8) 0xe7 24.225824547616867
'''
得出了的4个可能值。
理论上接下来我只需要猜这4个值的其中一个，然后用同样的方法就可以得到的可能值，但实际上这4个值测试完都不能得到一个均值差大于阈值的结果。同样地，在表中也不能用推出。
在进一步测试前先说一个结论，由于是可交换的，所以以上算法也是可交换的，即如果可以用推出，那么也可以用推出，可以自行用test(0, 4)和test(4, 0)测试一波。
然后在进一步测试中发现，用可以推出，接着还可以推出、、和共用一个缓存位置，最后测试剩余的数据发现题目的缓存使用情况是（同一行表示共用一个缓存位置，从左到右表示缓存的顺序）：
0 -> 4 -> 8 ;
12 -> 5 -> 9 -> 13 ;
1 -> 10 -> 14 -> 2 ;
6 -> 15 -> 3 -> 7 ;
11 ;
PS：另外参考了其他人的复现结果发现，即使自己生成的数据也会有这种缓存关系，原理未明，盲猜跟程序中T-表的内存位置和缓存的索引机制有关。
从题目的已知信息可知，由于同一个缓存中相邻的两个数据可以相互推出，所以根据已知推出未知的原则，就可以构造以下攻击链：
4 -> 8 ;
5 -> 12 ;
5 -> 9 -> 13 ;
1 -> 10 ;
2 -> 14 ;
3 -> 7 ;
3 -> 15 -> 6 ;
在测试中，每个未知的密钥字节都会推出4种可能，所以这里需要枚举种情况。
PS：这些4种可能都是高6位比特相同，原理未明。
然后剩下单独的需要枚举它的种可能性，合起来总的枚举复杂度就是，实测全部枚举大概需要半个小时。
参考Exp
THRESHOLD = 10
with open('./test.txt', 'r') as f:
raw_data = f.read()
data = []
for d in raw_data.split('n')[:-1]:
tmp = d.split(',')
tmp[0] = bytes.fromhex(tmp[0])
tmp[1] = int(tmp[1])
data += [tmp]
key = bytes.fromhex('97ca6080f575')
key = [set([ki]) for ki in key] + [set() for _ in range(16 - len(key))]
print(key)
def mean(l):
assert isinstance(l, list)
return sum(l) / len(l)
def check(i, j, ki, kj):
col = []
ncol = []
for di in range(len(data)):
p, t = data[di]
if p[i] ^ ki == p[j] ^ kj:
col += [t]
else:
ncol += [t]
r = mean(ncol) - mean(col)
if r < THRESHOLD:
return None
return r
def hack(chains):
for chi in chains:
print(chi)
i, j = chi
for ki in list(key[i]):
for kj in range(256):
r = check(i, j, ki, kj)
if r:
print((i, j), hex(kj), r)
if j > 5:
key[j].add(kj)
print(key)
print()
chains = [
(0, 4), (4, 8),
(5, 9), (9, 13), (5, 12),
(1, 10), (2, 14), (10, 14),
(3, 7), (3, 15), (15, 6)
]
#hack(chains)
key = [{151}, {202}, {96}, {128}, {245}, {117}, {228, 229, 230, 231}, {68, 69, 70, 71}, {228, 229, 230, 231}, {84, 85, 86, 87}, {244, 245, 246, 247}, set(), {188, 189, 190, 191}, {20, 21, 22, 23}, {104, 105, 106, 107}, {92, 93, 94, 95}]
print(key)
print()
import itertools
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from tqdm import tqdm
from math import prod
c = bytes.fromhex('7972c157dad7b858596ecdb798877cc4ed4b03d6822295954e69b7ecebb704af08c054a03a374f8bdaa18ff16ba09be2b6b25f1ef73ef80111646de84cd3af2514501e056889e95c680f7d199b6531e9dd6ee599aeb23835327e6e853a9a40a9f405bd1443e014363ea46631582b97c3d3f83f4e1101da2557f9b03808a61968')
key = [list(ki) if ki else list(range(256)) for ki in key]
print(key)
print()
for k16 in tqdm(itertools.product(*key), total=prod([len(ki) for ki in key])):
k = bytes(k16)
aes = AES.new(k, AES.MODE_ECB)
p = aes.decrypt(c)
try:
p = unpad(p, 16)
except:
continue
if b'flag' in p:
print(k.hex())
print(p)
print()
'''
66%|████████████████████████████▏ | 43992636/67108864 [18:25<09:26, 40781.32it/s]
97ca6080f575e646e557f755bf15685e
b'flag{uniform54349juliet:GL2aGs7ys8ygcW0kFBPLbwEdjLbwNltiPdX_ANqtOFbUpEh_ciY8tWZd4y2VblkUhOl-PxXJdJYK86pIHmmwcw0}'
'''
原文始发于微信公众号（山石网科安全技术研究院）：【卫星安全系列三】Leaky Crypto赛题复现
