Точки, в которых график пересекает целые значения r, св
Для того чтобы оценить степень снижения стойкости для большого количества итераций удобнее изучать не само число k, а обратное ему во сколько раз сократилось выходное множество, причем сразу в логарифмической шкале по основанию 2, чтобы единицами измерения стали биты: . Именно это число будет характеризовать снижение стойкости к полному перебору его необходимо вычесть из разрядности выбранной хеш-функции, чтобы получить разрядность эквивалентно стойкой хеш-функции. График зависимости r до 50.000 итераций приведен на рисунке:
Конечно, доля активных элементов продолжает с каждой итерацией уменьшаться, но не так быстро и катастрофично как в самом начале.
Доля множества значений, k
Номер итерации, i
Пусть во входном множестве было активно только kN элементов, где 0<k<1. Тогда вероятность НЕ выбора конкретного элемента равна , что по тому же следствию равно , а сужение выходного множества на этой итерации составит всего . Вот таблица первых 6 итераций:
Как только входное множество начинает быть заполненным не полностью (т.е. после второй итерации в первой модели угроз или сразу же во второй модели угроз (с атакой по словарю)), начинают работать другие формулы и другие закономерности. Это хорошо видно на том же рисунке для случая, если во входном множестве было всего 3 «активных» элемента. Вероятность «потерять» элемент (сузить выходное множество) резко уменьшается, т.к. теперь гораздо реже два и более отображения встречаются на одном и том же элементе.
Предел является следствием второго замечательного предела и равен , т.е. примерно 0,3679. Это вероятность того, что элемент в выходном множестве «станет серым». Попутно отметим, что при больших N (больше 232) степень «ухудшения» не зависит от разрядности хеш-функции. В итоге после первого повтора хеширования от пространства значений останется только около 63%. Если дальше всё пойдет также, то это будет катастрофой всего за 150 итераций мы «съедим» 100 бит выходного пространства, оставив, например, для MD5 только 2128-100=228 вариантов. К счастью, это не так.
Вероятность того, что конкретный элемент выходного множества НЕ будет выбран конкретным отображением (стрелкой) равна , соответственно, вероятность того, что он НЕ будет выбран ни одной из N стрелок равна или что тоже самое (благодаря свойству криптостойкой хеш-функции все N отображений события независимые в первом приближении).
Возьмем входное множество из N элементов и каждому из его объектов сопоставим в выходном множестве также из N объектов случайным образом какой-либо элемент (см. рис.). Очевидно, что несколько отображений покажут на одинаковые элементы, а, следовательно, останутся и элементы, к которым не подходит ни одной стрелки:
Одним из основных свойств/требований к криптостойким хеш-функциям является очень хорошая равномерность распределения выходных результатов. Это позволяет оперировать в потребующихся далее оценках обычной теорией вероятности и комбинаторикой.
Начнем с первого, более теоретического, вопроса: «сможет ли такое огромное пространство значений современной хеш-функции 2128 (MD5), 2160 (SHA-1), 2256 (ГОСТ Р 34.11, SHA-256) в результате многократного применения сузиться до такой степени, что коллизию к нему можно будет подобрать простым случайным поиском ?».
перебор по словарю.
перебор злоумышленником случайных входных наборов байт в надежде найти коллизию из-за сужения пространства значений («полный перебор»);
Снижение стойкости будем рассматривать в двух моделях угроз:
Поднявшаяся в дискуссия о криптостойкости многократного применения хеша над паролем (проскальзывавшая, кстати, и в других форумах), подтолкнула меня к этому немного математическому топику. Суть проблемы возникает из идеи многократной (1.000 и более раз) обработки пароля перед хранением каким-либо криптостойким алгоритмом (чаще всего хеш-функцией) с целью получить медленный алгоритм проверки, тем самым эффективно противостоящий brute force-у в случае перехвата или кражи злоумышленником этого значения. Как совершенно верно отметили хабрапользователи (автор первой статьи), и , идея не нова и ею пользуются разработчики оборудования Cisco, архиватора RAR и многие другие. Но, поскольку хеширование операция сжимающая множество значений, возникает вполне закономерный вопрос а не навредим ли мы стойкости системы? Попытка дать ответ на этот вопрос
Криптостойкость 1000-кратного хеширования пароля
Криптостойкость 1000-кратного хеширования пароля / Хабрахабр
Комментариев нет:
Отправить комментарий