У меня есть библиотека изображений на Amazon S3. Для каждого изображения я ввожу исходный URL-адрес на моем сервере и метку времени, чтобы получить уникальное имя файла. Поскольку S3 не может иметь подкаталогов, мне нужно хранить все эти изображения в одной плоской папке.
Нужно ли беспокоиться о коллизиях в полученном хеш-значении MD5?
Бонус: Сколько файлов я могу иметь, прежде чем начну видеть столкновения в хеш-значении, которое создает MD5?
Ответы:
Вероятность случайного столкновения всего двух хэшей составляет 1/2 128, что составляет 1 на 340 ундециллионов 282 дециллионов 366 ниллионов 920 октиллионов 938 септиллионов 463 квинтиллионов 373 квадриллионов 604 триллионов 431 миллиардов 768 миллионов 211 тысяч 456.
Однако, если вы сохраняете все хэши, вероятность немного выше благодаря парадоксу дня рождения . Чтобы иметь 50% вероятности столкновения любого хэша с любым другим хешем, вам нужно 2 64 хеша. Это означает, что для получения коллизии в среднем вам потребуется хэшировать 6 миллиардов файлов в секунду в течение 100 лет .
источник
1 - sPn/s^n, гдеsразмер пространства поиска (2^128в данном случае) иnколичество хэшированных элементов. Вероятно, вы думаете о том2^64, какое приблизительное количество элементов вам понадобится для хеширования MD5, чтобы иметь вероятность столкновения 50%.S3 может иметь подкаталоги. Просто введите «/» в имени ключа, и вы сможете получить доступ к файлам, как если бы они были в отдельных каталогах. Я использую это для хранения пользовательских файлов в отдельных папках на основе их идентификатора пользователя в S3.
Например: «mybucket / users / 1234 / somefile.jpg». Это не совсем то же самое, что каталог в файловой системе, но S3 API имеет некоторые функции, которые позволяют ему работать почти так же. Я могу попросить его перечислить все файлы, которые начинаются с «users / 1234 /», и он покажет мне все файлы в этом «каталоге».
источник
Так что подождите
или:
Если первое, вы большую часть пути к GUID, и я бы не беспокоился об этом. Если последнее, то посмотрите пост Карга о том, как вы в конечном итоге столкнетесь с столкновениями.
источник
md5(filename) + timestampснижает риск столкновения, потому что вам нужно иметь столкновение md5 для точно такой же временной метки, чтобы столкновение в целом.md5(filename + timestamp)аналогичноmd5(filename)предположению, что имя файла является случайным для начала (поскольку добавление большей случайности к чему-то случайному изменяет только индивидуальный результат md5, и проблема дня рождения по-прежнему существует во всех хэшах md5).Грубое эмпирическое правило для столкновений - это квадратный корень из диапазона значений. Ваш сигнал MD5 предположительно имеет длину 128 бит, поэтому вы, скорее всего, увидите столкновения выше 2 ^ 64 изображений.
источник
Хотя случайные коллизии MD5 чрезвычайно редки, если ваши пользователи могут предоставлять файлы (которые будут сохранены дословно), они могут спроектировать коллизии. То есть они могут намеренно создавать два файла с одинаковой суммой MD5, но разными данными. Убедитесь, что ваше приложение может разумно обработать этот случай, или, возможно, используйте более сильный хеш, такой как SHA-256.
источник
Несмотря на то, что из-за коллизий были хорошо известны проблемы с MD5, НЕУДАЧНЫЕ коллизии среди случайных данных встречаются крайне редко . С другой стороны, если вы хэшируете имя файла, это не случайные данные, и я ожидаю быстрых коллизий.
источник
Неважно, насколько это вероятно; это возможно. Это может произойти в первых двух вещах, которые вы хэшируете (очень маловероятно, но возможно), поэтому вам нужно будет поддерживать коллизии с самого начала.
источник
Столкновение MD5 крайне маловероятно. Если у вас 9 триллионов MD5, есть только один шанс из 9 триллионов, что произойдет столкновение.
источник