International Association for Cryptologic Research

International Association
for Cryptologic Research


William Millan


The classic Merkle-Damg{\aa}rd (\textbf{MD}) structure provides a popular way of turning a fixed-length compression function into a variable-length input cryptographic hash function. However, the multi-block collision attacks (MBCA) on the \textbf{MD}-style hash functions MD5, SHA-0 and SHA-1 demonstrate the weakness of the \textbf{MD} construction in extending the collision resistance property of a single compression function to its iterations. In this paper, we investigate a recently proposed cryptographic construction (called \textbf{3C}) devised by enhancing the \textbf{MD} construction, and prove it provides quantitatively more resistance against MBCA than does the \textbf{MD}-style. Specifically, we prove that it requires at least $2^{t/2}$ computational effort to perform any MBCA on the $t$-bit \textbf{3C} hash function when the same attack on a $t$-bit \textbf{MD} hash function (using the same compression function) requires an effort not less than $2^{t/4}$. This is the first result showing a generic construction with resistance to MBCA. We further improve the resistance of the \textbf{3C} design against MBCA and propose the new \textbf{3C+} hash function construction. We prove that \textbf{3C+} is completely \emph{immune} to MBCA since it costs at least $2^{t/2}$ effort to perform any MBCA on the \textbf{3C+} construction. This reduces the collision security of \textbf{3C+} to the collision security of the underlying compression function, hence restoring the paradigm that one only needs to design a secure compression function to obtain a secure iterated hash function. Both the \textbf{3C} and \textbf{3C+} constructions are very simple adjustments to the \textbf{MD} construction and they are immune to the straight forward extension attacks which apply to the \textbf{MD} hash functions. The second preimage attacks on $t$-bit hash functions also do not work on the constructions presented in this paper.
LILI-II is not Broken
William Millan Ed Dawson
In this note we point out that a recently published attack on the LILI-II stream cipher does not do better than generic time-memory tradeoff techniques (which generalise exhaustive search and apply to any 128-bit key cipher). Thus we assert that LILI-II remains unbroken.
3C- A Provably Secure Pseudorandom Function and Message Authentication Code.A New mode of operation for Cryptographic Hash Function
We propose a new cryptographic construction called 3C, which works as a pseudorandom function (PRF), message authentication code (MAC) and cryptographic hash function. The 3C-construction is obtained by modifying the Merkle-Damgard iterated construction used to construct iterated hash functions. We assume that the compression functions of Merkle-Damgard iterated construction realize a family of fixed-length-input pseudorandom functions (FI-PRFs). A concrete security analysis for the family of 3C- variable-length-input pseudorandom functions (VI-PRFs) is provided in a precise and quantitative manner. The 3C- VI-PRF is then used to realize the 3C- MAC construction called one-key NMAC (O-NMAC). O-NMAC is a more efficient variant of NMAC and HMAC in the applications where key changes frequently and the key cannot be cached. The 3C-construction works as a new mode of hash function operation for the hash functions based on Merkle-Damgard construction such as MD5 and SHA-1. The generic 3C- hash function is more resistant against the recent differential multi-block collision attacks than the Merkle-Damgard hash functions and the extension attacks do not work on the 3C- hash function. The 3C-X hash function is the simplest and efficient variant of the generic 3C hash function and it is the simplest modification to the Merkle-Damgard hash function that one can achieve. We provide the security analysis for the functions 3C and 3C-X against multi-block collision attacks and generic attacks on hash functions. We combine the wide-pipe hash function with the 3C hash function for even better security against some generic attacks and differential attacks. The 3C-construction has all these features at the expense of one extra iteration of the compression function over the Merkle-Damgard construction.
Some thoughts on Collision Attacks in the Hash Functions MD5, SHA-0 and SHA-1
The design principle of Merkle-Damg{\aa}rd construction is collision resistance of the compression function implies collision resistance of the hash function. Recently multi-block collisions have been found on the hash functions MD5, SHA-0 and SHA-1 using differential cryptanalysis. These multi-block collisions raise several questions on some definitions and properties used in the hash function literature. In this report, we take a closer look at some of the literature in cryptographic hash functions and give our insights on them. We bring out some important differences between the 1989's Damg{\aa}rd's hash function and the hash functions that followed it. We conclude that these hash functions did not consider the pseudo-collision attack in their design criteria. We also doubt whether these hash functions achieve the design principle of Merkle-Damg{\aa}rd's construction. We formalise some definitions on the properties of hash functions in the literature.
On Linear Redundancy in the AES S-Box
Joanne Fuller William Millan
We show the existence of a previously unknown linear redundancy property of the only nonlinear component of the AES block cipher. It is demonstrated that the outputs of the 8*8 Rijndael s-box (based on inversion in a finite field) are all equivalent under affine transformation. The method used to discover these affine relations is novel and exploits a new fundamental result on the invariance properties of local connection structure of affine equivalence classes. As well as increasing existing concerns about the security of the AES, these results may also have serious consequences for many other ciphers recently proposed for standardisation.