← ब्लॉग

अपना MD5 हैश दिखाने वाली PNG: The Arma Of Efe hashquine

हमने बिना किसी तैयार टेम्पलेट के, अपना MD5 हैश अपने ही पिक्सेलों में लिखने वाली PNG कैसे बनाई? MD5, टकराव (collision) कुंजियाँ, PNG की परतें और RTX 5070 के साथ efe23…23efe की खोज, एक इंटरैक्टिव व्याख्या में।

ऊपर का चित्र कोई साधारण लोगो नहीं है। दाईं ओर के मोड़ पर ऊपर से नीचे की ओर efe235ae1b88c53e73d1c11515623efe लिखा है, और यह फ़ाइल का अपना MD5 हैश है। चित्र डाउनलोड करके md5sum चलाएँ, तो वही 32 अक्षर दिखेंगे।

ऐसी फ़ाइलों को hashquine कहते हैं। इंटरनेट पर घूमता मशहूर उदाहरण retr0id का ड्रैगन वाला PNG है, और ज़्यादातर लोग वही तैयार टेम्पलेट इस्तेमाल करते हैं। हमने बिना किसी टेम्पलेट के, अपने लोगो (The Arma Of Efe) और अपने ब्लॉग लिंक के साथ, तथा efe से शुरू होकर efe पर खत्म होने वाले एक खास हैश के साथ, शुरू से बनाया। नीचे इसे चरण-दर-चरण, प्रयोग करते हुए समझाया गया है।

Retr0id का ड्रैगन वाला PNG hashquine, जो अपना ही MD5 दिखाता है

David “Retr0id” Buchanan का PNG hashquine, MD5 1337e2ef42b9bee8de06a4d223a51337। चित्र: Retr0id, corkami/collisions के माध्यम से।

हैश क्या है, और हर अक्षर पर क्यों बदलता है?

हैश (digest) फ़ाइल की सामग्री से निकलने वाली एक निश्चित लंबाई की पहचान (fingerprint) है। MD5 1991 में Ronald Rivest द्वारा डिज़ाइन किया गया एक हैश फ़ंक्शन है: इनपुट चाहे 1 बाइट हो या 50 GB, आउटपुट हमेशा 128 बिट होता है, यानी 0-9 और a-f अक्षरों से बने 32 अक्षर।

हैश फ़ंक्शनों की मूल विशेषता हिमस्खलन प्रभाव (avalanche effect) है: इनपुट में सबसे छोटा बदलाव भी आउटपुट को शुरू से आखिर तक बदल देता है। नीचे कुछ लिखकर देखें:

मुर्गी-अंडे की समस्या

हिमस्खलन प्रभाव के कारण, अपना MD5 अपने ऊपर लिखे चित्र का पहली नज़र में असंभव लगता है:

  1. चित्र बनाकर उसका MD5 निकाला जाता है, जैसे 4a8c91e0…।
  2. यह कोड चित्र पर लिखकर फ़ाइल सेव कर दी जाती है।
  3. पिक्सेल बदल गए, इसलिए फ़ाइल का MD5 अब कुछ और है, जैसे 9f02d71a…।
  4. नया कोड लिखा जाता है, और हैश फिर बदल जाता है।

इस चक्र को तोड़ने के लिए MD5 के भीतर झाँकना ज़रूरी है।

चक्र तोड़ने वाला विचार: ऐसी कुंजियाँ जो MD5 नहीं बदलतीं

MD5 फ़ाइल को एक साथ प्रोसेस नहीं करता। वह फ़ाइल को 64 बाइट के ब्लॉकों में बाँटता है और क्रम से प्रोसेस करता है: प्रारंभिक स्थिति (IV) पहले ब्लॉक से मिलकर एक मध्यवर्ती स्थिति (IHV) बनाती है। यह मध्यवर्ती स्थिति अगले ब्लॉक से मिलती है, और फ़ाइल खत्म होने तक यही चलता रहता है। आखिरी मध्यवर्ती स्थिति ही 32 अक्षरों वाला MD5 है।

अहम बात यह है कि 64 बाइट की सीमा पर सटीक बैठने वाले, 128 बाइट के दो अलग डेटा हिस्से (A और B) मिल सकते हैं जो दोनों एक ही मध्यवर्ती स्थिति तक पहुँचते हैं। इसे समान-उपसर्ग टकराव कहते हैं, और FastColl जैसे टूल इसे थोड़े समय में बना देते हैं। चूँकि इस हिस्से के बाद हर ब्लॉक एक ही मध्यवर्ती स्थिति देखता है:

  • A हिस्सा रखा जाए तो स्क्रीन पर एक रेखा-खंड दिखता है, B रखा जाए तो वह नहीं दिखता,
  • पर फ़ाइल के अंत का MD5 बिल्कुल नहीं बदलता।

यानी हर टकराव-जोड़ी एक कुंजी है, जो MD5 को बिगाड़े बिना खुलती और बंद होती है। पहले फ़ाइल का MD5 निकाला जाता है, फिर कुंजियों को ठीक उसी हैश को बनाने के लिए सेट किया जाता है। हैश नहीं बदलता, इसलिए चक्र टूट जाता है।

मोड़ को अक्षर-दर-अक्षर कैसे बनाया गया?

हमारी फ़ाइल में 32 अक्षर लोगो के मोड़ का अनुसरण करते हुए ऊपर से नीचे व्यवस्थित हैं। हर अक्षर एक सात-खंडीय (seven-segment) अंक है और हर खंड अपनी अलग कुंजी से बनाया गया है; कुल 224 कुंजियाँ। स्लाइडर से देखा जा सकता है कि हैश मोड़ पर कैसे बैठता है:

चूँकि हमने कोई तैयार टेम्पलेट इस्तेमाल नहीं किया, PNG की चार सत्यापन परतों को एक साथ पार करना ज़रूरी था:

  1. 64 बाइट संरेखण: हर कुंजी फ़ाइल में ठीक ऑफ़सेट % 64 == 0 की सीमा पर बैठनी चाहिए। DEFLATE संपीड़न धारा में शून्य-लंबाई वाले खाली ब्लॉक जोड़कर हमने हर कुंजी को इस सीमा पर संरेखित किया।
  2. PNG Sub और Up फ़िल्टर: पैलेट के 0..254 सूचकांक काले, और केवल 255 सूचकांक सफ़ेद रखा गया। एक टकराव-जोड़ी के दोनों हिस्से कुछ बाइटों के सबसे ऊँचे बिट में अलग होते हैं। Sub फ़िल्टर वाली पंक्ति में यह अंतर बाद के पिक्सेलों को 128 खिसकाता है और एक क्षैतिज रेखा बन जाता है; Up फ़िल्टर वाली पंक्तियाँ उसे नीचे ले जाती हैं। कुंजी के बाद के बाइट इस तरह चुने गए कि एक स्थिति में रेखा ठीक 255 (सफ़ेद) हो और दूसरी में काली।
  3. Zlib Adler-32 संतुलन: संपीड़ित डेटा खुलते समय Adler-32 जाँच-योग से गुजरता है, और हर कुंजी इस योग को कुछ सौ इकाई हिला देती है। काली पंक्तियों में 160 संतुलन कुंजियाँ रखीं; योग को ठीक वापस लाने वाला उपसमूह डायनेमिक प्रोग्रामिंग और मध्य-मिलन (meet-in-the-middle) खोज से चुना।
  4. IDAT CRC-32 सत्यापन: हर IDAT खंड के अंत में 32 बिट का CRC-32 होता है। संपीड़ित धारा के ठीक बाद 40 अतिरिक्त ब्लॉक रखे, और GF(2) पर एक रैखिक समीकरण-प्रणाली को Gauss विलोपन से हल करके CRC-32 मान को 0x1807EFE0 पर स्थिर कर दिया।

विशेष हैश: हर अक्षर काम को 16 गुना बढ़ाता है

फ़ाइल का अपना MD5 दिखाना काफ़ी नहीं था; हमें चाहिए था कि हैश efe से शुरू हो और efe पर खत्म हो। इसके लिए फ़ाइल के अंत में 64 बाइट के nonce ब्लॉक को बदल-बदलकर अरबों हैश आज़माए गए।

हर अक्षर के 16 संभावित मान होने से, हर नया तय अक्षर औसत प्रयासों को 16 गुना बढ़ा देता है: N तय अक्षरों के लिए औसतन 16^N प्रयास चाहिए। 24 कोर वाले CPU पर एक सरल C लूप प्रति सेकंड 17.7 करोड़ MD5 आज़मा रहा है। वही काम RTX 5070 लैपटॉप ग्राफ़िक्स कार्ड पर OpenCL से करवाने पर गति प्रति सेकंड 3.54 अरब हो गई, यानी लगभग 20 गुना। efe23…23efe के लिए औसतन 1.1 खरब प्रयास चाहिए; हमारा 90 अरबवें प्रयास पर, लगभग 25 सेकंड में मिला।

स्लाइडर से अक्षरों की संख्या बदलें; जो परिणाम हमें सचमुच मिले, वे चिह्नित बिंदुओं पर दिखते हैं:

स्वयं सत्यापित करें

चित्र डाउनलोड करें और टर्मिनल में चलाएँ। Windows पर certutil -hashfile dosya.png MD5 और macOS पर md5 dosya.png इस्तेमाल किया जा सकता है।

$ 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

आउटपुट के 32 अक्षर, मोड़ पर ऊपर से नीचे लिखे कोड से हूबहू मेल खाते हैं।

चित्र बनाने वाला पूरा कोड GitHub पर है: the-arma-of-owl/the-arma-of-efe-hashquine। टकराव का ढाँचा भी रिपॉज़िटरी में है, इसलिए आप अपने nonce मान से नया hashquine बना सकते हैं।

स्रोत: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗