陈佳哲 , 李贺鑫 , 王亚楠 , 王宇航
中国信息安全测评中心, 北京 100085

收稿日期: 2016-01-24
基金项目: 国家自然科学基金资助项目(61402536,61202493,61402252)
作者简介: 陈佳哲(1985-), 男, 助理研究员。E-mail: chenjz@secemail.cn


摘要：t检验是统计学中用来检验2个未知方差正态总体均值关系的假设检验方法。当总体的方差不相等, 且样本量也不相等时, Welch t检验是一种比Student's t检验更可靠的方法。该文将借鉴采用t检验对AES的实现进行侧信道信息泄露评估的方法, 用Welch t检验来对3DES算法运行过程中的侧信道信息泄露进行评估, 以衡量其是否可能受到一阶DPA攻击。该文构造了适合于3DES算法的Welch t检验方法, 并对实现方法不同的3个运行3DES算法的设备进行了实验。实验结果表明该文的方法是有效的。
关键词： Welch t检验 3DES算法 侧信道 信息泄露评估
Evaluating side-channel information leakage in 3DES using the t-test
CHEN Jiazhe, LI Hexin, WANG Yanan, WANG Yuhang
China Information Technology Security Evaluation Center, Beijing 100085, China


Abstract:The t-test is a hypothesis test that deals with two Gaussian samples with unknown variances. When the two samples have unequal variances and unequal sample sizes, the Welch t-test is more reliable than the Student's t-test. This paper evaluates the 1st order side-channel information leakage of 3DES with an AES type t-test. Welch t-tests suitable for evaluating 3DES are given with tests on three different devices that show this method is effective.
Key words: Welch t-test3DES algorithmside-channelinformation leakage evaluation
自从Kocher等^[1-2]提出了侧信道攻击之后，密码算法在运行过程中的物理安全受到了极大关注。因此，密码算法在实现时是否存在侧信道信息泄露以使密钥被恢复是对密码芯片(特别是智能卡芯片)产品进行安全性测评中需要重点衡量的方面。
在目前CC(Common Criteria)^[3]的测评方法^[4-5]中，对密码芯片中密码实现安全性的衡量主要是尝试所有已知的侧信道攻击方法来对被测芯片进行分析，然后对成功实施攻击所需的知识、人员、设备、时间等因素进行评分。这种做法的不足之处在于尝试所有的攻击方法要花费很长的时间，其次随着新攻击方法的层出不穷，采用现有的方法进行攻击可能不够完备^[6]。
因此，对密码芯片运行过程中信息量泄露的多少进行评估，既有利于对密码芯片的安全性进行定性的衡量，又有利于发现可能转化成侧信道攻击的泄露。在CC测评中，评估者如果先对芯片密码算法运行过程中的信息泄露进行衡量，再考虑尝试一些攻击方法，则能提高测评的效率和准确性。
Goodwill等^[7]采用了t检验来对AES(advanced encryption standard)的实现进行侧信道信息泄露评估，文^[8]中将该方法拓展到了RSA(Rivest-Shamir-Adleman)算法。这些方法被ISO/IEC标准草案^[9]所采用，用于衡量密码算法实现的DPA (differential power analysis)^[1]安全性。文^[6]中比较了3种评估方法：t检验、CMI (continuous mutual information)^[10]及DMI (discrete mutual information)^[11]，并指出在总体分布接近于正态分布，且需要衡量总体均值差异的显著性时，t检验的效果是比较好的。如果要对任何情况下的泄露进行衡量，则CMI是唯一的选择。在对被测芯片的了解并不是十分充分而难以准确估计MI (mutual information)的情况下，t检验是最好的选择^[6]。因此，本文将采用Welch t检验来对DES和3DES算法运行过程中的侧信道信息泄露进行评估。
自20世纪70年代发布之后，DES算法成为了应用最广泛的密码算法之一。虽然由于密钥长度问题，现在已不建议使用DES，但3DES作为3个DES的迭代(加密—解密—加密)，其密钥长度是DES的3倍(若第一个和最后一个密钥相同，则为2倍)。因此3DES仍然在许多重要领域广泛应用^[12]。
由于3DES算法只是3个DES的迭代，因此对3DES算法的侧信道分析的原理和技术与DES一样，只是在密钥恢复攻击中所需恢复的密钥比特数不一样。本文的目的是对侧信道信息泄露进行评估，DES和3DES使用的方法是一样的。因此，本文中的方法对DES和3DES同时适用。
本文将针对DES/3DES算法的特点构造几个Welch t检验，并对3个密码设备中实现的DES/3DES算法进行1阶DPA信息泄露评估。本文将在第1节中给出评估方法，并在第2节中给出实验结果，第3节将总结全文。
1 用Welch t检验对3DES算法进行安全性评估本节将给出对3DES算法进行侧信道信息泄露评估的方法。首先对Welch t检验做简要介绍，然后给出详细评估方法。
1.1 Welch t检验普通的t检验(Student's t-test)用于2个总体的方差未知但相等的时候。在2个总体的样本数和方差都不相等的时候，可以用Welch t检验，其统计量为

$t=\frac{{{X}_{A}}-{{X}_{A}}}{\frac{S_{A}^{2}}{{{N}_{A}}}+\frac{S_{B}^{2}}{{{N}_{B}}}}.$

其中：X_A、X_B为集合A、B中的样本均值，S_A²、S_B²为A、B中的样本方差，N_A、N_B分别为A、B的样本数。在Welch t检验中，原假设和备择假设分别为

${{H}_{0}}:{{\mu }_{A}}={{\mu }_{B}},{{H}_{1}}:{{\mu }_{A}}\ne {{\mu }_{B}},$

其中μ_A和μ_B分别为总体A和B的期望。需要根据显著性水平α和自由度v来计算临界值C从而确定拒绝域。即当|t|≥C时则判定拒绝H₀，否则判定接受H₀. 其自由度为

$v=\frac{{{\left( \frac{S_{A}^{2}}{{{N}_{A}}}+\frac{S_{B}^{2}}{{{N}_{B}}} \right)}^{2}}}{\frac{{{\left( \frac{S_{A}^{2}}{{{N}_{A}}} \right)}^{2}}}{{{N}_{A}}-1}+\frac{{{\left( \frac{S_{B}^{2}}{{{N}_{B}}} \right)}^{2}}}{{{N}_{B}}-1}}.$

1.2 DES/3DES简介DES算法的密钥长度为64位，但其中8位为奇偶校验位，这样实际的密钥长度只有56位。64位的明文在进行第1轮运算之前，需经过一个初始变换；中间变量在最后1轮运算之后经过一个逆变换得到密文。因为这2个变换与分析无关，因此不详细描述。DES算法是Feistel结构的分组密码算法，其轮运算如图1所示。

图 1 DES算法的轮运算

图选项

在第i(1≤i≤16)轮中，输入的64位中间变量分成各32位的左右2个部分L_i-1和R_i-1。R_i-1经过E扩展、轮密钥异或、S盒层、P置换后与L_i-1异或生成R_i，同时L_i←R_i-1,将第i轮S盒层的输出定义为S_i。对于DES算法的详细介绍参见文^[13]。3DES的加密过程为3次DES迭代：

$\begin{align} & ciphertext= \\ & DES_{{{k}_{3}}}^{encrypt}\left( DES_{{{k}_{2}}}^{desrypt}\left( DES_{{{k}_{1}}}^{encrypt}\left( pla\operatorname{int}ext \right) \right) \right). \\ \end{align}$

其中k₁和k₃可以不同，也可以相同，对应着不同的3DES密钥长度(112位或168位)。
在DES/3DES算法运行过程中，其功耗或电磁信号可能会泄露其中间变量的相关信息。根据不同的实现方式，泄露的模型也会不一样。因此本文将构造一些Welch t检验来对中间变量的信息泄露进行分析。
1.3 构造数据集合的方法由节1.1介绍的Welch t检验方法可知，要准确地评估密码算法的侧信道信息泄露，关键步骤在于构造合适的集合A、B. 在文^[7]中构造了两大类型数据的t检验来评估AES算法的信息泄露:第1大类是固定数据和随机数据的t检验，其中固定数据满足一定的条件；第2大类是将随机数据根据中间变量值的不同分成2个集合，然后对2个集合进行t检验，并且对AES算法中间轮(即除去第1轮和最后1轮)的信息泄露进行评估。
由于对信息泄露的衡量是以进行CC测评为最终目标，因此对本文有用的侧信道信息泄露是最终能转化成侧信道攻击的信息泄露，所以本文将采用和文^[7]中不一样的思路：1) 不构造第1大类的数据，而只是构造第2大类的数据。2) 根据3DES算法的特点来构造数据集合，尽可能地反映3DES运行过程中可能被利用的信息泄露。3) 在文^[7]中，探测多比特信息泄露时，作者对2个轮输出字节做t检验。本文将不检验具体值，而是检验汉明重量，以更加贴近CPA (correlation power analysis)^[14]等攻击方法。同时将对所有输出半字节(nipple)值的汉明重量做检验以完整地度量信息泄露。4) 对3DES运行的前2轮和后2轮信息泄露进行衡量，这样的信息泄露有利于转化成侧信道攻击。对于前2轮的中间变量，通过明文加密计算得来；对于后2轮的中间变量，通过密文解密计算得来。在上述原则下，数据构造方式如下。
在数据获取阶段，任意选定一个固定的密钥，随机选取N个明文进行3DES加密并得到相应密文，同时用示波器记录相应的功耗曲线，将这N条功耗曲线记为$\overrightarrow{{{r}^{j}}}$(r₀^j,r₁^j,…,r_n-1^j)，其中j=0,…,n-1。对于这些功耗曲线，需要进行一定的信号处理并将它们进行对齐。然后，对获取的数据进行分类，构造Welch t检验来评估3DES算法运行过程中的信息泄露。为了使3DES运行过程中的信息泄露点都能被检测到，且尽可能地将目前有效的泄露模型都考虑到，本文设计了下列8个检验。
检验1?对每个S盒输出的每一个比特，将功耗曲线分成2个集合。集合A：该比特的值为0。集合B：该比特的值为1。
检验2?对于R_i(当分析前2轮时)或L_i-1(当分析后2轮时)的每一个比特，将功耗曲线分成2个集合。集合A：该比特的值为0。集合B：该比特的值为1。
检验3?对于S_i⊕R_i-1的每一个比特，将功耗曲线分成2个集合。集合A：该比特的值为0。集合B：该比特的值为1。
检验4?对于R_i⊕R_i-1的每一个比特，将功耗曲线分成2个集合。集合A：该比特的值为0。集合B：该比特的值为1。
检验5?对每个S盒的输出，将功耗曲线分成2个集合。集合A：该S盒输出的汉明重量为h(h=0，…，4)。集合B：该S盒输出的汉明重量不为h。
检验6?对于R_i(当分析前2轮时)或L_i-1(当分析后2轮时)的每一个nipple，将功耗曲线分成2个集合。集合A：该nipple的汉明重量为h(h=0，…，4)。集合B：该nipple的汉明重量不为h。
检验7?对于S_i⊕R_i-1的每一个nipple，将功耗曲线分成2个集合。集合A：该nipple的汉明重量为h(h=0，…，4)。集合B：该nipple的汉明重量不为h。
检验8?对于S_i⊕R_i-1的每一个nipple，将功耗曲线分成2个集合。集合A：该nipple的汉明重量为h(h=0，…，4)。集合B：该nipple的汉明重量不为h。
分别对功耗曲线上的每个点i(i=0,…,n-1)做以上8个检验，同时针对的是3DES算法的前2轮和后2轮。
1.4 数据量及阈值的选取本小节中需要确定检验的拒绝域和所需数据量。在统计学中，假设检验可能发生2种类型的错误。第Ⅰ类错误：在H₀为真的情况下拒绝H₀. 在本文中，即实际没有信息泄露，但检验结果有。第Ⅱ类错误：在H₀为假的情况下接受H₀. 在本文中，即实际有信息泄露，但检验结果没有。
对于评估者来说，需要将犯2类错误的概率都尽量降低以保证评估的准确性。
在节1.3的数据选取方法中，由于明文是随机选的，当只关注一个中间变量比特时，其为0或1的概率大概为1/2,因此自由度v与N是一个数量级的。但当关注的是一个nipple的汉明重量，则自由度随着汉明重量的值会有较大变化。因此，为了在保证第Ⅰ类错误概率α低的同时，也使第Ⅱ类错误的概率β尽量低，需要在保证测评效率的同时选择足够大的N。本文的例子中选择的N为5万。为了使α尽量低，本文将拒绝域取为|t|≥±5,此时能保证显著性水平大于99.999 9%.
1.5 重复检验文^[7]中指出，因为每条功耗曲线上包含着很多点，即使α和β足够低，仍存在着某个点出错的可能性。因此为了提高正确率，可以选择进行重复检验：获取2N条功耗曲线，选取其中的N条做节1.3所提到的Welch t检验，再对剩下的N条做同样的检验。对于功耗曲线上的某个点，只有同时在2个检验中落入拒绝域，才拒绝H₀.
2 实验结果为了验证第1节中方法的有效性，本文选择了3个运行3DES的密码设备进行实验。设备D1为一张智能卡，其3DES算法为软件实现，且无任何防护。设备D2为另一张智能卡，其3DES算法为硬件实现，无任何防护。设备D3为一个USB Key，其3DES算法为硬件实现，且D3中实现了一些抵抗侧信道攻击的防护措施，如时钟扰乱、硬件掩码、伪运算等。
对3个设备分别获取10万条曲线，将其分成2个5万条曲线，对每个5万条曲线应用节1.3构造的8个Welch t检验进行检测，采用节1.5所述的重复检验方法来进行拒绝/接受H₀的判定。下面分别对3个设备的检验结果进行介绍。
表1给出了对设备D1的每个检验的最大t值，出现最大t值的比特或nipple的位置和值，以及所在的轮数(第15、16轮指的是第3个DES的第15、16轮)。
表 1 设备D1的检验结果

检验	最大的t值
1	2 993.08 (第1轮，比特14)
2	322.33 (第2轮，比特25)
3	93.76 (第16轮，比特24)
4	83.97 (第1轮，比特28)
5	655.86 (第15轮，第4个S盒输出，h=0)
6	80.85 (第1轮，第7个nipple，h=4)
7	351.90 (第1轮，第3个nipple，h=4)
8	39.48 (第2轮，第5个nipple，h=1)

表选项






图2给出了对第1个5万条曲线的检验1中所有32个比特在所有时间点的t检验值。从所得出的结果可知，对设备D1的检验结果是拒绝H₀，即D1存在着明显的侧信道信息泄露。

图 2 对设备D1第1个5万条曲线的检验1中所有32个比特在所有时间点的t值

图选项

表2中给出设备D2的检验结果。图3给出对设备D2第2个5万条曲线的检验4中所有32个比特在所有时间点的t检验值。
表 2 设备D2的检验结果

检验	最大的t值
1	7.20 (第1轮，比特25)
2	13.74 (第1轮，比特25)
3	10.61 (第1轮，比特2)
4	36.92 (第1轮，比特21)
5	20.74 (第1轮，第1个S盒输出，h=2)
6	6.86 (第1轮，第4个nipple，h=4)
7	4.99 (第1轮，第3个nipple，h=0)
8	33.03 (第1轮，第6个nipple，h=1)

表选项

图 3 设备D2第2个5万条曲线的检验4中所有32个比特在所有时间点的t值

图选项

从实验结果可知，对于硬件实现3DES的设备D2，虽然其信息泄露不如设备D1明显，但仍然存在着较大的信息泄露。因此，对该设备判定拒绝H₀。
对于加了一系列侧信道防护措施，且是硬件实现3DES算法的设备D3，预期其和前2个设备有着不同的检验结果。由于设备D3是USB Key，本文采集其电磁信号曲线以避免外围电路对功耗信号造成的影响，其中一条电磁信号曲线如图4所示。

图 4 设备D3的3DES算法的电磁信号曲线

图选项

对设备D3进行和之前一样的实验，检验结果如表3所示。
表 3 设备D3的检验结果

检验	最大的t值
1	4.17 (第15轮，比特11)
2	4.62 (第1轮，比特12)
3	4.36 (第1轮，比特32)
4	4.15 (第2轮，比特9)
5	4.38 (第16轮，第7个S盒输出，h=2)
6	4.46 (第1轮，第5个nipple，值h=1)
7	4.79 (第1轮，第6个nipple，值h=2)
8	4.68 (第2轮，第8个nipple，值h=1)

表选项






图5中给出了对第1个5万条曲线的检验8的所有结果的重叠。

图 5 对设备D3第1个5万条曲线的检验8中的所有结果的t值

图选项

从上述结果看出，设备D3并没有明显的信息泄露，因此判定接受H₀.
对于设备D1和D2，进一步进行CPA^[14]攻击，实验结果显示密钥确实能被恢复。对设备D1，获取10万条曲线需要大概1 d；对于设备D2和D3，大概需要6 h。而对于3个设备，用个人电脑进行Welch t检验的时间均在几分钟之内。
3 总结和展望本文给出了对3DES算法的侧信道信息泄露进行Welch t检验评估的方法，并对3个不同3DES实现的密码设备进行了实验，实验结果符合预期。
本文的方法可以判定一个设备中的3DES算法是否泄露1阶DPA可以利用的侧信道信息，但对于高阶DPA则需要下一步再结合相应的高阶DPA模型进行分析。此外，对于存在信息泄露的设备，如何建立t值和侧信道攻击所需数据量及成功率的关系，也需要进行下一步的研究。

参考文献

[1]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Kocher P, Jaffe J, Jun B. Differential power analysis[C]//Proc CRYPTO'99. Berlin Heidelberg:Springer-Verlag, 1999:388-397.
[2]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Kocher P. Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[C]//Proc CRYPTO'96. Berlin Heidelberg:Springer-Verlag, 1996:104-113.
[3]	Journal of Central South University(Science and Technology), 41(2):649-654.--> CCMB-2012-09-001. Common Criteria for information technology security evaluation[S/OL]. (2012-09). http://www.commoncriteriaportal.org/cc/.
[4]	Journal of Central South University(Science and Technology), 41(2):649-654.--> CCMB-2012-09-001. Common methodology for information technology security evaluation[S/OL]. (2012-09). http://www.commoncriteriaportal.org/files/ccfiles/CEMV3.1R4.pdf.
[5]	Journal of Central South University(Science and Technology), 41(2):649-654.--> CCDB-2013-05-002. Supporting document-mandatory technical document:application of attack potential to smartcards[S/OL]. (2013-05). http://www.commoncriteriaportal.org/files/supdocs/CCDB-2013-05-002.pdf.
[6]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Mather L, Oswald E, Bandenburg J, et al. Does my device leak information? An a priori statistical power analysis of leakage detection tests[C]//Proc Advances in Cryptology-ASIACRYPT 2013. Berlin Heidelberg:Springer-Verlag, 2013:486-505.
[7]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Goodwill G, Jun B, Jaffe J, et al. A testing methodology for side channel resistance validation[C]//Proc NIAT 2011. Gaithersburg:NIST, 2011.
[8]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Jaffe J, Rohatgi P, Witteman M. Efficient side-channel testing for public key algorithms:RSA case study[C]//Proc NIAT 2011. Gaithersburg:NIST, 2011.
[9]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Easter R, Quemard J-P, Sakurai G. ISO/IEC DIS 17825:Information technology-Security technique-Testing methods for the mitigation of non-invasive attack classes against cryptographic modules[Z]. Berlin:DIN, 2014-12-01.
[10]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Chothia T, Guha A. A statistical test for information leaks using continuous mutual information[C]//Proc Computer Security Foundations Symposium (CSF). Piscataway, NJ:IEEE Press, 2011:177-190.
[11]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Chatzikokolakis K, Chothia T, Guha A. Statistical measurement of information leakage[C]//Proc Tools and Algorithms for the Construction and Analysis of Systems. Berlin Heidelberg:Springer-Verlag, 2010:390-404.
[12]	Journal of Central South University(Science and Technology), 41(2):649-654.--> EMV. Integrated Circuit Card Specifications for Payment Systems[S]. California:EMVCo, 2011.
[13]	Journal of Central South University(Science and Technology), 41(2):649-654.--> FIPS PUB 46-3. The Official Document Describing the DES Standard[S]. Gaithersburg:NIST, 1999.
[14]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Brier E, Clavier C, Olivier F. Correlation power analysis with a leakage model[C]//Proc CHES 2004. Berlin Heidelberg:Springer-Verlag, 2004:16-29.