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

Question

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

Нужно ли беспокоиться о коллизиях в полученном хеш-значении MD5?

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

md5(filename) + timestamp

или

md5(filename + timestamp)

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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