Сколько случайных элементов происходит до того, как 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".Это не совсем то же самое, что каталог в файловой системе, но API S3 имеет некоторые функции, которые позволяют ему работать почти так же.Я могу попросить его перечислить все файлы, начинающиеся с «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

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