Bart Mennink

Title

Provable Security of Cryptographic Hash Functions
(Bewijsbare veiligheid van cryptografische hashfuncties)

Jury

Prof. dr. ir. Pierre Verbaeten, chairman
Prof. dr. ir. Bart Preneel, promotor
Prof. dr. ir. Vincent Rijmen, promotor
Prof. dr. Marc Fischlin (Darmstadt University of Technology, Germany)
Prof. dr. ir. Frank Piessens
Dr. ir. Martijn Stam (University of Bristol, UK)
Prof. dr. ir. Joos Vandewalle

Date, Time, and Location

Tuesday May 7, 2013 at 13:30
Auditorium Arenberg Castle
Kasteelpark Arenberg 1
3001 Heverlee, Belgium

Abstract

Cryptographic hash functions form the basis of the security of today's digital environment, and find applications in numerous cryptographic systems such as tamper detection, key derivation functions, and digital signatures. Ideally, hash functions behave like a random oracle, a function that returns random outputs for each new input, but in practice such a construction does not exist. Usually, a hash function is designed to give strong confidence that it is indeed secure, and it is presumed secure until it is broken. In 2004-2005, cryptanalytic breakthroughs have raised doubts about the security of many widely employed hash functions, such as MD5 and SHA-1. As a response, in 2007 the US National Institute for Standards and Technology (NIST) announced a call for the design of a new SHA-3 hashing algorithm.

This dissertation deals with the fundamental security properties of hash functions. It is divided into two parts.

In the first part of the dissertation, we analyze existing hash functions and introduce design methodologies. We particularly search for the limits within the provable security framework, by considering minimalist designs with maximal security. Firstly, we look at double block length 3n-to-2n-bit compression functions based on block ciphers with an n-bit message and key space. We consider the MDC-4 hash function, and improve its collision and preimage security bounds. Next, we present a family of designs that make three cipher calls and achieve optimal collision security and very good preimage security. Furthermore, we consider the possibility of compression functions based on permutations, and provide a full security classification of all 2n-to-n-bit compression functions solely built of XOR operators and three permutations.

As a final contribution of this part, we propose the family of parazoa functions as a generalization of the sponge hash function design, and prove that parazoa functions are indifferentiable from a random oracle. The sponge is a popular hash function design and many derivatives, called sponge-like functions, appeared in literature. However, these sponge-like functions do not automatically enjoy the same security guarantees as the original sponge. Our generalized parazoa family applies to a wide class of sponge-like functions, and the indifferentiability proof for parazoa naturally carries over.

In the second part of the dissertation, we consider NIST's SHA-3 hash function competition from a provable security point of view. We provide a detailed survey of the five SHA-3 finalists, in which we analyze and compare their security guarantees. We consider collision, preimage, and second preimage resistance and indifferentiability of all finalists, and solve open problems where needed.

Samenvatting

Cryptografische hashfuncties liggen ten grondslag aan de beveiliging van de hedendaagse digitale wereld, en worden gebruikt in talrijke cryptografische toepassingen zoals het detecteren van ongeoorloofde datawijzigingen, het afleiden van cryptografische sleutels en digitale handtekeningen. In het ideale geval gedraagt een hashfunctie zich als een volledig willekeurige functionaliteit, een functie die voor iedere invoer een willekeurige uitvoer produceert, maar zulk soort functies bestaan in de praktijk niet. Derhalve worden hashfuncties normaliter op een zodanige wijze ontworpen dat ze veilig genoeg lijken, en ze worden veilig geacht totdat iemand een zwakheid in de functie ontdekt. In 2004-2005 hebben cryptanalytische doorbraken echter de veiligheid van enkele wijdverspreide hashfuncties, zoals MD5 en SHA-1, ter discussie gesteld. Om deze reden lanceerde het National Institute for Standards and Technology (NIST) van de VS in 2007 een internationale competitie voor het ontwerp van een nieuwe SHA-3 hashfunctie.

Deze dissertatie behandelt fundamentele veiligheidsaspecten van cryptografische hashfuncties. Ze bestaat uit twee delen.

In het eerste deel van de dissertatie analyseren we bestaande hashfuncties en introduceren we nieuwe ontwerpmethoden. In het bijzonder gaan we op zoek naar de limieten van het bewijsbareveiligheidskader, waarbij we minimalistische ontwerpen met maximale veiligheid bekijken. Als eerste onderzoeken we compressiefuncties van dubbele bloklengte: 3n-naar-2n-bit compressiefuncties gebaseerd op blokcijfers met een n-bit bericht- en sleutelgrootte. We beschouwen de MDC-4 hashfunctie en verbeteren haar botsings- en éénwegsaanvalsbestendigheidsgrens. Vervolgens introduceren we een nieuwe familie van ontwerpen die drie cijferoproepen doen en die optimale botsingsbestendigheid en zeer goede éénwegsaanvalsbestendigheid bereiken. Voorts analyseren we de mogelijkheid om compressiefuncties te construeren van permutaties, en verschaffen een volledige veiligheidsclassificatie van alle 2n-naar-n-bit compressiefuncties louter gebouwd op XOR-operators en drie permutaties.

Als laatste bijdrage van dit deel van de dissertatie presenteren we de familie van parazoafuncties als een generalisatie van sponsfuncties, en bewijzen we dat parazoafuncties indifferentieerbaar zijn van een volledig willekeurige functionaliteit. De spons is een populair hashfunctieontwerp en tal van afgeleiden, zogenaamde sponsachtige functies, zijn in de loop der tijd gepubliceerd. Deze sponsachtige functies genieten echter niet automatisch dezelfde veiligheidsgaranties als de oorspronkelijke spons. Onze gegeneraliseerde parazoafamilie behelst een breed spectrum van sponsachtige functies, en het indifferentieerbaarheidsbewijs voor parazoa is overdraagbaar naar deze functies.

In het tweede deel van de dissertatie beschouwen we NIST's SHA-3 hashfunctiecompetitie met betrekking tot haar bewijsbare veiligheid. We presenteren een gedetailleerde beschouwing van de vijf SHA-3-finalisten, waarin we hun veiligheidseigenschappen analyseren en vergelijken. We beschouwen botsings-, éénwegsaanvals- en tweede-éénwegsaanvalsbestendigheid, alsmede indifferentieerbaarheid van alle finalisten, en lossen waar nodig open problemen op.

Samevatting

Cryptografische hashfunkties ligke te gróndjsjlaag aan de beveiliging van de hedendaagse digitale waereld, en waere gebroêk in talrieke cryptografische toepassinge zoès het opsjpaore van onrechmaotige gegaevesverangeringe, het aafleije van cryptografische sjleutels en digitale handjteikeninge. In het ideale geval gedreug ein hashfunktie zich wie ein volledig willekäörige funktionaliteit, ein funktie die veur jedere inveur ein willekäörige oetveur produceert, mèr zo ein funkties besjtaon in de praktijk neet. Daorom waere hashfunkties normaal gesjpraoke op ein zodanige maneer ontworpe dat ze veilig genóg lieke, en ze waere veilig besjouwd totdat emes ein zjwaakheid in de funktie ontdèk. In 2004-2005 höbbe cryptanalytische doorbrake echter de veiligheid van versjillende wiedversjpreide hashfunkties, zoès MD5 en SHA-1, ter discussie gesjtèld. Om dees raeje lanceerde het National Institute for Standards and Technology (NIST) van de VS in 2007 ein internationale competitie veur het ontwerp van ein nuuje SHA-3 hashfunktie.

Dees dissertatie behanjelt fundamentele veiligheidsaspecte van cryptografische hashfunkties. Ze besjteit oet tweë deile.

In het eësjte deil van de dissertatie analysere ver besjtaonde hashfunkties en introducere ver nuuje ontwerpmethodes. In het biezunjer gaon ver op zeuk nao de limiete van het bewiesbareveiligheidskader, wobie ver minimalistische ontwerpe mit maximale veiligheid bekieke. Es eësjte ongerzeuke ver kompressiefunkties van dubbele bloklengte: 3n-nao-2n-bit kompressiefunkties gebaseerd op bloksiefers mit ein n-bit berich- en sjleutelgroatte. Ver besjouwe de MDC-4 hashfunktie en verbaetere häör botsings- en einwaegsaanvalsbesjtendigheidsgrens. Vervolges introducere ver ein nuuje femielie van ontwerpe die drie sieferopreupe doon en die optimale botsingsbesjtendigheid en zeer gooje einwaegsaanvalsbesjtendigheid bereike. Wiejer analysere ver de mäögelikheid om kompressiefunkties te construere van permutaties, en versjaffe ein volledige veiligheidsklassifikatie van alle 2n-nao-n-bit kompressiefunkties louter geboewd op XOR-operators en drie permutaties.

Es lètste biedraag van dit deil van de dissertatie prizzentere ver de femielie van parazoafunkties es ein generalisatie van sjponsfunkties, en bewieze ver dat parazoafunkties indifferentieerbaar zeen van ein volledig willekäörige funktionaliteit. De sjpons is ein populair hashfunktieontwerp en tal van aafgeleije, zogenaamde sjponsachtige funkties, zeen in de laup der tied gepubliceerd. Dees sjponsachtige funkties genete echter neet automatisch dezelfde veiligheidsgeranties es de oorsjpronkelikke sjpons. Ózze gegeneraliseerde parazoafemielie behels ein breid sjpectrum van sjponsachtige funkties, en het indifferentieerbaarheidsbewies veur parazoa is euverdraagbaar nao dees funkties.

In het tweëde deil van de dissertatie besjouwe ver NIST's SHA-3 hashfunktiecompetitie mit betrèkking tot häör bewiesbare veiligheid. Ver presentere ein gedetailleerde besjouwing van de vief SHA-3-finaliste, wo-in ver hun veiligheidseigensjappe analysere en vergelieke. Ver besjouwe botsings-, einwaegsaanvals- en tweëde-einwaegsaanvalsbesjtendigheid, es auch indifferentieerbaarheid van alle finaliste, en losse wo neudig aope probleme op.

Last modified: Apr 6, 2024