Равномерное распределение усеченного md5? - PullRequest
Новая
       69

Равномерное распределение усеченного md5?

34 голосов
/ 18 ноября 2011

Можем ли мы сказать, что усеченный хэш md5 по-прежнему распределен равномерно?

Чтобы избежать неправильного толкования: я знаю, что вероятность столкновений намного больше, как только вы начинаете отрывать части от md5 результат;мой вариант использования на самом деле заинтересован в преднамеренных коллизиях.Я также знаю, что есть другие методы хеширования , которые могут лучше подходить для случаев использования более короткого хэша (включая, собственно, мой собственный), и я определенноизучая их.

Но я также хотел бы знать, относится ли равномерное распределение md5 к его частям.(Считай это горящим любопытством.)

Поскольку медиавики используют его (в частности, две левые шестнадцатеричные цифры в качестве символов результата) для генерации путей к файлам для изображений (например, /4/42/The-image-name-here.png), и онивероятно, также заинтересован как минимум в почти -однородном распределении, я думаю, что ответ "да", но на самом деле я не знаю .

Ответы [ 2 ]

28 голосов
/ 20 ноября 2011

Да, отсутствие смещения является требованием к дизайну криптографического хэша. MD5 взломан с криптографической точки зрения, однако распределение результатов никогда не ставилось под сомнение.

Если вам все еще нужно убедиться, это не сложное занятие - хэшировать кучу файлов, обрезать вывод и использовать ent (http://www.fourmilab.ch/random/) для анализа результата.

12 голосов
/ 19 февраля 2012

Я написал небольшую 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";
} 
?>
...