Fast Software Encryption

TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round attack presented by Wang and Wu at ACISP 2014, but a lower data complexity.

Then, we introduce alternative representations of both the round function of this block cipher and of a sequence of 4 rounds. LBlock, another lightweight block cipher, turns out to exhibit the same behaviour. Then, we illustrate how this alternative representation can shed new light on the security of TWINE by deriving high probability iterated truncated differential trails covering 4 rounds with probability \(2^{-16}\).

The importance of these is shown by combining different truncated differential trails to attack 23-rounds TWINE-128 and by giving a tighter lower bound on the high probability of some differentials by clustering differential characteristics following one of these truncated trails. A comparison between these high probability differentials and those recently found in a variant of LBlock by Leurent highlights the importance of considering the whole distribution of the coefficients in the difference distribution table of a S-Box and not only their maximum value.

MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan, and is recognized internationally as an European NESSIE-recommended cipher and an ISO standard. Since its introduction, MISTY1 was subjected to extensive cryptanalytic efforts, yet no attack significantly faster than exhaustive key search is known on its full version. The best currently known attack is a higher-order differential attack presented by Tsunoo et al. in 2012 which breaks a reduced variant of MISTY1 that contains 7 of the 8 rounds and 4 of the 5 FL layers in \(2^{49.7}\) data and \(2^{116.4}\) time.

In this paper, we present improved higher-order differential attacks on reduced-round MISTY1. Our attack on the variant considered by Tsunoo et al. requires roughly the same amount of data and only \(2^{100.4}\) time (i.e., is \(2^{16}\) times faster). Furthermore, we present the first attack on a MISTY1 variant with 7 rounds and all 5 FL layers, requiring \(2^{51.4}\) data and \(2^{121}\) time. To achieve our results, we use a new higher-order differential characteristic for 4-round MISTY1, as well as enhanced key recovery algorithms based on the partial sums technique.

As one of the generalizations of differential cryptanalysis, the truncated differential cryptanalysis has become a powerful toolkit to evaluate the security of block ciphers. In this article, taking advantage of the meet-in-the-middle like technique, we introduce a new method to construct truncated differential characteristics of block ciphers. Based on the method, we propose 10-round and 8-round truncated differential characteristics for CLEFIA and Camellia, respectively, which are ISO standard block ciphers. Applying the 10-round truncated differential characteristic for CLEFIA, we launch attacks on 14/14/15-round CLEFIA-128/192/256 with \(2^{108}\), \(2^{135}\) and \(2^{203}\) encryptions, respectively. For Camellia, we utilize the 8-round truncated differential to attack 11/12-round Camellia-128/192 including the \(FL/FL^{-1}\) and whiten layers with \(2^{121.3}\) and \(2^{185.3}\) encryptions. As far as we know, most of the cases are the best results of these attacks on both ciphers.

The decorrelation theory provides a different point of view on the security of block cipher primitives. Results on some statistical attacks obtained in this context can support or provide new insight on the security of symmetric cryptographic primitives. In this paper, we study, for the first time, the multidimensional linear attacks as well as the truncated differential attacks in this context. We show that the cipher should be decorrelated of order two to be resistant against some multidimensional linear and truncated differential attacks. Previous results obtained with this theory for linear, differential, differential-linear and boomerang attacks are also resumed and improved in this paper.

While recent publications have shown strong relations between impossible differential and zero-correlation distinguishers as well as between zero-correlation and integral distinguishers, we analyze in this paper some relations between the underlying key-recovery attacks against Type-II Feistel networks. The results of this paper are build on the relation presented at ACNS 2014. In particular, using a matrix representation of the round function, we show that we can not only find impossible, integral and multidimensional zero-correlation distinguishers but also find the key-words involved in the underlined key-recovery attacks. Based on this representation, for matrix-method-derived strongly-related zero-correlation and impossible distinguishers, we show that the key-words involved in the zero-correlation attack is a subset of the key-words involved in the impossible differential attack. Other relations between the key-words involved in zero-correlation, impossible and integral attacks are also extracted. Also we show that in this context the data complexity of the multidimensional zero-correlation attack is larger than that of the other two attacks.

Rank estimation algorithms allow analyzing the computational security of cryptographic keys for which adversaries have obtained partial information thanks to leakage or cryptanalysis. They are particularly useful in side-channel security evaluations, where the key is known by the evaluator but not reachable with exhaustive search. A first instance of such algorithms has been proposed at Eurocrypt 2013. In this paper, we propose a new tool for rank estimation that is conceptually simpler and much more efficient than this previous proposal. It allows approximating the key rank of (128-bit, 256-bit) symmetric keys with very tight bounds (i.e. with less than one bit of error), almost instantaneously and with limited memory. It also scales nicely to larger (e.g. 1024-bit) key sizes, for which the previous algorithm was hardly applicable.

A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with \(\mathcal{O}(k)\) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity \(\mathcal{O}(\log k)\) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in \(\mathcal{O}(\log k)\) instead of \(\mathcal{O}(k)\) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo \(2^k\) directly on Boolean shares, with the same complexity \(\mathcal{O}(\log k)\) instead of \(\mathcal{O}(k)\). We prove the security of our new algorithm against first-order attacks. Our algorithm performs well in practice, as for \(k=64\) we obtain a \(23\,\%\) improvement compared to Goubin’s algorithm.

We apply the comb scheduler to implementations on Haswell, Intel’s latest microarchitecture, for a wide range of modes. We observe a drastic speed-up of factor 5 for NIST’s CBC, CFB, OFB and CMAC performing around 0.88 cpb. Surprisingly, contrary to the entire body of previous performance analysis, the throughput of the authenticated encryption (AE) mode CCM gets very close to that of GCM and OCB3, with about 1.64 cpb (vs. 1.63 cpb and 1.51 cpb, resp.), despite Haswell’s heavily improved binary field multiplication. This suggests CCM as an AE mode of choice as it is NIST-recommended, does not have any weak-key issues like GCM, and is royalty-free as opposed to OCB3. Among the CAESAR contestants, the comb scheduler significantly speeds up CLOC/SILC, JAMBU, and POET, with the mostly sequential nonce-misuse resistant design of POET, performing at 2.14 cpb, becoming faster than the well-parallelizable COPA.

Finally, this paper provides the first optimized AES-NI implementations for the novel AE modes OTR, CLOC/SILC, COBRA, POET, McOE-G, and Julius.

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

NXP Semiconductors and its academic partners challenged the cryptographic community with finding practical attacks on the block cipher they designed, PRINCE. Instead of trying to attack as many rounds as possible using attacks which are usually impractical despite being faster than brute-force, the challenge invites cryptographers to find practical attacks and encourages them to actually implement them. In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the 6 and 8-round categories — the highest for which winners were identified. Our first attacks rely on a meet-in-the-middle approach and break up to 10 rounds of the cipher. We also describe heuristic methods we used to find practical SAT-based and differential attacks.

Finally, we also present an analysis of the cycle structure of the internal rounds of PRINCE leading both to a low complexity distinguisher for 4-round PRINCE-core and an alternative representation of the cipher valid in particular contexts and which highlights, in this cases, a poor diffusion.

The application of the concept of linear cryptanalysis to the domain of key-less primitives is largely an open problem. In this paper we, for the first time, propose a model in which its application is meaningful for distinguishing block ciphers.

Combining our model with ideas from message modification and rebound-like approaches, we initiate a study of cryptographic primitives with respect to this new attack vector and choose the lightweight block cipher PRESENT as an example target. This leads to known-key distinguishers over up to 27 rounds, whereas the best previous result is up to 18 rounds in the chosen-key model.

ICEPOLE is a CAESAR candidate with the intermediate level of robustness under nonce misuse circumstances in the original document. In particular, it was claimed that key recovery attack against ICEPOLE is impossible in the case of nonce misuse. ICEPOLE is strong against the differential cryptanalysis and linear cryptanalysis. In this paper, we developed the differential-linear attacks against ICEPOLE when nonce is misused. Our attacks show that the state of ICEPOLE–128 and ICEPOLE–128a can be recovered with data complexity \(2^{46}\) and time complexity \(2^{46}\); the state of ICEPOLE–256a can be recovered with data complexity \(2^{60}\) and time complexity \(2^{60}\). For ICEPOLE–128a and ICEPOLE–256a, the secret key is recovered once the state is recovered. We experimentally verified the attacks against ICEPOLE–128 and ICEPOLE–128a.

In this article, we analyse the security of the authenticated encryption mode JAMBU, a submission to the CAESAR competition that remains currently unbroken. We show that the security claims of this candidate regarding its nonce-misuse resistance can be broken. More precisely, we explain a technique to guess in advance a ciphertext block corresponding to a plaintext that has never been queried before (nor its prefix), thus breaking the confidentiality of the scheme when the attacker can make encryption queries with the same nonce. Our attack is very practical as it requires only about \(2^{32}\) encryption queries and computations (instead of the \(2^{128}\) claimed by the designers). Our cryptanalysis has been fully implemented in order to verify our findings. Moreover, due to the small tag length of JAMBU, we show how this attack can be extended in the nonce-respecting scenario to break confidentiality in the adaptive chosen-ciphertext model (IND-CCA2) with \(2^{96}\) computations, with message prefixes not previously queried.

We present a forgery attack on Prøst-OTR in a related-key setting. Prøst is a family of authenticated encryption algorithms proposed as candidates in the currently ongoing CAESAR competition, and Prøst-OTR is one of the three variants of the Prøst design. The attack exploits how the Prøst permutation is used in an Even-Mansour construction in the Feistel-based OTR mode of operation. Given the ciphertext and tag for any two messages under two related keys K and \(K \oplus \varDelta \) with related nonces, we can forge the ciphertext and tag for a modified message under K. If we can query ciphertexts for chosen messages under \(K \oplus \varDelta \), we can achieve almost universal forgery for K. The computational complexity is negligible.

This paper analyses the cryptography used in the Open Smart Grid Protocol (OSGP). The authenticated encryption (AE) scheme deployed by OSGP is a non-standard composition of RC4 and a home-brewed MAC, the “OMA digest”.

We present several practical key-recovery attacks against the OMA digest. The first and basic variant can achieve this with a mere 13 queries to an OMA digest oracle and negligible time complexity. A more sophisticated version breaks the OMA digest with only 4 queries and a time complexity of about \(2^{25}\) simple operations. A different approach only requires one arbitrary valid plaintext-tag pair, and recovers the key in an average of 144 message verification queries, or one ciphertext-tag pair and 168 ciphertext verification queries.

Since the encryption key is derived from the key used by the OMA digest, our attacks break both confidentiality and authenticity of OSGP.

We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number \(q_e\) of queries to the underlying ideal block cipher, representing adversary’s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number \(q_c\) of plaintext/ciphertext pairs that is less than the entire codebook. For any such \(q_c\), we aim to determine the highest number of block-cipher queries \(q_e\) the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.

More concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and \(\kappa \)-bit keys:

The simplicity and widespread use of blockciphers based on the iterated Even–Mansour (EM) construction has sparked recent interest in the theoretical study of their security. Previous work has established their strong pseudorandom permutation and indifferentiability properties, with some matching lower bounds presented to demonstrate tightness. In this work we initiate the study of the EM ciphers under related-key attacks which, despite extensive prior work on EM ciphers, has received little attention. We show that the simplest one-round EM cipher is strong enough to achieve non-trivial levels of RKA security even under chosen-ciphertext attacks. This class, however, does not include the practically relevant case of offsetting keys by constants. We show that two rounds suffice to reach this level under chosen-plaintext attacks and that three rounds can boost security to resist chosen-ciphertext attacks. We also formalize how indifferentiability relates to RKA security, showing strong positive results despite counterexamples presented for indifferentiability in multi-stage games.

Sponge functions were originally proposed for hashing, but find increasingly more applications in keyed constructions, such as encryption and authentication. Depending on how the key is used we see two main types of keyed sponges in practice: inner- and outer-keyed. Earlier security bounds, mostly due to the well-known sponge indifferentiability result, guarantee a security level of c / 2 bits with c the capacity. We reconsider these two keyed sponge versions and derive improved bounds in the classical indistinguishability setting as well as in an extended setting where the adversary targets multiple instances at the same time. For cryptographically significant parameter values, the expected workload for an attacker to be successful in an n-target attack against the outer-keyed sponge is the minimum over \(2^k/n\) and \(2^c/\mu \) with k the key length and \(\mu \) the total maximum multiplicity. For the inner-keyed sponge this simplifies to \(2^k/\mu \) with maximum security if \(k=c\). The multiplicity is a characteristic of the data available to the attacker. It is at most twice the data complexity, but will be much smaller in practically relevant attack scenarios. We take a modular proof approach, and our indistinguishability bounds are the sum of a bound in the PRP model and a bound on the PRP-security of Even-Mansour type block ciphers in the ideal permutation model, where we obtain the latter result by using Patarin’s H-coefficient technique.

A constant of \(2^{22}\) appears in the security bounds of the Galois/Counter Mode of Operation, GCM. In this paper, we first develop an algorithm to generate nonces that have a high counter-collision probability. We show concrete examples of nonces with the counter-collision probability of about \(2^{20.75}/2^{128}\). This shows that the constant in the security bounds, \(2^{22}\), cannot be made smaller than \(2^{19.74}\) if the proof relies on “the sum bound.” We next show that it is possible to avoid using the sum bound, leading to improved security bounds of GCM. One of our improvements shows that the constant of \(2^{22}\) can be reduced to 32.

We propose pure OMD (p-OMD) as a new variant of the Offset Merkle-Damgård (OMD) authenticated encryption scheme. Our new scheme inherits all desirable security features of OMD while having a more compact structure and providing higher efficiency. The original OMD scheme, as submitted to the CAESAR competition, couples a single pass of a variant of the Merkle-Damgård (MD) iteration with the counter-based XOR MAC algorithm to provide privacy and authenticity. Our improved p-OMD scheme dispenses with the XOR MAC algorithm and is purely based on the MD iteration; hence, the name “pure” OMD. To process a message of \(\ell \) blocks and associated data of a blocks, OMD needs \(\ell +a+2\) calls to the compression function while p-OMD only requires \(\max \left\{ \ell , a\right\} +2\) calls. Therefore, for a typical case where \(\ell \ge a\), p-OMD makes just \(\ell +2\) calls to the compression function; that is, associated data is processed almost freely compared to OMD. We prove the security of p-OMD under the same standard assumption (pseudo-randomness of the compression function) as made in OMD; moreover, the security bound for p-OMD is the same as that of OMD, showing that the modifications made to boost the performance are without any loss of security.

We consider the generic design of a tweakable blockcipher from one or more evaluations of a classical blockcipher, in such a way that all input and output wires are of size n bits. As a first contribution, we show that any tweakable blockcipher with one primitive call and arbitrary linear pre- and postprocessing functions can be distinguished from an ideal one with an attack complexity of about \(2^{n/2}\). Next, we introduce the tweakable blockcipher \({\widetilde{F}}[1]\). It consists of one multiplication and one blockcipher call with tweak-dependent key, and achieves \(2^{2n/3}\) security. Finally, we introduce \({\widetilde{F}}[2]\), which makes two blockcipher calls, one of which with tweak-dependent key, and achieves optimal \(2^n\) security. Both schemes are more efficient than all existing beyond birthday bound tweakable blockciphers known to date, as long as one blockcipher key renewal is cheaper than one blockcipher evaluation plus one universal hash evaluation.

To be resistant against certain time-memory-data-tradeoff (TMDTO) attacks, a common rule of thumb says that the internal state size of a stream cipher should be at least twice the security parameter. As memory gates are usually the most area and power consuming components, this implies a sever limitation with respect to possible lightweight implementations.

In this article, we provide new methods to look for lightweight MDS matrices, and in particular involutory ones. By proving many new properties and equivalence classes for various MDS matrices constructions such as circulant, Hadamard, Cauchy and Hadamard-Cauchy, we exhibit new search algorithms that greatly reduce the search space and make lightweight MDS matrices of rather high dimension possible to find. We also explain why the choice of the irreducible polynomial might have a significant impact on the lightweightness, and in contrary to the classical belief, we show that the Hamming weight has no direct impact. Even though we focused our studies on involutory MDS matrices, we also obtained results for non-involutory MDS matrices. Overall, using Hadamard or Hadamard-Cauchy constructions, we provide the (involutory or non-involutory) MDS matrices with the least possible XOR gates for the classical dimensions \(4 \times 4\), \(8 \times 8\), \(16 \times 16\) and \(32 \times 32\) in \(\mathrm {GF}(2^4)\) and \(\mathrm {GF}(2^8)\). Compared to the best known matrices, some of our new candidates save up to 50 % on the amount of XOR gates required for an hardware implementation. Finally, our work indicates that involutory MDS matrices are really interesting building blocks for designers as they can be implemented with almost the same number of XOR gates as non-involutory MDS matrices, the latter being usually non-lightweight when the inverse matrix is required.

In this paper, we present a new classification of 4-bit optimal S-boxes. All optimal 4-bit S-boxes can be classified into 183 different categories, among which we specify 3 platinum categories. Under the design criteria of the PRESENT (or SPONGENT) S-box, there are 8064 different S-boxes up to adding constants before and after an S-box. The 8064 S-boxes belong to 3 different categories, we show that the S-box should be chosen from one out of the 3 categories or other categories for better resistance against linear cryptanalysis. Furthermore, we study in detail how the S-boxes in the 3 platinum categories influence the security of PRESENT, RECTANGLE and SPONGENT\(_{88}\) against differential and linear cryptanalysis. Our results show that the S-box selection has a great influence on the security of the schemes. For block ciphers or hash functions with 4-bit S-boxes as confusion layers and bit permutations as diffusion layers, designers can extend the range of S-box selection to the 3 platinum categories and select their S-box very carefully. For PRESENT, RECTANGLE and SPONGENT\(_{88}\) respectively, we get a set of potentially best/better S-box candidates from the 3 platinum categories. These potentially best/better S-boxes can be further investigated to see if they can be used to improve the security-performance tradeoff of the 3 cryptographic algorithms.

Rotational cryptanalysis is a probabilistic attack applicable to word oriented designs that use (almost) rotation-invariant constants. It is believed that the success probability of rotational cryptanalysis against ciphers and functions based on modular additions, rotations and XORs, can be computed only by counting the number of additions. We show that this simple formula is incorrect due to the invalid Markov cipher assumption used for computing the probability. More precisely, we show that chained modular additions used in ARX ciphers do not form a Markov chain with regards to rotational analysis, thus the rotational probability cannot be computed as a simple product of rotational probabilities of individual modular additions. We provide a precise value of the probability of such chains and give a new algorithm for computing the rotational probability of ARX ciphers. We use the algorithm to correct the rotational attacks on BLAKE2 and to provide valid rotational attacks against the simplified version of Skein.

We introduce internal differential boomerang distinguisher as a combination of internal differentials and classical boomerang distinguishers. The new boomerangs can be successful against cryptographic primitives having high-probability round-reduced internal differential characteristics. The internal differential technique, which follow the evolution of differences between parts of the state, is particularly meaningful for highly symmetric functions like the inner permutation Keccak- \(f\) of the hash functions defined in the future SHA-3 standard. We find internal differential and standard characteristics for three to four rounds of Keccak- \(f\), and with the use of the new technique, enhanced with a strong message modification, show practical distinguishers for this permutation. Namely, we need \(2^{12}\) queries to distinguish 7 rounds of the permutation starting from the first round, and approximately \(2^{18}\) queries to distinguish 8 rounds starting from the fourth round. Due to the exceptionally low complexities, all of our results have been completely verified with a computer implementation of the analysis.

RC4 is a stream cipher designed by Ron Rivest in 1987, and is widely used in various applications. WPA is one of these applications, where TKIP is used for a key generation procedure to avoid weak IV generated by WEP. In FSE 2014, two different attacks against WPA were proposed by Sen Gupta et al. and Paterson et al. Both focused correlations between the keystream bytes and the first 3 bytes of the RC4 key in WPA. In this paper, we focus on linear correlations between unknown internal state and the first 3 bytes of the RC4 key in both generic RC4 and WPA, where the first 3 bytes of the RC4 key is known in WPA. As a result, we could discover various new linear correlations, and prove these correlations theoretically.