Algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering

Joo Yeon Cho, Josef Pieprzyk

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

Abstract

This paper presents algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering. For unstuttered SOBER-t32, two different attacks are implemented. In the first attack, we obtain multivariate equations of degree 10. Then, an algebraic attack is developed using a collection of output bits whose relation to the initial state of the LFSR can be described by low-degree equations. The resulting system of equations contains 269 equations and monomials, which can be solved using the Gaussian elimination with the complexity of 2196.5. For the second attack, we build a multivariate equation of degree 14. We focus on the property of the equation that the monomials which are combined with output bit are linear. By applying the Berlekamp-Massey algorithm, we can obtain a system of linear equations and the initial states of the LFSR can be recovered. The complexity of attack is around O(2100) with 292 keystream observations. The second algebraic attack is applicable to SOBER-t16 without stuttering. The attack takes around O(285) CPU clocks with 278 keystream observations.

Original languageEnglish
Pages (from-to)49-64
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3017
Publication statusPublished - 2004

Fingerprint

Dive into the research topics of 'Algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering'. Together they form a unique fingerprint.

Cite this