Как возможно захешировать любой файл, если количество комбинаций самой хеш-суммы ограничено?

Question

[FMars]

Понятное дело, что количество комбинаций хеш-суммы для каждого алгоритма огромное, но ведь файлов (или даже простых строк) еще больше.

Answer 1

[jcmvbkbc]

количество комбинаций хеш-суммы для каждого алгоритма огромное, но ведь файлов (или даже простых строк) еще больше

Возможных файлов больше. Реально использованных -- гораздо меньше. Т.е. если мы возьмём 10⁹ компьютеров перебирающих 10⁹ файлов в секунду, то чтобы перебрать все возможные значения sha1 потребуется 2¹⁶⁰/10¹⁸ = 10³⁰ секунд, т.е. 4 * 10²² лет, что существенно больше возраста Вселенной.

Answer 2

[tsarevfs]

Действительно, в общем случае коллизий не избежать. Однако, на практике вполне достаточно того что коллизии маловероятны.
Можно посмотреть на примеры использования хешей:
* контрольная сумма — проверка того что большой файл не испорчен или не изменен. Вероятность коллизии ~= 1/2^HASH_LENGTH при случайных изменениях. Хорошие криптографические хеш функции предполагают, что подобрать данные с заданым хешом очень сложно.
* hash map. Коллизия в этой структуре данных это нормальная ситуация. Коллизии отслеживаются и обрабатываются различными способами, и если их становится слишком много пространство хешей расширяют.

Answer 3

[Андрей]

В дополнение к совершенно правильному ответу @jcmvbkbc :

По парадоксу дней рождения первая коллизия наиболее вероятно наступит, когда будет создано sqrt(2^N), т.е. 2^(N/2) документов. Так вот чтобы создать такую массу файлов для MD5 все население земного шара должно создавать по одному документу каждую секунду в течение 100 лет.

Answer 4

[Дмитрий Энтелис]

На практике, на живых данных и шаловливых пользователях коллизии в hash функции встречаются гораздо чаще чем это можно ожидать теоретически. Поэтому на живом проекте важно помнить, что если хеш функции совпадают, это значит не "исходные строки совпадают", а "вероятно исходные строки совпадают"

Comments

[Андрей]

Не продемонстрируете хеш-коллизии в живых данных для MD5 или SHA-X ?