## CryptoDB

### Scott Contini

#### Publications

**Year**

**Venue**

**Title**

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.

2006

EPRINT

Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions
Abstract

In this paper, we analyze the security of HMAC and NMAC, both of which are hash-based message authentication codes. We present distinguishing, forgery, and partial key recovery attacks on HMAC and NMAC using collisions of MD4, MD5, SHA-0, and reduced SHA-1. Our results demonstrate that the strength of a cryptographic scheme can be greatly weakened by the insecurity of the underlying hash function.

2006

EPRINT

Weaknesses of the FORK-256 compression function
Abstract

This report presents analysis of the compression function of a recently proposed hash function, FORK-256. We exhibit some unexpected differentials existing for the step transformation and show their possible uses in collision-finding attacks on different variants of FORK-256. As a simple application of those observations we present a method of finding chosen IV collisions for a variant of FORK-256 reduced to two branches : either 1 and 2 or 3 and 4.
Moreover, we present how those differentials can be used in the full FORK-256 to easily find messages with hashes differing by only a relatively small number of bits.
We argue that this method allows for finding collisions in the full function with complexity not exceeding $2^{126.6}$ hash evaluations, better than birthday attack and additionally requiring only a small amount of memory.

2005

EPRINT

VSH, an Efficient and Provable Collision Resistant Hash Function
Abstract

We introduce VSH, {\em very smooth hash}, a new $S$-bit hash function that
is provably collision-resistant assuming the hardness of
finding nontrivial modular
square roots of very smooth numbers modulo an $S$-bit composite.
By very smooth, we mean that the smoothness bound is
some fixed polynomial function of~$S$.
We argue that finding collisions for VSH has the same asymptotic
complexity as factoring using the Number Field Sieve factoring algorithm,
i.e., subexponential in~$S$.
%We show how our asymptotic argument can be turned into a practical method to
%select parameters so that VSH meets a desired security level.
VSH is theoretically pleasing because it requires just a single
multiplication modulo the~$S$-bit composite
per $\Omega(S)$ message-bits (as opposed to $O(\log S)$
message-bits for previous provably secure hashes).
It is relatively practical.
A preliminary implementation on a 1GHz Pentium III
processor that achieves collision resistance at least equivalent
to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1
MegaByte per second, with a moderate slowdown to 0.7MB/s for
2048-bit RSA security.
VSH can be used to
build a fast, provably secure randomised trapdoor hash function,
which can be applied to speed up provably secure signature schemes (such
as Cramer-Shoup) and designated-verifier signatures.

2005

EPRINT

Collisions in the Original Version of a Chaotic Hash Function
Abstract

At the Crypto 2005 rump session, a new hash function based upon a
chaotic map was presented.
We display several messages that collide to the same output for this
hash function.

2003

EPRINT

Improved Cryptanalysis of SecurID
Abstract

SecurID is a widely used hardware token for strengthening
authentication in a corporate environment. Recently,
Biryukov, Lano, and Preneel presented an attack on the alleged
SecurID hash function~\cite{BLP}. They showed
that {\it vanishing differentials} -- collisions
of the hash function -- occur quite frequently, and that
such differentials allow an attacker to recover the secret key in the
token much faster than exhaustive search. Based on
simulation results, they estimated that given a single 2-bit vanishing
differential, the running time of their attack would be about $2^{48}$
full hash operations.
In this paper, we first give a more detailed analysis of the
attack in~\cite{BLP} and present several techniques to improve it
significantly. Our theoretical analysis and implementation experiments show
that the running time of our improved attack is about $2^{44}$
hash operations, though special cases involving $\ge$ 4-bit
differentials (which happen about one third of the time)
reduce the time further.
We then investigate into the use of extra information that an
attacker would typically have: multiple vanishing differentials
or knowledge that other vanishing differentials do not occur
in a nearby time period.
When using the extra information, it appears that key recovery can
always be accomplished within about $2^{40}$ hash operations.

#### Program Committees

- Asiacrypt 2008

#### Coauthors

- Olivier Billet (1)
- Jian Guo (2)
- Arjen K. Lenstra (2)
- San Ling (2)
- Krystian Matusiewicz (4)
- Thomas Peyrin (1)
- Josef Pieprzyk (5)
- Ronald L. Rivest (1)
- Matthew J. B. Robshaw (1)
- Ron Steinfeld (5)
- Huaxiong Wang (3)
- Yiqun Lisa Yin (5)