Integral Cryptanalysis and Impossible Differential Cryptanalysis of the μ2 Algorithm
-
摘要:
$ {\mu }^{\text{2}} $ 算法是由Yeoh等人设计的一种轻量级分组密码算法(doi:10.1007/978-981-15-0058-9-27 )，该算法全轮共15轮，采用TYPE-II广义Feistel结构，Yeoh等人在设计文档中对$ {\mu ^{\text{2}}} $ 算法抵抗差分分析、线性分析的能力进行了评估，但$ {\mu ^{\text{2}}} $ 算法抵抗积分攻击和不可能差分分析的能力目前尚不清楚。该文给出了$ {\mu ^{\text{2}}} $ 算法的8轮和9轮积分区分器和9轮不可能差分，利用8轮积分区分器，对9轮$ {\mu ^{\text{2}}} $ 算法进行了积分攻击，攻击的时间复杂度为${2^{76}}$ 次9轮加密，数据复杂度为${2^{48}}$ ，存储复杂度为${2^{48}}$ ；利用9轮不可能差分，对11轮$ {\mu ^{\text{2}}} $ 算法进行了不可能差分分析，攻击的时间复杂度为${2^{49}}$ 次11轮加密，数据复杂度为${2^{64}}$ 对明文。结果表明，9轮的$ {\mu ^{\text{2}}} $ 算法不能抵抗积分攻击，11轮的$ {\mu ^{\text{2}}} $ 算法不能抵抗不可能差分分析。另外，该文对$ {\mu ^{\text{2}}} $ 算法抵抗差分攻击的能力进一步评估并证明4轮$ {\mu ^{\text{2}}} $ 算法的差分特征的最大概率为${{\text{2}}^{{{ - 39}}}}$ ，与设计报告指出的4轮差分特征的概率不超过${2^{ - 3{\text{6}}}}$ 相比结果更为紧致。-
关键词:
- $ {\mu ^{\text{2}}} $算法 /
- 混合整数线性规划 /
- 积分分析 /
- 不可能差分分析 /
- 差分分析
Abstract:$ {\mu ^{\text{2}}} $ is a lightweight block cipher designed by Yeoh et al (doi:10.1007/978-981-15-0058-9-27 ). The cipher has 15 rounds in total and adopts TYPE-II generalized feistel network. The ability of the$ {\mu ^{\text{2}}} $ algorithm to resist differential analysis and linear analysis is evaluated by Yeoh et al. in the design document, but the ability of$ {\mu ^{\text{2}}} $ algorithm to resist integral attack and impossible differential attack is not clear. In this paper, 8/9-round integral distinguishers and 9-round impossible difference are given. Using 8-round integral distinguishers, 9-round$ {\mu ^{\text{2}}} $ is attacked and the time complexity of the attack is${2^{76}}$ 9-round encryptions, the data complexity is${2^{48}}$ , and the memory complexity is${2^{48}}$ . Using 9-round impossible difference, 11-round$ {\mu ^{\text{2}}} $ is attacked and the time complexity of the attack is${2^{49}}$ 11-round encryptions, the data complexity is${2^{64}}$ pairs of plaintexts. The results show that the 9-round$ {\mu ^{\text{2}}} $ algorithm can not resist integral attack, and the 11-round$ {\mu ^{\text{2}}} $ algorithm can not resist impossible differential analysis. In addition, the ability of$ {\mu ^{\text{2}}} $ algorithm to resist differential attack is reevaluated, and the maximum probability of differential characteristic of 4-round$ {\mu ^{\text{2}}} $ algorithm is${{\text{2}}^{{{ - 39}}}}$ , which is more compact than the probability${2^{ - 3{\text{6}}}}$ of 4-round differential characteristic pointed out in the design report. -
表 2 积分区分器
轮数 区分器 8轮 输入 cccccccccccccccc, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa 输出 ????????????????, ????????????????, bbbbbbbbbbbbbbbb, ???????????????? 输入 aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, cccccccccccccccc, aaaaaaaaaaaaaaaa 输出 bbbbbbbbbbbbbbbb, ????????????????, ????????????????, ???????????????? 9轮 输入 aaaaaaaaaaaaaaac, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa 输出 bbbbbbbbbbbbbbbb, ????????????????, ????????????????, ???????????????? 输入 aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaac, aaaaaaaaaaaaaaaa 输出 ????????????????, ????????????????, bbbbbbbbbbbbbbbb, ???????????????? 
下载: 导出CSV
表 3 4轮
${\mu ^2}$ 算法最优差分特征轮数 输入差分 第1轮输入 0000000000000000 0000000010110111 1010010100000010 0010000100000101 第2轮输入 0000000010110111 1010010100000000 0000000000000000 0000000000000000 第3轮输入 0000000000000000 0000000000000000 0000000000000000 0000000010110111 第4轮输入 0000000000000000 0000000000000000 0000000010110111 0000000000000000 第4轮输出 0000000000000000 0000000000000000 0000000010110111 1000010100000001
下载: 导出CSV
-
[1] KNUDSEN L and WAGNER D. Integral cryptanalysis: Extended abstract[C]. The 9th International Workshop on Fast Software Encryption, Leuven, Belgium, 2002: 112–127. [2] TODO Y. Structural evaluation by generalized integral property[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 287–314. [3] TODO Y. Integral cryptanalysis on full MISTY1[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 413–432. [4] TODO Y and MORII M. Bit-based division property and application to Simon family[C]. The 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 357–377. [5] XIANG Zejun, ZHANG Wentao, BAO Zhenzhen, et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 648–678. [6] HU Kai and WANG Meiqin. Automatic search for a variant of division property using three subsets[C]. Cryptographers’ Track at the RSA Conference, San Francisco, USA, 2019: 412–432. [7] WANG Senpeng, HU Bin, GUAN Jie, et al. MILP-aided method of searching division property using three subsets and applications[C]. The 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 2019: 398–427. [8] HU Kai, SUN Siwei, WANG Meiqin, et al. An algebraic formulation of the division property: Revisiting degree evaluations, cube attacks, and key-independent sums[C]. The 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 2020: 446–476. [9] BIHAM E and SHAMIR A. Differential Cryptanalysis of the Data Encryption Standard[M]. New York: Springer, 1993: 11–32. [10] MOUHA N, WANG Qingju, GU Dawu, et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]. The 7th International Conference on Information Security and Cryptology, Beijing, China, 2012: 57–76. doi: /10.1007/978-3-642-34704-7_5. [11] WU Shengbao and WANG Mingsheng. Security evaluation against differential cryptanalysis for block cipher structures[EB/OL]. https://eprint.iacr.org/2011/551.pdf, 2011. [12] SUN Siwei, HU Lei, WANG Peng, et al. Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, China, 2014: 158–178. [13] SUN Siwei, HU Lei, WANG Meiqin, et al. Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties[EB/OL]. https://eprint.iacr.org/2014/747.pdf, 2014. [14] SASAKI Y and TODO Y. New algorithm for modeling s-box in MILP based differential and division trail search[C]. The 10th International Conference for Information Technology and Communications, Bucharest, Romania, 2017: 150–165. [15] ZHOU Chunning, ZHANG Wentao, DING Tianyou, et al. Improving the MILP-based security evaluation algorithm against differential/linear cryptanalysis using a divide-and-conquer approach[EB/OL]. https://eprint.iacr.org/2019/019.pdf, 2019. [16] BOURA C and COGGIA D. Efficient MILP modelings for sboxes and linear layers of SPN ciphers[J]. IACR Transactions on Symmetric Cryptology, 2020, 2020(3): 327–361. doi: 10.13154/tosc.v2020.i3.327-361 [17] BIHAM E, BIRYUKOV A, and SHAMIR A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[J]. Journal of Cryptology, 2005, 18(4): 291–311. doi: 10.1007/s00145-005-0129-3 [18] KNUDSEN L R. DEAL-A 128-bit block cipher[EB/OL]. https://www.researchgate.net/publication/2452654_DEAL_-_A_128-bit_Block_Cipher, 2014. [19] YEOH W Z, TEH J S, and SAZALI M I S B M. µ2: A lightweight block cipher[C]. The 6th Computational Science and Technology, Kota Kinabalu, Malaysia, 2019: 281–290. -
图(5) / 表(3)
计量
- 文章访问数: 558
- HTML全文浏览量: 350
- PDF下载量: 83
- 被引次数: 0
下载:
