एमडी 5 से पहले कितने यादृच्छिक तत्व टकराव पैदा करते हैं?

मुझे अमेज़ॅन एस 3 पर एक छवि पुस्तकालय मिला है। प्रत्येक छवि के लिए, मैं अपने सर्वर पर स्रोत यूआरएल और एक अद्वितीय फ़ाइल नाम प्राप्त करने के लिए एक टाइमस्टैम्प एमडी 5 करता हूं। चूंकि एस 3 में उपनिर्देशिका नहीं हो सकती है, इसलिए मुझे इन सभी छवियों को एक फ्लैट फ़ोल्डर में स्टोर करने की आवश्यकता है।

क्या मुझे एमडी 5 हैश वैल्यू में टक्कर के बारे में चिंता करने की ज़रूरत है जो उत्पादित हो जाती है?

बोनस: एमडी 5 का उत्पादन हैश मूल्य में टकराव देखना शुरू करने से पहले मुझे कितनी फाइलें मिल सकती हैं?

 131
जोड़ा संपादित
विचारों: 8
स्रोत
ro ru fr es pt de bn ar
संबंधित: क्या दो ज्ञात स्ट्रिंग हैं जिनके पास समान MD5 हैश मान है?
जोड़ा लेखक kenorb, स्रोत
शाब्दिक उत्तर यह है कि दूसरी फ़ाइल में पहले के समान MD5 हो सकता है। हालांकि बाधाएं बहुत छोटी हैं।
जोड़ा लेखक Rick James, स्रोत

8 उत्तर

केवल दो हैश की गलती से टकराव की संभावना 1/2 128 जो 340 अतुलनीय 282 decillion 366 nonillion 920 octillion 938 सेप्टियन 463 sextillion 463 क्विंटिलियन 374 क्वाड्रिलियन 607 ट्रिलियन 431 अरब 768 मिलियन 211 हजार 456 में 1 है।

हालांकि यदि आप सभी हैंश रखते हैं तो संभावना अधिक है कि जन्मदिन विरोधाभास के लिए धन्यवाद। किसी भी हैश के साथ किसी भी हैश टकराव का 50% मौका पाने के लिए आपको 2 64 हैश की आवश्यकता है। इसका मतलब है कि टकराव पाने के लिए, औसतन, आपको हैश 6 अरब फ़ाइलें प्रति सेकंड 100 वर्षों के लिए ।

238
जोड़ा
स्रोत
तो आप कह रहे हैं कि एक मौका है!
जोड़ा लेखक vargonian, स्रोत
"टकराव की संभावना 1/2 ^ 64 है" - क्या? टकराव की संभावना पहले से मौजूद वस्तुओं की संख्या पर निर्भर है, यह एक निश्चित संख्या नहीं है। वास्तव में, यह बिल्कुल 1 - sPn/s ^ n के बराबर है, जहां s खोज स्थान का आकार है ( 2 ^ 128 में यह मामला), और n आइटमों की संख्या है। आप शायद जो सोच रहे हैं वह 2 ^ 64 है, जो कि एमडी 5 हैश को टकराव का 50% मौका देने के लिए आवश्यक वस्तुओं की अनुमानित संख्या है।
जोड़ा लेखक BlueRaja - Danny Pflughoeft, स्रोत
जर्जनफोग: और भौतिकी के सभी कानून या तो "सही नहीं" हैं। पैडेंटिज्म का ऐसा स्तर अनावश्यक है क्योंकि यह किसी भी सार्थक तरीके से जवाब नहीं बदलता है।
जोड़ा लेखक Kornel, स्रोत
@yaauie नहीं, यह हास्यास्पद रूप से असंभव है। मैं 2 ^ 128 संभावित वाले 2 ^ 64 हैश उत्पन्न करने के बारे में बात कर रहा हूं। यह एक प्रतिशत का एक चौथाई हिस्सा सभी संभव हैश उत्पन्न हुआ है।
जोड़ा लेखक Kornel, स्रोत
@ ब्लूराजा-डैनीफ्लूघोफ्ट जो वास्तव में मेरे मन में था। सुधारों के लिए धन्यवाद।
जोड़ा लेखक Kornel, स्रोत
@ConcernedOfTunbridgeWells: मैंने जन्मदिन के विरोधाभास के लिए सुधार किया है, यही कारण है कि उत्तर अरबों में है, क्विंटिलियन नहीं। मैं आपकी स्क्रिप्ट <कोड> पीवी = 2 ** 128 के साथ संभावना को सत्यापित करने में असमर्थ था; एसएस = 2 ** 64 : <कोड> ओवरफ्लो त्रुटि: int int// code> में कनवर्ट करने के लिए बहुत लंबा int
जोड़ा लेखक Kornel, स्रोत
सख्ती से सच नहीं है। टकराव की संभावना इस से काफी अधिक है क्योंकि एक नया यूआरएल तालिका में किसी भी मौजूदा आइटम के साथ संभावित रूप से टकरा सकता है। यह पोस्टिंग देखें (अस्वीकरण, मैंने इसे लिखा है) एक रन- गणित पर नीचे, और एक छोटी पायथन लिपि जिसे किसी विशेष संख्या के URL की संभावना की गणना करने के लिए अनुकूलित किया जा सकता है।
जोड़ा लेखक ConcernedOfTunbridgeWells, स्रोत
दुर्भाग्यवश, आप अभी भी सही नहीं हैं। आप मान रहे हैं कि हैश फ़ंक्शन वास्तव में यादृच्छिक है। यह नहीं। इसका मतलब है कि टकराव की संभावना अधिक है।
जोड़ा लेखक Jørgen Fogh, स्रोत
गणना जोड़ने के लिए +1। यह थोड़ा और सटीक है: http://www.google.com/search?q=2^64%2F100* (सेकंड + प्रति + वर्ष)
जोड़ा लेखक Mathias Bynens, स्रोत
(इसका मतलब है कि टकराव पाने के लिए, औसतन, आपको प्रति वर्ष 6 अरब फाइलें प्रति सेकंड 100 साल की आवश्यकता होगी।); गलत। इसका मतलब है कि समय आप 100 वर्षों के लिए प्रति सेकंड 6 बिलियन फाइलें हैं, आप उत्पन्न होने वाले हैंश का 50% पहले से जेनरेट किए गए हैंश के साथ टकराएंगे।
जोड़ा लेखक yaauie, स्रोत
+1 क्योंकि मैं हमेशा जानना चाहता था कि 999 ट्रिलियन लॉल से पहले कैसे गिनना है (और ओह हाँ आपका जवाब जानकारीपूर्ण था)
जोड़ा लेखक Kmeixner, स्रोत
सहजता से अगर हम जन्मदिन के विरोधाभास को अनदेखा करते हैं और केवल अनुमानित समाधान को देखते हैं: 2 ^ 64 सूची में हैश जोड़ें। अब उस सूची में एक और हैश जोड़ें। उस एक और हैश में 1/2 ^ 128 times 2 ^ 64 टक्कर का मौका है, यानी कि एक और हैश में 1/2 ^ 64 टकराव का मौका। अब सूची में एक और 2 ^ 64 हैश जोड़ें और आपको टक्कर मिलनी चाहिए। 2 ^ 63 (और नोट <कोड> 2 ^ 63 + 2 ^ 63 = 2 ^ 64 ) के लिए समान गणना करें।
जोड़ा लेखक robocat, स्रोत

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

उदाहरण के लिए: "mybucket/users/1234/somefile.jpg"। यह फ़ाइल सिस्टम में निर्देशिका के समान नहीं है, लेकिन एस 3 एपीआई में कुछ विशेषताएं हैं जो इसे लगभग उसी तरह काम करने देती हैं। मैं इसे "उपयोगकर्ताओं/1234 /" से शुरू होने वाली सभी फ़ाइलों को सूचीबद्ध करने के लिए कह सकता हूं और यह मुझे "निर्देशिका" में सभी फाइलें दिखाएगा।

22
जोड़ा
स्रोत
यह एक ऐसी सामग्री होनी चाहिए जो मुझे लगता है, क्योंकि यह वास्तव में टकराव की संभावना के बारे में सवाल का जवाब नहीं देता है
जोड़ा लेखक Ian Clark, स्रोत

तो रुको, क्या यह है:

md5(filename) + timestamp

या:

md5(filename + timestamp)

यदि पूर्व, आप GUID के लिए सबसे अधिक रास्ते हैं, और मैं इसके बारे में चिंता नहीं करता। यदि उत्तरार्द्ध है, तो अंततः टक्कर में भागने के तरीके के बारे में कार्ग की पोस्ट देखें।

16
जोड़ा
स्रोत
@BradThomas: यह नहीं करता है। टकराव का एमडी 5 जोखिम वही है चाहे वह फ़ाइल नाम पर हो या फ़ाइल नाम + टाइमस्टैम्प का संयोजन हो। लेकिन पहले परिदृश्य में, आपको एमडी 5 टक्कर और टाइमस्टैम्प टकराव दोनों की आवश्यकता होगी।
जोड़ा लेखक Vincent Hubert, स्रोत
यह अभी भी दो उपयोगकर्ताओं प्रति मिनट के साथ एक संयोजन के 2 ^ (128 ^ 60) मौका छोड़ देता है। सचमुच अनुपयोगी।
जोड़ा लेखक Berry M., स्रोत
टाइमस्टैम्प को टकराव का मौका कैसे बढ़ाता है, इस बारे में विस्तार से बताएं
जोड़ा लेखक Brad Thomas, स्रोत
@BradThomas स्पष्ट होने के लिए: md5 (फ़ाइल नाम) + टाइमस्टैम्प टक्कर के जोखिम को बड़े पैमाने पर कम कर देता है क्योंकि आपको टकराव समग्र रूप से एक ही टाइमस्टैम्प के लिए एमडी 5 टक्कर की आवश्यकता होगी। md5 (फ़ाइल नाम + टाइमस्टैम्प) md5 (फ़ाइल नाम) जैसा ही मानता है कि फ़ाइल नाम प्रारंभ करने के लिए यादृच्छिक है (क्योंकि कुछ यादृच्छिकता को यादृच्छिकता केवल व्यक्तिगत md5 को बदलती है परिणाम और जन्मदिन की समस्या अभी भी सभी एमडी 5 हैश में मौजूद है)।
जोड़ा लेखक robocat, स्रोत

टकराव के लिए अंगूठे का एक मोटा नियम मूल्यों की सीमा का वर्ग-रूट है। आपका एमडी 5 सिग संभवतः 128 बिट लंबा है, इसलिए आपको 2 ^ 64 छवियों के ऊपर और उससे बाहर टकराव देखने की संभावना होगी।

10
जोड़ा
स्रोत
en.wikipedia.org/wiki/Birthday_Problem समस्या के बारे में कुछ और जानकारी।
जोड़ा लेखक Georg Schölly, स्रोत
आप शायद 128 बिट्स का मतलब है, 2 ^ 128 नहीं। :-)
जोड़ा लेखक JesperE, स्रोत

हालांकि यादृच्छिक एमडी 5 टकराव बहुत दुर्लभ हैं, यदि आपके उपयोगकर्ता फाइलें प्रदान कर सकते हैं (जो वर्बैटिम संग्रहीत किया जाएगा) तो वे टकराव इंजीनियर बन सकते हैं। यही है, वे जानबूझकर एक ही MD5sum के साथ दो फाइलें बना सकते हैं लेकिन अलग-अलग डेटा। सुनिश्चित करें कि आपका एप्लिकेशन इस मामले को समझदार तरीके से संभाल सकता है, या शायद SHA-256 जैसे मजबूत हैश का उपयोग कर सकता है।

7
जोड़ा
स्रोत
नमक का उपयोग उपयोगकर्ता इंजीनियरिंग समस्या का ख्याल रखेगा, नहीं?
जोड़ा लेखक StackOverflowed, स्रोत
यह इस बात पर निर्भर करता है कि नमक कैसे लागू होता है। इसे उपयोगकर्ता द्वारा प्रदत्त डेटा का उपसर्ग होना चाहिए, या एचएमएसी के लिए अभी तक बेहतर है। यद्यपि रक्षा में अभ्यास करना अभी भी एक अच्छा विचार है।
जोड़ा लेखक bdonlan, स्रोत
नोट हालांकि SHA256 256 बिट्स लंबा है, तो आप SHA256 को कम बिट्स के साथ छोटा करके कुंजी की लंबाई के साथ टकराव के जोखिम को दूर कर सकते हैं उदा। SHA256 का उपयोग करें, लेकिन 128 बिट्स पर इसे छोटा करें (जो एमडी 5 का उपयोग करने से अधिक सुरक्षित है, भले ही उनके पास बिट्स की संख्या समान है)।
जोड़ा लेखक robocat, स्रोत

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

3
जोड़ा
स्रोत
मेरे पास टेलर उदाहरण के साथ एकमात्र समस्या यह है कि अगर किसी को आपके डेटाबेस की प्रति प्राप्त हो जाती है तो वे शायद इंद्रधनुष तालिका का उपयोग कर क्रेडिट कार्ड नंबरों को समझ सकते हैं ...
जोड़ा लेखक Sam Saffron, स्रोत
जबकि मैं क्रेडिट कार्ड के लिए एमडी 5 का उपयोग नहीं करना चाहूंगा, 10,000,000 के बीच सभी वैध क्रेडिट कार्ड नंबरों की एक इंद्रधनुष तालिका (8 अंकों को मैंने देखा है कि सबसे छोटा लम्बा क्रेडिट कार्ड है) और 9, 99, 99, 99, 999, 999 (सबसे बड़ा 16 अंक संख्या) अभी भी एक बड़ा है उत्पन्न करने के लिए टेबल। उन नंबरों को चुरा लेने के लिए शायद आसान तरीके हैं।
जोड़ा लेखक acrosman, स्रोत

एमडी 5 टकराव बेहद असंभव है। यदि आपके पास 9 ट्रिलियन MD5s हैं, तो 9 ट्रिलियन में केवल एक मौका है कि टक्कर होगी।

0
जोड़ा
स्रोत
एक अधिक आइटम जोड़ते समय कई अन्य उत्तर टकराव की संभावना के बारे में बात करते हैं। मुझे लगता है कि मेरा उत्तर अधिक उपयोगी है क्योंकि यह संभवतः पूरे टेबल की डुप्ली रखने के बारे में बात करता है।
जोड़ा लेखक Rick James, स्रोत

वास्तव में कोई फर्क नहीं पड़ता कि यह कितना संभव है; यह संभव है। यह आपके पहले दो चीजों पर हो सकता है (बहुत संभावना नहीं है, लेकिन संभव है), इसलिए आपको शुरुआत से टकराव का समर्थन करना होगा।

0
जोड़ा
स्रोत
निश्चित रूप से कई अन्य बुरी चीजें हो सकती हैं जो 1/2 ^ 128 की संभावना के साथ हो सकती हैं। हो सकता है कि आप इस बारे में चिंता करने के लिए अकेले नहीं रहना चाहें।
जोड़ा लेखक Will Dean, स्रोत
आप गंभीर नहीं हो सकते हैं। टकराव का अच्छा मौका पाने के लिए आपको प्रति सेकंड 6 अरब फाइलें प्रति सेकंड, हर सेकेंड के लिए 100 सेकंड की आवश्यकता होगी। यहां तक ​​कि यदि आप बहुत ही दुर्भाग्यपूर्ण हैं, तो शायद यह मानव जीवनकाल से अधिक समय तक उपयोग की जाने वाली एस 3 की पूरी क्षमता से अधिक ले जाएगा।
जोड़ा लेखक Kornel, स्रोत
यहां सबसे बुरी चीज हो सकती है कि आप एक फोटो प्राप्त कर सकते हैं। अपेक्षाकृत कम संख्या के लिए मैं चिंता नहीं करता। अब यदि आपका सॉफ़्टवेयर एक ऑटोपिलोट को एक विमान लैंडिंग को नियंत्रित कर रहा है, तो यह एक और कहानी है।
जोड़ा लेखक Jim C, स्रोत
यह अरबों गुना अधिक संभावना है कि आपका डेटाबेस और उसके बैकअप सभी असफल हो जाएंगे। टकराव के बारे में चिंता करने लायक नहीं हैं।
जोड़ा लेखक Artelius, स्रोत
टकराव की रोकथाम का समय अपने सर्वर को रखने के लिए एक बंकर बनाने का उपयोग करें! वे अजीब उल्का आपको मार सकते हैं (बहुत ही असंभव, लेकिन संभव), तो आपको भीख मांगने से उल्का आश्रय का समर्थन करना होगा।
जोड़ा लेखक polvoazul, स्रोत
6 जी फाइल/सेकंड पर टकराव का 50% मौका पाने में 100 साल लगेंगे। आपके पास पहले दशकों की टकराव का अच्छा मौका है।
जोड़ा लेखक user327961, स्रोत