International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Scott Contini

Publications

Year
Venue
Title
2015
EPRINT
2008
FSE
2007
FSE
2007
EPRINT
Cryptanalysis of LASH
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
ASIACRYPT
2006
EUROCRYPT
2006
EPRINT
Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions
Scott Contini Yiqun Lisa Yin
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
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
PKC
2005
EPRINT
VSH, an Efficient and Provable Collision Resistant Hash Function
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
Scott Contini
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.
2004
FSE
2003
EPRINT
Improved Cryptanalysis of SecurID
Scott Contini Yiqun Lisa Yin
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.
1999
FSE

Program Committees

Asiacrypt 2008