At the core of Apple’s iMessage is a signcryption scheme that involves symmetric encryption of a message under a key that is derived from the message itself. This motivates us to formalize a primitive we call Encryption under Message-Derived Keys (EMDK). We prove security of the EMDK scheme underlying iMessage. We use this to prove security of the signcryption scheme itself, with respect to definitions of signcryption we give that enhance prior ones to cover issues peculiar to messaging protocols. Our provable-security results are quantitative, and we discuss the practical implications for iMessage.
We study the problem of dynamic symmetric searchable encryption. In that setting, it is crucial to minimize the information revealed to the server as a result of update operations (insertions and deletions). Two relevant privacy properties have been defined in that context: forward and backward privacy. The first makes it hard for the server to link an update operation with previous queries and has been extensively studied in the literature. The second limits what the server can learn about entries that were deleted from the database, from queries that happen after the deletion. Backward privacy was formally studied only recently (Bost et al., CCS 2017) in a work that introduced a formal definition with three variable types of leakage (Type-I to Type-III ordered from most to least secure), as well as the only existing schemes that satisfy this property. In this work, we introduce three novel constructions that improve previous results in multiple ways. The first scheme achieves Type-II backward privacy and our experimental evaluation shows it has 145-253X faster search computation times than previous constructions with the same leakage. Surprisingly, it is faster even than schemes with Type-III leakage which makes it the most efficient implementation of a forward and backward private scheme so far. The second one has search time that is asymptotically within a polylogarithmic multiplicative factor of the theoretical optimal (i.e., the result size of a search), and it achieves the strongest level of backward privacy (Type-I). All previous Type-I constructions require time that is at least linear in the total number of updates for the requested keywords, even the (arbitrarily many) previously deleted ones. Our final scheme improves upon the second one by reducing the number of roundtrips for a search at the cost of extra leakage (Type-III).
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 predominantly 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.
The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks σ satisfies σ≪2n/2), and a matching attack that can distinguish plaintext/ciphertext pairs from random using about 2n/2 blocks of data.
The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity O~(2n/2). This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message.
To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required.
As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity O~(22n/3).
This paper revisits the multi-user (mu) security of symmetric encryption, from the perspective of delivering an analysis of the AES-GCM-SIV AEAD scheme. Our end result shows that its mu security is comparable to that achieved in the single-user setting. In particular, even when instantiated with short keys (e.g., 128 bits), the security of AES-GCM-SIV is not impacted by the collisions of two user keys, as long as each individual nonce is not re-used by too many users. Our bounds also improve existing analyses in the single-user setting, in particular when messages of variable lengths are encrypted. We also validate security against a general class of key-derivation methods, including one that halves the complexity of the final proposal.
As an intermediate step, we consider mu security in a setting where the data processed by every user is bounded, and where user keys are generated according to arbitrary, possibly correlated distributions. This viewpoint generalizes the currently adopted one in mu security, and can be used to analyze re-keying practices.
A boomerang attack is a cryptanalysis framework that regards a block cipher E as the composition of two sub-ciphers E1∘E0 and builds a particular characteristic for E with probability p2q2 by combining differential characteristics for E0 and E1 with probability p and q, respectively. Crucially the validity of this figure is under the assumption that the characteristics for E0 and E1 can be chosen independently. Indeed, Murphy has shown that independently chosen characteristics may turn out to be incompatible. On the other hand, several researchers observed that the probability can be improved to p or q around the boundary between E0 and E1 by considering a positive dependency of the two characteristics, e.g.~the ladder switch and S-box switch by Biryukov and Khovratovich. This phenomenon was later formalised by Dunkelman et al.~as a sandwich attack that regards E as E1∘Em∘E0, where Em satisfies some differential propagation among four texts with probability r, and the entire probability is p2q2r. In this paper, we revisit the issue of dependency of two characteristics in Em, and propose a new tool called Boomerang Connectivity Table (BCT), which evaluates r in a systematic and easy-to-understand way when Em is composed of a single S-box layer. With the BCT, previous observations on the S-box including the incompatibility, the ladder switch and the S-box switch are represented in a unified manner. Moreover, the BCT can detect a new switching effect, which shows that the probability around the boundary may be even higher than p or q. To illustrate the power of the BCT-based analysis, we improve boomerang attacks against Deoxys-BC, and disclose the mechanism behind an unsolved probability amplification for generating a quartet in SKINNY. Lastly, we discuss the issue of searching for S-boxes having good BCT and extending the analysis to modular addition.
Division property is a generalized integral property proposed by Todo at Eurocrypt 2015. Previous tools for automatic searching are mainly based on the Mixed Integer Linear Programming (MILP) method and trace the division property propagation at the bit level. In this paper, we propose automatic tools to detect ARX ciphers’ division property at the bit level and some specific ciphers’ division property at the word level. For ARX ciphers, we construct the automatic searching tool relying on Boolean Satisfiability Problem (SAT) instead of MILP, since SAT method is more suitable in the search of ARX ciphers’ differential/linear characteristics. The propagation of division property is translated into a system of logical equations in Conjunctive Normal Form (CNF). Some logical equations can be dynamically adjusted according to different initial division properties and stopping rule, while the others corresponding to r-round propagations remain the same. Moreover, our approach can efficiently identify some optimized distinguishers with lower data complexity. As a result, we obtain a 17-round distinguisher for SHACAL-2, which gains four more rounds than previous work, and an 8-round distinguisher for LEA, which covers one more round than the former one. For word-based division property, we develop the automatic search based on Satisfiability Modulo Theories (SMT), which is a generalization of SAT. We model division property propagations of basic operations and S-boxes by logical formulas, and turn the searching problem into an SMT problem. With some available solvers, we achieve some new distinguishers. For CLEFIA, 10-round distinguishers are obtained, which cover one more round than the previous work. For the internal block cipher of Whirlpool, the data complexities of 4/5-round distinguishers are improved. For Rijndael-192 and Rijndael-256, 6-round distinguishers are presented, which attain two more rounds than the published ones. Besides, the integral attacks for CLEFIA are improved by one round with the newly obtained distinguishers.
Conditional cube attack is an efficient key-recovery attack on Keccak keyed modes proposed by Huang et al. at EUROCRYPT 2017. By assigning bit conditions, the diffusion of a conditional cube variable is reduced. Then, using a greedy algorithm (Algorithm 4 in Huang et al.’s paper), Huang et al. find some ordinary cube variables, that do not multiply together in the 1st round and do not multiply with the conditional cube variable in the 2nd round. Then the key-recovery attack is launched. The key part of conditional cube attack is to find enough ordinary cube variables. Note that, the greedy algorithm given by Huang et al. adds ordinary cube variable without considering its bad effect, i.e. the new ordinary cube variable may result in that many other variables could not be selected as ordinary cube variable (they multiply with the new ordinary cube variable in the first round).
In this paper, we bring out a new MILP model to solve the above problem. We show how to model the CP-like-kernel and model the way that the ordinary cube variables do not multiply together in the 1st round as well as do not multiply with the conditional cube variable in the 2nd round. Based on these modeling strategies, a series of linear inequalities are given to restrict the way to add an ordinary cube variable. Then, by choosing the objective function of the maximal number of ordinary cube variables, we convert Huang et al.’s greedy algorithm into an MILP problem and the maximal ordinary cube variables are found.
Using this new MILP tool, we improve Huang et al.’s key-recovery attacks on reduced-round Keccak-MAC-384 and Keccak-MAC-512 by 1 round, get the first 7-round and 6-round key-recovery attacks, respectively. For Ketje Major, we conclude that when the nonce is no less than 11 lanes, a 7-round key-recovery attack could be achieved. In addition, for Ketje Minor, we use conditional cube variable with 6-6-6 pattern to launch 7-round key-recovery attack.
Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server’s searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50x in search latency, and a saving of 62% in server storage consumption.
Threshold cryptography provides a mechanism for protecting secret keys by sharing them among multiple parties, who then jointly perform cryptographic operations. An attacker who corrupts upto a threshold number of parties cannot recover the secrets or violate security. Prior works in this space have mostly focused on definitions and constructions for public-key cryptography and digital signatures, and thus do not capture the security concerns and efficiency challenges of symmetric-key based applications which commonly use long-term (unprotected) master keys to protect data at rest, authenticate clients on enterprise networks, and secure data and payments on IoT devices.
We put forth the first formal treatment for distributed symmetric-key encryption, proposing new notions of correctness, privacy and authenticity in presence of malicious attackers. We provide strong and intuitive game-based definitions that are easy to understand and yield efficient constructions.
We propose a generic construction of threshold authenticated encryption based on any distributed pseudorandom function (DPRF). When instantiated with the two different DPRF constructions proposed by Naor, Pinkas and Reingold (Eurocrypt 1999) and our enhanced versions, we obtain several efficient constructions meeting different security definitions. We implement these variants and provide extensive performance comparisons. Our most efficient instantiation uses only symmetric-key primitives and achieves a throughput of upto 1 million encryptions/decryptions per seconds, or alternatively a sub-millisecond latency with upto 18 participating parties.