Fast Software Encryption

In this paper, we propose related-key differential distinguishers based on the complementation property of Feistel ciphers. We show that with relaxed requirements on the complementation, i.e. the property does not have to hold for all keys and the complementation does not have to be on all bits, one can obtain a variety of distinguishers. We formulate criteria sufficient for attacks based on the complementation property. To stress the importance of our findings we provide analysis of the full-round primitives:

This paper aims to improve the understanding of the complexities for Matsui’s Algorithm 2 — one of the most well-studied and powerful cryptanalytic techniques available for block ciphers today.

We start with the observation that the standard interpretation of the wrong key randomisation hypothesis needs adjustment. We show that it systematically neglects the varying bias for wrong keys. Based on that, we propose an adjusted statistical model and derive more accurate estimates for the success probability and data complexity of linear attacks which are demonstrated to deviate from all known estimates. Our study suggests that the efficiency of Matsui’s Algorithm 2 has been previously somewhat overestimated in the cases where the adversary attempts to use a linear approximation with a low bias, to attain a high computational advantage over brute force, or both. These cases are typical since cryptanalysts always try to break as many rounds of the cipher as possible by pushing the attack to its limit.

A second assumption usually made in linear cryptanalysis is the key equivalence hypothesis, even though due to the linear hull effect, the bias can heavily depend on the key. As a further contribution of this paper, we propose a practical technique that aims to take this into account.

All theoretical observations and techniques are accompanied by experiments with small-scale ciphers.

WIDEA is a family of block ciphers designed by Junod and Macchetti in 2009 as an extension of IDEA to larger block sizes (256 and 512 bits for the main instances WIDEA-\(4\) and WIDEA-\(8\)) and larger key sizes (512 and 1024 bits, respectively). WIDEA-\(w\) is composed of \(w\) parallel copies of the IDEA block cipher, with an MDS matrix to provide diffusion between them. An important motivation was to use WIDEA to design a hash function.

In this paper we present low complexity attacks on WIDEA based on truncated differentials. We show a distinguisher for the full WIDEA with complexity only \(2^{65}\), and we use the distinguisher in a key-recovery attack with complexity \(w \cdot 2^{68}\). We also show a collision attack on WIDEA-\(8\) if it is used to build a hash function using the Merkle-Damgård mode of operation.

The attacks exploit the parallel structure of WIDEA and the limited diffusion between the IDEA instances, using differential trails where the MDS diffusion layer is never active. In addition, we use structures of plaintext to reduce the data complexity.

Relay attacks (and, more generally, man-in-the-middle attacks) are a serious threat against many access control and payment schemes. In this work, we present distance-bounding protocols, how these can deter relay attacks, and the security models formalizing these protocols. We show several pitfalls making existing protocols insecure (or at least, vulnerable, in some cases). Then, we introduce the SKI protocol which enjoys resistance to all popular attack-models and features provable security. As far as we know, this is the first protocol with such all-encompassing security guarantees.

PRINCE is a low-latency block cipher presented at ASIACRYPT 2012. The cipher was designed with a property called \(\alpha \)-reflection which reduces the definition of the decryption with a given key to an encryption with a different but related key determined by \(\alpha \). In the design document, it was shown that PRINCE is secure against known attacks independently of the value of \(\alpha \), and the design criteria for \(\alpha \) remained open.

In this paper, we introduce new generic distinguishers on PRINCE-like ciphers. First, we show that, by folding the cipher in the middle, the number of rounds can be halved due to the \(\alpha \)-reflection property. Furthermore, we investigate many classes of \(\alpha \) and find the best differential characteristic for the folded cipher. For such \(\alpha \) there exist an efficient key-recovery attack on the full 12-round cipher with the data complexity of \(2^{57.98}\) known plaintexts and time complexity of \(2^{72.39}\) encryptions. With the original value of \(\alpha \) we can attack a reduced six-round version of PRINCE. As a result of the new cryptanalysis method presented in this paper, new design criteria concerning the selection of the value of \(\alpha \) for PRINCE-like ciphers are obtained.

In this article, we provide the first third-party security analysis of the PRINCE lightweight block cipher, and the underlying \(\mathtt{PRINCE}_{core}\). First, while no claim was made by the authors regarding related-key attacks, we show that one can attack the full cipher with only a single pair of related keys, and then reuse the same idea to derive an attack in the single-key model for the full \(\mathtt{PRINCE}_{core}\) for several instances of the \(\alpha \) parameter (yet not the one randomly chosen by the designers). We also show how to exploit the structural linear relations that exist for PRINCE in order to obtain a key recovery attack that slightly breaks the security claims for the full cipher. We analyze the application of integral attacks to get the best known key-recovery attack on a reduced version of the PRINCE cipher. Finally, we provide time-memory-data tradeoffs that require only known plaintext-ciphertext data and that can be applied to full PRINCE.

In this paper we present known-plaintext single-key and chosen-key attacks on round-reduced LED-64 and LED-128. We show that with an application of the recently proposed slidex attacks [5], one immediately improves the complexity of the previous single-key 4-step attack on LED-128. Further, we explore the possibility of multicollisions and show single-key attacks on 6 steps of LED-128. A generalization of our multicollision attack leads to the statement that no 6-round cipher with two subkeys that alternate, or 2-round cipher with linearly dependent subkeys, is secure in the single-key model. Next, we exploit the possibility of finding pairs of inputs that follow a certain differential rather than a differential characteristic, and obtain chosen-key differential distinguishers for 5-step LED-64, as well as 8-step and 9-step LED-128. We provide examples of inputs that follow the 8-step differential, i.e. we are able to practically confirm our results on 2/3 of the steps of LED-128. We introduce a new type of chosen-key differential distinguisher, called random-difference distinguisher, and successfully penetrate 10 of the total 12 steps of LED-128. We show that this type of attack is generic in the chosen-key model, and can be applied to any 10-round cipher with two alternating subkeys.

We consider tweakable blockciphers with beyond the birthday bound security. Landecker, Shrimpton, and Terashima (CRYPTO 2012) gave the first construction with security up to \(\mathcal {O}(2^{2n/3})\) adversarial queries (\(n\) denotes the block size in bits of the underlying blockcipher), and for which changing the tweak does not require changing the keys for blockcipher calls. In this paper, we extend this construction, which consists of two rounds of a previous proposal by Liskov, Rivest, and Wagner (CRYPTO 2002), by considering larger numbers of rounds \(r>2\). We show that asymptotically, as \(r\) increases, the resulting tweakable blockcipher approaches security up to the information bound, namely \(\mathcal {O}(2^n)\) queries. Our analysis makes use of a coupling argument, and carries some similarities with the analysis of the iterated Even-Mansour cipher by Lampe, Patarin, and Seurin (ASIACRYPT 2012).

In this paper, we report extremely fast and optimised active and passive attacks against the old IEEE 802.11 wireless communication protocol WEP. This was achieved through a huge amount of theoretical and experimental analysis (capturing WiFi packets), refinement and optimisation of all the former known attacks and methodologies against RC4 stream cipher in WEP mode. We support all our claims by providing an implementation of this attack as a publicly available patch on Aircrack-ng. Our new attacks improve its success probability drastically. We adapt our theoretical analysis in Eurocrypt 2011 to real-world scenarios and we perform a slight adjustment to match the empirical observations. Our active attack, based on ARP injection, requires \(22\,500\) packets to gain success probability of \(50\,\%\) against a \(104\)-bit WEP key, using Aircrack-ng in non-interactive mode. It runs in less than \(5\) s on an off-the-shelf PC. Using the same number of packets, Aicrack-ng yields around \(3\,\%\) success rate. Furthermore, we describe very fast passive only attacks by just eavesdropping TCP/IPv4 packets in a WiFi communication. Our passive attack requires \(27\,500\) packets. This is much less than the number of packets Aircrack-ng requires in active mode (around \(37\,500\)), which is a huge improvement. We believe that our analysis brings on further insight to the security of RC4.

This paper investigates the practical security of RC4 in broadcast setting where the same plaintext is encrypted with different user keys. We introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a cumulative list of strong biases in the first 257 bytes of the RC4 keystream is constructed. We demonstrate a plaintext recovery attack using our strong bias set of initial bytes by the means of a computer experiment. Almost all of the first 257 bytes of the plaintext can be recovered, with probability more than 0.8, using only \(2^{32}\) ciphertexts encrypted by randomly-chosen keys. We also propose an efficient method to extract later bytes of the plaintext, after the 258th byte. The proposed method exploits our bias set of first 257 bytes in conjunction with the digraph repetition bias proposed by Mantin in EUROCRYPT 2005, and sequentially recovers the later bytes of the plaintext after recovering the first 257 bytes. Once the possible candidates for the first 257 bytes are obtained by our bias set, the later bytes can be recovered from about \(2^{34}\) ciphertexts with probability close to 1.

In this work we consider generic algorithms to find near-collisions for a hash function. If we consider only hash computations, it is easy to compute a lower-bound for the complexity of near-collision algorithms, and to build a matching algorithm. However, this algorithm needs a lot of memory, and makes more than \(2^{n/2}\) memory accesses. Recently, several algorithms have been proposed without this memory requirement; they require more hash evaluations, but the attack is actually more practical. They can be divided in two main categories: they are either based on truncation, or based on covering codes.

In this paper, we give a new insight to the generic complexity of a near-collision attack. First, we consider time-memory trade-offs for truncation-based algorithms. For a practical implementation, it seems reasonable to assume that some memory is available and we show that taking advantage of this memory can significantly reduce the complexity. Second, we show a new method combining truncation and covering codes. The new algorithm is always at least as good as the previous works, and often gives a significant improvement. We illustrate our results by giving a 10-near collision for MD5: our algorithm has a complexity of \(2^{45.4}\) using 1 TB of memory while the best previous algorithm required \(2^{52.5}\) computations.

On October 2-nd 2012 NIST announced its selection of the Keccak scheme as the new SHA-3 hash standard. In this paper we present the first published collision finding attacks on reduced-round versions of Keccak-384 and Keccak-512, providing actual collisions for 3-round versions, and describing an attack which is \(2^{45}\) times faster than birthday attacks for 4-round Keccak-384. For Keccak-256, we increase the number of rounds which can be attacked to 5. All these results are based on a generalized internal differential attack (introduced by Peyrin at Crypto 2010), and use it to map a large number of Keccak inputs into a relatively small subset of possible outputs with a surprisingly large probability. In such a squeeze attack it is easier to find random collisions in the reduced target subset by a standard birthday argument.

In this paper we attack round-reduced Keccak hash function with a technique called rotational cryptanalysis. We focus on Keccak variants proposed as SHA-3 candidates in the NIST’s contest for a new standard of cryptographic hash function. Our main result is a preimage attack on 4-round Keccak and a 5-round distinguisher on Keccak-\(f\)[1600] permutation — the main building block of Keccak hash function.

The hash function Skein is one of 5 finalists of the NIST SHA-3 competition. It is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper proposes a free-start partial-collision attack on round-reduced Skein-256 by combing the rebound attack with the modular differential techniques. The main idea of our attack is to connect two short differential paths into a long one with another differential characteristic that is complicated. Following our path, we give a free-start partial-collision attack on Skein-256 reduced to 32 rounds with Hamming distance 50 and complexity about \(2^{85}\) hash computations. In particular, we provide practical near-collision examples for Skein-256 reduced to 24 rounds and 28 rounds in the fixed tweaks and choosing tweaks setting separately.

As far as we know, this is the first construction of a non-linear differential path for Skein which can lead to significantly improvement over previous analysis.

Universal hash functions are commonly used primitives for fast and secure message authentication in the form of Message Authentication Codes (MACs) or Authenticated Encryption with Associated Data (AEAD) schemes. These schemes are widely used and standardised, the most well known being McGrew and Viega’s Galois/Counter Mode (GCM). In this paper we identify some properties of hash functions based on polynomial evaluation that arise from the underlying algebraic structure. As a result we are able to describe a general forgery attack, of which Saarinen’s cycling attack from FSE 2012 is a special case. Our attack removes the requirement for long messages and applies regardless of the field in which the hash function is evaluated. Furthermore we provide a common description of all published attacks against GCM, by showing that the existing attacks are the result of these algebraic properties of the polynomial-based hash function. Finally, we greatly expand the number of known weak GCM keys and show that almost every subset of the keyspace is a weak key class.

Security against related-key attacks is an important criteria for modern cryptographic constructions. In the related-key setting, the adversary has the ability to query the underlying function on the target key as well as on some related-keys. Although provable security against related-key attack has received considerable attention in recent years, most of the results in the literature aim to achieve pseudorandomness and semantic security and often lead to inefficient constructions.

In this paper, we formalize the notion of unpredictability in the related-key setting. We start with the definitions of related-key security of Message Authentication Codes and identify required properties of related-key derivation functions for provable security. We show that unlike PRFs, MACs can inherently tolerate related-key attacks against constant transformations. Next, we consider the construction of variable-input-length MACs from fixed-input-length related-key unpredictable functions. We present simple attacks against XCBC and TMAC. We present a general construction of related-key secure MACs. Our construction, instantiated with Enciphered CBC construction of Dodis, Pietrzak and Puniya (EUROCRYPT 2008), results into first provably secure domain extension of related-key secure unpredictable functions. Finally, we present two constructions of related-key secure MACs from DDH assumption. The first construction is extremely efficient and tolerates group-induced partial key transformations. The second construction achieves security against independent group-induced tranformations and is more efficient than the RK-PRFs achieved by Bellare and Cash (CRYPTO 2010).

\(\text {EAX}'\) (or EAX-prime) is an authenticated encryption (AE) specified by ANSI C12.22 as a standard security function for Smart Grid. \(\text {EAX}'\) is based on EAX proposed by Bellare, Rogaway, and Wagner. While EAX has a proof of security based on the pseudorandomness of the internal blockcipher, no published security result is known for \(\text {EAX}'\). This paper studies the security of \(\text {EAX}'\) and shows that there is a sharp distinction in security of \(\text {EAX}'\) depending on the input length. \(\text {EAX}'\) encryption takes two inputs, called cleartext and plaintext, and we present various efficient attacks against \(\text {EAX}'\) using single-block cleartext and plaintext. At the same time we prove that if cleartexts are always longer than one block, it is provably secure based on the pseudorandomness of the blockcipher.

Known-key distinguishers for block ciphers were proposed by Knudsen and Rijmen at ASIACRYPT 2007 and have been a major research topic in cryptanalysis since then. A formalization of known-key attacks in general is known to be difficult. In this paper, we tackle this problem for the case of block ciphers based on ideal components such as random permutations and random functions as well as propose new generic known-key attacks on generalized Feistel ciphers. We introduce the notion of known-key indifferentiability to capture the security of such block ciphers under a known key. To show its meaningfulness, we prove that the known-key attacks on block ciphers with ideal primitives to date violate security under known-key indifferentiability. On the other hand, to demonstrate its constructiveness, we prove the balanced Feistel cipher with random functions and the multiple Even-Mansour cipher with random permutations known-key indifferentiable for a sufficient number of rounds. We note that known-key indifferentiability is more quickly and tightly attained by multiple Even-Mansour which puts it forward as a construction provably secure against known-key attacks.

We propose to relax the assumption that decryption failures are indistinguishable in security models for symmetric encryption. Our main purpose is to build models that better reflect the reality of cryptographic implementations, and to surface the security issues that arise from doing so. We systematically explore the consequences of this relaxation, with some surprising consequences for our understanding of this basic cryptographic primitive. Our results should be useful to practitioners who wish to build accurate models of their implementations and then analyse them. They should also be of value to more theoretical cryptographers proposing new encryption schemes, who, in an ideal world, would be compelled by this work to consider the possibility that their schemes might leak more than simple decryption failures.

This paper studies state-of-the-art software implementation of lightweight symmetric primitives from embedded system programmer’s standpoint. In embedded environments, due to many possible variations of ROM/RAM-size combinations, it is not always easy to obtain an entire performance picture of a given primitive and to create a fair benchmark from top speed records.

In this study we classify these size combinations into several categories and optimize operation speed in each category. We implemented on Renesas’ RL78 microcontroller - a typical CISC embedded processor, four block ciphers and seven hash functions with various combinations of ROM and RAM sizes to make performance characteristics of these primitives clearer. We also discuss how to create an interface and measure size and speed of a given primitive from a practical point of view.

As a result, our AES encryption codes run at as fast as 3,855 cycles/block in the ROM-1KB RAM-64B category, and 6,622 cycles/block in the ROM-512B RAM-128B category. For another examples aiming at minimizing a ROM size, we have achieved 453-byte Keccak, 396-byte Skein-256 and 210-byte PRESENT encryption codes on this processor.

Masking is a widely used countermeasure to protect block cipher implementations against side-channel attacks. The principle is to split every sensitive intermediate variable occurring in the computation into \(d+1\) shares, where \(d\) is called the masking order and plays the role of a security parameter. A masked implementation is then said to achieve \(d\) ^th-order security if any set of \(d\) (or less) intermediate variables does not reveal key-dependent information. At CHES 2010, Rivain and Prouff have proposed a higher-order masking scheme for AES that works for any arbitrary order \(d\). This scheme, and its subsequent extensions, are based on an improved version of the shared multiplication processing published by Ishai et al. at CRYPTO 2003. This improvement enables better memory/timing performances but its security relies on the refreshing of the masks at some points in the algorithm. In this paper, we show that the method proposed at CHES 2010 to do such mask refreshing introduces a security flaw in the overall masking scheme. Specifically, we show that it is vulnerable to an attack of order \(\lceil d/2 \rceil +1\) whereas the scheme is supposed to achieve \(d\) ^th-order security. After exhibiting and analyzing the flaw, we propose a new solution which avoids the use of mask refreshing, and we prove its security. We also provide some implementation trick that makes our proposed solution, not only secure, but also faster than the original scheme.

In this paper, we propose a new Authenticated Lightweight Encryption algorithm coined ALE. The basic operation of ALE is the AES round transformation and the AES-128 key schedule. ALE is an online single-pass authenticated encryption algorithm that supports optional associated data. Its security relies on using nonces.

We provide an optimized low-area implementation of ALE in ASIC hardware and demonstrate that its area is about 2.5 kGE which is almost two times smaller than that of the lightweight implementations for AES-OCB and ASC-1 using the same lightweight AES engine. At the same time, it is at least 2.5 times more performant than the alternatives in their smallest implementations by requiring only about 4 AES rounds to both encrypt and authenticate a 128-bit data block for longer messages. When using the AES-NI instructions, ALE outperforms AES-GCM, AES-CCM and ASC-1 by a considerable margin, providing a throughput of 1.19 cpb close that of AES-OCB, which is a patented scheme. Its area- and time-efficiency in hardware as well as high performance in high-speed parallel software make ALE a promising all-around AEAD primitive.

We present attacks on full Hummingbird-2 which are able to recover the 128-bit secret keys of two black box cipher instances that have a certain type of low-weight XOR difference in their keys. We call these highly correlated keys as they produce the same ciphertext with a significant probability. The complexity of our main chosen-IV key-recovery attack is \(2^{64}\). The first 64 bits of the key can be independently recovered with only \(2^{36}\) effort. This is the first sub-exhaustive attack on the full cipher under two related keys. Our attacks use some novel tricks and techniques which are made possible by Hummingbird-2’s unique word-based structure. We have verified the correctness and complexity of our attacks by fully implementing them. We also discuss enabling factors of these attacks and describe an alternative design for the WD16 nonlinear keyed function which is resistant to attacks of this type. The new experimental function replaces S-boxes with simple \(\chi \) functions.

The GMR-1 and GMR-2 stream ciphers, which are used in the satellite phones, have been reconstructed by Driessen et al. recently. The GMR-1 cipher is shown to be a proprietary variant of the GSM A5/2 algorithm, thus it could be cracked using the previous known method. For the newly designed GMR-2 cipher, by observing a non-uniform behavior of its component, Driessen et al. proposed an efficient known plaintext attack to recover the encryption key (a session key with 64-bit) with approximately 5–6 frames (50–65 bytes) of keystream.

In this paper, we first revisit the properties of each component of the GMR-2 cipher, and then present a low data complexity attack on it by adopting the strategy of guess-and-determine. We call this kind of attack the dynamic guess and determine attack, since the evolution of the guessing part of the internal state of the attack is changed dynamically according to the intermediate process. Our theoretical analysis demonstrates that, using the proposed attack, the 64-bit encryption key could be recovered by guessing no more than 32 bits when 15 bytes (1 frame) of the keystream is available. Some experimental results are also performed on a single PC to confirm our analysis, and the number of candidates for exhaustive search is about \(2^{28}\) on average.

Dinur and Shamir have described cube attacks at EUROCRYPT ’09 and they have shown how efficient they are on the stream cipher Trivium up to 767 rounds. These attacks have been extended to distinguishers but since this seminal work, no better results on the complexity of key recovery attacks on Trivium have been presented. It appears that the time complexity to compute cubes is expensive and the discovery of linear superpoly also requires the computation of many cubes. In this paper, we increase the number of attacked initialization rounds by improving the time complexity of computing cube and we show attacks that go beyond this bound. We were able to find linear superpoly up to 784 rounds, which leads to an attack requiring \(2^{39}\) queries. Using quadratic superpoly, we were also able to provide another attack up to 799 rounds which complexity is \(2^{40}\) queries and \(2^{62}\) for the exhaustive search part. To achieve such results, we find a way to reduce the density of the polynomials, we look for quadratic relations and we extensively use the Moebius transform to speed up computations for various purposes.

Grain v1 is one of the \(7\) finalists selected in the final portfolio by the eSTREAM project. It has an elegant and compact structure, especially suitable for a constrained hardware environment. Though a number of potential weaknesses have been identified, no key recovery attack on the original design in the single key model has been found yet. In this paper, we propose a key recovery attack, called near collision attack, on Grain v1. The attack utilizes the compact NFSR-LFSR combined structure of Grain v1 and works even if all of the previous identified weaknesses have been sewed and if a perfect key/IV initialization algorithm is adopted. Our idea is to identify near collisions of the internal states at different time instants and restore the states accordingly. Combined with the BSW sampling and the non-uniform distribution of internal state differences for a fixed keystream difference, our attack has been verified on a reduced version of Grain v1 in experiments. An extrapolation of the results under some assumption indicates an attack on Grain v1 for any fixed IV in \(2^{71.4}\) cipher ticks after the pre-computation of \(2^{73.1}\) ticks, given \(2^{62.8}\)-bit memory and \(2^{67.8}\) keystream bits, which is the best key recovery attack against Grain v1 so far. Hopefully, it provides some new insights on such compact stream ciphers.

In this paper, we revisit Demirci and Selçuk meet-in-the-middle attacks on AES. We find a way to automatically model SPN block cipher and meet-in-the-middle attacks that allows to perform exhaustive search of this kind of attacks. This search uses the tool developed by Bouillaguet, Derbez and Fouque at CRYPTO 2011 as a subroutine to solve specific systems. We also take into account ideas introduced by Dunkelman, Keller and Shamir at ASIACRYPT 2010 which can be seen as a new tradeoff of the classical time/memory tradeoff used by Demirci and Selçuk. As a result, we automatically recover all the recent improved attacks of Derbez, Fouque and Jean on AES and we show new improved attacks against 8-rounds of AES-192 and AES-256.

In this paper we introduce Janus, a software framework – written in Java – which is built to provide assistance in finding independent-biclique attacks for a user-chosen set of parameters, e.g., the number of rounds and dimension of the biclique. Given a certain cipher, Janus not only finds an optimal bipartite graph (biclique), but also provides an all-round carefree package of finding an optimal matching-with-precomputation step, rendering the found biclique, and determining the computational complexity of the attack.

In several cryptographic primitives, Sboxes of small size are used to provide nonlinearity. After several iterations, all the output bits of the primitive are ideally supposed to depend in a nonlinear way on all of the input variables. However, in some cases, it is possible to find some output bits that depend in an affine way on a small number of input bits if the other input bits are fixed to a well-chosen value. Such situations are for example exploited in cube attacks or in attacks like the one presented by Fuhr against the hash function Hamsi. Here, we define a new property for nonlinear Sboxes, named \((v,w)\)-linearity, which means that \(2^w\) components of an Sbox are affine on all cosets of a \(v\)-dimensional subspace. This property is related to the generalization of the so-called Maiorana-McFarland construction for Boolean functions. We show that this concept quantifies the ability of an Sbox to propagate affine relations. As a proof of concept, we exploit this new notion for analyzing and slightly improving Fuhr’s attack against Hamsi and we show that its success strongly depends on the \((v,w)\)-linearity of the involved Sbox.