CTR mode как хеш функция
Берем блочный шифр. Подставляем исходное сообщение в качестве ключа в шифр, каскадируя нужное число блоков, чтобы вобрать все сообщение. Далее, подаем на вход получившегося каскада счетчик, т.е. используем в CTR mode. Теперь можно генерировать хеш произвольного размера. Очевидно что данную базовую схему можно переделать а-ля Merkle Damgard и всяко разно параллельно последовательно, разбивая на блоки и произвольно подстраивая требования скорость/память/стойкость.
Мне не встречалось упоминаний использования CTR моды как хеш функции. Нет ли здесь концептуальной или патентной проблемы?
ZAS
комментариев: 9796 документов: 488 редакций: 5664
Такое предлагали не столько для хэширования (хотя что-то похожее и для хэширования тоже), сколько для некоторых режимов шифрования (сцеплять блоки по ключевому входу) и аутентификации. Идею зарезали на подходе по причине того, что очень медленно и небезопасно. Криптографы негласно постановили, что атаки с известным/подобранным ключом хороши для теоретических изысканий для сравнения шифра с идеальной моделью, но на практике от них следует держаться подальше (просто избегать режимов, где они могли бы проявиться). Создатели шифров этими атаками часто сознательно пренебрегают и создают шифры с заведомо слабым (неидеальным) по некоторым параметрам ключевым расписанием.
В лучшем случае современные шифры кое-как противостоят атакам со связанными ключами, но не атакам с известными/подобранными/адаптивно подобранными ключами.
Даже в случае идеального шифра, стойкость получающегося по такой конструкции хэша будет не выше стойкости внутреннего состояния, т.е. размера блока используемого шифра. Т.е. для шифра со 128-битным блоком будет 64-битная стойкость к коллизиям. Смысл каскадирования только по ключу со счётчиком теряется. По этому в Дамгарде-Меркле и его более продвинутых аналогах (не говоря уже о бесключевых перестановках в губчатых конструкциях) используют шифры с размером блока в 256-512-1024 бита.
Подозреваю, что можно нагородить преобразование 128-бит блочного шифра в широкий блок через три прохода со сцеплением блоков «вправо-влево-вправо» и даже попытаться создать из этого хэш, но если вы не Беллэйр-Рогвей или их последователь, то лучше этого не делайте. Если такая идея лишь не «сбивается на подлёте», то без формального анализа это всё равно ни о чём.
Хорошее наблюдение; и насчет слабых ключевых расписаний тоже верно.
Поясните.
Для 128-битного блока существует (2^128)! вариантов; пространство данных CTR хеша перекрывает ничтожную часть этого множества.
http://www.zas-comm.ru
комментариев: 9796 документов: 488 редакций: 5664
Чтобы не было оверхэда по памяти и для соблюдения поточности, я понимаю, что на практике полагается сразу пошифровать счётчик (начальное значение все нули или const) первым ключом-блоком от сообщения, результат ксорить с counter+1, затем получившееся подавать на вход шифрования ещё одного ключа-блока сообщения, ксорить выход шифрования с counter+2 и так растягивать потоком в каскад размером с округления до целого (число бит сообщения) / (128 бит) + 1?
Именно поэтому.
В вашей конструкции предлагается использовать два входа в блочный шифр: ключевой для сообщения (которым может манипулировать противник) и открытый текст для счётчика (которым не зависит от сообщения и только пассивно известен противнику). Противник в первом блоке перебирает 264 ключей и получает коллизию: два разных ключа дадут одинаковый выход шифртекста при одинаковом входе открытого текста (счётчика). Нужно ещё посчитать вероятности подбора циклов через много раундов каскада. И это для идеального шифра, без учёта внутренних уязвимостей. Изменением конструкции без увеличения размера блока это не решается: это информационно-теоретическое представление, теорвер, комбинаторика, отношение множеств, через что хотите можете это формально доказывать. Можно напортачить с построением конструкций так, что коллизий вообще не будет, тогда хэш, в котором коллизий вообще нет, ломается ещё проще, чем тот, в котором количество хэшей строго равно 2b/2, b – размер блока внутреннего состояния.
Есть такая картинка для Sponge-хэшей:
Но всех других это также касается, только для разных конструкций есть разное понимание эффективно используемой ёмкости внутреннего состояния c (capacity). Но в любом случае, нельзя выйти за c / 2, стойкость лимитируется размером внутреннего состояния, она может быть даже меньше его половины (при его неидеальности или неэффективности использования, как в Sponge, когда эффективный capacity меньше внутреннего состояния всей перестановки), но не может быть выше.
Наконец, это азы не только хэширования, но и шифрования: для некоторых протоколов, режимов и условий использования стойкость шифра не больше половины размера блока, хоть вы в 128-битный по блоку шифр многокилобитный ключ запихайте. И каскадировать его в таких случаях бесполезно.
Насчет схемы хеша CTR mode с использованием сообщения как ключа: есть концептуальная проблема с slide attack (функции шифрования должны быть гарантированно разными в каждом каскаде). Кроме того, технические проблемы с связанными ключами и слабыми ключами.
Чужие мысли плохо помогают при отсутствии собственных.
Мне одному представляется, что ZAS в конец охренел? Что ж ты тут сидишь и спрашиваешь советов, коль своих мыслей громадьё?
Кстати о широких блоках. В том, что я читал, используют циклический сдвиг на пол-блока. То есть получается линейная диффузия на блок за раунд; соответственно для полной диффузии нужно N раундов, где N – число блоков из которых состоит широкий блок. Общее количество операций получается порядка N^2. Неэффективно. Очевидное решение – собирать полублоки через половину широкого блока. Тогда диффузия экспоненциальная и требуется log2(N) раундов.
Примерно так:
Нечто вроде транспонирования. Работает для любого N. Такой вариант сложнее проанализировать, чем со сдвигом.
Применяется ли на практике или сразу "cбивается на подлете" ?
комментариев: 9796 документов: 488 редакций: 5664
Судя по квадратичным расходам для полной диффузии на размер MDS-матриц — это так и есть, причём, возможно, формально доказуемо проще всего, как достаточное условие для полной диффузии.
С консервативной т.з. это возможно достаточное условие, если операция диффузии в блоке идеальна.
Есть ухищрения с сокращением числа операций с более сложными доказательствами. Вообще, имелись ввиду работы по созданию режимов с широкой диффузией для дискового шифрования. Там число раундов сокращают до двух-трёх, но возможно такие конструкции абсолютно неприменимы для хэшей.
Подозреваю, что могут быть оба плохи для хэшей, т.к. неидеальны и нужно, как минимум, вводить дополнительный коэффициент на число раундов. И сходу непонятно, какие типы неидеальности допустимы:
Требования к строгой неразличимости от идеальной модели, скорее всего, возрастают от п.1 к п.3.
Если знания из какой-то области представляют проблему для собственных мыслей, это скорее повод начать думать в другом направлении, куда можно более конструктивно применить
маниюэнергию своего изобретательства.Это как раз более-менее понятно.
Достаточно чтобы разность на входе любого из N блоков приводила к разности на выходе любого другого блока с вероятностью не хуже 2^размер блока.
Чтобы дифференциальная характеристика от общего входа до общего выхода имела среднекв. отклонения от среднего, не большее чем 2^(размер ключа/2).
То же, но на размер хеша.
http://www.zas-comm.ru