многократный хэш

[Victor Sudakov]

Коллеги,

В описании некоторых протоколов приходилось встречаться с упоминанием,
что например хэш от пароля вычисляется многократно (как я понял, из
хэша опять делается хэш и так 2^n раз). Можете объяснить для чайника,
зачем так делается?

[Artem Chuprina]

Victor Sudakov @ Tue, 11 Aug 2009 13:07:41 +0000 (UTC):

VS> В описании некоторых протоколов приходилось встречаться с
VS> упоминанием, что например хэш от пароля вычисляется многократно
VS> (как я понял, из хэша опять делается хэш и так 2^n раз). Можете
VS> объяснить для чайника, зачем так делается?

Как правило, там, где это встречается, оно обосновывается как удорожание
перебора. Т.е. ты сам тратишь больше времени на то, чтобы прожевать
пароль, но и брутфорсер будет его тратить пропорционально больше.

[Andrew A. Mezhutkov]

Tue Aug 11 2009 20:11, Artem Chuprina wrote to Victor Sudakov:

AC> From: Artem Chuprina <ran+***@ran.pp.ru>

AC> Victor Sudakov @ Tue, 11 Aug 2009 13:07:41 +0000 (UTC):

VS>> В описании некоторых протоколов приходилось встречаться с
VS>> упоминанием, что например хэш от пароля вычисляется многократно
VS>> (как я понял, из хэша опять делается хэш и так 2^n раз). Можете
VS>> объяснить для чайника, зачем так делается?

AC> Как правило, там, где это встречается, оно обосновывается как удорожание
AC> перебора. Т.е. ты сам тратишь больше времени на то, чтобы прожевать
AC> пароль, но и брутфорсер будет его тратить пропорционально больше.

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

шлите деньги факсом

[Dmitry Sklyarov]

Hello, Andrew!
You wrote to Artem Chuprina on Fri, 14 Aug 2009 06:38:58 +0000 (UTC):

AC>> From: Artem Chuprina <ran+***@ran.pp.ru>

AC>> Victor Sudakov @ Tue, 11 Aug 2009 13:07:41 +0000 (UTC):

VS>>> В описании некоторых протоколов приходилось встречаться с
VS>>> упоминанием, что например хэш от пароля вычисляется многократно
VS>>> (как я понял, из хэша опять делается хэш и так 2^n раз). Можете
VS>>> объяснить для чайника, зачем так делается?

AC>> Как правило, там, где это встречается, оно обосновывается как
AC>> удорожание перебора. Т.е. ты сам тратишь больше времени на то, чтобы
AC>> прожевать пароль, но и брутфорсер будет его тратить пропорционально
AC>> больше.

AAM> что в действительности совсем не факт. похожий пример из истории - в
AAM> начале прошлого века турки использовали последовательно ДВЕ таблицы
AAM> подстановок на одном ключе. т.е. зашифровали сообщение, потом его
AAM> перешифровали еще раз. кололась криптограмма, как легко догадаться, в
AAM> один этап.

Hу, это сильно зависит от того, что и как мы повторяем :)

Понятно, что для обычной подстановки можно Enc(key2, Enc(key1, msg)) свести
к Enc(key3, msg), а дальше колоть статистическим анализом.

Hо даже с современными шифрами, для которых сведене двух ключей к одному не
работает, plaintext-атака на двойное шифрование будет требовать максимум не
2 ** (nBits(key1) + nBits(key2)), а лишь 2 ** nBits(key1) + 2 ** nBits(key2)
операций, если устроить встречу посередине.

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

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


With best regards, Dmitry Sklyarov . E-mail: ***@elcomsoft.com

[Andrew A. Mezhutkov]

Fri Aug 14 2009 12:30, Dmitry Sklyarov wrote to Andrew A. Mezhutkov:

О, привет!
давненько не встречались!

DS> Hу, это сильно зависит от того, что и как мы повторяем :)
Дим, я как бы в курсе... собственно от этого и предостерегаю.
;-)

DS> Понятно, что для обычной подстановки можно Enc(key2, Enc(key1, msg))
DS> свести
DS> к Enc(key3, msg), а дальше колоть статистическим анализом.

вообще то строго говоря, чтобы свести как ты говоришь, надо чтобы Enc1(key1,
Enc2(key1, msg)) было группой (обрати внимание на изменение в формуле). пару
лет назад мы с Сергеем Леонтьевым на эту тему общались вроде даже здесь.
изменения связаны с тем, что "где набрать стока ключей". а любая (ну почти
любая) модификация ключа на циклах ничего не даст, так как мы знаем процедуру
хэширования, получения ключа и проч. бай дефинишен знаем
...

DS> В случае же многократного хеширования - если хеш хороший (необратимый),
криптографически стойкий

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

шлите деньги факсом

[Serguei E. Leontiev]

Здравствуйте, Andrew,
Вы писали к Dmitry Sklyarov от Fri, 14 Aug 2009 09:41:44 +0000 (UTC):

[...]
AAM> в формуле). пару лет назад мы с Сергеем Леонтьевым на эту тему
AAM> общались вроде даже здесь. изменения связаны с тем, что "где набрать
AAM> стока ключей". а любая (ну почти любая) модификация ключа на циклах
AAM> ничего не даст, так как мы знаем процедуру хэширования, получения
AAM> ключа и проч. бай дефинишен знаем
AAM> ...
DS>> В случае же многократного хеширования - если хеш хороший
DS>> (необратимый),
AAM> криптографически стойкий

Э-э, батеньки, этого недостаточно.

Вспоминая известную проблему PKCS#12 (точнее PKCS#5).

Есть ещё одна проблема, или дополнительные требования на хэш функции, обычно
не предъявляемые к ним.

Ясное дело, практически любая известная нам хэш функция H(x) является
сжимающим преобразованием (сюръективным). А всяческие методы анализа,
например, тривиальный "парадокс дней рождений", зависят от мощности области
значений. Соответственно, H^n(x) является значительно менее стойкой
хэш-функцией, чем H(x), что и ограничивает величину n.

Использование PRF(p,x) в качестве H(x) слегка улучшает ситуацию, т.к.
позволяет уменьшить n в два раза при той же вычислительной сложности
(возможно, для совсем уж несчастных хэш функций, он даже сможет заметно
снизить скорость сходимости к неизбежному циклу и/или увеличить его длину).

Как мне кажется (с потолка), для ГОСТ Р 34.11-94, n должно быть ограничено
2^14-2^18, т.е. на моём настольном компьютере можно будет обеспечить
скорость подбора около 100 паролей в секунду, при максимальном оптимизме.

В общем, на мой взгляд, для PKCS#12 и прочих методов получения ключа по
паролю надо разрабатывать сильно другие хэш функции, например, с
использованием эллиптических кривых, типа H(x) = VKO(UKM, x, P). Что бы,
хотя бы создать видимость защиты и/или аутентификации пользователя. Или,
наконец, констатировать смерть паролей.

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Victor Sudakov]

Post by Artem Chuprina
VS> В описании некоторых протоколов приходилось встречаться с
VS> упоминанием, что например хэш от пароля вычисляется многократно
VS> (как я понял, из хэша опять делается хэш и так 2^n раз). Можете
VS> объяснить для чайника, зачем так делается?
Как правило, там, где это встречается, оно обосновывается как удорожание
перебора. Т.е. ты сам тратишь больше времени на то, чтобы прожевать
пароль, но и брутфорсер будет его тратить пропорционально больше.

Hашел вот http://en.wikipedia.org/wiki/Key_strengthening