AES相关功耗分析问题

2023-07-11
Tags: AES, note.
Categories: notes.

🐮！

概述

一般来说，密码系统的评估是在攻击者可以获得其输入和输出的假设下评估受保护的资产（明文、密钥等）是否得到适当的保护。这意味着该密码系统对于攻击者来说是一个黑匣子。

但事实不是如此。密码系统通常在计算机中实现，而计算机在执行加密操作时会产生功耗。攻击者通过分析功耗来尝试获取受保护的资产，就称为功耗分析。

功耗分析有多种方法，比如简单功耗分析 (SPA)、差分功耗分析 (DPA) 和相关功耗分析 ( CPA )。

在CTF中对CPA的考察比较多，因此来一起探讨CPA。

相关功耗分析 ( CPA )

在解释之前，要明白两个概念：汉明距离和汉明权重。

  • 汉明距离 : 表示两个等长的字符串对应位不同的个数。对两个字符串进行异或运算，并统计其结果为1的个数就是汉明距离。

    1
    2
    3
    str1 = 1 0 1 0 1 0 0 0
    str2 = 1 0 1 1 0 1 0 0
    汉明距离：3

  • 汉明权重：它是一种特殊的汉明距离，指一个字符串与一个等长的“零"字符串的汉明距离，即一个字符串中非零的字符个数。

    1
    2
    3
    str1 = 0 1 1 0 1 0 1 1
    str2 = 0 0 0 0 0 0 0 0
    汉明权重：5

计算机数据存储在存储器和寄存器等设备中，这些存储器和寄存器根据内部是否保存电荷来确定数据是"1"还是"0"。由于电荷的特性，在反转(重写)该位时会产生大量功耗。一次数据改变中重写的数据量越大，功耗就越大。

在密码系统对数据进行操作时，会产生重写数据，同时存储设备根据每个处理的输入和输出之间的差异(汉明距离)来反转存储的位。如果输入与输出差值小，则功耗就小；如果差值大，则功耗也大。换言之，输入输出的汉明距离和功耗之间存在相关性。

相关功耗分析是一种利用这些输入和输出的汉明距离与其功耗之间的相关性的攻击

这种线性相关性可以用皮尔逊相关系数来表示。汉明距离与功耗越接近比例关系，相关系数越接近1。

计算相关系数的公式为，其中h为汉明权重，t为功耗的值

假设攻击者具有以下能力：

  • 任意明文均可加密（选择明文攻击）
  • 能够测量 AES 第一轮 SubBytes 处理的功耗

然而，AES 加密密钥无法直接得知。攻击者按照以下步骤进行攻击

  1. 通过大量明文获取 AES 第一轮 SubBytes 处理的功耗
  2. 选择密钥
  3. 使用选择的密钥，与明文进行 AES 第一轮 SubBytes 处理
  4. 计算相关系数
  5. 产生正确的密钥

CTF里的考察

GOOGLECTF 2022 ELECTRIC MAYHEM CLS

给出了50组明文和对应的密文以及功耗曲线，要求恢复密钥

pic1.png

波形清晰，从波形来看是10轮的 AES。

从trace.json获取到所有的信息后，便挨个字节去计算汉明重量和相关系数。在单个字节的相关系数的比较中，系数最大的就是正确的字节。

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
# script: https://trmr.hatenablog.com/entry/2018/03/18/220441

import json
import numpy as np
import matplotlib.pyplot as plt
import scipy.io as sio
from Crypto.Cipher import AES

humming = [bin(n).count("1") for n in range(256)]

json_open = open("traces.json", 'r')
json_load = json.load(json_open)

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
    )


def addkey_subbytes(pt, guesskey):
    return sbox[pt ^ guesskey]

N = len(json_load)
print(N)

bestguess = [0] * 16
data_start = 0
data_end = 100
NUM_POINTS = data_end - data_start
NUM_TRACES = len(json_load)
traces = []

for pt_ct_pm in json_load:
    traces.append(pt_ct_pm['pm'][data_start:data_end])

for k_idx in range(16): # determine key index
    cpaoutput = [0] * 256
    maxcpa = [0] * 256
    bestcor = 0
    bestkey = 0
    
    for kguess in range(256): # determine word key candidate
        sumnum = np.zeros(NUM_POINTS)
        sumden1 = np.zeros(NUM_POINTS)
        sumden2 = np.zeros(NUM_POINTS)
        hyp = np.zeros(NUM_TRACES)
        
        for t_idx in range(NUM_TRACES): # hypothesis hamming weight
            hyp[t_idx] = humming[addkey_subbytes(json_load[t_idx]['pt'][k_idx], kguess)]
        
        h_mean = np.mean(hyp, dtype=np.float64)
        t_mean = np.mean(traces, axis=0, dtype=np.float64)
        
        for t_idx in range(NUM_TRACES):
            hdiff = (hyp[t_idx] - h_mean)
            tdiff = traces[t_idx] - t_mean
            
            sumnum = sumnum + (hdiff * tdiff)
            sumden1 = sumden1 + hdiff ** 2

            sumden2 = sumden2 + tdiff ** 2
        cpaoutput[kguess] = sumnum / np.sqrt(sumden1 * sumden2)
        maxcpa[kguess] = max(cpaoutput[kguess]) # max(abs(cpaoutput[kguess]))
    
    bestguess[k_idx] = np.argmax(maxcpa)
    print("[+] best guess key [{0}] is {1:02x} (score: {2})".format(k_idx, bestguess[k_idx], maxcpa[bestguess[k_idx]]))

strkey = ''.join(map(chr, bestguess))
print(strkey)

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
50
[+] best guess key [0] is 57 (score: 0.7664977105152343)
[+] best guess key [1] is 30 (score: 0.8037369571679035)
[+] best guess key [2] is 63 (score: 0.8157907186646868)
[+] best guess key [3] is 6b (score: 0.8521975480655525)
[+] best guess key [4] is 41 (score: 0.8582517655176524)
[+] best guess key [5] is 77 (score: 0.8911782264396743)
[+] best guess key [6] is 6f (score: 0.8435973736511324)
[+] best guess key [7] is 63 (score: 0.9323855381027755)
[+] best guess key [8] is 4b (score: 0.7750422415424753)
[+] best guess key [9] is 61 (score: 0.7558696238936866)
[+] best guess key [10] is 57 (score: 0.6984881287051522)
[+] best guess key [11] is 6f (score: 0.7036888779819861)
[+] best guess key [12] is 43 (score: 0.8914487915813523)
[+] best guess key [13] is 6b (score: 0.8666624881937892)
[+] best guess key [14] is 61 (score: 0.8998081004528541)
[+] best guess key [15] is 31 (score: 0.8984227108207175)
W0ckAwocKaWoCka1