侧信道攻击：SPA / DPA
参考资料：Cryptographic Engineering, by Cetin Kaya Koç, Editor Springer.
文章目录
Side-Channel Analysis
对于密码算法的攻击手段，往往是将密码算法作为一个黑盒来调用，使用代数手段尝试恢复秘密值。但是一旦将密码算法实现在了软/硬件中，根据软/硬件的工作特性它总会泄露一些中间状态的信息，可以使用统计手段来恢复这些中间值从而获得秘密值。
侧信道敌手的能力，远比在安全归约模型中所假设敌手的能力要强得多（安全归约模型并不 catch 的情况）。在归约下安全的密码算法，在实际中不一定安全；但没有安全归约的密码算法，很难让人相信它是安全的。
Timing Analysis
如果逻辑分支（if, case, continue, break, return）与秘密值有关，并且不同逻辑分支的执行时间明显不同。那么通过观察程序的执行时间长短，可以区分程序执行了哪个分支，从而区分出秘密值的
1
1
1 比特信息。
Sample Power Analysis
所需设备：示波器（Oscilloscope）、电磁探头（EM probe）、电阻（resistor）、密码设备、电脑（PC）。
一种简单的方案：
- 为密码设备供电，由 PC 为它提供明文。
- 在密码设备的接地线上串联电阻，电阻两端连接示波器。
- 示波器结果发送到 PC 上，记录已知明文的能量迹（power trace）。
对于更加复杂的功耗攻击，应该使用 EM probe 通过侵入式 / 非侵入式来探测芯片上不同部位的电磁信号。采样率应当满足 Nyquist-Shannon sampling theorem，即至少是输入信号的最大频率的两倍；实际中两倍是不够的，但是经验上几倍就够了。
能量消耗是数据依赖或者操作依赖的，对于不同的数据和操作其能量消耗并不相同。有不少的能量泄露模型，比较简单且常用的两个模型，
-
汉明重量模型（Hamming-weight model）：假设能量消耗正比于正在被操作的数据的汉明重量、或者正在执行的指令的汉明重量。
-
汉明距离模型（Hamming-distance model）：假设能量消耗正比于当前状态相较于前一个状态的汉明距离。
一般而言，汉明重量模型适合于软件实现（总线，寄存器），汉明距离模型适合于硬件实现（CMOS 的比特翻转）。
例如，一个未知指令
f
(
x
)
f(x)
f(x)，它对于输入
x
∈
{
0
,
1
}
8
x in {0,1}^8
x∈{0,1}8 执行运算。当选取不同的输入
x
x
x 时，测得的能量迹的峰值不相同。假设泄露模型已知（例如汉明重量模型，依赖于
H
W
(
x
)
HW(x)
HW(x)），那么根据
x
∈
[
0
,
255
]
x in [0,255]
x∈[0,255] 的若干能量迹，可以确定出
f
f
f 是哪种指令。
Differential Power Analysis
然而，环境噪声（这也包括与秘密值无关的其他操作）可能会严重影响 SPA 的效果。假设环境噪声是高斯白噪声，那么多次实验取平均可以降低噪声（高斯分布加和的标准差按平方根增长）。
Boolean selection function：对于输入
y
y
y，输出
σ
(
y
)
=
0
sigma(y)=0
σ(y)=0 或者
σ
(
y
)
=
1
sigma(y)=1
σ(y)=1（例如 MSB 函数），这被用于对若干条能量迹的分组
Y
0
=
{
y
∣
σ
(
y
)
=
0
}
,
Y
1
=
{
y
∣
σ
(
y
)
=
1
}
mathcal Y_0 = {y|sigma(y)=0}, mathcal Y_1 = {y|sigma(y)=1}
Y0={y∣σ(y)=0},Y1={y∣σ(y)=1}
Bit Tracing：对于
Y
0
,
Y
1
mathcal Y_0,mathcal Y_1
Y0,Y1 对应的两组能量迹，计算这两组能量迹的平均值，然后计算它们的差分作为 DPA trace，
Δ
(
t
)
:
=
⟨
P
i
(
t
)
⟩
Y
0
−
⟨
P
i
(
t
)
⟩
Y
1
Delta(t) := langle P_i(t)rangle_{mathcal Y_0} - langle P_i(t)rangle_{mathcal Y_1}
Δ(t):=⟨Pi(t)⟩Y0−⟨Pi(t)⟩Y1
例如分组密码中，明文
{
x
i
}
=
[
0
,
255
]
{x_i}=[0,255]
{xi}=[0,255]，秘钥
k
∈
[
0
,
255
]
k in [0,255]
k∈[0,255]，S-Box 运算为
y
i
=
S
(
x
i
⊕
k
)
y_i=S(x_i oplus k)
yi=S(xi⊕k)。密码设备内置秘钥
k
∗
k^*
k∗ 加密明文
{
x
i
}
{x_i}
{xi}，我们采集到已知明文
{
x
i
}
{x_i}
{xi} 的能量迹
{
P
i
(
t
)
}
{P_i(t)}
{Pi(t)}，在汉明重量模型下
S
S
S 执行的时刻能量消耗关于
H
W
(
y
i
)
HW(y_i)
HW(yi) 线性变化（服从高斯分布
N
(
m
+
k
⋅
H
W
(
y
i
)
,
σ
2
)
N(m + k cdot HW(y_i), sigma^2)
N(m+k⋅HW(yi),σ2) 的随机变量）。
假设 S-box 的输出是均匀的（实际上并不均匀），那么根据
M
S
B
(
y
i
)
=
0
/
1
MSB(y_i)=0/1
MSB(yi)=0/1 对这些
{
P
i
(
t
)
}
{P_i(t)}
{Pi(t)} 分组后，
Y
0
mathcal Y_0
Y0 中的字节
y
i
y_i
yi 的平均汉明重量为
7
/
2
=
3.5
7/2=3.5
7/2=3.5，而
Y
1
mathcal Y_1
Y1 中的字节
y
i
y_i
yi 的平均汉明重量为
1
+
7
/
2
=
4.5
1+7/2=4.5
1+7/2=4.5。
我们随机猜测
k
∈
[
0
,
255
]
k in [0,255]
k∈[0,255] 的值：如果猜对了
y
i
=
x
i
⊕
k
∗
y_i = x_i oplus k^*
yi=xi⊕k∗，那么采集到的能量迹被正确地分组到
Y
0
,
Y
1
mathcal Y_0,mathcal Y_1
Y0,Y1 中，所以计算出的
Δ
(
t
)
Delta(t)
Δ(t) 将会出现明显的峰值；如果猜错了
y
i
≠
x
i
⊕
k
∗
y_i neq x_i oplus k^*
yi=xi⊕k∗，那么它们被随机分成两组，则
Δ
(
t
)
Delta(t)
Δ(t) 中将不会出现峰值（实际中会出现矮小的峰值）。这就区分出了正确秘钥。
DPA 的步骤：
- 确定一个能量泄露模型（汉明重量模型、汉明距离模型）
- 找出一个与秘密值有关的中间值（比特选择函数），它使得在选定模型上的功率表现不同
- 收集一些已知明文的能量迹（反映了中间值的统计信息）
- 猜测秘钥的值，计算对应的中间值，把这些能量迹分成两组（提取统计特征）
- 计算两组能量迹的均值迹，然后计算它们的差分迹（消除噪声）
- 查看是否有峰值，如果有那么说明秘钥猜对了，如果没有那么重新执行 step 4 直到出现峰值（不需要重新采集能量迹）
其他攻击
-
模板攻击（TA）：对于不同的秘密值计算一个模板
(
m
i
,
C
i
)
(m_i,C_i)
(mi,Ci)，其中m
i
m_i
mi 是均值C
i
C_i
Ci 是协方差矩阵，然后计算真实能量泄露的最大似然模板。 - 相关能量攻击（CPA）：假设一个秘钥值，计算出假设能量泄露，然后计算它与真实能量泄露的相关系数。
- 随机模型（Stochastic Model）、互信息分析（Mutual Information Analysis）、Kolmogorov-Smirnov Test，等等。
对抗方法
关键点：抑制侧信道信息与所用秘密值之间的相关性。
-
减少侧信道信息的泄露
- 程序的执行是常数时间的
- 分支不应依赖于秘密值（不仅是运行时间，还有访存地址）
-
添加噪声来掩盖侧信道信息
- 功率平滑（power smoothing），使得能量迹的变化平缓
- 插入待机状态（wait state, 硬件）或者空指令（dummy cycle, 软件）
- 对于同步信号使用不稳定的时钟（unstable clock）
- 软件层面，在密码算法中添加一些随机的数据掩码（data mask）
一般而言，混合使用软件保护以及硬件保护的效果更好。