International Association
for Cryptologic Research

Event date: 18 March to 20 March 2020
Submission deadline: 1 November 2019
Notification: 15 November 2019

Threshold Implementations (TI) are secure algorithmic countermeasures against side-channel attacks in the form of differential power analysis. The strength of TI lies in its minimal algorithmic requirements. These requirements have been studied over more than 10 years and many efficient implementations for symmetric primitives have been proposed. Thus, over the years the practice of protecting implementations matured, however, the theory behind threshold implementations remained the same. In this work, we revise this theory by looking at the properties of correctness, non-completeness, and uniformity as a composable security model. We prove that this model provides first-order and higher-order univariate security in the glitch-robust probing model which lets us expand the theoretic framework of TI. We first provide a link between uniformity and the notion of non-interference, a known composable security notion building out the probing model. We then relax the notion of non-completeness which helps the design of secure expansion and compression functions. Lastly, we provide generalisations of the threshold notions to allow for general secret sharing schemes and provide examples of how different sharing schemes affect the security and efficiency of the countermeasure.

Highly efficient encryption and authentication of short messages is an essential requirement for enabling security in constrained scenarios such as the CAN FD in automotive systems (max. message size 64 bytes), massive IoT, critical communication domains of 5G, and Narrowband IoT, to mention a few. In addition, one of the NIST lightweight cryptography project requirements is that AEAD schemes shall be “optimized to be efficient for short messages (e.g., as short as 8 bytes)”.

In this work we introduce and formalize a novel primitive in symmetric cryptography called a forkcipher. A forkcipher is a keyed function expanding a fixed-length input to a fixed-length output. We define its security as indistinguishability under chosen ciphertext attack. We give a generic construction validation via the new iterate-fork-iterate design paradigm.

We then propose ForkSkinny as a concrete forkcipher instance with a public tweak and based on SKINNY: a tweakable lightweight block cipher constructed using the TWEAKEY framework. We conduct extensive cryptanalysis of ForkSkinny against classical and structure-specific attacks.

We demonstrate the applicability of forkciphers by designing three new provably-secure, nonce-based AEAD modes which offer performance and security tradeoffs and are optimized for efficiency of very short messages. Considering a reference block size of 16 bytes, and ignoring possible hardware optimizations, our new AEAD schemes beat the best SKINNY-based AEAD modes. More generally, we show forkciphers are suited for lightweight applications dealing with predominately short messages, while at the same time allowing handling arbitrary messages sizes.

Furthermore, our hardware implementation results show that when we exploit the inherent parallelism of ForkSkinny we achieve the best performance when directly compared with the most efficient mode instantiated with the SKINNY block cipher.

Elliptic curves are typically defined by Weierstrass equations. Given a kernel, the well-known Velu’s formula shows how to explicitly write down an isogeny between Weierstrass curves. However, it is not clear how to do the same on other forms of elliptic curves without isomorphisms mapping to and from the Weierstrass form. Previous papers have shown some isogeny formulas for (twisted) Edwards, Huff, and Montgomery forms of elliptic curves. Continuing this line of work, this paper derives an explicit formula for isogenies between elliptic curves in (twisted) Hessian form.

In order to study the resistance of a block cipher against boomerang attacks, a tool called the Boomerang Connectivity Table (BCT) for S-boxes was recently introduced. Very little is known today about the properties of this table especially for bijective S-boxes defined for $n$ variables with $n\equiv 0 \mod{4}$. In this work we study the boomerang uniformity of some popular constructions used for building large S-boxes, e.g. for 8 variables, from smaller ones. We show that the BCTs of all the studied constructions have abnormally high values in some positions. This remark permits us in some cases to link the boomerang properties of an S-box with other well-known cryptanalytic techniques on such constructions while in other cases it leads to the discovery of new ones. A surprising outcome concerns notably the Feistel and MISTY networks. While these two structures are very similar, their boomerang uniformity can be very different. In a second time, we investigate the boomerang uniformity under EA-equivalence for Gold and the inverse function (as used respectively in MPC-friendly ciphers and the AES) and we prove that the boomerang uniformity is EA-invariant in these cases. Finally, we present an algorithm for inverting a given BCT and provide experimental results on the size of the BCT-equivalence classes for some $4$ and $8$-bit S-boxes.

At CRYPTO 2017, Rosca et al. introduce a new variant of the Learning With Errors (LWE) problem, called the Middle-Product LWE (MP-LWE). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the MP-LWE problem. In this paper, we propose a deterministic variant of their encryption scheme, which does not need Gaussian sampling and is thus simpler than the original one. Still, it has the same quasi-optimal asymptotic key and ciphertext sizes. The main ingredient for this purpose is the Learning With Rounding (LWR) problem which has already been used to derandomize LWE type encryption. The hardness of our scheme is based on a new assumption called Middle-Product Computational Learning With Rounding, an adaption of the computational LWR problem over rings, introduced by Chen et al. at ASIACRYPT 2018. We prove that this new assumption is as hard as the decisional version of MP-LWE and thus benefits from worst-case to average-case hardness guarantees.

We study the security of symmetric primitives against key-correlated attacks (KCA), whereby an adversary can arbitrarily correlate keys, messages, and ciphertexts. Security against KCA is required whenever a primitive should securely encrypt key-dependent data, even when it is used under related keys. KCA is a strengthening of the previously considered notions of related-key attack (RKA) and key-dependent message (KDM) security. This strengthening is strict, as we show that 2-round Even–Mansour fails to be KCA secure even though it is both RKA and KDM secure. We provide feasibility results in the ideal-cipher model for KCAs and show that 3-round Even–Mansour is KCA secure under key offsets in the random-permutation model. We also give a natural transformation that converts any authenticated encryption scheme to a KCA-secure one in the random-oracle model. Conceptually, our results allow for a unified treatment of RKA and KDM security in idealized models of computation.

In different contexts such as filtered LFSR, Goldreich's PRG, and FLIP stream ciphers, the security of a cryptographic primitive mostly depends on the algebraic properties of one Boolean function. Since the Seventies, more and more efficient attacks have been exhibited in this context, related to more and more general algebraic properties, such as the degree, the algebraic immunity, and finally, the fast algebraic immunity. Once the properties to estimate the attack complexities are identified, it remains to determine the exact parameters of interesting families of functions with these properties. Then, these functions can be combined in secondary constructions to guarantee the good algebraic properties of a main function. In particular, the family of symmetric functions, and more precisely the subclass of majority functions, has been intensively studied in the area of cryptography, because of their practical advantages and good properties.

The degree of all these functions is known, and they have been proven to reach the optimal algebraic immunity, but still very few is known about its fast algebraic immunity. For a function in $n=2^m+j$ variables, an upper bound is known for all $m$ and $j$, proving that these functions do not reach the optimal fast algebraic immunity. However, the exact fast algebraic immunity is known only for very few families indexed by $j$, where the parameter is exhibited for all members of the family since $m$ is big enough. Recent works gave exact values for $j=0$ and $j=1$ (in the first case), and for $j=2$ and $j=3$ with $m\geq2$ (in the second case). In this work, we determine the exact fast algebraic immunity for all possible values of $j$, for all member of the family assuming $m\geq 1+\log_2(j+1)$.

Two of the most sought-after properties of Multi-party Computation (MPC) protocols are fairness and guaranteed output delivery (GOD), the latter also referred to as robustness. Achieving both, however, brings in the necessary requirement of malicious-minority. In a generalised adversarial setting where the adversary is allowed to corrupt both actively and passively, the necessary bound for a $n$-party fair or robust protocol turns out to be $t_a + t_p < n$, where $t_a,t_p$ denote the threshold for active and passive corruption with the latter subsuming the former. Subsuming the malicious-minority as a boundary special case, this setting, denoted as dynamic corruption, opens up a range of possible corruption scenarios for the adversary. While dynamic corruption includes the entire range of thresholds for $(t_a,t_p)$ starting from $(\lceil \frac{n}{2} \rceil - 1 , \lfloor \frac{n}{2} \rfloor)$ to $(0,n-1)$, the boundary corruption restricts the adversary only to the boundary cases of $(\lceil \frac{n}{2} \rceil - 1, \lfloor \frac{n}{2} \rfloor)$ and $(0,n-1)$. Notably, both corruption settings empower an adversary to control majority of the parties, yet ensuring the count on active corruption never goes beyond $\lceil \frac{n}{2} \rceil - 1$.

We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, $\lceil \frac{n}{2} \rceil + 1$ rounds are necessary and sufficient for fair as well as robust MPC tolerating dynamic corruption. The non-constant barrier raised by dynamic corruption can be sailed through for a boundary adversary. The round complexity of $3$ and $4$ is necessary and sufficient for fair and GOD protocols respectively, with the latter having an exception of allowing $3$ round protocols in the presence of a single active corruption. While all our lower bounds assume pair-wise private and broadcast channels and are resilient to the presence of both public (CRS) and private (PKI) setup, our upper bounds are broadcast-only and assume only public setup. The traditional and popular setting of malicious-minority, being restricted compared to both dynamic and boundary setting, requires $3$ and $2$ rounds in the presence of public and private setup respectively for both fair as well as GOD protocols.

The Fiat-Shamir transform is an incredibly powerful technique that uses a suitable hash function to reduce the interaction of general public-coin protocols. Unfortunately, there are known counterexamples showing that this methodology may not be sound (no matter what concrete hash function is used). Still, these counterexamples are somewhat unsatisfying, as the underlying protocols were specifically tailored to make Fiat-Shamir fail. This raises the question of whether this transform is sound when applied to natural protocols.

One of the most important protocol for which we would like to reduce interaction is Kilian’s four-message argument system for all of NP, based on collision resistant hash functions (CRHF) and probabilistically checkable proofs (PCPs). Indeed, an application of the Fiat-Shamir transform to Kilian's protocol is at the heart of both theoretical results (e.g., Micali's CS proofs) as well as leading practical approaches of highly efficient non-interactive proof-systems (e.g., SNARKs and STARKs).

In this work, we show significant obstacles to establishing soundness of (what we refer to as) the "Fiat-Shamir-Kilian-Micali" (FSKM) protocol. More specifically:

- We construct a (contrived) CRHF for which FSKM is unsound for a very large class of PCPs and for any Fiat-Shamir hash function. The collision-resistance of our CRHF relies on very strong but plausible cryptographic assumptions. The statement is "tight" in the following sense: any PCP outside the scope of our result trivially implies a SNARK, eliminating the need for FSKM in the first place.

- Second, we consider a known extension of Kilian’s protocol to an interactive variant of PCPs called probabilistically checkable interactive proofs (PCIP) (also known as interactive oracle proofs or IOPs). We construct a particular (contrived) PCIP for NP for which the FSKM protocol is unsound no matter what CRHF and Fiat-Shamir hash function is used. This result is unconditional (i.e., does not rely on any cryptographic assumptions).

Put together, our results show that the soundness of FSKM must rely on some special structure of both the CRHF and PCP that underlie Kilian's protocol. We believe these negative results may cast light on how to securely instantiate the FSKM protocol by a synergistic choice of the PCP, CRHF, and Fiat-Shamir hash function.

Modern cryptography requires the ability to securely generate pseudorandom numbers. However, despite decades of work on side channel attacks, there is little discussion of their application to pseudorandom number generators (PRGs). In this work we set out to address this gap, empirically evaluating the side channel resistance of common PRG implementations.

We find that hard-learned lessons about side channel leakage from encryption primitives have not been applied to PRGs, at all levels of abstraction. At the design level, the NIST-recommended CTR_DRBG design does not have forward security if an attacker is able to compromise the state via a side-channel attack. At the primitive level, popular implementations of CTR_DRBG such as OpenSSL's FIPS module and NetBSD's kernel use leaky T-table AES as their underlying block cipher, enabling cache side-channel attacks. Finally, we find that many implementations make parameter choices that enable an attacker to fully exploit the side-channel attack in a realistic scenario and recover secret keys from TLS connections.

We empirically demonstrate our attack in two scenarios. In the first, we carry out an asynchronous cache attack that recovers the private state from vulnerable CTR_DRBG implementations under realistic conditions to recover long-term authentication keys when the attacker is a party in the TLS connection. In the second scenario, we show that an attacker can exploit the high temporal resolution provided by Intel SGX to carry out a blind attack to recover CTR\_DRBG's state within three AES encryptions, without viewing output, and thus to decrypt passively collected TLS connections from the victim.

Mix-nets constructed from homomorphic cryptosystems can be generalized to process lists of ciphertexts as units and use different public keys for different parts of such lists. We present a number of blackbox constructions that enriches the set of operations provided by such mix-nets. The constructions are simple, fully practical, and eliminates the need for some specialized protocols.

The binomial $B(x) = x^3 + \beta x^{36}$ (where $\beta$ is primitive in $\mathbb{F}_{2^4}$) over $\mathbb{F}_{2^{10}}$ is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZ-equivalent to a power function, and has remained unclassified into any infinite family of APN functions since its discovery in 2006. We generalize this binomial to an infinite family of APN quadrinomials of the form $x^3 + a (x^{2^i+1})^{2^k} + b x^{3 \cdot 2^m} + c (x^{2^{i+m}+2^m})^{2^k}$ from which $B(x)$ can be obtained by setting $a = \beta$, $b = c = 0$, $i = 3$, $k = 2$. We show that for any dimension $n = 2m$ with $m$ odd and $3 \nmid m$, setting $(a,b,c) = (\beta, \beta^2, 1)$ and $i = m-2$ or $i = (m-2)^{-1} \mod n$ yields an APN function, and verify that for $n = 10$ the quadrinomials obtained in this way for $i = m-2$ and $i = (m-2)^{-1} \mod n$ are CCZ-inequivalent to each other, to $B(x)$, and to any other known APN function over $\mathbb{F}_{2^{10}}$.

In the area of cloud computing, judging the fulfillment of service-level agreements on a technical level is gaining more and more importance. To support this we introduce privacy preserving set relations as inclusiveness and disjointness based on Bloom filters. We propose to compose them in a slightly different way by applying a keyed hash function. Besides discussing the correctness of the set relations, we analyze how this impacts the privacy of the sets content as well as providing privacy on the sets cardinality. Indeed, our solution proposes to bring another layer of privacy on the sizes. We are in particular interested how the overlapping bits of a Bloom filter impact the privacy level of our approach. We concretely apply our solution to a use case of cloud security audit on access control and present our results with real-world parameters.

In this article, we propose two new families of very lightweight and efficient authenticated encryption with associated data (AEAD) modes, Romulus and Remus, that provide security beyond the birthday bound with respect to the block-length $n$. The former uses a tweakable block cipher (TBC) as internal primitive and can be proven secure in the standard model. The later uses a block cipher (BC) as internal primitive and can be proven secure in the ideal cipher model. Both our modes allow to switch very easily from nonce-respecting to nonce-misuse scenario.

Previous constructions, such as ThetaCB, are quite computationally efficient, yet needing a large memory for implementation, which makes them unsuitable for platforms where lightweight cryptography should play a key role. Romulus and Remus break this barrier by introducing a new architecture evolved from a BC mode COFB. They achieve the best of what can be possible with TBC -- the optimal computational efficiency (rate-1 operation) and the minimum state size of a TBC mode (i.e., $(n+t)$-bit for $n$-bit block, $t$-bit tweak TBC), with almost equivalent provable security as ThetaCB. Actually, our comparisons show that both our designs present superior performances when compared to all other recent lightweight AEAD modes, being BC-based, TBC-based or sponge-based, in the nonce-respecting or nonce-misuse scenario.

We eventually describe how to instantiate Romulus and Remus modes using the Skinny lightweight tweakable block cipher proposed at CRYPTO 2016, including the hardware implementation results.

SNOW 3G is a stream cipher designed in 2006 by ETSI/SAGE, serving in 3GPP as one of the standard algorithms for data confidentiality and integrity protection. It is also included in the 4G LTE standard. In this paper we derive vectorized linear approximations of the finite state machine of SNOW 3G. In particular, we show one 24-bit approximation with a bias around $2^{-37}$ and one byte-oriented approximation with a bias around $2^{-40}$. We then use the approximations to launch attacks on SNOW 3G. The first approximation is used in a distinguishing attack resulting in an expected complexity of $2^{172}$ and the second one can be used in a standard fast correlation attack resulting in key recovery in an expected complexity of $2^{177}$. If the key length in SNOW 3G would be increased to 256 bits, the results show that there are then academic attacks on such a version faster than the exhaustive key search.

Substantial work on trapdoor functions (TDFs) has led to many powerful notions and applications. However, despite tremendous work and progress, all known constructions have prohibitively large public keys.

In this work, we introduce new techniques for realizing so-called range-trapdoor hash functions with short public keys. This notion, introduced by Döttling et al. [Crypto 2019], allows for encoding a range of indices into a public key in a way that the public key leaks no information about the range, yet an associated trapdoor enables recovery of the corresponding input part. We give constructions of range-trapdoor hash functions, where for a range $I$ the public key consists of $O(n)$ group elements, improving upon $O(n |I|)$ achieved by Döttling et al. Moreover, by designing our evaluation algorithm in a special way involving Toeplitz matrix multiplication and by showing how to perform fast-Fourier transforms in the exponent, we arrive at $O(n \log n)$ group operations for evaluation, improving upon $O(n^2)$, required of previous constructions. Our constructions rely on power-DDH assumptions in pairing-free groups. As applications of our results we obtain

(1) The first construction of (rate-1) lossy TDFs with public keys consisting of a linear number of group elements (without pairings).

(2) Rate-1 string OT with receiver communication complexity of $O(n)$ group elements, where $n$ is the sender's message size, improving upon $O(n^2)$ [Crypto 2019]. This leads to a similar result in the context of private-information retrieval (PIR).

(3) Semi-compact homomorphic encryption for branching programs: A construction of homomorphic encryption for branching programs, with ciphertexts consisting of $O(\lambda n d)$ group elements, improving upon $O(\lambda^2 n d)$. Here $\lambda$ denotes the security parameter, $n$ the input size and $d$ the depth of the program.

This work introduces Algorithm Substitution Attacks (ASAs) on message authentication schemes. In light of revelations concerning mass surveillance, ASAs were initially introduced by Bellare, Paterson and Rogaway as a novel attack class against the confidentiality of encryption schemes. Such an attack replaces one or more of the regular scheme algorithms with a subverted version that aims to reveal information to an adversary (engaged in mass surveillance), while remaining undetected by users. While most prior work focused on subverting encryption systems, we study options to subvert symmetric message authentication protocols. In particular we provide powerful generic attacks that apply e.g. to HMAC or Carter-Wegman based schemes, inducing only a negligible implementation overhead. As subverted authentication can act as an enabler for subverted encryption (software updates can be manipulated to include replacements of encryption routines), we consider attacks of the new class highly impactful and dangerous.

Homomorphic Encryption (HE) is an emerging technnology that enables computing on data while the data is encrypted. A major challenge with homomorphic encryption is that it takes extensive expert knowledge to design meaningful and useful programs that are constructed from atomic HE operations.

We present RAMPARTS to address this challenge. RAMPARTS provides an environment for developing HE applications in Julia, a high-level language, the same way as ``cleartext'' applications are typically written in Julia. RAMPARTS makes the following three contributions. First, we use symbolic execution to automate the construction of an optimized computation circuit where both the circuit size and multiplicative depth are chosen by the compiler. Second, RAMPARTS automatically selects the HE parameters for the generated circuit, which is typically done manually by an HE expert. Third, RAMPARTS automatically selects the plaintext encoding for input values, and performs input and output data transformations. These three operations are not easily performed by programmers who are not HE experts. Thus, RAMPARTS makes HE more widely available and usable by the the population of programmers.

We compare our approach with Cingulata, the only previously known system that automatically generates circuits for HE computations. The HE circuits generated by RAMPARTS are significantly more efficient than the circuits compiled by Cingulata. For instance, our runtimes for key generation/circuit compilation and all online operations are more than one order of magnitude lower for a sample image processing application used for performance evaluation in our study.

This work introduces a new class of Algorithm Substitution Attack (ASA) on Symmetric Encryption Schemes. ASAs were introduced by Bellare, Paterson and Rogaway in light of revelations concerning mass surveillance. An ASA replaces an encryption scheme with a subverted version that aims to reveal information to an adversary engaged in mass surveillance, while remaining undetected by users. Previous work posited that a particular class of AEAD scheme (satisfying certain correctness and uniqueness properties) is resilient against subversion. Many if not all real-world constructions - such as GCM, CCM and OCB - are members of this class. Our results stand in opposition to those prior results. We present a potent ASA that generically applies to any AEAD scheme, is undetectable in all previous frameworks and which achieves successful exfiltration of user keys. We give even more efficient non-generic attacks against a selection of AEAD implementations that are most used in practice.In contrast to prior work, our new class of attack targets the decryption algorithm rather than encryption. We argue that this attack represents an attractive opportunity for a mass surveillance adversary. Our work serves to refine the ASA model and contributes to a series of papers that raises awareness and understanding about what is possible with ASAs.