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

Связанный: Существуют ли две известные строки с одинаковым хеш-значением MD5?

Буквальный ответ заключается в том, что файл второй может иметь тот же MD5, что и первый. Однако шансы крайне малы.

Конечно, может быть много других плохих вещей, которые могут произойти с вероятностью 1/2 ^ 128. Возможно, вы не захотите выделять это, о котором стоит беспокоиться.

Худшее, что здесь может случиться, - это сфотографироваться. За относительно небольшое количество я бы не стал волноваться. Теперь, если ваше программное обеспечение управляет автопилотом, приземляющим самолет, это уже другая история.

Ты не можешь быть серьезным. Вам нужно будет хэшировать 6 миллиардов файлов в секунду каждую секунду в течение 100 лет, чтобы получить хорошие шансы на коллизию. Даже если вам очень-очень не повезло, вероятно, потребуется больше, чем вся емкость S3, используемая дольше, чем человеческая жизнь.

В миллиарды раз больше вероятность того, что ваша база данных и ее резервные копии выйдут из строя. О столкновениях не стоит беспокоиться.

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

Потребуется 100 лет, чтобы получить вероятность столкновения 50% при скорости файлов 6 ГБ / сек. У вас есть вероятность столкновения хорошо десятилетиями ранее.

Плохо то, что кто-то может загружать конфликтующие файлы С ЦЕЛЬЮ, что может привести к ошибкам или, что еще хуже, к нарушению безопасности, например, это может позволить переопределить файл другим файлом. avira.com/en/blog/md5-the-broken-algorithm

Вы, вероятно, имеете в виду 128 бит, а не 2 ^ 128. :-)

Я думаю, это должен быть контент, поскольку на самом деле он не отвечает на вопрос о вероятности столкновения.

Пожалуйста, поясните, как включение временной метки увеличивает вероятность столкновения.

@BradThomas: Это не так. Риск столкновения MD5 одинаков как в имени файла, так и в комбинации имя файла + отметка времени. Но в первом сценарии вам потребуется как коллизия MD5, так и коллизия отметок времени.

Это по-прежнему оставляет 2 ^ (128 ^ 60) шанс столкновения с двумя пользователями в минуту. Буквально непригодный для использования.

@BradThomas Для большей ясности: md5(filename) + timestamp значительно снижает риск столкновения, потому что вам потребуется столкновение md5 для точно такой же временной метки, чтобы иметь общее столкновение. md5(filename + timestamp) совпадает с md5(filename), предполагая, что имя файла изначально случайное (поскольку добавление большей случайности к чему-то случайному изменяет только индивидуальный результат md5, а проблема дня рождения все еще существует для всех хэшей md5).

Единственная проблема, с которой я столкнулся с примером taylors, заключается в том, что если кто-то получит копию вашей базы данных, он, вероятно, сможет выяснить номера кредитных карт, используя радужную таблицу ...

Хотя я бы не стал использовать MD5 для кредитных карт, таблица Rainbow со всеми действительными номерами кредитных карт от 10 000 000 (8 цифр - это самая маленькая кредитная карта, которую я видел) и 9 999 999 999 999 999 (наибольшее 16-значное число) по-прежнему остается большой. таблица для создания. Вероятно, есть более простые способы украсть эти числа.

+1 за добавление расчета. Это немного точнее: http://www.google.com/search?q=2^64%2F100*(seconds+per+year)

Не совсем так. Вероятность коллизии намного выше, чем эта, поскольку новый URL-адрес потенциально может столкнуться с любым существующим элементом в таблице. См. Эта публикация (отказ от ответственности, я написал его) для подробного изучения математики и небольшой скрипт на Python, который можно адаптировать для вычисления вероятности для определенного количества URL-адресов.

@ConcernedOfTunbridgeWells: Я исправил парадокс дня рождения, поэтому ответ исчисляется миллиардами, а не квинтиллионами. Мне не удалось проверить вероятность с помощью вашего скрипта PV=2**128; SS=2**64: OverflowError: long int too large to convert to int

@ BlueRaja-DannyPflughoeft - вот что я действительно имел в виду. Спасибо за исправление.

+1 потому что я всегда хотел знать, как считать после 999 триллионов лол (и о да, ваш ответ был информативным)

К сожалению, вы все еще не правы. Вы предполагаете, что хеш-функция действительно случайна. Это не. Это означает, что вероятность столкновения выше.

Йорген Фог: И все законы физики тоже «неверны». Такой уровень педантизма не нужен, потому что он не меняет сколько-нибудь значимого ответа.

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

@yaauie Нет, это до смешного невозможно. Я говорю о создании 2 ^ 64 хэшей из 2 ^ 128 возможных. Это одна квадриллионная процента всех возможных сгенерированных хэшей.

Интуитивно, если мы проигнорируем парадокс дня рождения и просто посмотрим на примерное решение: добавить хэши 2^64 в список. Теперь добавьте к этому списку еще один хеш. Этот еще один хэш имеет вероятность столкновения 1 / 2^128, умноженную на 2^64, то есть еще один хэш имеет вероятность столкновения 1 / 2^64. Теперь добавьте в список еще один хеш 2^64, и вы должны получить коллизию. Проделайте тот же расчет для 2^63 (и обратите внимание на 2^63 + 2^63 = 2^64).

Значит, вы говорите, что есть шанс!

Могу ли я использовать этот алгоритм хеширования для имен файлов? Как хешировать содержимое файлов, установить имена этих файлов на их соответствующие хэши и сохранить их в каталоге? Максимальное количество файлов в каталоге одновременно составляет около 3000.

@AmirhoseinAl да, для всех практических целей он будет таким же уникальным, как и имена файлов.

значит ли это "не волнуйся"? В качестве первичного ключа моей БД используются хеши MD5!

@AnuragVohra Да, тебе не о чем беспокоиться. Наиболее вероятное столкновение - столкновение с землей астероидом.

Если мы возьмем случайные хэши 2^64 из 2^128, то согласно приближенной формуле из Атака на день рождения у нас будет 0,39 шанс на хотя бы одно значение выбирается более одного раза, тогда как для хэшей 2,2 * 10 ^ 19 для выбора у нас есть 50% шанс хотя бы одной коллизии (см. Таблицу в статье)

использование соли решило бы проблему пользовательской инженерии, не так ли?

Это зависит от того, как применяется соль. Это должен быть префикс данных, предоставленных пользователем, или, еще лучше, ключ для HMAC. Тем не менее, это, вероятно, хорошая идея - потренироваться в глубокой защите.

Обратите внимание, хотя SHA256 имеет длину 256 бит, вы можете снизить риск столкновений с длиной ключа, который вы храните, усекая SHA256 до меньшего количества бит, например. используйте SHA256, но усеките его до 128 бит (что более безопасно, чем использование MD5, даже если они имеют одинаковое количество бит).

Многие другие ответы говорят о вероятности столкновения при добавлении один дополнительных элементов. Я думаю, что мой ответ более полезен, потому что он говорит о том, что, вероятно, вся таблица имеет дублирование.

Это не имеет ничего общего с MD5 и неверно. Это все равно, что сказать, что если у вас 9 триллионов кошек, вероятность того, что у кого-то еще есть такая же кошка, составляет 1 из 9 триллионов. Ключевая проблема здесь в том, что вы можете получить один и тот же хэш с более чем одним значением.

@JoonasAlhonen - Да, это правда. И многие бедные люди используют это как предлог, чтобы купить еще один лотерейный билет, который они не могут себе позволить.