РегистрацияПодскажите способы генерации S-box из ключа
Возьмем, к примеру ГОСТ, там есть таблица замен, состоящая из восьми узлов замен. Подстановка 4-в-4. Итого 512 бит.
Вопрос: какие есть возможности задания подстановки по ключу? Ну что-то вроде скрещения blowfish и DES.
[think] Кажется, такие разработки уже были с DES. Но там задавалась перестановка S-блоков.[/think]
[think] Слышал, что секретная таблица замен эквивалентна ключу в триста с чем-то бит. Вроде было в работе по взлому S-блоков ГОСТ с заданным ключом. [/think]
Слышал, что были предложения относительно построения S-блоков DES, когда рассуждали о черном ходе АНБ. Наверное, аналогичные рассуждения (и методики если есть) можно отнести и к ГОСТ, а потом и на другие S-блоки для современных блочных шифров.
В ДЕС S-боксы были созданы для устойчивости диф.анализу. По определенным правилам.
И они были статичны, так как в то время микросхемы не позволили создать их динамическими.
В наше же время динамические блоки весьмя и весма перспективны.
(Хотите верте, хотите нет. Дело ваше.)
комментариев: 9796 документов: 488 редакций: 5664
Тема переименована в
Подскажите способы генерации S-box из ключа
А вот не верим и считаем тему как раз неактуальной последние лет 10-15. Такие шифры сыграли свою историческую роль (Blowfish, Twofish) и больше не нужны. При разработке новых шифров этот метод следует исключить из проектирования как теоретически необоснованный.
комментариев: 9796 документов: 488 редакций: 5664
Что такое блочный шифр вообще? Некая функция f = Y = (k, X), где k — ключ, X — открытый текст, Y — шифртекст. Вообще, кратко такие элементарные понятия рассмотрены в разделе Криптография: общие вопросы, но рассмотрим подробнее в контексте.
Модель идеального блочного шифра (ICM) — это частный случай модели случайного оракула (ROM). Пусть все возможные варианты (k, X, Y) для некоего идеального шифра заполнены в виде трёхмерного массива; k и X заполнены по счётчику от "все биты нули" {00 ... 0} до все биты единицы {11 ...1}, а Y подобраны с помощью идеального генератора случайных чисел, так, чтобы для каждого k все возможные пары X и Y создавали псевдослучайную перестановку всех возможных вариантов открытого текста в шифртексты, неотличимую от идеально случайной. Иначе говоря, Y это биективное отображение множества X в некотором случайном порядке.
Возьмём реальный шифр C. Если можно найти отличие между ним и идеальным шифром f быстрее, чем за 2k или в ряде случаев за 2b, где b — размер блока X и Y, то C — нестойкий. И, грубо говоря, наплевать какое отличие вы найдёте и как. При этом, можете также в вежливой форме наплевать на негодование криптографов старой школы (включая известных израильских), которые не считают такие различители за атаки. Конкурс SHA-3 (хотя там про хэши, а не шифры) показывает (IMHO), что они неправы.
А теперь представьте, что вы разрабатываете не любительский шифр, а современный, с большой теоретической выкладкой. И вам нужно будем всеми способами продемонстрировать, что найти различитель между вашим C и f невозможно. Чем сильнее будет доказательство, тем лучше шифр будет противостоять любым атакам. Можете абстрагироваться от атак на поиск ключа, на раскрытие открытого текста и т.д. Нет их. Забудьте временно эти частные случаи. Используйте самую сильную модель стойкости (ICM).
Как взломали AES в связи с конкурсом SHA-3 из-за применения его в хэшах? Пусть пока и без серьёзных практических последствий для самого AES. Сначала нашли различитель в модели открытого ключа, затем вывели атаку на связанных ключах. А это уже что-то. Т.е. противник знает и шифртекст и открытый текст и может их подбирать как вздумается и он знает ключ, а не ищет его, как было принято в старой криптографической школе.
Значит он знает все выведенные S-блоки, подключи на каждом раунде и вообще всё внутреннее состояние шифра. Если даже при всём при этом он не сможет найти различитель, значит это стойкий шифр.
А выводимые из ключа S-блоки сразу смотрятся слабой уловкой в модели криптоанализа с открытым ключом. Они не дают почти никаких преимуществ в доказательстве стойкости.
[think] рассмотрение блочного шифра как криптопримитив подходящий для всех и вся, сравнивание его со случайным оракулом это как... сферический шифр в вакууме о_0. Это не троллинг если что. [/think]
К примеру, доказать для ГОСТ что практически любой псевдослучайный вектор размеро 512 бит это хорошая подстановка. Потом его генерировать при помощи ГПСЧ. Или шифровать на этом ключе константу при дефолтной таблице замен. Шанс выбрать линейную таблицу замен стремиться к нулю.
комментариев: 9796 документов: 488 редакций: 5664
Считают, что нельзя идеализировать криптопримитив до такой степени.
Но на самом деле, кто знает как будет применяться шифр? Может он действительно будет использоваться как функция сжатия в хэше. Может он будет использоваться для генерации MAC. Может его будут использовать для какого-нибудь экзотического режима дискового шифрования. Или в режиме AoN-transform — преобразование "всё-или-ничего", антикодирования, где шифрования вообще не производится как такого.
И никто не знает, как неидеальность может быть использована для развития более сильных атак.
Многие доказательства на конкурсе SHA-3 звучат примерно так: "если используемый в функции сжатия шифр является идеальным блочным шифром, то сконструированная хэш-функция является неразличимой от случайного оракула". И наоборот, для AES таким образом "случайно" доказали неидеальность и сняли все производные от него хэши с конкурса. Не верите в Ideal Cipher Model, ваше дело. Только скорее всего, если когда-нибудь будет новый конкурс вместо AES, то будут рассматривать кандидатов в рамках этой модели, независимо от хэшей.
Может ему для начала ключевое расписание подправить? И в итоге вообще отказаться от ГОСТ, потому что все преимущества в его простоте потеряются.
Такое известно для больших S-блоков (8x8) и использовалось в дизайне Twofish и Anubis. Кстати, в этих шифрах большие S-блоки для компактности "разворачиваются" из маленьких, что в обоих случаях давало подозрения в неидеальности результата, но до атак не дошли.
В Blowfish блоки 8x32 могут быть слабыми, но практически тоже шанс стремится к нулю.
В ГОСТ блоки маленькие, там фокус со случайной подстановкой не пройдёт. По крайней мере простого решения не видно.
IMHO, лучше при проектировании новых шифров доказать стойкость против всех атак, исходя из невозможности найти различитель в ICM и в модели открытого ключа, что легче сделать для простой структуры шифра, чем думать как сложная функция с изменением S-блоков повлияет на его свойства, пусть даже и отсекая на первый взгляд кучу практических атак.
Кстати, циклический сдвиг, зависящий от шифруемых данных (RC5, RC6) — из той же оперы и некоторые криптографы считают, что эти шифры себя не оправдали. Против атак с известным/подобранным открытым текстом такой трюк помогает не просто слабо, а даёт сравнительно более плохие результаты.
Есть консервативная израильская школа (Шамир там и др.), где как раз примерно так и считают, у них там была забавная работа, что нужно проектировать криптопримитивы и протоколы не исходя из идеализаций, а оценивать атаки в деньгах. Память, время, доступные тексты переводить в деньги и считать, во сколько 2n "мегагигатераэксапетабаксов" обойдётся взлом. И защищаться в первую очередь против дешёвых атак. По крайней мере оценивать важность теоретических работ в таком виртуально-денежном эквиваленте.
комментариев: 9796 документов: 488 редакций: 5664
Обычная SP-сеть (Substitution Permutation) — просто замены и перестановки:
Только п.3 — нелинейная операция, а что значит слово "гамма" при описании внутренней структуры блочного шифра?
При S-блоке, зависящем от ключа, всё как раз выглядит непросто. Простая схема должна хорошо работать и при статичном S-блоке.
комментариев: 9796 документов: 488 редакций: 5664
Там учтено, включая закон Мура и тенденции изменения цен на железо (память, процы). Плюс при 128-битных величинах ошибка в несколько сотен раз некритична. И конечно, это впервую очередь для голосования по поводу того, чья работа лучше. Например, одни могут взломать за 220 операций, но за 2100 памяти, другие за 2100 операций, но за 220 памяти. Просто такие работы отражают тенденцию некоторых криптографов к практичности против чрезмерных теоретических идеализаций.
Видимо не зря rsa.com отменил премии за нахождение сомножителей:
RSA Laboratories
В подобном контексте звучит немного двусмысленно :)
Это от обозначения этапа преобразования греческой буквой.
Такое чувство, будто бы все блочные шифры созданы как "безопасность на запутывании". Подмешайте S-блоки, умножьте на таблицу, сложите с ключом. В построении блочных шифров какие-то туманные рекомендации и методы. Криптография снова стала как искусство.
комментариев: 11558 документов: 1036 редакций: 4118