Сколько случайных элементов перед MD5 вызывает столкновения?

У меня есть библиотека изображений на Amazon S3. Для каждого изображения я md5 URL-адрес источника на моем сервере плюс отметка времени, чтобы получить уникальное имя файла. Поскольку S3 не может иметь подкаталоги, мне нужно сохранить все эти изображения в одной плоской папке.

Нужно ли беспокоиться о столкновениях в хеш файле MD5, который создается?

Бонус: Сколько файлов у меня есть, прежде чем я начну видеть столкновения в хеш-значении, которое производит MD5?

Ответы

Ответ 1

Вероятность случайного столкновения только двух хешей 1/2 128 которая является 1 в 340 нед. Млн. 282 дециллиона 366 нетллионов 920 окт. 938 сепций 463 секстиллиона 463 квинтиллиона 374 квадриллиона 607 трлн 431 млрд 768 млн 211 тыс. 456.

Однако, если вы сохраните все хэши, вероятность будет немного выше благодаря парадоксальности дня рождения. Чтобы иметь 50% -ный шанс на любой хэш, сталкивающийся с любым другим хэшем, вам нужны 2 64 хэши. Это означает, что для достижения столкновения в среднем вам понадобится хеш 6 миллиардов файлов в секунду в течение 100 лет.

Ответ 2

S3 может иметь подкаталоги. Просто введите "/" в имя ключа, и вы можете получить доступ к файлам, как если бы они были в отдельных каталогах. Я использую это для хранения пользовательских файлов в отдельных папках на основе их идентификатора пользователя в S3.

Например: "mybucket/users/1234/somefile.jpg". Это не совсем то же самое, что и каталог в файловой системе, но у S3 API есть некоторые функции, которые позволяют работать почти одинаково. Я могу попросить его перечислить все файлы, начинающиеся с "users/1234/", и он покажет мне все файлы в этом "каталоге".

Ответ 3

Итак, подождите, это:

md5 (имя файла) + метка времени

или

md5 (имя файла + метка времени)

Если первый, вы больше всего на пути к GUID, и я бы не стал беспокоиться об этом. Если последний, то см. Сообщение Карга о том, как вы в конечном итоге столкнетесь с столкновениями.

Ответ 4

Незначительное эмпирическое правило для столкновений является квадратным корнем диапазона значений. Ваш MD5-сиг, предположительно, длиннее 128 бит, так что вы увидите вероятные столкновения выше и выше 2 ^ 64 изображений.

Ответ 5

Хотя случайные столкновения MD5 чрезвычайно редки, если ваши пользователи могут предоставить файлы (которые будут храниться дословно), тогда они могут спровоцировать столкновения. То есть они могут преднамеренно создавать два файла с одним и тем же MD5sum, но с разными данными. Убедитесь, что ваше приложение может обрабатывать этот случай разумным способом или, возможно, использовать более сильный хеш, такой как SHA-256.

Ответ 6

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

Ответ 7

Несмотря на то, что из-за столкновений были широко разрешены проблемы с MD5, UNINTENTIONAL столкновений между случайными данными чрезвычайно редко. С другой стороны, если вы хешируете имя файла, это не случайные данные, и я бы ожидал столкновения быстро.

Ответ 9

Столкновение MD5 крайне маловероятно. Если у вас 9 триллионов MD5, есть только один шанс в 9 триллионов, что произойдет столкновение.