International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jian Guo

Affiliation: Nanyang Technological University, Singapore

Publications

Year
Venue
Title
2019
FSE
2019
TOSC
Zero-Correlation Attacks on Tweakable Block Ciphers with Linear Tweakey Expansion 📺
The design and analysis of dedicated tweakable block ciphers is a quite recent and very active research field that provides an ongoing stream of new insights. For instance, results of Kranz, Leander, and Wiemer from FSE 2017 show that the addition of a tweak using a linear tweak schedule does not introduce new linear characteristics. In this paper, we consider – to the best of our knowledge – for the first time the effect of the tweak on zero-correlation linear cryptanalysis for ciphers that have a linear tweak schedule. It turns out that the tweak can often be used to get zero-correlation linear hulls covering more rounds compared to just searching zero-correlation linear hulls on the data-path of a cipher. Moreover, this also implies the existence of integral distinguishers on the same number of rounds. We have applied our technique on round reduced versions of Qarma, Mantis, and Skinny. As a result, we can present – to the best of our knowledge – the best attack (with respect to number of rounds) on a round-reduced variant of Qarma.
2019
TOSC
PEIGEN – a Platform for Evaluation, Implementation, and Generation of S-boxes 📺
In this paper, a platform named PEIGEN is presented to evaluate security, find efficient software/hardware implementations, and generate cryptographic S-boxes. Continuously developed for decades, S-boxes are constantly evolving in terms of the design criteria for both security requirements and software/hardware performances. PEIGEN is aimed to be a platform covering a comprehensive check-list of design criteria of S-boxes appearing in the literature. To do so, the security requirements are first intensively surveyed, existing tools of S-boxes are then comprehensively compared, and finally our platform PEIGEN is presented. The survey part is aimed to be a systematic reference for the theoretical study of S-boxes. The platform is aimed to be an assistant tool for the experimental study and practical use of S-boxes. PEIGEN not only integrates most of the features in existing tools, but also equips with functionalities to evaluate new security-related properties, improves the efficiency of the search algorithms for optimized implementations in several aspects. With the help of this powerful platform, many interesting observations are made in-between the security notations, as well as on the S-boxes used in the existing symmetrickey cryptographic primitives. PEIGEN will become an open platform and welcomes contributions from all parties to help the community to facilitate the research and use of S-boxes.
2019
TOSC
ZOCB and ZOTR: Tweakable Blockcipher Modes for Authenticated Encryption with Full Absorption
We define ZOCB and ZOTR for nonce-based authenticated encryption with associated data, and analyze their provable security. These schemes use a tweakable blockcipher (TBC) as the underlying primitive, and fully utilize its input to process a plaintext and associated data (AD). This property is commonly referred to as full absorption, and this has been explored for schemes based on a permutation or a pseudorandom function (PRF). Our schemes improve the efficiency of TBC-based counterparts of OCB and OTR called OCB3 (Krovetz and Rogaway, FSE 2011) and OTR (Minematsu, EUROCRYPT 2014). Specifically, ΘCB3 and OTR have an independent part to process AD, and our schemes integrate this process into the encryption part of a plaintext by using the tweak input of the TBC. Up to a certain length of AD, ZOCB and ZOTR completely eliminate the independent process for it. Even for longer AD, our schemes process it efficiently by fully using the tweak input of the TBC. For this purpose, based on previous tweak extension schemes for TBCs, we introduce a scheme called XTX*. To our knowledge, ZOCB and ZOTR are the first efficiency improvement of ΘCB3 and OTR in terms of the number of TBC calls. Compared to Sponge-based and PRF-based schemes, ZOCB and ZOTR allow fully parallel computation of the underlying primitive, and have a unique design feature that an authentication tag is independent of a part of AD. We present experimental results illustrating the practical efficiency gain and clarifying the efficiency cost for it with a concrete instantiation. The results show that for long input data, our schemes have gains, while we have efficiency loss for short input data.
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
TOSC
Key-Recovery Attacks on Full Kravatte
This paper presents a cryptanalysis of full Kravatte, an instantiation of the Farfalle construction of a pseudorandom function (PRF) with variable input and output length. This new construction, proposed by Bertoni et al., introduces an efficiently parallelizable and extremely versatile building block for the design of symmetric mechanisms, e.g. message authentication codes or stream ciphers. It relies on a set of permutations and on so-called rolling functions: it can be split into a compression layer followed by a two-step expansion layer. The key is expanded and used to mask the inputs and outputs of the construction. Kravatte instantiates Farfalle using linear rolling functions and permutations obtained by iterating the Keccak round function.We develop in this paper several attacks against this PRF, based on three different attack strategies that bypass part of the construction and target a reduced number of permutation rounds. A higher order differential distinguisher exploits the possibility to build an affine space of values in the cipher state after the compression layer. An algebraic meet-in-the-middle attack can be mounted on the second step of the expansion layer. Finally, due to the linearity of the rolling function and the low algebraic degree of the Keccak round function, a linear recurrence distinguisher can be found on intermediate states of the second step of the expansion layer. All the attacks rely on the ability to invert a small number of the final rounds of the construction. In particular, the last two rounds of the construction together with the final masking by the key can be algebraically inverted, which allows to recover the key.The complexities of the devised attacks, applied to the Kravatte specifications published on the IACR ePrint in July 2017, or the strengthened version of Kravatte recently presented at ECC 2017, are far below the security claimed.
2018
ASIACRYPT
New MILP Modeling: Improved Conditional Cube Attacks on Keccak-Based Constructions
In this paper, we propose a new MILP modeling to find better or even optimal choices of conditional cubes, under the general framework of conditional cube attacks. These choices generally find new or improved attacks against the keyed constructions based on Keccak permutation and its variants, including Keccak-MAC, KMAC, Keyak, and Ketje, in terms of attack complexities or the number of attacked rounds. Interestingly, conditional cube attacks were applied to round-reduced Keccak-MAC, but not to KMAC despite the great similarity between Keccak-MAC and KMAC, and the fact that KMAC is the NIST standard way of constructing MAC from SHA-3. As examples to demonstrate the effectiveness of our new modeling, we report key recovery attacks against KMAC128 and KMAC256 reduced to 7 and 9 rounds, respectively; the best attack against Lake Keyak with 128-bit key is improved from 6 to 8 rounds in the nonce-respected setting and 9 rounds of Lake Keyak can be attacked if the key size is of 256 bits; attack complexity improvements are found generally on other constructions. Our new model is also applied to Keccak-based full-state keyed sponge and gives a positive answer to the open question proposed by Bertoni et al. whether cube attacks can be extended to more rounds by exploiting full-state absorbing. To verify the correctness of our attacks, reduced-variants of the attacks are implemented and verified on a PC practically. It is remarked that this work does not threaten the security of any full version of the instances analyzed in this paper.
2018
TOSC
Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP 📺
Ling Song Jian Guo
Cube-attack-like cryptanalysis on round-reduced Keccak was proposed by Dinur et al. at EUROCRYPT 2015. It recovers the key through two phases: the preprocessing phase for precomputing a look-up table and online phase for querying the output and getting the cube sum with which the right key can be retrieved by looking up the precomputed table. It was shown that such attacks are efficient specifically for Keccak-based constructions with small nonce or message block size. In this paper, we provide a mixed integer linear programming (MILP) model for cubeattack- like cryptanalysis on keyed Keccak, which does not impose any unnecessary constraint on cube variables and finds almost optimal cubes by balancing the two phases of cube-attack-like cryptanalysis. Our model is applied to Ketje Jr, Ketje Sr, a Xoodoo-based authenticated encryption and Keccak-MAC-512, all of which have a relatively small nonce or message block size. As a result, time complexities of 5-round attacks on Ketje Jr and 7-round attacks on Ketje Sr can be improved significantly. Meanwhile, 6-round attacks, one more round than the previous best attack, are possible if the key size of Ketje V1 (V2) is reduced to 72 (80) bits. For Xoodoo-based AE in Ketje style, the attack reaches 6 rounds. Additionally, a 7-round attack of Keccak-MAC-512 is achieved. To verify the correctness of our attacks, a 5-round attack on Ketje V1 is implemented and tested practically. It is noted that this work does not threaten the security of any Keccak-based construction.
2017
EUROCRYPT
2017
CRYPTO
2017
CRYPTO
2017
TOSC
Some cryptanalytic results on Lizard
Lizard is a lightweight stream cipher proposed by Hamann, Krause and Meier in IACR ToSC 2017. It has a Grain-like structure with two state registers of size 90 and 31 bits. The cipher uses a 120-bit secret key and a 64-bit IV. The authors claim that Lizard provides 80-bit security against key recovery attacks and a 60-bit security against distinguishing attacks. In this paper, we present an assortment of results and observations on Lizard. First, we show that by doing 258 random trials it is possible to find a set of 264 triplets (K, IV0, IV1) such that the Key-IV pairs (K, IV0) and (K, IV1) produce identical keystream bits. Second, we show that by performing only around 228 random trials it is possible to obtain 264 Key-IV pairs (K0, IV0) and (K1, IV1) that produce identical keystream bits. Thereafter, we show that one can construct a distinguisher for Lizard based on IVs that produce shifted keystream sequences. The process takes around 251.5 random IV encryptions (with encryption required to produce 218 keystream bits) and around 276.6 bits of memory. Next, we propose a key recovery attack on a version of Lizard with the number of initialization rounds reduced to 223 (out of 256) based on IV collisions. We then outline a method to extend our attack to 226 rounds. Our results do not affect the security claims of the designers.
2016
EUROCRYPT
2016
CRYPTO
2016
ASIACRYPT
2016
ASIACRYPT
2016
TOSC
Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs
We present an invariant subspace attack on the block cipher Midori64, proposed at Asiacrypt 2015. Our analysis shows that Midori64 has a class of 232 weak keys. Under any such key, the cipher can be distinguished with only a single chosen query, and the key can be recovered in 216 time with two chosen queries. As both the distinguisher and the key recovery have very low complexities, we confirm our analysis by implementing the attacks. Some tweaks of round constants make Midori64 more resistant to the attacks, but some lead to even larger weak-key classes. To eliminate the dependency on the round constants, we investigate alternative S-boxes for Midori64 that provide certain level of security against the found invariant subspace attacks, regardless of the choice of the round constants. Our search for S-boxes is enhanced with a dedicated tool which evaluates the depth of any given 4-bit S-box that satisfies certain design criteria. The tool may be of independent interest to future S-box designs.
2016
TOSC
Meet-in-the-Middle Attacks on Classes of Contracting and Expanding Feistel Constructions
We show generic attacks on unbalanced Feistel ciphers based on the meet-in-the-middle technique. We analyze two general classes of unbalanced Feistel structures, namely contracting Feistels and expanding Feistels. In both of the cases, we consider the practical scenario where the round functions are keyless and known to the adversary. In the case of contracting Feistels with 4 branches, we show attacks on 16 rounds when the key length k (in bits) is as large as the block length n (in bits), and up to 24 rounds when k = 2n. In the case of expanding Feistels, we consider two scenarios: one, where different nonlinear functions without particular structures are used in the round function, and a more practical one, where a single nonlinear is used but different linear functions are introduced in the state update. In the former case, we propose generic attacks on 13 rounds when k = n, and up to 21 rounds when k = 2n. In the latter case, 16 rounds can be attacked for k = n, and 24 rounds for k = 2n.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
CRYPTO
2014
EPRINT
2014
EPRINT
2014
ASIACRYPT
2014
FSE
2014
FSE
2013
ASIACRYPT
2012
FSE
2012
FSE
2011
CRYPTO
2011
CHES
2010
EPRINT
Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2
We revisit narrow-pipe designs that are in practical use, and their security against preimage attacks. Our results are the best known preimage attacks on Tiger, MD4, and reduced SHA-2, with the result on Tiger being the first cryptanalytic shortcut attack on the full hash function. Our attacks runs in time $2^{188.8}$ for finding preimages, and $2^{188.2}$ for second-preimages. Both have memory requirement of order $2^{8}$, which is much less than in any other recent preimage attacks on reduced Tiger. Using pre-computation techniques, the time complexity for finding a new preimage or second-preimage for MD4 can now be as low as $2^{78.4}$ and $2^{69.4}$ MD4 computations, respectively. The second-preimage attack works for all messages longer than 2 blocks. To obtain these results, we extend the meet-in-the-middle framework recently developed by Aoki and Sasaki in a series of papers. In addition to various algorithm-specific techniques, we use a number of conceptually new ideas that are applicable to a larger class of constructions. Among them are (1) incorporating multi-target scenarios into the MITM framework, leading to faster preimages from pseudo-preimages, (2) a simple precomputation technique that allows for finding new preimages at the cost of a single pseudo-preimage, and (3) probabilistic initial structures, compared with deterministic ones, to enable more neutral words, and hence to reduce the attack time complexity. All the techniques developed await application to other hash functions. To illustrate this, we give as another example improved preimage attacks on SHA-2 members.
2010
EPRINT
Differential and invertibility properties of BLAKE (full version)
BLAKE is a hash function selected by NIST as one of the 14 second round candidates for the SHA-3 Competition. In this paper, we follow a bottom-up approach to exhibit properties of BLAKE and of its building blocks: based on differential properties of the internal function G, we show that a round of BLAKE is a permutation on the message space, and present an efficient inversion algorithm. For 1.5 rounds we present an algorithm that finds preimages faster than in previous attacks. Discovered properties lead us to describe large classes of impossible differentials for two rounds of BLAKE’s internal permutation, and particular impossible differentials for five and six rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear and rotation-free model, we describe near-collisions for four rounds of the compression function. Finally, we discuss the problem of establishing upper bounds on the probability of differential characteristics for BLAKE.
2010
ASIACRYPT
2010
FSE
2009
ASIACRYPT
2009
FSE
2008
FSE
2008
EPRINT
Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits
LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we point out that there exist some errors in the calculation of Zhao & Qi's attack. After re-calculating, the result shows that their attack is unable for attacking RSA with primes sharing bits. Consequently, we give a revised version to make their attack feasible. We also propose a new method to further extend the security boundary, compared with the revised version. The proposed attack also supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than (n/4) least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.
2007
EPRINT
Cryptanalysis of LASH
We show that the LASH-$x$ hash function is vulnerable to attacks that trade time for memory, including collision attacks as fast as $2^{\frac{4}{11}x}$ and preimage attacks as fast as $2^{\frac47x}$. Moreover, we describe heuristic lattice based collision attacks that use small memory but require very long messages. Based upon experiments, the lattice attacks are expected to find collisions much faster than $2^{x/2}$. All of these attacks exploit the designers' choice of an all zero IV. We then consider whether LASH can be patched simply by changing the IV. In this case, we show that LASH is vulnerable to a $2^{\frac78x}$ preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key. None of our attacks depend upon the particular contents of the LASH matrix -- we only assume that the distribution of elements is more or less uniform. Additionally, we show a generalized birthday attack on the final compression of LASH which requires $O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory. Our method extends the Wagner algorithm to truncated sums, as is done in the final transform in LASH.

Program Committees

Eurocrypt 2020
FSE 2019
TCC 2019
Asiacrypt 2019
Eurocrypt 2018
FSE 2018
FSE 2017
Asiacrypt 2017