Как доказать равномерность хэш-функции?

Question

[mimicria]

Предположим, что разработана специализированная хэш-функция, отображающая множество последовательностей байт (длиной 64) в хэш-значения (длиной 4 байта).
Логично, что инъекция невозможна и коллизий не избежать, но как проверить главное свойство хэшей - равномерность распределения выходных результатов?
Перебирать все возможные входные значения 2^512 нереально.

Answer 1

[Rsa97]

Если достаточно нестрогого доказательства, то методом Монте-Карло. Генерируете случайные блоки, считаете хэш, смотрите его распределение.
Если нужно строгое доказательство - либо полный перебор, либо аналитически.

Comments

[mimicria]

Про Монте-Карло отличный вариант. Остаётся вопрос - какой объем выборки на входе?

Answer 2

[Андрей]

Проведите над массивами значений, полученных после хеширования случайных наборов входных данных, тесты на случайность (DieHard, FIPS 140-1 и аналогичные)

Comments

[mimicria]

Как тесты на случайность докажут равномерность? Выход может быть и случайным, но концентрироваться в одной области больше, в другой меньше.

[Андрей]

mimicria: Тесты на случайность проверяют в том числе отсутствие "концентрирования в одной области"