मैं हैश टकराव की संभावना का आकलन कैसे करूं?

Question

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

स्पष्ट समाधान खोज प्रणाली और बैकएंड के बीच एक मध्यवर्ती परत प्रदान करना है। यह बैकएंड के अनुरोध को कतार देगा और परिणाम आने की प्रतीक्षा करेगा। यदि इंटरमीडिएट परत में अनुरोध का समय - कोई समस्या नहीं है, बैकएंड काम करना जारी रखेगा, केवल इंटरमीडिएट परत को पुनरारंभ किया जाएगा और जब अनुरोध को बाद में खोज प्रणाली द्वारा अनुरोध किया जाता है तो यह बैकएंड से परिणाम पुनर्प्राप्त कर सकता है।

समस्या यह है कि फ़ाइलों की पहचान कैसे करें। उनके नाम यादृच्छिक रूप से बदलते हैं। मैं एक हैश फ़ंक्शन का उपयोग करना चाहता हूं जैसे MD5 फ़ाइल सामग्री को हैश करने के लिए। मुझे birthday paradox के बारे में अच्छी तरह से पता है और संभावना की गणना करने के लिए लिंक किए गए आलेख से अनुमान लगाया गया है। अगर मुझे लगता है कि मेरे पास 100 से अधिक   000 फ़ाइलें नहीं हैं, तो एक ही एमडी 5 (128 बिट) वाली दो फाइलों की संभावना 1,47x10 ^-29 है।

क्या मुझे ऐसी टकराव की संभावना का ख्याल रखना चाहिए या बस मान लें कि बराबर हैश मानों का मतलब बराबर फ़ाइल सामग्री है?

Answer 1

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

कोई आकस्मिक एमडी 5 टकराव नहीं हैं, 1,47x10 ^-29 वास्तव में वास्तव में वास्तव में बहुत कम संख्या है।

बड़ी फ़ाइलों को रिहा करने के मुद्दे को दूर करने के लिए मेरे पास 3 चरणबद्ध पहचान योजना होगी।

1. FILESIZE अकेले
2. FILESIZE + फाइल
3. एक पूर्ण हैश

तो अगर आप एक नया आकार आप के लिए पता है के साथ एक फ़ाइल को देखने में 64K * 4 अलग अलग स्थानों में की एक हैश निश्चित है कि आपके पास डुप्लिकेट नहीं है। और इसी तरह।

Answer 2

मुझे लगता है कि आपको नहीं करना चाहिए।

हालांकि, यदि आपके पास अलग-अलग दो समान फाइलों की धारणा है (वास्तविक नाम, एमडी 5-आधारित नहीं)। जैसे, खोज प्रणाली में दो दस्तावेज़ों में एक ही सामग्री हो सकती है, लेकिन अलग होने के कारण वे अलग-अलग स्थानों पर स्थित हैं।

Answer 3

मैं मोंटे कार्लो दृष्टिकोण के साथ आया था ताकि वितरित सिस्टम के लिए यूयूआईडी का उपयोग करते समय सुरक्षित रूप से सोने में सक्षम हो सकें, जिन्हें टकराव के बिना क्रमबद्ध करना है।

5 hash orders of magnitude events before collission: 1 
6 hash orders of magnitude events before collission: 5 
7 hash orders of magnitude events before collission: 21 
8 hash orders of magnitude events before collission: 91 
9 hash orders of magnitude events before collission: 274 
10 hash orders of magnitude events before collission: 469 
11 hash orders of magnitude events before collission: 138 
12 hash orders of magnitude events before collission: 1 

मैं सूत्र सुना था से पहले:

from random import randint 
from math import log 
from collections import Counter 

def colltest(exp): 
    uniques = [] 
    while True: 
     r = randint(0,2**exp) 
     if r in uniques: 
      return log(len(uniques) + 1, 2) 
     uniques.append(r) 

for k,v in Counter([colltest(20) for i in xrange(1000)]): 
    print k, "hash orders of magnitude events before collission:",v 

की तरह कुछ प्रिंट होगा आप लॉग (एक्स/2) कुंजी स्टोर करने के लिए की जरूरत है, एक हैशिंग कार्य है कि कम से कम keyspace ई का उपयोग * *(एक्स)।

दोहराया प्रयोगों 1000 लॉग-20 रिक्त स्थान की आबादी के लिए है, तो आप कभी कभी एक टक्कर के रूप में जल्दी लॉग (एक्स/4) के रूप में मिलता है दिखाते हैं।

uuid4 जो 122 बिट्स का मतलब है कि मैं सुरक्षित रूप से सो, जबकि कई कंप्यूटरों यादृच्छिक UUID के लेने जब तक मैं के बारे में 2 ** 31 आइटम नहीं हैं है। सिस्टम में पीक लेनदेन मैं सोच रहा हूं कि प्रति सेकेंड लगभग 10-20 घटनाएं हैं, मैं औसत 7 का अनुमान लगा रहा हूं। यह मुझे लगभग 10 वर्षों की एक ऑपरेटिंग विंडो देता है, जो चरम परावर्तक को देखते हैं।

Answer 4

यहाँ एक इंटरैक्टिव कैलकुलेटर आप किसी भी हैश आकार और वस्तुओं की संख्या के लिए टक्कर की संभावना का अनुमान है जिसे - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/

Answer 5

सिर्फ इसलिए संभावना है 1/एक्स इसका मतलब यह नहीं है कि यह जब तक आप करने के लिए नहीं होगा आपके पास एक्स रिकॉर्ड हैं। यह लॉटरी की तरह है, तो आप जीतने के लिए की संभावना नहीं कर रहे हैं वहाँ बाहर होगा जीत है, लेकिन किसी।

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

यदि प्रदर्शन सही मायने में एक मुद्दा है तो BLAKE2 जो वास्तव में तेजी से होता है MD5 से लेकिन टकराव की संभावना कम करने के लिए, जबकि एक ही या बेहतर प्रदर्शन होने 256+ बिट्स का समर्थन करता है का उपयोग करें। हालांकि, जबकि ब्लैक 2 को अच्छी तरह से अपनाया गया है, लेकिन शायद आपको अपनी परियोजना में एक नई निर्भरता जोड़ने की आवश्यकता होगी।