CryptoDB
Eyal Ronen
Publications
Year
Venue
Title
2022
CRYPTO
CHIP and CRISP: Protecting All Parties Against Compromise through Identity-Binding PAKEs
Abstract
Recent advances in password-based authenticated key exchange (PAKE) protocols can offer stronger security guarantees for globally deployed security protocols. Notably, the OPAQUE protocol [Eurocrypt2018] realizes Strong Asymmetric PAKE (saPAKE), strengthening the protection offered by aPAKE to compromised servers: after compromising an saPAKE server, the adversary still has to perform a full brute-force search to recover any passwords or impersonate users. However, (s)aPAKEs do not protect client storage, and can only be applied in the so-called asymmetric setting, in which some parties, such as servers, do not communicate with each other using the protocol.
Nonetheless, passwords are also widely used in symmetric settings, where a group of parties share a password and can all communicate (e.g., Wi-Fi with client devices, routers, and mesh nodes; or industrial IoT scenarios). In these settings, the (s)aPAKE techniques cannot be applied, and the state-of-the-art still involves handling plaintext passwords.
In this work, we propose the notions of (strong) identity-binding PAKEs that improve this situation: they protect against compromise of any party, and can also be applied in the symmetric setting. We propose counterparts to state-of-the-art security notions from the asymmetric setting in the UC model, and construct protocols that provably realize them. Our constructions bind the local storage of all parties to abstract identities, building on ideas from identity-based key exchange, but without requiring a third party.
Our first protocol, CHIP, generalizes the security of aPAKE protocols to all parties, forcing the adversary to perform a brute-force search to recover passwords or impersonate others. Our second protocol, CRISP, additionally renders any adversarial pre-computation useless, thereby offering saPAKE-like guarantees for all parties, instead of only the server.
We evaluate prototype implementations of our protocols and show that even though they offer stronger security for real-world use cases, their performance is in line with, or even better than, state-of-the-art protocols.
2021
EUROCRYPT
Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3
📺
Abstract
Format-Preserving Encryption (FPE) schemes accept plaintexts from any finite set of values (such as social security numbers or birth dates) and produce ciphertexts that belong to the same set. They are extremely useful in practice since they make it possible to encrypt existing databases or communication packets without changing their format. Due to industry demand, NIST had standardized in 2016 two such encryption schemes called FF1 and FF3. They immediately attracted considerable cryptanalytic attention with decreasing attack complexities. The best currently known attack on the Feistel construction FF3 has data and memory complexity of ${O}(N^{11/6})$ and time complexity of ${O}(N^{17/6})$, where the input belongs to a domain of size $N \times N$.
In this paper, we present and experimentally verify three improved attacks on FF3. Our best attack achieves the tradeoff curve $D=M=\tilde{O}(N^{2-t})$, $T=\tilde{O}(N^{2+t})$ for all $t \leq 0.5$.
In particular, we can reduce the data and memory complexities to the more practical $\tilde{O}(N^{1.5})$, and at the same time, reduce the time complexity to $\tilde{O}(N^{2.5})$.
We also identify another attack vector against FPE schemes, the {\em related-domain} attack. We show how one can mount powerful attacks when the adversary is given access to the encryption under the same key in different domains, and show how to apply it to efficiently distinguish FF3 and FF3-1 instances.
2020
EUROCRYPT
The Retracing Boomerang Attack
📺
Abstract
Boomerang attacks are extensions of differential attacks, that make it
possible to combine
two unrelated differential properties of the first and second part of a
cryptosystem with probabilities $p$ and $q$ into a new differential-like
property
of the whole cryptosystem with probability $p^2q^2$ (since each one of the
properties has to be satisfied twice). In this paper we describe a new
version of
boomerang attacks which uses the counterintuitive idea of throwing out most
of the data in order to force equalities between certain values
on the ciphertext side. In certain cases,
this creates a correlation between the four probabilistic events,
which increases the probability of the combined property to $p^2q$
and increases the signal to noise ratio of the resultant distinguisher.
We call this variant a {\it retracing boomerang attack} since we make
sure that the boomerang we throw follows the same path
on its forward and backward directions.
To demonstrate the power of the new
technique, we apply it to the case of 5-round AES. This version of AES was
repeatedly
attacked by a large variety of techniques, but for twenty years its
complexity had remained
stuck at $2^{32}$. At Crypto'18 it was finally reduced to $2^{24}$ (for full key recovery), and with
our
new technique we can further reduce the complexity of full key recovery to
the surprisingly low value of $2^{16.5}$
(i.e., only $90,000$ encryption/decryption operations are required for a full
key recovery on half the rounds of AES).
In addition to improving previous
attacks, our new technique unveils a hidden relationship between
boomerang attacks and two other cryptanalytic techniques, the yoyo game and
the recently introduced mixture differentials.
2019
JOFC
Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities
Abstract
Determining the security of AES is a central problem in cryptanalysis, but progress in this area had been slow and only a handful of cryptanalytic techniques led to significant advancements. At Eurocrypt 2017 Grassi et al. presented a novel type of distinguisher for AES-like structures, but so far all the published attacks which were based on this distinguisher were inferior to previously known attacks in their complexity. In this paper we combine the technique of Grassi et al. with several other techniques in a novel way to obtain the best known key recovery attack on 5-round AES in the single-key model, reducing its overall complexity from about $$2^{32}$$ 2 32 to less than $$2^{22}$$ 2 22 . Extending our techniques to 7-round AES, we obtain the best known attacks on reduced-round AES-192 which use practical amounts of data and memory, breaking the record for such attacks which was obtained in 2000 by the classical Square attack. In addition, we use our techniques to improve the Gilbert–Minier attack (2000) on 7-round AES, reducing its memory complexity from $$2^{80}$$ 2 80 to $$2^{40}$$ 2 40 .
2018
CRYPTO
Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities
Abstract
Determining the security of AES is a central problem in cryptanalysis, but progress in this area had been slow and only a handful of cryptanalytic techniques led to significant advancements. At Eurocrypt 2017 Grassi et al. presented a novel type of distinguisher for AES-like structures, but so far all the published attacks which were based on this distinguisher were inferior to previously known attacks in their complexity. In this paper we combine the technique of Grassi et al. with several other techniques to obtain the best known key recovery attack on 5-round AES in the single-key model, reducing its overall complexity from about $$2^{32}$$ to about $$2^{22.5}$$. Extending our techniques to 7-round AES, we obtain the best known attacks on AES-192 which use practical amounts of data and memory, breaking the record for such attacks which was obtained 18 years ago by the classical Square attack.
Coauthors
- Ohad Amon (1)
- Achiya Bar-On (2)
- Cas Cremers (1)
- Orr Dunkelman (4)
- Nathan Keller (4)
- Moni Naor (1)
- Shahar Paz (1)
- Adi Shamir (4)