Piccolo算法的Biclique分析
|
摘要
Piccolo算法作为一种硬件实现极为高效的轻量级分组密码算法,对其的安全性评估一直是学术界研究的热点.本文中基于Biclique攻击的思想,结合算法轮函数结构和密钥扩展方面的性质,利用非平衡Biclique攻击和Stars攻击两种方法对Piccolo-80和Piccolo-128算法分别进行了安全性分析.其中,对于Piccolo-80算法,进行非平衡Biclique攻击所需的数据复杂度、存储复杂度以及计算复杂度分别为2~(36)、2~(11.12)和2~(79.03);进行Stars攻击所需的数据复杂度、存储复杂度以及计算复杂度分别为2、2~(8.12)和2~(79.31).对于Piccolo-128算法的这两种攻击分别所需的数据复杂度为2~(20)、2,存储复杂度为2~(11.17)、2~(8.19),计算复杂度为2~(127.05)、2~(127.40).与现有的攻击结果相比,增加考虑了存储复杂度,且在数据复杂度和计算复杂度方面均有一定的优化.
The lightweight block cipher Piccolo is very efficient for hardware implementation, and its security evaluation has been a hot topic in academia. Based on the idea of biclique attack, combined with the properties of the round function and the key schedule of Piccolo, this paper analyzes the security of Piccolo-80 and Piccolo-128 with unbalanced biclique attack and stars attack. For the unbalanced biclique attack of Piccolo-80, the required data complexity is 2~(36), memory complexity is 2~(11.12), and computational complexity is 2~(79.03). For the Stars attack of Piccolo-80, the required data complexity is 2, memory complexity is 2~(8.12) and computational complexity is 2~(79.31). For the two attacks of Piccolo-128, the required data complexities are 2~(20) and 2, memory complexities are 2~(11.17) and 2~(8.19), and computational complexities are 2~(127.05) and 2~(127.40), respectively. Compared with the existing attacks, this study takes into consideration of the memory complexity, and makes some optimization in terms of data complexity and computational complexity.
The lightweight block cipher Piccolo is very efficient for hardware implementation, and its security evaluation has been a hot topic in academia. Based on the idea of biclique attack, combined with the properties of the round function and the key schedule of Piccolo, this paper analyzes the security of Piccolo-80 and Piccolo-128 with unbalanced biclique attack and stars attack. For the unbalanced biclique attack of Piccolo-80, the required data complexity is 2~(36), memory complexity is 2~(11.12), and computational complexity is 2~(79.03). For the Stars attack of Piccolo-80, the required data complexity is 2, memory complexity is 2~(8.12) and computational complexity is 2~(79.31). For the two attacks of Piccolo-128, the required data complexities are 2~(20) and 2, memory complexities are 2~(11.17) and 2~(8.19), and computational complexities are 2~(127.05) and 2~(127.40), respectively. Compared with the existing attacks, this study takes into consideration of the memory complexity, and makes some optimization in terms of data complexity and computational complexity.
引文
[1]SZCZECHOWIAK P,COLLIER M.TinyIBE:Identity-based encryption for heterogeneous sensor networks[C].In:2009 International Conference on Intelligent Sensors,Sensor Networks and Information Processing(ISSNIP2009).IEEE,2009:319-354.[DOI:10.1109/ISSNIP.2009.5416743]
[2]SINGH S,SHARMA P K,MOON S Y,et al.Advanced lightweight encryption algorithms for IoT devices:Survey,challenges and solutions[J].Journal of Ambient Intelligence and Humanized Computing,2017:1-18.[DOI:10.1007/s12652-017-0494-4]
[3]WANG B C,HU Y P.Public key cryptosystem based on two cryptographic assumptions[J].IEE ProceedingsCommunications,2005,152(6):861-865.[DOI:10.1049/ip-com:20045278]
[4]GUERMAZI A,ABID M.An efficient key distribution scheme to secure data-centric routing protocols in hierarchical wireless sensor networks[J].Procedia Computer Science,2011,5:208-215.[DOI:10.1016/j.procs.2011.07.028]
[5]CAO X F,KOU W D,DU X N.A pairing-free identity-based authenticated key agreement protocol with minimal message exchanges[J].Information Sciences,2010,180(15):2895-2903.[DOI:10.1016/j.ins.2010.04.002]
[6]TENG J K,WU C K.An identity-based group key agreement protocol for low power mobile devices[J].Chinese Journal of Electronics,2016,25(4):726-733.[DOI:10.1049/cje.2016.06.038]
[7]SHIBUTANI K,ISOBE T,HIWATARI H,et al.Piccolo:An ultra-lightweight blockcipher[C].In:Cryptographic Hardware and Embedded Systems-CHES 2011.Springer Berlin Heidelberg,2011:342-357.[DOI:10.1007/978-3-642-23951-9_23]
[8]BOGDANOV A,KHOVRATOVICH D,RECHBERGER C.Biclique cryptanalysis of the full AES[C].In:Advances in Cryptology-ASIACRYPT 2011.Springer Berlin Heidelberg,2011:344-371.[DOI:10.1007/978-3-642-25385-0_19]
[9]CUI J Y,GUO J S,LIU Y P,et al.Biclique attack on CLEFIA-256[J].Journal of Information Engineering University,2017,18(3):322-327.[DOI:10.3969/j.issn.1671-0673.2017.03.013]崔竞一,郭建胜,刘翼鹏,等.CLEFIA-256算法的Biclique攻击[J].信息工程大学学报,2017,18(3):322-327.[DOI:10.3969/j.issn.1671-0673.2017.03.013]
[10]WANG Y,WU W,YU X,et al.Security on LBlock against Biclique cryptanalysis[C].In:Information Security Applications-WISA 2012.Springer Berlin Heidelberg,2012:1-14.[DOI:10.1007/978-3-642-35416-8_1]
[11]JEONG K,KANG H C,LEE C,et al.Biclique cryptanalysis of lightweight block ciphers PRESENT,Piccolo and LED[J].IACR Cryptology ePrint Archive,2012:2012/621.https://eprint.iacr.org/2012/621.
[12]GONG Z,LIU S S,WEN Y M,et al.Biclique analysis on the reduced-round PRESENT[J].Chinese Journal of Computers,2013,36(6):1139-1148.[DOI:10.3724/SP.J.1016.2013.01139]龚征,刘树生,温雅敏,等.缩减轮数PRESENT算法的Biclique分析[J].计算机学报,2013,36(6):1139-1148.[DOI:10.3724/SP.J.1016.2013.01139]
[13]YUAN Z,PENG Z.Biclique cryptanalysis of lightweight block cipher PRINCE[J].Journal of Cryptologic Research,2017,4(6):517-527.[DOI:10.13868/j.cnki.jcr.000203]袁征,彭真.轻量级分组密码PRINCE算法的Biclique分析[J].密码学报,2017,4(6):517-527.[DOI:10.13868/j.cnki.jcr.000203]
[14]LIU Y,CHENG L,LIU Z,et al.Improved meet-in-the-middle attacks on reduced-round Piccolo[J].Science China Information Sciences,2018,61(3):032108.[DOI:10.1007/s11432-016-9157-y]
[15]WANG Y,WU W,YU X.Biclique cryptanalysis of reduced-round Piccolo block cipher[C].In:Information Security Practice and Experience-ISPEC 2012.Springer Berlin Heidelberg,2012:337-352.[DOI:10.1007/978-3-642-29101-2_23]
[16]HAN G,ZHANG W.Improved Biclique cryptanalysis of the lightweight block cipher Piccolo[J].Security and Communication Networks,2017:7589306.[DOI:10.1155/2017/7589306]
[17]AHMADI S,AHMADIAN Z,MOHAJERI J,et al.Low-data complexity Biclique cryptanalysis of block ciphers with application to Piccolo and Hight[J].IEEE Transactions on Information Forensics and Security,2014,9(10):1641-1652.[DOI:10.1109/TIFS.2014.2344445]
[18]CUI J Y,GUO J S,LIU Y P.Generalized independent Biclique automated attack framework and its applications[J].Chinese Journal of Computers,2018,41(2):349-367.[DOI:10.11897/SP.J.1016.2018.00349]崔竞一,郭建胜,刘翼鹏.广义Independent Biclique攻击框架及其应用[J].计算机学报,2018,41(2):349-367.[DOI:10.11897/SP.J.1016.2018.00349]
[19]BOGDANOV A,CHANG D,GHOSH M,et al.Biclique with minimal data and time complexity for AES[C].In:Information Security and Cryptology-ICISC 2014.Springer Cham,2014:160-174.[DOI:10.1007/978-3-319-15943-0_10]
[2]SINGH S,SHARMA P K,MOON S Y,et al.Advanced lightweight encryption algorithms for IoT devices:Survey,challenges and solutions[J].Journal of Ambient Intelligence and Humanized Computing,2017:1-18.[DOI:10.1007/s12652-017-0494-4]
[3]WANG B C,HU Y P.Public key cryptosystem based on two cryptographic assumptions[J].IEE ProceedingsCommunications,2005,152(6):861-865.[DOI:10.1049/ip-com:20045278]
[4]GUERMAZI A,ABID M.An efficient key distribution scheme to secure data-centric routing protocols in hierarchical wireless sensor networks[J].Procedia Computer Science,2011,5:208-215.[DOI:10.1016/j.procs.2011.07.028]
[5]CAO X F,KOU W D,DU X N.A pairing-free identity-based authenticated key agreement protocol with minimal message exchanges[J].Information Sciences,2010,180(15):2895-2903.[DOI:10.1016/j.ins.2010.04.002]
[6]TENG J K,WU C K.An identity-based group key agreement protocol for low power mobile devices[J].Chinese Journal of Electronics,2016,25(4):726-733.[DOI:10.1049/cje.2016.06.038]
[7]SHIBUTANI K,ISOBE T,HIWATARI H,et al.Piccolo:An ultra-lightweight blockcipher[C].In:Cryptographic Hardware and Embedded Systems-CHES 2011.Springer Berlin Heidelberg,2011:342-357.[DOI:10.1007/978-3-642-23951-9_23]
[8]BOGDANOV A,KHOVRATOVICH D,RECHBERGER C.Biclique cryptanalysis of the full AES[C].In:Advances in Cryptology-ASIACRYPT 2011.Springer Berlin Heidelberg,2011:344-371.[DOI:10.1007/978-3-642-25385-0_19]
[9]CUI J Y,GUO J S,LIU Y P,et al.Biclique attack on CLEFIA-256[J].Journal of Information Engineering University,2017,18(3):322-327.[DOI:10.3969/j.issn.1671-0673.2017.03.013]崔竞一,郭建胜,刘翼鹏,等.CLEFIA-256算法的Biclique攻击[J].信息工程大学学报,2017,18(3):322-327.[DOI:10.3969/j.issn.1671-0673.2017.03.013]
[10]WANG Y,WU W,YU X,et al.Security on LBlock against Biclique cryptanalysis[C].In:Information Security Applications-WISA 2012.Springer Berlin Heidelberg,2012:1-14.[DOI:10.1007/978-3-642-35416-8_1]
[11]JEONG K,KANG H C,LEE C,et al.Biclique cryptanalysis of lightweight block ciphers PRESENT,Piccolo and LED[J].IACR Cryptology ePrint Archive,2012:2012/621.https://eprint.iacr.org/2012/621.
[12]GONG Z,LIU S S,WEN Y M,et al.Biclique analysis on the reduced-round PRESENT[J].Chinese Journal of Computers,2013,36(6):1139-1148.[DOI:10.3724/SP.J.1016.2013.01139]龚征,刘树生,温雅敏,等.缩减轮数PRESENT算法的Biclique分析[J].计算机学报,2013,36(6):1139-1148.[DOI:10.3724/SP.J.1016.2013.01139]
[13]YUAN Z,PENG Z.Biclique cryptanalysis of lightweight block cipher PRINCE[J].Journal of Cryptologic Research,2017,4(6):517-527.[DOI:10.13868/j.cnki.jcr.000203]袁征,彭真.轻量级分组密码PRINCE算法的Biclique分析[J].密码学报,2017,4(6):517-527.[DOI:10.13868/j.cnki.jcr.000203]
[14]LIU Y,CHENG L,LIU Z,et al.Improved meet-in-the-middle attacks on reduced-round Piccolo[J].Science China Information Sciences,2018,61(3):032108.[DOI:10.1007/s11432-016-9157-y]
[15]WANG Y,WU W,YU X.Biclique cryptanalysis of reduced-round Piccolo block cipher[C].In:Information Security Practice and Experience-ISPEC 2012.Springer Berlin Heidelberg,2012:337-352.[DOI:10.1007/978-3-642-29101-2_23]
[16]HAN G,ZHANG W.Improved Biclique cryptanalysis of the lightweight block cipher Piccolo[J].Security and Communication Networks,2017:7589306.[DOI:10.1155/2017/7589306]
[17]AHMADI S,AHMADIAN Z,MOHAJERI J,et al.Low-data complexity Biclique cryptanalysis of block ciphers with application to Piccolo and Hight[J].IEEE Transactions on Information Forensics and Security,2014,9(10):1641-1652.[DOI:10.1109/TIFS.2014.2344445]
[18]CUI J Y,GUO J S,LIU Y P.Generalized independent Biclique automated attack framework and its applications[J].Chinese Journal of Computers,2018,41(2):349-367.[DOI:10.11897/SP.J.1016.2018.00349]崔竞一,郭建胜,刘翼鹏.广义Independent Biclique攻击框架及其应用[J].计算机学报,2018,41(2):349-367.[DOI:10.11897/SP.J.1016.2018.00349]
[19]BOGDANOV A,CHANG D,GHOSH M,et al.Biclique with minimal data and time complexity for AES[C].In:Information Security and Cryptology-ICISC 2014.Springer Cham,2014:160-174.[DOI:10.1007/978-3-319-15943-0_10]
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |