Design and analysis of hash functions

Abstract

Özet fonksiyonlar sayısal imza, veri bütünlüğünün kontrolü, şifre saklama ve rassal sayı üretimi gibi birçok uygulamada kullanılan kriptografik araçlardır. Özet fonksiyonlar önceleri açık anahtarlı şifrelemenin duyurulmasıyla kullanımı artan modüler aritmetik işlemlerinden yararlanılarak tasarlanıyordu. Daha sonra 1989'da bağımsız olarak Merkle ve Damgard tarafından yinelemeli bir tasarım metodu duyuruldu. Bu methodun uygulanması kolaydı ve bir güvenlik ispatı vardı. Tasarım metodlarındaki gelişmeler, analiz metodlarının da gelişip çeşitlenmesine sebep oldu. Wang ve ekibinin MD ve SHA ailesine yaptığı saldırılar MD-5 ile SHA-0 ve SHA-1 i tehdit ederken, aynı yapıdaki standart özet algoritması SHA-2 'nin güvenliğini de şüpheye düşürüyordu. Bu sebeple NIST, daha güvenli bir özet fonksiyonu seçmek için, açık katılımlı bir yarışma düzenledi.Özet fonskiyonların tasarımı ve analizi, bu yarışmanın duyurulmasıyla kriptografinin en ilgi çeken konusu haline geldi. Yarışma için birçok algoritma tasarlandı, güvenlikleri test edildi ve NIST'e gönderildi. Daha sonra da dünya çapında ilgililer tarafından güvenlikleri sınandı ve sınanmakta.Bu tez özet fonksiyonların iki önemli yönünü sunmaktadır: tasarım ve analiz. Tasarım sıkıştırma fonksiyonları ve yapı yöntemleri olmak üzere iki altbaşlık altında incelenmektedir. Sıkıştırma fonksiyonları algoritmanın çekirdeğini oluştururlar ve tasarım aşamasında en çok üzerinde durulan öğedir. Merkle-Damgard yapısındaki özet fonksiyonlarda algoritmanın güvenliği, sıkıştırma fonksiyonunun güvenliğine dayanır. Yapı yöntemi, algoritmanın güvenliğini belirleyen bir başka tasarım öğesidir. Yapı yöntemi ile sıkıştırma fonksiyonu birbirleriyle tutarlı olmalıdır. Diğer taraftan, tasarım aşamasında analizler de tasarım öğelerinin seçimi kadar önemlidir. Bilinen ataklar yardımıyla algoritmadaki zayıflıklar ortaya çıkartılıp algoritma güçlendirilebilir. Ayrıca kullanımda olan bir özet algoritmasının güvenliği de bu yöntemlerle sınanabilir. Tezin analiz bölümü birçok algoritmaya uygulanabilen ataklardan oluşmaktadır. Bu ataklar arasında NIST tarafından seçilecek algoritmanın dayanıklı olması özellikle vurgulanan ataklar da bulunmaktadır.

Hash functions are cryptographic tools that are used in various applications like digital signature, message integrity checking, password storage and random number generation. These cryptographic primitives were, first, constructed using modular arithmetical operations which were popular at that time because of public key cryptography. Later, in 1989, Merkle and Damgard independently proposed an iterative construction method. This method was easy to implement and had a security proof. MD-4 was the first hash function to be designed using Merkle-Damgard construction. MD-5 and SHA algorithms followed MD-4. The improvements in the construction methods accordingly resulted in improvements and variations of cryptanalytic methods. The series of attacks of Wang et al. on MD and SHA families threaten the security of these hash functions. Moreover, as the standard hashing algorithm SHA-2 has a similar structure with the mentioned hash functions, its security became questionable. Therefore, NIST announced a publicly available contest to select the new algorithm as the new hash standard SHA-3.The design and analysis of hash functions became the most interesting topic of cryptography. A considerable number of algorithms had been designed for the competition. These algorithms were tested against possible attacks and proposed to NIST. After this step, a worldwide interest started to check the security of the algorithms which will continue until 4th quarter of 2011 to contribute to the selection process.This thesis presents two important aspects of hash functions: design and analysis. The design of hash functions are investigated under two subtopics which are compression functions and the construction methods. Compression functions are the core of the hashing algorithms and most of the effort is on the compression function when designing an algorithm. Moreover, for Merkle-Damgard hash functions, the security of the algorithm depends on the security of the compression function. Construction method is also an important design parameter which defines the strength of the algorithm. Construction method and compression function should be consistent with each other. On the other hand, when designing a hash function analysis is as important as choosing designing parameters. Using known attacks, possible weaknesses in the algorithm can be revealed and algorithm can be strengthened. Also, the security of a hash function can be examined using cryptanalytic methods. The analysis part of the thesis is consisting of various generic attacks that are selected to apply most of the hash functions. This part includes the attacks that NIST is expecting from new standard algorithm to resist.