Есть ли у md5 какая-либо гарантия уникальности для коротких строк (конечное число строк)?

Question

Итак, я понимаю, что есть доказательство того, что MD5 не может гарантировать уникальность, так как в юниверсе больше строк, чем хеш-строк MD5, но есть ли обратное доказательство для конечного числа строк?

В принципе, если у меня есть строки максимальной длины X, есть ли X, для которого MD5 гарантированно будет уникальным? если да, то что это за Х? и если существует более одного значения для X, каково максимальное значение X?

или есть такой X для любого другого алгоритма хеширования, SHA-1 и т. д.?

Answer 1

Обобщая отличные ответы здесь: Какая пара строк самая короткая, которая вызывает столкновение MD5?

Самая короткая из известных атак на MD5 требует 2 входных блока, то есть 128 байтов или 1024 бит.

Для любого алгоритма хеширования, который выдает N битов, при условии, что он распределяет входные данные приблизительно случайным образом, можно предположить, что вероятность столкновения составляет более 50% в sqrt(2^N) входы. Например, MD5 хэширует до 128 бит, поэтому вы можете ожидать коллизию между всеми 64-битными входами. Это предполагает равномерно случайный хэш. Любые недостатки могут уменьшить количество входов, прежде чем можно ожидать столкновения.

Answer 2

Ответ на ваш вопрос - да. Для любой хеш-функции существует максимальная длина X, для которой вы получите уникальные строки. Однако найти Х может быть очень сложно. Идея состоит в том, чтобы запустить эту программу:

X= 0;
For i = 0 onward
   For all strings of length i
      Compute the hash code of that string.
      If a collision is found, return X.
   X = i

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

Предполагая, что хеш-функция на самом деле довольно случайна, вам нужно сгенерировать O(√U) различных строк, прежде чем вы обнаружите столкновение, где U - размер пространства, на которое отображается хеш-функция. Для 256-битных хэшей это 2²⁵⁶. Это означает, что на практике вышеприведенная программа никогда не прекратит работу, если хеш-функция не будет сильно нарушена, но теоретически это означает, что ваше число X существует.

Надеюсь это поможет!