## CryptoDB

### Jian Guo

#### Affiliation: Nanyang Technological University, Singapore

#### Publications

**Year**

**Venue**

**Title**

2020

TOSC

Improved Security Evaluation of SPN Block Ciphers and its Applications in the Single-key Attack on SKINNY
Abstract

In this paper, a new method for evaluating the integral property, truncated and impossible differentials for substitution-permutation network (SPN) block ciphers is proposed. The main assumption is an explicit description/expression of the internal state words in terms of the plaintext (ciphertext) words. By counting the number of times these words occur in the internal state expression, we can evaluate the resistance of a given block cipher to integral and impossible/truncated differential attacks more accurately than previous methods. More precisely, we explore the cryptographic consequences of uneven frequency of occurrences of plaintext (ciphertext) words appearing in the algebraic expression of the internal state words. This approach gives a new family of distinguishers employing different concepts such as the integral property, impossible/truncated differentials and the so-called zero-sum property. We then provide algorithms to determine the maximum number of rounds of such new types of distinguishers for SPN block ciphers. The potential and efficiency of this relatively simple method is confirmed through applications. For instance, in the case of SKINNY block cipher, several 10-round integral distinguishers, all of the 11-round impossible differentials, and a 7-round truncated differential could be determined. For the last case, using a single pair of plaintexts differing in three words so that (a = b = c) ≠ (a’ = b’ = c’), we are able to distinguish 7-round SKINNY from random permutations. More importantly, exploiting our distinguishers, we give the first practical attack on 11-round SKINNY-128-128 in the single-key setting (a theoretical attack reaches 16 rounds). Finally, using the same ideas, we provide a concise explanation on the existing distinguishers for round-reduced AES.

2020

TOSC

Improved Meet-in-the-Middle Preimage Attacks against AES Hashing Modes
Abstract

Hashing modes are ways to convert a block cipher into a hash function, and those with AES as the underlying block cipher are referred to as AES hashing modes. Sasaki in 2011, introduced the first preimage attack against AES hashing modes with the AES block cipher reduced to 7 rounds, by the method of meet-in-the-middle. In his attack, the key-schedules are not taken into account. Hence, the same attack applies to all three versions of AES. In this paper, by introducing neutral bits from the key, extra degree of freedom is gained, which is utilized in two ways, i.e., to reduce the time complexity and to extend the attack to more rounds. As an immediate result, the complexities of 7-round pseudo-preimage attacks are reduced from 2120 to 2104, 296, and 296 for AES-128, AES-192, and AES-256, respectively. By carefully choosing the neutral bits from the key to cancel those from the state, the attack is extended to 8 rounds for AES-192 and AES-256 with complexities 2112 and 296. Similar results are obtained for Kiasu-BC, a tweakable block cipher based on AES-128, and interestingly the additional input tweak helps reduce the complexity and extend the attack to one more round. To the best of our knowledge, these are the first preimage attacks against 8-round AES hashing modes.

2020

JOFC

Practical Collision Attacks against Round-Reduced SHA-3
Abstract

The Keccak hash function is the winner of the SHA-3 competition (2008–2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some Keccak variants. Following the framework developed by Dinur et al. at FSE 2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3 , namely 5-round SHAKE128 , SHA3 -224 and SHA3 -256, and three instances of Keccak contest, namely Keccak [1440, 160, 5, 160], Keccak [640, 160, 5, 160] and Keccak [1440, 160, 6, 160], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family.

2020

EUROCRYPT

TNT: How to Tweak a Block Cipher
📺
Abstract

In this paper, we propose Tweak-aNd-Tweak (TNT for short) mode, which builds a tweakable block cipher from three independent block ciphers. TNT handles the tweak input by simply XOR-ing the unmodified tweak into the internal state of block ciphers twice. Due to its simplicity, TNT can also be viewed as a way of turning a block cipher into a tweakable block cipher by dividing the block cipher into three chunks, and adding the tweak at the two cutting points only. TNT is proven to be of beyond-birthday-bound $2^{2n/3}$ security, under the assumption that the three chunks are independent secure $n$-bit SPRPs. It clearly brings minimum possible overhead to both software and hardware implementations. To demonstrate this, an instantiation named TNT-AES with 6, 6, 6 rounds of AES as the underlying block ciphers is proposed. Besides the inherent proven security bound and tweak-independent rekeying feature of the TNT mode, the performance of TNT-AES is comparable with all existing TBCs designed through modular methods.

2019

TOSC

Zero-Correlation Attacks on Tweakable Block Ciphers with Linear Tweakey Expansion
📺
Abstract

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
📺
Abstract

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
Abstract

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.

2019

JOFC

Generic Attacks on Hash Combiners
Abstract

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
Abstract

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
★
Abstract

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
Abstract

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
📺
Abstract

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

CRYPTO

2017

TOSC

Some cryptanalytic results on Lizard
Abstract

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

TOSC

Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs
Abstract

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
Abstract

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

2010

EPRINT

Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2
Abstract

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)
Abstract

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 BLAKEs 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

2008

EPRINT

Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits
Abstract

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
Abstract

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
- Asiacrypt 2020
- FSE 2019
- Asiacrypt 2019
- Eurocrypt 2018
- FSE 2018
- FSE 2017
- Asiacrypt 2017

#### Coauthors

- Ralph Ankele (1)
- Kazumaro Aoki (1)
- Jean-Philippe Aumasson (2)
- Subhadeep Banik (1)
- Zhenzhen Bao (7)
- Alex Biryukov (1)
- Meichun Cao (1)
- Colin Chaigneau (1)
- Scott Contini (2)
- Tingting Cui (1)
- Lin Ding (1)
- Itai Dinur (1)
- Christoph Dobraunig (1)
- Le Dong (1)
- Alexandre Duc (1)
- Dengguo Feng (1)
- Thomas Fuhr (1)
- Praveen Gauravaram (1)
- Henri Gilbert (1)
- Dawu Gu (2)
- Chun Guo (1)
- Takanori Isobe (1)
- Tetsu Iwata (3)
- Jérémy Jean (6)
- Dmitry Khovratovich (1)
- Simon Knellwolf (2)
- Eran Lambooij (1)
- Gregor Leander (1)
- Gaëtan Leurent (1)
- Ruilin Li (1)
- Guohong Liao (2)
- San Ling (7)
- Meicheng Liu (5)
- Guozhen Liu (1)
- Krystian Matusiewicz (6)
- Willi Meier (2)
- Kazuhiko Minematsu (3)
- Sumio Morioka (2)
- Nicky Mouha (1)
- Ivica Nikolić (5)
- Enes Pasalic (1)
- Thomas Peyrin (5)
- Josef Pieprzyk (3)
- Axel Poschmann (2)
- Kexin Qiao (3)
- Longjiang Qu (1)
- Christian Rechberger (2)
- Jean-René Reinhard (1)
- Vincent Rijmen (2)
- Matthew J. B. Robshaw (1)
- Yu Sasaki (10)
- Danping Shi (1)
- Siang Meng Sim (1)
- Ling Song (8)
- Ron Steinfeld (3)
- Bing Sun (2)
- Hung-Min Sun (1)
- Yosuke Todo (1)
- Huaxiong Wang (6)
- Lei Wang (11)
- Haoyang Wang (1)
- Meiqin Wang (2)
- Lei Wei (1)
- Long Wen (2)
- Shuang Wu (3)
- Mu-En Wu (1)
- Wenling Wu (1)
- Guoyan Zhang (1)
- Wenying Zhang (2)
- Jingyuan Zhao (1)
- Jian Zou (1)