【作者】 王薇；

【导师】 王小云；

【作者基本信息】 山东大学 ， 信息安全， 2009， 博士

【摘要】 分组密码属于对称密码算法,用同一密钥进行加密和解密运算。本质上,分组密码是一种有效的带密钥的置换,将固定长度的明文转换为相同长度的密文。分组密码广泛应用于各类密码算法,如加密算法和消息认证码（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’)的差分不可能只有一个非零字节。更多还原

【Abstract】 Block ciphers belong to symmetric ciphers, which use the same key for both encryption and decryption. A block cipher is an efficient, keyed permutation that transforms a fixed-length block of plaintext into a block of ciphertext of the same length. Block ciphers can be used in many cryptographic primitives, such as encryption and message authentication code （MAC）. A MAC function takes as input a secret key and a message of arbitrary length, and produces as output a short tag. MAC is used to ensure integrity and authenticity of messages. The security evaluation of block ciphers and MAC functions has been hot topics of cryptographic research during the past decade.There are two main approaches to construct block ciphers, one is Feistel Network, and another is Substitution-Permutation Network （SPN）. An early and highly influential block cipher, the Data Encryption Standard （DES）, is based on the Feistel Network, which has a block size of 64-bit and key size of 56-bit. As the rapid development of computer technology, the inadequacy in the key length became apparent. In September 1997, National Institute of Standards and Technology （NIST） announced request for candidate algorithms for the Advanced Encryption Standard （AES）,a successor to DES. In October 2000, Rijndael, which is designed by Daemen and Rijnmen, was selected as the proposed AES, and was approved as FIPS PUB 197 in November 2001. AES is a SPN, with a block size of 128-bit and key size of 128/192/256-bit, which has been one of the most popular block ciphers.Many other block ciphers are influenced by the design rationale of the above two, such as CLEFIA, which was proposed by Shirai et al. at FSE 2007. CLEFIA is a 4-branch generalized Feistel Network, and supports 128-bit input and 128/192/256-bit key for 18/22/26-round, respectively. Each round contains two SP-type F-functions, composed of AddRoundKey, SubByte and MixColumn operations. Sony claimed that CLEFIA will be used across various applications and products.The development of block ciphers influences the design of MAC algorithms. Beside the CBC-MAC, which is a well-known mode for block ciphers to provide MACs, several new MAC constructions have been proposed. They take a block cipher and a reduced version of the block cipher as main components, in order to gain higher performance. The AES and reduced AES are taken as representative. Daemen and Ri-jmen, the designer of AES, proposed the A_LRED construction at FSE’05, and presented an instance based on AES and 1-round AES, which is named A_LPHA-MAC. Later, they published an optimized version of A_LPHA-MAC, the P_ELICAN algorithm, which is composed of AES and 4-round AES. Minematsu and Tsunoom introduced the MT-MAC construction and PC-MAC construction at FSE’06, including two examples MT-MAC-AES and PC-MAC-AES, which are also based on AES and 4-round AES. Since they take reduced AES, all of them are efficient than CBC-MAC instantiated with AES.New design techniques improve the performance of algorithms, while their impact on the security needs further investigation. Under the instructions of my supervisor, Xiaoyun Wang, we present cryptanalysis of block cipher CLEFIA and MAC functions P_ELICAN, MT-MAC-AES and PC-MAC-AES as follows.（1） Saturation cryptanalysis of reduced CLEFIASony Corporation published the security and performance evaluations of CLEFIA, which claimed that CLEFIA achieves sufficient immunity against known cryptanalytic attacks. For saturation cryptanalysis, they presented two 8-round saturation characteristics, and applied them to attack the CLEFIA reduced to 10-round without key whitenings.We point out that the 8-round distinguishes proposed by the designers are wrong, and present a right one. We observe that the whitening key can be combined with the round subkey, and the equation with 32-bit variable can be subdivided into 4 byte-wise equations, thus the number of guessed subkeys can be reduced by a divide-and-conquer strategy. Moreover, the partial sum technique is adopted to reduce the time complexity. As a result, the 10-round saturation cryptanalysis is extended to 11-round CLEFIA-128/192/256,12-round CLEFIA-192/256 and 13-round CLEFIA-256, taking the whitening keys into consideration. Till now, it’s the best result in the saturation cryptanalysis of CLEFIA.The new 8-round saturation distinguisher we identify is:where A_0（96）,A_1（96） and A_2（96） are 32-bit words, and A_0（96）|A_1（96）|A_2（96） stands for all states of 96-bit values. The distinguisher means that for 2⁹⁶ different inputs where the third 32-bit word is a constant, the XOR value of the 2⁹⁶ 8-round outputs is zero at the first word.According to the 8-round distinguisher, the correct subkey candidates are suggested by the equation （?）C₃^8,i=0, where i=0,…,2⁹⁶. Choose other sets of plaintexts enough, and get such an equation respectively, only the right subkey value satisfies all equations.Combining with the structure of CLEFIA, we find that a divide-and-conquer strat-egy can be used to guess solutions for the equation （?）C₃^8,i=0, which is equivalent to four byte-wise equations. Moreover, we observe that the XOR of 128-bit whitening key and 128-bit subkey can be considered as a 128-bit equivalent subkey. Therefore, the number of related subkeys which are needed to do a partial decryption is reduced greatly. Taking the attack on 10-round version for example, the first byte-wise equation can be written aswhere Y₀ can be derived from the ciphertexts directly. To do a partial decryption, only 40-bit subkey (RK’_17,0,RK₁₈) is needed to guess instead of 64-bit subkey (RK₁₇,RK₁₈) claimed in. The partial sum technique is adopted to reduce the time complexity of our attack.The time complexity of the guessing step is about 2^46.2 encryptions, while the previous result is about 2¹²⁴ encryptions. Thus we can directly extend the 10-round attack to 11-round by guessing the 64-bit subkeys involved in the 11-th round. The complexity is 2^111.4 encryptions and 2^99.8 chosen plaintexts. The attacks on 12-round CLEFIA-192/256 and 13-round CLEFIA-256 can be proceeded in a similar way.（2） Impossible differential cryptanalysis of reduced CLEFIAFor impossible differential cryptanalysis, Sony corporation proposed two 9-round impossible differentials, and analyzed 10-round CLEFIA-128/192/256, 11-round CLEFIA-192/256 and 12-round CLEFIA-256, where they did not consider key whitenings in 12-round attack.We utilize the same impossible differentials, but adopt different extension way. Exploring more technique details, the wrong subkeys can be filtered out more efficiently. Based on the specific difference of plaintexts pairs, we propose the birthday sieve method to reduce the time complexity of precomputation greatly. For CLEFIA-128/192/256, we extend the attack from 10-round to 12-round. For 13-round CLEFIA-192/256 and 14-round CLEFIA-256, our attack still works. We correct the error in the complexity evaluation of 12-round attack in. Meanwhile, it is clear that the whitening keys have no influence on the resistance against impossible differential cryptanalysis.To perform the impossible differential cryptanalysis, we prepend and append more rounds on the top and end of the impossible differential first, and obtain the wanted input/output difference. Construct plaintexts structures where each two plaintexts satisfy the input difference, and sieve the plaintexts pairs with the required output differences by precomputation. Since there are 2^2n-1 plaintexts pairs from 2ⁿ plaintexts, we need to explore a more efficient algorithm to sieve required pairs. We observe the relation between the difference of input and output, and propose a birthday sieve method based on the birthday attack, which reduces the time complexity of sieving pairs to 2ⁿ XOR operations. Suppose the input differenceΔP=（0,0,α,*） and the wanted output dif-ferenceΔC=（*,*,0,α）, whereαis a fixed 32-bit value, and * denotes arbitrary 32-bit nonzero value. Since the second and third bytes ofΔP equal to the third and fourth bytes ofΔC respectively,ΔC=（*,*,0,α） is equivalent toΔ（?）=（*,*,0,0）, where （?）=（P>>>32）（?）C. And the pairs satisfyingΔ（?）=（*,*,0,0） can be obtained by birthday attack.Then, for each sieved pair, discard the wrong subkeys which cause the partial encryption and decryption to match the impossible differential. Only the correct subkey is left in the subkey space after enough pairs are analyzed. In the sieve process, the following property can be used to deduce one 32-bit subkey in one F-computation by time-memory tradeoff.·For the F-function F （F₀orF₁）, let （In,In’） be two 32-bit inputs, andΔOut be the difference of the corresponding outputs, the 32-bit round subkey RK involved in F can be deduced with about one F-computation.Moreover, from the specific structure of CLEFIA, we deduce a linear relation between the whitening key and round subkey, and take the two subkeys as one, which reduce the number of related subkeys.·For r-round CLEFIA, let (RK_2r-3,RK_2r-4) be the subkey in the （r-1）-th round, (RK_2r-1,RK_2r-2) be the subkey in the r-th round, （WK₂, WK₃） be the whiten-ing key in the final round, and C^r=（C₀^r,C₁^r,C₂^r,C₃^r） be the ciphertext, we have the following two equations which reveal the correlations among subkeys WK₂, WK₃,RK_2r-3, and RK_2r-4:Here InS_F0^r-1 and InS_F1^r-1 are the inputs to the four S-boxes of F₀^r-1 and F₁^r-1 inthe （r-1）-th round, respectively.By these observations, our attack on 11-round CLEFIA only takes 2^103.1 encryp-tions and 2^103.1 chosen plaintexts, instead of the original 2¹⁸⁸ encryptions and 2^103.5 chosen plaintexts. Moreover, combining with a special way to choose plaintexts pairs, our attack can be applied to 12-round CLEFIA-128/192/256 with 2^119.1 time complexity and 2^119.1 data complexity.Independently, similar observations are presented by Tsunoo et al. They presented some new 9-round impossible differentials, which were applied to attack 12-round CLEFIA-128/192/256, 13-round CLEFIA-192/256 and 14-round CLEFIA-256. However, in the attack on 12-round CLEFIA, they neglected the time complexity of the precomputation. Thus the time complexity is 2^125.8 encryptions actually, which is higher than the claimed 2^118.9. Using the birthday sieve method described in this dissertation, we correct this mistake and keep the previous complexity. At present, these results had been improved by Tsujihara et al.（3） Impossible differential cryptanalysis of MACs based on 4-round AESP_ELICAN, MT-MAC-AES and PC-MAC-AES belong to iterative MAC algorithms. Based on birthday attack, Preneel et al. presented a general forgery attack on all iterative MACs with （?） messages and （?） queries, where n is the length of MAC value. Furthermore, for P_ELICAN, suppose a key or an internal state is known, the second preim-age can be found. In addition, a side-channel collision attack can recover its internal state, which mounts a selective forgery attack.Recently, Wang et al. explored new ideas based on the birthday attack to detect the inner near-collision with specific difference rather than collision, from which more information can be derived. According to birthday paradox, the existence of the inner near-collision with specific difference can be guaranteed by collection of 2^n/2 （message, MAC） pairs. Then such a collision is detected with probability close to 1 by appending message pairs with specific form. The series works extended these ideas to the second preimage attack on CBC-like MACs and an equivalent subkey recovery attack on A_lpha-MAC, respectively.Enlightened by the above techniques, Xiaoyun Wang suggests us to adopt the impossible differential cryptanalysis on MACs, which brings new idea to the cryptanalysis of MACs. Impossible differential cryptanalysis is a powerful attack on AES, which can be applied to 7-round AES-128 （10 rounds in total） . However, little has been done for impossible differential cryptanalysis on MACs, due to the fact that the internal state values as well as their difference, are concealed by the final encryption or complex keyed iterations. We identify the difference of the internal states by birthday attack. Since the main components of P_ELICAN, MT-MAC-AES and PC-MAC-AES are AES and 4-round AES, we can recover the internal state of P_ELICAN with 2^85.5 chosen messages and 2^85.5 queries with a new 3-round impossible differential of AES. Then the selective forgery attack can be processed. This internal state recovery attack directly turns to be a subkey recovery attack on MT-MAC-AES with the same complexities. For PC-MAC-AES, we are able to recover its two 128-bit secret keys separately, once the internal state is identified with 2^85.5 chosen messages and 2¹²⁸ queries.The main idea is as follows: First, construct two structures to produce messagepairs with specific difference. Each structure has 2^n/2 messages. Second, utilize thebirthday attack to search collisions between the two structures. Since the compressionfunction is a permutation, output collision means inner collision. And the inner valueis the XOR of message word and internal state. Thus, the difference of the internalstates can be detected from the difference of message words. Third, once the differenceof the internal states is verified, we can recover the internal state XORed with themessage using a 3-round impossible differential property since 4-round AES is takenas a building block. The 3-round impossible differential characteristic is as follows:·For 3-round AES, given an input pair (z₂^I,z₂^I’) whose components equal in allexcept six bytes indexed by （0,1,5,8,12,13） （or （0,1,4,5,9,12）, or （0,4,5,8,9,13）, or （1,4,8,9,12,13））, the difference of the output pair (z₄^O,z₄^O’) can not haveexactly one nonzero byte.更多还原