Почему слишком быстрая хэш-функция небезопасна?

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

Принятый в настоящее время ответ хорош, но я хотел бы кое-что добавить. «безопасность» в этом контексте является широким термином, и вы должны спросить, от какой угрозы вы хотите защититься. В большинстве дискуссий «столкновение» связано с поиском другого входа с идентичным выходом.Но в случае с паролем «быстрый хэш» проблематичен только для простого грубого форсирования. С помощью быстрого хэша злоумышленнику легко атаковать по словарю множество возможных входных данных в поисках совпадения с хешем.

Это не случай «быстрого хэша == слишком мало битов вывода», как спросил OP. Просто, если хэш слишком быстрый, слишком легко найти исходный ввод (а не коллизию), что делает его небезопасным.

Учитывая хеш-функцию, которая настраивается на «скорость» (возможно, итерации), увеличение скорости, с которой она хеширует, не Создайте больше столкновений. Проблема безопасности со слишком быстрым хэшем заключается в том, что при заданном количестве времени X более быстрый хеш будет генерировать большее количество выходных данных, поэтому у злоумышленника больше шансов найти столкновение.

ОП получил идею от пост на ютубе что спорит вокруг MD5.

Вот простой аргумент, если кто-нибудь смотрит видео.

Скорость не означает, что хеш-функция небезопасна, дизайн делает ее безопасной..

С годами исследователи находили слабые места в конструкции MD5 и со временем совершенствовали ее. После выпуска MD5 в 1992 году начались атаки, а в 2010 году Се и Дэнго Фэн объявили первая опубликованная одноблочная (512-битная) коллизия MD5. Конечно, улучшение процессоров и их циклов помогает проводить атаки быстрее, однако основной вклад вносят методологии атак. Учтите, что общая атака столкновений (атака дня рождения) требует $2^{64}$ Хэши MD5 с вероятностью успеха 1/2. Даже сегодня ни один обычный процессор не может $2^{64}$ в разумное время. С другой стороны, теперь у нас есть мгновенное столкновение для MD5, увидеть корками.

С другой стороны, Blake2 является очень быстрая хэш-функция, быстрее, чем MD5 и SHA-1, и не имеет атаки с расширением длины, поскольку использует ХАЙФА структура, исправления оформления МД. Это быстрее, чем MD5 и безопасно по крайней мере, в обозримой особенности. Его выходной размер достаточно безопасен для массивных параллельных атак или даже для Алгоритм квантового поиска Гровера. Серия Blake теперь имеет БЛЕЙК3, это параллельный хеш и очень быстро.

Что важно в скорости и ее отношении к безопасности, так это размер дайджеста. Общие атаки для атаки по прообразу, вторичной атаки по прообразу и общего столкновения: $2^n$,$2^n$, и $2^{n/2}$, соответственно. Если у вас есть 256- или 512-битный вывод, у вас все в порядке с общими атаками. Имейте в виду, что короткое поле ввода является проблемой для атак с предварительным изображением, и рекомендуется использовать HMAC.

PS: хеширование пароля (не требуется сопротивление столкновению), где мы хотим контролируемую скорость, твердость памятии количество потоков хэш-функции пароля. Надо читать канонический вопрос с нашего почтенного сайта, информационной безопасности.. Также, Аргон2 бумага, победитель конкурса хеширования паролей 2015 года, является хорошим выбором для чтения.

Последнее замечание: нужно тщательно определить свою проблему, чтобы они могли достичь безопасного дизайна. Нет настоящей безопасности, если вы не знаете своих рисков.

Давайте рассмотрим использование хеша для защиты пароля и рассмотрим пару примеров.

• Первый случай: у нас есть хэш-функция, которая принимает 1 секунда выполнить на обычном компьютере. Если злоумышленник имеет доступ к 1 миллиону компьютеров (например, через ботнет), он может совершать 1 миллион попыток в секунду, 86 миллиардов попыток в день. Но 8-символьный пароль с использованием старших, младших, цифр и символов составляет около 50 бит энтропии, поэтому при текущей производительности он по-прежнему будет занимать в среднем около 18 лет взломать этот пароль, даже с этим массивным ботнетом (конечно, через 18 лет все, вероятно, ускорится довольно сильно, поэтому он будет короче, но все же). В худшем случае это займет 36 лет.

• Второй случай: у нас есть хеш-функция, которая принимает 1 микросекунда выполнить. Тот же злоумышленник, использующий тот же ботнет с миллионом компьютеров, теперь может совершать на миллион попыток больше в секунду. Теперь это занимает 1125 секунд (менее 20 минут), чтобы попробовать каждый из примерно 2 ^ 50 возможных 8-символьных паролей. Так что в среднем примерно в половине случаев.

Если вы думаете, что ботнет с миллионом компьютеров — это фантастика, подумай еще раз.

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