Doğum Günü ve Çakışma Saldırıları

23 kişilik bir grupta iki kişinin aynı doğum gününe sahip olma olasılığı %50'yi aşar. 70 kişi olduğunda bu olasılık %99,9'u aşar. Matematiksel olarak, N büyüklüğünde bir kümede çakışma olasılığı yaklaşık √N örnekten sonra %50'yi aşar. Buna doğum günü sınırı denir.

n bitlik bir özet işlevi için bir çakışma (H(m1) = H(m2), m1 ≠ m2), yaklaşık 2^{n/2} rastgele denemeyle bulunabilir. SHA-256 (256 bit) için çakışma bulmak yaklaşık 2^{128} işlem gerektirir; bu hesaplama açısından uygulanabilir değildir. MD5 (128 bit) için gereken yaklaşık 2^{64} işlemlik maliyet ise sınırda uygulanabilirdir.

Genel amaçlı çakışma bulma: 2^{n/2} rastgele ileti üretin, özetleri hesaplayın, özet değerine göre sıralayın ve yinelenenleri bulun. Bellek O(2^{n/2}) olur. Rho algoritması (Floyd'un döngü bulma yöntemi), aynı zaman maliyetinde belleği O(1)'e düşürür. van Oorschot-Wiener paralel çakışma araması, donanımla süreyi azaltır.

MD5'te pratik çakışmalar, doğum günü saldırısı kullanılarak değil, diferansiyel kriptanaliz kullanılarak Wang ve arkadaşları tarafından 2004'te bulundu. Özdeş MD5 özetine sahip iki farklı 1024 bitlik ileti saniyeler içinde üretilebiliyor. Hertzbleed ve seçilmiş önek çakışmaları, sertifika çakışmaları oluşturmaya olanak tanır. MD5, çakışma direnci açısından tamamen kırılmıştır.

Daha güçlü bir yaklaşımda, iki rastgele önek P1 ve P2 verildiğinde H(P1||S1) = H(P2||S2) olacak S1 ve S2 sonekleri bulunur. Stevens ve arkadaşları (2017), seçilmiş önekli MD5 çakışmaları buldu. Bu yöntem, geçerli bir MD5 imzasına sahip kötü amaçlı bir CA sertifikası oluşturmak için kullanıldı. MD5'in sertifikalarda kullanımına son verildi.

Google'ın SHAttered çalışması (2017), SHA-1'deki ilk pratik çakışmayı ortaya koydu. Aynı SHA-1 özetine sahip iki farklı PDF dosyası üretildi. 2^{63.1} SHA-1 sıkıştırma işlemi gerekti; bu, 6.500 CPU yılına ve 110 GPU yılına eşdeğerdi. Maliyet yaklaşık 110.000 dolardı. Tarayıcılar SHA-1 sertifikalarını 2017'de kullanımdan kaldırdı.

Merkle-Damgård özet işlevleri (MD5, SHA-1, SHA-2) için: H(m)'yi biliyorsanız, m'yi bilmeden H(m||padding||m') hesaplayabilirsiniz. Bu durum H(secret||message) gibi MAC yapılarının güvenliğini bozar. Çözüm: HMAC kullanın (iç ve dış dolgu kullanır) veya SHA-3 kullanın (sünger yapısı; uzunluk genişletme saldırılarına karşı bağışıktır).

Çakışma direnci: aynı özete sahip, birbirinden farklı herhangi iki mesaj bulma (2^{n/2} çalışma). İkinci ön görüntü direnci: m verildiğinde, aynı özete sahip m' ≠ m bulma (2^n çalışma). Ön görüntü direnci: belirli bir özet için herhangi bir mesaj bulma (2^n çalışma). Çakışma direnci her zaman en zayıf olanıdır.

MAC, çakışmalara karşı savunmasız bir özet işlevi kullanıyorsa, H içinde çakışma bulabilen bir saldırgan MAC'leri sahteleyebilir. HMAC-MD5, MD5 çakışmalarına rağmen güvenli kabul edilir; çünkü HMAC yapısı yalnızca çakışma saldırılarını değil, ön görüntü saldırılarını gerektirir. Ancak yeni sistemler için HMAC-MD5 kullanımından vazgeçin.

Joux (2004): Merkle-Damgård özetleri için 2^k-yollu çakışmalar bulmak (aynı özete sahip 2^k mesaj) tek bir çakışma bulmak için gereken çalışmanın k katını değil, yalnızca k katını gerektirir. Bu durum birleştirilmiş özetlerdeki güvenlik açıklarını büyütür (H1(m)||H2(m), düşünüldüğü kadar güçlü değildir).

Çakışmaya dayanıklı özetleme için SHA-256 veya SHA-3 kullanın. Herhangi bir güvenlik amacıyla MD5 ve SHA-1 kullanmaktan kaçının. MAC'ler için HMAC-SHA-256 veya HMAC-SHA-3 kullanın. Parola özetleme için doğrudan SHA-2 yerine Argon2 kullanın. Uzunluk genişletme saldırılarına karşı direnç gerektiğinde her zaman SHA-3 kullanın.

n bitlik bir özet işlevinde çakışma bulmak için yaklaşık kaç özet hesaplaması gerekir?

Doğum günü saldırısı, 2^{n/2} çalışma ile özet çakışmaları bulur. MD5'in pratik seçilmiş ön ek çakışmaları vardır; SHA-1, 2017'de kırılmıştır. Uzunluk genişletme saldırıları, saf H(key||msg) MAC'lerinin güvenliğini bozar. SHA-256 veya SHA-3 kullanın; mesaj kimlik doğrulaması için HMAC kullanın. Sıradaki konu: ortada buluşma saldırıları.