LiCi分組密碼算法的不可能差分分析

韋永壯; 史佳利; 李靈琛

doi:10.11999/JEIT180729

LiCi分組密碼算法的不可能差分分析

doi: 10.11999/JEIT180729

韋永壯^{1, 2},
史佳利^{2, 3, ,},
李靈琛^{4, 5}

1.
桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室? ?桂林? ?541004
2.
桂林電子科技大學(xué)廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室? ?桂林? ?541004
3.
桂林電子科技大學(xué)廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室? ?桂林? ?541004
4.
中國科學(xué)院大學(xué)? ?北京? ?100049
5.
中國科學(xué)院軟件研究所? ?北京? ?100190

基金項(xiàng)目: 國家自然科學(xué)基金(61572148, 61872103, 61561016), 廣西研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目(YCBZ2018051), 獲桂林電子科技大學(xué)研究生優(yōu)秀學(xué)位論文培育項(xiàng)目(16YJPYSS12), 桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃(2018YJCX45)

詳細(xì)信息

作者簡(jiǎn)介:
韋永壯：男，1976年生，教授，博士生導(dǎo)師，研究方向?yàn)槊艽a函數(shù)、分組密碼分析

史佳利：女，1992年生，碩士生，研究方向?yàn)閷?duì)稱密碼算法分析

李靈?。号?，1988年生，博士生，研究方向?yàn)榉纸M密碼的分析與設(shè)計(jì)

通訊作者:
史佳利　jiali00@126.com

中圖分類號(hào): TP309
計(jì)量
- 文章訪問數(shù): 3679
- HTML全文瀏覽量: 1608
- PDF下載量: 122
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-07-19
- 修回日期: 2018-10-29
- 網(wǎng)絡(luò)出版日期: 2019-03-18
- 刊出日期: 2019-07-01

Impossible Differential Cryptanalysis of LiCi Block Cipher

Yongzhuang WEI^{1, 2},
Jiali SHI^{2, 3
, ,},
Lingchen LI^{4, 5}

1.
Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004 ,China
2.
Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing, Guilin University of Electronic Technology, Guilin 541004 ,China
3.
Guangxi Colleges and University Key Laboratory of Cloud Computing and Complex Systems, Guilin University of Electronic Technology, Guilin 541004 ,China
4.
University of Chinese Academy of Sciences, Beijing 100049, China
5.
Institute of Software, Chinese Academy of Sciences, Beijing 100190, China

Funds: The National Natural Science Foundation of China (61572148, 61872103, 61561016), The Innovation Project of Guangxi Graduate Education (YCBZ2018051), Guilin University of Electrionic Technology Excellent Graduate Thesis Program (16YJPYSS12), The Innovation Project of Guilin University of Electrionic Technology Graduate Education (2018YJCX45)

摘要

摘要: LiCi是由Patil等人(2017)提出的輕量級(jí)分組密碼算法。由于采用新型的設(shè)計(jì)理念，該算法具有結(jié)構(gòu)緊湊、能耗低、占用芯片面積小等優(yōu)點(diǎn)，特別適用于資源受限的環(huán)境。目前該算法的安全性備受關(guān)注，Patil等人聲稱：16輪簡(jiǎn)化算法足以抵抗經(jīng)典的差分攻擊及線性攻擊。該文基于S盒的差分特征，結(jié)合中間相遇思想，構(gòu)造了一個(gè)10輪的不可能差分區(qū)分器?；诖藚^(qū)分器，向前后各擴(kuò)展3輪，并利用密鑰編排方案，給出了LiCi的一個(gè)16輪的不可能差分分析方法。該攻擊需要時(shí)間復(fù)雜度約為2^83.08次16輪加密，數(shù)據(jù)復(fù)雜度約為2^59.76選擇明文，存儲(chǔ)復(fù)雜度約為2^76.76數(shù)據(jù)塊，這說明16輪簡(jiǎn)化的LiCi算法無法抵抗不可能差分攻擊。
- 輕量分組密碼算法 /
- LiCi算法 /
- 不可能差分分析 /
- 差分特征
Abstract: LiCi algorithm is a newly lightweight block cipher. Due to its new design idea adopted by Patil et al, it has the advantages of compact design, low energy consumption and less chip area, thus is is especially suitable for resource-constrained environments. Currently, its security receives extensively attention, and Patil et al. claimed that the 16-round reduced LiCi can sufficiently resist both differential attack and linear attack. In this paper, a new 10-round impossible differential distinguisher is constructed based on the differential characteristics of the S-box and the meet-in-the-middle technique. Moreover, on the basis of this distinguisher, a 16-round impossible differential attack on LiCi is proposed by respectively extending 3-round forward and backward via the key scheduling scheme. This attack requires a time complexity of about 2^83.08 16-round encryptions, a data complexity of about 2^59.76 chosen plaintexts, and a memory complexity of 2^76.76 data blocks, which illustrates that the 16-round LiCi cipher can not resist impossible differential attack.
- Lightweight block cipher /
- LiCi cipher /
- Impossible differential cryptanalysis /
- Differential characteristic

HTML全文

圖 1 LiCi算法的輪函數(shù)

下載: 全尺寸圖片幻燈片

圖 2 LiCi算法的10輪不可能差分路線

下載: 全尺寸圖片幻燈片

圖 3 LiCi算法的16輪不可能差分分析

下載: 全尺寸圖片幻燈片

表 1 S盒輸入/輸出差分特征

輸入差分	0001	0100	1000	1100	1101	**11	*1	*0	***1	***0
輸出差分	1***	***1	***1	1**0	0***	0001	0010	0011	0100	0101

下載: 導(dǎo)出CSV

表 2 S盒輸入/輸出差分特征概率

輸入差分	**11	*1	***1	****	0001	0***	0*	01**	*000
輸出差分	0001	0010	0100	1000	1***	****	****	****	****
概率	1/4	1/8	1/8	1/16	1/8	1/2	1/2	1/4	1/8

下載: 導(dǎo)出CSV

表 3 不可能差分分析16輪LiCi算法的密鑰恢復(fù)各步驟的時(shí)間復(fù)雜度

步驟	恢復(fù)的密鑰比特	猜測(cè)比特?cái)?shù)目	時(shí)間復(fù)雜度(單位：次16輪加密所用的時(shí)間)
(1)	–	0	${2^{m + 49}} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 42}}$
(2)	${\rm{Rk}}{0_1}\left[ {24 \sim 21} \right]$	4	${2^{m + 21}} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 18}}$
(3)	${\rm{Rk}}{15_2}\left[ {15 \sim 12} \right]$	4	${2^{m + 18}} \times {2^4} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 19}}$
(4)	${\rm{Rk}}{15_2}\left[ {31 \sim 28} \right]$	4	${2^{m + 15}} \times {2^4} \times {2^4} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 20}}$
(5)	${\rm{Rk}}{15_2}\left[ {23 \sim 20} \right]$	4	${2^{m + 14}} \times {2^4} \times {2^4} \times {2^4} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 23}}$
(6)	${\rm{Rk}}{15_1}\left[ {16 \sim 13} \right]$, ${\rm{Rk}}{14_2}\left[ {23 \sim 20} \right]$	8	${2^{m + 13}} \times {2^4} \times {2^4} \times {2^4} \times {2^4} \times {2^8} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 30}}$
(7)	${\rm{Rk}}{15_2}\left[ {19 \sim 16,11 \sim 9} \right]$, ${\rm{Rk}}{15_1}\left[ {12 \sim 9} \right]$, ${\rm{Rk}}{14_2}\left[ {19 \sim 16} \right]$	12	${2^{m + 10}} \times {2^{16}} \times {2^8} \times {2^{12}} \times 2 \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 40}}$
(8)	${\rm{Rk}}{15_2}\left[ {27 \sim 24} \right]$, ${\rm{Rk}}{15_1}\left[ {20 \sim 17} \right]$, ${\rm{Rk}}{14_2}\left[ {27 \sim 24} \right]$	12	${2^{m + 7}} \times {2^{24}} \times {2^{12}} \times {2^{12}} \times 2 \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 49}}$
(9)	${\rm{Rk}}{15_2}\left[ {8 \sim 6} \right]$, ${\rm{Rk}}{15_1}\left[ {8 \sim 6} \right]$, ${\rm{Rk}}{15_2}\left[ {15 \sim 13} \right]$, ${\rm{Rk}}{14_1}\left[ {16 \sim 13} \right]$	10	${2^{m + 5}} \times {2^{24}} \times {2^{12}} \times {2^{12}} \times {2^{10}} \times 2 \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 56}}$
(10)	${\rm{Rk}}{0_1}\left[ {20 \sim 9} \right]$, ${\rm{Rk}}{0_2}\left[ {23 \sim 20} \right]$, ${\rm{Rk}}{1_1}\left[ {16 \sim 13} \right]$	20	${2^{m{\rm{ - }}16}} \times {2^{58}} \times {2^{20}} \times 3 \times \frac{1}{{8 \times 16}} + {2^{74}} = {2^{{{m}} + 56.58}} + {2^{74}}$

下載: 導(dǎo)出CSV

表 4 LiCi算法的攻擊結(jié)果對(duì)比

分析方法	攻擊輪數(shù)	選擇明文量	時(shí)間復(fù)雜度	存儲(chǔ)復(fù)雜度	參考文獻(xiàn)
線性分析	16	2¹⁰⁶	–	–	文獻(xiàn)[10]
差分分析	16	2⁹⁶	–	–	文獻(xiàn)[10]
不可能差分分析	16	2^59.76	2^83.08	2^76.76	本文

下載: 導(dǎo)出CSV

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

BIRYUKOV A and PERRIN L. State of the art in lightweight symmetric cryptography[R]. Cryptology ePrint Archive: Report 2017/511, 2017: 1–11.

GUO Jian, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]. Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems, Nara, Japan, 2011: 326–341.

BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. Proceedings of 9th International Workshop on Cryptographic Hardware and Embedded Systems, Vienna, Austria, 2007: 450–466.

BANIK S, PANDEY S K, PEYRIN T, et al. GIFT: A small present[C]. Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded Systems, Taipei, China, 2017: 321–345.

BANIK S, BOGDANOV A, ISOBE T, et al. Midori: A block cipher for low energy[C]. Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 2015: 411–436.

WU Wenling and ZHANG Lei. LBlock: A lightweight block cipher[C]. Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Nerja, Spain, 2011: 327–344.

國家商用密碼管理辦公室. 無線局域網(wǎng)產(chǎn)品使用的SMS4密碼算法[EB/OL]. http://www.oscca.gov.cn/sca/c100061/201611/1002423/files/330480f731f64e1ea75138211ea0dc27.pdf, 2018.

Office of State Commercial Cipher Administration. Block cipher for WLAN products-SMS4[EB/OL]. http://www.oscca.gov.cn/sca/c100061/201611/1002423/files/330480f731f64e1ea75138211ea0dc27.pdf, 2018.

BEAULIEU R, TREATMAN-CLARK S, SHORS D, et al. The SIMON and SPECK lightweight block ciphers[C]. Proceedings of the 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6.

AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: A 128-bit block cipher suitable for multiple platforms-design and analysis[C]. Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography, Ontario, Canada, 2000: 39–56.

PATIL J, BANSOD G, and KANT K S. LiCi: A new ultra-lightweight block cipher[C]. Proceedings of 2017 International Conference on Emerging Trends & Innovation in ICT, Pune, India, 2017: 40–45.

KNUDSEN L R. DEAL-a 128-bit block cipher[R]. Technical Report, 1998.

BIHAM E, BIRYUKOV A, and SHAMIR A. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[M]. Berlin, Germany, 1999: 12–23.

BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[C]. Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, 1991: 2–21.

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

LIU Ya, GU Dawu, LIU Zhiqiang, et al. Impossible differential attacks on reduced-round LBlock[C]. Proceedings of the 8th International Conference on Information Security Practice and Experience, Hangzhou, China, 2012: 97–108.

KONDO K, SASAKI Y, TODO Y, et al. Analyzing key schedule of SIMON: Iterative key differences and application to related-key impossible differentials[C]. Proceedings of the 12th International Workshop on Security, Hiroshima, Japan, 2017: 141–158.

MEHRDAD A, MOAZAMI F, and SOLEIMANY H. Impossible differential cryptanalysis on Deoxys-BC-256[R]. Cryptology ePrint Archive: Report 2018/048, 2018.

SHAHMIRZADI A R, AZIMI S A, SALMASIZADEH M, et al. Impossible differential cryptanalysis of reduced-round Midori64 block cipher[J]. ISeCure, 2018, 10(1): 3–14.

TEZCAN C. Improbable differential attacks on Present using undisturbed bits[J]. Journal of Computational and Applied Mathematics, 2014, 259: 503–511. doi: 10.1016/j.cam.2013.06.023

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)