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