International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lei Wang

Publications

Year
Venue
Title
2021
CRYPTO
Revisiting the Security of DbHtS MACs: Beyond-Birthday-Bound in the Multi-User Setting 📺
Double-block Hash-then-Sum (\textsf{DbHtS}) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including \textsf{SUM-ECBC}, \textsf{PMAC\_Plus}, \textsf{3kf9} and \textsf{LightMAC\_Plus}. Recently Datta et al. (FSE'19), and then Kim et al. (Eurocrypt'20) prove that \textsf{DbHtS} constructions are secure beyond the birthday bound in the single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in the multi-user setting. In this work, we revisit the security of \textsf{DbHtS} MACs in the multi-user setting. We propose a generic framework to prove beyond-birthday-bound security for \textsf{DbHtS} constructions. We demonstrate the usability of this framework with applications to key-reduced variants of \textsf{DbHtS} MACs, including \textsf{2k-SUM-ECBC}, \textsf{2k-PMAC\_Plus} and \textsf{2k-LightMAC\_Plus}. Our results show that the security of these constructions will not degrade as the number of users grows. On the other hand, our results also indicate that these constructions are secure beyond the birthday bound in both single-user and multi-user setting without additional domain separation, which is used in the prior work to simplify the analysis. Moreover, we find a critical flaw in \textsf{2kf9}, which is proved to be secure beyond the birthday bound by Datta et al. (FSE'19). We can successfully forge a tag with probability 1 without making any queries. We go further to show attacks with birthday-bound complexity on several variants of \textsf{2kf9}.
2020
TOSC
Improved Security Bounds for Generalized Feistel Networks 📺
We revisit the security of various generalized Feistel networks. Concretely, for unbalanced, alternating, type-1, type-2, and type-3 Feistel networks built from random functions, we substantially improve the coupling analyzes of Hoang and Rogaway (CRYPTO 2010). For a tweakable blockcipher-based generalized Feistelnetwork proposed by Coron et al. (TCC 2010), we present a coupling analysis and for the first time show that with enough rounds, it achieves 2n-bit security, and this provides highly secure, double-length tweakable blockciphers.
2019
TOSC
On Beyond-Birthday-Bound Security: Revisiting the Development of ISO/IEC 9797-1 MACs 📺
Yaobin Shen Lei Wang
ISO/IEC 9797-1 is an international standard for block-cipher-based Message Authentication Code (MAC). The current version ISO/IEC 9797-1:2011 specifies six single-pass CBC-like MAC structures that are capped at the birthday bound security. For a higher security that is beyond-birthday bound, it recommends to use the concatenation combiner of two single-pass MACs. In this paper, we reveal the invalidity of the suggestion, by presenting a birthday bound forgery attack on the concatenation combiner, which is essentially based on Joux’s multi-collision. Notably, our new forgery attack for the concatenation of two MAC Algorithm 1 with padding scheme 2 only requires 3 queries. Moreover, we look for patches by revisiting the development of ISO/IEC 9797-1 with respect to the beyond-birthday bound security. More specifically, we evaluate the XOR combiner of single-pass CBC-like MACs, which was used in previous version of ISO/IEC 9797-1.
2019
JOFC
Generic Attacks on Hash Combiners
Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) combiner $$ \mathcal {H}_1(M) \oplus \mathcal {H}_2(M) $$ H 1 ( M ) ⊕ H 2 ( M ) and the concatenation combiner $$ \mathcal {H}_1(M) \Vert \mathcal {H}_2(M) $$ H 1 ( M ) ‖ H 2 ( M ) . Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice $$\mathcal {H}_2(\mathcal {H}_1(IV, M), M)$$ H 2 ( H 1 ( I V , M ) , M ) and the Zipper hash $$\mathcal {H}_2(\mathcal {H}_1(IV, M), \overleftarrow{M})$$ H 2 ( H 1 ( I V , M ) , M ← ) , where $$\overleftarrow{M}$$ M ← is the reverse of the message M . In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows: 1. Several generic preimage attacks on the XOR combiner: A first attack with a best-case complexity of $$ 2^{5n/6} $$ 2 5 n / 6 obtained for messages of length $$ 2^{n/3} $$ 2 n / 3 . It relies on a novel technical tool named interchange structure. It is applicable for combiners whose underlying hash functions follow the Merkle–Damgård construction or the HAIFA framework. A second attack with a best-case complexity of $$ 2^{2n/3} $$ 2 2 n / 3 obtained for messages of length $$ 2^{n/2} $$ 2 n / 2 . It exploits properties of functional graphs of random mappings. It achieves a significant improvement over the first attack but is only applicable when the underlying hash functions use the Merkle–Damgård construction. An improvement upon the second attack with a best-case complexity of $$ 2^{5n/8} $$ 2 5 n / 8 obtained for messages of length $$ 2^{5n/8} $$ 2 5 n / 8 . It further exploits properties of functional graphs of random mappings and uses longer messages. These attacks show a rather surprising result: regarding preimage resistance, the sum of two n -bit narrow-pipe hash functions following the considered constructions can never provide n -bit security. 2. A generic second-preimage attack on the concatenation combiner of two Merkle–Damgård hash functions. This attack finds second preimages faster than $$ 2^n $$ 2 n for challenges longer than $$ 2^{2n/7} $$ 2 2 n / 7 and has a best-case complexity of $$ 2^{3n/4} $$ 2 3 n / 4 obtained for challenges of length $$ 2^{3n/4} $$ 2 3 n / 4 . It also exploits properties of functional graphs of random mappings. 3. The first generic second-preimage attack on the Zipper hash with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is $$ 2^{3n/5} $$ 2 3 n / 5 , obtained for challenge messages of length $$ 2^{2n/5} $$ 2 2 n / 5 . 4. An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is $$ 2^{13n/22} $$ 2 13 n / 22 , obtained for challenge messages of length $$ 2^{13n/22} $$ 2 13 n / 22 . The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two n -bit narrow-pipe Merkle–Damgård hash functions do not provide much more security than that can be provided by a single n -bit hash function. Our main technical contributions include the following: 1. The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input. 2. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multi-collision for both of the underlying hash functions. 3. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.
2018
TOSC
Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions
We provide a survey about generic attacks on cryptographic hash constructions including hash-based message authentication codes and hash combiners. We look into attacks involving iteratively evaluating identical mappings many times. The functional graph of a random mapping also involves iteratively evaluating the mapping. These attacks essentially exploit properties of the functional graph. We map the utilization space of those properties from numerous proposed known attacks, draw a comparison among classes of attacks about their advantages and limitations. We provide a systematic exposition of concepts of cycles, deep-iterate images, collisions and their roles in cryptanalysis of iterated hash constructions. We identify the inherent relationship between these concepts, such that case-by-case theories about them can be unified into one knowledge system, that is, theories on the functional graph of random mappings. We show that the properties of the cycle search algorithm, the chain evaluation algorithm and the collision search algorithm can be described based on statistic results on the functional graph. Thereby, we can provide different viewpoints to support previous beliefs on individual knowledge. In that, we invite more sophisticated analysis of the functional graph of random mappings and more future exploitations of its properties in cryptanalysis.
2018
ASIACRYPT
Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user Security
Chun Guo Lei Wang
Key-Alternating Feistel (KAF) ciphers, a.k.a. Feistel-2 models, refer to Feistel networks with round functions of the form $$F_i(k_i\oplus x_i)$$, where $$k_i$$ is the (secret) round-key and $$F_i$$ is a public random function. This model roughly captures the structures of many famous Feistel ciphers, and the most prominent instance is DES.Existing provable security results on KAF assumed independent round-keys and round functions (ASIACRYPT 2004 & FSE 2014). In this paper, we investigate how to achieve security under simpler and more realistic assumptions: with round-keys derived from a short main-key, and hopefully with identical round functions.For birthday-type security, we consider 4-round KAF, investigate the minimal conditions on the way to derive the four round-keys, and prove that when such adequately derived keys and the same round function are used, the 4-round KAF is secure up to $$2^{n/2}$$ queries.For beyond-birthday security, we focus on 6-round KAF. We prove that when the adjacent round-keys are independent, and independent round-functions are used, the 6 round KAF is secure up to $$2^{2n/3}$$ queries. To our knowledge, this is the first beyond-birthday security result for KAF without assuming completely independent round-keys.Our results hold in the multi-user setting as well, constituting the first non-trivial multi-user provable security results on Feistel ciphers. We finally demonstrate applications of our results on designing key-schedules and instantiating keyed sponge constructions.
2017
CRYPTO
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
FSE
2015
EUROCRYPT
2015
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
FSE
2014
FSE
2013
ASIACRYPT
2013
ASIACRYPT
2013
ASIACRYPT
2013
FSE
2013
FSE
2012
ASIACRYPT
2012
ASIACRYPT
2010
ASIACRYPT
2010
FSE
2009
EPRINT
How to Prove the Security of Practical Cryptosystems with Merkle-Damg{\aa}rd Hashing by Adopting Indifferentiability
In this paper, we show that major cryptosystems such as FDH, OAEP, and RSA-KEM are secure under a hash function $MD^h$ with Merkle-Damg{\aa}rd (MD) construction that uses a random oracle compression function $h$. First, we propose two new ideal primitives called Traceable Random Oracle ($\mathcal{TRO}$) and Extension Attack Simulatable Random Oracle ($\mathcal{ERO}$) which are weaker than a random oracle ($\mathcal{RO}$). Second, we show that $MD^h$ is indifferentiable from $\mathcal{LRO}$, $\mathcal{TRO}$ and $\mathcal{ERO}$, where $\mathcal{LRO}$ is Leaky Random Oracle proposed by Yoneyama et al. This result means that if a cryptosystem is secure in these models, then the cryptosystem is secure under $MD^h$ following the indifferentiability theory proposed by Maurer et al. Finally, we prove that OAEP is secure in the $\mathcal{TRO}$ model and RSA-KEM is secure in the $\mathcal{ERO}$ model. Since it is also known that FDH is secure in the $\mathcal{LRO}$ model, as a result, major cryptosystems, FDH, OAEP and RSA-KEM, are secure under $MD^h$, though $MD^h$ is not indifferentiable from $\mathcal{RO}$.
2009
EPRINT
Davies-Meyer Merkle-Damg{\aa}rd Revisited:\\Variants of Indifferentiability and Random Oracles
In this paper, we succeed in analyzing practical cryptosystems that employ the Davies-Meyer Merkle-Damg{\aa}rd hash function $\mddm^E$ with ideal cipher $E$ by using two approaches: {\it indifferentiability from variants of random oracles} and {\it indifferentiability from a random oracle $\ro$ with conditions}. We show that RSA-KEM with $\mddm^E$ is secure by using the former approach and that OAEP with $\mddm^E$ is secure by using the latter approach. The public-use random oracle ($\pubro$) model is a variant of random oracle (proposed by Dodis et al. and Yoneyama et al.). We also show that cryptosystems secure under $\pubro$ model, such as FDH, Fiat-Shamir, PSS and so on, are also secure under $\mddm^E$ by using the former approach. Note that Dodis et al. failed in the paper of EUROCRYPT 2009 in analyzing the security of cryptosystems with $\mddm^E$, because they started by analyzing the underlying compression function, while our first approach starts by analyzing the hash function.
2009
ASIACRYPT
2009
ASIACRYPT
2008
EUROCRYPT
2007
FSE

Program Committees

FSE 2019
FSE 2018
FSE 2017
Asiacrypt 2017
FSE 2016
Eurocrypt 2014