Simon D. Fischer | Hinterdorfstrasse 11a | 6042 Dietwil
phone: +41 41 5444241
email: mail at simonfischer ch
I am a physicist working for [Siemens Building Technologies].
Until 2008, I have been a research assistant at [FHNW] and [EPFL], where I defended my thesis and obtained the Dr. sc. EPFL. My research focus was cryptanalysis of stream ciphers. See [dblp] and [scholar] for a list of publications.
Prior to that, I studied physics at the [University of Bern]. I wrote my master's thesis in field of computational physics and obtained the M. Sc. in 2003.
I like to spend time with my familiy, and some of my interests are Yoga and tennis.
Last update: January 2013
Analysis of Lightweight Stream Ciphers.
Simon Fischer.
Prof. M. A. Shokrollahi, Prof. S. Vaudenay, Prof. C. Carlet, Prof. A. Lenstra, Dr M. Robshaw.
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.
[thesis] - [slides] - [EPFL library] - [homepage S. Vaudenay] - [homepage W. Meier]
×Akkretion und Gasströmung.
Simon Künzli.
Prof. W. Benz.
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.
Some remarks on FCSRs and implications for stream ciphers.
Simon Fischer, Willi Meier, and Dirk Stegemann.
Journal of Mathematical Cryptology. Volume 3, Issue 3, Pages 227–236.
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.
Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers.
Simon Fischer, Shahram Khazaei, and Willi Meier.
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.
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.
[paper] - [slides] - [SASC 2008] ×
New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba.
Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger.
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.
Best analysis of Rumba, the award comes with $1000 prize money.
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.
[paper] - [slides] - [ePrint] - [FSE 2008] - [eSTREAM] - [Salsa20 page] - [ChaCha page] - [Rumba page]
×Reduced Complexity Attacks on the Alternating Step Generator.
Shahram Khazaei, Simon Fischer, and Willi Meier.
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.
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].
Algebraic Immunity of S-boxes and Augmented Functions.
Simon Fischer and Willi Meier.
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.
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.
Non-randomness in eSTREAM Candidates Salsa20 and TSC-4.
Simon Fischer, Willi Meier, Côme Berbain, Jean-François Biasse, Matt Robshaw.
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.
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.
Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks.
Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, and Olivier Ruatta.
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.
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.
[paper] - [slides] - [Eurocrypt 2006] - [homepage F. Armknecht] - [homepage N. Courois]
×Distinguishing Attacks on T-functions.
Simon Künzli, Pascal Junod, and Willi Meier.
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.
Best paper of the conference.
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.
Equivalent Representations of the F-FCSR Keystream Generator.
Simon Fischer, Willi Meier, and Dirk Stegemann.
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.
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.
[paper] - [slides] - [SASC 2008] - [WMC 2008]
×Distinguishing Attack on MAG.
Simon Künzli and Willi Meier.
In eSTREAM, ECRYPT Stream Cipher Project, Report 2005/053, 2005.
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.