Correlation Power Analysis (CPA) Technical Guide

Basic Principles

Correlation Power Analysis (CPA), also known as power attack, is a side-channel power analysis method. It operates by establishing correlations between hypothetical models and actual power consumption to derive the correct data model. The key is determined by selecting the value with the highest correlation.

How to Use CPA to Decrypt Encryption Keys

1. Finding Leakage Points

Power analysis typically focuses on processes with the highest power consumption. In AES, for example, the SubBytes operation consumes noticeably more power due to the presence of S-box and table lookups. The first round is often targeted since it involves the original key.

Important Note: We focus on leakage points where power consumption is most obvious, particularly after S-box lookup. This is because:

  • Registers show distinct power consumption P_{data} during value assignment
  • At the assembly level, S-box operations require multiple move instructions for value retrieval and decoding
  • The matrix operations after S-box cause power leakage due to large matrix movements
  • The magnitude of high-low level transitions (0-1) increases significantly during these operations

2. Measuring Actual Power Consumption

Using AES-128 as an example:

  1. Select N plaintexts and group them into 128-bit blocks (typically arranged as 16 bytes in a 4x4 matrix)

  2. Set variable PT_i (plaintext divided into 16 groups), example:

    1
    32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34

    Where PT_0=32, PT_1=43, etc.

  3. Obtain the power trace T = D * T and establish the power matrix:

    T=t0′=t0,1,...,t0,T′T={t'_0={t_{0,1},...,t'_{0,T}} }

    This represents D total power traces, each containing T sampling points.

3. Modeling Power Consumption for Intermediate/Leakage Values

For AES analysis:

  1. Set up a hypothetical key set:

    K=(k1,...,Kk),where k∈28K=(k1,...,K_k), where \ k ∈ 2^8

  2. Choose a matrix shape corresponding to the plaintext (N * k)

  3. Calculate model power consumption at leakage point:

    HW(f(T∗K))HW(f(T*K))

    Note: For each BYTE, the power intermediate value matrix is N * K (simplified)

4. Mapping Linear Correlation Calculation

Create a mapping between modeled and actual power consumption matrices:

  1. For the nth trace with plaintext PT_n:

    • Intermediate value/hypothetical power matrix = HW(sbox(PTn,K))HW(sbox(PT_n,K))
    • Corresponding to Tn=tn′=tn,1,...,tn,T′T_n={t'_n={t_{n,1},...,t'_{n,T}}}

  2. Calculate correlation using the formula:

    rij=∑i=0N(hN,i−hN,iˉ)(TN,i−TN,iˉ)∑d=1D(hi,j−hˉi,j)2∑d=1D(Ti−Tˉi)2r_{ij} = \frac{\sum_{i=0}^N (h_{N,i} - \bar{h_{N,i}})(T_{N,i} - \bar{T_{N,i}})}{\sqrt{\sum_{d=1}^D (h_{i,j} - \bar{h}_{i,j})^2} \sqrt{\sum_{d=1}^D (T_{i} - \bar{T}_{i})^2}}

    Where:

    • rijr_{ij} represents the score at point J when the key is i
    • i={0,…,256}, j∈{0,T}

5. Implementation Example

Using plaintext:

1
32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34

And key:

1
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f

Implementation steps:

  1. Randomly select plaintexts p_1,p_2,…,p_N

  2. Record traces (voltage v, T samples per trace)

  3. For each byte (1:16):

    1
    2
    3
    For k = 0:255 (all possible keys)
        For sampling point m = 0:M
            Calculate correlation

    Final correlation power matrix shape: 255:M

  4. Example analysis of element (1,1):

    • Value = cor(HW(:N,0),T(:N,0))
    • Physical meaning: correlation between hypothetical key 0’s Hamming Weight with all traces and actual power curve at point 0
    • N (trace count) is crucial for correlation attack effectiveness

Important Considerations

  1. Correlation Definition:

    • Uses Pearson binary correlation between hypothetical and real power consumption
    • Analysis performed across entire curve
    • Proven that correlations between different leakage points are random

  2. Implementation Notes:

    • Must maintain precise correspondence between hypothetical and real power consumption
    • Compare correlation scores between each row and guessed values
    • Proper timing and synchronization are crucial for accurate results

CPA（相关功耗分析）基本原理

CPA，即相关功耗分析，也称为功耗攻击。它是一种功耗分析侧信道方式，通过建立假设模型，再利用数学方法分析其与实际功耗的相关性，继而选出不同候选密钥值的得分。

如何使用CPA解密加密密钥

  1. 寻找泄漏点：在功耗分析中，我们不关注整体时间维度很重要，反而，因为会提高SNR，我们更关注密码设备的加密时刻的功耗泄露。通常这个过程的功耗消耗最好是占比最高的。例如在AES中，SubBytes过程中，查表过程由于访存（通用CPU），能耗明显。

    注意我们关注的泄漏点都是功耗比较明显的地方，比如SBOX之后的查找。这是因为寄存器在赋值的时候，数据功耗会相对明显PdataP_{data}.
    理解：
    这里我们可以用汇编层以下的代码去理解
    比如SBOX 会多次运用move指令取值 译码
    SBOX之后的矩阵同样会mova大矩阵导致功耗泄露，这里的0 1（高低电平转换量级就会增加）

  2. 测量实际功耗：（以AES-128为例）

    1. 选择N个明文并分组，每组128位（通常分为16字节，4x4矩阵）。设置变量PTiPT_i（明文分为16组），例如：

      32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34

      PT0=32PT_0=32，PT1=43PT_1=43，依此类推。

      得到：

      明文对矩阵 P=D×PTiP = D\times{PT_i}

      能量迹T=D×t′0T= D\times t'0，

      其中PTiPT_i 代表每个明文中的第ii字节,T’0对应功耗矩阵 t0′=t0,1,...,t0,T′t'_0={t_{0,1},...,t'_{0,T}}共T个采样点，D表示总共对应的曲线数量。

  3. 确定中间/泄露值的建模功耗：

    对于AES而言，由于第一轮轮异或包含密钥原始值和明文，我们选取该轮SBOX作为我们攻击的时刻。

    1. 设定一组假设密钥集合K=(k1,...,Kk)K=(k1,...,K_k),这里对于AES -128,k∈28k \in 2^8

    2. 选择与明文对应的矩阵形状，这里为得到假设密钥集合Ci=D∗kC_i = D * k

    3. 计算泄漏点的模型功耗，我们得到h=HW(f(T∗K))h=HW(f(T*K))

      说明对于所有明文的BYTE，这个假设模型矩阵为 D×KD\times K

    思考：

    在这里，我们选择SBOX的操作作为中间值，是因为受功耗影响度大，但是，实际操作中我们选择的到底是$f =T \oplus K $ 还是 f=Sbox((f（T⊕K))f = Sbox((f（T\oplus K))

  4. 映射线性相关度计算（实际值与假设值之间）：

    我们将上述功耗和已经得到的真实功耗矩阵做一个映

    以一条功耗曲线为例，取第n条trace，对应的明文为PTnPT_n那么他的中间值/假设功耗矩阵即HW(sbox(PTn,K)sbox(PT_n,K) 对应的TnT_n=tn′=tn,1,...,tn,T′{t'_n={t_{n,1},...,t'_{n,T}}}

    利用下面的相关性公式计算. 我们求出这条曲线上每个点（J）的相关性得分，注意,由于目前只有一条曲线，那我们的均值和标准差

    rij=∑i=0N(hn,i−hN,Iˉ)(TN,i−TN,iˉ)∑d=1D(hi,j−hˉi,j)2∑d=1D(Ti−Tˉi)2(2)r_{ij} = \frac{\sum_{i=0}^N (h_{n,i} - \bar{h_{N,I}})(T_{N,i} - \bar{T_{N,i}})}{\sqrt{\sum_{d=1}^D (h_{i,j} - \bar{h}_{i,j})^2} \sqrt{\sum_{d=1}^D (T_{i} - \bar{T}_{i})^2}} \tag 2

    数据说明，rijr_{ij} i是代表密钥为i，能量迹在J点的得分

    显然 i=0,..256,j∈0,Ti={0,..256},j\in{0,T}

    上式中均值都是指总体样本的同一点的均值（纵向对比）

    具体的物理意义分别是 HˉN,i\bar H_{N,i}代表不同曲线下的密钥i汉明平均值（每个曲线的明文和当前密钥）

    TˉN,j\bar T_{N,j}代表不同曲线下，J代表不同曲线下时刻J的功耗平均值

    进阶:怎么理解皮尔逊系数的线性相关

    这里的线性度为什么不用斜率来判断？

    总体样本的重要性在这里面如何定量评估？（只提供了均值和方差的占比）

    思考

    1. 样本点不可能所有点都在已知的直线上，只能保证大概率分布,这样计算是左侧判断，如下图

    2. 为什么减去均值 利用均值减少偏移量，简化了计算（相当于计算样本的x,y以两个输入均值（xˉ,yˉ\bar x,\bar y）为原点的线性投影）

    3. 为什么需要除以标准差的乘积 因为只有这样，才能将相关系数限制在(−1,1)(-1,1)这个范围内

    4. 均值受高噪声点影响，如何确保其不影响 pearson系数，同时其对方差影响会较大，应该做极端值检测

      另外，spearman 以及kendall’s tau相关系数成比例地排列了数据队列 一定程度地避免了真实数据的影响

      这点还能够继续拓展研究

  5. 以一个明文为例：32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34，密钥为 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f

    编码实现：

    1. 以第一字节为例子，总体样本设置为50，我们计算出在每条曲线的第一字节与所有密钥的汉明密钥矩阵异或后的汉明重量均值 HW(SBOX((pt⊕keys))ˉ\bar {HW (SBOX((pt \oplus keys))}

      这里的矩阵形状为 H = N * 256 由当前明文与256假设密钥组成的列，注意这里的均值是整个列样本的均值，代表每条曲线第一字节与对应的假设密钥产生的均值。

      以32为例子，现在假设密钥值为2与其做异或然后查表得到32，以此类推，得到[，256]这个形状的矩阵

      以此类推，求出所有样本第一字节与假设值2异或形成的中间值，进而得到所有猜测的均值，进而带入后面的相关性计算。

    2. 映射真实功耗，同样功耗曲线样本为50，我们大概估算，这个曲线上在1000，5000这个范围内是AES在第一轮加密的操作

      以1050这个点为例，我们把所有样本在1050的能量点当作进行SBOX操作加密的值，这样，我们更进一步，由于响应延迟，每次操作会有波动，我们直接将得到区间所有的均值点带入trace1050ˉ\bar {trace_{1050}}

    3. 将1,2得到的数据和均值取相关性，最后利用公式 (2)\ (2)，得到该店（假设密钥，对应时刻）的数据得分，在所有假设密钥中，最大相关性点就是该点的得分

    思考：

    • 样本只提供所谓的计算均值，但是需要每条曲线都参与循环计算吗，我任意选取的单一曲线能否直接辨明
    • 判断泄漏点的相关问题，所谓的泄露值T检测，到底是什么。

    Flow

  • 皮尔逊二元相关性我们这里具象的是 假设功耗 与 真实功耗
  • 我们具体计算的时候是整条曲线做相关性分析（且这里已有结论证明不同泄露点之间相关性随机）
  • 因此，实际工程代码中，我们要注意==假设功耗==与==真实功耗==的对应,然后才是对比每行相关性与猜测值相关性的比分。