Page 223 - 《软件学报》2021年第9期

尚方舟 等:概率积分及其在 PUFFIN 算法中的应用 2847

2 42.17 次查表,10 轮实验的时间复杂度之和约为 2 42.65 次查表,这相当于 2 42.65 /(9×16)≈2 35.48 次 9 轮加密.另外,为存
16
20
20
12
4
8
储密钥,攻击需要对猜测的密钥字进行存储,存储复杂度为(2 +2 +2×2 +2×2 +4×2 )≈2 个存储单元.
Table 5 Correspondence between probability balance positions and guess key words (C=2)
表 5 概率平衡位置与猜测密钥字的对应关系(令 C=2)
(9)
序号 概率平衡位置 RK (8) RK 全平衡概率 组数 m 除正确密钥外候选密钥量
−3 8
20
1 20,21,22 5 4,10,11,14 83 8 9×2 ×(2 ) <1
8
−3 4
2 52,53,55 13 4,10,11,13 83 4 5×2 ×(2 ) <1
−2 8
12
3 14,15 3 0,4,11,12 92 8 4×2 ×(2 ) <1
16
−2 11
4 17,19 4 3,5,8,13 76 11 41×2 ×(2 ) <1
−2 8
12
5 33,34 8 1,4,9,14 84 8 9×2 ×(2 ) <1
6 38,39 9 8,10,11,14 93 3 3×2 ×(2 ) <1
4
−2 3
−2 6
8
7 40,41 10 5,9,13,15 77 6 10×2 ×(2 ) <1
−2 4
4
8 44,47 11 3,5,9,13 78 4 6×2 ×(2 ) <1
−1 6
4
9 2 0 0,3,12,14 93 6 3×2 ×(2 ) <1
4
−1 7
10 56 14 0,5,8,9 87 7 6×2 ×(2 ) <1
3 总结与展望
本文从传统的积分分析出发,考虑常数对多项式首项系数的影响,将“概率”这一思想运用到积分分析中,首
次提出了概率积分区分器的构造方法以及概率积分攻击模型.针对 PUFFIN 算法,构造了 7 轮概率积分区分器,
并由此对 9 轮 PUFFIN 算法进行攻击.该攻击可恢复 92 比特轮密钥,数据复杂度为 2 24.8 个选择明文,时间复杂度
20
为 2 35.48 次 9 轮加密,存储复杂度为 2 个存储单元.这是目前针对 PUFFIN 算法最好的实际积分分析结果.概率
积分分析方法的提出,完善了积分区分器的理论和实际应用,对于积分分析的进一步研究和改进,有学术价值和
重要意义.这一方法也可以应用于其他轻量级分组密码的分析中.
References:
[1] Sun B, Zhang P, Li C. Impossible differential and integral cryptanalysis of Zodiac. Ruan Jian Xue Bao/Journal of Software,
2011,22(8):1911−1917 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3875.htm [doi: 10.3724/SP.J.1001.
2011.03875]
[2] Daemen J, Knudsen L, Rijmen V. The block cipher square In: Proc. of the Int’l Workshop on Fast Software Encryption. 1997.
149−165. [doi: 10.1007/BFb0052343]
[3] Biryukov A, Shamir A. Structural cryptanalysis of SASAS. Journal of Cryptology, 2010,23(4):505−518. [doi: 10.1007/s00145-010-
9062-1]
[4] Lucks S. The saturation attack—A bait for Twofish. In: Proc. of the Revised Papers from the Int’l Workshop on Fast Software
Encryption. Springer-Verlag, 2001. 1−15. [doi: 10.1007/3-540-45473-X_1]
[5] Z’Aba MR, Raddum H, Henricksen M, et al. Bit-pattern based integral attack. In: Proc. of the Fast Software Encryption. 2008.
363−381. [doi: 10.1007/978-3-540-71039-4_23]
[6] Daemen J, Peeters M, Van Assche G, Rijmen V. Nessie proposal: NOEKEON. In: Proc. of the 1st Open NESSIE Workshop. 2000.
http://gro.noekeon.org/
[7] Anderson R, Biham E, Knudsen L. Serpent: A proposal for the advanced encryption standard. In: Proc. of the NIST AES Proposal.
1998. http://www.cl.cam.ac.uk/rja14/serpent.html [doi: 10.1007/3-540-69710-1_15]
[8] Bogdanov A, Knudsen LR, Leander G, et al. PRESENT: An ultra-lightweight block cipher. In: Proc. of the Int’l Workshop on
Cryptographic Hardware and Embedded Systems. Berlin, Heidelberg: Springer-Verlag, 2007. 450−466. [doi: 10.1007/978-3-540-
74735-2_31]
[9] Todo Y. Structural evaluation by generalized integral property. In: Proc. of the Advances in Cryptology (EUROCRYPT 2015).
Berlin Heidelberg: Springer-Verlag, 2015. 287−314. [doi: 10.1007/978-3-662-46800-5_12]
[10] Todo Y, Morii M. Bit-based division property and application to Simon family. In: Proc. of the Fast Software Encryption. Berlin
Heidelberg: Springer-Verlag, 2016. 357−377. [doi: 10.1007/978-3-662-52993-5_18]