International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Dongdai Lin

Publications

Year
Venue
Title
2023
EUROCRYPT
Impossibility of Indifferentiable Iterated Blockciphers from 3 or Less Primitive Calls
Chun Guo Lei Wang Dongdai Lin
Virtually all modern blockciphers are {\it iterated}. In this paper, we ask: to construct a secure iterated blockcipher ``non-trivially'', how many calls to random functions and permutations are necessary? When security means {\it indistinguishability from a random permutation}, optimality is achieved by the Even-Mansour scheme using 1 call to a public permutation. We seek for the arguably strongest security {\it indifferentiability from an ideal cipher}, a notion introduced by Maurer et al. (TCC 2004) and popularized by Coron et al. (JoC, 2014). We provide the first generic negative result/lower bounds: when the key is not too short, no iterated blockciphers making 3 calls is (statistically) indifferentiable. This proves optimality for a 4-call positive result of Guo et al. (Eprint 2016). Furthermore, using 1 or 2 calls, even indifferentiable iterated blockciphers with polynomial keyspace are impossible. To prove this, we develop an abstraction of idealized iterated blockciphers and establish various basic properties, and apply Extremal Graph Theory results to prove the existence of certain (generalized) non-random properties such as the boomerang and yoyo.
2023
TCHES
Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate
Lattice reduction algorithms have been proved to be one of the most powerful and versatile tools in public key cryptanalysis. In this work, we primarily concentrate on lattice attacks against (EC)DSA with nonce leakage via some sidechannel analysis. Previous works relying on lattice reduction algorithms such as LLL and BKZ will finally lead to the “lattice barrier”: lattice algorithms become infeasible when only fewer nonce is known. Recently, Albrecht and Heninger introduced lattice algorithms augmented with a predicate and broke the lattice barrier (Eurocrypt 2021). We improve their work in several aspects.We first propose a more efficient predicate algorithm which aims to search for the target lattice vector in a large database. Then, we combine sieving with predicate algorithm with the “dimensions for free” and “progressive sieving” techniques to further improve the performance of our attacks. Furthermore, we give a theoretic analysis on how to choose the optimal Kannan embedding factor.As a result, our algorithm outperforms the state-of-the-art lattice attacks for existing records such as 3-bit nonce leakage for a 256-bit curve and 2-bit nonce leakage for a 160-bit curve in terms of running time, sample numbers and success probability. We also break the lattice records on the 384-bit curve with 3-bit nonce leakage and the 256-bit curve with 2-bit nonce leakage which are thought infeasible previously. Finally, we give the first lattice attack against ECDSA with a single-bit nonce leakage, which enables us to break a 112-bit curve with 1-bit nonce leakage in practical time.
2023
CRYPTO
Moving a Step of ChaCha in Syncopated Rhythm
The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient method for finding a good set of PNBs. A refined framework of key-recovery attack is then formalized for round-reduced ChaCha. The new techniques allow us to break 7.5 rounds of ChaCha without the last XOR and rotation, as well as to bring faster attacks on 6 rounds and 7 rounds of ChaCha.
2021
CRYPTO
Differential-Linear Cryptanalysis from an Algebraic Perspective 📺
The differential-linear cryptanalysis is an important cryptanalytic tool in cryptography, and has been extensively researched since its discovery by Langford and Hellman in 1994. There are nevertheless very few methods to study the middle part where the differential and linear trail connect, besides the Differential-Linear Connectivity Table (Bar-On et al., EUROCRYPT 2019) and the experimental approach. In this paper, we study differential-linear cryptanalysis from an algebraic perspective. We first introduce a technique called Differential Algebraic Transitional Form (DATF) for differential-linear cryptanalysis, then develop a new theory of estimation of the differential-linear bias and techniques for key recovery in differential-linear cryptanalysis. The techniques are applied to the CAESAR finalist ASCON, the AES finalist SERPENT, and the eSTREAM finalist Grain v1. The bias of the differential-linear approximation is estimated for ASCON and SERPENT. The theoretical estimates of the bias are more accurate than that obtained by the DLCT, and the techniques can be applied with more rounds. Our general techniques can also be used to estimate the bias of Grain v1 in differential cryptanalysis, and have a markedly better performance than the Differential Engine tool tailor-made for the cipher. The improved key recovery attacks on round-reduced variants of these ciphers are then proposed. To the best of our knowledge, they are thus far the best known cryptanalysis of SERPENT, as well as the best differential-linear cryptanalysis of ASCON and the best initialization analysis of Grain v1. The results have been fully verified by experiments. Notably, security analysis of SERPENT is one of the most important applications of differential-linear cryptanalysis in the last two decades. The results in this paper update the differential-linear cryptanalysis of SERPENT-128 and SERPENT-256 with one more round after the work of Biham, Dunkelman and Keller in 2003.
2018
EUROCRYPT
2017
TOSC
Direct Construction of Optimal Rotational-XOR Diffusion Primitives
As a core component of SPN block cipher and hash function, diffusion layer is mainly introduced by matrices built from maximum distance separable (MDS) codes. Up to now, most MDS constructions require to perform an equivalent or even exhaustive search. In this paper, we study the cyclic structure of rotational-XOR diffusion layer, a commonly used diffusion primitive over (
2016
ASIACRYPT
2015
TCC
2015
ASIACRYPT
2015
ASIACRYPT
2013
FSE
2012
ASIACRYPT
2011
ASIACRYPT
2007
EUROCRYPT
1988
EUROCRYPT

Program Committees

Asiacrypt 2022 (Program chair)
Asiacrypt 2021
Asiacrypt 2020
PKC 2019 (Program chair)
Asiacrypt 2017
Asiacrypt 2016
Asiacrypt 2013
Asiacrypt 2012