कटा हुआ एमडी 5 का समान वितरण?

Question

क्या हम कह सकते हैं कि एक छोटा सा md5 हैश अभी भी समान रूप से वितरित किया गया है?

गलत व्याख्याओं से बचने के लिए: मुझे पता है कि md5 परिणाम से भागों को हैक करने के लिए टकराव का मौका बहुत अधिक है; मेरा उपयोग-केस वास्तव में जानबूझकर टकराव में है। मुझे यह भी पता है कि otherhash methods है जो कि छोटे हैश (वास्तव में, मेरे स्वयं के) के उपयोग के मामलों के लिए उपयुक्त हो सकता है, और मैं निश्चित रूप से उन लोगों को देख रहा हूं।

लेकिन मुझे यह भी जानना अच्छा लगेगा कि md5 का समान वितरण भी इसके हिस्सों पर लागू होता है। (यह एक जलती हुई जिज्ञासा पर विचार करें।)

के बाद से MediaWiki इसे इस्तेमाल करता है (विशेष रूप से, सबसे बाईं ओर दो परिणाम के पात्रों के रूप में हेक्स अंक) छवियों के लिए filepaths उत्पन्न करने के लिए (जैसे /4/42/The-image-name-here.png) और वे शायद यह भी में रुचि रखते हैं कम से कम -निर्धारित वितरण के पास, मुझे लगता है कि उत्तर 'हां' है, लेकिन मुझे वास्तव में पता नहीं है।

Answer 1

हां, किसी भी पूर्वाग्रह का प्रदर्शन नहीं करना एक क्रिप्टोग्राफिक हैश के लिए एक डिजाइन आवश्यकता है। एमडी 5 क्रिप्टोग्राफिक पॉइंट ऑफ व्यू से टूटा हुआ है, हालांकि परिणामों का वितरण कभी सवाल नहीं था।

यदि आपको अभी भी आश्वस्त होने की आवश्यकता है, तो यह परिणाम का विश्लेषण करने के लिए फ़ाइलों का एक समूह हैश आउटपुट का एक बड़ा उपक्रम नहीं है, आउटपुट को छोटा करता है और एंट (http://www.fourmilab.ch/random/) का उपयोग करने के लिए उपयोग नहीं करता है।

Answer 2

मैंने इस प्रश्न का उत्तर देने के लिए एक छोटा PHP प्रोग्राम लिखा था। यह बहुत वैज्ञानिक नहीं है, लेकिन यह हैशटेक्स्ट के रूप में प्राकृतिक संख्याओं का उपयोग करके हैशवाल के पहले और अंतिम 8 बिट्स के वितरण को दिखाता है। लगभग 40,000.000 के बाद उच्चतम और निम्नतम के बीच का अंतर 1% तक गिर जाता है, इसलिए मैं कहूंगा कि वितरण ठीक है। मुझे आशा है कि कोड की गणना करने के लिए कोड अधिक सटीक है :-) बीटीडब्ल्यू, इसी तरह के कार्यक्रम के साथ मैंने पाया कि अंतिम 8 बिट्स पहले की तुलना में थोड़ा बेहतर वितरित किए जाते हैं।

<?php 
// Setup count-array: 
for ($y=0; $y<16; $y++) { 
    for ($x=0; $x<16; $x++) { 
    $count[dechex($x).dechex($y)] = 0; 
    } 
} 

$text = 1; // The text we will hash. 
$hashCount = 0; 
$steps = 10000; 

while (1) { 
    // Calculate & count a bunch of hashes: 
    for ($i=0; $i<$steps; $i++) { 
    $hash = md5($text); 
    $count[substr($hash, 0, 2)]++; 
    $count[substr($hash, -2)]++; 
    $text++; 
    } 
    $hashCount += $steps; 

    // Output result so far: 
    system("clear"); 
    $min = PHP_INT_MAX; $max = 0; 
    for ($y=0; $y<16; $y++) { 
    for ($x=0; $x<16; $x++) { 
     $n = $count[dechex($x).dechex($y)]; 
     if ($n < $min) $min = $n; 
     if ($n > $max) $max = $n; 
     print $n."\t"; 
    } 
    print "\n"; 
    } 
    print "Hashes: $hashCount, Min: $min, Max: $max, Delta: ".((($max-$min)*100)/$max)."%\n"; 
} 
?>