智能卡加密算法的微分能量分析方法研究

    1 引言

    智能卡作为一种安全可靠的高技术产品, 在我国正逐步取代磁卡而广泛应用于金融行业以及其他相关产业。但部分用户在对智能卡产品的认识上存在着一些误区, 片面地认为所有拥有微处理器的智能卡都具有高安全性和高可靠性, 从而忽略了这方面的要求。事实上针对智能卡的攻击方法伴随着智能卡的发展而发展, 一直威胁着智能卡的安全。

    目前比较流行的是称作能量分析的攻击方法, 它分为两类: 简单能量分析( SPA)和微分能量分析( DPA)。SPA是一种直接解释能量消耗测定值的技术。系统消耗能量的大小随微处理器执行的指令不同而不同, 当微处理器在对加密算法的不同部分执行运算时, 能量消耗变化有的会很明显。借助这种特征, 攻击者能区分出单条指令, 达到破解算法的目的。DPA 的攻击力比SPA 强得多, 而且更加难以防范, 它不像SPA从系统的能量消耗直观地作出判断, 而是借助统计方法来提取与密钥有关的信息。尽管实现的过程更加复杂, 但降低了对攻击者的智能卡专业技术水平的要求。

    2 微分能量分析

    在密码的运算过程中, 智能卡执行一条指令所消耗的能量与指令的操作数相关。如果用PI 表示指令I 执行过程中平均消耗的能量, op₁ , op₂ , ..., op_n 表示I 的操作数, 当op₁ 取不同值时, 有 

    称P_I 与op₁ 相关, 即P_I ( 0) ≠ P_I ( 1) 。微分能量分析正是从这种相关性着手, 最终实现对加密密钥的破解。设P_I ( 0 ) , P_I ( 1)的差值为D_I , D_I 越大, 对作DPA 分析越有利。一阶微分能量分析往往采用以下步骤:

    ( 1) 确立类似于op₁ 的操作数或中间变量, 取值为α。要求根据已知智能卡信息( 明文、密文) D 和未知的密钥信息能够推导出它的值, 即α= f( K, D) 。

    ( 2) 对多组不同明文分别进行加密, 对相应的能量信号进行采样并记录波形。

    ( 3) 对K 的值进行猜测, 计算出相应的α, 将( 2) 中的采样结果按照α= 0 和α= 1 分成两组, 求两组的均值差( 即构建统计函数) 。α时刻均值差最大时, K猜测正确。从以上步骤我们可以看出, 攻击者要发动DPA 攻击, 需要具备以下条件: 熟悉智能卡中采用的加密算法原理结构; 知道智能卡处理的明文或者是处理后的密文; 有相应的硬件条件,用于测量能量消耗轨迹。图1 就是实施DPA 攻击的基本电路。 

    3 智能卡常用加密算法的DPA 攻击

    根据加密机制的不同, 加密算法可以分为两类: 对称加密算法和非对称加密算法。智能卡中常用的加密算法, 如DES,3DES, RSA 和ECC 等都可以归结到这两类算法中。DPA 最先是在针对智能卡的对称加密算法的破解方法研究中发现的, 但随后就发现它对破解非对称加密算法同样有效。下面我们分别就这两类算法中最具代表性的算法: DES 和ECC 来对DPA攻击进行分析。

    3. 1 DES 的DPA 攻击

    DES 是对称密码体制中最典型的一个例子, 它是由IBM 公司公布的一种加密算法, 1977 年被美国国家标准局确立为 联邦数据加密标准后完全公开, 是世界上技术最成熟的加密算 法。DES 在加密时, 将明文分成长度为64 位的由0、1 组成的 串, 使用的密钥长度为64 位。DES 采用了Feistel 网络结构, 有 16 个迭代周期, 每个周期按照公式( 1) 迭代: 

    其中, f( R _{i - 1} , K _i ) = P( S( E( R _{i - 1} ) ī K _I ) ) , K _i 表示第i 个迭代周期的密钥。迭代过程如图2 所示。 

     在对DES 进行DPA 分析时, 我们选定的中间操作数是第16 轮迭代过程输入L15 值中的一位, 设为d。d 与已知信息、待求密钥之间的关系如下式所示: 

    其中, b 为R ₁₆ 中由d 经过加密得到的二进制位。C* 为R15 中输入S* 的比特位。在每个迭代过程中, 密钥被分成了八个二进制密钥块, 分别对应一个S 盒, S* 是d 对应的S 盒。K*₁₆ 是输入S* 的六位二进制密钥块, K ₁₆ 中的一部分。K^*₁₆ 是破解的对象, 作为六位的二进制密钥块, 它的取值无非有64 种, 这其中当然包括正确的密钥。下面的工作就是要结合实际观测找出该密钥。

    假设DES 算法加密不同的明文时观测到的能量信号为Sij( i 表示明文编号, j 表示时间) 。明文数量为N 时, 针对K*16 的每一种猜测就会有N 个观测结果, 由式( 2) 计算出d 值, 根据d值对观测结果分类, 如下所示: 

    假定S₀ 和S₁ 的均值差为T[ j] , 考虑到S₀ 和S₁ 是随机能量信号集合分出的两个子集, 唯一的区别是加密进行到d 时d的取值不同, 因而S₀ 和S₁ 的均值是有差异的。对于T[ j] , 如果猜测密钥正确, 则在d 处理时刻T[ j] 会出现一个峰值, 与d无关的时刻, T[ j] 趋于零; 如果密钥错误, 由函数D 得出的d值可能与真值不符, 导致部分Sij 不能正确归入S₀ 和S₁ , 削弱了d 时刻应有的能量差异性, T[ j] 在这个时刻即使有峰值, 也无法与密钥正确时相比。不过相同的是在d 以外的点, T[ j] 仍然趋于零。因此, 找出64 个当中含有最大峰值的T[ j] 轨迹,其对应的密钥块即为K*₁₆ 。重复上述过程对其余七个S 盒进行分析, 就可以得出第16 轮使用的48 位密钥。要破解整个DES 密钥, 只需对前面各轮进行同样分析即可。

    3. 2 ECC 的DPA 攻击

   公开密钥算法通常基于一个数学上的难题, 椭圆曲线加密算法也不例外。考虑等式K = kG( K, G 是椭圆曲线上的点, k为小于G 的阶的整数) , 不难发现, 给定k 和G, 根据椭圆曲线加法法则, 计算K 很容易; 但给定K 和G, 求k 就相对困难了。

    我们把点G 称为基点, k 称为私有密钥, K 称为公开密钥。ECC 主要涉及的是类似kG 的点乘运算, 该运算在智能卡芯片中用指令实现时, k 往往写成二进制扩展形式, 即k = k _{n - 1} k _{n - 2}...k₀ , 而kG 则用连加的形式代替, 如下列代码所示: 

    其中, “+ ”是椭圆曲线上的加法, 运算法则与普通加法不同。从代码可以看出当循环运算进行到i 时, X[ 0] 的值仅与k的二进制扩展表示中的( k _{n - 1} , ..., k _i ) 有关。如果X[ 0] 的中间结果用pM表示( p 是整型系数, 随For 循环递增, 可能的取值取决于k _i ) , 那么运算过程中的能量消耗将与pM 二进制表示中的位相关。例如, 为了获取k 的二进制位k _{n - 2} , 我们可以考查4M中的位与能量信号的相关性。对N 个不同的M分别执行上述指令操作, 观测它们的能量信号轨迹, 记作S _i。选定4M二进制表示中的一个比特位( 如第二位b₂ ) 作为对S _i 进行分组的依据:

    S₀ = < S_i | b₂ = 0 >

    S₁ = < S_i |b₂ = 1 >

    设S₀ 和S₁ 的均值差为C( t) , 从它的轨迹就可以判断出k _{n - 2}的值。原因在于: d _{n- 2} = 0 时, 4M是中间结果, S_i 与b₂ 相关, 在b₂ 对应时刻C( t) 出现峰值; d _{n - 2} = 1 时, 4M不是中间结果, S₀ 和S₁ 的均值不再有明显差异, C( t) 不会出现峰值。依此类推, 我们可以获取k 二进制表示中剩余各位的值。

    4  AES 候选算法与DPA 攻击

    DES 使用的密钥因为太短, 无法满足安全要求, 正逐步走向末路。AES是美国国家标准技术研究所( NIST) 发起征集的旨在取代DES 的高级数据加密标准。它的基本要求是: 必须是私钥分组加密算法, 密钥长度至少为128 位。本文提到的AES 候选算法特指入围第二轮评选的五种算法( Twofish  ,Rijndael , Serpent , MARS, RC6 ) , 它们都有自己独特的设计思路和风格, 对许多目前流行的攻击方法有相当的抵抗能力, 但这并不包括DPA 攻击。

    ( 1) Twofish 加密算法使用16 轮的Feistel 网络结构, 在网络的输入和输出运用了白化处理技术。这种技术原理比较简单, 就是将待隐藏数据和特定密钥进行“加”或“异或”运算, 但产生的加密效果很强, 攻击者因此而得不到核心部分的输入输出。在利用DPA 对Twofish 进行分析时, 关键在于获取白化过程中采用的密钥。统计分析建立在如下基础上: 当白化密钥位是0 时, 对应输入的明文二进制位保持不变; 当白化密钥位是1 时, 对应输入的明文二进制位取反。我们可以对多组明文进行加密, 采集能量信号, 求出128 位白化密钥对应的明文二进制位与能量信号的协方差函数, 由于两者主要是在异或前读取数据, 异或和异或后写入结果时刻相关, 故协方差函数波形中有不多的几个峰值。主要观察的是异或前读取数据和异或后写入结果时刻对应的峰值, 两个峰值方向相同表示密钥是0,反之则表示密钥是1。在获取白化过程使用的密钥后, 接下来是希望通过Twofish 密钥生成算法推导出核心过程密钥, 但这无法直接实现, 只能是结合密钥生成算法和白化过程密钥将核心过程密钥取值范围缩小后逐一验证。

    ( 2) Rijndael 采用的是代替/ 置换网络, 当加密分组和密钥长度都为128 位时, 加密轮数是10。加密开始时, 输入分组的各字节按特定的方式装入一个矩阵State 中, 接下来是一个与密钥的异或操作, 不仅仅是在轮加密开始之前, 在每轮加密之中和轮加密之后都有类似的操作, 只是采用的密钥不同, 但它们都是由Rijndael 密钥生成算法统一生成。第一次的异或操作密钥完全可以通过DPA 攻击获取, 然后根据Rijndael 密钥生成算法直接推出其余各轮的密钥, 这与Twofish 相比要简单得多。

    ( 3) Serpent 是一个在初始置换和末尾置换之间安排有32轮加密操作的算法, 没有采用白化技术, 每一轮包含密钥混合运算、S- 盒及线性变换。针对Serpent 完全可以采用前面介绍的针对DES 类似的DPA 分析。考虑到利用Serpent 的密钥生成算法推出其余各轮密钥, 必须预知两轮以上的子密钥, 这就意味着攻击者至少要破解32 轮中前面至少两轮以上的加密过程。

    由此可见, Twofish, Rijndael, Serpent 只要利用简单的几轮DPA 分析得来的子密钥, 结合统一的相对独立的密钥生成算法, 就可以用来破解主密钥和其他的子密钥。但同样的方法对MARS 和RC6 并不适用, 这主要在于它们的密钥生成算法设计独特, 使得密钥间的递推难以实现, 这就迫使攻击者必须对这两种算法的核心加密过程展开分析。加密算法总是由基本操作组成的, 这些操作抵御能量攻击的能力差异较大, 与Twofish, Rijndael, Serpent 相比, MARS 和RC6 包含了较多比较脆弱的操作, 如异或、查表、轮移、算术运算( 加、减、乘) 等, 有些更适合用SPA 进行分析。MARS 和RC6 算法设计者采用白化技术的初衷就是为了增强对核心过程的保护。攻击者一旦采用DPA 技术解除了这种保护功能, 便能结合SPA, DPA 直接对核心部分展开分析, 破解其中的密钥。 

    (文/1. 北京理工大学电子工程系, 北京100081; 2. 华中科技大学计算机科学系, 湖北武汉430074; 3. 中国信息安全测评认证中心, 胡勇1 , 沈庭芝1 , 郭涛2 , 李守鹏3)