<i>μ</i><sup>2</sup>算法的積分攻擊和不可能差分攻擊

胡斌; 張貴顯

doi:10.11999/JEIT210638

μ²算法的積分攻擊和不可能差分攻擊

doi: 10.11999/JEIT210638 cstr: 32379.14.JEIT210638

胡斌,
張貴顯^,

戰(zhàn)略支援部隊信息工程大學(xué) ??鄭州 ??450001

基金項目: 國家自然科學(xué)基金(61802438)

詳細信息

作者簡介:
胡斌：男，博士生導(dǎo)師，研究方向為密碼學(xué)與信息安全

張貴顯：男，碩士生，研究方向為對稱密碼的設(shè)計與分析

通訊作者:
張貴顯　zgxxgz111@126.com

中圖分類號: TN918.1
計量
- 文章訪問數(shù): 617
- HTML全文瀏覽量: 439
- PDF下載量: 92
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2021-06-28
- 修回日期: 2022-02-26
- 錄用日期: 2022-03-10
- 網(wǎng)絡(luò)出版日期: 2022-03-20
- 刊出日期: 2022-09-19

Integral Cryptanalysis and Impossible Differential Cryptanalysis of the μ² Algorithm

HU Bin,
ZHANG Guixian^,

The SSF Information Engineering University, Zhengzhou 450001, China

Funds: The National Natural Science Foundation of China (61802438)

摘要

摘要: $ {\mu }^{\text{2}} $算法是由Yeoh等人設(shè)計的一種輕量級分組密碼算法(doi: 10.1007/978-981-15-0058-9-27)，該算法全輪共15輪，采用TYPE-II廣義Feistel結(jié)構(gòu)，Yeoh等人在設(shè)計文檔中對$ {\mu ^{\text{2}}} $算法抵抗差分分析、線性分析的能力進行了評估，但$ {\mu ^{\text{2}}} $算法抵抗積分攻擊和不可能差分分析的能力目前尚不清楚。該文給出了$ {\mu ^{\text{2}}} $算法的8輪和9輪積分區(qū)分器和9輪不可能差分，利用8輪積分區(qū)分器，對9輪$ {\mu ^{\text{2}}} $算法進行了積分攻擊，攻擊的時間復(fù)雜度為${2^{76}}$次9輪加密，數(shù)據(jù)復(fù)雜度為${2^{48}}$，存儲復(fù)雜度為${2^{48}}$；利用9輪不可能差分，對11輪$ {\mu ^{\text{2}}} $算法進行了不可能差分分析，攻擊的時間復(fù)雜度為${2^{49}}$次11輪加密，數(shù)據(jù)復(fù)雜度為${2^{64}}$對明文。結(jié)果表明，9輪的$ {\mu ^{\text{2}}} $算法不能抵抗積分攻擊，11輪的$ {\mu ^{\text{2}}} $算法不能抵抗不可能差分分析。另外，該文對$ {\mu ^{\text{2}}} $算法抵抗差分攻擊的能力進一步評估并證明4輪$ {\mu ^{\text{2}}} $算法的差分特征的最大概率為${{\text{2}}^{{{ - 39}}}}$，與設(shè)計報告指出的4輪差分特征的概率不超過${2^{ - 3{\text{6}}}}$相比結(jié)果更為緊致。
- $ {\mu ^{\text{2}}} $算法 /
- 混合整數(shù)線性規(guī)劃 /
- 積分分析 /
- 不可能差分分析 /
- 差分分析
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.
- $ {\mu ^{\text{2}}} $ algorithm /
- Mixed Integral Linear Programming (MILP) /
- Integral attack /
- Impossible differential analysis /
- Differential analysis

HTML全文

圖 1 ${\mu ^{\text{2}}}$算法結(jié)構(gòu)圖

下載: 全尺寸圖片幻燈片

圖 2 S-P結(jié)構(gòu)圖

下載: 全尺寸圖片幻燈片

圖 3 F函數(shù)圖示

下載: 全尺寸圖片幻燈片

圖 4 ${\mu ^2}$算法的9輪不可能差分

下載: 全尺寸圖片幻燈片

圖 5 ${\mu ^2}$算法的11輪不可能差分攻擊

下載: 全尺寸圖片幻燈片

表 1 S盒

$x$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$S[x]$	C	5	6	B	9	0	A	D	3	E	F	8	4	7	1	2

下載: 導(dǎo)出CSV

表 2 積分區(qū)分器

輪數(shù)	區(qū)分器
8輪	輸入	cccccccccccccccc, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa
	輸出	????????????????, ????????????????, bbbbbbbbbbbbbbbb, ????????????????
	輸入	aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, cccccccccccccccc, aaaaaaaaaaaaaaaa
	輸出	bbbbbbbbbbbbbbbb, ????????????????, ????????????????, ????????????????
9輪	輸入	aaaaaaaaaaaaaaac, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa
	輸出	bbbbbbbbbbbbbbbb, ????????????????, ????????????????, ????????????????
	輸入	aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaac, aaaaaaaaaaaaaaaa
	輸出	????????????????, ????????????????, bbbbbbbbbbbbbbbb, ????????????????

下載: 導(dǎo)出CSV

表 3 4輪${\mu ^2}$算法最優(yōu)差分特征

輪數(shù)	輸入差分
第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

下載: 導(dǎo)出CSV

參考文獻(19)

[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. μ²: A lightweight block cipher[C]. The 6th Computational Science and Technology, Kota Kinabalu, Malaysia, 2019: 281–290.