NDLI: Improving algebraic attacks on stream ciphers based on linear feedback shift register over $$\mathbb {F}

Content Provider	Springer Nature Link
Author	Rønjom, Sondre
Copyright Year	2016
Abstract	In this paper we investigate univariate algebraic attacks on filter generators over extension fields $$\mathbb {F}_q=\mathbb {F}_{2^n}$$ with focus on the Welch–Gong (WG) family of stream ciphers. Our main contribution is to reduce the general algebraic attack complexity on such cipher by proving new and lower bounds for the spectral immunity of such ciphers. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the minimum number of nonzero coefficients of a multiple of a univariate polynomial. In particular, there is an algebraic degeneracy in these constructions, which, when combined with attacks based on low-weight multiples over $$\mathbb {F}_q$$ , provides much more efficient attacks than over $$\mathbb {F}_2$$ . With negligible computational complexity, our best attack breaks the primitive WG-5 if given access to 4 kilobytes of keystream, break WG-7 if given access to 16 kilobytes of keystream and break WG-8 if given access to half a megabyte of keystream. Our best attack on WG-16 targeted at 4G-LTE is less practical, and requires $$2^{103}$$ computational complexity and $$2^{61}$$ bits of keystream. In all instances, we significantly lower both keystream and computational complexity in comparison to previous estimates. On a side note, we resolve an open problem regarding the rank of a type of equation systems used in algebraic attacks.
Ending Page	41
Page Count	15
Starting Page	27
File Format	PDF
ISSN	09251022
e-ISSN	15737586
Journal	Designs, Codes and Cryptography
Issue Number	1-2
Volume Number	82
Language	English
Publisher	Springer US
Publisher Date	2016-05-05
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Information and Communication, Circuits Data Structures, Cryptology and Information Theory Algebraic attacks Data encryption Spectral immunity Discrete Mathematics in Computer Science Data Encryption Algebraic coding theory; cryptography Coding and Information Theory Cryptography Combinatorics Applications to coding theory and cryptography
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Algebraic attacks on a class of stream ciphers with unknown output function

On extended algebraic immunity

On the number of irreducible linear transformation shift registers

On affine sub-families of the NFSR in Grain

On the largest affine sub-families of a family of NFSR sequences

On the spectral immunity of periodic sequences restricted to binary annihilators

Enumeration of linear transformation shift registers

On the k-error linear complexity over $$\mathbb{F}_p$$ of Legendre and Sidelnikov sequences

Primitive polynomials, singer cycles and word-oriented linear feedback shift registers

Improving algebraic attacks on stream ciphers based on linear feedback shift register over $$\mathbb {F}_{2^k}$$

Similar Documents

Algebraic attacks on a class of stream ciphers with unknown output function

On extended algebraic immunity

On the number of irreducible linear transformation shift registers

On affine sub-families of the NFSR in Grain

On the largest affine sub-families of a family of NFSR sequences

On the spectral immunity of periodic sequences restricted to binary annihilators

Enumeration of linear transformation shift registers

On the k-error linear complexity over $$\mathbb{F}_p$$ of Legendre and Sidelnikov sequences

Primitive polynomials, singer cycles and word-oriented linear feedback shift registers

Improving algebraic attacks on stream ciphers based on linear feedback shift register over $$\mathbb {F}_{2^k}$$