Çarpışma saldırısı

Kriptografide, bir kriptografik hash üzerindeki bir çarpışma saldırısı, aynı hash değerini üreten iki girdi bulmaya çalışır, yani bir hash çarpışması . Bu, belirli bir hedef karma değerinin belirtildiği bir ön görüntü saldırısı nın aksine bir saldırıdır. Kabaca iki tür çarpışma saldırısı vardır:

Klasik çarpışma saldırısı

   hash(m1) = hash(m2) olacak şekilde iki farklı mesaj m1 vem² bulun.

Daha genel olarak:

Seçilmiş önek çarpışma saldırısı

   İki farklı p1 ve p2 öneki verildiğinde, hash(p1 ∥ m1) = hash(p2 ∥ m2) olacak şekilde iki ek m1 vem² bulun; burada ∥ birleştirme  işlemini gösterir.

Matematiksel olarak ifade edildiğinde, bir çarpışma saldırısı, hash(m1) = hash(m2) olacak şekilde iki farklı m1 vem² mesajı bulur. Klasik bir çarpışma saldırısında, saldırganın her iki mesajın içeriği üzerinde hiçbir kontrolü yoktur, ancak bunlar algoritma tarafından keyfi olarak seçilir.

Simetrik anahtar şifrelerinin kaba kuvvet saldırılarına karşı savunmasız olması gibi, her kriptografik karma işlevi, doğası gereği bir doğum günü saldırısı kullanan çarpışmalara karşı savunmasızdır. Doğum günü sorunu nedeniyle, bu saldırılar kaba kuvvetten çok daha hızlıdır. n bitlik bir karma, 2n/2 zaman adımlarında kırılabilir (karma fonksiyonunun değerlendirmeleri).

Belirli hash işlevlerine kriptanaliz uygulayarak daha verimli saldırılar mümkündür. Bir çarpışma saldırısı keşfedildiğinde ve bir doğum günü saldırısından daha hızlı olduğu tespit edildiğinde, bir hash işlevi genellikle "bozuk" olarak kınanır. NIST özet işlevi rekabeti, büyük ölçüde, çok yaygın olarak kullanılan iki özet işlevine, MD5 ve SHA-1 'e karşı yayınlanan çarpışma saldırıları tarafından başlatıldı. MD5'e yönelik çarpışma saldırıları o kadar gelişti ki, 2007'den itibaren normal bir bilgisayarda sadece birkaç saniye sürüyor. Bu şekilde oluşturulan karma çarpışmalar genellikle sabit uzunluktadır ve büyük ölçüde yapılandırılmamıştır, bu nedenle yaygın belge biçimlerine veya protokollere saldırmak için doğrudan uygulanamaz.

Ancak, birçok biçimde bulunan dinamik yapıları kötüye kullanarak geçici çözümler mümkündür. Bu şekilde, aynı hash değerine sahip olmak için mümkün olduğunca benzer iki belge oluşturulacaktır. Bir belge imzalanmak üzere bir yetkiliye gösterilecek ve ardından imza diğer dosyaya kopyalanabilecekti. Böyle kötü niyetli bir belge, aynı belgede iki farklı mesaj içerir, ancak dosyada yapılan küçük değişikliklerle şartlı olarak birini veya diğerini görüntüler:

• PostScript gibi bazı belge biçimleri veya Microsoft Word'deki makrolar koşullu yapılara sahiptir. (if-then-else) görüntülenenleri kontrol etmek için dosyadaki bir konumun şu veya bu değere sahip olup olmadığının test edilmesini sağlar.
• TIFF dosyaları, karma değerini etkilemeden görüntünün farklı bir bölümünün görüntülendiği kırpılmış görüntüler içerebilir.
• PDF dosyaları, renk değeri kullanılarak çarpışma saldırılarına karşı savunmasızdır (bir mesajın metni, arka plana karışan beyaz bir renkle görüntülenir ve diğer mesajın metni koyu renkle görüntülenir) bu metin daha sonra imzalanan belgenin içeriğini değiştirmek için değiştirilebilir.

Çarpışma saldırısının bir uzantısı, Merkle-Damgård karma işlevlerine özgü olan, seçilen önek çarpışma saldırısıdır. Bu durumda, saldırgan keyfi olarak farklı iki belge seçebilir ve ardından tüm belgelerin eşit bir karma değerine sahip olmasıyla sonuçlanan farklı hesaplanmış değerler ekleyebilir. Bu saldırı, klasik bir çarpışma saldırısından çok daha güçlüdür.

Matematiksel olarak ifade edildiğinde, iki farklı p1, p2 öneki verildiğinde, saldırı hash(p1 ∥ m1) = hash(p2 ∥ m2) olacak şekilde iki uzantı m1 vem² bulur (burada ∥ birleştirme işlemidir).

2007'de, MD5'e karşı, MD5 işlevinin kabaca 2⁵ değerlendirmesini gerektiren, seçilen bir önek çarpışma saldırısı bulundu. Makale ayrıca, farklı alan adları için çarpışan karma değerlere sahip iki X.509 sertifikasını da gösteriyor. Bu, bir sertifika yetkilisinden bir etki alanı için bir sertifika imzalamasının istenebileceği ve ardından bu sertifikanın (özellikle imzasının) başka bir etki alanını taklit etmek için yeni bir sahte sertifika oluşturmak için kullanılabileceği anlamına gelir.

Aralık 2008'de bir grup güvenlik araştırmacısı, MD5 karma işlevine karşı bir ön ek çarpışma saldırısından yararlanarak bir sertifika yetkilisini taklit etmek için kullanılabilecek sahte bir X.509 imzalama sertifikası yayınladığında gerçek dünya çarpışma saldırısı yayınlandı. Bu, bir saldırganın SSL güvenli herhangi bir web sitesini ortadaki adam olarak taklit edebileceği ve böylece elektronik ticareti korumak için her web tarayıcısında yerleşik olarak bulunan sertifika doğrulamasını bozabileceği anlamına geliyordu. Hileli sertifika, gerçek yetkililer tarafından iptal edilemeyebilir ve ayrıca keyfi bir sahte son kullanma süresine sahip olabilir. MD5'in 2004'te çok zayıf olduğu bilinmesine rağmen, sertifika yetkilileri Aralık 2008'de MD5 onaylı sertifikaları imzalamaya hala istekliydi ve Mayıs 2012'de en az bir Microsoft kod imzalama sertifikası hala MD5 kullanıyordu.

Flame kötü amaçlı yazılımı, bileşenlerinin, hala güvenliği ihlal edilmiş MD5 algoritmasını kullanan bir Microsoft kök sertifikası tarafından kod imzasını yanıltmak için seçilen önek çarpışma saldırısının yeni bir varyasyonunu başarıyla kullandı.

2019'da araştırmacılar, SHA-1 'e karşı 266.9 ile 269.4 arasında ve maliyeti 100.000 ABD dolarından daha düşük olan, seçilmiş bir önek çarpışma saldırısı buldular. 2020'de araştırmacılar, SHA-1'e karşı seçilen önek çarpışma saldırısının karmaşıklığını 263.4'e düşürdü.

Kriptografik özet işlevlerinin çoğu uygulaması çarpışma direncine dayanmaz, bu nedenle çarpışma saldırıları güvenliklerini etkilemez. Örneğin, HMAC'ler savunmasız değildir. Saldırının faydalı olması için, saldırganın hash fonksiyonuna girdiyi kontrol etmesi gerekir.

Dijital imzalar

Dijital imza algoritmaları büyük miktarda veriyi verimli bir şekilde imzalayamadığından, çoğu uygulama, imzalanması gereken veri miktarını sabit bir boyuta indirmek ("sıkıştırmak") için bir karma işlevi kullanır. Dijital imza şemaları, genellikle, temeldeki karma işlevi pratik olarak bozulduğu anda karma çakışmalarına karşı savunmasız hale gelir; rastgele (tuzlu) karma gibi teknikler, daha sert ön görüntü saldırısını gerektirerek fazladan zaman alacaktır.

Her zamanki saldırı senaryosu şu şekildedir:

1. Mallory, aynı karma değere, yani bir çarpışmaya sahip iki farklı A ve B belgesi oluşturur. Mallory, görünüşte Alice'den gelen B belgesini kabul etmesi için Bob'u kandırmaya çalışır.
2. Mallory, A belgesini Alice'e gönderir, o da belgenin söylediklerini kabul eder, karmasını imzalar ve imzayı Mallory'ye gönderir.
3. Mallory, A belgesindeki imzayı B belgesine ekler.
4. Mallory daha sonra imzayı ve B belgesini Bob'a gönderir ve Alice'in B'yi imzaladığını iddia eder. Dijital imza, B belgesinin karma değeriyle eşleştiğinden, Bob'un yazılımı ikameyi algılayamaz.

2008'de araştırmacılar, sahte bir sertifika yetkilisi sertifikası üretmek için bu senaryoyu kullanarak MD5'e karşı seçilen bir önek çarpışma saldırısı kullandılar. Biri meşru görünen ve RapidSSL sertifika yetkilisi tarafından imzalanmak üzere gönderilen TLS ortak anahtar sertifikasının iki sürümünü oluşturdular. Aynı MD5 karma değerine sahip olan ikinci sürüm, web tarayıcılarına keyfi başka sertifikalar vermek için meşru bir otorite olarak kabul etmelerini işaret eden bayraklar içeriyordu.

Hash Taşması

Hash taşması (HashDoS olarak da bilinir), hash tablosu aramalarının en kötü durum (doğrusal araştırma) çalışma zamanından yararlanmak için hash çarpışmalarını kullanan bir hizmet reddi saldırısıdır . İlk olarak 2003'te tanımlanmıştır. Böyle bir saldırıyı gerçekleştirmek için, saldırgan sunucuya aynı değere sahip birden fazla veri parçası gönderir ve ardından sunucunun yavaş aramalar yapmasını sağlamaya çalışır. Hash tablolarında kullanılan hash fonksiyonlarının ana odak noktası güvenlik yerine hız olduğundan, çoğu büyük programlama dili etkilendi ve bu sınıfın yeni güvenlik açıkları orijinal sunumdan on yıl sonra hala ortaya çıkıyor.

Karma işlevini aşırı karmaşık hale getirmeden karma taşmasını önlemek için, anahtar bilinmediği sürece çarpışmaların bulunmasının zor olduğu güvenlik amacı ile daha yeni anahtarlı karma işlevleri tanıtıldı. Önceki karmalardan daha yavaş olabilirler, ancak yine de hesaplamaları kriptografik karmalardan çok daha kolaydır. 2021 itibarıyla Daniel J. Bernstein'ın SipHash (2012) en yaygın kullanılan hash fonksiyonu bu sınıftır. (Uygulamanın karma tablosu dışarıdan kontrol edilemediği sürece, anahtarsız "basit" karmaların kullanımı güvenli kalır.)

Bir (kısmi) ön görüntü saldırısı kullanarak Bloom filtrelerini doldurmak için benzer bir saldırı gerçekleştirmek mümkündür.

1. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.
2. M.M.J. Stevens (June 2007). "On Collisions for MD5" (PDF). [...] we are able to find collisions for MD5 in about 224.1 compressions for recommended IHVs which takes approx. 6 seconds on a 2.6 GHz Pentium 4.
3. Magnus Daum; Stefan Lucks . "Hash Collisions (The Poisoned Message Attack)". Eurocrypt 2005 rump session. Archived from the original on 2010-03-27.
4. Max Gebhardt; Georg Illies; Werner Schindler. "A Note on the Practical Value of Single Hash Collisions for Special File Formats" (PDF).
5. Marc Stevens; Arjen Lenstra; Benne de Weger (2007-11-30). "Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities" .
6. Alexander Sotirov; et al. (2008-12-30). "Creating a rogue CA certificate". Archived from the original on 2012-04-18. Retrieved 2009-10-07.
7. "Microsoft releases Security Advisory 2718704". Microsoft . 3 June 2012. Archived from the original on 7 June 2012. Retrieved 4 June 2012.
8. Marc Stevens (7 June 2012). "CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware" . Centrum Wiskunde & Informatica. Retrieved 9 June 2012.
9. Catalin Cimpanu (2019-05-13). "SHA-1 collision attacks are now actually practical and a looming danger" . ZDNet.
10. Gaëtan Leurent; Thomas Peyrin (2019-05-06). "From Collisions to Chosen-Prefix Collisions Application to Full SHA-1" (PDF).
11. Gaëtan Leurent; Thomas Peyrin (2020-01-05). "SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust" (PDF).
12. "Hash Collision Q&A". Cryptography Research Inc. 2005-02-15. Archived from the original on 2008-07-17. Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply
13. Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures
14. Alexander Sotirov; Marc Stevens; Jacob Appelbaum; Arjen Lenstra; David Molnar; Dag Arne Osvik; Benne de Weger (30 December 2008). MD5 considered harmful today . Chaos Communication Congress 2008.
15. Falkenberg, Andreas; Mainka, Christian; Somorovsky, Juraj; Schwenk, Jörg (2013). "A New Approach towards DoS Penetration Testing on Web Services". 2013 IEEE 20th International Conference on Web Services: 491–498. doi :10.1109/ICWS.2013.72 .
16. "About that hash flooding vulnerability in Node.js... · V8" . v8.dev.
17. Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th conference on USENIX Security Symposium - Volume 12 (SSYM'03), Vol. 12. USENIX Association, Berkeley, CA, USA, 3-3.
18. Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). "SipHash: a fast short-input PRF" (PDF).
19. Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (12 November 2014). "The Power of Evil Choices in Bloom Filters" . INRIA Grenoble.

• "Meaningful Collisions", attack scenarios for exploiting cryptographic hash collisions
• Fast MD5 and MD4 Collision Generators Piskopos Fox (eskiden Stach & Liu). Orijinal olarak Xiaoyun Wang tarafından geliştirilen teknikleri geliştiren çığır açan yeni kodu kullanarak MD4 ve MD5 karma çarpışmaları oluşturun. 1,6 GHz Pentium 4 kullanılarak, ortalama 45 dakikada MD5 çarpışmaları ve ortalama 5 saniyede MD4 çarpışmaları oluşturulabilir. Orijinal olarak 22 Haziran 2006'da yayınlandı.