— unknown (18/12/2008 09:47, исправлен 18/12/2008 09:53)   

получаем ли мы увеличение кол-ва коллизий или конечный хеш можно рассматривать как любой другой и коллизий у него будет столько же, сколько и у обычного?

теоретически, вероятность коллизий у него действительно будет выше. Если на одном из шагов Y_n = H ( X_n-1 ) получиться, что Y_n равно какому-либо из предыдущих значений за 1000-n шагов, то за оставшиеся шаги цепочка зациклится.

Т.е. энтропия хэша после множества итераций снижается, появляются более вероятные значения, вероятность коллизий возрастает.

Но хотя, энтропия хэша снижается, практического значения это не имеет.

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

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

— unknown (18/12/2008 10:26)   
Вообще, многократное хэширование используется вроде бы только для получения ключей из паролей, теория рассмотрена например здесь^[link1]. Обычно простого многократного хэширования стараются избегать, используют рандомизированное, со счётчиком или ещё какие-то дополнения, если нужно для практических целей, то лучше делать по стандартам на KDF.

— Мухтар (18/12/2008 12:32)   
Теоретически, зависимость количества коллизий от количества итераций может как подтвердится, так и не подтвердится. Тут нужно проводить анализ алгоритма хеш-функции.

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

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

— unknown (18/12/2008 13:36, исправлен 18/12/2008 13:39)   

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

И получим различитель, когда хэш-функция будет себя вести лучше чем идеальная псевдослучайная функция? Как раз хэш не надо делать таким как шифр. Нельзя свойства PRP (перестановки) переносить на PRF (функции). Речь идёт как раз об идеальной PRF, а не о конкретной хэш-функции. В вопросе имелось ввиду не количество раундов внутри самой функции, а многократное хэширование.

К сожалению не могу найти работу, где уже готовая формула приведена под этот случай. В вышеприведённой работе про KDF кое-что похожее, но не то.

— Мухтар (18/12/2008 14:05)   

И получим различитель, когда хэш-функция будет себя вести лучше чем идеальная псевдослучайная функция?

Unknown, не могли бы вы пояснить данную терминологию?

В вопросе имелось ввиду не количество раундов внутри самой функции, а многократное хэширование.

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

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

— unknown (18/12/2008 16:01, исправлен 18/12/2008 16:03)   
Про терминологию написал длинный пост, но он в форум не отправился и не сохранился.

Зато нашёл "Theoretical analysis of hash iteration"

Приложение "А" в конце работы^[link2].

— Мухтар (18/12/2008 17:28, исправлен 18/12/2008 17:37)   
Прочитал. Я уже об этом написал выше.

ведь смысл хеш-функции в срезе именно бОльших блоков данных, имхо

Тогда свойство хеша в его нестойкости при большом числе итераций – это свойство, обусловленное тем что об обратном не позаботились разработчики.

И это имеет практическое значение.

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

И кстати, в указанной Вами статье про соль упоминается.

— unknown (19/12/2008 09:18)   

Тогда свойство хеша в его нестойкости при большом числе итераций – это свойство, обусловленное тем что об обратном не позаботились разработчики.

Вот здесь весь ключевой момент. Хэш должен вести себя как идеальная псевдослучайная функция (PRF). Никаких дополнительных критериев дизайна в него вносить не нужно. Он должен давать коллизии при 2^n/2, а при увеличении числа итераций и вероятность коллизии должна возрастать. Иначе получим тривиальный (хотя непрактичный) различитель: в одном чёрном ящике будет наш хэш, в другом PRF (или "случайный оракул"). Если хэш при очень большом числе запросов будет давать меньше коллизий, чем идеальная псевдослучайная функция, то мы сможем их различать. В каком-то другом протоколе это может быть ненужно и вести к взлому.

Кстати ваше предложение не входит в число критериев NIST на конкурс SHA-3^[link3], которые можете посмотреть в наших новостях.

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

Или нужно изобретать хэш со множеством переключателей режимов использования (как хэш функцию Skein^[link4] ).