2020-03-01发表2022-05-29更新Cryptography10 分钟读完 (大约1481个字)

DCA - 对AES侧信道分析的总结

DCA计算原理与实现中的局限性

DCA采用与硬件上DPA相近的从trace到relationship computation的操作方案，通过采集样本-样本分类-样本相关性对比的方法，分析给出的猜测是否正确，得出结论。目前的情况是，处于中间的noisy round，无法抵御或完全抵御DCA攻击。

踪迹采集

踪迹采集器TracerGrind是一个valgrind的插件，他会记录每一次应用中的读写及其读写周期、外部调用、指令地址、数据地址、数据区域及长度等。一般我们需要采集的为数据的读写情况。每一次加密采集都会形成一个(明文，密文，读写上下文)三元组。不同的三元组有利于最终后期做CPA时不同的覆盖情况。根据算法内部的长度不同，需要采用不同的监视长度。如noisy_round是8-128的，两个64拼成一个128。这意味着大概率CPA所需要的读写踪迹分布在长度为8的部分上。这也是一开始分析8-128不成功的原因。

踪迹汇总

采集后的踪迹会汇总形成一个独立的有一定格式的二进制文件上，供Daredevil进行CPA分析。Daredevil一般采用一阶相关关系分析来做密钥的匹配工作。相关配置会写在config文件上。如

[Traces]
files=1
trace_type=i
transpose=true
index=0
nsamples=492096
trace=stack_data_rw8_201_492096.trace 201 492096

[Guesses]
files=1
guess_type=u
transpose=true
guess=stack_data_rw8_201_492096.input 201 16

[General]
threads=8
order=1
return_type=double
algorithm=AES
position=LUT/AES_BEFORE_SBOX
round=0
bitnum=all
bytenum=all
correct_key=0x000102030405060708090a0b0c0d0e0f
memory=4G
top=20

就代表了，踪迹的数据为整型，踪迹矩阵（时间为列，数据为行）需要经过转置（这里是固定参数），踪迹汇总名为stack_data_rw8_201_492096.trace，猜测推导输入是利用明文输入，名为stack_data_rw8_201_492096.input，一共进行了201此追踪，产生了492096个读写样本点，算法每轮长度为16字节（即针对0~15轮进行破解），用AES的在sbox之前的表来进行比对（这个通常要after sbox才能成功），针对round 0 进行破解，给出前20个最高可能的待选样本。

tracegraph 得到的chow-m4ri结果

构建猜想

构建猜想的过程进行选择函数的过程。选择函数会将每一个明文输入对应到字节一个映射过的字节，这个过程我们称之为猜想表对换。输入明文会被对换，然后按照16字节的对换后结果进行汇总。通常选择函数会将一个字节对应到一个对换过的汉明距离（当数据有缺陷的时候）或每一比特位置对应到0-1上，成为选择分类的依据。这里的矩阵结构比较不明显，他是一个$n \times m$的矩阵，n是采样次数，m是16，固定长度。代表输入的明文被合并到一个矩阵上。这些矩阵每个明文通过一个选择，就得到猜想。

for (i=0; i < nrows; i++) {
  for (j=0; j < n_keys; j++) {
      if (bit == -1) { /* No individual bits. */
        (*guess)[j][i] = HW ((TypeGuess) sbox[ (uint8_t) mem[i][bytenum] ^ j ]);
      } else if (bit >= 0 && bit < 8) {
        (*guess)[j][i] = (TypeGuess) ((sbox[ (uint8_t) mem[i][bytenum] ^ j ] >> bit)&1);
      }
  }
}

样本关系计算

这一步会将每一个样本点与上一步骤的猜想进行比对。每读写16个字节的样本，就与目标猜想进行一次比对。这也是为什么noisy round会成功的原因：如果你的选择函数有效，且你的有效区间被采样了，如果相关关系正确，你就必然会在后续的关系比对上产生一个峰值。但这也是为什么noisy round会导致部分出错的原因：我们攻击的是第0轮到第一轮之间的数据。如果这个16字节noisy round被拆开了有一半被当作下一个16字节样本，后续的所有过程会有连锁反应。这也是第一轮noisy round能部分阻挡DCA的原因。这也侧面证明了，noisy round在实现上与我们所想的，有一定的差别。他的结构跟正常AES轮次不太一样。

按照相关关系，给出Top K符合的字节

并不是每一次都能获取到最佳的比对字节。有可能有一个比对达标，但又有可能没有。其中，peek最接近0.25，0.5，0.75，1的，被认为是最佳选择。

常见的操作失败

目标数据长度不同。如：8-128的表必定对应长度为8字节，即64bit的读写区间。（因为8字节是目前最长的基础数据）如果使用了1、2、4字节，即char，short，int，会错误采样。默认进行4字节的采样。
目标地址不能精准定位。这tracegraph，也确实是吹牛。因为几乎不可能看出来地址在哪里。
动态库有自己的地址空间，必须采取其他措施。

WBSM4可能存在的隐患

仿射变换的计算过程会直接干扰到对换关系的比对，这会导致cpa无法进行或误判。这点日后深入拓展。
主密钥的情况，会有更多出入。aes和des的第一轮密钥都是原生密钥没有改变，所以第一轮就给出master key。sm4的情况？

#crypto