simonfischer.ch

Science

Choose
thesis
papers
software

Last update: January 2013

Contact form

×
title

Analysis of Lightweight Stream Ciphers.

author

Simon Fischer.

examining committee

Prof. M. A. Shokrollahi, Prof. S. Vaudenay, Prof. C. Carlet, Prof. A. Lenstra, Dr M. Robshaw.

abstract

Stream ciphers are fast cryptographic primitives to provide confidentiality of electronically transmitted data. They can be very suitable in environments with restricted resources, such as mobile devices or embedded systems. Practical examples are cell phones, RFID transponders, smart cards or devices in sensor networks. Besides efficiency, security is the most important property of a stream cipher. In this thesis, we address cryptanalysis of modern lightweight stream ciphers. We derive and improve cryptanalytic methods for different building blocks and present dedicated attacks on specific proposals, including some eSTREAM candidates. As a result, we elaborate on the design criteria for the development of secure and efficient stream ciphers. The best-known building block is the linear feedback shift register (LFSR), which can be combined with a nonlinear Boolean output function. A powerful type of attacks against LFSR-based stream ciphers are the recent algebraic attacks, these exploit the specific structure by deriving low degree equations for recovering the secret key. We efficiently determine the immunity of existing and newly constructed Boolean functions against fast algebraic attacks. The concept of algebraic immunity is then generalized by investigating the augmented function of the stream cipher. As an application of this framework, we improve the cryptanalysis of a well-known stream cipher with irregularly clocked LFSR's. Algebraic attacks can be avoided by substituting the LFSR with a suitable nonlinear driving device, such as a feedback shift register with carry (FCSR) or the recently proposed class of T-functions. We investigate both replacement schemes in view of their security, and devise different practical attacks (including linear attacks) on a number of specific proposals based on T-functions. Another efficient method to amplify the nonlinear behavior is to use a round-based filter function, where each round consists of simple nonlinear operations. We use differential methods to break a reduced-round version of eSTREAM candidate Salsa20. Similar methods can be used to break a related compression function with a reduced number of rounds. Finally, we investigate the algebraic structure of the initialization function of stream ciphers and provide a framework for key recovery attacks. As an application, a key recovery attack on simplified versions of eSTREAM candidates Trivium and Grain-128 is given.

resources and links

[thesis] - [slides] - [EPFL library] - [homepage S. Vaudenay] - [homepage W. Meier]

×
title

Akkretion und Gasströmung.

author

Simon Künzli.

supervisor

Prof. W. Benz.

abstract

In the process of planetary formation, growth of meter-sized bodies is not well understood. Since surface forces are no longer effective and gravity is still much too weak, two body collisions result in fragmentation rather than growth. Wurm et al. have recently proposed a new mechanism in planetesimal formation. The nebular gas flow may drag ejected dust grains back to the parent body, and after one or more inelastic bounces, the grains will have reduced their velocity and be accreted. We investigate the importance of this aerodynamical accretion for planetesimal growth in the protosolar nebula with the aid of a Monte-Carlo model. Our computational results show that gas flow provides accretion only in a very restricted parameter space. Within our model assumptions, we consider aerodynamical accretion not as a dominant growth mechanism for meter-sized bodies in the protosolar nebula.

resources and links

[paper] - [mpeg animation]

×
title

Some remarks on FCSRs and implications for stream ciphers.

authors

Simon Fischer, Willi Meier, and Dirk Stegemann.

publication

Journal of Mathematical Cryptology. Volume 3, Issue 3, Pages 227–236.

abstract

Feedback with carry shift registers (FCSRs) are extensively discussed in the context of pseudorandom number generation and as building blocks for stream ciphers. Similarly to linear feedback shift registers, FCSRs may be represented in Galois and in Fibonacci architecture. We describe the first formal characterization of periodic Galois states and show an efficient mapping between periodic Galois states and periodic Fibonacci states. Additionally we provide a method for explicitly computing the autocorrelation of maximum-period FCSR sequences and discuss the impact of our findings on the design of FCSR-based stream ciphers.

resources and links

[link to paper]

×
title

Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers.

authors

Simon Fischer, Shahram Khazaei, and Willi Meier.

publication

In S. Vaudenay, editor, Progress in Cryptology - AFRICACRYPT 2008, First International Conference on Cryptology in Africa, Casablanca, Morocco, June 11-14, 2008. Proceedings, volume 5023 of Lecture Notes in Computer Science, pages 236-245. Springer-Verlag, 2008.

Also in SASC 2008 - The State of the Art of Stream Ciphers, Lausanne, Switzerland, February 13-14, 2008. Workshop record, pages 33-42.

abstract

A recent framework for chosen IV statistical distinguishing analysis of stream ciphers is exploited and formalized to provide new methods for key recovery attacks. As an application, a key recovery attack on simplified versions of two eSTREAM Phase 3 candidates is given: For Grain-128 with IV initialization reduced to up to 180 of its 256 iterations, and for Trivium with IV initialization reduced to up to 672 of its 1152 iterations, it is experimentally demonstrated how to deduce a few key bits. Evidence is given that the present analysis is not applicable on Grain-128 or Trivium with full IV initialization.

resources and links

[paper] - [slides] - [SASC 2008] ×

title

New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba.

authors

Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger.

publication

In K. Nyberg, editor, Fast Software Encryption - FSE 2008, 15th International Workshop, Lausanne, Switzerland, February 10-13, 2008. Proceedings, volume 5086 of Lecture Notes in Computer Science, pages 470-488. Springer-Verlag, 2008.

award

Best analysis of Rumba, the award comes with $1000 prize money.

abstract

The stream cipher Salsa20 was introduced by Bernstein in 2005 as a candidate in the eSTREAM project, accompanied by the reduced versions Salsa20/8 and Salsa20/12. ChaCha is a variant of Salsa20 aiming at bringing better diffusion for similar performance. Variants of Salsa20 with up to 7 rounds (instead of 20) have been broken by differential cryptanalysis, while ChaCha has not been analyzed yet. In this paper, we introduce a novel method for differential cryptanalysis of Salsa20 and ChaCha, inspired by correlation attacks and related to the notion of neutral bits. This is the first application of neutral bits in stream cipher cryptanalysis, and it allows us to present the first break of Salsa20/8, to bring faster attacks on the 7-round variant, and to break 6- and 7-round ChaCha. In a second part, we analyze the compression function Rumba, constructed as the XOR of four Salsa20 instances, and returning a 512-bit output. We find collision and preimage attacks for two simplified variants, then we discuss differential attacks on the original version, and exploit a high-probability differential to reduce complexity of collision search from 2256to 279 for 3-round Rumba. We give examples of collisions over three rounds for a version without feedforward, and near-collisions of weight 16 for three rounds of the original compression function, and of weight 129 for four rounds.

resources and links

[paper] - [slides] - [ePrint] - [FSE 2008] - [eSTREAM] - [Salsa20 page] - [ChaCha page] - [Rumba page]

×
title

Reduced Complexity Attacks on the Alternating Step Generator.

authors

Shahram Khazaei, Simon Fischer, and Willi Meier.

publication

In C. Adams, A. Miri, and M. Wiener, editors, Selected Areas in Cryptography - SAC 2007, 14th International Workshop, Ottawa, Canada, August 16-17, 2007. Proceedings, volume 4876 of Lecture Notes in Computer Science, pages 1-16. Springer-Verlag, 2007.

abstract

In this paper, we present some reduced complexity attacks on the Alternating Step Generator (ASG). The attacks are based on a quite general framework and mostly benefit from the low sampling resistance of the ASG, and of an abnormal behavior related to the distribution of the initial states of the stop/go LFSR's which produce a given segment of the output sequence. Our results compare well with previous results as they show a greater flexibility with regard to known output of the ASG, which amounts in reduced complexity. We will also give a closed form for the complexity of attacks on ASG (and SG) as presented in [Joh98].

resources and links

[pdf] - [slides]

×
title

Algebraic Immunity of S-boxes and Augmented Functions.

authors

Simon Fischer and Willi Meier.

publication

In A. Biryukov, editor, Fast Software Encryption - FSE 2007, 14th International Workshop, Luxembourg City, Luxembourg, March 26-28, 2007. Proceedings, volume 4593 of Lecture Notes in Computer Science, pages 366-381. Springer-Verlag, 2007.

abstract

In this paper, the algebraic immunity of S-boxes and augmented functions of stream ciphers is investigated. Augmented functions are shown to have some algebraic properties that are not covered by previous measures of immunity. As a result, efficient algebraic attacks with very low data complexity on certain filter generators become possible. In a similar line, the algebraic immunity of the augmented function of the eSTREAM candidate Trivium is experimentally tested. These tests suggest that Trivium has some immunity against algebraic attacks on augmented functions.

resources and links

[paper] - [slides]

×
title

Non-randomness in eSTREAM Candidates Salsa20 and TSC-4.

authors

Simon Fischer, Willi Meier, Côme Berbain, Jean-François Biasse, Matt Robshaw.

publication

In R. Barua and T. Lange, editors, Progress in Cryptology - INDOCRYPT 2006, 7th International Conference on Cryptology in India, Kolkata, India, December 11-13, 2006. Proceedings, volume 4329 of Lecture Notes in Computer Science, pages 2-16. Springer-Verlag, 2006.

abstract

Stream cipher initialisation should ensure that the initial state or keystream is not detectably related to the key and initialisation vector. In this paper we analyze the key/IV setup of the eSTREAM Phase 2 candidates Salsa20 and TSC-4. In the case of Salsa20 we demonstrate a key recovery attack on six rounds and observe non-randomness after seven. For TSC-4, non-randomness over the full eight-round initialisation phase is detected, but would also persist for more rounds.

resources and links

[talk] - [slides]

×
title

Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks.

authors

Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, and Olivier Ruatta.

publication

In S. Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006. Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 147-164. Springer-Verlag, 2006.

abstract

In this paper we propose several efficient algorithms for assessing the resistance of Boolean functions against algebraic and fast algebraic attacks when implemented in LFSR-based stream ciphers. An algorithm is described which permits to compute the algebraic immunity d of a Boolean function with n variables in O(D^2) operations, for D \approx \binom{n}{d}, rather than in O(D^3) operations necessary in all previous algorithms. Our algorithm is based on multivariate polynomial interpolation. For assessing the vulnerability of arbitrary Boolean functions with respect to fast algebraic attacks, an efficient generic algorithm is presented that is not based on interpolation. This algorithm is demonstrated to be particularly efficient for symmetric Boolean functions. As an application it is shown that large classes of symmetric functions are very vulnerable to fast algebraic attacks despite their proven resistance against conventional algebraic attacks.

resources and links

[paper] - [slides] - [Eurocrypt 2006] - [homepage F. Armknecht] - [homepage N. Courois]

×
title

Distinguishing Attacks on T-functions.

authors

Simon Künzli, Pascal Junod, and Willi Meier.

publication

In E. Dawson and S. Vaudenay, editors, Progress in Cryptology - MyCrypt 2005, First International Conference on Cryptology in Malaysia, Kuala Lumpur, Malaysia, September 28-30, 2005. Proceedings, volume 3715 of Lecture Notes in Computer Science, pages 2-15. Springer-Verlag, 2005.

award

Best paper of the conference.

abstract

Klimov and Shamir proposed a new class of simple cryptographic primitives named T-functions. For two concrete proposals based on the squaring operation, a single word T-function and a previously unbroken multi-word T-function with a 256-bit state, we describe an efficient distinguishing attack having a 232 data complexity. Furthermore, Hong et al. recently proposed two fully specified stream ciphers, consisting of multi-word T-functions with 128-bit states and filtering functions. We describe distinguishing attacks having a 222 and a 234 data complexity, respectively. The attacks have been implemented.

resources and links

[paper] - [slides]

×
title

Equivalent Representations of the F-FCSR Keystream Generator.

authors

Simon Fischer, Willi Meier, and Dirk Stegemann.

publication

In SASC 2008 - The State of the Art of Stream Ciphers, Lausanne, Switzerland, February 13-14, 2008. Workshop record, pages 87-96.

Also in WMC 2008 - Second Workshop on Mathematical Cryptology, Santander, Spain, October 23-25, 2008.

abstract

In this technical report, we investigate the security of the eSTREAM phase 3 stream cipher candidate F-FCSR. Our analysis shows a link to an equivalent representation. We conclude that this other representation is not weaker than the original one and thus doesn't constitute a practical threat.

resources and links

[paper] - [slides] - [SASC 2008] - [WMC 2008]

×
title

Distinguishing Attack on MAG.

authors

Simon Künzli and Willi Meier.

publication

In eSTREAM, ECRYPT Stream Cipher Project, Report 2005/053, 2005.

abstract

MAG is a synchronous stream cipher submitted to the ECRYPT stream cipher project. We present a very simple distinguishing attack (with some predicting feature) on MAG, requiring only 129 successive bytes of known keystream, computation and memory are negligible. The attack has been verified.

resources and links

[paper] - [eSTREAM]

×
title

authors

publication

abstract

resources and links

×