基于分类搜索与快速变换的流密码攻击算法
|
摘要
提出了基于分类搜索、快速变换和最大似然译码(MLD)的快速相关攻击算法FCA-MLD-CS-FWT。在寻找校验方程时首次引入分类搜索策略;对校验方程引用快速Walsh变换;在译码阶段对线性反馈移位寄存器(LFSR)的状态分割,并采用MLD进行LFSR初态的破译。实验表明:该算法可在单核计算平台上将原始密钥长度为60的流密码破译时间缩短在1 h左右;通过静态字典的建立可实现不同参数校验方程的快速搜索;译码阶段时间复杂度由O(2~Bm)降低为O(2~BB+m)。
A fast correlation attack algorithm FCA-MLD-CS-FWT based on classification search,fast transformation and maximum likelihood decoding( MLD) is constructed. The classification search strategy is introduced for the first time in finding the checkout equation,and the fast Walsh transform is used for the check equation. In the decoding stage,the state of LFSR is segmented and MLD is used to decipher the initial state of LFSR. The experimental shows that FCAMLD-CS-FWT can shorten the decoding time of the stream cipher with the original key length of 60 on the single core computing platform for about 1 hours. Through the establishment of the static dictionary,the fast search for the calibration equation of different parameters can be realized; the time complexity of the decoding phase is reduced from O( 2~Bm) to O( 2~BB + m).
A fast correlation attack algorithm FCA-MLD-CS-FWT based on classification search,fast transformation and maximum likelihood decoding( MLD) is constructed. The classification search strategy is introduced for the first time in finding the checkout equation,and the fast Walsh transform is used for the check equation. In the decoding stage,the state of LFSR is segmented and MLD is used to decipher the initial state of LFSR. The experimental shows that FCAMLD-CS-FWT can shorten the decoding time of the stream cipher with the original key length of 60 on the single core computing platform for about 1 hours. Through the establishment of the static dictionary,the fast search for the calibration equation of different parameters can be realized; the time complexity of the decoding phase is reduced from O( 2~Bm) to O( 2~BB + m).
引文
[1] Upadhya D,Gandhi S. Randomness Evaluation of ZUC,SNOW and GRAIN Stream Ciphers[C]//Proceedings of International Conference on Communication and Networks. NY:IEEE,2017.
[2] Zhang B,Xu C,Meier W. Fast Correlation Attacks over Extension Fields,Large-Unit Linear Approximation and Cryptanalysis of SNOW2. 0[C]//Advances in Cryptology——CRYPTO 2015.[s. l.]:Springer Berlin Heidelberg,2015:643-662.
[3] Kim H R,Lee H J,Moon S J. A Security Enhancement of the E0Cipher in Bluetooth System[C]//Kes International Conference on Agent and Multi-Agent Systems:Technologies and Applications.[s.l.]:Springer-Verlag,2008:858-867.
[4] Zhang H N,Li L,Wang X Y. Fast correlation attack on stream cipher ABC v3[J]. Science China Information Sciences,2008,51(7):936-947.
[5] Ma Z,Qi W F,Tian T. On affine sub-families of the NFSR in Grain[J]. Designs Codes&Cryptography,2015,75(2):199-212.
[6] Yun J,Park K W,Shin Y,et al. An Efficient Stream Cipher for Resistive RAM[J]. IEICE Electronics Express,2017,14(7):1-6.
[7] Chakraborty A,Mukhopadhyay D. A Practical Template Attack on MICKEY-128 2. 0 Using PSO Generated IVs and LS-SVM[C]//International Conference on Vlsi Design and 2016, International Conference on Embedded Systems.[s. l.]:IEEE,2016:529-534.
[8] Hell M,Johansson T. Breaking the stream ciphers F-FCSR-H and FFCSR-16 in real time[J]. Journal of Cryptology,2011,24(3):427-445.
[9] Johansson T. Correlation attacks on stream ciphers and related decoding problems[M]. 1998.
[10] Agren M,Londahl C,Hell M,et al. A survey on fast correlation attacks[J]. Cryptography&Communications,2012,4(3-4):173-202.
[11] Chepyzhov V V,Johansson T,Smeets B. A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers[C]//International Workshop on Fast Software Encryption. Berlin:Springer,Heidelberg,2000:181-195.
[12] Molland H,Mathiassen J E,Helleseth T. Improved Fast Correlation Attack Using Low Rate Codes[C]//Cryptography and Coding,Ima International Conference,Cirencester. UK:Proceedings DBLP,2003:67-81.
[13]伍文君,唐贵林,黄芝平.一种快速相关攻击算法[J].计算机工程,2009,35(17):129-13.
[24]刘好莉,任义,杨晗.一种改进的CJS型快速相关攻击算法[J].电子技术与软件工程,2017(21):141.
[15] 2017年全国高校密码数学挑战赛之赛题二[EB/OL].(2017)[2018-5-25]. http://www. cmsecc. org/xiazai/.
[16]陈运.信息论与编码[M].北京:电子工业出版社,2016.
[17]田宝玉,杨洁,贺志强,等.信息论基础[M].北京:人民邮电出版社,2016.
[18] Noorkami M,Fekri F. A Fast Correlation Attack via Unequal Error Correcting LDPC Codes[J]. Lecture Notes in Computer Science,2004,2964:54-66.
[2] Zhang B,Xu C,Meier W. Fast Correlation Attacks over Extension Fields,Large-Unit Linear Approximation and Cryptanalysis of SNOW2. 0[C]//Advances in Cryptology——CRYPTO 2015.[s. l.]:Springer Berlin Heidelberg,2015:643-662.
[3] Kim H R,Lee H J,Moon S J. A Security Enhancement of the E0Cipher in Bluetooth System[C]//Kes International Conference on Agent and Multi-Agent Systems:Technologies and Applications.[s.l.]:Springer-Verlag,2008:858-867.
[4] Zhang H N,Li L,Wang X Y. Fast correlation attack on stream cipher ABC v3[J]. Science China Information Sciences,2008,51(7):936-947.
[5] Ma Z,Qi W F,Tian T. On affine sub-families of the NFSR in Grain[J]. Designs Codes&Cryptography,2015,75(2):199-212.
[6] Yun J,Park K W,Shin Y,et al. An Efficient Stream Cipher for Resistive RAM[J]. IEICE Electronics Express,2017,14(7):1-6.
[7] Chakraborty A,Mukhopadhyay D. A Practical Template Attack on MICKEY-128 2. 0 Using PSO Generated IVs and LS-SVM[C]//International Conference on Vlsi Design and 2016, International Conference on Embedded Systems.[s. l.]:IEEE,2016:529-534.
[8] Hell M,Johansson T. Breaking the stream ciphers F-FCSR-H and FFCSR-16 in real time[J]. Journal of Cryptology,2011,24(3):427-445.
[9] Johansson T. Correlation attacks on stream ciphers and related decoding problems[M]. 1998.
[10] Agren M,Londahl C,Hell M,et al. A survey on fast correlation attacks[J]. Cryptography&Communications,2012,4(3-4):173-202.
[11] Chepyzhov V V,Johansson T,Smeets B. A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers[C]//International Workshop on Fast Software Encryption. Berlin:Springer,Heidelberg,2000:181-195.
[12] Molland H,Mathiassen J E,Helleseth T. Improved Fast Correlation Attack Using Low Rate Codes[C]//Cryptography and Coding,Ima International Conference,Cirencester. UK:Proceedings DBLP,2003:67-81.
[13]伍文君,唐贵林,黄芝平.一种快速相关攻击算法[J].计算机工程,2009,35(17):129-13.
[24]刘好莉,任义,杨晗.一种改进的CJS型快速相关攻击算法[J].电子技术与软件工程,2017(21):141.
[15] 2017年全国高校密码数学挑战赛之赛题二[EB/OL].(2017)[2018-5-25]. http://www. cmsecc. org/xiazai/.
[16]陈运.信息论与编码[M].北京:电子工业出版社,2016.
[17]田宝玉,杨洁,贺志强,等.信息论基础[M].北京:人民邮电出版社,2016.
[18] Noorkami M,Fekri F. A Fast Correlation Attack via Unequal Error Correcting LDPC Codes[J]. Lecture Notes in Computer Science,2004,2964:54-66.