कोलाइसन अटैक: Difference between revisions

[[क्रिप्टोग्राफी]] में, [[क्रिप्टोग्राफ़िक हैश]] पर टकराव का हमला समान हैश मान उत्पन्न करने वाले दो इनपुट को खोजने की कोशिश करता है, यानी हैश टकराव। यह प्रीइमेज हमले के विपरीत है जहां एक विशिष्ट लक्ष्य हैश मान निर्दिष्ट किया जाता है।

टकराव के हमले मोटे तौर पर दो प्रकार के होते हैं:

;शास्त्रीय टकराव का हमला: दो अलग-अलग संदेश ''एम'' ढूंढें₁ और एम₂ ऐसा है कि हैश(एम₁) = हैश(एम₂).

आम तौर पर अधिक:

;चुना-उपसर्ग टकराव हमला: दो अलग-अलग उपसर्ग दिए गए पी₁ और पी₂, दो उपांग खोजें एम₁ और एम₂ ऐसे कि हैश(p₁ ∥ एम₁) = हैश(पी₂ ∥ एम₂), जहां ∥ संघनन संक्रिया को दर्शाता है।

==शास्त्रीय टक्कर आक्रमण==

गणितीय रूप से कहा गया है, एक टकराव के हमले में दो अलग-अलग संदेश एम 1 और एम 2 मिलते हैं, जैसे कि हैश (एम 1) = हैश (एम 2)। शास्त्रीय टकराव के हमले में, हमलावर का किसी भी संदेश की सामग्री पर कोई नियंत्रण नहीं होता है, लेकिन उन्हें एल्गोरिदम द्वारा मनमाने ढंग से चुना जाता है।

जैसे [[सममित-कुंजी सिफर]] क्रूर बल के हमलों के प्रति संवेदनशील होते हैं, वैसे ही प्रत्येक [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] जन्मदिन के हमले का उपयोग करके टकराव के लिए स्वाभाविक रूप से असुरक्षित होता है। [[जन्मदिन की समस्या]] के कारण, ये हमले किसी क्रूर बल की तुलना में कहीं अधिक तेज़ होते हैं। n बिट्स का एक हैश 2 में तोड़ा जा सकता है^n/2 समय चरण (हैश फ़ंक्शन का मूल्यांकन)।

विशिष्ट हैश फ़ंक्शंस में [[क्रिप्ट विश्लेषण]] को नियोजित करके अधिक कुशल हमले संभव हैं। जब टकराव के हमले का पता चलता है और जन्मदिन के हमले की तुलना में तेज़ पाया जाता है, तो हैश फ़ंक्शन को अक्सर टूटा हुआ घोषित किया जाता है। [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता]] मुख्य रूप से दो बहुत ही सामान्य रूप से उपयोग किए जाने वाले हैश फ़ंक्शन, [[एमडी5]] के विरुद्ध प्रकाशित टकराव हमलों से प्रेरित थी<ref name=md5-2004>Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: [http://eprint.iacr.org/2004/199 Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD], Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.</ref> और [[SHA-1]]. एमडी5 के विरुद्ध टकराव के हमलों में इतना सुधार हुआ है कि, 2007 तक, एक नियमित कंप्यूटर पर इसमें केवल कुछ सेकंड लगते हैं।<ref>{{cite journal |author=M.M.J. Stevens |date=June 2007 |title=On Collisions for MD5 |url=http://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf |quote=[...] we are able to find collisions for MD5 in about 2^24.1 compressions for recommended IHVs which takes approx. 6 seconds on a 2.6GHz Pentium 4. }}</ref> इस तरह से बनाए गए हैश टकराव आमतौर पर स्थिर लंबाई के होते हैं और काफी हद तक असंरचित होते हैं, इसलिए इन्हें व्यापक दस्तावेज़ प्रारूपों या प्रोटोकॉल पर हमला करने के लिए सीधे लागू नहीं किया जा सकता है।

हालाँकि, कई प्रारूपों में मौजूद गतिशील संरचनाओं का दुरुपयोग करके समाधान संभव है। इस तरह, दो दस्तावेज़ बनाए जाएंगे जो समान हैश मान रखने के लिए यथासंभव समान होंगे। एक दस्तावेज़ पर हस्ताक्षर करने के लिए प्राधिकारी को दिखाया जाएगा, और फिर हस्ताक्षर को दूसरी फ़ाइल में कॉपी किया जा सकता है। ऐसे दुर्भावनापूर्ण दस्तावेज़ में एक ही दस्तावेज़ में दो अलग-अलग संदेश होंगे, लेकिन फ़ाइल में सूक्ष्म परिवर्तनों के माध्यम से सशर्त रूप से एक या दूसरे को प्रदर्शित किया जाएगा:

* कुछ दस्तावेज़ प्रारूप जैसे [[ परिशिष्ट भाग ]], या [[माइक्रोसॉफ्ट वर्ड]] में [[मैक्रो (कंप्यूटर विज्ञान)]] में सशर्त संरचनाएं होती हैं।<ref>{{cite web |author=Magnus Daum |author2=Stefan Lucks |author2-link=Stefan Lucks |title=हैश टकराव (जहरीला संदेश हमला)|work=[[Eurocrypt]] 2005 rump session |url=http://th.informatik.uni-mannheim.de/People/lucks/HashCollisions/ |url-status=dead |archive-url=https://web.archive.org/web/20100327141611/http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/ |archive-date=2010-03-27 }}</ref><ref name=special-file-formats>{{cite journal |author1=Max Gebhardt |author2=Georg Illies |author3=Werner Schindler |title=विशेष फ़ाइल प्रारूपों के लिए एकल हैश टकराव के व्यावहारिक मूल्य पर एक नोट|date=4 January 2017 |url=http://csrc.nist.gov/groups/ST/hash/documents/Illies_NIST_05.pdf }}</ref> (यदि-तब-अन्यथा) जो यह परीक्षण करने की अनुमति देता है कि क्या प्रदर्शित होने को नियंत्रित करने के लिए फ़ाइल में किसी स्थान का एक या दूसरा मान है।

*टीआईएफएफ फाइलों में क्रॉप की गई छवियां हो सकती हैं, जिसमें हैश मान को प्रभावित किए बिना छवि का एक अलग हिस्सा प्रदर्शित किया जा सकता है।<ref name=special-file-formats />*[[पीडीएफ]] फाइलें रंग मान का उपयोग करके टकराव के हमलों के प्रति संवेदनशील होती हैं (जैसे कि एक संदेश का पाठ सफेद रंग के साथ प्रदर्शित होता है जो पृष्ठभूमि में मिश्रित होता है, और दूसरे संदेश का पाठ गहरे रंग के साथ प्रदर्शित होता है) जिसे बाद में बदला जा सकता है हस्ताक्षरित दस्तावेज़ की सामग्री बदलें.<ref name=special-file-formats />

==चुना-उपसर्ग टकराव हमला==

टकराव हमले का एक विस्तार चुना-उपसर्ग टकराव हमला है, जो मर्कले-डैमगार्ड निर्माण के लिए विशिष्ट है|मर्कल-डैमगार्ड हैश फ़ंक्शन। इस मामले में, हमलावर दो मनमाने ढंग से अलग-अलग दस्तावेज़ चुन सकता है, और फिर अलग-अलग गणना किए गए मान जोड़ सकता है जिसके परिणामस्वरूप पूरे दस्तावेज़ में एक समान हैश मान होता है। यह हमला क्लासिकल टक्कर हमले से कहीं अधिक शक्तिशाली है।

गणितीय रूप से कहा गया है, दो अलग-अलग उपसर्ग दिए गए हैं₁, पी₂, हमले में दो उपांग मिलते हैं एम₁ और एम₂ ऐसे कि हैश(p₁ ∥ एम₁) = हैश(पी₂ ∥ एम₂) (जहाँ ∥ संघनन संक्रिया है)।

2007 में, एमडी5 के विरुद्ध एक चयनित-उपसर्ग टकराव हमला पाया गया, जिसके लिए लगभग 2 की आवश्यकता थी^{MD5 फ़ंक्शन के 50}मूल्यांकन। पेपर अलग-अलग डोमेन नामों के लिए टकराते हैश मानों के साथ दो X.509 प्रमाणपत्र भी प्रदर्शित करता है। इसका मतलब यह है कि एक प्रमाणपत्र प्राधिकारी को एक डोमेन के लिए प्रमाणपत्र पर हस्ताक्षर करने के लिए कहा जा सकता है, और फिर उस प्रमाणपत्र (विशेष रूप से उसके हस्ताक्षर) का उपयोग किसी अन्य डोमेन का प्रतिरूपण करने के लिए एक नया दुष्ट प्रमाणपत्र बनाने के लिए किया जा सकता है।<ref name=md5-chosen-2007>{{cite journal |author1=Marc Stevens |author2=Arjen Lenstra |author3=Benne de Weger |date=2007-11-30 |title=Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities |journal=Lecture Notes in Computer Science |volume=4515 |page=1 |doi=10.1007/978-3-540-72540-4_1 |bibcode=2007LNCS.4515....1S |isbn=978-3-540-72539-8 |url=http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ |doi-access=free }}</ref>

फ़्लेम (मैलवेयर) मैलवेयर ने Microsoft रूट प्रमाणपत्र द्वारा अपने घटकों के कोड हस्ताक्षर को धोखा देने के लिए चुने हुए-उपसर्ग टकराव हमले के एक नए संस्करण का सफलतापूर्वक उपयोग किया जो अभी भी समझौता किए गए MD5 एल्गोरिदम का उपयोग करता है।<ref>{{cite web| url=http://blogs.technet.com/b/msrc/archive/2012/06/03/microsoft-releases-security-advisory-2718704.aspx?Redirected=true| title=Microsoft releases Security Advisory 2718704|publisher=[[Microsoft]]|date=3 June 2012|access-date=4 June 2012|archive-url=https://web.archive.org/web/20120607215605/http://blogs.technet.com/b/msrc/archive/2012/06/03/microsoft-releases-security-advisory-2718704.aspx?Redirected=true|archive-date=7 June 2012|url-status=dead}}</ref><ref>{{cite web|url=http://www.cwi.nl/news/2012/cwi-cryptanalist-discovers-new-cryptographic-attack-variant-in-flame-spy-malware|title=सीडब्ल्यूआई क्रिप्टैनालिस्ट ने फ़्लेम स्पाई मैलवेयर में नए क्रिप्टोग्राफ़िक अटैक वेरिएंट की खोज की|author=Marc Stevens|publisher=Centrum Wiskunde & Informatica|date=7 June 2012|access-date=9 June 2012}}</ref>

2019 में, शोधकर्ताओं ने 2 के बीच कंप्यूटिंग जटिलता के साथ SHA-1 के खिलाफ एक चुना-उपसर्ग टकराव हमला पाया^66.9और 2^69.4और लागत 100,000 अमेरिकी डॉलर से कम। <ref name = "SHA-1 collision attacks are now actually practical and a looming danger_2019"> {{cite news | title = SHA-1 टकराव के हमले अब वास्तव में व्यावहारिक हैं और एक खतरा मंडरा रहा है| url = https://www.zdnet.com/article/sha-1-collision-attacks-are-now-actually-practical-and-a-looming-danger/ | work = ZDNet | author = Catalin Cimpanu | language = en | date = 2019-05-13 }} </ref><ref name = 'Collisions of Chosen-Prefix Collisions SHA-1_2019'> {{ cite web | title = टकरावों से लेकर चयनित-उपसर्ग टकरावों के अनुप्रयोग से लेकर पूर्ण SHA-1 तक| url = https://eprint.iacr.org/2019/459.pdf | author1 = Gaëtan Leurent |author2=Thomas Peyrin | date = 2019-05-06 }} </ref> 2020 में, शोधकर्ताओं ने SHA-1 के विरुद्ध चुने गए-उपसर्ग टकराव हमले की जटिलता को कम करके 2 कर दिया^63.4. <ref name = "SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust">{{ cite web | title = SHA-1 एक जर्जर स्थिति है - SHA-1 पर पहला चुना-उपसर्ग टकराव और ट्रस्ट के पीजीपी वेब पर अनुप्रयोग| url = https://eprint.iacr.org/2020/014.pdf | author1 = Gaëtan Leurent |author2=Thomas Peyrin | date = 2020-01-05 }}</ref>

क्रिप्टोग्राफ़िक हैश फ़ंक्शंस के कई अनुप्रयोग [[टकराव प्रतिरोध]] पर निर्भर नहीं होते हैं, इस प्रकार टकराव के हमले उनकी सुरक्षा को प्रभावित नहीं करते हैं। उदाहरण के लिए, [[एचएमएसी]] असुरक्षित नहीं हैं।<ref name=collision-qna>{{cite web |date=2005-02-15 |title=हैश टकराव प्रश्नोत्तर|publisher=Cryptography Research Inc. |url=http://www.cryptography.com/cnews/hash.html  |quote=जिस तरह से एचएमएसी निर्माण में हैश फ़ंक्शन का उपयोग किया जाता है, इन हालिया हमलों में उपयोग की जाने वाली तकनीकें लागू नहीं होती हैं|archive-url = https://web.archive.org/web/20080717103333/http://www.cryptography.com/cnews/hash.html |archive-date = 2008-07-17}}</ref> हमले के उपयोगी होने के लिए, हमलावर के पास हैश फ़ंक्शन के इनपुट का नियंत्रण होना चाहिए।

2008 में, शोधकर्ताओं ने इस परिदृश्य का उपयोग करते हुए, एक दुष्ट प्रमाणपत्र प्राधिकरण प्रमाणपत्र तैयार करने के लिए, एमडी5 के विरुद्ध एक चुने हुए-उपसर्ग टकराव हमले का उपयोग किया। उन्होंने ट्रांसपोर्ट लेयर सिक्योरिटी [[सार्वजनिक कुंजी प्रमाणपत्र]] के दो संस्करण बनाए, जिनमें से एक वैध प्रतीत हुआ और रैपिडएसएसएल प्रमाणपत्र प्राधिकरण द्वारा हस्ताक्षर करने के लिए प्रस्तुत किया गया। दूसरे संस्करण में, जिसमें समान MD5 हैश था, इसमें झंडे शामिल थे जो वेब ब्राउज़र को मनमाने ढंग से अन्य प्रमाणपत्र जारी करने के लिए इसे वैध प्राधिकारी के रूप में स्वीकार करने का संकेत देते थे।<ref>{{cite conference |url=http://www.win.tue.nl/hashclash/rogue-ca/ |author=Alexander Sotirov |author2=Marc Stevens |author3=Jacob Appelbaum |author4=Arjen Lenstra |author5=David Molnar |author6=Dag Arne Osvik |author7=Benne de Weger |date=30 December 2008 |title=MD5 considered harmful today |conference=[[Chaos Communication Congress]] 2008 }}</ref>

हैश फ्लडिंग (जिसे HashDoS के नाम से भी जाना जाता है<ref>{{cite book |last1=Falkenberg |first1=Andreas |last2=Mainka |first2=Christian |last3=Somorovsky |first3=Juraj |last4=Schwenk |first4=Jörg |title=2013 IEEE 20th International Conference on Web Services |chapter=A New Approach towards DoS Penetration Testing on Web Services |year=2013 |pages=491–498 |doi=10.1109/ICWS.2013.72|isbn=978-0-7695-5025-1 |s2cid=17805370 }}</ref>) सेवा हमले से इनकार है जो [[ हैश तालिका ]] लुकअप के सबसे खराब स्थिति (रैखिक जांच) रनटाइम का फायदा उठाने के लिए हैश टकराव का उपयोग करता है।<ref name=v8>{{cite web |title=About that hash flooding vulnerability in Node.js... · V8 |url=https://v8.dev/blog/hash-flooding |website=v8.dev}}</ref> इसे मूल रूप से 2003 में वर्णित किया गया था। इस तरह के हमले को अंजाम देने के लिए, हमलावर सर्वर को डेटा के कई टुकड़े भेजता है जो समान मूल्य पर हैश होता है और फिर सर्वर को धीमी गति से लुकअप करने का प्रयास करता है। चूंकि हैश तालिकाओं में उपयोग किए जाने वाले हैश फ़ंक्शन का मुख्य फोकस सुरक्षा के बजाय गति पर था, इसलिए अधिकांश प्रमुख प्रोग्रामिंग भाषाएं प्रभावित हुईं,<ref>Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th conference on USENIX Security Symposium - Volume 12 (SSYM'03), Vol. 12. USENIX Association, Berkeley, CA, USA, 3-3.</ref> इस वर्ग की नई कमजोरियाँ मूल प्रस्तुति के एक दशक बाद भी दिखाई दे रही हैं।<ref name=v8/>