## CryptoDB

### Stefano Tessaro

#### Affiliation: UCSB

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

On the Memory-Tightness of Hashed ElGamal
📺
Abstract

We study the memory-tightness of security reductions in public-key
cryptography, focusing in particular on Hashed ElGamal. We prove that
any {\em straightline} (i.e., without rewinding) black-box reduction
needs memory which grows linearly with the number of queries of the
adversary it has access to, as long as this reduction treats the
underlying group generically. This makes progress towards proving a
conjecture by Auerbach {\em et al.} (CRYPTO 2017), and is also the
first lower bound on memory-tightness for a concrete cryptographic
scheme (as opposed to generalized reductions across security
notions). Our proof relies on compression arguments in the generic
group model.

2020

CRYPTO

The Memory-Tightness of Authenticated Encryption
📺
Abstract

This paper initiates the study of the provable security of authenticated encryption (AE) in the memory-bounded setting. Recent works -- Tessaro and Thiruvengadam (TCC '18), Jaeger and Tessaro (EUROCRYPT '19), and Dinur (EUROCRYPT '20) -- focus on confidentiality, and look at schemes for which trade-offs between the attacker's memory and its data complexity are inherent. Here, we ask whether these results and techniques can be lifted to the full AE setting, which additionally asks for integrity.
We show both positive and negative results. On the positive side, we provide tight memory-sensitive bounds for the security of GCM and its generalization, CAU (Bellare and Tackmann, CRYPTO '16). Our bounds apply to a restricted case of AE security which abstracts the deployment within protocols like TLS, and rely on a new memory-tight reduction to corresponding restricted notions of confidentiality and integrity. In particular, our reduction uses an amount of memory which linearly depends on that of the given adversary, as opposed to only imposing a constant memory overhead as in earlier works (Auerbach et al, CRYPTO '17).
On the negative side, we show that a large class of black-box reductions cannot generically lift confidentiality and integrity security to a joint definition of AE security in a memory-tight way.

2020

TCC

Towards Defeating Backdoored Random Oracles: Indifferentiability with Bounded Adaptivity
📺
Abstract

In the backdoored random-oracle (BRO) model, besides access to a random function $\hash$, adversaries are provided with a backdoor oracle that can compute arbitrary leakage functions $f$ of the function table of $\hash$. Thus, an adversary would be able to invert points, find collisions, test for membership in certain sets, and more. This model was introduced in the work of Bauer, Farshim, and Mazaheri (Crypto 2018) and extends the auxiliary-input idealized models of Unruh (Crypto 2007), Dodis, Guo, and Katz (Eurocrypt 2017), Coretti et al. (Eurocrypt 2018), and Coretti, Dodis, and Guo (Crypto~2018). It was shown that certain security properties, such as one-wayness, pseudorandomness, and collision resistance can be re-established by combining two independent BROs, even if the adversary has access to both backdoor oracles.
In this work we further develop the technique of combining two or more independent BROs to render their backdoors useless in a more general sense. More precisely, we study the question of building an \emph{indifferentiable} and backdoor-free random function by combining multiple BROs. Achieving full indifferentiability in this model seems very challenging at the moment. We however make progress by showing that the xor combiner goes well beyond security against preprocessing attacks and offers indifferentiability as long as the adaptivity of queries to different backdoor oracles remains logarithmic in the input size of the BROs. We even show that an extractor-based combiner of three BROs can achieve indifferentiability with respect to a linear adaptivity of backdoor queries. Furthermore, a natural restriction of our definition gives rise to a notion of \emph{indifferentiability with auxiliary input}, for which we give two positive feasibility results.
To prove these results we build on and refine techniques by Göös et al. (STOC 2015) and Kothari et al. (STOC 2017) for decomposing distributions with high entropy into distributions with more structure and show how they can be applied in the more involved adaptive settings.

2020

TCC

Super-Linear Time-Memory Trade-Offs for Symmetric Encryption
📺
Abstract

We build symmetric encryption schemes from a pseudorandom
function/permutation with domain size $N$ which have very high
security -- in terms of the amount of messages $q$ they can securely
encrypt -- assuming the adversary has $S < N$ bits of memory. We aim
to minimize the number of calls $k$ we make to the underlying
primitive to achieve a certain $q$, or equivalently, to maximize the
achievable $q$ for a given $k$. We target in
particular $q \gg N$, in contrast to recent works (Jaeger and
Tessaro, EUROCRYPT '19; Dinur, EUROCRYPT '20) which aim to beat the
birthday barrier with one call when $S < \sqrt{N}$.
Our first result gives new and explicit bounds for the
Sample-then-Extract paradigm by Tessaro and Thiruvengadam (TCC
'18). We show instantiations for which $q =\Omega((N/S)^{k})$.
If $S < N^{1- \alpha}$, Thiruvengadam and Tessaro's weaker bounds
only guarantee $q > N$ when $k = \Omega(\log N)$. In contrast, here,
we show this is true already for $k = O(1/\alpha)$.
We also consider a scheme by Bellare, Goldreich and Krawczyk (CRYPTO
'99) which evaluates the primitive at $k$ independent random
strings, and masks the message with the XOR of the outputs. Here, we
show $q= \Omega((N/S)^{k/2})$, using new combinatorial bounds
on the list-decodability of XOR codes which are of independent
interest. We also study best-possible attacks against this
construction.

2020

TCC

Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness
📺
Abstract

This paper studies concrete security with respect to expected-time adversaries. Our first contribution is a set of generic tools to obtain tight bounds on the advantage of an adversary with expected-time guarantees. We apply these tools to derive bounds in the random-oracle and generic-group models, which we show to be tight.
As our second contribution, we use these results to derive concrete bounds on the soundness of public-coin proofs and arguments of knowledge. Under the lens of concrete security, we revisit a paradigm by Bootle at al. (EUROCRYPT '16) that proposes a general Forking Lemma for multi-round protocols which implements a rewinding strategy with expected-time guarantees. We give a tighter analysis, as well as a modular statement. We adopt this to obtain the first quantitative bounds on the soundness of Bulletproofs (Bünz et al., S&P 2018), which we instantiate with our expected-time generic-group analysis to surface inherent dependence between the concrete security and the statement to be proved.

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.

2019

CRYPTO

Seedless Fruit Is the Sweetest: Random Number Generation, Revisited
📺
Abstract

The need for high-quality randomness in cryptography makes random-number generation one of its most fundamental tasks.A recent important line of work (initiated by Dodis et al., CCS ’13) focuses on the notion of robustness for pseudorandom number generators (PRNGs) with inputs. These are primitives that use various sources to accumulate sufficient entropy into a state, from which pseudorandom bits are extracted. Robustness ensures that PRNGs remain secure even under state compromise and adversarial control of entropy sources. However, the achievability of robustness inherently depends on a seed, or, alternatively, on an ideal primitive (e.g., a random oracle), independent of the source of entropy. Both assumptions are problematic: seed generation requires randomness to start with, and it is arguable whether the seed or the ideal primitive can be kept independent of the source.
This paper resolves this dilemma by putting forward new notions of robustness which enable both (1) seedless PRNGs and (2) primitive-dependent adversarial sources of entropy. To bypass obvious impossibility results, we make a realistic compromise by requiring that the source produce sufficient entropy even given its evaluations of the underlying primitive. We also provide natural, practical, and provably secure constructions based on hash-function designs from compression functions, block ciphers, and permutations. Our constructions can be instantiated with minimal changes to industry-standard hash functions SHA-2 and SHA-3, or key derivation function HKDF, and can be downgraded to (online) seedless randomness extractors, which are of independent interest.On the way we consider both a computational variant of robustness, where attackers only make a bounded number of queries to the ideal primitive, as well as a new information-theoretic variant, which dispenses with this assumption to a certain extent, at the price of requiring a high rate of injected weak randomness (as it is, e.g., plausible on Intel’s on-chip RNG). The latter notion enables applications such as everlasting security. Finally, we show that the CBC extractor, used by Intel’s on-chip RNG, is provably insecure in our model.

2019

CRYPTO

Memory-Hard Functions from Cryptographic Primitives
📺
Abstract

Memory-hard functions (MHFs) are moderately-hard functions which enforce evaluation costs both in terms of time and memory (often, in form of a trade-off). They are used e.g. for password protection, password-based key-derivation, and within cryptocurrencies, and have received a considerable amount of theoretical scrutiny over the last few years. However, analyses see MHFs as modes of operation of some underlying hash function $$\mathcal {H}$$, modeled as a monolithic random oracle. This is however a very strong assumption, as such hash functions are built from much simpler primitives, following somewhat ad-hoc design paradigms.This paper initiates the study of how to securely instantiate $$\mathcal {H}$$ within MHF designs using common cryptographic primitives like block ciphers, compression functions, and permutations. Security here will be in a model in which the adversary has parallel access to an idealized version of the underlying primitive. We will provide provably memory-hard constructions from all the aforementioned primitives. Our results are generic, in that we will rely on hard-to-pebble graphs designed in prior works to obtain our constructions.One particular challenge we encounter is that $$\mathcal {H}$$ is usually required to have large outputs (to increase memory hardness without changing the description size of MHFs), whereas the underlying primitives generally have small output sizes.

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 (5)
- Sandro Coretti (1)
- Jean-Sébastien Coron (1)
- Wei Dai (2)
- Yevgeniy Dodis (3)
- Pooya Farshim (1)
- Marc Fischlin (1)
- Peter Gaži (8)
- Ashrujit Ghoshal (2)
- Shafi Goldwasser (1)
- Viet Tung Hoang (5)
- Thomas Holenstein (1)
- Russell Impagliazzo (1)
- Joseph Jaeger (3)
- Ragesh Jaiswal (1)
- Valentine Kabanets (1)
- Chethan Kamath (1)
- Bruce M. Kapron (1)
- Harish Karthikeyan (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)
- Sogol Mazaheri (1)
- 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)
- Xihu Zhang (1)