AES算法的积分分析

AES算法的积分分析积分攻击 (Integral Attack)积分攻击是一种针对分组密码的密码分析技术通常用来恢复密码算法的部分密钥。它由Lars Knudsen于1997年提出主要用于分析Square密码因此有时也称为Square攻击后来被应用于Rijndael(AES)等其他密码算法。积分攻击是一种选择明文攻击方法,它是继差分密码分析和线性密码分析后,密码学界公认的最有效的密码分析方法之一。这种攻击方法更多地与算法的结构有关,而与算法部件的具体取值关系不大,适用于每一个模块均为双射的分组密码。这一攻击方法对大多以字节为变换单位的减轮密码是有效的。该方法被提出后,已经成功对AES、Camellia和FOX等著名密码进行了不同程度的攻击。基本概念积分攻击的核心思想是选择一组明文这些明文在某些比特位置上是固定的在其他比特位置上遍历所有可能值。通过追踪这些明文通过密码算法加密后密文的某些比特的异或和积分。利用积分性质如平衡性来恢复密钥信息。攻击步骤选择明文集选择2^d个明文其中d个比特位置取所有可能值其余位置固定。加密过程获取这些明文的密文。积分计算计算密文某些比特的异或和。密钥恢复利用积分性质推断轮密钥的部分信息。积分分析中涉及到的3个字节集1活跃字节集(A)在相同位置的字节Ai取遍(0…255)这256个不同值且取每个不同值的次数相同其中i(0…255)。2平衡字节集(B)在相同位置的字节Bi满足异或和等于0即B0⊕…⊕B2550。3常量字节集(C)在相同位置的256个字节Ci取值保持不变的字节即B0…B255C。Ⅴ结构考虑AES算法的一个结构ⅤⅤ有256个状态每个状态对应于AES算法状态矩阵的16个字节如果其中Ⅴ[j](Ⅴ的第j个状态)的第1个字节为活跃字节集A其余的15个字节为常量字节C那么经过3轮加密后输出的状态中的16个字节全部为平衡字节B。3轮AES算法积分区分器的推导(如上图所示)1第一轮第1轮的输入状态的第1个字节为活跃字节A经过SubByte变换后仍为活跃字节A又经过ShiftRow变换后积分性质不变经过MixColumn变换后状态第1列4个字节都变为活跃字节A经过AddKey变换后积分性质不变不变。2第二轮第2轮的输入状态的第1列的4个字节都为活跃字节A经过SubByte变换后仍为活跃字节A又经过ShiftRow变换后活跃字节的位置发生变化经过MixColumn变换后状态矩阵中的所有16字节全部变为活跃字节集A经过AddKey变换后积分性质不变。3第三轮第3轮的输入状态的16字节状态全部为活跃字节A经过SubByte变换后积分性质不变又经过ShiftRow变换后活跃字节的位置发生变化经过MixColumn变换后16字节状态全变为平衡字节B经过AddKey变换后差分性质不变。记第三轮加密变换的行移位之后的状态矩阵为Xx0||…||x15那么第三轮加密变换的列混合之后的状态矩阵为Yy0||…||y15。则Y可以表示成关于X的表达式我们对y0进行求异或和则得所以y0为平衡字节B同理可证其它的15个字节也都是平衡字节B。不过在第四轮加密中的SubByte变换会破坏这一性质故AES算法的积分区分器最长为3轮。以上我们证明了在输入的明文数据只有1个活跃字节其它字节全部为常量的情况下AES算法三轮加密后的状态矩阵的全部16个字节都为平衡字节即异或和为0。因为在随机的情况下加密过程中间状态的异或和为字节(有0到255等256种取值)每种取值的概率都是一样的所以三轮的积分区分器可以将AES算法与随机置换相互区分而且我们可以以此区分器来恢复约减为4轮的AES算法的轮密钥。密钥恢复1选择一个Ⅴ结构使得Ⅴ[j](Ⅴ的第j个状态)的第1个字节为活跃字节集A其余的15个字节为常量字节C对此Ⅴ结构加密4轮(我们假设AES算法只有4轮且最后一轮没有列混合变换)密文记为C。我们记第4轮的轮密钥为RK4(128比特)则RK4[i]表示第i个密钥字节。2记第4轮的输入状态为P3则经过SubByte变换后的状态记为Q3SubByte(P3), 经过ShiftRow变换后的状态记为R3ShiftRow (Q3)经过AddKey变换后的状态记为CAddKey (R3)。我们记gkRK4[0]我们猜测gk的值对C进行部分解密。容易证明P3[0] SubByte-1(C[0]⊕gk)SBOX-1(C[0]⊕gk)如上图所示C[0]U0。因为P3[0]为平衡字节故其异或和等于0如果我们猜测的gk值满足此条件则gk可能为正确的密钥如果猜测的gk值不满足此条件则说明此gk为错误的密钥可以排除。3如果步骤2中剩下的密钥值不唯一则可以重新选择Ⅴ结构和设置不同的初始值反复测试即重复步骤1和步骤2直至gk值唯一此唯一值即为正确的密钥值。总的来说积分分析通过加密算法结构中的固有的弱点来恢复部分密钥其属于是选择明文攻击。积分分析与差分分析有些类似在攻击方式上差分攻击Differential Attack主要是分析明文对的差分传播积分攻击Integral Attack主要是分析明密文的积分性质在数据需求方面差分攻击需要大量随机明文对积分攻击需要特定结构的选择明文在适用场景方面差分攻击几乎适用于所有的对称加密算法积分攻击主要用于分析基于SPN结构和轮函数为双射的分组加密算法。