डच शोधकर्ता मार्क स्टीवंस ने एमडी 5 (
पीडीएफ ) पर एक सफल हमले
के विवरण का
अनावरण किया है और एकल 512-बिट डेटा ब्लॉक के भीतर टकराव को देखने के लिए एक C ++ प्रोग्राम रखा है।
विंडोज प्रोग्रामजल्द ही सूत्र
यहां दिखाई देंगे।
टकराव का उदाहरण
संदेश 1
4d c9 68 ff 0e e3 5c 20 95 72 d4 77 7b 72 15 87
d3 6f a7 b2 1b dc 56 b7 4a 3 डी c0 78 3e 7b 95 18
af bf a2 [00] a8 28 4b f3 6e 8e 4b 55 b3 5f 42 75
93 d8 49 67 6d a0 d1 [55] 5d 83 60 fb 5f 07 fe a2
संदेश 2
4d c9 68 ff 0e e3 5c 20 95 72 d4 77 7b 72 15 87
d3 6f a7 b2 1b dc 56 b7 4a 3 डी c0 78 3e 7b 95 18
af bf a2 [02] a8 28 4b f3 6e 8e 4b 55 b3 5f 42 75
93 d8 49 67 6d a0 d1 [d5] 5d 83 60 fb 5f 07 fe a2
एमडी 5 आम हैश
008ee33a9d58b51cfeb425b0959121c9
इन संदेशों के लिए SHA1 हैश:
> sha1sum message1.bin message2.bin
c6b384c4968b28812b676b49d40c09f8af4ed4cc4.11.bin
c728d8d93091e9c7b87b43d9e33829379231d7ca new2.bin
Core2 Q9550 प्रोसेसर पर, तीन हफ्तों में एक टक्कर मिली। मार्क स्टीवंस के अनुसार, अनुमानित समय लगभग पांच सप्ताह है। यह संभव है कि GPU पर CUDA का उपयोग करते समय, इस समस्या को घंटों में हल किया जा सकता है। लेखक का कहना है कि कार्यक्रम को समानांतर बनाना आसान है।
एमडी 5 में टकराव का पता लगाने के शास्त्रीय तरीके 2004 से प्रकाशित किए गए हैं, उनमें से कुछ को 2 10 तक की न्यूनतम जटिलता की आवश्यकता होती है, अर्थात, उन्हें एक नियमित होम पीसी पर एक सेकंड में किया जा सकता है, लेकिन व्यवहार में इन तरीकों का बहुत कम महत्व था, क्योंकि शास्त्रीय तरीके केवल खोज पर केंद्रित थे समान हैश (समान-उपसर्ग टकराव के हमले) वाले विभिन्न दस्तावेज़। ये दूसरी तरह के तथाकथित टकराव हैं।
हैश फ़ंक्शंस पर एक विशेष प्रकार का हमला चुना-उपसर्ग के हमलों को चुना जाता है, जब एक हमलावर दो यादृच्छिक दस्तावेज लेता है और यह दिखा सकता है कि वांछित हैश फ़ंक्शन को प्राप्त करने के लिए बिट्स को एक दस्तावेज़ में बदलना होगा। ये पहली तरह के टकराव हैं: किसी दिए गए संदेश M के लिए, दूसरे संदेश N का चयन करना संभव हो जाता है जिसके लिए H (N) = H (M) होता है। एमडी 5 पर इस तरह का हमला पहली बार 2007 में किया गया था, टकराव खोज की जटिलता एमडी 5 कॉमेडी फ़ंक्शन के बारे में 2,550 कॉल थी। तब से, एल्गोरिदम ने 2,339 कॉलों में तेजी ला दी है, और 2009 में शोधकर्ताओं के एक समूह ने चुने हुए-उपसर्ग टकरावों का प्रदर्शन किया , जिसमें केवल 596 बिट्स की आवश्यकता थी और 2,353.2 कॉल की कम्प्यूटेशनल जटिलता के साथ। उसके बाद, एमडी 5 की कमजोरी सभी के लिए स्पष्ट हो गई, और यहां तक कि इस पद्धति का उपयोग करके नकली प्रमाणन प्राधिकरण स्तर के प्रमाण पत्र भी बनाए गए।
जैसा कि मार्क स्टीवंस बताते हैं, 2010 में, चीनी शोधकर्ताओं ने पहली बार एकल 512-बिट एमडी 5 ब्लॉकों के लिए समान-उपसर्ग टकराव का प्रदर्शन किया, लेकिन उन्होंने "सुरक्षा कारणों से" उनके एल्गोरिथ्म का विवरण नहीं दिया। इसके बजाय, उन्होंने एमडी 5 के लिए इस हमले को दोहराने के लिए क्रिप्टोग्राफर्स के बीच एक तरह की प्रतियोगिता की घोषणा की। मार्क स्टीवंस का काम इस "प्रतियोगिता" को जीतने का दावा करता है। यह हमला हैश गणना (एमडी 5 चार राउंड में काम करता है) के पहले दौर में विकल्पों की एक छोटी संख्या के आधार पर एक नई टक्कर खोज एल्गोरिथ्म पर आधारित है, और मार्क स्टीवंस विधि पहले की खोज की गई सुरंग तकनीकों का उपयोग करती है। स्टीवंस के अनुसार, इसके एल्गोरिथ्म के अनुसार एक 512-बिट ब्लॉक में टकराव की खोज की जटिलता MD5Compress फ़ंक्शन के 2 49.81 कॉल पर अनुमानित है।