संघट्टन प्रतिरोध

क्रिप्टोग्राफी में, कोलीजन रेजिस्टेंस क्रिप्टोग्राफ़िक हैश फ़ंक्शंस की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।

बर्थडे पैराडॉक्स कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2^N/2 (या $\scriptstyle {\sqrt {2^{N}}}$) की गणना करता है और रैंडम इनपुट पर हैश ऑपरेशन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि ब्रूट-फ़ोर्स अटैक की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे सामान्यतः हैश फ़ंक्शन में दोष माना जाता है।

क्रिप्टोग्राफ़िक हैश फ़ंक्शन सामान्यतः कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से एमडी5 और एसएचए-1 दोनों ने कोलीजन का पता लगाने के लिए ब्रूट-फ़ोर्स की तुलना में अधिक कुशल तकनीकें पब्लिश की हैं। हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रूफ है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय प्रॉब्लम (जैसे इन्टिजर फेक्टराइज़ेशन या डिस्क्रीट लोगारिथ्म) जितना कठिन है। उन फ़ंक्शंस को प्रूवेबली सिक्योर कहा जाता है।

परिभाषा

फंक्शन {h_k : {0, 1}^m(k) → {0, 1}^l(k)} का समूह कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक समूह है, यदि |m(k)| > |l(k)| किसी भी k के लिए, अर्थात, h_k इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक h_k k दिए गए पोलीनोमिअल टाइम के भीतर गणना की जा सकती है, लेकिन किसी भी प्रोबबिलिस्टिक पोलीनोमिअल एल्गोरिथ्म ए के लिए, हमारे पास निम्न हैं

Pr [k ← G(1ⁿ), (x₁, x₂) ← A(k, 1ⁿ) s.t. x₁ ≠ x₂ but h_k(x₁) = h_k(x₂)] < negl(n),

जहां negl(·) कुछ नेग्लिजिबल फ़ंक्शन को दर्शाता है, और n सिक्योरिटी पैरामीटर है।

रैशनल

कोलीजन रेजिस्टेंस कई कारणों से डिज़ायरेबल है।

• कुछ डिजिटल सिग्नेचर सिस्टम में, एक पार्टी डॉक्यूमेंट के हैश पर पब्लिक की सिग्नेचर पब्लिश करके डॉक्यूमेंट को अटेस्ट करता है। यदि एक ही हैश के साथ दो डॉक्यूमेंट तैयार करना संभव है, तो एक अटैकर एक पार्टी से एक को अटेस्ट करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को अटेस्ट कर दिया है।
• कुछ डिस्ट्रिब्यूटेड कंटेंट सिस्टम में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश को कमपेअर करती हैं कि उनका वर्ज़न समान है। अटैकर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, यूजर को यह भरोसा दिला सकता है कि उनके पास फ़ाइल का एक ही वर्ज़न है जबकि वास्तव में ऐसा नहीं था।

यह भी देखें

• कोलीजन अटैक
• प्रीइमेज अटैक
• एनआईएसटी हैश फ़ंक्शन कॉम्पटीशन
• प्रूवेबली सिक्योर क्रिप्टोग्राफ़िक हैश फ़ंक्शन
• एरर डिटेक्शन एंड करेक्शन