SIMON不可能差分及零相关路径自动化搜索算法
|
摘要
对于分组密码,不可能差分和零相关线性分析都是很重要的分析手段.通过研究非线性组件与(AND)的性质,首先得到用于刻画SIMON轮函数差分及线性传播特性的约束式,再基于布尔可满足约束问题(SAT),提出一种普适性不可能差分和零相关路径自动化搜索算法,并利用该算法搜索得到SIMON更多的不可能差分及零相关路径.除用于自动化搜索外,该算法还可判断特定的差分对(掩码对)是否能构成一条有效不可能差分和零相关路径.此外,基于该算法,从抵抗不可能差分攻击的角度出发,给出SIMON轮函数设计中循环移位常数的选取依据.
Impossible differential cryptanalysis and zero-correlation linear cryptanalysis are two of the most useful cryptanalysis methods in the field of symmetric ciphers. Taking the non-linear components into consideration, this article proposes a method for searching the impossible differentials and zero-correlation linear approximations of SIMON based on a technique of SAT. In applications, the proposed method is used to find more impossible differentials and zero-correlation linear approximations for 11-round SIMON. Furthermore, this tool can be used to prove whether there are impossible differentials(zero-correlation linear approximations) in certain rounds of SIMON, particularly for certain subset of input and output patterns of differences(masks). Utilizing this tool, the security of SIMON as well as the choice of its parameter set when resisting the impossible differential cryptanalysis are also explored.
Impossible differential cryptanalysis and zero-correlation linear cryptanalysis are two of the most useful cryptanalysis methods in the field of symmetric ciphers. Taking the non-linear components into consideration, this article proposes a method for searching the impossible differentials and zero-correlation linear approximations of SIMON based on a technique of SAT. In applications, the proposed method is used to find more impossible differentials and zero-correlation linear approximations for 11-round SIMON. Furthermore, this tool can be used to prove whether there are impossible differentials(zero-correlation linear approximations) in certain rounds of SIMON, particularly for certain subset of input and output patterns of differences(masks). Utilizing this tool, the security of SIMON as well as the choice of its parameter set when resisting the impossible differential cryptanalysis are also explored.
引文
[1]Bogdanov A,Knudsen LR,Leander G,Paar C,Poschmann A,Robshaw MJB,Seurin Y,Vikkelsoe C.PRESENT:An ultralightweight block cipher.In:Proc.of the CHES 2007.LNCS 4727,Berlin:Springer-Verlag,2007.350-466.
[2]Borghoff J,Canteaut A,Gneysu T,Lender G,et al.PRINCE-A low-latency block cipher for pervasive computing applications:Extended abstract.In:Proc.of the ASIACRYPT 2012.LNCS 7658,Berlin:Springer-Verlag,2012.208-225.
[3]De Canniére C,Dunkelman O,Knezevic M.KATAN and KTANTAN:A family of small and efficient hardware-oriented block ciphers.In:Proc.of the CHES 2009.LNCS 5747,Berlin:Springer-Verlag,2009.272-288.
[4]Albrecht MR,Driessen B,Kavun EB,Leander G,Paar C,Yalcn T,et al.Block ciphers-focus on the linear layer(feat.PRIDE).In:Proc.of the CRYPTO 2014.LNCS 8616,Berlin:Springer-Verlag,2014.57-76.
[5]Beaulieu R,Shors D,Smith J,Clark ST,Weeks B,Wingers L.The SIMON and SPECK families of lightweight block ciphers.Technical Report,2013/404,2013.
[6]Abed F,List E,Lucks S,Wenzel J.Differential and linear cryptanalysis of reduced-round SIMON.Technical Report,526,2013.
[7]Alkhzaimi H,Lauridsen M.Cryptanalysis of the SIMON family of block ciphers.Technical Report,543,2013.
[8]Alizadeh J,Bagheri N,Gauravaram P,Kumar A,Sanadhya SK.Linear cryptanalysis of round reduced SIMON.Technical Report,663,2013.
[9]Abed F,List E,Lucks S,Wenzel J.Cryptanalysis of the SPECK family of block ciphers.Technical Report,568,2013.
[10]Abed F,List E,Lucks S,Wenzel J.Differential cryptanalysis of round-reduced SIMON and SPECK.In:Proc.of the FSE 2014.LNCS 8540,Berlin:Springer-Verlag,2014.525-545.
[11]Biryukov A,Roy A,Velichkov V.Differential analysis of block ciphers SIMON and SPECK.In:Proc.of the FSE 2014.LNCS8540,Berlin:Springer-Verlag,2014.546-570.
[12]Yu XL,Wu WL,Shi ZQ,Member S,Shi ZQ,Zhang J,Zhang L,Wang YF.Zero-Correlation linear cryptanalysis of reduced-round SIMON.Journal of Computer Science and Technology,2015,30(6):1358-1369.
[13]K?bl S,Leander G,Tiessen T.Observations on the SIMON block cipher family.In:Proc.of the CRYPTO 2015.LNCS 9215,Berlin:Springer-Verlag,2015.161-185.
[14]Biham E,Biryukov A,Shamir A.Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials.In:Proc.of the EUROCRYPT’99.Berlin,Heidelberg:Springer-Verlag,1999.12-23.
[15]FIPS PUB 197.Announcing the Advanced Encryption Standard(AES).Washington:National Institute of Standards and Technology,2001.
[16]Matsui M.New block encryption algorithm MISTY.In:Proc.of the FSE’97.LNCS 1267,Berlin:Springer-Verlag,1997.64-67.
[17]Bogdanov A,Rijmen V.Linear hulls with correlation zero and linear cryptanalysis of block ciphers.Designs,Codes and Cryptography,2014,70(3):369-383.
[18]Kim J,Hong S,Lim J.Impossible differential cryptanalysis using matrix method.Discrete Mathematics,2010,310(5):988-1002.
[19]Luo YY,Lai XJ,Wu ZM,Gong G.A unified method for finding impossible differentials of block cipher structures.Information Sciences,2014,263(1):211-220.
[20]Cui TT,Jia KT,Fu K,Chen SY,Wang MQ.New automatic search tool for impossible differentials and zero-correlation linear approximations.IACR Cryptology ePrint Archive,2016.https://eprint.iacr.org/2016/689.pdf
[21]Wang QJ,Liu ZQ,Varici K,Sasaki Y,Rijmen V,Yosuke T.Cryptanalysis of reduced-round SIMON32 and SIMON48.In:Proc.of the INDOCRYPT 2014.LNCS 8885,Berlin:Springer-Verlag,2014.143-160.
[2]Borghoff J,Canteaut A,Gneysu T,Lender G,et al.PRINCE-A low-latency block cipher for pervasive computing applications:Extended abstract.In:Proc.of the ASIACRYPT 2012.LNCS 7658,Berlin:Springer-Verlag,2012.208-225.
[3]De Canniére C,Dunkelman O,Knezevic M.KATAN and KTANTAN:A family of small and efficient hardware-oriented block ciphers.In:Proc.of the CHES 2009.LNCS 5747,Berlin:Springer-Verlag,2009.272-288.
[4]Albrecht MR,Driessen B,Kavun EB,Leander G,Paar C,Yalcn T,et al.Block ciphers-focus on the linear layer(feat.PRIDE).In:Proc.of the CRYPTO 2014.LNCS 8616,Berlin:Springer-Verlag,2014.57-76.
[5]Beaulieu R,Shors D,Smith J,Clark ST,Weeks B,Wingers L.The SIMON and SPECK families of lightweight block ciphers.Technical Report,2013/404,2013.
[6]Abed F,List E,Lucks S,Wenzel J.Differential and linear cryptanalysis of reduced-round SIMON.Technical Report,526,2013.
[7]Alkhzaimi H,Lauridsen M.Cryptanalysis of the SIMON family of block ciphers.Technical Report,543,2013.
[8]Alizadeh J,Bagheri N,Gauravaram P,Kumar A,Sanadhya SK.Linear cryptanalysis of round reduced SIMON.Technical Report,663,2013.
[9]Abed F,List E,Lucks S,Wenzel J.Cryptanalysis of the SPECK family of block ciphers.Technical Report,568,2013.
[10]Abed F,List E,Lucks S,Wenzel J.Differential cryptanalysis of round-reduced SIMON and SPECK.In:Proc.of the FSE 2014.LNCS 8540,Berlin:Springer-Verlag,2014.525-545.
[11]Biryukov A,Roy A,Velichkov V.Differential analysis of block ciphers SIMON and SPECK.In:Proc.of the FSE 2014.LNCS8540,Berlin:Springer-Verlag,2014.546-570.
[12]Yu XL,Wu WL,Shi ZQ,Member S,Shi ZQ,Zhang J,Zhang L,Wang YF.Zero-Correlation linear cryptanalysis of reduced-round SIMON.Journal of Computer Science and Technology,2015,30(6):1358-1369.
[13]K?bl S,Leander G,Tiessen T.Observations on the SIMON block cipher family.In:Proc.of the CRYPTO 2015.LNCS 9215,Berlin:Springer-Verlag,2015.161-185.
[14]Biham E,Biryukov A,Shamir A.Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials.In:Proc.of the EUROCRYPT’99.Berlin,Heidelberg:Springer-Verlag,1999.12-23.
[15]FIPS PUB 197.Announcing the Advanced Encryption Standard(AES).Washington:National Institute of Standards and Technology,2001.
[16]Matsui M.New block encryption algorithm MISTY.In:Proc.of the FSE’97.LNCS 1267,Berlin:Springer-Verlag,1997.64-67.
[17]Bogdanov A,Rijmen V.Linear hulls with correlation zero and linear cryptanalysis of block ciphers.Designs,Codes and Cryptography,2014,70(3):369-383.
[18]Kim J,Hong S,Lim J.Impossible differential cryptanalysis using matrix method.Discrete Mathematics,2010,310(5):988-1002.
[19]Luo YY,Lai XJ,Wu ZM,Gong G.A unified method for finding impossible differentials of block cipher structures.Information Sciences,2014,263(1):211-220.
[20]Cui TT,Jia KT,Fu K,Chen SY,Wang MQ.New automatic search tool for impossible differentials and zero-correlation linear approximations.IACR Cryptology ePrint Archive,2016.https://eprint.iacr.org/2016/689.pdf
[21]Wang QJ,Liu ZQ,Varici K,Sasaki Y,Rijmen V,Yosuke T.Cryptanalysis of reduced-round SIMON32 and SIMON48.In:Proc.of the INDOCRYPT 2014.LNCS 8885,Berlin:Springer-Verlag,2014.143-160.