对广义自缩生成器的区分攻击

doi:10.3969/j.issn.1001-2400.2012.04.021

Abstract

Abstract:

With simple construction and easy implementation, the generalized self-shrinking generator is a keystream generator intended to be used as a stream cipher. This paper investigates the security of the generalized self-shrinking generator. We propose two distinguishing attacks on the generalized self-shrinking sequences by using the feedback polynomial and the sequence v. The results show that the attacker can launch a distinguishing attack by choosing the h^w-1 keystream bit of the generalized self-shrinking generator, if the feedback polynomial f(x) is of hamming weight w and degree h. On the other hand, if the hamming weight of f(x) is low, then the attacker can launch a distinguishing attack, and the attack complexity depends on the weight of f(x). Therefore, neither type of the polynomials can be chosen as the feedback polynomials of the generalized self-shrinking generator. Users should choose the feedback polynomial carefully, otherwise the stream cipher can suffer from distinguishing attacks.

Key words: cryptography, generalized self-shrinking generators, distinguishing attacks, linear feedback shift registers, polynomials

CLC Number:

T N918. 1

LI Xuelian;GAO Juntao;HU Yupu;ZHANG Fengrong. Distinguishing attacks on generalized self-shrinking generators[J].J4, 2012, 39(4): 114-119.

References

［1］ Coppersmith D, Krawczyk H, Mansour Y. The Shrinking Generator［C］//Advanced in Cryptology-CRYPT'93: LNCS 765. Berlin: Springer-Verlag, 1994: 22-39.
［2］ Meier W, Staffelbach O. The Self-Shrinking Generator ［C］//Advanced in Cryptology-Eurocrypt'94: LNCS 905. Berlin: Springer-Verlag, 1994: 205-214.
［3］ Kanso A. Modified Self-shrinking Generator［J］. Computers ＆ Electrical Engineering, 2010, 36(5): 993-1001.
［4］ Hu Yupu, Xiao Guozhen. The Generalized Self-shrinking Generator［J］. IEEE Trans on Information Theory, 2004, 50(4): 714-719.
［5］ Fuster-Sabater A, Caballero-Gil P. Analysis of the Generalized Self-shrinking Generator［J］. Computers ＆ Mathematics with Applications, 2011, 61(4): 871-880.
［6］ Zhang Bin, Wu Hongjun, Feng Dengguo, et al. Security Analysis of the Generalized Self-shrinking Generator［C］//ICICS'04: LNCS 3269. Berlin: Springer-Verlag, 2004: 388-400.
［7］ Hell M, Johansson T, Brynielsson L. An Overview of Distinguishing Attacks on Stream Ciphers［J］. Cryptography and Communications, 2009, 1(1): 71-94.
［8］ Meier W, Staffelbach O. Fast Correlation Attacks on Stream Ciphers［C］//Advanced in Cryptology-Eurocrypt'88: LNCS330. Berlin: Springer-Verlag, 1994: 310-314.
［9］ Du Yusong, Pei Dingyi. Construction of Boolean Functions with Maximum Algebraic Immunity and Count of Their Annihilators at Lowest Degree［J］. Science China: Information Sciences, 2010, 53(4): 780-787.
［10］刘福运, 肖鸿, 肖国镇. 一种代数正规形快速变换的零化子算法［J］. 西安电子科技大学学报, 2009, 36(5): 890-895.
Liu Fuyun, Xiao Hong, Xiao Guozhen. Research on Finding Annihilators of Boolean Functions Based the Algebraic Normal Form Fast Transformations［J］. Journal of Xidian University, 2009, 36(5): 890-895.
［11］ Hell M, Johansson T. Some Attacks on the Bit-Search Generator［C］//Fast Software Encryption, 12th International Workshop, FSE 2005: LNCS 3557. Berlin: Springer-Verlag, 2005: 215-227.
［12］ McEliece R J. Finite Field for Computer Scientists and Engineers［M］. Massachusetts: Kluwer Academic Publishers, 1987.
［13］ Golic' J D. Computation of Low-Weight Parity Check Polynomials［J］. Electronic Letters, 1996, 32(21): 1981-1982.

[1]	ZENG Yong,WU Zhengyuan,DONG Lihua,LIU Zhihong,MA Jianfeng,LI Zan. Research on malicious traffic identification technology in encrypted traffic [J]. Journal of Xidian University, 2021, 48(3): 170-187.
[2]	DONG Xinfeng,ZHANG Wenzheng,XU Chunxiang. 8 bits lightweight S-box with the Feistel structure [J]. Journal of Xidian University, 2021, 48(1): 69-75.
[3]	GUO Songge;LV Donghui;REN Yanli. Improved (k, n) tagged visual cryptography scheme [J]. Journal of Xidian University, 2018, 45(5): 170-176+183.
[4]	SHEN Dongsu;MA Wenping;YIN Xunru;WANG Lili. Improvement of a two-party quantum key agreement protocol [J]. J4, 2015, 42(1): 86-90+186.
[5]	JIANG Mingming;HU Yupu;WANG Baocang;LIU Zhenhua;LAI Qiqi. Proxy re-signature scheme over the lattice [J]. J4, 2014, 41(2): 20-24.
[6]	YANG Xiaowei;GAN Lu. Fast blind estimation algorithm for Hamming codes parameters [J]. J4, 2013, 40(5): 60-65.
[7]	ZHAO Yongbin;HU Yupu;JIA Yanyan. New design of LFSR based stream ciphers to resist power attack [J]. J4, 2013, 40(3): 172-179+200.
[8]	LIU Dongsu;MIAO Meixia;MA Hua;LIN Ruibin;TIAN Haibo. Digital anti-counterfeiting scheme based on key-exposure free chameleon signature [J]. J4, 2012, 39(5): 24-29.
[9]	SUN Jin;HU Yupu. Fully secure attribute-based broadcast encryption [J]. J4, 2012, 39(4): 23-28+154.
[10]	XIAO Hong;WANG Hong;MA Runnian;CUI Jie. Provably secure threshold FFS signature scheme in the random oracle model [J]. J4, 2011, 38(6): 130-133+151.
[11]	ZHANG Yinghui；LI Hui；MA Hua. Free protocol for the subliminal channels in the Schnorr-type ordinal multi-signature schemes [J]. J4, 2011, 38(3): 140-144.
[12]	HE Ye-feng;MA Wen-ping. One class of highly nonlinear cryptographic functions [J]. J4, 2010, 37(6): 1107-1110.
[13]	QIU Gang;WANG Hong;XIAO Hong;XIAO Guo-zhen. Security analysis of two forward-secure blind signature schemes [J]. J4, 2010, 37(1): 107-112+147.
[14]	LI Xue-yuan;WANG Xin-mei. Generalized tweakable enciphering schemes [J]. J4, 2009, 36(4): 686-690.
[15]	ZHANG Chuan-rong;ZHANG Yu-qing. Provable security signcryption scheme and its hybrid construction [J]. J4, 2009, 36(4): 756-760.

Distinguishing attacks on generalized self-shrinking generators

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0