Использование хэш-функций
Mikael Mylnikov
Не думал, что буду в эхе обсуждать собственные доморощеные идеи :-), но
пришла в голову одна мысль, и чтобы от нее избавиться, спешу поделиться с
общественностью. Возможно, что это известно и давно применяется, но я пока
такого не встречал.
Стокость хэш функций, учитывая атаку "дня рождения", определяется как
половина длины хэша. Это заставило отказаться от 128 битных функций в пользу
160 битных, а впереспективе переход на 256 бит. Можно использовать другой
способ - к каждому сообщению перед хэшированием добавлять "соль" - несколько
случайных байт, которые потом добавляются к хэш-сумме и вместе с ней
подписываются каким-либо ассимметричным алгоритмом. Рассмотрим простейший
вариант - к каждому сообщению добавляются два случайных бита. Злоумышленник
выполняет обычную атаку "дня рождения", но из всех пар с одинаковым хэшем
подходят только те, у которых совпадают биты "соли" (они включены в подпись
и не могут варьироваться), в среднем одна пара из четырех, причем атакующий
не может знать заранее, какая пара будет выбрана, и, получив искомую пару с
одинаковым хэшем, имеет вероятность 1/4 что именно эта "соль" окажется в
подписи. Таким образом, увеличив длину подписи на два бита мы уменьшаем
вероятность взлома в 4 раза, в то время как увеличение длины хэша на два
бита всего лишь удвоит объем работ. Таким образом, добавляя к сообщению 64
бита "соли", мы достигаем для 128 битной хэш функции эффективной стойкости
128 бит при общей длине хэш+соль 192 бит вместо 256 при стандартном подходе.
Такое применение абсолютно не затрагивает алгоритм самих хэш-функций, да и
не может быть в него включено, потому что требует генератора случайных
чисел. Но все нормальные реализации _уже_ снабжены такими генераторами, и
значения хэша перед подписью обязательно дополняются большим случайным
числом, значит внедрение такого метода требует минимальных изменений в
программах (причем не затрагивающих чувствительные алгоритмические части)
при значительном повышении стойкости. Длина соли в принципе не должна
превышать половину длины хэша, все равно стойкость не может превышать полный
перебор хэшей.
С уважением, Михаил.
Stanislav Asanov
Mikael Mylnikov wrote:
> Hе думал, что буду в эхе обсуждать собственные доморощеные идеи
> :-), но пришла в голову одна мысль,
Спешу огорчить.
> Стокость хэш функций, учитывая атаку "дня рождения",
> определяется как половина длины хэша.
...
> Можно использовать другой способ - к каждому сообщению перед
> хэшированием добавлять "соль" - несколько случайных байт,
Hеприятность в том, что для некоторых типов нарушителей этот способ
не работает. Атака "дней рождений" наиболее эффективна в том случае,
если я _сам_ генерирую два сообщения с одинаковым хэшом, например,
расписки на 10000$ и 100$. Потом я пересылаю тебе одно (на 10000$),
а когда дело доходит до суда, предъявляю другое.
Соответственно, при генерации я могу устроить так, что "случайная"
соль станет неслучайной (одинаковой). Финиш.
WBR,
(С)танислав.
Mikael Mylnikov
Hello, "Stanislav Asanov" ! You wrote:
> Привет!
>
> Mikael Mylnikov wrote:
> > Hе думал, что буду в эхе обсуждать собственные доморощеные идеи
> > :-), но пришла в голову одна мысль,
>
> Спешу огорчить.
Рад, что ты откликнулся. На лавры первооткрывателя я уже давно не претендую
:-) Хотелось разобраться.
>
> > Стокость хэш функций, учитывая атаку "дня рождения",
> > определяется как половина длины хэша.
> ...
> > Можно использовать другой способ - к каждому сообщению перед
> > хэшированием добавлять "соль" - несколько случайных байт,
>
> Hеприятность в том, что для некоторых типов нарушителей этот способ
> не работает. Атака "дней рождений" наиболее эффективна в том случае,
> если я _сам_ генерирую два сообщения с одинаковым хэшом, например,
> расписки на 10000$ и 100$. Потом я пересылаю тебе одно (на 10000$),
> а когда дело доходит до суда, предъявляю другое.
>
> Соответственно, при генерации я могу устроить так, что "случайная"
> соль станет неслучайной (одинаковой). Финиш.
Да, ты прав. Моя схема работает только тогда, когда генерит сообщения один,
а подписывает другой.
С уважением, Михаил.