改進(jìn)的Type-1型廣義Feistel結(jié)構(gòu)的量子攻擊及其在分組密碼CAST-256上的應(yīng)用

倪博煜; 董曉陽

doi:10.11999/JEIT190633

改進(jìn)的Type-1型廣義Feistel結(jié)構(gòu)的量子攻擊及其在分組密碼CAST-256上的應(yīng)用

doi: 10.11999/JEIT190633 cstr: 32379.14.JEIT190633

倪博煜^{1, 2},
董曉陽^3, ,

1.
山東大學(xué)密碼技術(shù)與信息安全教育部重點實驗室濟(jì)南 250100
2.
山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院青島 266237
3.
清華大學(xué)高等研究院北京 100084

基金項目: 國家重點研發(fā)計劃(2017YFA0303903)，國家自然科學(xué)基金(61902207)，國家密碼發(fā)展基金(MMJJ20180101, MMJJ20170121)

詳細(xì)信息

作者簡介:
董曉陽：男，1988年生，助理研究員。研究方向為對稱密碼算法的安全性分析與設(shè)計

通訊作者:
董曉陽　xiaoyangdong@tsinghua.edu.cn

中圖分類號: TN918; TP309
計量
- 文章訪問數(shù): 3535
- HTML全文瀏覽量: 1083
- PDF下載量: 152
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-08-26
- 修回日期: 2019-11-26
- 網(wǎng)絡(luò)出版日期: 2019-11-29
- 刊出日期: 2020-02-19

Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256

Boyu NI^{1, 2},
Xiaoyang DONG^{3
, ,}

1.
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan 250100, China
2.
School of Cyber Science and Technology, Shandong University, Qingdao 266237, China
3.
Institute for Advanced Study, Tsinghua University, Beijing 100084, China

Funds: The National Key Research and Development Program of China (2017YFA0303903), The National Natural Science Foundation of China (61902207), The National Cryptography Development Fund (MMJJ20180101, MMJJ20170121)

摘要

摘要: 廣義Feistel結(jié)構(gòu)(GFS)是設(shè)計對稱密碼算法的重要基礎(chǔ)結(jié)構(gòu)之一，其在經(jīng)典計算環(huán)境中受到了廣泛的研究。但是，量子計算環(huán)境下對GFS的安全性評估還相當(dāng)稀少。該文在量子選擇明文攻擊(qCPA)條件下和量子選擇密文攻擊(qCCA)條件下，分別對Type-1 GFS進(jìn)行研究，給出了改進(jìn)的多項式時間量子區(qū)分器。在qCPA條件下，給出了3d – 3輪的多項式時間量子區(qū)分攻擊，其中$d(d \ge 3)$是Type-1 GFS的分支數(shù)，攻擊輪數(shù)較之前最優(yōu)結(jié)果增加$d - 2$輪。得到更好的量子密鑰恢復(fù)攻擊，即相同輪數(shù)下攻擊的時間復(fù)雜度降低了${2^{(d - 2)n/2}}$。在qCCA條件下，對于Type-1 GFS給出了$3d - 2$輪的多項式時間量子區(qū)分攻擊，比之前最優(yōu)結(jié)果增加了$d - 1$輪。該文將上述區(qū)分攻擊應(yīng)用到CAST-256分組密碼中，得到了12輪qCPA多項式時間量子區(qū)分器，以及13輪qCCA多項式時間量子區(qū)分器，該文給出19輪CAST-256的量子密鑰恢復(fù)攻擊。
- 分組密碼 /
- 廣義Feistel結(jié)構(gòu) /
- 量子攻擊 /
- CAST-256加密算法
Abstract: Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty. In this paper, more improved polynomial-time quantum distinguishers are presented on Type-1 GFS in quantum Chosen-Plaintext Attack (qCPA) setting and quantum Chosen-Ciphertext Attack (qCCA) setting. In qCPA setting, new quantum polynomial-time distinguishers are proposed on $3d - 3$ round Type-1 GFS with branches $d \ge 3$, which gain $d - 2$ more rounds than the previous distinguishers. Hence, key- recovery attacks can be obtained, whose time complexities gain a factor of ${2^{\frac{{\left( {d - 2} \right)n}}{2}}}$. In qCCA setting, $3d - 3$ round quantum distinguishers can be obtained on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers. In addition, given some quantum attacks on CAST-256 block cipher. 12-round and 13-round polynomial-time quantum distinguishers are obtained in qCPA and qCCA settings, respectively. Hence, the quantum key-recovery attack on 19-round CAST-256 is derived.
- Block cipher /
- Generalized Feistel Scheme (GFS) /
- Quantum attack /
- CAST-256 cipher algorithm

HTML全文

圖 1 3輪的量子區(qū)分器

下載: 全尺寸圖片幻燈片

圖 2 FX結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 3 Ito等人在Feistel上的4輪量子區(qū)分器

下載: 全尺寸圖片幻燈片

圖 4 $d$分支Type-1 GFS的第$i$輪

下載: 全尺寸圖片幻燈片

圖 5 4分支Type-1 GFS的選擇明文量子區(qū)分器

下載: 全尺寸圖片幻燈片

圖 6 4分支Type-1 GFS的16輪密鑰恢復(fù)攻擊

下載: 全尺寸圖片幻燈片

圖 7 4分支CAST256-like GFS的10輪區(qū)分器

下載: 全尺寸圖片幻燈片

圖 8 CAST-256的12輪區(qū)分器

下載: 全尺寸圖片幻燈片

圖 9 CAST-256的14輪攻擊

下載: 全尺寸圖片幻燈片

圖 10 CAST-256的13輪區(qū)分器

下載: 全尺寸圖片幻燈片

表 1 Type-1 GFS的量子區(qū)分器的輪數(shù)

來源	攻擊條件	$r$	$d = 3$	$d = 4$	$d = 5$	$d = 6$	$d = 7$
文獻(xiàn)[35]	qCPA	2d–1	5	7	9	11	13
4.1節(jié)	qCPA	3d–3	6	9	12	15	18
4.2節(jié)	qCCA	3d–2	7	10	13	16	19

下載: 導(dǎo)出CSV

表 2 在量子環(huán)境下對Type-1 GFS的密鑰恢復(fù)攻擊

來源	區(qū)分器輪數(shù)	密鑰恢復(fù)輪數(shù)	復(fù)雜度(log)	窮搜復(fù)雜度(log)
文獻(xiàn)[35]	$2d - 1$	$r \ge {d^2}$	$T + ({{r - {d^2} + d - 2)n} / 2}$	${{rn} / 2}$
4.1節(jié)	$3d - 3$	$r \ge {d^2}$	$T + ({{r - {d^2})n} / 2}$	${{rn} / 2}$

下載: 導(dǎo)出CSV

表 3 CAST-256的量子攻擊

來源	攻擊條件	區(qū)分器輪數(shù)	密鑰恢復(fù)攻擊輪數(shù)
來源	攻擊條件	區(qū)分器輪數(shù)	$r = 14$	$r = 15$	$r = 16$	$r = 17$	$r = 18$	$r = 19$
文獻(xiàn)[35]	qCPA	7	${2^{74}}$	${2^{92.5}}$	${2^{111}}$	$ - $	$ - $	$ - $
5.1節(jié)	qCPA	12	${2^{37}}$	${2^{55.5}}$	${2^{74}}$	${2^{92.5}}$	${2^{111}}$	$ - $
5.2節(jié)	qCCA	13	${2^{18.5}}$	${2^{37}}$	${2^{55.5}}$	${2^{74}}$	${2^{92.5}}$	${2^{111}}$

下載: 導(dǎo)出CSV

表 4 針對CAST-256的經(jīng)典攻擊和量子攻擊的比較

來源	密鑰長度	攻擊	輪數(shù)	數(shù)據(jù)	時間
文獻(xiàn)[39]	128	飛去來器	16	${2^{49.3}}$	$ - $
5.2節(jié)	128	qCCA	16	–	$ {2^{55.5}} $
文獻(xiàn)[40]	192	線性攻擊	24	${2^{124.1}}$	$ {2^{156.52}} $
5.2節(jié)	192	qCCA	17	–	$ {2^{74}}$
文獻(xiàn)[41]	256	多維零相關(guān)	28	${2^{98.8}}$	$ {2^{246.9}} $
5.2節(jié)	256	qCCA	19	–	$ {2^{111}} $

下載: 導(dǎo)出CSV

參考文獻(xiàn)(41)

KNUDSEN L R. The security of Feistel ciphers with six rounds or less[J]. Journal of Cryptology, 2002, 15(3): 207–222. doi: 10.1007/s00145-002-9839-y

ISOBE T and SHIBUTANI K. Generic key recovery attack on Feistel scheme[C]. The 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, 2013: 464–485.

GUO Jian, JEAN J, NIKOLI? I, et al. Meet-in-the-middle attacks on generic Feistel constructions[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, China, 2014: 458–477.

DINUR I, DUNKELMAN O, KELLER N, et al. New attacks on Feistel structures with improved memory complexities[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 433–454.

AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: A 128-bit Block Cipher Suitable for Multiple Platforms - Design and Analysis[M]. Berlin, Heidelberg: Springer, 2001: 39–56.

National Soviet Bureau of Standards. GOST 28147-89 Information processing systems. cryptographic protection cryptographic transformation algorithm[S]. 1989.

ZHENG Yuliang, MATSUMOTO T, and IMAI H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses[C]. Conference on the Theory and Application of Cryptology, Santa Barbara, USA, 1990: 461–480.

ANDERSON R and BIHAM E. Two practical and provably secure block ciphers: BEAR and LION[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 113–120.

LUCKS S. Faster luby-rackoff ciphers[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 189–203.

SCHNEIER B and KELSEY J. Unbalanced Feistel networks and block cipher design[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 121–144.

First AES Candidate Conference[EB/OL]. http://csrc.nist.gov/archive/aes/round1/conf1/aes1conf.htm.

SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128-bit blockcipher CLEFIA (extended abstract)[C]. The 14th International Workshop on Fast Software Encryption, Luxembourg, Luxembourg, 2007: 181–195.

GUERON S and MOUHA N. Simpira v2: A family of efficient permutations using the AES round function[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 95–125.

LUBY M and RACKOFF C. How to construct pseudorandom permutations from pseudorandom functions[J]. SIAM Journal on Computing, 1988, 17(2): 373–386. doi: 10.1137/0217022

MORIAI S and VAUDENAY S. On the pseudorandomness of top-level schemes of block ciphers[C]. The 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, 2000: 289–302.

HOANG V T and ROGAWAY P. On generalized Feistel networks[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010: 613–630.

JUTLA C S. Generalized birthday attacks on unbalanced Feistel networks[C]. The 18th Annual International Cryptology Conference, Santa Barbara, USA, 1998: 186–199.

GUO Jian, JEAN J, NIKOLIC I, et al. Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions[J]. IACR Transactions on Symmetric Cryptology, 2016(2): 307–337.

NACHEF V, VOLTE E, and PATARIN J. Differential attacks on generalized Feistel schemes[C]. The 12th International Conference on Cryptology and Network Security, Paraty, Brazil, 2013: 1–19.

TJUAWINATA I, HUANG Tao, and WU Hongjun. Improved differential cryptanalysis on generalized Feistel schemes[C]. The 18th International Conference on Cryptology in India, Chennai, India, 2017: 302–324.

PATARIN J, NACHEF V, and BERBAIN C. Generic attacks on unbalanced Feistel schemes with contracting functions[C]. The 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, 2006: 396–411.

PATARIN J, NACHEF V, and BERBAIN C. Generic attacks on unbalanced Feistel schemes with expanding functions[C]. The 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, 2007: 325–341.

VOLTE E, NACHEF V, and PATARIN J. Improved generic attacks on unbalanced Feistel schemes with expanding functions[C]. The 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2010: 94–111.

GROVER L K. A fast quantum mechanical algorithm for database search[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219.

KUWAKADO H and MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation[C]. IEEE International Symposium on Information Theory, Austin, USA, 2010: 2682–2685.

SIMON D R. On the power of quantum computation[J]. SIAM Journal on Computing, 1997, 26(5): 1474–1483. doi: 10.1137/S0097539796298637

KUWAKADO H and MORII M. Security on the quantum-type even-mansour cipher[C]. 2012 International Symposium on Information Theory and its Applications, Honolulu, USA, 2012: 312–316.

KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking symmetric cryptosystems using quantum period finding[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 207–237.

BONNETAIN X. Quantum key-recovery on full AEZ[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2018: 394–406.

LEANDER G and MAY A. Grover meets simon - quantumly attacking the FX-construction[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 161–178.

ZHANDRY M. How to construct quantum random functions[C]. The 53rd IEEE Annual Symposium on Foundations of Computer Science, New Brunswick, USA, 2012: 679–687.

ITO G, HOSOYAMADA A, MATSUMOTO R, et al. Quantum chosen-ciphertext attacks against Feistel ciphers[C]. The Cryptographers' Track at the RSA Conference, San Francisco, USA, 2019: 391–411.

HOSOYAMADA A and SASAKI Y. Quantum demiric-sel?uk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions[C]. The 11th International Conference on Security and Cryptography for Networks, Amalfi, Italy, 2018: 386–403.

DONG Xiaoyang and WANG Xiaoyun. Quantum key-recovery attack on Feistel structures[J]. Science China Information Sciences, 2018, 61(10): 102501. doi: 10.1007/s11432-017-9468-y

DONG Xiaoyang, LI Zheng, and WANG Xiaoyun. Quantum cryptanalysis on some generalized Feistel schemes[J]. Science China Information Sciences, 2019, 62(2): 22501. doi: 10.1007/s11432-017-9436-7

DONG Xiaoyang, DONG Bingyou, and WANG Xiaoyun. Quantum attacks on some Feistel block ciphers[R]. Cryptology ePrint Archive, Report 2018/504, 2018.

BONNETAIN X, NAYA-PLASENCIA M, and SCHROTTENLOHER A. On quantum slide attacks[R]. Cryptology ePrint Archive, Report 2018/1067, 2018.

HOSOYAMADA A and IWATA T. Tight quantum security bound of the 4-round luby-rackoff construction[R]. Cryptology ePrint Archive, Report 2019/243, 2019.

WAGNER D. The boomerang attack[C]. The 6th International Workshop on Fast Software Encryption, Rome, Italy, 1999: 156–170.

WANG Meiqin, WANG Xiaoyun, and HU Changhui. New linear cryptanalytic results of reduced-round of CAST-128 and CAST-256[C]. The 15th International Workshop on Selected Areas in Cryptography, Sackville, Canada, 2009: 429–441.

BOGDANOV A, LEANDER G, NYBERG K, et al. Integral and multidimensional linear distinguishers with correlation zero[C]. The 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2012: 244–261.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計