увиличивают ли итерации кол-во коллизий хеша?
собственно сабж..имеем 1000 итераций хеша, у каждого из этой тысячи хешей есть свои коллизии, они могут повторятся, но все же – получаем ли мы увеличение кол-ва коллизий или конечный хеш можно рассматривать как любой другой и коллизий у него будет столько же, сколько и у обычного?
комментариев: 9796 документов: 488 редакций: 5664
теоретически, вероятность коллизий у него действительно будет выше. Если на одном из шагов Yn = H ( Xn-1 ) получиться, что Yn равно какому-либо из предыдущих значений за 1000-n шагов, то за оставшиеся шаги цепочка зациклится.
Т.е. энтропия хэша после множества итераций снижается, появляются более вероятные значения, вероятность коллизий возрастает.
Но хотя, энтропия хэша снижается, практического значения это не имеет.
Во-первых, вероятность такого события даже при сотнях тысяч операций ничтожно мала и при любых разумных вычислениях снижение энтропии незначительно.
Во-вторых, трудно представить, что противник может рассчитать каким-то способом низкоэнтропийные цепочки или вычислить конечные наиболее вероятные значения хэшей после n итераций, по крайней мере вычислительные затраты на это будут такие же как и на обычные атаки.
Если только для каких-то укороченных значений хэшей можно создать базу предвычисленных значений или использовать это совместно с какими-то экзотическими теоретическими видами криптоанализа против нестойких хэшей.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 155 документов: 20 редакций: 5
Тем не менее, я склонен считать что на практике такая зависимость не подтвердится. Это связано с тем, что коллизии обычно находят на мощности исходного поля, значительно большего чем длина результирующей хеш-функции.
Я не думаю, что разработчики хеш-ранудов не позаботились о простой перестановке, дающей эффективность, аналогичную прибавлению к хешу значения счетчика и перестановке, как это делается в блочном кифере.
комментариев: 9796 документов: 488 редакций: 5664
И получим различитель, когда хэш-функция будет себя вести лучше чем идеальная псевдослучайная функция? Как раз хэш не надо делать таким как шифр. Нельзя свойства PRP (перестановки) переносить на PRF (функции). Речь идёт как раз об идеальной PRF, а не о конкретной хэш-функции. В вопросе имелось ввиду не количество раундов внутри самой функции, а многократное хэширование.
К сожалению не могу найти работу, где уже готовая формула приведена под этот случай. В вышеприведённой работе про KDF кое-что похожее, но не то.
комментариев: 155 документов: 20 редакций: 5
Unknown, не могли бы вы пояснить данную терминологию?
Я это так и понял. Действительно, хеш-функцию нет смысла применять при повторном хешировании хеша. Потому что смысл хеш-функции не в невозможности обратить вычисления, а смысл в отсутствии коллизионного крипто-анализа. Т.е. я бы наверное для защиты от брутфоса паролей применял не повторное хеширование, а однократное хеширование + многократное шифрование со счетчиком, причем размер хеша должен быть спопоставим с размером блока.
Мне кажется что многократные хеши могут иметь коллизии на размерах исходных данных, равных размеру результирующего хеша, если разработчики хеш-функции об этом не позаботились, ведь смысл хеш-функции в срезе именно бОльших блоков данных, имхо.
комментариев: 9796 документов: 488 редакций: 5664
Зато нашёл "Theoretical analysis of hash iteration"
Приложение "А" в конце работы.
комментариев: 155 документов: 20 редакций: 5
Тогда свойство хеша в его нестойкости при большом числе итераций – это свойство, обусловленное тем что об обратном не позаботились разработчики.
И это имеет практическое значение.
Кто мешает применять после первой итерации вместо повтора, итерации с невырождающимся гсч? Это вопрос, поскольку я не знаю, уменьшится ли стойкость при таком алгоритме.
И кстати, в указанной Вами статье про соль упоминается.
комментариев: 9796 документов: 488 редакций: 5664
Вот здесь весь ключевой момент. Хэш должен вести себя как идеальная псевдослучайная функция (PRF). Никаких дополнительных критериев дизайна в него вносить не нужно. Он должен давать коллизии при 2n/2, а при увеличении числа итераций и вероятность коллизии должна возрастать. Иначе получим тривиальный (хотя непрактичный) различитель: в одном чёрном ящике будет наш хэш, в другом PRF (или "случайный оракул"). Если хэш при очень большом числе запросов будет давать меньше коллизий, чем идеальная псевдослучайная функция, то мы сможем их различать. В каком-то другом протоколе это может быть ненужно и вести к взлому.
Кстати ваше предложение не входит в число критериев NIST на конкурс SHA-3, которые можете посмотреть в наших новостях.
Тут или хэш должен быть таким как есть, а все дополнительные навороты делаться в конкретном протоколе и их стойкость доказываться отдельно и конкретно для этого протокола.
Или нужно изобретать хэш со множеством переключателей режимов использования (как хэш функцию Skein ).