[git] गिट में हैश टकराव



Answers

एक SHA-1 हैश एक 40 हेक्स वर्ण स्ट्रिंग है ... यह 4 बिट प्रति चरित्र समय 40 है ... 160 बिट्स। अब हम जानते हैं कि 10 बिट्स लगभग 1000 (1024 सटीक होने का अर्थ है) जिसका अर्थ है कि 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 विभिन्न SHA-1 हैश ... 10 48

यह बराबर क्या है? खैर चंद्रमा लगभग 10 47 परमाणुओं से बना है। तो अगर हमारे पास 10 चंद्रमा हैं ... और आप यादृच्छिक रूप से इन चंद्रमाओं में से एक पर एक परमाणु चुनते हैं ... और फिर आगे बढ़ें और फिर उन पर एक यादृच्छिक परमाणु चुनें ... फिर संभावना है कि आप एक ही परमाणु को दो बार चुन लेंगे , यह संभावना है कि दो गिट के पास एक ही SHA-1 हैश होगा।

इस पर विस्तार से हम सवाल पूछ सकते हैं:

टकराव के बारे में चिंता करना शुरू करने से पहले आपको एक भंडार में कितनी चीजें चाहिए?

यह तथाकथित "जन्मदिन के हमले" से संबंधित है, जो बदले में "जन्मदिन विरोधाभास" या "जन्मदिन की समस्या" को संदर्भित करता है, जिसमें कहा गया है कि जब आप किसी दिए गए सेट से यादृच्छिक रूप से चुनते हैं, तो आपको आश्चर्यजनक रूप से कुछ चुनने की आवश्यकता होती है इससे पहले कि आप अधिक संभावना न हों कुछ दो बार चुना है। लेकिन "आश्चर्यजनक रूप से कुछ" यहां एक बहुत सापेक्ष शब्द है।

विकिपीडिया में जन्मदिन विरोधाभास टकराव की संभावना पर एक सारणी है । 40 वर्ण हैश के लिए कोई प्रविष्टि नहीं है। लेकिन 32 और 48 अक्षरों के लिए प्रविष्टियों का एक इंटरपोलेशन हमें टक्कर की 0.1% संभावना के लिए 5 * 10 22 गिट की सीमा में ले जाता है। यह पचास हजार अरब अरब अलग-अलग काम करता है, या पचास ज़ेटाकॉमिट्स , इससे पहले कि आप एक टक्कर मारने वाले 0.1% मौके तक पहुंच गए हों।

इन कामों के लिए अकेले हैंश का बाइट योग एक वर्ष के लिए पृथ्वी पर उत्पन्न सभी डेटा की तुलना में अधिक डेटा होगा, जिसका कहना है कि आपको वीडियो स्ट्रीमिंग के मुकाबले कोड को तेज़ करने की आवश्यकता होगी। उसके साथ अच्छा भाग्य। : डी

इसका मुद्दा यह है कि जब तक कोई जानबूझकर टकराव नहीं कर लेता है, तब तक यादृच्छिक रूप से होने वाली किसी की संभावना इतनी छोटी है कि आप इस मुद्दे को अनदेखा कर सकते हैं

पर क्या अगर...?

ठीक है, मान लीजिए कि असंभव होता है, या मान लीजिए कि कोई जानबूझकर SHA-1 हैश टकराव तैयार करने में कामयाब रहा। फिर क्या होता है?

उस स्थिति में एक उत्कृष्ट उत्तर है जहां किसी ने इसका प्रयोग किया था । मैं उस उत्तर से उद्धरण दूंगा:

  1. यदि एक हीश के साथ एक ब्लॉब पहले से मौजूद है, तो आपको कोई चेतावनी नहीं मिलेगी। सबकुछ ठीक लगता है, लेकिन जब आप धक्का देते हैं, कोई क्लोन, या आप वापस आते हैं, तो आप नवीनतम संस्करण खो देंगे (ऊपर बताए गए अनुसार)।
  2. यदि एक वृक्ष वस्तु पहले से मौजूद है और आप एक ही हैश के साथ एक ब्लॉब बनाते हैं: जब तक आप या तो धक्का देने की कोशिश नहीं करते हैं या कोई आपके भंडार को क्लोन करता है तब तक सब कुछ सामान्य प्रतीत होता है। फिर आप देखेंगे कि रेपो भ्रष्ट है।
  3. यदि कोई प्रतिबद्ध वस्तु पहले से मौजूद है और आप उसी हैश के साथ ब्लॉब बनाते हैं: # 2 - भ्रष्ट के समान
  4. यदि एक ब्लॉब पहले से मौजूद है और आप एक ही हैश के साथ एक प्रतिबद्ध वस्तु बनाते हैं, तो "ref" को अपडेट करते समय यह असफल हो जाएगा।
  5. यदि एक ब्लॉब पहले से मौजूद है और आप एक ही हैश के साथ एक पेड़ वस्तु बनाते हैं। प्रतिबद्धता बनाते समय यह असफल हो जाएगा।
  6. यदि एक वृक्ष वस्तु पहले से मौजूद है और आप एक ही हैश के साथ एक प्रतिबद्ध वस्तु बनाते हैं, तो यह "रेफरी" को अपडेट करते समय विफल हो जाएगा।
  7. यदि एक वृक्ष वस्तु पहले से मौजूद है और आप एक ही हैश के साथ एक पेड़ वस्तु बनाते हैं, तो सब कुछ ठीक लगेगा। लेकिन जब आप प्रतिबद्ध होते हैं, तो सभी भंडार गलत पेड़ का संदर्भ देंगे।
  8. यदि कोई प्रतिबद्ध वस्तु पहले से मौजूद है और आप एक ही हैश के साथ एक प्रतिबद्ध वस्तु बनाते हैं, तो सब कुछ ठीक लगेगा। लेकिन जब आप प्रतिबद्ध होते हैं, तो प्रतिबद्धता कभी नहीं बनाई जाएगी, और हेड पॉइंटर को पुरानी प्रतिबद्धता में ले जाया जाएगा।
  9. यदि कोई प्रतिबद्ध वस्तु पहले से मौजूद है और आप एक ही हैश के साथ एक वृक्ष वस्तु बनाते हैं, तो प्रतिबद्धता बनाते समय यह विफल हो जाएगा।

जैसा कि आप महसूस कर सकते हैं कि कुछ मामले अच्छे नहीं हैं। विशेष रूप से मामले # 2 और # 3 आपके भंडार को गड़बड़ कर देते हैं। हालांकि, ऐसा लगता है कि गलती उस भंडार के भीतर रहती है, और हमला / विचित्र अयोग्यता अन्य reposistories के लिए प्रचार नहीं करता है।

यह भी लगता है कि जानबूझकर टकराव का मुद्दा वास्तविक खतरे के रूप में पहचाना जा रहा है, और उदाहरण के लिए गिटहब इसे रोकने के लिए उपाय कर रहा है

Question

गिट का उपयोग करते समय मेरे पास हैश टकराव था तो वास्तव में क्या होगा?

जैसे मैं एक ही sha1 चेकसम के साथ दो फाइलें करने का प्रबंधन करता हूं, क्या यह नोटिस करेगा या फाइलों में से किसी एक को दूषित करेगा?

क्या इसके साथ रहने के लिए गिट सुधार किया जा सकता है, या क्या मुझे एक नया हैश एल्गोरिदम में बदलना होगा?

(कृपया इस प्रश्न को इस बात पर ध्यान न दें कि यह कितना असंभव है - धन्यवाद)




मुझे हाल ही में एक बीएसडी चर्चा समूह में 2013-04-29 से एक पोस्टिंग मिली

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

जहां पोस्टर का दावा है:

गिट रिबेस का उपयोग करते हुए, मैं एक बार हैश टकराव में भाग गया।

दुर्भाग्य से, वह अपने दावे के लिए कोई सबूत नहीं देता है। लेकिन शायद आप उससे संपर्क करने की कोशिश करना चाहते हैं और इस घटना के बारे में उससे पूछें।

लेकिन अधिक सामान्य स्तर पर, जन्मदिन के हमले के कारण एसएचए -1 हैश टक्कर के लिए मौका 1 (2, 80) में 1 है।

यह बहुत कुछ लगता है और दुनिया के सभी गिट भंडारों में मौजूद व्यक्तिगत फाइलों के संस्करणों की कुल संख्या से निश्चित रूप से अधिक तरीका है।

हालांकि, यह केवल उन संस्करणों पर लागू होता है जो वास्तव में संस्करण इतिहास में रहते हैं।

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

लेकिन यदि टक्कर या फ़िल्टर-शाखा के दौरान टक्कर होती है, तो इसका प्रतिकूल प्रभाव पड़ सकता है।

एक और बात यह है कि गिट रिपॉजिटरीज में हैश की गई इकाइयों की कुल संख्या का अनुमान लगाया जाए और देखें कि वे कितने दूर तक हैं (2, 80)।

आइए मान लें कि हमारे पास लगभग 8 बिलियन लोग हैं, और वे सभी गिट चला रहे होंगे और प्रति व्यक्ति 100 गिट भंडारों में अपनी सामग्री का संस्करण बनाए रखेंगे। आइए मान लें कि औसत भंडार में 100 काम और 10 फाइलें हैं, और उनमें से केवल एक फाइल प्रति प्रतिबद्धता में बदलाव करती है।

प्रत्येक संशोधन के लिए हमारे पास वृक्ष वस्तु के लिए कम से कम एक हैश और प्रतिबद्ध वस्तु स्वयं है। बदले गए फाइल के साथ हमारे पास प्रति संशोधन 3 हैश है, और इस प्रकार प्रति शेयर 300 हैश।

8 अरब लोगों के 100 भंडारों के लिए यह पाउ (2, 47) देता है जो अभी भी पाउ (2, 80) से बहुत दूर है।

हालांकि, इसमें उल्लिखित अनुमानित गुणा प्रभाव शामिल नहीं है, क्योंकि मुझे इस अनुमान में इसे शामिल करने के लिए अनिश्चितता है। शायद यह टक्कर के लिए काफी संभावनाओं को बढ़ा सकता है। विशेष रूप से यदि बहुत बड़े भंडार जो लंबे समय तक प्रतिबद्ध इतिहास (लिनक्स कर्नेल की तरह) को छोटे बदलावों के लिए कई लोगों द्वारा पुन: विश्राम किया जाता है, फिर भी सभी प्रभावित कार्यों के लिए अलग-अलग हैंश बनाते हैं।




क्या इसके साथ रहने के लिए गिट सुधार किया जा सकता है, या क्या मुझे एक नया हैश एल्गोरिदम में बदलना होगा?

किसी भी हैश एल्गोरिदम के लिए टकराव संभव है, इसलिए हैश फ़ंक्शन को बदलना समस्या को रोकता नहीं है, यह केवल घटित होने की संभावना कम करता है। तो आपको तब वास्तव में एक अच्छा हैश फ़ंक्शन चुनना चाहिए (SHA-1 पहले से ही है, लेकिन आपने कहा नहीं जाने वाला कहा :)




एक हैश टक्कर इतनी असंभव है कि यह बेहद मस्तिष्क उड़ रहा है! पूरी दुनिया में वैज्ञानिक एक प्राप्त करने के लिए कड़ी मेहनत कर रहे हैं, लेकिन अभी तक इसका प्रबंधन नहीं किया है। कुछ एल्गोरिदम जैसे कि एमडी 5 के लिए उन्होंने सफलता प्राप्त की, हालांकि।

हालात क्या हैं?

एसएचए -256 में 2 ^ 256 संभव हैश हैं। यह लगभग 10 ^ 78 है । या अधिक ग्राफिक होने के लिए, टक्कर की संभावनाएं हैं

1: 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

लॉटरी जीतने का मौका लगभग 1: 14 एमओओ है । एसएचए -256 के साथ टक्कर का मौका लगातार 11 दिनों में लॉटरी जीतना है!

गणितीय स्पष्टीकरण: 14 000 000 ^ 11 ~ 2 ^ 256

इसके अलावा, universe में लगभग 10 ^ 80 परमाणु हैं। SHA-256 संयोजनों की तुलना में यह केवल 100 गुना अधिक है।

सफल एमडी 5 टकराव

एमडी 5 के लिए भी संभावनाएं छोटी हैं। हालांकि, गणितज्ञ टक्कर पैदा करने में कामयाब रहे:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

के रूप में एक ही एमडी 5 है

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

इसका मतलब यह नहीं है कि एमडी 5 अब कम सुरक्षित है कि इसका एल्गोरिदम क्रैक हो गया है। आप उद्देश्य पर एमडी 5 टकराव बना सकते हैं, लेकिन एक आकस्मिक एमडी 5 टक्कर का मौका अभी भी 2 ^ 128 है, जो अभी भी बहुत कुछ है।

निष्कर्ष

टकराव के बारे में आपको चिंता करने की ज़रूरत नहीं है। हैशिंग एल्गोरिदम फ़ाइल समानता की जांच करने का दूसरा सबसे सुरक्षित तरीका है। एकमात्र सुरक्षित तरीका बाइनरी तुलना है।




Links