Advances in Cryptology – CRYPTO 2016

The best existing bounds on the concrete security of key-alternating ciphers (Chen and Steinberger, EUROCRYPT ’14) are only asymptotically tight, and the quantitative gap with the best existing attacks remains numerically substantial for concrete parameters. Here, we prove exact bounds on the security of key-alternating ciphers and extend them to XOR cascades, the most efficient construction for key-length extension. Our bounds essentially match, for any possible query regime, the advantage achieved by the best existing attack.

Our treatment also extends to the multi-user regime. We show that the multi-user security of key-alternating ciphers and XOR cascades is very close to the single-user case, i.e., given enough rounds, it does not substantially decrease as the number of users increases. On the way, we also provide the first explicit treatment of multi-user security for key-length extension, which is particularly relevant given the significant security loss of block ciphers (even if ideal) in the multi-user setting.

The common denominator behind our results are new techniques for information-theoretic indistinguishability proofs that both extend and refine existing proof techniques like the H-coefficient method.

We propose the Synthetic Counter-in-Tweak (\(\mathsf {SCT}\)) mode, which turns a tweakable block cipher into a nonce-based authenticated encryption scheme (with associated data). The \(\mathsf {SCT}\) mode combines in a SIV-like manner a Wegman-Carter MAC inspired from \(\mathsf {PMAC}\) for the authentication part and a new counter-like mode for the encryption part, with the unusual property that the counter is applied on the tweak input of the underlying tweakable block cipher rather than on the plaintext input. Unlike many previous authenticated encryption modes, \(\mathsf {SCT}\) enjoys provable security beyond the birthday bound (and even up to roughly \(2^n\) tweakable block cipher calls, where n is the block length, when the tweak length is sufficiently large) in the nonce-respecting scenario where nonces are never repeated. In addition, \(\mathsf {SCT}\) ensures security up to the birthday bound even when nonces are reused, in the strong nonce-misuse resistance sense (MRAE) of Rogaway and Shrimpton (EUROCRYPT 2006). To the best of our knowledge, this is the first authenticated encryption mode that provides at the same time close-to-optimal security in the nonce-respecting scenario and birthday-bound security for the nonce-misuse scenario. While two passes are necessary to achieve MRAE-security, our mode enjoys a number of desirable features: it is simple, parallelizable, it requires the encryption direction only, it is particularly efficient for small messages compared to other nonce-misuse resistant schemes (no precomputation is required) and it allows incremental update of associated data.

We present \(\mathrm {XPX}\), a tweakable blockcipher based on a single permutation \(P\). On input of a tweak \((t_{11},t_{12},t_{21},t_{22})\in \mathcal {T}\) and a message m, it outputs ciphertext \(c=P(m\oplus \varDelta _1)\oplus \varDelta _2\), where \(\varDelta _1=t_{11}k\oplus t_{12}P(k)\) and \(\varDelta _2=t_{21}k\oplus t_{22}P(k)\). Here, the tweak space \(\mathcal {T}\) is required to satisfy a certain set of trivial conditions (such as \((0,0,0,0)\not \in \mathcal {T}\)). We prove that \(\mathrm {XPX}\) with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of \(\mathrm {XPX}\) under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that \(\mathrm {XPX}\) achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of \(\mathcal {T}\). For instance, if \(t_{12}, t_{22}\ne 0\) and \((t_{21}, t_{22})\ne (0,1)\) for all tweaks, \(\mathrm {XPX}\) is XOR-related-key secure. \(\mathrm {XPX}\) generalizes Even-Mansour (\(\mathrm {EM}\)), but also Rogaway’s \(\mathrm {XEX}\) based on \(\mathrm {EM}\), and various other tweakable blockciphers. As such, \(\mathrm {XPX}\) finds a wide range of applications. We show how our results on \(\mathrm {XPX}\) directly imply related-key security of the authenticated encryption schemes Prøst-\(\mathrm {COPA}\) and \(\mathrm {Minalpher}\), and how a straightforward adjustment to the MAC function \(\mathrm {Chaskey}\) and to keyed Sponges makes them provably related-key secure.

We prove that a balanced 8-round Feistel network is indifferentiable from a random permutation, improving on previous 10-round results by Dachman-Soled et al. and Dai et al. Our simulator achieves security \(O(q^8/2^n)\), similarly to the security of Dai et al. For further comparison, Dachman-Soled et al. achieve security \(O(q^{12}/2^n)\), while the original 14-round simulator of Holenstein et al. achieves security \(O(q^{10}/2^n)\).

We propose a nonce-based MAC construction called EWCDM (Encrypted Wegman-Carter with Davies-Meyer), based on an almost xor-universal hash function and a block cipher, with the following properties: (i) it is simple and efficient, requiring only two calls to the block cipher, one of which can be carried out in parallel to the hash function computation; (ii) it is provably secure beyond the birthday bound when nonces are not reused; (iii) it provably retains security up to the birthday bound in case of nonce misuse. Our construction is a simple modification of the Encrypted Wegman-Carter construction, which is known to achieve only (i) and (iii) when based on a block cipher. Underlying our new construction is a new PRP-to-PRF conversion method coined Encrypted Davies-Meyer, which turns a pair of secret random permutations into a function which is provably indistinguishable from a perfectly random function up to at least \(2^{2n/3}\) queries, where n is the bit-length of the domain of the permutations.

This directly affects the asymptotic security of the bootstrappable homomorphic encryption schemes LTV and YASHE which rely on a mildly overstretched NTRU assumption: the subfield lattice attack runs in sub-exponential time \(2^{O(\lambda /\log ^{1/3}\lambda )}\) invalidating the security claim of \(2^{\varTheta (\lambda )}\). The effect is more dramatic on GGH-like Multilinear Maps: this attack can run in polynomial time without encodings of zero nor the zero-testing parameter, yet requiring an additional quantum step to recover the secret parameters exactly.

We present a novel cryptanalysis of the Algebraic Eraser primitive. This key agreement scheme, based on techniques from permutation groups, matrix groups and braid groups, is proposed as an underlying technology for ISO/IEC 29167-20, which is intended for authentication of RFID tags. SecureRF, the company owning the trademark Algebraic Eraser, markets it as suitable in general for lightweight environments such as RFID tags and other IoT applications. Our attack is practical on standard hardware: for parameter sizes corresponding to claimed 128-bit security, our implementation recovers the shared key using less than 8 CPU hours, and less than 64 MB of memory.

We present a multi-key fully homomorphic encryption scheme that supports an unbounded number of homomorphic operations for an unbounded number of parties. Namely, it allows to perform arbitrarily many computational steps on inputs encrypted by an a-priori unbounded (polynomial) number of parties. Inputs from new parties can be introduced into the computation dynamically, so the final set of parties needs not be known ahead of time. Furthermore, the length of the ciphertexts, as well as the space complexity of an atomic homomorphic operation, grow only linearly with the current number of parties.

Prior works either supported only an a-priori bounded number of parties (López-Alt, Tromer and Vaikuntanthan, STOC ’12), or only supported single-hop evaluation where all inputs need to be known before the computation starts (Clear and McGoldrick, Crypto ’15, Mukherjee and Wichs, Eurocrypt ’16). In all aforementioned works, the ciphertext length grew at least quadratically with the number of parties.

Technically, our starting point is the LWE-based approach of previous works. Our result is achieved via a careful use of Gentry’s bootstrapping technique, tailored to the specific scheme. Our hardness assumption is that the scheme of Mukherjee and Wichs is circular secure (and thus bootstrappable). A leveled scheme can be achieved under standard LWE.

Dodis, Kalai and Lovett (STOC 2009) initiated the study of the Learning Parity with Noise (LPN) problem with (static) exponentially hard-to-invert auxiliary input. In particular, they showed that under a new assumption (called Learning Subspace with Noise) the above is quasi-polynomially hard in the high (polynomially close to uniform) noise regime.

Inspired by the “sampling from subspace” technique by Yu (eprint 2009/467) and Goldwasser et al. (ITCS 2010), we show that standard LPN can work in a mode (reducible to itself) where the constant-noise LPN (by sampling its matrix from a random subspace) is robust against sub-exponentially hard-to-invert auxiliary input with comparable security to the underlying LPN. Plugging this into the framework of [DKL09], we obtain the same applications as considered in [DKL09] (i.e., CPA/CCA secure symmetric encryption schemes, average-case obfuscators, reusable and robust extractors) with resilience to a more general class of leakages, improved efficiency and better security under standard assumptions.

As a main contribution, under constant-noise LPN with certain sub-exponential hardness (i.e., \(2^{\omega (n^{1/2})}\) for secret size n) we obtain a variant of the LPN with security on poly-logarithmic entropy sources, which in turn implies CPA/CCA secure public-key encryption (PKE) schemes and oblivious transfer (OT) protocols. Prior to this, basing PKE and OT on constant-noise LPN had been an open problem since Alekhnovich’s work (FOCS 2003).

We initiate the study of multi-user (mu) security of authenticated encryption (AE) schemes as a way to rigorously formulate, and answer, questions about the “randomized nonce” mechanism proposed for the use of the AE scheme GCM in TLS 1.3. We (1) Give definitions of mu ind (indistinguishability) and mu kr (key recovery) security for AE (2) Characterize the intent of nonce randomization as being improved mu security as a defense against mass surveillance (3) Cast the method as a (new) AE scheme RGCM (4) Analyze and compare the mu security of both GCM and RGCM in the model where the underlying block cipher is ideal, showing that the mu security of the latter is indeed superior in many practical contexts to that of the former, and (5) Propose an alternative AE scheme XGCM having the same efficiency as RGCM but better mu security and a more simple and modular design.

Application Programming Interfaces (APIs) to cryptographic tokens like smartcards and Hardware Security Modules (HSMs) provide users with commands to manage and use cryptographic keys stored on trusted hardware. Their design is mainly guided by industrial standards with only informal security promises.

In this paper we propose cryptographic models for the security of such APIs. The key feature of our approach is that it enables modular analysis. Specifically, we show that a secure cryptographic API can be obtained by combining a secure API for key-management together with secure implementations of, for instance, encryption or message authentication. Our models are the first to provide such compositional guarantees while considering realistic adversaries that can adaptively corrupt keys stored on tokens. We also provide a proof of concept instantiation (from a deterministic authenticated-encryption scheme) of the key-management portion of cryptographic API.

We formally define the primitive of encryption switching protocol (ESP), allowing to switch between two encryption schemes. Intuitively, this two-party protocol converts given ciphertexts from one scheme into ciphertexts of the same messages under the other scheme, for any polynomial number of switches, in any direction. Although ESP is a special kind of two-party computation protocol, it turns out that ESP implies general two-party computation (2-PC) under natural conditions. In particular, our new paradigm is tailored to the evaluation of functions over rings. Indeed, assuming the compatibility of two additively and multiplicatively homomorphic encryption schemes, switching ciphertexts makes it possible to efficiently reconcile the two internal laws. Since no such pair of public-key encryption schemes appeared in the literature, except for the non-interactive case of fully homomorphic encryption which still remains prohibitive in practice, we build the first multiplicatively homomorphic ElGamal-like encryption scheme over \((\mathbb {Z}_n,\times )\) as a complement to the Paillier encryption scheme over \((\mathbb {Z}_n,+)\), where n is a strong RSA modulus. Eventually, we also instantiate secure ESPs between the two schemes, in front of malicious adversaries. This enhancement relies on a new technique called refreshable twin ciphertext pool, which we show being of independent interest. We additionally prove this is enough to argue the security of our general 2-PC protocol against malicious adversaries.

Suppose Alice wishes to send a message to Bob privately over an untrusted channel. Cryptographers have developed a whole suite of tools to accomplish this task, with a wide variety of notions of security, setup assumptions, and running times. However, almost all prior work on this topic made a seemingly innocent assumption: that Alice has access to a trusted computer with a proper implementation of the protocol. The Snowden revelations show us that, in fact, powerful adversaries can and will corrupt users’ machines in order to compromise their security. And, (presumably) accidental vulnerabilities are regularly found in popular cryptographic software, showing that users cannot even trust implementations that were created honestly. This leads to the following (seemingly absurd) question: “Can Alice securely send a message to Bob even if she cannot trust her own computer?!”

Indeed, we find a rich structure of solutions that vary in efficiency, security, and setup assumptions, in close analogy with message transmission in the classical setting. Our strongest and most important result shows a protocol that achieves interactive, concurrent CCA-secure message transmission with a reverse firewall—i.e., CCA-secure message transmission on a possibly compromised machine! Surprisingly, this protocol is quite efficient and simple, requiring only four rounds and a small constant number of public-key operations for each party. It could easily be used in practice. Behind this result is a technical composition theorem that shows how key agreement with a sufficiently secure reverse firewall can be used to construct a message-transmission protocol with its own secure reverse firewall.

Inspired by the Dual EC DBRG incident, Dodis et al. (Eurocrypt 2015) initiated the formal study of backdoored PRGs, showing that backdoored PRGs are equivalent to public key encryption schemes, giving constructions for backdoored PRGs (BPRGs), and showing how BPRGs can be “immunised” by careful post-processing of their outputs. In this paper, we continue the foundational line of work initiated by Dodis et al., providing both positive and negative results.

We first revisit the backdoored PRG setting of Dodis et al., showing that PRGs can be more strongly backdoored than was previously envisaged. Specifically, we give efficient constructions of BPRGs for which, given a single generator output, Big Brother can recover the initial state and, therefore, all outputs of the BPRG. Moreover, our constructions are forward-secure in the traditional sense for a PRG, resolving an open question of Dodis et al. in the negative.

We then turn to the question of the effectiveness of backdoors in robust PRNGs with input (c.f. Dodis et al., ACM-CCS 2013): generators in which the state can be regularly refreshed using an entropy source, and in which, provided sufficient entropy has been made available since the last refresh, the outputs will appear pseudorandom. The presence of a refresh procedure might suggest that Big Brother could be defeated, since he would not be able to predict the values of the PRNG state backwards or forwards through the high-entropy refreshes. Unfortunately, we show that this intuition is not correct: we are also able to construct robust PRNGs with input that are backdoored in a backwards sense. Namely, given a single output, Big Brother is able to rewind through a number of refresh operations to earlier “phases”, and recover all the generator’s outputs in those earlier phases.

Finally, and ending on a positive note, we give an impossibility result: we provide a bound on the number of previous phases that Big Brother can compromise as a function of the state-size of the generator: smaller states provide more limited backdooring opportunities for Big Brother.

MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan, and is recognized internationally as a European NESSIE-recommended cipher and an ISO standard. After almost 20 years of unsuccessful cryptanalytic attempts, a first attack on the full MISTY1 was presented at CRYPTO 2015 by Yosuke Todo. The attack, using a new technique called division property, requires almost the full codebook and has time complexity of \(2^{107.3}\) encryptions.

In this paper we present a new attack on the full MISTY1. It is based on Todo’s division property, along with a variety of refined key-recovery techniques. Our attack requires almost the full codebook (like Todo’s attack), but allows to retrieve 49 bits of the secret key in time complexity of only \(2^{64}\) encryptions, and the full key in time complexity of \(2^{69.5}\) encryptions.

While our attack is clearly impractical due to its large data complexity, it shows that MISTY1 provides security of only \(2^{70}\) — significantly less than what was considered before.

At Eurocrypt 2016, Méaux et al. proposed FLIP, a new family of stream ciphers intended for use in Fully Homomorphic Encryption systems. Unlike its competitors which either have a low initial noise that grows at each successive encryption, or a high constant noise, the FLIP family of ciphers achieves a low constant noise thanks to a new construction called filter permutator.

In this paper, we present an attack on the early version of FLIP that exploits the structure of the filter function and the constant internal state of the cipher. Applying this attack to the two instantiations proposed by Méaux et al. allows for a key recovery in \(2^{54}\) basic operations (resp. \(2^{68}\)), compared to the claimed security of \(2^{80}\) (resp. \(2^{128}\)).

We introduce the notion of an Extremely Lossy Function (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a polynomial-sized image. Moreover, for any efficient adversary, for a sufficiently large polynomial r (necessarily chosen to be larger than the running time of the adversary), the adversary cannot distinguish the injective case from the case of image size r.

Under the Decisional Diffie-Hellman (DDH) assumption, we present a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. More concretely, there is an evaluation algorithm \(\mathsf{Eval}\) with a single bit of output, such that if an input \(w\in \{0,1\}^n\) is shared into \((w^0,w^1)\), then for any deterministic branching program P of size S we have that \(\mathsf{Eval}(P,w^0)\oplus \mathsf{Eval}(P,w^1)=P(w)\) except with at most \(\delta \) failure probability. The running time of the sharing algorithm is polynomial in n and the security parameter \(\lambda \), and that of \(\mathsf{Eval}\) is polynomial in \(S,\lambda \), and \(1/\delta \). This applies as a special case to boolean formulas of size S or boolean circuits of depth \(\log S\). We also present a public-key variant that enables homomorphic computation on inputs contributed by multiple clients.

The above result implies the following DDH-based applications:

Prior to our work, similar results could only be achieved using fully homomorphic encryption. We hope that our approach will lead to more practical alternatives to known fully homomorphic encryption schemes in the context of low-communication secure computation.

We introduce a new variant of the number field sieve algorithm for discrete logarithms in \(\mathbb {F}_{p^n}\) called exTNFS. The most important modification is done in the polynomial selection step, which determines the cost of the whole algorithm: if one knows how to select good polynomials to tackle discrete logarithms in \(\mathbb {F}_{p^\kappa }\), exTNFS allows to use this method when tackling \(\mathbb {F}_{p^{\eta \kappa }}\) whenever \(\gcd (\eta ,\kappa )=1\). This simple fact has consequences on the asymptotic complexity of NFS in the medium prime case, where the complexity is reduced from \(L_Q(1/3,\root 3 \of {96/9})\) to \(L_Q(1/3,\root 3 \of {48/9})\), \(Q=p^n\), respectively from \(L_Q(1/3,2.15)\) to \(L_Q(1/3,1.71)\) if multiple number fields are used. On the practical side, exTNFS can be used when \(n=6\) and \(n=12\) and this requires to updating the keysizes used for the associated pairing-based cryptosystems.

We propose a new suite of algorithms that significantly improve the performance of supersingular isogeny Diffie-Hellman (SIDH) key exchange. Subsequently, we present a full-fledged implementation of SIDH that is geared towards the 128-bit quantum and 192-bit classical security levels. Our library is the first constant-time SIDH implementation and is up to 2.9 times faster than the previous best (non-constant-time) SIDH software. The high speeds in this paper are driven by compact, inversion-free point and isogeny arithmetic and fast SIDH-tailored field arithmetic: on an Intel Haswell processor, generating ephemeral public keys takes 46 million cycles for Alice and 52 million cycles for Bob, while computing the shared secret takes 44 million and 50 million cycles, respectively. The size of public keys is only 564 bytes, which is significantly smaller than most of the popular post-quantum key exchange alternatives. Ultimately, the size and speed of our software illustrates the strong potential of SIDH as a post-quantum key exchange candidate and we hope that these results encourage a wider cryptanalytic effort.

It has been proved in Eurocrypt 2016 by Sun et al. that if the details of the S-boxes are not exploited, an impossible differential and a zero-correlation linear hull can extend over at most 4 rounds of the AES. This paper concentrates on distinguishing properties of AES-like SPN ciphers by investigating the details of both the underlying S-boxes and the MDS matrices, and illustrates some new insights on the security of these schemes. Firstly, we construct several types of 5-round zero-correlation linear hulls for AES-like ciphers that adopt identical S-boxes to construct the round function and that have two identical elements in a column of the inverse of their MDS matrices. We then use these linear hulls to construct 5-round integrals provided that the difference of two sub-key bytes is known. Furthermore, we prove that we can always distinguish 5 rounds of such ciphers from random permutations even when the difference of the sub-keys is unknown. Secondly, the constraints for the S-boxes and special property of the MDS matrices can be removed if the cipher is used as a building block of the Miyaguchi-Preneel hash function. As an example, we construct two types of 5-round distinguishers for the hash function Whirlpool. Finally, we show that, in the chosen-ciphertext mode, there exist some nontrivial distinguishers for 5-round AES. To the best of our knowledge, this is the longest distinguisher for the round-reduced AES in the secret-key setting. Since the 5-round distinguisher for the AES can only be constructed in the chosen-ciphertext mode, the security margin for the round-reduced AES under the chosen-plaintext attack may be different from that under the chosen-ciphertext attack.

In this paper we consider the fundamental question of optimizing finite field multiplications with one fixed element. Surprisingly, this question did not receive much attention previously. We investigate which field representation, that is which choice of basis, allows for an optimal implementation. Here, the efficiency of the multiplication is measured in terms of the number of XOR operations needed to implement the multiplication. While our results are potentially of larger interest, we focus on a particular application in the second part of our paper. Here we construct new MDS matrices which outperform or are on par with all previous results when focusing on a round-based hardware implementation.