Birthday और collision हमले

23 लोगों के समूह में, दो लोगों का जन्मदिन एक ही होने की प्रायिकता 50% से अधिक होती है। 70 लोगों पर यह 99.9% से अधिक हो जाती है। गणितीय रूप से, N आकार वाले समुच्चय में लगभग √N नमूनों के बाद टकराव की प्रायिकता 50% से अधिक हो जाती है। इसे जन्मदिन सीमा कहते हैं।

n-बिट हैश फलन के लिए, एक टकराव (H(m1) = H(m2), m1 ≠ m2) लगभग 2^{n/2} यादृच्छिक प्रयासों में पाया जा सकता है। SHA-256 (256-बिट) के लिए टकराव खोजने में लगभग 2^{128} कार्य लगता है—जो संगणनात्मक रूप से असंभव है। MD5 (128-बिट) के लिए लगभग 2^{64} कार्य लगता है—जो सीमित रूप से संभव है।

सामान्य टकराव-खोज: 2^{n/2} यादृच्छिक संदेश बनाएँ, उनके हैश निकालें, हैश मान के अनुसार क्रमबद्ध करें और डुप्लिकेट खोजें। मेमोरी O(2^{n/2}) होती है। Rho एल्गोरिदम (Floyd का चक्र-खोज) समान समय लागत पर मेमोरी को O(1) तक घटा देता है। van Oorschot-Wiener का समानांतर टकराव-खोज हार्डवेयर की सहायता से समय घटाता है।

Wang और सहकर्मियों ने 2004 में विभेदी क्रिप्टविश्लेषण का उपयोग करके व्यावहारिक MD5 टकराव खोजे—यह जन्मदिन आक्रमण नहीं था। अलग-अलग 1024-बिट संदेशों का समान MD5 हैश कुछ सेकंड में बनाया गया। Hertzbleed और चयनित-उपसर्ग टकराव प्रमाणपत्र टकराव संभव बनाते हैं। टकराव-प्रतिरोध के लिए MD5 पूरी तरह असुरक्षित है।

यह अधिक शक्तिशाली विधि है: दो मनमाने उपसर्ग P1 और P2 दिए होने पर, ऐसे प्रत्यय S1 और S2 खोजें कि H(P1||S1) = H(P2||S2) हो। Stevens और सहकर्मियों ने 2017 में चयनित-उपसर्ग MD5 टकराव खोजे। इसका उपयोग वैध MD5 हस्ताक्षर वाला दुर्भावनापूर्ण CA प्रमाणपत्र बनाने में किया गया। इसके बाद प्रमाणपत्रों में MD5 का उपयोग बंद कर दिया गया।

Google का SHAttered (2017) पहला व्यावहारिक SHA-1 टकराव था। दो अलग-अलग PDF फ़ाइलों का SHA-1 हैश समान था। इसके लिए 2^{63.1} SHA-1 संपीड़न आवश्यक थे—जो 6,500 CPU-वर्ष और 110 GPU-वर्ष के बराबर हैं। लागत लगभग 110,000 डॉलर थी। ब्राउज़रों ने 2017 में SHA-1 प्रमाणपत्रों का समर्थन समाप्त करना शुरू कर दिया।

Merkle-Damgard हैश फलनों (MD5, SHA-1, SHA-2) के लिए: यदि आपको H(m) ज्ञात है, तो m जाने बिना H(m||padding||m') की गणना की जा सकती है। इससे H(secret||message) जैसी MAC रचनाएँ असुरक्षित हो जाती हैं। समाधान: HMAC का उपयोग करें (जो आंतरिक और बाहरी पैडिंग का उपयोग करता है) या SHA-3 का उपयोग करें (स्पंज रचना, जो लंबाई-विस्तार से सुरक्षित है)।

टक्कर-प्रतिरोध: समान हैश वाले कोई भी दो अलग-अलग संदेश ढूँढ़ना (2^{n/2} प्रयास)। द्वितीय पूर्व-प्रतिबिंब प्रतिरोध: m दिए जाने पर उसी हैश वाला m' ≠ m ढूँढ़ना (2^n प्रयास)। पूर्व-प्रतिबिंब प्रतिरोध: दिए गए हैश के लिए कोई भी संदेश ढूँढ़ना (2^n प्रयास)। टक्कर-प्रतिरोध हमेशा सबसे कमजोर होता है।

यदि MAC में टक्करों के प्रति असुरक्षित हैश का उपयोग होता है, तो H में टक्कर ढूँढ़ सकने वाला आक्रमणकारी जाली MAC बना सकता है। HMAC-MD5 को MD5 की टक्करों के बावजूद सुरक्षित माना जाता है, क्योंकि HMAC की रचना के लिए केवल टक्कर नहीं, बल्कि पूर्व-प्रतिबिंब आक्रमण आवश्यक होते हैं। फिर भी, नई प्रणालियों के लिए HMAC-MD5 से हट जाएँ।

Joux (2004): Merkle-Damgard हैशों के लिए 2^k-मार्गीय टक्करें ढूँढ़ने में (समान हैश वाले 2^k संदेश) एक टक्कर ढूँढ़ने के काम का केवल k गुना काम लगता है, k अलग-अलग टक्करों जितना नहीं। इससे संयोजित हैशों की कमजोरियाँ बढ़ जाती हैं (H1(m)||H2(m) उतना मजबूत नहीं है जितना आप सोच सकते हैं)।

टक्कर-प्रतिरोधी हैशिंग के लिए SHA-256 या SHA-3 का उपयोग करें। किसी भी सुरक्षा उद्देश्य के लिए MD5 और SHA-1 से बचें। MAC के लिए HMAC-SHA-256 या HMAC-SHA-3 का उपयोग करें। पासवर्ड हैशिंग के लिए Argon2 का उपयोग करें, सीधे SHA-2 का नहीं। जब लंबाई-विस्तार से सुरक्षा आवश्यक हो, तब हमेशा SHA-3 का उपयोग करें।

जन्मदिन आक्रमण में 2^{n/2} प्रयासों में हैश टक्कर मिल जाती है। MD5 में चुने हुए उपसर्ग वाली व्यावहारिक टक्करें संभव हैं; 2017 में SHA-1 को तोड़ दिया गया था। लंबाई-विस्तार आक्रमण सरल H(key||msg) MAC को तोड़ देते हैं। SHA-256 या SHA-3 का उपयोग करें और संदेश प्रमाणीकरण के लिए HMAC का उपयोग करें। अगला विषय: बीच में मिलान वाले आक्रमण।