## CryptoDB

### Noboru Kunihiro

#### Affiliation: The University of Tokyo

#### Publications

**Year**

**Venue**

**Title**

2016

CRYPTO

2015

EPRINT

2014

CRYPTO

2010

EPRINT

Solving Generalized Small Inverse Problems
Abstract

We introduce a ``generalized small inverse problem (GSIP)'' and
present an algorithm for solving this problem. GSIP is formulated
as finding small solutions of $f(x_0, x_1, \ldots , x_n)=x_0 h(x_1,
\ldots , x_n)+C=0 (\bmod \; M)$ for an $n$-variate polynomial $h$,
non-zero integers $C$ and $M$. Our algorithm is based on
lattice-based Coppersmith technique. We provide a strategy for
construction of a lattice basis for solving $f=0$, which are
systematically transformed from a lattice basis for solving $h=0$.
Then, we derive an upper bound such that the target problem can be
solved in polynomial time in $\log M$ in an explicit form.
Since GSIPs include some RSA related problems, our algorithm is
applicable to them. For example, the small key attacks by Boneh
and Durfee are re-found automatically.

2007

PKC

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.

1998

EUROCRYPT

#### Program Committees

- PKC 2013

#### Coauthors

- Nuttapong Attrapadung (4)
- Goichiro Hanaoka (8)
- Junya Honda (2)
- Tetsuya Izu (1)
- Kenji Koyama (2)
- Kaoru Kurosawa (1)
- Yusuke Naito (5)
- Kazuo Ohta (7)
- Bagus Santoso (1)
- Yu Sasaki (6)
- Jacob C. N. Schuldt (1)
- Takeshi Shimoyama (3)
- Naoyuki Shinohara (1)
- Atsushi Takayasu (1)
- Yukio Tsuruoka (1)
- Lei Wang (2)
- Jun Yajima (3)
- Shota Yamada (8)
- Takashi Yamakawa (3)