MD yapıları için tanım değeri belirleme

Abstract

Özet fonksiyonları dijital imza, veri bütünlüğü, asıllama protokolleri, mesaj asıllama kod (MAC) algoritmaları ve rastgele sayı üreteçleri (RNG'ler) gibi çeşitli uygulamalarda yaygın olarak kullanılan kriptografik yapılardan biridir. Özet fonksiyonlarının tek yönlü olması gereklidir, yani ilk değer dirençli. Bu fonksiyonların enteresan özelliklerinden biri farklı uzunluklarda mesajları sabit uzunluktaki mesajlara dönüştürmeleridir. Genellikle, bu işlem mesajı eşit uzunlukta bloklara bölüp her birini sırayla sıkıştırma fonksiyonundan geçirerek yapılır. Mesaj uzunluğu tamamlama bloğuna ek olarak özet değeri oluşmadan önce son blokla birleştirilir, bu yönteme Merkle-Damgård (MD) güçlendirmesi denir. Bu çalışmada, MD güçlendirmesi kullansa da özet fonksiyonlarının sıkıştırma fonksiyonlarından oluşturulan Rainbow tabloları ile ilk değer bulmaya yönelik bir yöntem önerilmiştir. MD güçlendirmesinin üstesinden gelmek için Rainbow veya Hellman yöntemlerinin klasik uygulanmasının aksine sütun fonksiyonları ilk değerler kümesinden oluşturulmuştur. Farklı bir yaklaşım olarak, ilk değeri bulmak için verilen değerin tablodaki pozisyonu kullanılmıştır. Zincir değerinin ve özet değerinin uzunluğu olan bir fonksiyonda verilen bir özet değerinin ilk değerini bulmanın iş yükü hafıza kullanıp adım işlem yapmaktır. Çalışmada, çıkışta farklı fonksiyon kullanan, mesaj blok uzunluğunu girdi olarak alan veya rastgele tuz değeri kullanan bazı geliştirilmiş MD yapıları için ilk değer bulma yöntemine uzantılar ekleyerek yöntemin çalışmasının sağlanabileceği gösterilmiştir. Ayrıca, yakın ilk değer kavramı önerilmiş ve bu kavram için yakın ilk değer bulmaya yönelik yöntem sunulmuştur. Bu yöntem zincir ve özet değerinin uzunluğu eşit olmayan fonksiyonlar da göz önüne alınarak genelleştirilmiştir. Deneysel sonuçlar elde edilmiş ve 40 bit özet uzunluğuna sahip bir fonksiyona ait ilk değer deneme yanılma yöntemiyle yaklaşık bir hafta sürecekken bu yöntemle standart bir bilgisayar kullanılarak bir dakika içinde ele geçirilmiştir.

Hash functions are one of the ubiquitous cryptographic functions used widely for various applications such as digital signatures, data integrity, authentication protocols, message authentication code (MAC) algorithms, random number generators (RNGs), etc. Hash functions are supposed to be one-way, i.e., preimage resistant. One interesting property of hash functions is that they process arbitrary-length messages into fixed-length outputs. In general, this can be achieved mostly by applying compression functions onto the message blocks of fixed length, recursively. The length of the message is incorporated as padding in the last block prior to the hash, a procedure called the Merkle-Damgård strengthening. In this thesis, we introduce a new way to find preimages on a hash function by using a Rainbow table of its compression function even if the hash function utilizes the Merkle-Damgård (MD) strengthening as a padding procedure. To overcome the MD strengthening, we identify the column functions as representatives of certain set of preimages, unlike conventional usage of Rainbow tables or Hellman tables to invert one-way functions. As a different approach, we use the position of the given value in the table to invert it. The workload of finding a preimage of a given arbitrary digest value is steps by using memory, where is both the digest size and the length of the chaining value. We give some extensions of the preimage attack on certain improved variants of MD constructions such as using output functions, incorporating the length of message blocks or using random salt values. Moreover, we introduce the notion of ?near-preimage? and mount an attack to find near-preimages. We generalize the attack when the digest size is not equal to the length of chaining value. We have verified the results experimentally, in which we could find a preimage in one minute for the 40-bit hash function, whereas the exhaustive search took roughly one week on a standard PC.