分组密码属于对称密码算法,用同一密钥进行加密和解密运算。本质上,分组密码是一种有效的带密钥的置换,将固定长度的明文转换为相同长度的密文。分组密码广泛应用于各类密码算法,如加密算法和消息认证码（MAC）。消息认证码将密钥和任意长度的消息作为输入,输出一个固定长度的标签。消息认证码主要用于保证消息完整性和进行消息源认证。分组密码和消息认证码的安全性分析是密码学研究领域的热点问题。分组密码算法主要有两种构造方法:一种是Feistel网络结构,一种是代替-置换网络（SPN）结构。具有深远影响的早期的分组加密标准DES,就是基于Feistel网络结构设计的。DES的分组长度为64比特,密钥长度为56比特。随着计算机运算能力的提高,56比特的密钥长度已经不足以保证DES的安全性。1997年9月,美国国家标准与技术研究所（NIST）公开征集高级加密标准（AES）,以替代DES。2000年10月,比利时密码学家Daemen和Rijmen设计的Rijndael算法最终胜出。2001年11月,AES由NIST发布于FIPS PUB 197,现已成为对称密码中最流行的算法之一。AES基于SPN结构,分组长度为128比特,密钥长度可为128/192/256比特。其它分组密码算法的设计也受到了DES和AES设计原理的影响,例如,Shirai等在2007年快速软件加密大会（FSE’07）上提出的CLEFIA算法。CLEFIA分组密码算法基于广义Feistel网络结构,分支数为4,支持128比特的分组长度和128/192/256比特的密钥长度,相应圈数为18/22/26。圈函数采用SPN结构,由异或密钥、S盒变换和列混合操作组成。索尼公司希望将CLEFIA算法广泛应用到软硬件中,为音乐和图像等数字内容的发行加入版权保护和认证技术。分组密码的发展也影响了消息认证码的设计。CBC-MAC是一种常见的基于分组密码算法设计消息认证码的模式。近年来,出现了几种新的设计结构。这些新结构采用分组密码及缩减轮数的分组密码算法为主要组件,以达到更高的实现效率。其中,以基于AES和缩减的AES为代表。AES的设计者Daemen和Rijmen在FSE’05上提出A_LRED结构,并给出一个基于AES和1圈AES的实例A_LPHA-MAC。随后,他们对A_LPHA-MAC进行优化,以AES和缩减到4圈的AES为主要部件设计了P_ELICAN算法。Minematsu和Tsunoom在FSE’06上提出MT-MAC结构和PC-MAC结构,并分别给出基于AES和4圈AES的实例MT-MAC-AES和PC-MAC-AES。因为采用缩减轮数的AES,他们比基于AES设计的CBC-MAC更加有效。新的设计理念使算法运行效率有了较大提高。鉴于其广阔的应用前景,新的设计理念对算法安全性的影响值得我们深入探讨。在导师王小云教授的悉心指导下,我们对分组密码算法CLEFIA和消息认证码算法P_ELICAN)、MT-MAC-AES和PC-MAC-AES的安全性进行分析,并有如下结果。（1）缩减轮数的CLEFIA算法的饱和度分析索尼公司在CLEFIA的安全和性能评估报告（以下简称“评估报告”）中宣称,CLEFIA足以抵抗所有现已提出的攻击方法。对于饱和度分析（SaturationCryptanalysis）,评估报告中给出了两个8圈饱和特征,并用于分析约减到10圈的无白化密钥（Whitening Key）的CLEFIA算法。我们指出评估报告中的8圈区分器的错误,并给出新的8圈区分器。将白化密钥和子密钥等价为一个子密钥,并发现具有饱和特性的变量为32比特的方程可成功分割为4个变量为8比特的子方程,从而可利用分别征服策略,对每个子方程分别求解,减少需要猜测的密钥个数。而且,采用“部分和”技术进一步降低攻击的时间复杂度,将评估报告中对10圈CLEFIA的饱和度攻击扩展到11圈的CLEFIA-128/192/256、12圈的CLEFIA-192/256和13圈的CLEFIA-256,并将白化密钥考虑在内。该结果是目前对CLEFIA算法进行饱和度分析的最好结果。新发现的8圈区分器如下:其中,A_0（96）,A_1（96）和A_2（96）都是32比特字,且A_0（96）|A_1（96）|A_2（96）取遍所有长96比特的可能值。也就是说,若有2⁹⁶个不同的明文,其中每个明文的第三个32比特字是一个常数,则8轮后相应2⁹⁶个密文的第一个字的异或值为零。根据8圈区分器,满足（?）C₃^8,i=0(i=0,…,2⁹⁶)的子密钥集合S一定包含正确的子密钥,其中C₃^8,i为32比特的变量。选择足够多的明文集合,直到所有集合S的交集只有一个元素,即为正确的子密钥。结合CLEFIA算法的结构,方程（?）C₃^8,i=0可以按字节分割为四个子方程,从而可以利用分别征服攻击,分别对每个变量为8比特的子方程求解。而且,我们发现128比特的白化密钥和128比特的子密钥的异或值相当于一个128比特的子密钥。因此,可以大大降低求解一个方程需要猜测的子密钥的个数,进而降低攻击的复杂度。以约减到10圈的CLEFIA算法为例,第一个子方程如下:其中,Y₀可由密文直接获得。可见,只有40比特子密钥(RK’_17,0,RK₁₈)和该子方程相关,而文献却是64比特子密钥(RK₁₇,RK₁₈)。在具体求解过程中,通过采用部分和技术,可进一步降低攻击的时间复杂度。密钥猜测环节的时间复杂度为2^46.2次加密运算,而此前的结果为2¹²⁴次加密运算。通过穷举第11圈的64比特子密钥,我们将10圈的分析应用于11圈,复杂度为2^111.4次加密运算和2^99.8个选择明文。同理,可将该攻击应用于12圈的CLEFIA-192/256和13圈的CLEFIA-256。（2）缩减轮数的CLEFIA算法的不可能差分分析索尼公司在评估报告中给出了两个9圈不可能差分特征,并用于分析10圈的CLEFIA-128/192/256,11圈的CLEFIA-192/256和12圈的CLEFIA-256,其中,对12圈的分析也没有考虑白化密钥。我们的分析基于评估报告中的不可能差分特征,但是采用了新的路线扩展方式,减少需要猜测的子密钥个数。结合对CLEFIA算法轮函数的新发现,及白化密钥可与子密钥结合的特性,更加有效地过滤错误密钥,使攻击效率显著提高。在预计算处理方面,根据所需明文对的特殊差分形式,提炼代数特征,提出新的生日筛法,降低攻击的时间复杂度。对于CLEFIA-128/192/256,将评估报告中10圈的分析扩展到12圈,并且,对于13圈的CLEFIA-192/256和14圈的CLEFIA-256,该攻击同样适用。此外,指出并改正Tsunoo等对12圈CLEFIA的攻击中时间复杂度方面的问题。同时,分析表明,该算法中采用的白化密钥并不能增强抗不可能差分分析的强度。在不可能差分分析过程中,首先,要在不可能差分特征的两端分别添加适当的圈数,得到所需的输入输出差分。通过预计算,构造满足特殊输入差分的明文集合,并筛选出满足特殊输出差分的明文对。因为2ⁿ个明文一共可产生2^2n-1个明文对,所以需要更有效的算法来筛选明文对。发现输入输出差分之间的代数特征,利用生日攻击,提出生日筛法,将对2ⁿ个明文进行筛选的时间复杂度控制在2ⁿ次异或运算。例如,输入差分ΔP=（0,0,α,*）,而要筛选出的明文对满足输出差分ΔC=（*,*,0,α）,其中,α为固定的32比特非零值,*表示任意的32比特非零值。根据ΔP的第二、三字节和ΔC的三、四字节相等的特性,转换为筛选满足Δ（?）=（*,*,0,0）的明文对,其中,（?）=（P>>>32）（?）C,而这可以通过生日攻击来实现。然后,对每个筛选出的明文对,猜测相关的子密钥,进行加密或解密,使得加解密后的结果和不可能差分特征吻合的密钥为错误密钥,将其从子密钥空间删除。分析足够多的明文对,直到子密钥空间中只剩下一个元素,就是正确的子密钥。在过滤正确子密钥的过程中,我们发现利用以下性质,对32比特子密钥的求解可通过时间-存储平衡,在一次F运算内完成。·对F函数（F₀或F₁）,若已知两个32比特的输入（In,In’）及相应的输出差分ΔOut,则求解F函数的子密钥RK只需一次F-运算。而且,结合CLEFIA算法的特殊结构,推导出含有两个子密钥的线性表达式如下,从而将两个子密钥合为一个,减少猜测密钥的个数。·对缩减为r圈的CLEFIA分组密码算法,令(RK_2r-3,RK_2r-4)为第（r-1）圈的子密钥,(RK_2r-1,RK_2r-2)为第r圈的子密钥,（WK₂,WK₃）为最后一圈的白化密钥,C^r=（C₀^r,C₁^r,C₂^r,C₃^r）为密文,则子密钥RK_2r-3,RK_2r-4和白化密钥WK₂,WK₃有如下关系:其中,InS_F0^r-1和InS_F1^r-1分别表示第（r-1）圈的F₀^r-1和F₁^r-1中S盒的输入。利用上述特性,对11圈CLEFIA的攻击只需2^103.1次加密运算和2^103.1个选择明文,比设计者给出的2¹⁸⁸次加密运算和2^103.5个选择明文有较大改善。而且,结合一种特殊的选择明文方式,该攻击可以扩展到12圈的CLEFIA-128/192/256,复杂度为2^119.1次加密运算和2^119.1个选择明文。同理,可分析13圈的CLEFIA-192/256和14圈的CLEFIA-256。Tsunoo等也独立发现了类似的性质,并公布了新的9圈不可能差分路线,将不可能差分分析扩展到12圈的CLEFIA-128/192/256,13圈的CLEFIA-192/256和14圈的CLEFIA-256。然而,他们对12圈CLEFIA的分析忽略了预计算的时间复杂度,从而导致实际攻击的时间复杂度为2^125.8次加密运算,而不是文献中的2^118.9。我们指出,其预计算的时间复杂度可以用本论文中提出的生日筛法来降低,使得分析12圈CLEFIA的的时间复杂度仍为2^118.9次加密运算。目前,这些分析结果已被Tsujihara等改进。（3）基于四圈AES的消息认证码的不可能差分分析基于四圈AES的消息认证码P_ELICAN、MT-MAC-AES和PC-MAC-AES都属于迭代MAC算法。Preneel等指出,可利用生日攻击对这类算法进行存在性伪造,复杂度为（?）个消息和（?）次询问,其中,n为MAC值的长度。此外,在密钥或中间状态已知的情况下,可对P_ELICAN进行第二原像攻击。还存在一种侧信道碰撞攻击可以恢复P_ELICAN的中间状态,从而进行选择性伪造。最近,王小云教授等提出了利用生日攻击识别满足特殊差分的内部几乎碰撞的新技术。通过识别具有特殊差分的内部几乎碰撞,而非简单的碰撞,可以提炼出更多的信息。根据生日攻击,收集足够多的消息及其认证码(一般为2^n/2左右),可以保证具有特殊差分的内部几乎碰撞的存在性。然后,通过附加具有特殊差分形式的消息对,能以接近于1的概率将这个内部几乎碰撞识别出来。文献的一系列工作将这个识别内部几乎碰撞的新思想分别应用于CBC类MAC的第二原像攻击和A_LPHA-MAC的等价子密钥恢复攻击。结合上述工作,在王小云教授的建议下,我们首次将不可能差分分析用于MAC算法。对分组密码来说,不可能差分分析是一种有效的分析方法,可以分析7圈的AES-128（一共10圈）。但是,由于MAC算法的中间状态及其差分被最后的加密运算或复杂的带密钥的迭代过程所掩盖,鲜有用不可能差分分析MAC算法的文章。利用生日攻击,解决MAC算法中间状态的差分难识别的问题。由于P_ELICAN、MT-MAC-AES和PC-MAC-AES以AES和4圈AES为组件,可根据新发现的3圈AES不可能差分特征,恢复P_ELICAN的中间状态,复杂度为2^85.5个选择消息和2^85.5次询问。灵活选择消息的差分,可对P_ELICAN进行选择性伪造。该恢复中间状态的攻击可转换为对MT-MAC-AES的子密钥恢复攻击,复杂度保持不变。对PC-MAC-AES,一旦恢复了中间状态,可以分别恢复两个128比特的主密钥,复杂度为2^85.5个选择消息和2¹²⁸次询问。大致思路为:首先,构造两个各含2^n/2个消息的集合,保证每个消息对满足特殊差分。然后,利用生日攻击查找两个集合之间的碰撞。由于P_ELICAN、MT-MAC-AES和PC-MAC-AES的压缩函数是一个置换,外部碰撞意味着中间输出值的碰撞。而中间输出值是消息字和中间状态的异或值。因此,外部碰撞所对应的中间状态的差分即为相应消息字的差分。由于这些MAC算法以4圈AES为组件,一旦识别了内部状态的差分,利用一个3圈不可能差分特征,就可以恢复与消息进行异或运算的内部状态。新提出的3圈不可能差分特征如下:·3圈AES的不可能差分特征:对3圈AES,若输入对(z₂^I,z₂^I’),满足除位置（0,1, 5,8,12,13）（或（0,1,4,5,9,12）,或（0,4,5,8,9,13）,或（1,4,8,9,12,13））以外的字节都相等,则输出对(z₄^O,z₄^O’)的差分不可能只有一个非零字节。