International Association for Cryptologic Research

International Association
for Cryptologic Research


Michael Paddon


Design and Primitive Specification for Shannon
Shannon is a synchronous stream cipher with message authentication functionality, designed according to the ECrypt NoE call for stream cipher primitives, profile 1A (but well after the call). Shannon is named in memory of Claude E. Shannon[20] of Bell Labs and MIT, founder of Information Theory. Shannon is an entirely new design, influenced by members of the SOBER family of stream ciphers, Helix/Phelix, Trivium, Scream, and SHA-256. It consists of a single 32-bit wide, 16-element nonlinear feedback shift register and an extra word, which is supplemented for message authentication with 32 parallel CRC-16 registers. Shannon is free to use for any purpose, and reference source code can be found at .
On Corrective Patterns for the SHA-2 Family
The Secure Hash Standard (SHS) [3] includes hashing algorithms denoted SHA-n, (n in {224, 256, 384, 512}) for producing message digests of length n. These algorithms are based on a common design, sometimes known as SHA-2, that consists of a message schedule and a register. The most successful attacks on the SHA algorithms are Chabaud-Joux differential collisions [1, 2, 4, 5, 7], which are based on finding a corrective pattern for the register. Previous analysis of the SHA-2 algoritms [4] indicated that, for all SHA-2 algorithms, the best corrective pattern has probability 2^-66. We find that the complexity of obtaining a collision is 2^39 when the register state is unknown. Of this complexity, a factor of 2^9 corresponds to conditions on the internal state that must be satisfied, and a factor of 2^30 corresponds to 30 bits of internal state that must be guessed correctly in order to generate a collision. When the register state is known (as is the case when generating a hash) then the guessed bits are known and the complexity is reduced to 2^9. The simple analysis of the message schedule in [4] determines limits on the probability of collision for SHA-2, and was sufficient at that time to conclude that the algorithms resist the attacks. In [4] the claimed complexity is compared against the birthday attack bound of 2^n/2. However, the corrective pattern can be converted into a second pre-image attack for which the complexity should be greater than 2^n. When accounting for the complexity of 2^9 per corrective pattern, the previous analysis of the message schedule yields lower bounds on the complexities 2^27 for SHA-224/256 and 2^45 for SHA-224/256. These complexities are significantly less than the 2^n bound. It is no longer certain that SHA-2 resists this attack. More detailed analysis of the message schedule is required.
Musings on the Wang et al. MD5 Collision
Wang et al. caused great excitement at CRYPTO2004 when they announced a collision for MD5~\cite{R92_MD5}. This paper is examines the internal differences and conditions required for the attack to be successful. There are a large number of conditions that must be satisfied, thus indicating Wang at al. have found a clever way to generate message pairs for which the conditions are satisfied. The large number of conditions suggests that an attacker cannot use these differentials to cause second pre-image attacks with complexity less than generic attacks. Initial examination also suggests that an attacker cannot cause such collisions for HMAC-MD5 with complexity less than generic attacks.
The Mundja Streaming MAC
Mundja is a MAC generation algorithm that has been designed for use together with a stream cipher. Mundja accumulates the message onto two independent registers: the first is a Cyclic Redundancy Checksum (CRC) that uses linear feedback; the second is a strengthened version of the SHA-256 register that uses nonlinear feedback. Mundja is fast (asymptotically about 4 times the speed of HMAC-SHA-256), and can generate MACs of any desired length. Mundja is designed to be secure at the equivalent level of 128-bit keys. When used in cooperation with a correspondingly secure stream cipher, it is hoped to remain secure even at the equivalent level of 256-bit keys. Appendices give details of the use of Mundja with the SOBER-128, Turing and RC4 stream ciphers.