测信道攻击——利用一个bit恢复AES key

前面对AES原理做了解释，而本实验的AES是一个半AES，因为没有那么复杂，非常简单，方便初学者理解。这次实验不用硬件设备。实验的目的就是通过一个bit位的泄漏，即使不知道key，但知道加密算法也可以恢复完整的AES key，这个方法非常妙！

简单来说，本实验的阉割版AES长这样：

S-box

sbox = [
    # 0    1    2    3    4    5    6    7    8    9    a    b    c    d    e    f 
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76, # 0
    0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0, # 1
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15, # 2
    0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75, # 3
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84, # 4
    0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf, # 5
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8, # 6
    0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2, # 7
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73, # 8
    0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb, # 9
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79, # a
    0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08, # b
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a, # c
    0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e, # d
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf, # e
    0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16  # f
]

定义aes_internal用于返回加密后的秘文，加密后的秘文就是AES key和输入异或的值在s-box中对应的数值

def aes_internal(inputdata, key):
    return sbox[inputdata ^ key]

这里可以验证一下：

assert(aes_internal(0xAB, 0xEF) == 0x1B)
assert(aes_internal(0x22, 0x01) == 0x26)
print("✔️ OK to continue!")

接下来就是设置一个要攻击的目标，定义一个新的函数aes_secret，不透露key，内置一个固定的key。

def aes_secret(inputdata):
    secret_key = 0xEF
    return aes_internal(secret_key, inputdata)

这段代码就是教我们怎么用python生成随机数，并且通过加密函数得到output（这里somefunc是一个例子，不是前面说的要用的加密函数）

##Some Python hints/useful functions:

# You can use this function to generate the random data
import random
random.randint(0, 255)

# List comprehension can be used to shovel data through a function
def somefunc(a):
    return a + 4
input_data = [1,2,5,6]
output_data = [somefunc(a) for a in input_data]

# You can use this while ignoring the index variable too
output_data = [somefunc(random.randint(0,255)) for _ in range(0, 1000)]

生成1000个0～255的随机整数：

input_data = [random.randint(0,255) for _ in range(0, 1000)]

接下来是生成泄漏数据，取input的最低bit位，& 0x01就是取最低比特位的作用，这样计算出来就能把最低比特位给泄漏

leaked_data = [(aes_secret(a) & 0x01) for a in input_data]

输出的就是泄漏的1000个数据每个数据最低比特位数

[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1]

通过画图可以直观查看泄漏数据leaked_data的内容

import matplotlib.pylab as plt
plt.plot(leaked_data[0:200])
plt.show()

这里介绍一下要获得两个list相同元素的数量可以先转化为numpy array，然后两个array进行比较，最后sum出True(1)的数量

def num_same(a, b):
    
    if len(a) != len(b):
        raise ValueError("Arrays must be same length!")

    if max(a) != max(b):
        raise ValueError("Arrays max() should be the same!")
    
    #Count how many list items match up
    same = 0
    for i, _ in enumerate(a):
        if a[i] == b[i]:
            same += 1
    
    return same

可以检测下是否正确实现代码块

#Simple test vectors - if you get the check-mark printed all OK.
assert(num_same([0,1,0,1,1,1,1,0], [0,1,0,1,1,1,1,0]) == 8)
assert(num_same([1,1,1,0,0,0,0,0], [0,1,0,1,1,1,1,0]) == 2)
assert(num_same([1, 0], [0, 1]) == 0)
print("✔️ OK to continue!")

那么利用上面比特位的泄漏方式以及判断两个array是否相同的方法， 我们就可以枚举所有key的可能，key的一个字节就是0x00~0xff，将这些所有可能去加密相同的input_data得到key_guess，再将结果和泄漏数据的这个list进行比较，看是否相同！发现EF是1000，代表之前随机生成的1000个数据，在AES加密后生成的密文的最低比特位（1000个数据1000个最低比特位）与我们从枚举一个字节的所有可能值（0x00～0xFF）中的0xEF对同样的明文加密后，产生的密文是一样的！（因为最低比特位1000个都一样，而且唯一也就它是正好1000），所以0xEF就是密钥key的一个固定字节！那么按照这个思路，继续猜测密文的其他字节也同样可行，这招真的是妙啊！

Guess 00:  487 bits same
Guess 01:  431 bits same
Guess 02:  495 bits same
Guess 03:  493 bits same
....
....
....
Guess EE:  476 bits same
Guess EF: 1000 bits same
Guess F0:  495 bits same
Guess F1:  473 bits same
Guess F2:  459 bits same
Guess F3:  473 bits same
Guess F4:  503 bits same
Guess F5:  453 bits same
Guess F6:  493 bits same
Guess F7:  535 bits same
Guess F8:  451 bits same
Guess F9:  570 bits same
Guess FA:  477 bits same
Guess FB:  457 bits same
Guess FC:  539 bits same
Guess FD:  465 bits same
Guess FE:  461 bits same
Guess FF:  543 bits same

上面已经够妙了，然鹅我们还可以在算法上更优化下，不那么傻傻地一个个找了，怎么做呢？这里先介绍下numpy的argsort用法，np.argsort函数用来输出从小到大数值对应的index，这里输出就是“0 3 4 1 2“，要从大到小就是[::-1]或者np.argsort(-np.array(list()))

import numpy as np

count_list = [2, 7, 24, 4, 5]

np.argsort(count_list)

到这里，应该能知道为啥要介绍这个函数了吧，我们可以直接把结果从大到小排序，只考虑前五个guess key的结果

import numpy as np

guess_list = [0] * 256

for guess in range(0, 256):   
    
    #Get a hypothetical leakage list - use aes_internal(guess, input_byte) and mask off to only get value of lowest bit
    hypothetical_leakage = [aes_internal(guess, input_byte) & 0x01 for input_byte in input_data]
    
    #Use our function
    same_count = num_same(hypothetical_leakage, leaked_data)   
    
    #Track the number of correct bits
    guess_list[guess] = same_count

#Use np.argsort to generate a list of indicies from low to high, then [::-1] to reverse the list to get high to low.
sorted_list = np.argsort(guess_list)[::-1]

#Print top 5 only
for guess in sorted_list[0:5]:
        print("Key Guess {:02X} = {:04d} matches".format(guess, guess_list[guess]))

结果如下，还是很明显的，EF最多，而且一字不纳

Key Guess EF = 1000 matches
Key Guess C5 = 0578 matches
Key Guess 24 = 0572 matches
Key Guess B8 = 0572 matches
Key Guess F9 = 0570 matches

接下来就是如何猜测key中的下一个字节呢？，其实只要稍微修改下前面的leaked_data函数代码就ok，比如前面一个字节，那么就是第‘3’位的数据

leaked_data = [(aes_secret(a)>>3 & 0x01) for a in input_data]

继续完善leaked_data函数，让它根据随机数来决定返回正确加密结果还是0，来模拟噪声

import random

def aes_secret_chance(inputdata, chance_correct):
        secret_key = 0xEF
        correct = aes_internal(secret_key, inputdata)

        if random.randint(0, 100) <= chance_correct:
            return correct
        else:
            return 0

        
def num_same(a, b):
    
    if len(a) != len(b):
        raise ValueError("Arrays must be same length!")
    
    #Count how many list items match up
    same = 0
    for i, _ in enumerate(a):
        if a[i] == b[i]:
            same += 1
    
    return same
        
#This sets the percentage of correct observations
chances_to_try = range(20, 105, 5)
traces_needed = []
    
for chance_correct in chances_to_try:
    leaked_data = [(aes_secret_chance(a, chance_correct) & 0x01) for a in input_data]
        
    #Try for number of traces
    for traces in range(1, len(input_data), 1):
        
        guess_list = [0] * 256

        for guess in range(0, 256):
    
            #Get a hypothetical leakage list - use aes_internal(guess, input_byte) and mask off to only get value of lowest bit
            hypothetical_leakage = [aes_internal(guess, input_byte) & 0x01 for input_byte in input_data[0:traces]]

            #Use our function
            same_count = num_same(hypothetical_leakage, leaked_data[0:traces])

            #Track the number of correct bits
            guess_list[guess] = same_count

        #Use np.argsort to generate a list of indicies from low to high, then [::-1] to reverse the list to get high to low.
        sorted_list = np.argsort(guess_list)[::-1]
        
        if sorted_list[0] == 0xEF:
            print("Found key at %d %% correct data with %d encryptions"%(chance_correct, traces))
            traces_needed.append(traces)
            break
            
    if sorted_list[0] != 0xEF:
        raise ValueError("Failed to find answer for %d %% - need more traces"%(chance_correct))

Found key at 20 % correct data with 97 encryptions
Found key at 25 % correct data with 10 encryptions
Found key at 30 % correct data with 64 encryptions
Found key at 35 % correct data with 40 encryptions
Found key at 40 % correct data with 20 encryptions
Found key at 45 % correct data with 39 encryptions
Found key at 50 % correct data with 34 encryptions
Found key at 55 % correct data with 15 encryptions
Found key at 60 % correct data with 10 encryptions
Found key at 65 % correct data with 28 encryptions
Found key at 70 % correct data with 9 encryptions
Found key at 75 % correct data with 9 encryptions
Found key at 80 % correct data with 9 encryptions
Found key at 85 % correct data with 15 encryptions
Found key at 90 % correct data with 9 encryptions
Found key at 95 % correct data with 9 encryptions
Found key at 100 % correct data with 9 encryptions

对结果画图

import matplotlib.pylab as plt

plt.figure(figsize=(6,3), dpi=150)
plt.plot(chances_to_try, traces_needed)
plt.title('Guesses for Single Bit Observation')
plt.xlabel('% Chance of Correct Observation')
plt.ylabel('Encryptions To Recover Key')

从图可知，70%以上正确率的基本上都只需要少量数据就可以恢复正确的key

Reference

Chipwhisperer-Jupyter