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

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

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

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

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

Ответ 1

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

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

Ответ 2

Я написал небольшую php-программу, чтобы ответить на этот вопрос. Он не очень научный, но он показывает распределение для первого и последнего 8 бит хэш-значений, используя натуральные числа как hashtext. После примерно 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";
} 
?>