Fast Software Encryption

Bellare and Kohno introduced a formal framework for the study of related-key attacks against blockciphers. They established sufficient conditions (output-unpredictability and collision-resistance) on the set of related-key-deriving (RKD) functions under which an ideal cipher is secure against related-key attacks, and suggested this could be used to derive security goals for real blockciphers. However, to do so requires the reinterpretation of results proven in the ideal-cipher model for the standard model (in which a blockcipher is modelled as, say, a pseudorandom permutation family). As we show here, this is a fraught activity. In particular, building on a recent idea of Bernstein, we first demonstrate a related-key attack that applies generically to a large class of blockciphers. The attack exploits the existence of a short description of the blockcipher, and so does not apply in the ideal-cipher model. However, the specific RKD functions used in the attack are provably output-unpredictable and collision-resistant. In this sense, the attack can be seen as a separation between the ideal-cipher model and the standard model. Second, we investigate how the related-key attack model of Bellare and Kohno can be extended to include sets of RKD functions that themselves access the ideal cipher. Precisely such related-key functions underlie the generic attack, so our extended modelling allows us to capture a larger universe of related-key attacks in the ideal-cipher model. We establish a new set of conditions on related-key functions that is sufficient to prove a theorem analogous to the main result of Bellare and Kohno, but for our extended model. We then exhibit non-trivial classes of practically relevant RKD functions meeting the new conditions. We go on to discuss standard model interpretations of this theorem, explaining why, although separations between the ideal-cipher model and the standard model still exist for this setting, they can be seen as being much less natural than our previous separation. In this manner, we argue that our extension of the Bellare–Kohno model represents a useful advance in the modelling of related-key attacks. In the full version of the paper, we also consider the topic of key-recovering related-key attacks and its relationship to the Bellare–Kohno formalism. In particular, we address the question of whether lowering the security goal by requiring the adversary to perform key-recovery excludes separations of the type exhibited by us in the Bellare–Kohno model.

Analyzing desired generic properties of hash functions is an important current area in cryptography. For example, in Eurocrypt 2009, Dodis, Ristenpart and Shrimpton [8] introduced the elegant notion of “Preimage Awareness” (PrA) of a hash function H ^P, and they showed that a PrA hash function followed by an output transformation modeled to be a FIL (fixed input length) random oracle is PRO (pseudorandom oracle) i.e. indifferentiable from a VIL (variable input length) random oracle. We observe that for recent practices in designing hash function (e.g. SHA-3 candidates) most output transformations are based on permutation(s) or blockcipher(s), which are not PRO. Thus, a natural question is how the notion of PrA can be employed directly with these types of more prevalent output transformations? We consider the Davies-Meyer’s type output transformation OT(x) : = E(x) ⊕ x where E is an ideal permutation. We prove that OT(H ^P(·)) is PRO if H ^P is PrA, preimage resistant and computable message aware (a related but not redundant notion, needed in the analysis that we introduce in the paper). The similar result is also obtained for 12 PGV output transformations. We also observe that some popular double block length output transformations can not be employed as output transformation.

We present a new variant of cube attacks called a dynamic cube attack. Whereas standard cube attacks [4] find the key by solving a system of linear equations in the key bits, the new attack recovers the secret key by exploiting distinguishers obtained from cube testers. Dynamic cube attacks can create lower degree representations of the given cipher, which makes it possible to attack schemes that resist all previously known attacks. In this paper we concentrate on the well-known stream cipher Grain-128 [6], on which the best known key recovery attack [15] can recover only 2 key bits when the number of initialization rounds is decreased from 256 to 213. Our first attack runs in practical time complexity and recovers the full 128-bit key when the number of initialization rounds in Grain-128 is reduced to 207. Our second attack breaks a Grain-128 variant with 250 initialization rounds and is faster than exhaustive search by a factor of about 2²⁸. Finally, we present an attack on the full version of Grain-128 which can recover the full key but only when it belongs to a large subset of 2^− 10 of the possible keys. This attack is faster than exhaustive search over the 2¹¹⁸ possible keys by a factor of about 2¹⁵. All of our key recovery attacks are the best known so far, and their correctness was experimentally verified rather than extrapolated from smaller variants of the cipher. This is the first time that a cube attack was shown to be effective against the full version of a well known cipher which resisted all previous attacks.

The knapsack generator was introduced in 1985 by Rueppel and Massey as a novel LFSR-based stream cipher construction. Its output sequence attains close to maximum linear complexity and its relation to the knapsack problem suggests strong security. In this paper we analyze the security of practically relevant instances of this generator as they are recommended for the use in RFID systems, for example. We describe a surprisingly effective guess and determine strategy, which leads to practical attacks on small instances and shows that the security margin of larger instances is smaller than expected. We also briefly discuss a variant of the knapsack generator recently proposed by von zur Gathen and Shparlinski and show that this variant should not be used for cryptographic applications.

In this paper, contrary to the claim of Mantin and Shamir (FSE 2001), we prove that there exist biases in the initial bytes (3 to 255) of the RC4 keystream towards zero. These biases immediately provide distinguishers for RC4. Additionally, the attack on broadcast RC4 to recover the second byte of the plaintext can be extended to recover the bytes 3 to 255 of the plaintext given Ω(N ³) many ciphertexts. Further, we also study the non-randomness of index j for the first two rounds of PRGA, and identify a strong bias of j ₂ towards 4. This in turn provides us with certain state information from the second keystream byte.

The GOST block cipher is the Russian encryption standard published in 1989. In spite of considerable cryptanalytic efforts over the past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and related keys) has not been published yet. In this paper, we show a first single-key attack, which works for all key classes, on the full GOST block cipher. To construct the attack, we develop a new attack framework called Reflection-Meet-in-the-Middle Attack. This approach combines techniques of the reflection attack and the meet-in-the-middle attack. We apply it to the GOST block cipher with further novel techniques which are the effective MITM techniques using equivalent keys on short rounds. As a result, a key can be recovered with 2²²⁵ computations and 2³² known plaintexts.

We study software performance of authenticated-encryption modes CCM, GCM, and OCB. Across a variety of platforms, we find OCB to be substantially faster than either alternative. For example, on an Intel i5 (“Clarkdale”) processor, good implementations of CCM, GCM, and OCB encrypt at around 4.2 cpb, 3.7 cpb, and 1.5 cpb, while CTR mode requires about 1.3 cpb. Still we find room for algorithmic improvements to OCB, showing how to trim one blockcipher call (most of the time, assuming a counter-based nonce) and reduce latency. Our findings contrast with those of McGrew and Viega (2004), who claimed similar performance for GCM and OCB.

Hummingbird-1 is a lightweight encryption and message authentication primitive published in RISC ’09 and WLC ’10. Hummingbird-1 utilizes a 256-bit secret key and a 64-bit IV. We report a chosen-IV, chosen-message attack that can recover the full secret key with a few million chosen messages processed under two related IVs. The attack requires at most 2⁶⁴ off-line computational effort. The attack has been implemented and demonstrated to work against a real-life implementation of Hummingbird-1. By attacking the differentially weak E component, the overall attack complexity can be reduced by a significant factor. Our cryptanalysis is based on a differential divide-and-conquer method with some novel techniques that are uniquely applicable to ciphers of this type.

We analyze \(\mathrm{adp}^\texttt{ARX}\), the probability with which additive differences propagate through the following sequence of operations: modular addition, bit rotation and XOR (ARX). We propose an algorithm to evaluate \(\mathrm{adp}^\texttt{ARX}\) with a linear time complexity in the word size. This algorithm is based on the recently proposed concept of S-functions. Because of the bit rotation operation, it was necessary to extend the S-functions framework. We show that \(\mathrm{adp}^\texttt{ARX}\) can differ significantly from the multiplication of the differential probability of each component. To the best of our knowledge, this paper is the first to propose an efficient algorithm to calculate \(\mathrm{adp}^\texttt{ARX}\). Accurate calculations of differential probabilities are necessary to evaluate the resistance of cryptographic primitives against differential cryptanalysis. Our method can be applied to find more accurate differential characteristics for ARX-based constructions.

Addition modulo 2³¹ − 1 is a basic arithmetic operation in the stream cipher ZUC. For evaluating ZUC’s resistance against linear cryptanalysis, it is necessary to study properties of linear approximations of the addition modulo 2³¹ − 1. In this paper we discuss linear approximations of the addition of k inputs modulo 2ⁿ − 1 for n ≥ 2. As a result, an explicit expression of the correlations of linear approximations of the addition modulo 2ⁿ − 1 is given when k = 2, and an iterative expression when k > 2. For a class of special linear approximations with all masks being equal to 1, we further discuss the limit of their correlations when n goes to infinity. It is shown that when k is even, the limit is equal to zero, and when k is odd, the limit is bounded by a constant depending on k.