← Blog

Kendi MD5 özetini gösteren PNG: The Arma Of Efe hashquine

Kendi MD5 özetini kendi piksellerinde yazan bir PNG'yi hazır şablon kullanmadan nasıl ürettik? MD5, çakışma anahtarları, PNG katmanları ve RTX 5070 ile efe23…23efe araması, etkileşimli anlatımla.

Yukarıdaki görsel sıradan bir logo değil. Sağdaki kavisin üzerinde yukarıdan aşağıya efe235ae1b88c53e73d1c11515623efe yazıyor ve bu, dosyanın kendi MD5 özeti. Görseli indirip md5sum çalıştırırsanız aynı 32 haneyi görürsünüz.

Böyle dosyalara hashquine denir. İnternette dolaşan ünlü örnek, retr0id’in ejderhalı PNG’sidir ve çoğu kişi o hazır şablonu kullanır. Biz hiçbir şablon kullanmadan, kendi logomuzla (The Arma Of Efe), kendi blog bağlantımızla ve efe ile başlayıp efe ile biten özel bir özetle sıfırdan ürettik. Aşağıda adım adım, deneyerek anlatıyorum.

Retr0id’in kendi MD5 özetini gösteren ejderhalı PNG hashquine’i

David “Retr0id” Buchanan’ın PNG hashquine’i, MD5’i 1337e2ef42b9bee8de06a4d223a51337. Görsel: Retr0id, corkami/collisions üzerinden.

Hash nedir ve neden her harfte değişir?

Bir hash (özet), dosyanın içeriğinden çıkan sabit uzunlukta bir parmak izidir. MD5, 1991’de Ronald Rivest’in tasarladığı bir özet fonksiyonudur: girdi 1 bayt da olsa 50 GB da olsa çıktı her zaman 128 bit, yani 0-9 ve a-f karakterlerinden oluşan 32 hane olur.

Özet fonksiyonlarının temel özelliği çığ etkisidir: girdideki en küçük değişiklik çıktıyı baştan sona değiştirir. Aşağıya bir şeyler yazmayı deneyin:

Tavuk-yumurta sorunu

Çığ etkisi yüzünden, kendi MD5’ini üzerinde taşıyan bir resim ilk bakışta imkânsız görünür:

  1. Resmi çizer ve MD5’ini alırsınız, örneğin 4a8c91e0….
  2. Bu kodu resmin üzerine yazıp kaydedersiniz.
  3. Pikseller değiştiği için dosyanın MD5’i artık başka bir şeydir, örneğin 9f02d71a….
  4. Yeni kodu yazarsınız ve özet yine değişir.

Bu döngüyü kırmak için MD5’in içine bakmak gerekiyor.

Döngüyü kıran fikir: MD5’i değiştirmeyen anahtarlar

MD5 dosyayı tek seferde işlemez. Dosyayı 64 baytlık bloklara böler ve sırayla işler: başlangıç durumu (IV) ilk blokla karışır ve bir ara durum (IHV) çıkar. Bu ara durum bir sonraki blokla karışır ve dosya bitene kadar böyle devam eder. Son ara durum, 32 haneli MD5’in kendisidir.

Kritik nokta şu: 64 bayt sınırına hizalanmış, 128 baytlık iki farklı veri parçası (A ve B) bulunabilir ki ikisi de aynı ara duruma çıkar. Buna aynı önekli çakışma denir ve FastColl gibi araçlar bunu kısa sürede üretir. Bu parçadan sonraki her blok aynı ara durumu gördüğü için:

  • A parçası konursa ekranda bir çizgi parçası görünür, B konursa görünmez,
  • ama dosyanın sonundaki MD5 hiç değişmez.

Yani her çakışma çifti, MD5’i bozmadan açılıp kapanan bir anahtardır. Önce dosyanın MD5’i hesaplanır, sonra anahtarlar tam o özeti çizecek şekilde ayarlanır. Özet değişmediği için döngü kırılır.

Kavis harf harf nasıl çizildi?

Dosyamızda 32 karakter, logodaki yayı takip eden bir kavis üzerinde yukarıdan aşağıya dizili. Her karakter yedi segmentli bir rakam ve her segmenti ayrı bir anahtar çiziyor: toplam 224 anahtar. Kaydırıcıyla özetin kavise nasıl yerleştiğini izleyebilirsiniz:

Hazır şablon kullanmadığımız için PNG’nin dört doğrulama katmanını aynı anda geçmemiz gerekti:

  1. 64 baytlık hizalama: Her anahtar dosyada tam ofset % 64 == 0 sınırına oturmalı. DEFLATE sıkıştırma akışına sıfır uzunluklu boş bloklar ekleyerek her anahtarı bu sınıra hizaladık.
  2. PNG Sub ve Up filtreleri: Paletin 0..254 indekslerini siyah, yalnızca 255 indeksini beyaz yaptık. Bir çakışma çiftinin iki parçası birkaç baytın en üst bitinde ayrışır. Sub filtreli satırda bu fark ardından gelen pikselleri 128 kaydırır ve yatay bir çizgiye dönüşür; Up filtreli satırlar onu aşağı taşır. Anahtardan sonraki baytları, çizgi bir durumda tam 255 (beyaz), diğerinde siyah olacak şekilde seçtik.
  3. Zlib Adler-32 dengelemesi: Sıkıştırılmış veri açılırken Adler-32 sağlama toplamından geçer ve her anahtar bu toplamı birkaç yüz birim oynatır. Siyah satırlara 160 dengeleme anahtarı yerleştirdik; toplamı tam olarak geri getiren alt kümeyi dinamik programlama ve ortada buluşma aramasıyla seçtik.
  4. IDAT CRC-32 doğrulaması: Her IDAT yığınının sonunda 32 bitlik bir CRC-32 vardır. Sıkıştırılmış akışın hemen ardına 40 ek blok koyduk ve GF(2) üzerinde bir doğrusal denklem sistemini Gauss eliminasyonuyla çözerek CRC-32 değerini 0x1807EFE0 olarak sabitledik.

Özel özet: her hane işi 16 katına çıkarır

Dosyanın kendi MD5’ini göstermesi yetmedi; özetin efe ile başlayıp efe ile bitmesini istedik. Bunun için dosyanın sonundaki 64 baytlık bir nonce bloğunu değiştirerek milyarlarca özet denedik.

Her hane 16 farklı değer alabildiği için, sabitlenen her yeni hane ortalama deneme sayısını 16 katına çıkarır: N sabit hane için ortalama 16^N deneme gerekir. 24 çekirdekli işlemcide basit bir C döngüsü saniyede 177 milyon MD5 deniyor. Aynı işi RTX 5070 dizüstü ekran kartında OpenCL ile yaptırınca hız saniyede 3,54 milyara, yani yaklaşık 20 katına çıktı. efe23…23efe için ortalama 1,1 trilyon deneme gerekir; bizimki 90 milyarıncı denemede, yaklaşık 25 saniyede çıktı.

Kaydırıcıyla hane sayısını değiştirin; gerçekten bulduğumuz sonuçlar işaretli noktalarda görünüyor:

Kendiniz doğrulayın

Görseli indirin ve terminalde çalıştırın. Windows’ta certutil -hashfile dosya.png MD5, macOS’ta md5 dosya.png komutunu kullanabilirsiniz:

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

Çıktıdaki 32 hane, kavisin üzerinde yukarıdan aşağıya yazan kodla birebir aynıdır.

Görseli üreten kodun tamamı GitHub’da: the-arma-of-owl/the-arma-of-efe-hashquine. Çakışma iskeleti de depoda olduğu için kendi nonce değerinizle yeni bir hashquine üretebilirsiniz.

Kaynaklar: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗