Boşluk azalması meydana gelir, ancak böyle değildir.
Güvenli hash işlevlerinin, ortalama olarak rastgele bir işlevin yapacağı gibi davranması beklenir (yani, olası işlevler kümesi arasından tek tip olarak seçilen bir işlev ile aynı giriş ve çıkış uzunlukları). MD5 ve SHA-1'in nihai olarak güvenli olmadığı biliniyor (çünkü onlar için çarpışmaları rastgele bir işlevle bulabileceğimizden daha verimli bir şekilde bulabiliriz), ancak burada hala yeterince yakın tahminler var (yine de, birlikte çalışabilirlik dışında bunları kullanmamalısınız eski uygulamalarla; gerçekten SHA-256 gibi daha modern ve güvenli bir işlev kullanmalısınız).
Yani, n bitlik bir çıktı varsayarsak, 2 n n bit dizileri varsa, tüm çıktıların 2 n boşluğunun yaklaşık% 63.21'ini kapsamasını bekleyebilirsiniz. sup> olası çıktı değerleri (bu 1- (1 / e )). Alanın üçte birinden biraz fazlasını kaybedersiniz. Ancak , elde edilen tüm bu değerleri yeniden kullanırsanız, üçte birinden çok daha azını kaybedersiniz. Azaltma faktörü her tur için sabit değildir. Birkaç turdan sonra, tur başına ekstra azaltma çok azdır.
Belirli bir değere art arda birçok kez hash işlemi uyguladığınızda, aslında bir "rho yapısı" nda yürürsünüz. aşağıdaki şekil:
Bu yapı, kabaca Yunanca ρ, "rho" harfine benzediği için bu şekilde adlandırılmıştır. Her nokta n bitlik bir değerdir ve her ok, karma işlevinizin uygulamasını temsil eder. Mavi nokta, başlangıç noktanızdır. Yani fikir şu ki, işlevi yeterince çok kez uygulayarak, sonunda bir döngüye giriyorsunuz. Döngüde bir kez, hash fonksiyonunun art arda uygulamaları artık olası değerlerin alanını azaltmaz: sadece döngüde süresiz olarak yürürsünüz. Döngü uzunluğu, elde edebileceğiniz minimum alan boyutudur.
Hem "kuyruk" (döngüye girmeden önce geçtiğiniz değerler) hem de "döngünün" uzunlukları ortalama olarak 2 n / 2 sup >. Dolayısıyla, 128-bit çıktılı bir karma işlevi için, ardışık uygulamalar alanı 2 64 değerinin altına düşürmez, bu oldukça büyük bir değerdir; Bu minimum alana eşit bir şekilde ulaşmak, ortalama olarak 2 64 karma işlevi değerlendirmesi gerektirir, bu da pahalıdır.
Döngüyü, rho yapısını yürüyerek bulmak aslında Bir karma işlevi için çarpışmalar oluşturmak için kullanılabilen genel algoritmalardan biri olan Floyd'un döngü bulma algoritmasının temeli: rho yapısında, kuyruğun döngüye eklendiği noktada , bir çarpışma var (aynı değere hash olan iki farklı değer). Kriptografik olarak güvenli bir hash işlevi için, çarpışmaları bulmak zor olmalı; özellikle, Floyd'un algoritması hesaplama açısından uygulanabilir olmamalıdır; bu, n yeterince büyük hale getirilerek elde edilir (ör. SHA-256 için n = 256 : bu Floyd'un algoritmasının maliyetini artırır 2 128 , yani Dünya'da gerçekçi olarak mümkün değil).
Diğer bir deyişle: eğer yeterince geniş bir güvenli hash işlevi seçerseniz çıktı (güvenli olmanın bir ön koşulu), o zaman döngüye ulaşamayacak ve / veya yürüyemeyeceksiniz ve güvenliğiniz herhangi bir "alan azaltma" dan zarar görmeyecektir. Sonuç: Bir alan azaltma sorununuz varsa, o zaman güvenli bir karma işlevi kullanmıyorsunuzdur ve bu , düzeltmeniz gereken sorundur. Bu nedenle, SHA-256 kullanın.