More Web Proxy on the site http://driver.im/

Article

Exploiting Multiples of the Connection Polynomial in Word-Oriented Stream Ciphers

Authors:

Gregory G. RoseAuthors Info & Claims

ASIACRYPT '00: Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology

Pages 303 - 316

Published: 03 December 2000 Publication History

Abstract

This paper describes some attacks on word-oriented stream ciphers that use a linear feedback shift register (LFSR) and a non-linear filter. These attacks rely on exploiting linear relationships corresponding to multiples of the connection polynomial that define the LFSR.

References

[1]

S. Blackburn, S. Murphy, F. Piper, and P. Wild. A SOBERing remark. Technical report, Information Security Group, Royal Holloway University of London, Egham, Surrey TW20 0EX, U.K., 1998.

[2]

D. Bleichenbacher, W. Meier, and S. Patel. Analysis of the SOBER stream cipher. Technical Report TR45.AHAG.08.30.12, TR45 Ad Hoc Authentication Group, 1999.

[3]

D. Bleichenbacher and S. Patel. SOBER cryptanalysis. Fast Software Encryption, FSE'99 Lecture Notes in Computer Science, vol. 1636, L. Knudsen ed., Springer-Verlag , pages 305-316, 1999.

[4]

V. Chepyzhov and B. Smeets. On a fast correlation attack on certain stream ciphers. Advances in Cryptology, EUROCRYPT'91, Lecture Notes in Computer Science, vol. 547, D. W. Davies ed., Springer-Verlag, pages 176-185, 1991.

[5]

J. Golic, A. Clark, and E. Dawson. Inversion attack and branching. Information Security and Privacy, Fourth Australasian Conference, ACISP'99, Lecture Notes in Computer Science, vol. 1587, J. Pieprzyk, R Safavi-Naini, J. Seberry eds., Springer-Verlag, pages 88-102, 1999.

[6]

J. Dj. Golic. On the security of nonlinear filter generators. Fast Software Encryption, Lecture Notes in Computer Science, vol. 1039, D. Gollmann ed., Springer, pages 173-188, 1995.

[7]

P. Hawkes. An attack on SOBER-II. Technical report, QUALCOMM Australia, Suite 410, Birkenhead Point, Drummoyne NSW 2137, Australia, 1999.

[8]

P. Hawkes and G. Rose. The t-class of SOBER stream ciphers. Technical report, QUALCOMM Australia, Suite 410, Birkenhead Point, Drummoyne NSW 2137, Australia, 1999. See http://www.home.aone.net.au/qualcomm.

[9]

T. Herlestam. On functions of Linear Shift Register Sequences. Advances in Cryptology, EUROCRYPT'85, Lecture Notes in Computer Science, vol. 219, F. Pichler ed., Springer-Verlag, 1986.

[10]

T. Johansson and F Jönsson. Improved fast correlation attacks on stream ciphers via convolutional codes. Advances in Cryptology, EUROCRYPT'99, Lecture Notes in Computer Science, vol. 1592, J. Stern ed., Springer-Verlag, pages 347-362, 1999.

[11]

B. Löhlein. Analysis and modifications of the conditional correlation attack. 1999. Accepted at 3rd IEEE/ITG Conference on Source and Channel Coding, 17-19 Jan. 2000, Munich.

[12]

G. Rose. S32: A fast stream cipher based on linear feedback over GF(2³²). Technical report, QUALCOMM Australia, Suite 410, Birkenhead Point, Drummoyne NSW 2137, Australia, 1998.

[13]

G. Rose. SOBER: A stream cipher based on linear feedback over GF(2⁸). Technical report, QUALCOMM Australia, Suite 410, Birkenhead Point, Drummoyne NSW 2137, Australia, 1998. See http://www.home.aone.net.au/qualcomm.

[14]

G. Rose. A stream cipher based on linear feedback over GF(2⁸). Information Security and Privacy, Third Australasian Conference, ACISP'98, Lecture Notes in Computer Science, vol. 1438, C. Boyd, E. Dawson eds., Springer-Verlag, pages 135-146, 1998.

[15]

M. Zhang, C. Carroll, and A. Chan. SSC. Technical Report TR45.AHAG.99.02.09.15, TR45 Ad Hoc Authentication Group, 1999.

[16]

M. Zhang, C. Carroll, and A. Chan. The software-oriented stream cipher SSC-II. In Proceedings of Fast Software Encryption Workshop 2000, pages 39-56, 2000.

Cited By

Verstegen AVerdult RBokslag WRossow CYounan Y(2018)Hitag 2 hell - brutally optimizing guess-and-determine attacksProceedings of the 12th USENIX Conference on Offensive Technologies10.5555/3307423.3307437(14-14)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.5555/3307423.3307437
Duval SLallemand VRotella Y(2016)Cryptanalysis of the FLIP Family of Stream CiphersProceedings, Part I, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 981410.1007/978-3-662-53018-4_17(457-475)Online publication date: 14-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-53018-4_17
Meier W(2011)Fast correlation attacksProceedings of the 18th international conference on Fast software encryption10.5555/2022159.2022165(55-67)Online publication date: 13-Feb-2011
https://dl.acm.org/doi/10.5555/2022159.2022165
Show More Cited By

Recommendations

Digest Ciphers, Stream Digests, and Winnowing Stream Ciphers
The Salsa20 Family of Stream Ciphers
New Stream Cipher Designs

Salsa20 is a family of 256-bit stream ciphers designed in 2005 and submitted to eSTREAM, the ECRYPT Stream Cipher Project. Salsa20 has progressed to the third round of eSTREAM without any changes. The 20-round stream cipher Salsa20/20 is consistently ...
Cryptanalysis of WG-8 and WG-16 stream ciphers

In 2008, the WG family of stream ciphers was designed by Navaz and Gong to secure lightweight applications for RFIDs and smart cards. In 2012, a distinguishing attack was discovered against the WG-7 stream cipher by Orumiehchiha, Pieprzyk and Steinfeld. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ASIACRYPT '00: Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology

December 2000

627 pages

ISBN:3540414045

Editor:
Tatsuaki Okamoto

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 December 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Verstegen AVerdult RBokslag WRossow CYounan Y(2018)Hitag 2 hell - brutally optimizing guess-and-determine attacksProceedings of the 12th USENIX Conference on Offensive Technologies10.5555/3307423.3307437(14-14)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.5555/3307423.3307437
Duval SLallemand VRotella Y(2016)Cryptanalysis of the FLIP Family of Stream CiphersProceedings, Part I, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 981410.1007/978-3-662-53018-4_17(457-475)Online publication date: 14-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-53018-4_17
Meier W(2011)Fast correlation attacksProceedings of the 18th international conference on Fast software encryption10.5555/2022159.2022165(55-67)Online publication date: 13-Feb-2011
https://dl.acm.org/doi/10.5555/2022159.2022165
Gao ZFu F(2009)The minimal polynomial over Fq of linear recurring sequence over FqmFinite Fields and Their Applications10.1016/j.ffa.2009.07.00215:6(774-784)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.ffa.2009.07.002
Meidl WÖZbudak F(2009)Linear complexity over F q and over Fqm for linear recurring sequencesFinite Fields and Their Applications10.1016/j.ffa.2008.09.00415:1(110-124)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1016/j.ffa.2008.09.004
Ohigashi TShiraishi YMorii M(2008)New Weakness in the Key-Scheduling Algorithm of RC4IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1093/ietfec/e91-a.1.3E91-A:1(3-11)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1093/ietfec/e91-a.1.3
Wang LNiederreiter H(2008)Successive minima profile, lattice profile, and joint linear complexity profile of pseudorandom multisequencesJournal of Complexity10.1016/j.jco.2007.07.00124:2(144-153)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.jco.2007.07.001
Wang L(2008)Lattice basis reduction algorithms and multi-dimensional continued fractionsFinite Fields and Their Applications10.1016/j.ffa.2008.05.00814:4(979-991)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1016/j.ffa.2008.05.008
Niederreiter HVenkateswarlu A(2008)Periodic multisequences with large error linear complexityDesigns, Codes and Cryptography10.1007/s10623-008-9174-x49:1-3(33-45)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1007/s10623-008-9174-x
Wang L(2008)A Lattice-Based Minimal Partial Realization AlgorithmProceedings of the 5th international conference on Sequences and Their Applications10.1007/978-3-540-85912-3_25(278-289)Online publication date: 14-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85912-3_25
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents