University of Oulu

Hash function security : cryptanalysis of the Very Smooth Hash and multicollisions in generalised iterated hash functions

Saved in:
Author: Halunen, Kimmo1,2,3
Organizations: 1University of Oulu Graduate School
2University of Oulu, Faculty of Technology, Department of Computer Science and Engineering
3University of Oulu, Infotech Oulu
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, 0.8 MB)
Persistent link:
Language: English
Published: Oulu : University of Oulu, 2012
Publish Date: 2012-11-06
Thesis type: Doctoral Dissertation
Defence Note: Academic dissertation to be presented with the assent of the Doctoral Training Committee of Technology and Natural Sciences of the University of Oulu for public defence in Auditorium TS101, Linnanmaa, on 16 November 2012, at 9 a.m.
Tutor: Professor Juha Röning
Reviewer: Professor Bart Preneel
Doctor Martijn Stam


In recent years, the amount of electronic communication has grown enormously. This has posed some new problems in information security. In particular, the methods in cryptography have been under much scrutiny. There are several basic primitives that modern cryptographic protocols utilise. One of these is hash functions, which are used to compute short hash values from messages of any length.

In this thesis, we study the security of hash functions from two different viewpoints. First of all, we analyse the security of the Very Smooth Hash against preimage attacks. We develop an improved method for finding preimages of Very Smooth Hash, compare this method with existing methods and demonstrate its efficiency with practical results. Furthermore, we generalise this method to the discrete logarithm variants of the Very Smooth Hash.

Secondly, we describe the methods for finding multicollisions in traditional iterated hash functions and give some extensions and improvements to these. We also outline a method for finding multicollisions for generalised iterated hash functions and discuss the implications of these findings. In addition, we generalise these multicollision finding methods to some graph-based hash functions.

see all


Viime vuosina digitaaliseen tiedonsiirtoon perustuva tiedonsiirto on yleistynyt valtavasti. Tästä on seurannut monia uusia tietoturvaongelmia. Tässä yhteydessä erityisesti tiedon suojaamiseen käytetyt kryptografiset menetelmät ovat olleet tarkastelun kohteena. Hash-funktiot ovat yksi käytetyimmistä työkaluista nykyisissä kryptografisissa protokollissa.

Tässä väitöskirjassa tarkastellaan hash-funktioiden turvallisuutta kahden eri tutkimusongelman kautta. Aluksi tutkitaan Very Smooth Hash -funktion turvallisuutta alkukuvien löytämistä vastaan. Alkukuvien löytämiseksi esitetään parannettu menetelmä, jota arvioidaan teoreettisilla ja käytännöllisillä menetelmillä. Tämä parannettu menetelmä yleistetään koskemaan myös Very Smooth Hashin muunnoksia, jotka perustuvat diskreetin logaritmin ongelmaan.

Toisena tutkimuskohteena ovat iteroitujen hash-funktioiden yleistykset ja monitörmäykset. Aluksi esitellään perinteisiin iteroituihin hash-funktioihin liittyviä monitörmäysmenetelmiä. Tämän jälkeen tutkitaan iteroitujen hash-funktioiden yleistyksiä ja osoitetaan, että aiemmat monitörmäysmenetelmät voidaan laajentaa koskemaan myös näitä yleistyksiä. Lopuksi tutkitaan graafeihin perustuviin hash-funktioihin liittyviä monitörmäysmenetelmiä ja osoitetaan, että iteroitujen hash-funktioiden monitörmäysmenetelmä voidaan osittain yleistää koskemaan myös graafeihin perustuvia hash-funktioita.

see all

Series: Acta Universitatis Ouluensis. C, Technica
ISSN: 0355-3213
ISSN-E: 1796-2226
ISSN-L: 0355-3213
ISBN: 978-951-42-9966-7
ISBN Print: 978-951-42-9965-0
Issue: 433
Copyright information: © University of Oulu, 2012. This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.