MD5CRK

क्रिप्टोग्राफी में, MD5CRK जीन-ल्यूक कुक और उनकी कंपनी, सर्टेनके क्रिप्टोसिस्टम्स द्वारा लॉन्च किया गया एक स्वैच्छिक कंप्यूटिंग प्रयास (वितरित.net के समान) था, यह प्रदर्शित करने के लिए कि MD5 संदेश संग्रह कलन विधि एक हैश टक्कर खोजने से असुरक्षित है – दो संदेश जो समान MD5 हैश उत्पन्न करते हैं। यह परियोजना 1 मार्च, 2004 को शुरू हुई थी। शोधकर्ताओं द्वारा स्वतंत्र रूप से एमडी5 में टक्कर उत्पन्न करने के लिए एक तकनीक का प्रदर्शन करने के बाद परियोजना 24 अगस्त, 2004 को समाप्त हो गई थी। सर्टेनकी ने वांग, फेंग, लाई और यू को उनकी खोज के लिए 10,000 कनाडाई डॉलर का पुरस्कार दिया।

पोलार्ड की रो टक्कर एक ही रास्ता खोजती है

MD5 के लिए टक्कर खोजने की कोशिश करने के लिए फ्लोयड के चक्र-खोज एल्गोरिदम नामक तकनीक का उपयोग किया गया था। एल्गोरिदम को यादृच्छिक चलने के साथ सादृश्य द्वारा वर्णित किया जा सकता है। इस सिद्धांत का उपयोग करते हुए कि फीडबैक लूप में रखे गए संभावित आउटपुट की एक सीमित संख्या के साथ कोई भी फ़ंक्शन चक्र करेगा, विशेष संरचनाओं के साथ आउटपुट को स्टोर करने के लिए अपेक्षाकृत कम मात्रा में मेमोरी का उपयोग कर सकता है और मार्कर के पारित होने पर बेहतर पता लगाने के लिए मार्कर के रूप में उनका उपयोग कर सकता है। पहले। इन मार्करों को विशिष्ट बिंदु कहा जाता है, जिस बिंदु पर दो इनपुट एक ही आउटपुट उत्पन्न करते हैं उसे टक्कर बिंदु कहा जाता है। MD5CRK ने किसी भी बिंदु पर विचार किया जिसके पहले 32 अंश शून्य थे एक विशिष्ट बिंदु।

जटिलता

टकराव खोजने के लिए अपेक्षित समय के बराबर नहीं है $2^{N}$ कहाँ $N$ डाइजेस्ट आउटपुट में बिट्स की संख्या है। यह वास्तव में है $2^{N}! \over {(2^{N}-K)!\times {2^{N}}^{K}}$, कहाँ $K$ एकत्र किए गए फ़ंक्शन आउटपुट की संख्या है।

इस परियोजना के लिए, के बाद सफलता की संभावना $K$ MD5 संगणनाओं का अनुमान लगाया जा सकता है: $1 \over {1-e^{K\times (1-K) \over 2^{N+1}}}$.

128-बिट MD5 संदेश डाइजेस्ट फ़ंक्शन में टक्कर उत्पन्न करने के लिए आवश्यक संगणनाओं की अपेक्षित संख्या इस प्रकार है: ${1.17741\times 2^{N/2}}={1.17741\times 2^{64}}$ इसे कुछ परिप्रेक्ष्य देने के लिए, 12.25 टेराफ्लॉप्स के अधिकतम प्रदर्शन के साथ वर्जीनिया टेक के सिस्टम एक्स (सुपरकंप्यूटर) का उपयोग करने में लगभग समय लगेगा ${2.17\times 10^{19}/12.25\times 10^{12}\approx 1,770,000}$ सेकंड या लगभग 3 सप्ताह। या कमोडिटी प्रोसेसर के लिए 2 गीगाफ्लॉप पर लगभग समान समय में 6,000 मशीनें लगेंगी।

यह भी देखें

• स्वयंसेवी कंप्यूटिंग परियोजनाओं की सूची
• पशुबल का आक्रमण

संदर्भ

अग्रिम पठन

• Paul C. van Oorschot; Michael J. Wiener. Parallel Collision Search with Application to Hash Functions and Discrete Logarithms (PDF). ACM Conference on Computer and Communications Security 1994. pp. 210–218.