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
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
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
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
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
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
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
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
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
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
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
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
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
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
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