减缩轮PRIDE算法的线性分析

doi:10.3969/j.issn.0372-2112.2017.02.028

电子学报 ›› 2017, Vol. 45 ›› Issue (2): 468-476.DOI: 10.3969/j.issn.0372-2112.2017.02.028

减缩轮PRIDE算法的线性分析

伊文坛, 田亚, 陈少真

数学工程与先进计算国家重点实验室, 河南郑州 450001

收稿日期:2015-07-15 修回日期:2016-01-04 出版日期:2017-02-25
- 作者简介:
- 伊文坛,男,1989年生于山东菏泽.研究方向为分组密钥安全性分析.E-mail:nlwt89@sina.com;田亚,男,1991年生于江苏徐州.硕士研究生,研究方向为分组密码安全性分析;陈少真,女,1967年生于江苏无锡.博士生导师,研究方向为分组密码的设计与分析.
- 基金资助:
- 信息保障技术重点实验室开放基金 (No.KJ-13-010）

Linear Cryptanalysis of Reduced-Round PRIDE Block Cipher

YI Wen-tan, TIAN Ya, CHEN Shao-zhen

State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, Henan 450001, China

Received:2015-07-15 Revised:2016-01-04 Online:2017-02-25 Published:2017-02-25

摘要/Abstract

摘要：

PRIDE是Albrecht等人在2014美密会上提出的轻量级分组密码算法.PRIDE采用典型SPN密码结构，共迭代20轮.其设计主要关注于线性层，兼顾了算法的效率和安全.该文探讨了S盒和线性层矩阵的线性性质，构造了16条优势为2^-5的2轮线性逼近和8条优势为2^-3的1轮线性逼近.利用合适的线性逼近，结合密钥扩展算法、S盒的线性性质和部分和技术，我们对18轮和19轮PRIDE算法进行了线性分析.该分析分别需要2⁶⁰个已知明文，2^74.9次18轮加密和2⁶²个已知明文，2^74.9次19轮加密.另外，我们给出了一些关于S盒差分性质和线性性质之间联系的结论，有助于减少攻击过程中的计算量.本文是已知明文攻击.本文是关于PRIDE算法的第一个线性分析.

关键词: 分组密码, PRIDE算法, 线性分析, 线性逼近

Abstract:

PRIDE is a light weight block cipher designed by Albrecht et al.in CRYPTO 2014,which adopts the classical SPN (Substitution Permutation Network) structure and iterates for 20 rounds.The construction of linear layers is very interesting and performances good both in security and efficiency.This paper investigates the properties of the S-boxes and the linear matrices,and then constructs 16 different 2-round iterative linear approximations with the bis 2^-5 and 8 different 1-round iterative linear approximations with the bis 2^-3.Base on some suitable approximations,attacks on 18-round and 19-round PRIDE are presented by means of linear cryptanalysis with the properties of key schedule,the linear characteristics and the partial-sum technique,which need about 2^74.9 encryptions with 2⁶⁰ known plaintexts and 2^74.9 encryptions with 2⁶² known plaintexts,respectively.Furthermore,some interesting links between differential and linear characteristics are shown,which are helpful to reduce the compute complexity.Our analysis is the first linear attack on PRIDE block cipher with known plaintexts.

Key words: block cipher, PRIDE, linear cryptanalysis, linear approximation

中图分类号:

TP309

伊文坛, 田亚, 陈少真. 减缩轮PRIDE算法的线性分析[J]. 电子学报, 2017, 45(2): 468-476.

YI Wen-tan, TIAN Ya, CHEN Shao-zhen. Linear Cryptanalysis of Reduced-Round PRIDE Block Cipher[J]. Acta Electronica Sinica, 2017, 45(2): 468-476.

参考文献

[1] Bogdanov A,Knudsen LR,Leander G,et al.Present:An ultra-lightweight block cipher[A].CHES 2007[C].Vienna,Austria:LNCS 4727,2007.450-466.
[2] Izadi M,Sadeghiyan B,Sadeghian S S,et al.MIBS:A new light-weight block cipher[A].Cryptology and Network Security 2009[C].LNCS 5888,2009.334-348.
[3] Guo J,Peyein T,Poschmann A,et al.The LED Block Cipher[A].CHES 2011[C].Nara,Japan:LNCS 6917,2011.326-341.
[4] Wu W L,Zhang L.LBlock:A Lightweight Block Cipher[A].ACNS 2011[C].Nerja,Spain:LNCS 6715,2011.327-344.
[5] Beaulieu R,et al.The SIMON and SPECK Families of Lightweight Block Ciphers[Z].IACR Cryptology ePrint Archive,2013:414.
[6] Albrecht M R,Driessen B,Kavun E B,et al.Block Ciphers-Focus on the Linear Layer (Feat.PRIDE)[M].Advances in Cryptology-CRYPTO 2014,Santa Barbara,CA,USA:LNCS 8616,2014.57-76.
[7] Zhao J,et al.Differential Analysis on Block Cipher PRIDE[Z].Cryptology ePrint Archive,http://eprint.iacr.org/2014/5/25.
[8] Yang Q,et al.Improved differential analysis of block cipher PRIDE[A].Information Security Practice and Experience[C].LNCS,2015.9065:209-219.
[9] Dai Y,et al.Cryptanalysis of Full PRIDE Block Cipher[Z].Cryptology ePrint Archive,http://eprint.iacr.org/2014/987.pdf.
[10] Matsui M.Linear cryptanalysis method for DES cipher[A].Advances in Cryptology-EUROCRYPT'93[C].Norway:LNCS 765,1994.386-397.
[11] Matsui M.The first experimental cryptanalysis of the Data Encryption Standard[A].Advances in Cryptology-Crypto'94[C].California,USA:LNCS 839,1994.1-11.
[12] Biryukov A,De Canniere C,Quisquater M.On multiple linear approximations[A].Advances in Cryptology-CRYPTO 2004[C].California,USA:LNCS 3152,2004.1-22.
[13] Hermelin M,Cho J Y,Nyberg K.Multidimensional linear cryptanalysis of reduced round Serpent[A].Information Security and Privacy[C].LNCS 5107,2008.203-215.
[14] Kaliski Jr B S,Robshaw M J B.Linear cryptanalysis using multiple approximations[A].Advances in Cryptology-Crypto'94[C].California,USA:LNCS 839,1994.26-39.
[15] Hermelin M,Cho J Y,Nyberg K.Multidimensional extension of Matsui's algorithm 2[A].Fast Software Encryption-FSE2009[C].Leuven,Belgium:LNCS 5665,2009.209-227.
[16] Bogdanov A,et al.Linear hulls with correlation zero and linear cryptanalysis of block ciphers[J].Designs,Codes and Cryptography,2014,70(3):369-383.
[17] Bogdanov A,Wang M.et al.Zero correlation linear cryptanalysis with reduced data complexity[A].Fast Software Encryption-FSE 2012[C].Washington DC,USA:LNCS 7549,2012.29-48.
[18] Bogdanov A,Leander G,Nyberg K,et al.Integral and multidimensional linear distinguishers with correlation zero[A].Advances in Cryptology-ASIACRYPT 2012[C].Beijing:LNCS 7658,2012.244-261.
[19] Biham E,et al.An Improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[A].Selected Areas in Cryptography-SAC 2014[C].Montreal,Quebec:LNCS 8781,2014.59-76.
[20] Cho J,et al.Linear cryptanalysis of reduced-round PRESENT[A].Topics in Cryptology-CT-RSA 2010[C].San Francisco,Ca:LNCS 5985,2010.302-317.
[21] 陈怀凤,温隆,王美琴.基于FFT技术的MULTI2线性分析[J].密码学报,2014,1(4):311-320. Chen Huaifeng,Wen Long,Wang Meiqin.Linear cryptanalysis on MULTI2 with FFT technique[J].Journal of Cryptologic Research,2014,1(4):311-320.(in Chinese)
[22] Selcuk A A,et al.On probability of success in linear and differential cryptanalysis[J].Journal of Cryptology,2008,21(1):131-147.

减缩轮PRIDE算法的线性分析

Linear Cryptanalysis of Reduced-Round PRIDE Block Cipher

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	欧庆于, 罗芳, 吴晓平, 杨鹏. 基于电压毛刺故障扰动的分组密码安全性度量方法研究[J]. 电子学报, 2021, 49(3): 417-423.
[2]	马宿东, 金晨辉, 关杰. 一类ARIA型扩散结构分支数的研究[J]. 电子学报, 2020, 48(3): 449-455.
[3]	李航, 任炯炯, 陈少真. 减轮LEA密码算法的积分攻击[J]. 电子学报, 2020, 48(1): 17-27.
[4]	王念平. 一类分组密码变换簇抵抗线性密码分析的安全性评估[J]. 电子学报, 2020, 48(1): 137-142.
[5]	杜怡然, 南龙梅, 戴紫彬, 李伟. 可重构分组密码逻辑阵列加权度量模型及高能效映射算法[J]. 电子学报, 2019, 47(1): 82-91.
[6]	付立仕, 崔霆, 金晨辉. 嵌套SP网络的New-Structure系列结构的零相关线性逼近与不可能差分性质研究[J]. 电子学报, 2017, 45(6): 1367-1374.
[7]	冯晓, 李伟, 戴紫彬, 马超, 李功丽. 面向分组密码的可重构异构多核并行处理架构[J]. 电子学报, 2017, 45(6): 1311-1320.
[8]	魏长河, 李俊志, 张少武. 对288轮Trivium算法的线性分析[J]. 电子学报, 2017, 45(6): 1456-1461.
[9]	王寿成, 严迎建, 徐进辉. 基于流体系结构的高效能分组密码处理器研究[J]. 电子学报, 2017, 45(4): 937-943.
[10]	王寿成, 李功丽, 严迎建, 徐进辉. 面向分组密码的四维度并行处理架构研究[J]. 电子学报, 2017, 45(10): 2457-2463.
[11]	李浪, 李肯立, 贺位位, 邹祎, 刘波涛. Magpie:一种高安全的轻量级分组密码算法[J]. 电子学报, 2017, 45(10): 2521-2527.
[12]	王念平. 四分组类CLEFIA变换簇抵抗差分密码分析的安全性评估[J]. 电子学报, 2017, 45(10): 2528-2532.
[13]	郭建胜, 崔竞一, 罗伟, 刘翼鹏. CIKS-128分组算法的相关密钥-差分攻击[J]. 电子学报, 2016, 44(8): 1837-1844.
[14]	王健, 戚文峰, 郑群雄. 模m加法的一类线性逼近关系研究[J]. 电子学报, 2015, 43(11): 2194-2199.
[15]	黄永洪, 郭建胜, 罗伟. LBlock算法的相关密钥-不可能差分攻击[J]. 电子学报, 2015, 43(10): 1948-1953.