What a lovely hat

Tweakable enciphering modes (TEMs) provide security in a variety of storage and space-critical applications like disk and file-based encryption, and packet-based communication protocols, among others. XCB-AES (known as XCBv2) is specified in the IEEE 1619.2 standard for encryption of sector-oriented storage media and it comes with a proof of security for block-aligned input messages. In this work, we demonstrate the $\textit{first}$ and most efficient plaintext recovery attack on...

XCB, a tweakable enciphering mode, is part of IEEE Std. 1619.2 for shared storage media. We show that all versions of XCB are not secure through three plaintext recovery attacks. A key observation is that XCB behaves like an LRW1-type tweakable block cipher for single-block messages, which lacks CCA security. The first attack targets one-block XCB, using three queries to recover the plaintext. The second one requires four queries to recover the plaintext that excludes one block. The last one...

Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions is poorly understood, and no systematic analysis has been performed. We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some...

We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram's equivalent of the TLS record protocol. We give positive and negative results. On the one hand, we formally and in detail model a slight variant of Telegram's "record protocol" and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our...

MEGA is a leading cloud storage platform with more than 250 million users and 1000 Petabytes of stored data. MEGA claims to offer user-controlled, end-to-end security. This is achieved by having all data encryption and decryption operations done on MEGA clients, under the control of keys that are only available to those clients. This is intended to protect MEGA users from attacks by MEGA itself, or by adversaries who have taken control of MEGA’s infrastructure. We provide a detailed...

Cryptanalysis of symmetric-key ciphers, e.g., linear/differential cryptanalysis, requires an adversary to know the internal structures of the target ciphers. On the other hand, deep learning-based cryptanalysis has attracted significant attention because the adversary is not assumed to have knowledge about the target ciphers with the exception of the algorithm interfaces. Such cryptanalysis in a blackbox setting is extremely strong; thus, we must design symmetric-key ciphers that are secure...

Homomorphic encryption primitives have the potential to be the main enabler of privacy preserving computation delegation to cloud environments. One of the avenues which has been explored to reduce their significant computational overhead with respect to cleartext computation is the one of the so-called noise-free homomorphic encryption schemes. In this work, we present an attack against fully homomorphic encryption primitives where a distinguisher for a single plaintext value exists. We...

This paper presents an attack based on side-channel information and Information Set Decoding (ISD) on the Niederreiter cryptosystem and an evaluation of the practicality of the attack using an electromagnetic side channel. First, we describe a basic plaintext-recovery attack on the decryption algorithm of the Niederreiter cryptosystem. In case the cryptosystem is used as Key-Encapsulation Mechanism (KEM) in a key exchange, the plaintext corresponds to a session key. Our attack is an...

XTS is an encryption scheme for storage devices standardized by IEEE and NIST. It is based on Rogaway's XEX tweakable block cipher and is known to be secure up to the collisions between the blocks, thus up to around $2^{n/2}$ blocks for $n$-bit blocks. However this only implies that the theoretical indistinguishability notion is broken with $O(2^{n/2})$ queries and does not tell the practical risk against the plaintext recovery if XTS is targeted. We show several plaintext recovery attacks...

In this paper, we compute an algebraic decomposition of blackbox rings in the generic ring model. More precisely, we explicitly decompose a black-box ring as a direct product of a nilpotent black-box ring and local Artinian black-box rings, by computing all its primitive idempotents. The algorithm presented in this paper uses quantum subroutines for the computation of the p-power parts of a black-box ring and then classical algorithms for the computation of the corresponding primitive...

We present practical attacks on OCB2. This mode of operation of a blockcipher was designed with the aim to provide particularly efficient and provably-secure authenticated encryption services, and since its proposal about 15 years ago it belongs to the top performers in this realm. OCB2 was included in an ISO standard in 2009. An internal building block of OCB2 is the tweakable blockcipher obtained by operating a regular blockcipher in XEX$^\ast$ mode. The latter provides security only when...

Inoue and Minematsu [Cryptology ePrint Archive: Report 2018/1040] presented efficient forgery attacks against OCB2, and Poettering [Cryptology ePrint Archive: Report 2018/1087] presented a distinguishing attack. In this short note, based on these results, we show a plaintext recovery attack against OCB2 in the chosen plaintext and ciphertext setting. We also show that the decryption oracle of the underlying block cipher can be simulated. This complements the simulation of the encryption...

Today, about 10% of TLS connections are still using CBC-mode cipher suites, despite a long history of attacks and the availability of better options (e.g. AES-GCM). In this work, we present three new types of attack against four popular fully patched implementations of TLS (Amazon's s2n, GnuTLS, mbed TLS and wolfSSL) which elected to use ``pseudo constant time'' countermeasures against the Lucky 13 attack on CBC-mode. Our attacks combine several variants of the PRIME+PROBE cache timing...

In this paper, using probability transition matrix, at first we revisit the work of Mantin on finding the probability distribution of RC4 permutation after the completion of KSA. After that, we extend the same idea to analyse the probabilities during any iteration of Pseudo Random Generation Algorithm. Next, we study the bias $Z_r=r$ (where $Z_r$ is the $r$-th output keystream bit), which is one of the significant biases observed in RC4 output keystream. This bias has played an important...

Differential power analysis (DPA) is a powerful tool to extract the key of a cryptographic implementation from observing its power consumption during the en-/decryption of many different inputs. Therefore, cryptographic schemes based on frequent re-keying such as leakage-resilient encryption aim to inherently prevent DPA on the secret key by limiting the amount of data being processed under one key. However, the original asset of encryption, namely the plaintext, is disregarded. This paper...

The security of order-revealing encryption (ORE) has been unclear since its invention. Dataset characteristics for which ORE is especially insecure have been identified, such as small message spaces and low-entropy distributions. On the other hand, properties like one-wayness on uniformly-distributed datasets have been proved for ORE constructions. This work shows that more plaintext information can be extracted from ORE ciphertexts than was previously thought. We identify two issues: ...

Schemes for secure outsourcing of client data with search capability are being increasingly marketed and deployed. In the literature, schemes for accomplishing this efficiently are called Searchable Encryption (SE). They achieve high efficiency with provable security by means of a quantifiable leakage profile. However, the degree to which SE leakage can be exploited by an adversary is not well understood. To address this, we present a characterization of the leakage profiles of in-the-wild...

Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on {\it a short-term bias} in the first two bytes of a keystream and {\it a long-term bias} in the first two bytes of every cycle of $N$ keystream bytes, where $N$ is the size of the internal permutation. Our attacks are able to distinguish a keystream of...

We explore the use of the Mantin biases (Mantin, Eurocrypt 2005) to recover plaintexts from RC4-encrypted traffic. We provide a more fine-grained analysis of these biases than in Mantin's original work. We show that, in fact, the original analysis was incorrect in certain cases: the Mantin biases are sometimes non-existent, and sometimes stronger than originally predicted. We then show how to use these biases in a plaintext recovery attack. Our attack targets two unknown bytes of plaintext...

Telegram is a popular messaging app which supports end-to-end encrypted communication. In Spring 2015 we performed an audit of Telegram's source code. This short paper summarizes our findings. Our main discovery is that the symmetric encryption scheme used in Telegram -- known as MTProto -- is not IND-CCA secure, since it is possible to turn any ciphertext into a different ciphertext that decrypts to the same message. We stress that this is a theoretical attack on the definition of...

s2n is an implementation of the TLS protocol that was released in late June 2015 by Amazon. It is implemented in around 6,000 lines of C99 code. By comparison, OpenSSL needs around 70,000 lines of code to implement the protocol. At the time of its release, Amazon announced that s2n had undergone three external security evaluations and penetration tests. We show that, despite this, s2n - as initially released - was vulnerable to a timing attack in the case of CBC-mode ciphersuites, which...

RC4 suffered from a range of plaintext-recovery attacks using statistical biases, which use substantial, albeit close-to-practical, amounts of known keystream in applications such as TLS or WEP/WPA. Spritz was recently proposed at the rump session of CRYPTO 2014 as a slower redesign of RC4 by Rivest and Schuldt, aiming at reducing the statistical biases that lead to these attacks on RC4. Even more devastating than those plaintext-recovery attacks from large amounts of keystream would be...

We conduct an analysis of the RC4 algorithm as it is used in the IEEE WPA/TKIP wireless standard. In that standard, RC4 keys are computed on a per-frame basis, with specific key bytes being set to known values that depend on 2 bytes of the WPA frame counter (called the TSC). We observe very large, TSC-dependent biases in the RC4 keystream when the algorithm is keyed according to the WPA specification. These biases permit us to mount an effective statistical, plaintext-recovering attack in...

The first three bytes of the RC4 key in WPA are public as they are derived from the public parameter IV, and this derivation leads to a strong mutual dependence between the first two bytes of the RC4 key. In this paper, we provide a disciplined study of RC4 biases resulting specifically in such a scenario. Motivated by the work of AlFardan et al. (2013), we first prove the interesting sawtooth distribution of the first byte in WPA and the similar nature for the biases in the initial...

The block cipher modes of operation that are widely used (CBC, CTR, CFB) are secure up to the birthday bound; that is, if $w2^{w}$ or fewer bits of data are encrypted with a $w$-bit block cipher. However, the detailed security properties close to this bound are not widely appreciated, despite the fact that $64$-bit block ciphers are sometimes used in that domain. This work addresses the issue by analyzing plaintext-recovery attacks that are effective close to that bound. We describe...