## CryptoDB

### Yusuke Naito

#### Publications

**Year**

**Venue**

**Title**

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

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

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

Highly Secure Nonce-based MACs from the Sum of Tweakable Block Ciphers
Abstract

Tweakable block ciphers (TBCs) have proven highly useful to boost the security guarantees of authentication schemes. In 2017, Cogliati et al. proposed two MACs combining TBC and universal hash functions: a nonce-based MAC called NaT and a deterministic MAC called HaT. While both constructions provide high security, their properties are complementary: NaT is almost fully secure when nonces are respected (i.e., n-bit security, where n is the block size of the TBC, and no security degradation in terms of the number of MAC queries when nonces are unique), while its security degrades gracefully to the birthday bound (n/2 bits) when nonces are misused. HaT has n-bit security and can be used naturally as a nonce-based MAC when a message contains a nonce. However, it does not have full security even if nonces are unique.This work proposes two highly secure and efficient MACs to fill the gap: NaT2 and eHaT. Both provide (almost) full security if nonces are unique and more than n/2-bit security when nonces can repeat. Based on NaT and HaT, we aim at achieving these properties in a modular approach. Our first proposal, Nonce-as-Tweak2 (NaT2), is the sum of two NaT instances. Our second proposal, enhanced Hash-as-Tweak (eHaT), extends HaT by adding the output of an additional nonce-depending call to the TBC and prepending nonce to the message. Despite the conceptual simplicity, the security proofs are involved. For NaT2 in particular, we rely on the recent proof framework for Double-block Hash-then-Sum by Kim et al. from Eurocrypt 2020.

2019

TOSC

The Exact Security of PMAC with Two Powering-Up Masks
📺
Abstract

PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.’s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the lower bound Ω(q2/2n) for q queries and the block cipher size n. Regarding the MAC security (unforgeability), a hash collision for MAC queries, or guessing a tag offers the lower bound Ω(q2m /2n + qv/2n) for qm MAC queries and qv verification queries (forgery attempts). The tight upper bound of the PRF-security O(q2/2n) of PMAC was given by Gaži et el. (ToSC 2017, Issue 1), but their proof requires a 4-wise independent masking scheme that uses 4 n-bit random values. Open problems from their work are: (1) find a masking scheme with three or less random values with which PMAC has the tight upper bound for PRF-security; (2) find a masking scheme with which PMAC has the tight upper bound for MAC-security.In this paper, we consider PMAC with two powering-up masks that uses two random values for the masking scheme. Using the structure of the powering-up masking scheme, we show that the PMAC has the tight upper bound O(q2/2n) for PRF-security, which answers the open problem (1), and the tight upper bound O(q2m /2n + qv/2n) for MAC-security, which answers the open problem (2). Note that these results deal with two-key PMACs, thus showing tight upper bounds of PMACs with single-key and/or with one powering-up mask are open problems.

2019

TCHES

Lightweight Authenticated Encryption Mode of Operation for Tweakable Block Ciphers
📺
Abstract

The use of a small block length is a common strategy when designing lightweight (tweakable) block ciphers (TBCs), and several 64-bit primitives have been proposed. However, when such a 64-bit primitive is used for an authenticated encryption with birthday-bound security, it has only 32-bit data complexity, which is subject to practical attacks. To employ a short block length without compromising security, we propose PFB, a lightweight TBC-based authenticated encryption with associated data mode, which achieves beyond-birthday-bound security. For this purpose, we extend iCOFB, which is originally defined with a tweakable random function. Unlike iCOFB, the proposed method can be instantiated with a TBC using a fixed tweak length and can handle variable-length data. Moreover, its security bound is improved and independent of the data length; this improves the key lifetime, particularly in lightweight blocks with a small size. The proposed method also covers a broader class of feedback functions because of the generalization presented in our proof. We evaluate the concrete hardware performances of PFB, which benefits from the small block length and shows particularly good performances in threshold implementation.

2018

TCHES

SAEB: A Lightweight Blockcipher-Based AEAD Mode of Operation
📺
Abstract

Lightweight cryptography in computationally constrained devices is actively studied. In contrast to advances of lightweight blockcipher in the last decade, lightweight mode of operation is seemingly not so mature, yet it has large impact in performance. Therefore, there is a great demand for lightweight mode of operation, especially that for authenticated encryption with associated data (AEAD). Among many known properties of conventional modes of operation, the following four properties are essential for constrained devices:
Minimum State Size: the state size equals to a block size of a blockcipher.
Inverse Free: no need for a blockcipher decryption.
XOR Only: only XOR is needed in addition to a blockcipher encryption.
Online: a data block is processed only once.
The properties 1 and 4 contribute to small memory usage, and the properties 2 and 3 contribute to small program/circuit footprint. On top of the above properties, the fifth property regarding associated data (AD) is also important for performance:
Efficient Handling of Static AD: static AD can be precomputed.
We design a lightweight blockcipher-based AEAD mode of operation called SAEB: the first mode of operation that satisfies all the five properties to the best of our knowledge. Performance of SAEB is evaluated in various software and hardware platforms. The evaluation results show that SAEB outperforms conventional blockcipher-based AEAD modes of operation in various performance metrics for lightweight cryptography.

2017

TOSC

Tweakable Blockciphers for Efficient Authenticated Encryptions with Beyond the Birthday-Bound Security
Abstract

Modular design via a tweakable blockcipher (TBC) offers efficient authenticated encryption (AE) schemes (with associated data) that call a blockcipher once for each data block (of associated data or a plaintext). However, the existing efficient blockcipher-based TBCs are secure up to the birthday bound, where the underlying keyed blockcipher is a secure strong pseudorandom permutation. Existing blockcipher-based AE schemes with beyond-birthday-bound (BBB) security are not efficient, that is, a blockcipher is called twice or more for each data block. In this paper, we present a TBC, XKX, that offers efficient blockcipher-based AE schemes with BBB security, by combining with efficient TBC-based AE schemes such as ΘCB3 and

2009

EPRINT

How to Prove the Security of Practical Cryptosystems with Merkle-Damg{\aa}rd Hashing by Adopting Indifferentiability
Abstract

In this paper, we show that major cryptosystems such as FDH, OAEP, and RSA-KEM are secure
under a hash function $MD^h$ with Merkle-Damg{\aa}rd (MD) construction that uses a random oracle compression function $h$.
First, we propose two new ideal primitives called Traceable Random
Oracle ($\mathcal{TRO}$) and Extension Attack Simulatable Random Oracle ($\mathcal{ERO}$) which are weaker than a random oracle ($\mathcal{RO}$).
Second, we show that $MD^h$ is indifferentiable from $\mathcal{LRO}$, $\mathcal{TRO}$ and $\mathcal{ERO}$,
where $\mathcal{LRO}$ is Leaky Random Oracle proposed by Yoneyama et al.
This result means that if a cryptosystem is secure in these models,
then the cryptosystem is secure under $MD^h$ following the indifferentiability theory proposed by Maurer et al.
Finally, we prove that OAEP is secure in the $\mathcal{TRO}$ model and RSA-KEM is secure in the $\mathcal{ERO}$ model.
Since it is also known that FDH is secure in the $\mathcal{LRO}$ model, as a result, major cryptosystems, FDH, OAEP and RSA-KEM, are secure under $MD^h$, though $MD^h$ is not indifferentiable from $\mathcal{RO}$.

2009

EPRINT

Davies-Meyer Merkle-Damg{\aa}rd Revisited:\\Variants of Indifferentiability and Random Oracles
Abstract

In this paper, we succeed in analyzing practical cryptosystems that
employ the Davies-Meyer Merkle-Damg{\aa}rd hash function $\mddm^E$ with ideal cipher $E$ by using two approaches:
{\it indifferentiability from variants of random oracles} and {\it indifferentiability from a random oracle $\ro$ with conditions}.
We show that RSA-KEM with $\mddm^E$ is secure by using the former approach and
that OAEP with $\mddm^E$ is secure by using the latter approach.
The public-use random oracle ($\pubro$) model is a variant of random oracle (proposed by Dodis et al. and Yoneyama et al.).
We also show that cryptosystems secure under $\pubro$ model, such as FDH, Fiat-Shamir, PSS and so on, are also secure under $\mddm^E$ by using the former approach.
Note that Dodis et al. failed in the paper of EUROCRYPT 2009 in analyzing the security of cryptosystems with $\mddm^E$, because they started by analyzing the underlying compression function,
while our first approach starts by analyzing the hash function.

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.

#### Coauthors

- Wonseok Choi (1)
- Akiko Inoue (1)
- Noboru Kunihiro (5)
- ByeongHak Lee (1)
- Jooyoung Lee (1)
- Eik List (1)
- Mitsuru Matsui (1)
- Kazuhiko Minematsu (1)
- Kazuo Ohta (8)
- Yu Sasaki (10)
- Takeshi Shimoyama (3)
- Takeshi Sugawara (7)
- Daisuke Suzuki (1)
- Lei Wang (3)
- Jun Yajima (3)
- Kan Yasuda (1)
- Kazuki Yoneyama (3)