← Bloq

Öz MD5 hash-ini göstərən PNG: The Arma Of Efe hashquine

Öz MD5 hash-ini öz piksellərində yazan PNG-ni hazır şablon istifadə etmədən necə yaratdıq? MD5, toqquşma açarları, PNG təbəqələri və RTX 5070 ilə efe23…23efe axtarışı, interaktiv izahla.

Yuxarıdakı şəkil sadə loqo deyil. Sağdakı qövsün üzərində yuxarıdan aşağıya efe235ae1b88c53e73d1c11515623efe yazılıb və bu, faylın öz MD5 hash-idir. Şəkli yükləyib md5sum komandasını işə salsanız eyni 32 rəqəmi görərsiniz.

Belə fayllara hashquine deyilir. İnternetdə məşhur nümunə retr0id-in əjdahalı PNG-sidir və çoxları o hazır şablondan istifadə edir. Biz heç bir şablon istifadə etmədən, öz loqomuzla (The Arma Of Efe), öz blog keçidimizlə və efe ilə başlayıb efe ilə bitən xüsusi bir hash ilə sıfırdan yaratdıq. Aşağıda addım-addım, sınaqlarla izah edirəm.

Retr0id-in öz MD5 xülasəsini göstərən əjdahalı PNG hashquine-i

David “Retr0id” Buchanan-ın PNG hashquine-i, MD5: 1337e2ef42b9bee8de06a4d223a51337. Şəkil: Retr0id, corkami/collisions vasitəsilə.

Hash nədir və niyə hər hərfdə dəyişir?

Bir hash (heş), faylın məzmunundan çıxan sabit uzunluqlu barmaq izidir. MD5 1991-ci ildə Ronald Rivest tərəfindən hazırlanmış hash funksiyasıdır: giriş 1 bayt da olsa, 50 GB da olsa, çıxış həmişə 128 bit, yəni 0-9 və a-f simvollarından ibarət 32 rəqəm olur.

Hash funksiyalarının əsas xüsusiyyəti lavina effektidir: girişdəki ən kiçik dəyişiklik çıxışı baştan-başa dəyişdirir. Aşağıya nəsə yazmağa çalışın:

Toyuq-yumurta problemi

Lavina effekti üzündən, öz MD5-ini üzərində daşıyan şəkil ilk baxışda qeyri-mümkün görünür:

  1. Şəkli çəkir və onun MD5-ini alırsınız, məsələn 4a8c91e0….
  2. Bu kodu şəklin üzərinə yazır və saxlayırsınız.
  3. Piksellər dəyişdiyi üçün faylın MD5-i artıq başqa bir şeydir, məsələn 9f02d71a….
  4. Yeni kodu yazırsınız və hash yenə dəyişir.

Bu dövrü qırmaq üçün MD5-in daxilinə baxmaq lazımdır.

Dövrü qıran ideya: MD5-i dəyişməyən açarlar

MD5 faylı bir dəfəyə emal etmir. Faylı 64 baytlıq bloklara bölür və ardıcıl emal edir: başlanğıc vəziyyət (IV) ilk blokla qarışır və aralıq vəziyyət (IHV) alınır. Bu aralıq vəziyyət növbəti blokla qarışır və fayl bitənə qədər belə davam edir. Son aralıq vəziyyət 32 rəqəmli MD5-in özüdür.

Əsas məqam budur: 64 bayt sərhədinə düzülmüş, 128 baytlıq iki fərqli məlumat parçası (A və B) mövcud ola bilər ki, hər ikisi eyni aralıq vəziyyətə çıxır. Buna eyni prefiksli toqquşma deyilir və FastColl kimi alətlər bunu qısa müddətdə yaradır. Bu parçadan sonrakı hər blok eyni aralıq vəziyyəti gördüyü üçün:

  • A parçası qoyulanda ekranda xətt parçası görünür, B qoyulanda görünmür,
  • amma faylın sonundakı MD5 heç dəyişmir.

Yəni hər toqquşma cütü MD5-i pozmadan açılıb-bağlanan bir açardır. Əvvəlcə faylın MD5-i hesablanır, sonra açarlar məhz o hash-i çəkəcək şəkildə tənzimlənir. Hash dəyişmədiyi üçün dövr qırılır.

Qövs hərf-hərf necə çəkildi?

Faylımızda 32 simvol loqodakı qövsü izləyən bir qövs üzərində yuxarıdan aşağıya düzülüb. Hər simvol yeddi seqmentli bir rəqəmdir və hər seqmenti ayrı bir açar çəkir: cəmi 224 açar. Sürüşdürücü ilə hash-in qövsə necə yerləşdiyini izləyə bilərsiniz:

Hazır şablon istifadə etmədiyimiz üçün PNG-nin dörd doğrulama təbəqəsini eyni anda keçməli olduq:

  1. 64 baytlıq düzləmə: Hər açar faylda tam ofset % 64 == 0 sərhədinə oturmalıdır. DEFLATE sıxışdırma axınına sıfır uzunluqlu boş bloklar əlavə edərək hər açarı bu sərhədə düzlədik.
  2. PNG Sub və Up filtrləri: Palitranın 0..254 indekslərini qara, yalnız 255 indeksini ağ etdik. Bir toqquşma cütünün iki parçası bir neçə baytın ən yuxarı bitində ayrılır. Sub filtrli sətirdə bu fərq sonrakı pikselləri 128 sürüşdürür və üfüqi xəttə çevrilir; Up filtrli sətirlər onu aşağı daşıyır. Açardan sonrakı baytları elə seçdik ki, xətt bir halda tam 255 (ağ), digərində qara olsun.
  3. Zlib Adler-32 tarazlaması: Sıxılmış məlumat açılarkən Adler-32 yoxlama cəmindən keçir və hər açar bu cəmi bir neçə yüz vahid yerindən oynadır. Qara sətirlərə 160 tarazlama açarı yerləşdirdik; cəmi tam geri qaytaran alt çoxluğu dinamik proqramlaşdırma və ortada görüşmə axtarışı ilə seçdik.
  4. IDAT CRC-32 yoxlaması: Hər IDAT yığınının sonunda 32 bitlik bir CRC-32 var. Sıxılmış axının dərhal arxasına 40 əlavə blok qoyduq və GF(2) üzərində xətti tənliklər sistemini Qauss eliminasiyası ilə həll edərək CRC-32 dəyərini 0x1807EFE0-a sabitlədik.

Xüsusi hash: hər rəqəm işi 16 dəfə artırır

Faylın öz MD5-ini göstərməsi kifayət etmədi; hash-in efe ilə başlayıb efe ilə bitməsini istədik. Bunun üçün faylın sonundakı 64 baytlıq nonce blokunu dəyişdirərək milyardlarla hash sınadıq.

Hər rəqəm 16 fərqli dəyər ala bildiyi üçün, sabitlənən hər yeni rəqəm orta sınaq sayını 16 dəfə artırır: N sabit rəqəm üçün orta hesabla 16^N sınaq lazımdır. 24 nüvəli prosessorda sadə bir C döngüsü saniyədə 177 milyon MD5 sınayır. Eyni işi RTX 5070 dizüstü qrafik kartında OpenCL ilə etdirdikdə sürət saniyədə 3,54 milyarda çatdı, yəni təxminən 20 dəfə artdı. efe23…23efe üçün orta hesabla 1,1 trilyon sınaq lazımdır; bizimki 90 milyardıncı sınaqda, təxminən 25 saniyəyə tapıldı.

Sürüşdürücü ilə rəqəm sayını dəyişin; həqiqətən tapdığımız nəticələr işarələnmiş nöqtələrdə görünür:

Özünüz yoxlayın

Şəkli yükləyin və terminalda işə salın. Windows-da certutil -hashfile dosya.png MD5, macOS-da md5 dosya.png komandasından istifadə edə bilərsiniz:

$ 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

Çıxışdakı 32 rəqəm, qövsün üzərində yuxarıdan aşağıya yazılan kodla tam eynidir.

Şəkli yaradan kodun tamamı GitHub-dadır: the-arma-of-owl/the-arma-of-efe-hashquine. Toqquşma skeleti də depoda olduğu üçün öz nonce dəyərinizlə yeni bir hashquine yarada bilərsiniz.

Mənbələr: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗