Hash Functions and Gröbner Bases Cryptanalysis

Abstract

Hash functions are being used as building blocks in such diverse primitives as commitment schemes, message authentication codes and digital signatures. These primitives have important applications by themselves, and they are also used in the construction of more complex protocols such as electronic voting systems, online auctions, public-key distribution, mutual authentication handshakes and more. Part of the work presented in this thesis has contributed to the \SHA-3 contest" for developing the new standard for hash functions organized by the National Institute of Standards and Technology. We constructed the candidate Edon-R, which is a hash function based on quasigroup string transformation. Edon-R was designed to be much more efficient than SHA-2 cryptographic hash functions, while at the same time offering same or better security. Most notably Edon-R was the most efficient hash function submitted to the contest.

Another contribution to the contest was our cryptanalysis of the second round SHA-3 candidate Hamsi. In our work we studied Hamsi's resistance to differential and higher-order differential cryptanalysis, with focus on the 256-bit version of Hamsi. Our main results are efficient distinguishers and near-collisions for its full (3-round) compression function, and distinguishers for its full (6-round) finalization function, indicating that Hamsi's building blocks do not behave ideally.

Another important part of this thesis is the application of Gröbner bases. In the last decade, Gröbner bases have shown to be a valuable tool for algebraic cryptanalysis. The idea is to set up a system of multivariate equations such that the solution of the system reveals some secret information of the cryptographic primitive. The system is then solved with Gröbner bases computation. Staying close to the topic of hash functions, we have applied this tool for cryptanalysis and construction of multivariate digital signature schemes, which is a major hash function application. The result of this is our cryptanalysis of the public-key cryptosystem MQQ, where we show exactly why the multivariate quadratic equation system is so easy to solve in practice. The knowledge we gained from finding the underlying weakness of the MQQ scheme was used to construct a digital signature scheme. The resulting scheme, MQQ-SIG, is a provably CMA resistant multivariate quadratic digital signature scheme based on multivariate quadratic quasigroups. The scheme is designed to be very fast both in hardware and in software. Compared to some other multivariate quadratic digital signature schemes, MQQ-SIG is much better in signing and private key size, while worse in key generation, verification and public key size. This means that MQQ-SIG is a good alternative for protocols where the constrained environment is on the side of the signer.