×

zbMATH — the first resource for mathematics

Practical collisions for SHAMATA-256. (English) Zbl 1267.94066
Jacobson, Michael J. jun. (ed.) et al., Selected areas in cryptography. 16th annual international workshop, SAC 2009, Calgary, Alberta, Canada, August 13–14, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-05443-3/pbk). Lecture Notes in Computer Science 5867, 1-15 (2009).
Summary: In this paper, we present a collision attack on the SHA-3 submission SHAMATA. SHAMATA is a stream cipher-like hash function design with components of the AES, and it is one of the fastest submitted hash functions. In our attack, we show weaknesses in the message injection and state update of SHAMATA. It is possible to find certain message differences that do not get changed by the message expansion and non-linear part of the state update function. This allows us to find a differential path with a complexity of about \(2^{96}\) for SHAMATA-256 and about \(2^{110}\) for SHAMATA-512, using a linear low-weight codeword search. Using an efficient guess-and-determine technique we can significantly improve the complexity of this differential path for SHAMATA-256. With a complexity of about \(2^{40}\) we are even able to construct practical collisions for the full hash function SHAMATA-256.
For the entire collection see [Zbl 1177.94012].

MSC:
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI