id: Гость   вход   регистрация
текущее время 08:41 29/03/2024
Автор темы: Гость, тема открыта 23/09/2014 07:18 Печать
Категории: криптография, алгоритмы, хэширование
http://www.pgpru.com/Форум/Криптография/CTRModeКакХешФункция
создать
просмотр
ссылки

CTR mode как хеш функция


Берем блочный шифр. Подставляем исходное сообщение в качестве ключа в шифр, каскадируя нужное число блоков, чтобы вобрать все сообщение. Далее, подаем на вход получившегося каскада счетчик, т.е. используем в CTR mode. Теперь можно генерировать хеш произвольного размера. Очевидно что данную базовую схему можно переделать а-ля Merkle Damgard и всяко разно параллельно последовательно, разбивая на блоки и произвольно подстраивая требования скорость/память/стойкость.


Мне не встречалось упоминаний использования CTR моды как хеш функции. Нет ли здесь концептуальной или патентной проблемы?


ZAS


 
Комментарии
— unknown (23/09/2014 17:52, исправлен 23/09/2014 17:56)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


В лучшем случае современные шифры кое-как противостоят атакам со связанными ключами, но не атакам с известными/подобранными/адаптивно подобранными ключами.



Даже в случае идеального шифра, стойкость получающегося по такой конструкции хэша будет не выше стойкости внутреннего состояния, т.е. размера блока используемого шифра. Т.е. для шифра со 128-битным блоком будет 64-битная стойкость к коллизиям. Смысл каскадирования только по ключу со счётчиком теряется. По этому в Дамгарде-Меркле и его более продвинутых аналогах (не говоря уже о бесключевых перестановках в губчатых конструкциях) используют шифры с размером блока в 256-512-1024 бита.


Подозреваю, что можно нагородить преобразование 128-бит блочного шифра в широкий блок через три прохода со сцеплением блоков «вправо-влево-вправо» и даже попытаться создать из этого хэш, но если вы не Беллэйр-Рогвей или их последователь, то лучше этого не делайте. Если такая идея лишь не «сбивается на подлёте», то без формального анализа это всё равно ни о чём.

— ZAS (23/09/2014 18:35)   <#>
В лучшем случае современные шифры кое-как противостоят атакам со связанными ключами, но не атакам с известными/подобранными/адаптивно подобранными ключами.


Хорошее наблюдение; и насчет слабых ключевых расписаний тоже верно.

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


Поясните.

Для 128-битного блока существует (2^128)! вариантов; пространство данных CTR хеша перекрывает ничтожную часть этого множества.

http://www.zas-comm.ru
— unknown (23/09/2014 21:19, исправлен 23/09/2014 21:30)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Чтобы не было оверхэда по памяти и для соблюдения поточности, я понимаю, что на практике полагается сразу пошифровать счётчик (начальное значение все нули или const) первым ключом-блоком от сообщения, результат ксорить с counter+1, затем получившееся подавать на вход шифрования ещё одного ключа-блока сообщения, ксорить выход шифрования с counter+2 и так растягивать потоком в каскад размером с округления до целого (число бит сообщения) / (128 бит) + 1?



Именно поэтому.


В вашей конструкции предлагается использовать два входа в блочный шифр: ключевой для сообщения (которым может манипулировать противник) и открытый текст для счётчика (которым не зависит от сообщения и только пассивно известен противнику). Противник в первом блоке перебирает 264 ключей и получает коллизию: два разных ключа дадут одинаковый выход шифртекста при одинаковом входе открытого текста (счётчика). Нужно ещё посчитать вероятности подбора циклов через много раундов каскада. И это для идеального шифра, без учёта внутренних уязвимостей. Изменением конструкции без увеличения размера блока это не решается: это информационно-теоретическое представление, теорвер, комбинаторика, отношение множеств, через что хотите можете это формально доказывать. Можно напортачить с построением конструкций так, что коллизий вообще не будет, тогда хэш, в котором коллизий вообще нет, ломается ещё проще, чем тот, в котором количество хэшей строго равно 2b/2, b – размер блока внутреннего состояния.


Есть такая картинка для Sponge-хэшей:


Плоское пространство атак (26 Кб)

Но всех других это также касается, только для разных конструкций есть разное понимание эффективно используемой ёмкости внутреннего состояния c (capacity). Но в любом случае, нельзя выйти за c / 2, стойкость лимитируется размером внутреннего состояния, она может быть даже меньше его половины (при его неидеальности или неэффективности использования, как в Sponge, когда эффективный capacity меньше внутреннего состояния всей перестановки), но не может быть выше.


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

— ZAS (23/09/2014 23:25)   <#>
A, вот вы про что. Дык это очевидно: если мы хешируем сообщение функцией с размером состояния b, и получаем на выходе хеш размером nb, то мы можем отдельно находить прообразы по каждому выходному блоку b за 2^b работы. Чтобы найти прообраз для всего хеша nb, потребуетcя 2^(nb/2) работы (birthday paradox), a не 2^nb, как было бы наивно полагать. При фиксированном размере состояния невозможно придумать никагого волшебства, вы правы.

Насчет схемы хеша CTR mode с использованием сообщения как ключа: есть концептуальная проблема с slide attack (функции шифрования должны быть гарантированно разными в каждом каскаде). Кроме того, технические проблемы с связанными ключами и слабыми ключами.

Наконец, это азы не только хэширования, но и шифрования:


Чужие мысли плохо помогают при отсутствии собственных.
— Гость (24/09/2014 06:22)   <#>

Мне одному представляется, что ZAS в конец охренел? Что ж ты тут сидишь и спрашиваешь советов, коль своих мыслей громадьё?
— ZAS (25/09/2014 08:37)   <#>
Подозреваю, что можно нагородить преобразование 128-бит блочного шифра в широкий блок через три прохода со сцеплением блоков «вправо-влево-вправо» и даже попытаться создать из этого хэш, но если вы не Беллэйр-Рогвей или их последователь, то лучше этого не делайте. Если такая идея лишь не «сбивается на подлёте», то без формального анализа это всё равно ни о чём.


Кстати о широких блоках. В том, что я читал, используют циклический сдвиг на пол-блока. То есть получается линейная диффузия на блок за раунд; соответственно для полной диффузии нужно N раундов, где N – число блоков из которых состоит широкий блок. Общее количество операций получается порядка N^2. Неэффективно. Очевидное решение – собирать полублоки через половину широкого блока. Тогда диффузия экспоненциальная и требуется log2(N) раундов.

Примерно так:



Нечто вроде транспонирования. Работает для любого N. Такой вариант сложнее проанализировать, чем со сдвигом.
Применяется ли на практике или сразу "cбивается на подлете" ?
— unknown (25/09/2014 14:19)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Судя по квадратичным расходам для полной диффузии на размер MDS-матриц — это так и есть, причём, возможно, формально доказуемо проще всего, как достаточное условие для полной диффузии.

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

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


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

  1. Для разных режимов шифрования.
  2. Для построения блочных шифров.
  3. Для хэшей.

Требования к строгой неразличимости от идеальной модели, скорее всего, возрастают от п.1 к п.3.


Если знания из какой-то области представляют проблему для собственных мыслей, это скорее повод начать думать в другом направлении, куда можно более конструктивно применить манию энергию своего изобретательства.
— ZAS (25/09/2014 19:38)   <#>
И сходу непонятно, какие типы неидеальности допустимы:


Это как раз более-менее понятно.

Для разных режимов шифрования.


Достаточно чтобы разность на входе любого из N блоков приводила к разности на выходе любого другого блока с вероятностью не хуже 2^размер блока.
Для построения блочных шифров.


Чтобы дифференциальная характеристика от общего входа до общего выхода имела среднекв. отклонения от среднего, не большее чем 2^(размер ключа/2).

Для хэшей.


То же, но на размер хеша.

http://www.zas-comm.ru
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3