## CryptoDB

### Stefano Tessaro

#### Affiliation: UCSB

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

Tight Time-Memory Trade-Offs for Symmetric Encryption
📺
Abstract

Concrete security proofs give upper bounds on the attacker’s advantage as a function of its time/query complexity. Cryptanalysis suggests however that other resource limitations – most notably, the attacker’s memory – could make the achievable advantage smaller, and thus these proven bounds too pessimistic. Yet, handling memory limitations has eluded existing security proofs.This paper initiates the study of time-memory trade-offs for basic symmetric cryptography. We show that schemes like counter-mode encryption, which are affected by the Birthday Bound, become more secure (in terms of time complexity) as the attacker’s memory is reduced.One key step of this work is a generalization of the Switching Lemma: For adversaries with S bits of memory issuing q distinct queries, we prove an n-to-n bit random function indistinguishable from a permutation as long as $$S \times q \ll 2^n$$S×q≪2n. This result assumes a combinatorial conjecture, which we discuss, and implies right away trade-offs for deterministic, stateful versions of CTR and OFB encryption.We also show an unconditional time-memory trade-off for the security of randomized CTR based on a secure PRF. Via the aforementioned conjecture, we extend the result to assuming a PRP instead, assuming only one-block messages are encrypted.Our results solely rely on standard PRF/PRP security of an underlying block cipher. We frame the core of our proofs within a general framework of indistinguishability for streaming algorithms which may be of independent interest.

2018

EUROCRYPT

2018

CRYPTO

The Curse of Small Domains: New Attacks on Format-Preserving Encryption
📺
Abstract

Format-preserving encryption (FPE) produces ciphertexts which have the same format as the plaintexts. Building secure FPE is very challenging, and recent attacks (Bellare, Hoang, Tessaro, CCS ’16; Durak and Vaudenay, CRYPTO ’17) have highlighted security deficiencies in the recent NIST SP800-38G standard. This has left the question open of whether practical schemes with high security exist.In this paper, we continue the investigation of attacks against FPE schemes. Our first contribution are new known-plaintext message recovery attacks against Feistel-based FPEs (such as FF1/FF3 from the NIST SP800-38G standard) which improve upon previous work in terms of amortized complexity in multi-target scenarios, where multiple ciphertexts are to be decrypted. Our attacks are also qualitatively better in that they make no assumptions on the correlation between the targets to be decrypted and the known plaintexts. We also surface a new vulnerability specific to FF3 and how it handles odd length domains, which leads to a substantial speedup in our attacks.We also show the first attacks against non-Feistel based FPEs. Specifically, we show a strong message-recovery attack for FNR, a construction proposed by Cisco which replaces two rounds in the Feistel construction with a pairwise-independent permutation, following the paradigm by Naor and Reingold (JoC, ’99). We also provide a strong ciphertext-only attack against a variant of the DTP construction by Brightwell and Smith, which is deployed by Protegrity within commercial applications. All of our attacks show that existing constructions fall short of achieving desirable security levels. For Feistel and the FNR schemes, our attacks become feasible on small domains, e.g., 8 bits, for suggested round numbers. Our attack against the DTP construction is practical even for large domains. We provide proof-of-concept implementations of our attacks that verify our theoretical findings.

2018

TCC

Provable Time-Memory Trade-Offs: Symmetric Cryptography Against Memory-Bounded Adversaries
Abstract

We initiate the study of symmetric encryption in a regime where the memory of the adversary is bounded. For a block cipher with n-bit blocks, we present modes of operation for encryption and authentication that guarantee security beyond$$2^n$$ encrypted/authenticated messages, as long as (1) the adversary’s memory is restricted to be less than $$2^n$$ bits, and (2) the key of the block cipher is long enough to mitigate memory-less key-search attacks. This is the first proposal of a setting which allows to bypass the $$2^n$$ barrier under a reasonable assumption on the adversarial resources.Motivated by the above, we also discuss the problem of stretching the key of a block cipher in the setting where the memory of the adversary is bounded. We show a tight equivalence between the security of double encryption in the ideal-cipher model and the hardness of a special case of the element distinctness problem, which we call the list-disjointness problem. Our result in particular implies a conditional lower bound on time-memory trade-offs to break PRP security of double encryption, assuming optimality of the worst-case complexity of existing algorithms for list disjointness.

2016

EUROCRYPT

2016

CRYPTO

2014

ASIACRYPT

2012

EUROCRYPT

2009

ASIACRYPT

2009

CRYPTO

2008

ASIACRYPT

2007

EPRINT

Domain Extension of Public Random Functions: Beyond the Birthday Barrier
Abstract

A public random function is a random function that is accessible by
all parties, including the adversary. For example, a (public) random
oracle is a public random function $\{0,1\}^{*} \to \{0,1\}^n$. The
natural problem of constructing a public random oracle from a public
random function $\{0,1\}^{m} \to \{0,1\}^n$ (for some $m > n$) was
first considered at Crypto 2005 by Coron et al.\ who proved the
security of variants of the Merkle-Damg{\aa}rd construction against
adversaries issuing up to $O(2^{n/2})$ queries to the construction and
to the underlying compression function. This bound is less than the
square root of $n2^m$, the number of random bits contained in the
underlying random function.
In this paper, we investigate domain extenders for public random
functions approaching optimal security. In particular, for all
$\epsilon \in (0,1)$ and all functions $m$ and $\ell$ (polynomial in
$n$), we provide a construction $\mathbf{C}_{\epsilon,m,\ell}(\cdot)$
which extends a public random function $\mathbf{R}: \{0,1\}^{n} \to
\{0,1\}^n$ to a function $\mathbf{C}_{\epsilon,m,\ell}(\R):
\{0,1\}^{m(n)} \to \{0,1\}^{\ell(n)}$ with time-complexity polynomial
in $n$ and $1/\epsilon$ and which is secure against adversaries which
make up to $\Theta(2^{n(1-\epsilon)})$ queries. A central tool for
achieving high security are special classes of unbalanced bipartite
expander graphs with small degree. The achievability of practical (as
opposed to complexity-theoretic) efficiency is proved by a
non-constructive existence proof.
Combined with the iterated constructions of Coron et al., our result
leads to the first iterated construction of a hash
function $\{0,1\}^{*} \to \{0,1\}^n$ from a component
function $\{0,1\}^{n} \to \{0,1\}^n$ that withstands all recently
proposed generic attacks against iterated hash functions, like Joux's
multi-collision attack, Kelsey and Schneier's second-preimage attack,
and Kelsey and Kohno's herding attacks.

#### Program Committees

- Eurocrypt 2019
- Crypto 2017
- TCC 2017
- TCC 2015
- Crypto 2014
- Asiacrypt 2014
- TCC 2013
- Crypto 2011

#### Coauthors

- Joël Alwen (2)
- Mihir Bellare (6)
- Daniel J. Bernstein (1)
- Priyanka Bose (1)
- Elette Boyle (1)
- Ran Canetti (1)
- David Cash (3)
- Binyi Chen (4)
- Jean-Sébastien Coron (1)
- Wei Dai (1)
- Yevgeniy Dodis (1)
- Marc Fischlin (1)
- Peter Gaži (8)
- Shafi Goldwasser (1)
- Viet Tung Hoang (5)
- Thomas Holenstein (1)
- Russell Impagliazzo (1)
- Joseph Jaeger (1)
- Ragesh Jaiswal (1)
- Valentine Kabanets (1)
- Chethan Kamath (1)
- Bruce M. Kapron (1)
- Eike Kiltz (1)
- Valerie King (1)
- Vladimir Kolmogorov (1)
- Robin Künzler (1)
- Jooyoung Lee (2)
- Anja Lehmann (2)
- Huijia Lin (5)
- Ueli Maurer (5)
- Jacques Patarin (1)
- Krzysztof Pietrzak (6)
- Leonid Reyzin (1)
- Thomas Ristenpart (3)
- Yannick Seurin (3)
- Thomas Shrimpton (1)
- Pratik Soni (2)
- Martijn Stam (1)
- John P. Steinberger (3)
- Igors Stepanovs (3)
- Aishwarya Thiruvengadam (1)
- Ni Trieu (1)
- Vinod Vaikuntanathan (1)
- Alexander Vardy (1)
- David A. Wilson (2)