CryptoDB
Ashrujit Ghoshal
Publications
Year
Venue
Title
2022
EUROCRYPT
Hiding in Plain Sight: Memory-tight Proofs via Randomness Programming
📺
Abstract
This paper continues the study of {\em memory-tight reductions}
(Auerbach et al, CRYPTO '17). These are reductions that only incur
minimal memory costs over those of the original adversary, allowing
precise security statements for memory-bounded adversaries (under
appropriate assumptions expressed in terms of adversary time and
memory usage). Despite its importance, only a few techniques to
achieve memory-tightness are known and impossibility results in
prior works show that even basic, textbook reductions cannot be
made memory-tight.
This paper introduces a new class of memory-tight reductions which
leverage random strings in the interaction with the adversary to hide
state information, thus shifting the memory costs to the adversary.
We exhibit this technique with several examples.
We give memory-tight proofs for digital signatures allowing
many forgery attempts when considering randomized message distributions
or probabilistic RSA-FDH signatures specifically.
We
prove security of the authenticated encryption scheme
Encrypt-then-PRF with a memory-tight reduction to the underlying
encryption scheme.
By considering specific schemes or
restricted definitions we avoid generic
impossibility results of Auerbach et al.~(CRYPTO '17)
and Ghoshal et al.~(CRYPTO '20).
As a further case study, we consider the textbook equivalence of
CCA-security for public-key encryption for one or
multiple encryption queries. We show two
qualitatively different memory-tight versions of this result,
depending on the considered notion of CCA security.
2022
CRYPTO
On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing
📺
Abstract
We study the power of preprocessing adversaries in finding bounded-length collisions in the widely used Merkle-Damgard (MD) hashing in the random oracle model. Specifically, we consider adversaries which have arbitrary $S$-bit advice about the random oracle and can make at most $T$ queries to it. Our goal is to characterize the advantage of such adversaries in finding a $B$-block collision in an MD hash function constructed using the random oracle with range size $N$ as the compression function (given a random salt).
The answer to this question is completely understood for very large values of $B$ (essentially $\Omega(T)$) as well as for $B=1,2$. For $B\approx T$, Coretti et al.~(EUROCRYPT '18) gave matching upper and lower bounds of $\tilde\Theta(ST^2/N)$. Akshima et al.~(CRYPTO '20) observed that the attack of Coretti et al.\ could be adapted to work for any value of $B>1$, giving an attack with advantage $\tilde\Omega(STB/N + T^2/N)$. Unfortunately, they could only prove that this attack is optimal for $B=2$. Their proof involves a compression argument with exhaustive case analysis and, as they claim, a naive attempt to generalize their bound to larger values of B (even for $B=3$) would lead to an explosion in the number of cases needed to be analyzed, making it unmanageable. With the lack of a more general upper bound, they formulated the \emph{STB conjecture}, stating that the best-possible advantage is $\tildeO(STB/N + T^2/N)$ for any $B>1$.
In this work, we confirm the STB conjecture in many new parameter settings. For instance, in one result, we show that the conjecture holds for all constant values of $B$, significantly extending the result of Akshima et al. Further, using combinatorial properties of graphs, we are able to confirm the conjecture even for super constant values of $B$, as long as some restriction is made on $S$. For instance, we confirm the conjecture for all $B \le T^{1/4}$ as long as $S \le T^{1/8}$. Technically, we develop structural characterizations for bounded-length collisions in MD hashing that allow us to give a compression argument in which the number of cases needed to be handled does not explode.
2022
CRYPTO
Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
📺
Abstract
Sponge hashing is a novel alternative to the popular Merkle-Damg\aa rd hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA-3 hashing standard. Sponge hashing is parametrized by two numbers, $r$ and $c$ (bitrate and capacity, respectively), and by a fixed-size permutation on $r+c$ bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with an arbitrary $S$-bit auxiliary advice input about the random permutation and $T$ queries. Recent work by Coretti et al.\ (CRYPTO '18) showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Theta(ST^2/2^c + T^2/ 2^{r})$.
Although the above attack formally breaks collision resistance in some range of parameters, its practical relevance is limited since the resulting collision is very long (on the order of $T$ blocks). Focusing on the task of finding \emph{short} collisions, we study the complexity of finding a $B$-block collision for a given parameter $B\ge 1$. We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage
\begin{align*}
\Omega \left(\left(\frac{S^{2}T}{2^{2c}}\right)^{2/3} + \frac{T^2}{2^r}\right).
\end{align*}
In some range of parameters, our attack has constant advantage of winning while the previously-known best attack has exponentially small advantage. To the best of our knowledge, this is the first natural application for which sponge hashing is \emph{provably less secure} than the corresponding instance of Merkle-Damg\aa rd hashing.
Our attack relies on a novel connection between single-block collision finding in sponge hashing and the well-studied function inversion problem.
We also give a general attack that works for any $B\ge 2$ and has advantage $\Omega({STB}/{2^{c}} + {T^2}/{2^{\min\{r,c\}}})$, adapting an idea of Akshima et al. (CRYPTO '20).
We complement the above attacks with bounds on the best possible attacks. Specifically, we prove that there is a qualitative jump in the
advantage of best possible attacks for finding unbounded-length collisions and those for finding very short collisions. Most notably, we prove (via a highly non-trivial compression argument) that the above attack is optimal for $B=2$ and in some range of parameters.
2021
CRYPTO
Tight State-Restoration Soundness in the Algebraic Group Model
📺
Abstract
Most efficient zero-knowledge arguments lack a concrete security
analysis, making parameter choices and efficiency comparisons
challenging. This is even more true for non-interactive versions of
these systems obtained via the Fiat-Shamir transform, for which the
security guarantees generically derived from the interactive
protocol are often too weak, even when assuming a random oracle.
This paper initiates the study of {\em state-restoration soundness}
in the algebraic group model (AGM) of Fuchsbauer, Kiltz, and Loss
(CRYPTO '18). This is a stronger notion of soundness for an
interactive proof or argument which allows the prover to rewind the
verifier, and which is tightly connected with the concrete soundness
of the non-interactive argument obtained via the Fiat-Shamir
transform.
We propose a general methodology to prove tight bounds on
state-restoration soundness, and apply it to variants of
Bulletproofs (Bootle et al, S\&P '18) and Sonic (Maller et al., CCS
'19). To the best of our knowledge, our analysis of Bulletproofs
gives the {\em first} non-trivial concrete security analysis for a
non-constant round argument combined with the Fiat-Shamir transform.
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.
2018
TOSC
Lightweight and Side-channel Secure 4 × 4 S-Boxes from Cellular Automata Rules
📺
Abstract
This work focuses on side-channel resilient design strategies for symmetrickey cryptographic primitives targeting lightweight applications. In light of NIST’s lightweight cryptography project, design choices for block ciphers must consider not only security against traditional cryptanalysis, but also side-channel security, while adhering to low area and power requirements. In this paper, we explore design strategies for substitution-permutation network (SPN)-based block ciphers that make them amenable to low-cost threshold implementations (TI) - a provably secure strategy against side-channel attacks. The core building blocks for our strategy are cryptographically optimal 4×4 S-Boxes, implemented via repeated iterations of simple cellular automata (CA) rules. We present highly optimized TI circuits for such S-Boxes, that consume nearly 40% less area and power as compared to popular lightweight S-Boxes such as PRESENT and GIFT. We validate our claims via implementation results on ASIC using 180nm technology. We also present a comparison of TI circuits for two popular lightweight linear diffusion layer choices - bit permutations and MixColumns using almost-maximum-distance-separable (almost-MDS) matrices. We finally illustrate design paradigms that combine the aforementioned TI circuits for S-Boxes and diffusion layers to obtain fully side-channel secure SPN block cipher implementations with low area and power requirements.
Coauthors
- Nilanjan Datta (1)
- Cody Freitag (1)
- Riddhi Ghosal (1)
- Joseph Jaeger (2)
- Ilan Komargodski (2)
- Debdeep Mukhopadhyay (1)
- Sikhar Patranabis (1)
- Stjepan Picek (1)
- Rajat Sadhukhan (1)
- Stefano Tessaro (4)