## CryptoDB

### Yu Sasaki

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Quantum Collision Attacks on Reduced SHA-256 and SHA-512
📺
Abstract

In this paper, we study dedicated quantum collision attacks on SHA-256 and SHA-512 for the first time.
The attacks reach 38 and 39 steps, respectively, which significantly improve the classical attacks for 31 and 27 steps.
Both attacks adopt the framework of the previous work that converts many semi-free-start collisions into a 2-block collision, and are faster than the generic attack in the cost metric of time-space tradeoff.
We observe that the number of required semi-free-start collisions can be reduced in the quantum setting, which allows us to convert the previous classical 38 and 39 step semi-free-start collisions into a collision.
The idea behind our attacks is simple and will also be applicable to other cryptographic hash functions.

2021

TCHES

AES-LBBB: AES Mode for Lightweight and BBB-Secure Authenticated Encryption
📺
Abstract

In this paper, a new lightweight authenticated encryption scheme AESLBBB is proposed, which was designed to provide backward compatibility with advanced encryption standard (AES) as well as high security and low memory. The primary design goal, backward compatibility, is motivated by the fact that AES accelerators are now very common for devices in the field; we are interested in designing an efficient and highly secure mode of operation that exploits the best of those AES accelerators. The backward compatibility receives little attention in the NIST lightweight cryptography standardization process, in which only 3 out of 32 round-2 candidates are based on AES. Our mode, LBBB, is inspired by the design of ALE in the sense that the internal state size is a minimum 2n bits when using a block cipher of length n bits for the key and data. Unfortunately, there is no security proof of ALE, and forgery attacks have been found on ALE. In LBBB, we introduce an additional feed from block cipher’s output to the key state via a certain permutation λ, which enables us to prove beyond-birthday-bound (BBB) security. We then specify its AES instance, AES-LBBB, and evaluate its performance for (i) software implementation on a microcontroller with an AES coprocessor and (ii) hardware implementation for an application-specific integrated circuit (ASIC) to show that AES-LBBB performs better than the current state-of-the-art Remus-N2 with AES-128.

2021

ASIACRYPT

Double-Block-Length Hash Function for Minimum Memory Size
Abstract

Sharing a common primitive for multiple functionalities is essential for lightweight cryptography, and NIST's lightweight cryptography competition (LWC) considers the integration of hashing to AEAD. While permutations are natural primitive choices in such a goal, for design diversity, it is interesting to investigate how small block-cipher (BC) based and tweakable block-cipher (TBC) based schemes can be. Double-block-length (DBL) hash function modes are suitable to ensure the same security level for AEAD and hashing, but hard to achieve a small memory size. Romulus, a TBC-based finalist in NIST LWC, introduced the DBL hashing scheme Romulus-H, but it requires $3n+k$ bits of memory using an underlying primitive with an $n$-bit block and a $k$-bit (twea)key. Even the smallest DBL modes in the literature require $2n+k$ bits of memory. Addressing this issue, we present new DBL modes EXEX-NI and EXEX-I achieving $(n+k)$-bit state size, i.e., no extra memory in addition to $n+k$ bits needed within the primitive. EXEX-NI is indifferentiable from a random oracle up to $n - \log n$ bits. By instantiating it with SKINNY, we can provide hashing to Romulus with zero memory overhead. EXEX-I is an optimized mode with collision resistance. We finally compare the hardware performances of EXEX-NI and EXEX-I, and Romulus-H with SKINNY-128-384. EXEX-NI and EXEX-I achieve the circuit-area reduction by 2,000+ GE, yielding the total areas being smaller than 70% of that of Romulus-H.

2020

TOSC

INT-RUP Secure Lightweight Parallel AE Modes
📺
Abstract

Owing to the growing demand for lightweight cryptographic solutions, NIST has initiated a standardization process for lightweight cryptographic algorithms. Specific to authenticated encryption (AE), the NIST draft demands that the scheme should have one primary member that has key length of 128 bits, and it should be secure for at least 250 − 1 byte queries and 2112 computations. Popular (lightweight) modes, such as OCB, OTR, CLOC, SILC, JAMBU, COFB, SAEB, Beetle, SUNDAE etc., require at least 128-bit primitives to meet the NIST criteria, as all of them are just birthday bound secure. Furthermore, most of them are sequential, and they either use a two pass mode or they do not offer any security when the adversary has access to unverified plaintext (RUP model). In this paper, we propose two new designs for lightweight AE modes, called LOCUS and LOTUS, structurally similar to OCB and OTR, respectively. These modes achieve notably higher AE security bounds with lighter primitives (only a 64-bit tweakable block cipher). Especially, they satisfy the NIST requirements: secure as long as the data complexity is less than 264 bytes and time complexity is less than 2128, even when instantiated with a primitive with 64-bit block and 128-bit key. Both these modes are fully parallelizable and provide full integrity security under the RUP model. We use TweGIFT-64[4,16,16,4] (also referred as TweGIFT-64), a tweakable variant of the GIFT block cipher, to instantiate our AE modes. TweGIFT-64-LOCUS and TweGIFT-64-LOTUS are significantly light in hardware implementation. To justify, we provide our FPGA based implementation results, which demonstrate that TweGIFT-64-LOCUS consumes only 257 slices and 690 LUTs, while TweGIFT-64-LOTUS consumes only 255 slices and 664 LUTs.

2020

EUROCRYPT

Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation
📺
Abstract

This paper proposes tweakable block cipher (TBC) based modes \textsf{PFB}\_\textsf{Plus} and \textsf{PFB}$\omega$ that are efficient in threshold implementations (TI). Let $t$ be an algebraic degree of a target function, e.g. $t=1$ (resp. $t>1$) for linear (resp. non-linear) function. The $d$-th order TI encodes the internal state into $d t + 1$ shares. Hence, the area size increases proportionally to the number of shares. This implies that TBC based modes can be smaller than block cipher (BC) based modes in TI because TBC requires $s$-bit block to ensure $s$-bit security, e.g. \textsf{PFB} and \textsf{Romulus}, while BC requires $2s$-bit block. However, even with those TBC based modes, the minimum we can reach is 3 shares of $s$-bit state with $t=2$ and the first-order TI ($d=1$).
Our first design \textsf{PFB}\_\textsf{Plus} aims to break the barrier of the $3s$-bit state in TI. The block size of an underlying TBC is $s/2$ bits and the output of TBC is linearly expanded to $s$ bits. This expanded state requires only 2 shares in the first-order TI, which makes the total state size $2.5s$ bits. We also provide rigorous security proof of \textsf{PFB}\_\textsf{Plus}. Our second design \textsf{PFB}$\omega$ further increases a parameter $\omega$: a ratio of the security level $s$ to the block size of an underlying TBC. We prove security of \textsf{PFB}$\omega$ for any $\omega$ under some assumptions for an underlying TBC and for parameters used to update a state. Next, we show a concrete instantiation of \textsf{PFB}\_\textsf{Plus} for 128-bit security. It requires a TBC with 64-bit block, 128-bit key and 128-bit tweak, while no existing TBC can support it. We design a new TBC by extending \textsf{SKINNY} and provide basic security evaluation. Finally, we give hardware benchmarks of \textsf{PFB}\_\textsf{Plus} in the first-order TI to show that TI of \textsf{PFB}\_\textsf{Plus} is smaller than that of \textsf{PFB} by more than one thousand gates and is the smallest within the schemes having 128-bit security.

2020

EUROCRYPT

Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound
📺
Abstract

In this paper we spot light on dedicated quantum collision attacks on concrete hash functions, which has not received much attention so far.
In the classical setting, the generic complexity to find collisions of an $n$-bit hash function is $O(2^{n/2})$, thus classical collision attacks based on differential cryptanalysis such as rebound attacks build differential trails with probability higher than $2^{-n/2}$.
By the same analogy, generic quantum algorithms such as the BHT algorithm find collisions with complexity $O(2^{n/3})$.
With quantum algorithms, a pair of messages satisfying a differential trail with probability $p$ can be generated with complexity $p^{-1/2}$.
Hence, in the quantum setting, some differential trails with probability up to $2^{-2n/3}$ that cannot be exploited in the classical setting may be exploited to mount a collision attack in the quantum setting.
In particular, the number of attacked rounds may increase.
In this paper, we attack two international hash function standards: AES-MMO and Whirlpool.
For AES-MMO, we present a $7$-round differential trail with probability $2^{-80}$ and use it to find collisions with a quantum version of the rebound attack,
while only $6$ rounds can be attacked in the classical setting.
For Whirlpool, we mount a collision attack based on a $6$-round differential trail from a classical rebound distinguisher with a complexity higher than the birthday bound. This improves the best classical attack on 5 rounds by 1.
We also show that those trails are optimal in our approach.
Our results have two important implications.
First, there seems to exist a common belief that classically secure hash functions will remain secure against quantum adversaries. Indeed, several second-round candidates in the NIST post-quantum competition use existing hash functions, say SHA-3, as quantum secure ones. Our results disprove this common belief.
Second, our observation suggests that differential trail search should not stop with probability $2^{-n/2}$ but should consider up to $2^{-2n/3}$.
Hence it deserves to revisit the previous differential trail search activities.

2020

CRYPTO

Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems
📺
Abstract

The security and performance of many integrity proof systems like SNARKs, STARKs and Bulletproofs highly depend on the underlying hash function. For this reason several new proposals have recently been developed. These primitives obviously require an in-depth security evaluation, especially since their implementation constraints have led to less standard design approaches. This work compares the security levels offered by two recent families of such primitives, namely GMiMC and HadesMiMC. We exhibit low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in recently launched public challenges for STARK-friendly hash functions. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we present a practical collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. To achieve those results, we adapt and generalize several cryptographic techniques to fields of odd characteristic.

2020

TOSC

Pyjamask: Block Cipher and Authenticated Encryption with Highly Efficient Masked Implementation
📺
Abstract

This paper introduces Pyjamask, a new block cipher family and authenticated encryption proposal submitted to the NIST lightweight cryptography standardization process. Pyjamask targets side-channel resistance as one of its main goal. More precisely, it strongly minimizes the number of nonlinear gates used in its internal primitive in order to allow efficient masked implementations, especially for high-order masking in software. Compared to other block ciphers, our proposal has thus among the smallest number of binary AND computations per input bit at the time of writing. Even though Pyjamask minimizes such an important criterion, it remains rather lightweight and efficient, thanks to a general bitslice construction that enables to computation of all nonlinear gates in parallel. For authenticated encryption, we adopt the provably secure AEAD mode OCB which has been extensively studied and has the benefit to offer full parallelization. Of course, other block cipher-based modes can be considered as well if other performance profiles are to be targeted.The paper first gives the specification of the Pyjamask block cipher and the associated AEAD proposal. We also provide a detailed design rationale for the block cipher which is guided by our aim of software efficiency in the presence of high-order masking. The security of the design is analyzed against most commonly known cryptanalysis techniques. We finally describe efficient (masked) implementations in software and provide implementation results with aggressive performances for masking of very high orders (up to 128). We also provide a rough estimation of the hardware performances which remain much better than those of an AES round-based implementation.

2020

TOSC

SKINNY-AEAD and SKINNY-Hash
📺
Abstract

We present the family of authenticated encryption schemes SKINNY-AEAD and the family of hashing schemes SKINNY-Hash. All of the schemes employ a member of the SKINNY family of tweakable block ciphers, which was presented at CRYPTO 2016, as the underlying primitive. In particular, for authenticated encryption, we show how to instantiate members of SKINNY in the Deoxys-I-like ΘCB3 framework to fulfill the submission requirements of the NIST lightweight cryptography standardization process. For hashing, we use SKINNY to build a function with larger internal state and employ it in a sponge construction. To highlight the extensive amount of third-party analysis that SKINNY obtained since its publication, we briefly survey the existing cryptanalysis results for SKINNY-128-256 and SKINNY-128-384 as of February 2020. In the last part of the paper, we provide a variety of ASIC implementations of our schemes and propose new simple SKINNY-AEAD and SKINNY-Hash variants with a reduced number of rounds while maintaining a very comfortable security margin.
https://csrc.nist.gov/Projects/Lightweight-Cryptography

2020

TOSC

ESTATE: A Lightweight and Low Energy Authenticated Encryption Mode
📺
Abstract

NIST has recently initiated a standardization project for efficient lightweight authenticated encryption schemes. SUNDAE, a candidate in this project, achieves optimal state size which results in low circuit overhead on top of the underlying block cipher. In addition, SUNDAE provides security in nonce-misuse scenario as well. However, in addition to the block cipher circuit, SUNDAE also requires some additional circuitry for multiplication by a primitive element. Further, it requires an additional block cipher invocation to create the starting state. In this paper, we propose a new lightweight and low energy authenticated encryption family, called ESTATE, that significantly improves the design of SUNDAE in terms of implementation costs (both hardware area and energy) and efficient processing of short messages. In particular, ESTATE does not require an additional multiplication circuit, and it reduces the number of block cipher calls by one. Moreover, it provides integrity security even under the release of unverified plaintext (or RUP) model. ESTATE is based on short-tweak tweakable block ciphers (or tBC, small ’t’ denotes short tweaks) and we instantiate it with two recently designed tBCs: TweAES and TweGIFT. We also propose a low latency variant of ESTATE, called sESTATE, that uses a round-reduced (6 rounds) variant of TweAES called TweAES-6. We provide comprehensive FPGA based hardware implementation for all the three instances. The implementation results depict that ESTATE_TweGIFT-128 (681 LUTs, 263 slices) consumes much lesser area as compared to SUNDAE_GIFT-128 (931 LUTs, 310 slices). When we moved to the AES variants, along with the area-efficiency (ESTATE_TweAES consumes 1901 LUTs, 602 slices while SUNDAE_AES-128 needs 1922 LUTs, 614 slices), we also achieve higher throughput for short messages (For 16-byte message, a throughput of 1251.10 and 945.36 Mbps for ESTATE_TweAES and SUNDAE_AES-128 respectively).

2020

TOSC

On the Security Margin of TinyJAMBU with Refined Differential and Linear Cryptanalysis
📺
Abstract

This paper presents the first third-party security analysis of TinyJAMBU, which is one of 32 second-round candidates in NIST’s lightweight cryptography standardization process. TinyJAMBU adopts an NLFSR based keyed-permutation that computes only a single NAND gate as a non-linear component per round. The designers evaluated the minimum number of active AND gates, however such a counting method neglects the dependency between multiple AND gates. There also exist previous works considering such dependencies with stricter models, however those are known to be too slow. In this paper, we present a new model that provides a good balance of efficiency and accuracy by only taking into account the first-order correlation of AND gates that frequently occurs in TinyJAMBU. With the refined model, we show a 338-round differential with probability 2−62.68 that leads to a forgery attack breaking 64-bit security. This implies that the security margin of TinyJAMBU with respect to the number of unattacked rounds is approximately 12%. We also show a differential on full 384 rounds with probability 2−70.64, thus the security margin of full rounds with respect to the data complexity, namely the gap between the claimed security bits and the attack complexity, is less than 8 bits. Our attacks also point out structural weaknesses of the mode that essentially come from the minimal state size to be lightweight.

2020

TOSC

LM-DAE: Low Memory Deterministic Authenticated Encryption for 128-bit Security
Abstract

This paper proposes a new lightweight deterministic authenticated encryption (DAE) scheme providing 128-bit security. Lightweight DAE schemes are practically important because resource-restricted devices sometimes cannot afford to manage a nonce properly. For this purpose, we first design a new mode LM-DAE that has a minimal state size and uses a tweakable block cipher (TBC). The design can be implemented with low memory and is advantageous in threshold implementations (TI) as a side-channel attack countermeasure. LM-DAE further reduces the implementation cost by eliminating the inverse tweak schedule needed in the previous TBC-based DAE modes. LM-DAE is proven to be indistinguishable from an ideal DAE up to the $O(2^n)$ query complexity for the block size $n$. To achieve 128-bit security, an underlying TBC must handle a 128-bit block, 128-bit key, and 128+4-bit tweak, where the 4-bit tweak comes from the domain separation. To satisfy this requirement, we extend SKINNY-128-256 with an additional 4-bit tweak, by applying the elastic-tweak proposed by Chakraborti et al. We evaluate the hardware performances of the proposed scheme with and without TI. Our LM-DAE implementation achieves 3,717 gates, roughly 15% fewer than state-of-the-art nonce-based schemes, thanks to removing the inverse tweak schedule.

2020

TOSC

LM-DAE: Low-Memory Deterministic Authenticated Encryption for 128-bit Security
Abstract

This paper proposes a new lightweight deterministic authenticated encryption (DAE) scheme providing 128-bit security. Lightweight DAE schemes are practically important because resource-restricted devices sometimes cannot afford to manage a nonce properly. For this purpose, we first design a new mode LM-DAE that has a minimal state size and uses a tweakable block cipher (TBC). The design can be implemented with low memory and is advantageous in threshold implementations (TI) as a side-channel attack countermeasure. LM-DAE further reduces the implementation cost by eliminating the inverse tweak schedule needed in the previous TBC-based DAE modes. LM-DAE is proven to be indistinguishable from an ideal DAE up to the O(2n) query complexity for the block size n. To achieve 128-bit security, an underlying TBC must handle a 128-bit block, 128-bit key, and 128+4-bit tweak, where the 4-bit tweak comes from the domain separation. To satisfy this requirement, we extend SKINNY-128-256 with an additional 4-bit tweak, by applying the elastic-tweak proposed by Chakraborti et al. We evaluate the hardware performances of the proposed scheme with and without TI. Our LM-DAE implementation achieves 3,717 gates, roughly 15% fewer than state-of-the-art nonce-based schemes, thanks to removing the inverse tweak schedule.

2020

TOSC

Improved Attacks on sLiSCP Permutation and Tight Bound of Limited Birthday Distinguishers
Abstract

Limited birthday distinguishers (LBDs) are widely used tools for the cryptanalysis of cryptographic permutations. In this paper we propose LBDs on several variants of the sLiSCP permutation family that are building blocks of two round 2 candidates of the NIST lightweight standardization process: Spix and SpoC. We improve the number of steps with respect to the previously known best results, that used rebound attack. We improve the techniques used for solving the middle part, called inbound, and we relax the external conditions in order to extend the previous attacks. The lower bound of the complexity of LBDs has been proved only against functions. In this paper, we prove for the first time the bound against permutations, which shows that the known upper bounds are tight.

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

CRYPTO

Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full $\mathsf {MORUS}$
📺
Abstract

We show that the correlation of any quadratic Boolean function can be read out from its so-called disjoint quadratic form. We further propose a polynomial-time algorithm that can transform an arbitrary quadratic Boolean function into its disjoint quadratic form. With this algorithm, the exact correlation of quadratic Boolean functions can be computed efficiently.We apply this method to analyze the linear trails of $$\mathsf {MORUS}$$ (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of $$\mathsf {MORUS}$$-like key-stream generators. In our model, any tool for finding linear trails of block ciphers can be used to search for trails of $$\mathsf {MORUS}$$-like key-stream generators. As a result, a set of trails with correlation $$2^{-38}$$ is identified for all versions of full $$\mathsf {MORUS}$$, while the correlations of previously published best trails for $$\mathsf {MORUS}$$-640 and $$\mathsf {MORUS}$$-1280 are $$2^{-73}$$ and $$2^{-76}$$ respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on $$\mathsf {MORUS}$$-1280-256 from $$2^{152}$$ to $$2^{76}$$. These new trails also lead to the first distinguishing and message-recovery attacks on $$\mathsf {MORUS}$$-640-128 and $$\mathsf {MORUS}$$-1280-128 with surprisingly low complexities around $$2^{76}$$.Moreover, we observe that the condition for exploiting these trails in an attack can be more relaxed than previously thought, which shows that the new trails are superior to previously published ones in terms of both correlation and the number of ciphertext blocks involved.

2019

ASIACRYPT

Quantum Attacks Without Superposition Queries: The Offline Simon’s Algorithm
Abstract

In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon’s period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.In this paper, we introduce a new quantum algorithm which uses Simon’s subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover’s algorithm. In particular, we are able to break the Even-Mansour construction in quantum time $$\tilde{O}(2^{n/3})$$, with $$O(2^{n/3})$$ classical queries and $$O(n^2)$$ qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity.Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover’s algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure.We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

2019

JOFC

A Practical Forgery Attack on Lilliput-AE
Abstract

Lilliput-AE is a tweakable block cipher submitted as a candidate to the NIST lightweight cryptography standardization process. It is based upon the lightweight block cipher Lilliput, whose cryptanalysis so far suggests that it has a large security margin. In this note, we present an extremely efficient forgery attack on Lilliput-AE: Given a single arbitrary message of length about $$2^{36}$$ 2 36 bytes, we can instantly produce another valid message that leads to the same tag, along with the corresponding ciphertext. The attack uses a weakness in the tweakey schedule of Lilliput-AE which leads to the existence of a related-tweak differential characteristic with probability 1 in the underlying block cipher. The weakness we exploit, which does not exist in Lilliput, demonstrates the potential security risk in using a very simple tweakey schedule in which the same part of the key/tweak is reused in every round, even when round constants are employed to prevent slide attacks. Following this attack, the Lilliput-AE submission to NIST was tweaked.

2019

JOFC

Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes
Abstract

The Sponge function is known to achieve $$2^{c/2}$$ 2 c / 2 security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a $$\min \{2^{c/2},2^\kappa \}$$ min { 2 c / 2 , 2 κ } security bound, with $$\kappa $$ κ the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical $$2^{c/2}$$ 2 c / 2 security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of $$\min \{2^{b/2},2^c,2^\kappa \}$$ min { 2 b / 2 , 2 c , 2 κ } , with $$b>c$$ b > c the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity $$2^{c/2}$$ 2 c / 2 , therewith demonstrating that the techniques cannot be applied to APE.

2018

ASIACRYPT

Cryptanalysis of MORUS
Abstract

MORUS is a high-performance authenticated encryption algorithm submitted to the CAESAR competition, and recently selected as a finalist. There are three versions of MORUS: MORUS-640 with a 128-bit key, and MORUS-1280 with 128-bit or 256-bit keys. For all versions the security claim for confidentiality matches the key size. In this paper, we analyze the components of this algorithm (initialization, state update and tag generation), and report several results.As our main result, we present a linear correlation in the keystream of full MORUS, which can be used to distinguish its output from random and to recover some plaintext bits in the broadcast setting. For MORUS-1280, the correlation is $$2^{-76}$$, which can be exploited after around $$2^{152}$$ encryptions, less than what would be expected for a 256-bit secure cipher. For MORUS-640, the same attack results in a correlation of $$2^{-73}$$, which does not violate the security claims of the cipher.To identify this correlation, we make use of rotational invariants in MORUS using linear masks that are invariant by word-rotations of the state. This motivates us to introduce single-word versions of MORUS called MiniMORUS, which simplifies the analysis. The attack has been implemented and verified on MiniMORUS, where it yields a correlation of $$2^{-16}$$.We also study reduced versions of the initialization and finalization of MORUS, aiming to evaluate the security margin of these components. We show a forgery attack when finalization is reduced from 10 steps to 3, and a key-recovery attack in the nonce-misuse setting when initialization is reduced from 16 steps to 10. These additional results do not threaten the full MORUS, but studying all aspects of the design is useful to understand its strengths and weaknesses.

2017

EUROCRYPT

2017

TOSC

Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds
Abstract

The current paper studies the probability of differential characteristics for an unkeyed (or with a fixed key) construction. Most notably, it focuses on the gap between two probabilities of differential characteristics: probability with independent S-box assumption, pind, and exact probability, pexact. It turns out that pexact is larger than pind in Feistel network with some S-box based inner function. The mechanism of this gap is then theoretically analyzed. The gap is derived from interaction of S-boxes in three rounds, and the gap depends on the size and choice of the S-box. In particular the gap can never be zero when the S-box is bigger than six bits. To demonstrate the power of this improvement, a related-key differential characteristic is proposed against a lightweight block cipher RoadRunneR. For the 128-bit key version, pind of 2−48 is improved to pexact of 2−43. For the 80-bit key version, pind of 2−68 is improved to pexact of 2−62. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: pind of 2−128 is improved to pexact of 2−96, which allows to extend the attack by two rounds.

2017

TOSC

MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics
Abstract

Current Mixed Integer Linear Programming (MILP)-based search against symmetric-key primitives with 8-bit S-boxes can only build word-wise model to search for truncated differential characteristics. In such a model, the properties of the Differential Distribution Table (DDT) are not considered. To take these properties into account, a bit-wise model is necessary, which can be generated by the H-representation of the convex hull or the logical condition modeling. However, the complexity of both approaches becomes impractical when the size of the S-box exceeds 5 bits. In this paper, we propose a new modeling for large (8-bit or more) S-boxes. In particular, we first propose an algorithm to generate a bit-wise model of the DDT for large S-boxes. We observe that the problem of generating constraints in logical condition modeling can be converted into the problem of minimizing the product-of-sum of Boolean functions, which is a well-studied problem. Hence, classical off-the-shelf solutions such as the Quine-McCluskey algorithm or the Espresso algorithm can be utilized, which makes building a bit-wise model, for 8-bit or larger S-boxes, practical. Then this model is further extended to search for the best differential characteristic by considering the probabilities of each propagation in the DDT, which is a much harder problem than searching for the lower bound on the number of active S-boxes. Our idea is to separate the DDT into multiple tables for each probability and add conditional constraints to control the behavior of these multiple tables. The proposed modeling is first applied to SKINNY-128 to find that there is no differential characteristic having probability higher than 2−128 for 14 rounds, while the designers originally expected that 15 rounds were required. We also applied the proposed modeling to two, arbitrarily selected, constructions of the seven AES round function based constructions proposed in FSE 2016 and managed to improve the lower bound on the number of the active S-boxes in one construction and the upper bound on the differential characteristic for the other.

2017

TOSC

A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers
Abstract

In this article, we provide the first independent security analysis of Deoxys, a third-round authenticated encryption candidate of the CAESAR competition, and its internal tweakable block ciphers Deoxys-BC-256 and Deoxys-BC-384. We show that the related-tweakey differential bounds provided by the designers can be greatly improved thanks to a Mixed Integer Linear Programming (MILP) based search tool. In particular, we develop a new method to incorporate linear incompatibility in the MILP model. We use this tool to generate valid differential paths for reduced-round versions of Deoxys-BC-256 and Deoxys-BC-384, later combining them into broader boomerang or rectangle attacks. Here, we also develop a new MILP model which optimises the two paths by taking into account the effect of the ladder switch technique. Interestingly, with the tweak in Deoxys-BC providing extra input as opposed to a classical block cipher, we can even consider beyond full-codebook attacks. As these primitives are based on the TWEAKEY framework, we further study how the security of the cipher is impacted when playing with the tweak/key sizes. All in all, we are able to attack 10 rounds of Deoxys-BC-256 (out of 14) and 13 rounds of Deoxys-BC-384 (out of 16). The extra rounds specified in Deoxys-BC to balance the tweak input (when compared to AES) seem to provide about the same security margin as AES-128. Finally we analyse why the authenticated encryption modes of Deoxys mostly prevent our attacks on Deoxys-BC to apply to the authenticated encryption primitive.

2017

CHES

GIFT: A Small Present
Abstract

In this article, we revisit the design strategy of PRESENT, leveraging all the advances provided by the research community in construction and cryptanalysis since its publication, to push the design up to its limits. We obtain an improved version, named GIFT, that provides a much increased efficiency in all domains (smaller and faster), while correcting the well-known weakness of PRESENT with regards to linear hulls.
GIFT is a very simple and clean design that outperforms even SIMON or SKINNY for round-based implementations, making it one of the most energy efficient ciphers as of today. It reaches a point where almost the entire implementation area is taken by the storage and the Sboxes, where any cheaper choice of Sbox would lead to a very weak proposal. In essence, GIFT is composed of only Sbox and bit-wiring, but its natural bitslice data flow ensures excellent performances in all scenarios, from area-optimised hardware implementations to very fast software implementation on high-end platforms.We conducted a thorough analysis of our design with regards to state-of-the-art cryptanalysis, and we provide strong bounds with regards to differential/linear attacks.

2016

ASIACRYPT

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

2013

ASIACRYPT

2012

EUROCRYPT

2012

ASIACRYPT

2010

EPRINT

Efficient Differential Fault Analysis for AES
Abstract

This paper proposes improved post analysis methods for Differential Fault Analysis (DFA) against AES. In detail, we propose three techniques to improve the attack efficiency as 1) combining previous DFA methods, 2) performing a divide-and-conquer attack by considering the AES key-schedule structure, and 3) taking the linearity of the MixColumns operation into account. As a result, the expectation of the analysis time in the previous work can be reduced to about one sixteenth.
Notice that these improvements are based on the detailed analysis of the previous DFA methods and the calculation time and memory cost in practical implementations. Moreover, the proposed techniques can be widely applied to DFA attacks under different assumptions.

2007

EPRINT

Practical Password Recovery on an MD5 Challenge and Response
Abstract

This paper shows an attack against APOP protocol which is a challenge-and-response protocol. We utilize the Wang's attack to make collisions in MD5, and apply it to APOP protocol. We confirmed that the first 3 octets of secret key can be recovered by several hundred queries under the man-in-the-middle environment.

2006

EPRINT

Message Modification for Step 21-23 on SHA-0
Abstract

In CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed an efficient collision attack on SHA-0.
Collision messages are found with complexity $2^{39}$ SHA-0 operations by using their method.
Collision messages can be obtained when a message satisfying all sufficient conditions is found.
In their paper, they proposed message modifications that can satisfy all sufficient conditions of step 1-20.
However, they didn't propose message modifications for sufficient conditions after step 21.
In this paper, we propose message modifications for sufficient conditions of step 21-23.
By using our message modifications, collision messages are found with complexity $2^{36}$ SHA-0 operations.

2006

EPRINT

How to Construct Sufficient Condition in Searching Collisions of MD5
Abstract

In Eurocrypt 2005, Wang et al. presented a collision attak on MD5. In their paper, they
intoduced gSufficient Conditionh which would be needed to generate collisions. In this paper, we explain
how to construct sufficent conditions of MD5 when a differential path is given. By applying our algorithm
to a collision path given byWang et al, we found that sufficient conditions introduced by them contained
some unnecessary conditions. Generally speaking, when a differential path is given, corresponding sets
of sufficient conditions is not unique. In our research, we analyzed the differential path found by Wang
et al, and we found a different set of sufficient conditions from that of Wang et al. We have generated
collisions by using our sifficient conditions.

2005

EPRINT

Improved Collision Attack on MD4
Abstract

In this paper, we propose an attack method to find collisions of MD4 hash function. This attack is the improved version of the attack
which was invented by Xiaoyun Wang et al [1]. We were able to find collisions with probability almost 1, and the average complexity
to find a collision is upper bounded by three times of MD4 hash operations. This result is improved compared to the original result of [1] where
the probability were from $2^{-6}$ to $2^{-2}$, and the average complexity to find a collision was upper bounded by $2^8$ MD4 hash operations.
We also point out the lack of sufficient conditions and imprecise modifications for the original attack in [1].

2005

EPRINT

Improved Collision Attack on MD5
Abstract

In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al.
In this attack, conditions which are sufficient to generate collisions (called
``sufficient condition") are introduced.
This attack raises the success probability by modifing messages to satisfy these conditions.
In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is $2^{37}$.
After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the
complexity is $2^{33}$.
In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far.
In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that
this method work correctly is roughly 1/2. Therefore, the complexity of this attack is $2^{30}$. Furthermore, we propose a more efficient
collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8.

#### Program Committees

- Asiacrypt 2020
- FSE 2020 (Program chair)
- Asiacrypt 2019
- FSE 2019 (Program chair)
- FSE 2018
- Eurocrypt 2018
- FSE 2017
- Eurocrypt 2017
- Asiacrypt 2017
- FSE 2016
- Asiacrypt 2015
- Asiacrypt 2013
- Eurocrypt 2013
- FSE 2012

#### Coauthors

- Ahmed Abdelkhalek (1)
- Kazumaro Aoki (5)
- Tomer Ashur (1)
- Nasour Bagheri (1)
- Subhadeep Banik (1)
- Zhenzhen Bao (1)
- Christof Beierle (2)
- Tim Beyne (1)
- Xavier Bonnetain (1)
- Anne Canteaut (2)
- Avik Chakraborti (2)
- Carlos Cid (2)
- Nilanjan Datta (2)
- Itai Dinur (1)
- Orr Dunkelman (1)
- Maria Eichlseder (2)
- Toshinori Fukunaga (1)
- Shigeto Gomisawa (1)
- Dahmun Goudarzi (1)
- Jian Guo (10)
- Akinori Hosoyamada (5)
- Lei Hu (1)
- Tao Huang (3)
- Mitsugu Iwamoto (1)
- Jérémy Jean (6)
- Ashwin Jha (2)
- Keting Jia (1)
- Philipp Jovanovic (1)
- Nathan Keller (1)
- Stefan Kölbl (3)
- Noboru Kunihiro (6)
- Eran Lambooij (2)
- Martin M. Lauridsen (1)
- Gregor Leander (4)
- Gaëtan Leurent (3)
- Chaoyun Li (1)
- Yang Li (2)
- San Ling (1)
- Atul Luykx (1)
- Cuauhtemoc Mancillas-Lopez (2)
- Krystian Matusiewicz (2)
- Florian Mendel (2)
- Bart Mennink (1)
- Brice Minaud (1)
- Amir Moradi (2)
- Yusuke Naito (10)
- Mridul Nandi (2)
- María Naya-Plasencia (4)
- Samuel Neves (1)
- Ivica Nikolić (6)
- Kazuo Ohta (8)
- Sumit Kumar Pandey (1)
- Léo Perrin (1)
- Thomas Peyrin (9)
- Kexin Qiao (1)
- Shahram Rasoolzadeh (1)
- Matthieu Rivain (1)
- Yann Rotella (1)
- Dhiman Saha (1)
- Kazuo Sakiyama (2)
- Pascal Sasdrich (2)
- Martin Schläffer (1)
- André Schrottenloher (1)
- Danping Shi (2)
- Takeshi Shimoyama (3)
- Ferdinand Sibleyras (1)
- Siang Meng Sim (5)
- Ling Song (2)
- Marc Stevens (1)
- Takeshi Sugawara (5)
- Siwei Sun (2)
- Junko Takahashi (1)
- Yosuke Todo (5)
- Mohamed Tolba (1)
- Benoît Viguier (1)
- Lei Wang (13)
- Meiqin Wang (2)
- Long Wen (2)
- Friedrich Wiemer (1)
- Shuang Wu (3)
- Wenling Wu (1)
- Keita Xagawa (1)
- Jun Yajima (3)
- Go Yamamoto (1)
- Kan Yasuda (2)
- Amr M. Youssef (1)
- Yingjie Zhang (1)