Stefan Kölbl

Publications

  1. Mind the Gap - A Closer Look at the Security of Block Ciphers against Differential Cryptanalysis

    Resistance against differential cryptanalysis is an important design criteria for any modern block cipher and most designs rely on finding some upper bound on probability of single differential characteristics. However, already at EUROCRYPT'91, Lai et al. comprehended that differential cryptanalysis rather uses differentials instead of single characteristics. In this paper, we consider exactly the gap between these two approaches and investigate this gap in the context of recent lightweight cryptographic primitives. This shows that for many recent designs like Midori, Skinny or Sparx one has to be careful as bounds from counting the number of active S-boxes only give an inaccurate evaluation of the best differential distinguishers. For several designs we found new differential distinguishers and show how this gap evolves. We found an 8-round differential distinguisher for Skinny-64 with a probability of 2^−56.93 , while the best single characteristic only suggests a probability of 2^−72. Our approach is integrated into publicly available tools and can easily be used when developing new cryptographic primitives.
    Moreover, as differential cryptanalysis is critically dependent on the distribution over the keys for the probability of differentials, we provide experiments for some of these new differentials found, in order to confirm that our estimates for the probability are correct. While for Skinny-64 the distribution over the keys follows a Poisson distribution, as one would expect, we noticed that Speck-64 follows a bimodal distribution, and the distribution of Midori-64 suggests a large class of weak keys.

    Authors: Ralph Ankele and Stefan Kölbl

    Venue: SAC 2018

    Paper Code

  2. Finding Integral Distinguishers with Ease

    The division property method is a technique to determine integral distinguishers on block ciphers. While the complexity of finding these distinguishers is higher, it has recently been shown that MILP and SAT solvers can efficiently find such distinguishers. In this paper, we provide a framework to automatically find those distinguishers which solely requires a description of the cryptographic primitive. We demonstrate that by finding integral distinguishers for 30 primitives with different design strategies.
    We provide several new or improved bit-based division property distinguishers for ChaCha, Chaskey, DES, GIFT, LBlock, Mantis, Qarma, RoadRunner, Salsa and SM4. Furthermore, we present an algorithm to find distinguishers with lower data complexity more efficiently.

    Authors: Zahra Eskandari, Andreas Brasen Kidmose, Stefan Kölbl and Tyge Tiessen

    Venue: SAC 2018

    Paper Code

  3. ShiftRows Alternatives for AES-like Ciphers and Optimal Cell Permutations for Midori and Skinny

    We study possible alternatives for ShiftRows to be used as cell permutations in AES-like ciphers. As observed during the design process of the block cipher Midori, when using a matrix with a non-optimal branch number for the MixColumns operation, the choice of the cell permutation, i.e., an alternative for ShiftRows, can actually improve the security of the primitive. In contrast, when using an MDS matrix it is known that one cannot increase the minimum number of active S-boxes by deviating from the ShiftRows-type permutation. However, finding the optimal choice for the cell permutation for a given, non-optimal, MixColumns operation is a highly non-trivial problem. In this work, we propose techniques to speed up the search for the optimal cell permutations significantly. As case studies, we apply those techniques to Midori and Skinny and provide possible alternatives for their cell permutations. We finally state an easy-to-verify sufficient condition on a cell permutation, to be used as an alternative in Midori, that attains a high number of active S-boxes and thus provides good resistance against differential and linear attacks.

    Authors: Gianira N. Alfarano, Christof Beierle, Takanori Isobe, Stefan Kölbl, Gregor Leander

    Venue: IACR Transactions on Symmetric Cryptology 2018

    Paper BibTex Code

  4. Putting Wings on SPHINCS

    SPHINCS is a recently proposed stateless hash-based signature scheme and promising candidate for a post-quantum secure digital signature scheme. In this work we provide a comparison of the performance when instantiating SPHINCS with different cryptographic hash functions on both recent Intel and AMD platforms found in personal computers and the ARMv8-A platform which is prevalent in mobile phones.
    In particular, we provide a broad comparison of the performance of cryptographic hash functions utilizing the cryptographic extensions and vector instruction set extensions available on modern microprocessors. This comes with several new implementations optimized towards the specific use case of hash-based signature schemes. Further, we instantiate SPHINCS with these primitives and provide benchmarks for the costs of generating keys, signing messages and verifying signatures with SPHINCS on Intel Haswell, Intel Skylake, AMD Ryzen, ARM Cortex A57 and Cortex A72.

    Authors: Stefan Kölbl

    Venue: PQCrypto 2018

    Paper BibTex Slides Code

  5. Gimli: a cross-platform permutation

    This paper presents Gimli, a 384-bit permutation designed to achieve high security with high performance across a broad range of platforms, including 64-bit Intel/AMD server CPUs, 64-bit and 32-bit ARM smartphone CPUs, 32-bit ARM microcontrollers, 8-bit AVR microcontrollers, FPGAs, ASICs without side-channel protection, and ASICs with side-channel protection.

    Authors: Daniel J. Bernstein, Stefan Kölbl, Stefan Lucks, Pedro Maat Costa Massolino, Florian Mendel, Kashif Nawaz, Tobias Schneider, Peter Schwabe, François-Xavier Standaert, Yosuke Todo, Benoît Viguier

    Venue: CHES 2017

    Paper BibTex Slides Code

  6. Haraka - Efficient Short-Input Hashing for Post-Quantum Applications

    Recently, many efficient cryptographic hash function design strategies have been explored, not least because of the SHA-3 competition. These designs are, almost exclusively, geared towards high performance on long inputs. However, various applications exist where the performance on short (fixed length) inputs matters more. Such hash functions are the bottleneck in hash-based signature schemes like SPHINCS or XMSS, which is currently under standardization.
    Secure functions specifically designed for such applications are scarce. We attend to this gap by proposing two short-input hash functions (or rather simply compression functions). By utilizing AES instructions on modern CPUs, our proposals are the fastest on such platforms, reaching throughputs below one cycle per hashed byte even for short inputs, while still having a very low latency of less than 60 cycles.
    Under the hood, these results come with several innovations. First, we study whether the number of rounds for our hash functions can be reduced, if only second-preimage resistance (and not collision resistance) is required. The conclusion is: only a little. Second, since their inception, AES-like designs allow for supportive security arguments by means of counting and bounding the number of active S-boxes. However, this ignores powerful attack vectors using truncated differentials, including the powerful rebound attacks. We develop a general tool-based method to include arguments against attack vectors using truncated differentials.

    Authors: Stefan Kölbl, Martin M. Lauridsen, Florian Mendel and Christian Rechberger

    Venue: IACR Transactions on Symmetric Cryptology 2017

    Paper BibTex Slides Code

  7. The SKINNY Family of Block Ciphers and its Low-Latency Variant MANTIS

    We present a new tweakable block cipher family SKINNY, whose goal is to compete with NSA recent design SIMON in terms of hardware/software performances, while proving in addition much stronger security guarantees with regards to differential/linear attacks. In particular, unlike SIMON, we are able to provide strong bounds for all versions, and not only in the single-key model, but also in the related-key or related-tweak model.
    SKINNY has flexible block/key/tweak sizes and can also benefit from very efficient threshold implementations for side-channel protection. Regarding performances, it outperforms all known ciphers for ASIC round-based implementations, while still reaching an extremely small area for serial implementations and a very good efficiency for software and micro-controllers implementations (SKINNY has the smallest total number of AND/OR/XOR gates used for encryption process).
    Secondly, we present MANTIS, a dedicated variant of SKINNY for low-latency implementations, that constitutes a very efficient solution to the problem of designing a tweakable block cipher for memory encryption. MANTIS basically reuses well understood, previously studied, known components. Yet, by putting those components together in a new fashion, we obtain a competitive cipher to PRINCE in latency and area, while being enhanced with a tweak input.

    Authors: Christof Beierle and Jérémy Jean and Stefan Kölbl and Gregor Leander and Amir Moradi and Thomas Peyrin and Yu Sasaki and Pascal Sasdrich and Siang Meng Sim

    Venue: Crypto 2016

    Paper BibTex Slides Code Video

  8. A Brief Comparison of Simon and Simeck

    Simeck is a new lightweight block cipher design based on combining the design principles of the Simon and Speck block cipher. While the design allows a smaller and more efficient hardware implementation, its security margins are not well understood. The lack of design rationals of its predecessors further leaves some uncertainty on the security of Simeck.
    In this work we give a short analysis of the impact of the design changes by comparing the upper bounds on the probability of differential and linear trails with Simon. We also give a comparison of the effort of finding those bounds, which surprisingly is significantly lower for Simeck while covering a larger number of rounds at the same time. Furthermore, we provide new differentials for Simeck which can cover more rounds compared to previous results on Simon and study how to choose good differentials for attacks and show that one can find better differentials by building them from a larger set of trail with initially lower probability.
    We also provide experimental results for the differentials for Simon32 and Simeck32 which show that there exist keys for which the probability of the differential is significantly higher than expected. Based on this we mount key recovery attacks on 19/26/33 rounds of Simeck32/48/64, which also give insights on the reduced key guessing effort due to the different set of rotation constants.

    Authors: Stefan Kölbl and Arnab Roy

    Venue: LightSec 2016

    Paper BibTex Slides Code

  9. State-recovery analysis of Spritz

    RC4 suffered from a range of plaintext-recovery attacks using statistical biases, which use substantial, albeit close-to-practical, amounts of known keystream in applications such as TLS or WEP/WPA. Spritz was recently proposed at the rump session of CRYPTO 2014 as a slower redesign of RC4 by Rivest and Schuldt, aiming at reducing the statistical biases that lead to these attacks on RC4. Even more devastating than those plaintext-recovery attacks from large amounts of keystream would be state- or key-recovery attacks from small amounts of known keystream. For RC4, there is unsubstantiated evidence that they may exist, the situation for Spritz is however not clear, as resistance against such attacks was not a design goal.
    In this paper, we provide the first cryptanalytic results on Spritz and introduce three different state recovery algorithms. Our first algorithm recovers an internal state, requiring only a short segment of keystream, with an approximated complexity of 2^1400, which is much faster than exhaustive search through all possible states, but is still far away from a practical attack.
    Furthermore, we introduce a second algorithm that uses a pattern in the keystream to reduce the number of guessed values in our state recovery algorithm. Our third algorithm uses a probabilistic approach by considering the permutation table as probability distribution. All in all, rather than showing a weakness, our analysis supports the conjecture that compared to RC4, Spritz may also provide higher resistance against potentially devastating state-recovery attacks.

    Authors: Ralph Ankele, Stefan Kölbl and Christian Rechberger

    Venue: Latincrypt 2015

    Paper BibTex Slides

  10. Observations on the SIMON block cipher family

    In this paper we analyse the general class of functions underlying the Simon block cipher. In particular, we derive efficiently computable and easily implementable expressions for the exact differential and linear behaviour of Simon-like round functions. Following up on this, we use those expressions for a computer aided approach based on SAT/SMT solvers to find both optimal differential and linear characteristics for Simon.
    Furthermore, we are able to find all characteristics contributing to the probability of a differential for Simon32 and give better estimates for the probability for other variants. Finally, we investigate a large set of Simon variants using different rotation constants with respect to their resistance against differential and linear cryptanalysis. Interestingly, the default parameters seem to be not always optimal.

    Authors: Stefan Kölbl, Gregor Leander and Tyge Tiessen

    Venue: Crypto 2015

    Paper BibTex Slides Video Code

  11. Security of AES with a Secret S-box

    How does the security of the AES change when the S-box is replaced by a secret S-box, about which the adversary has no knowledge? Would it be safe to reduce the number of encryption rounds?
    In this paper, we demonstrate attacks based on integral cryptanalysis which allows to recover both the secret key and the secret S-box for respectively four, five, and six rounds of the AES. Despite the significantly larger amount of secret information which an adversary needs to recover, the attacks are very efficient with time/data complexities of 2^17/2^16, 2^38/2^40 and 2^90/2^64, respectively.
    Another interesting aspect of our attack is that it works both as chosen plaintext and as chosen ciphertext attack. Surprisingly, the chosen ciphertext variant has a significantly lower time complexity in the attacks on four and five round, compared to the respective chosen plaintext attacks.

    Authors: Tyge Tiessen, Lars R. Knudsen, Stefan Kölbl and Martin M. Lauridsen

    Venue: Fast Software Encryption (FSE) 2015

    Paper BibTex Slides Video

  12. Practical Attacks on AES-like Cryptographic Hash Functions

    Despite the great interest in rebound attacks on AES-like hash functions since 2009, we report on a rather generic, albeit keyschedule-dependent, algorithmic improvement: A new message modification technique to extend the inbound phase, which even for large internal states makes it possible to drastically reduce the complexity of attacks to very practical values for reduced-round versions. Furthermore, we describe new and practical attacks on Whirlpool and the recently proposed GOST R hash function with one or more of the following properties: more rounds, less time/memory complexity, and more relevant model. To allow for easy verification, we also provide a source-code for them.

    Authors: Stefan Kölbl and Christian Rechberger

    Venue: Latincrypt 2014

    Paper BibTex Slides Code

  13. Differential Cryptanalysis of Keccak Variants

    In October 2012, NIST has announced Keccak as the winner of the SHA-3 cryptographic hash function competition. Recently, at CT-RSA 2013, NIST brought up the idea to standardize Keccak variants with different parameters than those submitted to the SHA-3 competition. In particular, NIST considers to reduce the capacity to the output size of the SHA-3 standard and additionally, standardize a Keccak variant with a permutation size of 800 instead of 1600 bits. However, these variants have not been analyzed very well during the SHA-3 competition. Especially for the variant using an 800-bit permutation no analysis on the hash function has been published so far.
    In this work, we analyze these newly proposed Keccak variants and provide practical collisions for up to 4 rounds for all output sizes by constructing internal collisions. Our attacks are based on standard differential cryptanalysis contrary to the recent attacks by Dinur at al. from FSE 2013. We use a non-linear low probability path for the first two rounds and use methods from coding theory to find a high-probability path for the last two rounds. The low probability path as well as the conforming message pair is found using an automatic differential path search tool. Our results indicate that reducing the capacity slightly improves attacks, while reducing the permutation size degrades attacks on Keccak.

    Authors: Stefan Kölbl, Florian Mendel, Tomislav Nad and Martin Schläffer

    Venue: International Conference on Cryptography and Coding (IMACC) 2013

    Paper BibTex Slides

  14. Practical Attacks on the Maelstrom-0 Compression Function

    In this paper we present attacks on the compression function of Maelstrom-0. It is based on the Whirlpool hash function standardized by ISO and was designed to be a faster and more robust enhancement. We analyze the compression function and use differential cryptanalysis to construct collisions for reduced variants of the Maelstrom-0 compression function. The attacks presented in this paper are of practical complexity and show significant weaknesses in the construction compared to its predecessor. The methods used are based on recent results in the analysis of AES-based hash functions.

    Authors: Stefan Kölbl and Florian Mendel

    Venue: Applied Cryptography and Network Security (ACNS) 2011

    Paper BibTex Slides