University of Oulu

On iteration-based security flaws in modern hash functions

Saved in:
Author: Kortelainen, Tuomas
Organizations: University of Oulu Graduate School
University of Oulu, Faculty of Science, Department of Mathematical Sciences
University of Oulu, Faculty of Information Technology and Electrical Engineering, Department of Information Processing Science
Format: eBook
Online Access: PDF Full Text (PDF, 1.3 MB)
Persistent link: http://urn.fi/urn:isbn:9789526206431
Language: English
Published: Oulu : University of Oulu, 2014
Publish Date: 2014-11-28
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 the OP auditorium (L10), Linnanmaa, on 9 December 2014, at 12 noon
Tutor: Professor Markku Niemenmaa
Doctor Ari Vesanen
Reviewer: Professor Valtteri Niemi
Professor Orr Dunkelman
Description:

Abstract

The design principles proposed independently by both Ralph Merkle and Ivan Damgård in 1989 are applied widely in hash functions that are used in practice. The construction reads the message in one message block at a time and applies iteratively a compression function that, given a single message block and a hash value, outputs a new hash value.

This iterative structure has some security weaknesses. It is vulnerable, for instance, to Joux's multicollision attack, herding attack that uses diamond structures and Trojan message attack.

Our principal research topic comprises the deficiencies in hash function security induced by the Merkle-Damgård construction. In this work, we present a variant of Joux's multicollision attack. We also develop a new, time-saving algorithm for creating diamond structures. Moreover, two new efficient versions of Trojan message attack are introduced.

The main contribution of the thesis is the analysis of generalized iterated hash functions. We study the combinatorial properties of words from a new perspective and develop results that are applied to give a new upper bound for the complexity of multicollision attacks against the so called q-bounded generalized iterated hash functions.


Tiivistelmä

Vuonna 1989 Ralph Merkle ja Ivan Damgård ehdottivat toisistaan riippumatta hash-funktioille suunnitteluperiaatteita, joita käytetään tänä päivänä laajasti. Niin kutsuttu Merkle-Damgård -rakenne lukee viestin sisään viestiblokki kerrallaan ja käyttää tiivistefunktiota, joka liittää hash-arvoon ja viestiblokkiin uuden hash-arvon.

Tällä iteratiivisella rakenteella on joitakin turvallisuusheikkouksia. Se on haavoittuva esimerkiksi Joux’n monitörmäyshyökkäykselle, timanttirakenteita hyödyntävälle paimennushyökkäykselle ja Troijan viesti -hyökkäykselle.

Väitöskirjan pääasiallinen tutkimusaihe on Merkle-Damgård -rakenteen aiheuttamat puutteet tietoturvassa. Tässä työssä esitetään uusi versio Joux’n monitörmäyshyökkäyksestä, luodaan uusi aikaa säästävä algoritmi timanttirakenteiden kehittämiseksi ja kaksi uutta tehokasta versiota Troijan viesti -hyökkäyksestä.

Väitöskirjan tärkein kontribuutio on yleistettyjen iteratiivisten hash-funktioiden turvallisuuden analysointi. Sanojen kombinatorisia ominaisuuksia tutkitaan uudesta näkökulmasta, jonka pohjalta kehitettyjä tuloksia soveltamalla luodaan uusi yläraja niin kutsuttujen q-rajoitettujen yleisten iteratiivisten hash-funktioiden monitörmäyshyökkäysten kompleksisuudelle.


Series: Acta Universitatis Ouluensis. A, Scientiae rerum naturalium
ISSN: 0355-3191
ISSN-E: 1796-220X
ISSN-L: 0355-3191
ISBN: 978-952-62-0643-1
ISBN Print: 978-952-62-0642-4
Issue: 638
Subjects:
Copyright information: This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.