id: Гость   вход   регистрация
текущее время 23:57 28/03/2024
Автор темы: Мухтар, тема открыта 21/03/2008 23:25 Печать
Категории: криптография, алгоритмы
https://www.pgpru.com/Форум/Криптография/ВариантУлучшенияКриптостойкостиХешаНаОсновеРандомизацииАлгоритма
создать
просмотр
ссылки

Вариант улучшения криптостойкости хеша на основе рандомизации алгоритма


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


 
Комментарии
— ntldr (22/03/2008 05:18)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Не хочу вступать в споры по поводу оригинальности и целесообразности такой идеи, но мне она кажется сомнительной.
Пишите реализацию и отправляйте ее на конкурс SHA-3. Если ваш "рандомизированый" алгоритм победит, то будем его юзать.
— Гость (22/03/2008 09:46)   <#>
У меня тоже есть идея – шифруем блочным шифром и все зашифрованные блоки XOR-им друг с другом. И зачем рандом?
— ntldr (22/03/2008 10:47)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
У меня тоже есть идея – шифруем блочным шифром и все зашифрованные блоки XOR-им друг с другом. И зачем рандом?

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

Вобще, все это мне напоминает предложения "давайте наворотим чего-нибудь, авось враг это не разгребет". Хотя с точки зрения того, что криптография это наука о незнании, такой подход может иметь смысл. Но прежде чем "воротить что-нибудь", следует изучить то что сделано до нас, иначе 99.9% вероятность что получится фигня.
— unknown (22/03/2008 12:05)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Хэш – это универсальная конструкция. Я подозреваю, что Вы предусматриваете только одно использование хэша – хэширование сообщения перед подписью.

Но ведь у него сотни других применений, где рандомизация не может быть осуществлена или даже вредна.

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

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

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

Где-то это даже полезно, но в большинстве случаев сужает область использования хэшей и абсолютно неприемлимо.

Предлагаю также ознакомиться с требованиями NIST на SHA-3, там всё грамотно изложено. Рандомизация предусмотрена как выборочная опция.
Только думаю, что доказательство простейшего утверждения для конкретного хэша, что для поиска H(M1, r1) = H(M2, r2) нужно n шагов для атаки при условии, что r не контролируется атакующим, потребует много страниц сложнейшей теоретической работы. Тем более, что в отличии от блочных шифров, теория хэшей проработана плохо.
— SATtva (22/03/2008 16:07)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Где-то это даже полезно, но в большинстве случаев сужает область использования хэшей и абсолютно неприемлимо.

Keyed HMAC не есть то, что предлагает автор вопроса?
— ntldr (22/03/2008 17:03)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Keyed HMAC не есть то, что предлагает автор вопроса?

Если я правильно понял, то автор предлагает усложнение самого алгоритма, т.е. изменение поведения раунд-функции на основе дополнительного ключа.
— Мухтар (22/03/2008 17:55)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
Я новичек в криптографии, и не пытаюсь создать математику. Просто логику.

Во-первых, почему сжатие, так это потому что можно анализировать коллизии многократно прогоняя хеширование на похожих повторяющихся данных. Конечно, 0100000 и 0010000 хеш обязан выловить, но вот 000 и 111 уже может и повторить в одном значении хеша. Например, некоторые любительские реализации известных протоколов шифрования не выдерживают атаку сжатием, когда зашифрованные bmp и jpg сжимаются по-разному.

Во-вторых, почему рандомизация выборки исходных данных (раунд-функция?) чтобы:
1) Периодический рефреш хеша на сервере заставлял атакующего повторять атаку
2) Сложнее находить коллизии, так как при рандомизации, алгоритм нахождения коллизий одного и того же файла, возможно, будет различаться. Хотя это нужно еще подумать.
— Paran0ik (23/03/2008 02:19)   профиль/связь   <#>
комментариев: 88   документов: 13   редакций: 3
получается что-то типо "плавающего" хеша чтоли?
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3