Подскажите способы генерации S-box из ключа
Возьмем, к примеру ГОСТ, там есть таблица замен, состоящая из восьми узлов замен. Подстановка 4-в-4. Итого 512 бит.
Вопрос: какие есть возможности задания подстановки по ключу? Ну что-то вроде скрещения blowfish и DES.
[think] Кажется, такие разработки уже были с DES. Но там задавалась перестановка S-блоков.[/think]
[think] Слышал, что секретная таблица замен эквивалентна ключу в триста с чем-то бит. Вроде было в работе по взлому S-блоков ГОСТ с заданным ключом. [/think]
Слышал, что были предложения относительно построения S-блоков DES, когда рассуждали о черном ходе АНБ. Наверное, аналогичные рассуждения (и методики если есть) можно отнести и к ГОСТ, а потом и на другие S-блоки для современных блочных шифров.
Ссылки
[link1] https://www.pgpru.com/faq/kriptografijaobschievoprosy
[link2] http://www.rsa.com/rsalabs/node.asp?id=2093
[link3] https://www.pgpru.com/comment18999
[link4] http://economics.kiev.ua/
[link5] http://crisis-blog.ru/reasons
[link6] https://www.pgpru.com/comment41699
[link7] http://www.wisdom.weizmann.ac.il/~orrd/crypt/ESC-Model.pdf
[link8] https://www.pgpru.com/comment42251
Тема весьма и весьма нетривиальная. Бесплатных хороших паперов с теорией я не смог найти.
Вопрос, который оброс более выдумками, чем теорией.
В ДЕС S-боксы были созданы для устойчивости диф.анализу. По определенным правилам.
И они были статичны, так как в то время микросхемы не позволили создать их динамическими.
В наше же время динамические блоки весьмя и весма перспективны.
(Хотите верте, хотите нет. Дело ваше.)
Тема переименована в
Подскажите способы генерации S-box из ключа
А вот не верим и считаем тему как раз неактуальной последние лет 10-15. Такие шифры сыграли свою историческую роль (Blowfish, Twofish) и больше не нужны. При разработке новых шифров этот метод следует исключить из проектирования как теоретически необоснованный.
Что такое блочный шифр вообще? Некая функция f = Y = (k, X), где k — ключ, X — открытый текст, Y — шифртекст. Вообще, кратко такие элементарные понятия рассмотрены в разделе Криптография: общие вопросы[link1], но рассмотрим подробнее в контексте.
Модель идеального блочного шифра (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 бит это хорошая подстановка. Потом его генерировать при помощи ГПСЧ. Или шифровать на этом ключе константу при дефолтной таблице замен. Шанс выбрать линейную таблицу замен стремиться к нулю.
Я понимаю о чём вы. Не все даже ведущие криптографы также как и вы соглашаются с такой позицией.
Считают, что нельзя идеализировать криптопримитив до такой степени.
Но на самом деле, кто знает как будет применяться шифр? Может он действительно будет использоваться как функция сжатия в хэше. Может он будет использоваться для генерации MAC. Может его будут использовать для какого-нибудь экзотического режима дискового шифрования. Или в режиме AoN-transform — преобразование "всё-или-ничего", антикодирования, где шифрования вообще не производится как такого.
И никто не знает, как неидеальность может быть использована для развития более сильных атак.
Многие доказательства на конкурсе SHA-3 звучат примерно так: "если используемый в функции сжатия шифр является идеальным блочным шифром, то сконструированная хэш-функция является неразличимой от случайного оракула". И наоборот, для AES таким образом "случайно" доказали неидеальность и сняли все производные от него хэши с конкурса. Не верите в Ideal Cipher Model, ваше дело. Только скорее всего, если когда-нибудь будет новый конкурс вместо AES, то будут рассматривать кандидатов в рамках этой модели, независимо от хэшей.
Может ему для начала ключевое расписание подправить? И в итоге вообще отказаться от ГОСТ, потому что все преимущества в его простоте потеряются.
Такое известно для больших S-блоков (8x8) и использовалось в дизайне Twofish и Anubis. Кстати, в этих шифрах большие S-блоки для компактности "разворачиваются" из маленьких, что в обоих случаях давало подозрения в неидеальности результата, но до атак не дошли.
В Blowfish блоки 8x32 могут быть слабыми, но практически тоже шанс стремится к нулю.
В ГОСТ блоки маленькие, там фокус со случайной подстановкой не пройдёт. По крайней мере простого решения не видно.
IMHO, лучше при проектировании новых шифров доказать стойкость против всех атак, исходя из невозможности найти различитель в ICM и в модели открытого ключа, что легче сделать для простой структуры шифра, чем думать как сложная функция с изменением S-блоков повлияет на его свойства, пусть даже и отсекая на первый взгляд кучу практических атак.
Кстати, циклический сдвиг, зависящий от шифруемых данных (RC5, RC6) — из той же оперы и некоторые криптографы считают, что эти шифры себя не оправдали. Против атак с известным/подобранным открытым текстом такой трюк помогает не просто слабо, а даёт сравнительно более плохие результаты.
Есть консервативная израильская школа (Шамир там и др.), где как раз примерно так и считают, у них там была забавная работа, что нужно проектировать криптопримитивы и протоколы не исходя из идеализаций, а оценивать атаки в деньгах. Память, время, доступные тексты переводить в деньги и считать, во сколько 2n "мегагигатераэксапетабаксов" обойдётся взлом. И защищаться в первую очередь против дешёвых атак. По крайней мере оценивать важность теоретических работ в таком виртуально-денежном эквиваленте.
Мне больше всего нравятся системы криптографической мысли, включающие в себя замену, перестановку и гамму (нелинейную замену). Логично и просто выглядит математика.
Обычная SP-сеть (Substitution Permutation) — просто замены и перестановки:
Только п.3 — нелинейная операция, а что значит слово "гамма" при описании внутренней структуры блочного шифра?
При S-блоке, зависящем от ключа, всё как раз выглядит непросто. Простая схема должна хорошо работать и при статичном S-блоке.
Думаю что вводить меру взлома в стоимости нелогично. Цены меняются. Существующие оценки в трудоемкости получше будут.
Там учтено, включая закон Мура и тенденции изменения цен на железо (память, процы). Плюс при 128-битных величинах ошибка в несколько сотен раз некритична. И конечно, это впервую очередь для голосования по поводу того, чья работа лучше. Например, одни могут взломать за 220 операций, но за 2100 памяти, другие за 2100 операций, но за 220 памяти. Просто такие работы отражают тенденцию некоторых криптографов к практичности против чрезмерных теоретических идеализаций.
Видимо не зря rsa.com отменил премии за нахождение сомножителей:
RSA Laboratories[link2]
В подобном контексте звучит немного двусмысленно :)
Это от обозначения этапа преобразования греческой буквой.
Не хочется открывать новую тему, чтобы сказать мысль.
Такое чувство, будто бы все блочные шифры созданы как "безопасность на запутывании". Подмешайте S-блоки, умножьте на таблицу, сложите с ключом. В построении блочных шифров какие-то туманные рекомендации и методы. Криптография снова стала как искусство.
Слишком толсто.
Мысль старая и уже многократно озвучивалась, см., например, от /comment18999[link3] и ниже по треду (особенно, unknown'а). Также, man Коблитц.
ЩИТО ?
В мире "выгоднопродайства" вообще всё оценивается в деньгах. Так думать меньше надо. :)
Ну почему же? Вот например одна из цитат из АНБ приведена на сайте. Про любителей и алгоритмы, про профи и экономику. А вот как перевести стойкость в деньги? На то и есть статья евреев.
В условия, когда деньги делаются "из воздуха"[link4] (ещё тут[link5] ), и "наделано" их уже в десятки раз больше, чем имеется товаров, цена вещей определяется не себистоимостью и даже не спросом, а произволом очень небольшой группы хозяев этих денег. В таких условиях оценивать стойкость криптоалгоритмов в деньгах ненаучно.
И все же, не мог бы анонимус закинуть ссылку ?
Если вы об этом[link6]: так это не анонимус а unknown писал.
Обращение к анонимусу это как обращение к общественности. Здесь и другие спецы сидят, анонимусы, хотя наш неизвестный тоже можно сказать анон, ибо неизвестнен он – кэп.
Ссылку придётся искать долго, т.к. были доступны только слайды с доклада, но ничего не сохранилось, приводил по памяти, надеюсь ничего не перепутал ;-)
Это всё-таки был провокационно-шутливый доклад, тем не менее отражающий реальное отношение части криптографов к излишней теоретизации атак. Реальное практическое предназначение метода — голосование по поводу работ, которые "взламывают" алгоритм слишком абстрактными и несравнимыми между собой способами. Тогда атаки предлагается пересчитать в деньги (виртуальные сами по себе, но имеющие хоть какую-то связь с реальностью), хотя бы по ценам сегодняшнего дня и плюс немного вперёд. Когда несколько работ одинаково ценны теоретически, но выбрать, какая из ни лучшая сложно.
Кто печатает деньги и как их виртуально делает в реальном мире не имеет значения вообще в данном вопросе. Нужна рыночная оценка относительной (сравнительной между собой) стоимости разных ресурсов. Клиентов всё-равно будет интересовать именно это, плевать им пока на несправедливость финансового мироустройства.
если вам так не нравятся деньги – посчитайте в киловаттчасах на текущий мемент по цене какой-нить аризонщины ;)
может быть вы все-таки приведете хотя бы название доклада? поищем вместе =))
это печально, но можно ли его использовать для серъезных работ или "плохой тон"?
заказчики понимают ведь только количество денег. если просчитать стоимость лучшей атаки на алгоритм, сравнить с ценой защищаемой информации, то м/б и никто не будет отаковать.
является ли этот доклад первым в своем роде? вроде все, что я слышал, это оценки времени взлома и необходимой энергии.
Так для этого нужен рынок, но как раз в его наличии и закрадываются сомения.
Unknown, и все же, помните ли вы хоть какие-нибудь реквизиты, хотя бы частично или примерно:
1. Название работы
2. Автор (шамир, бихам, их студенты)
3. Год (до 2000, после 2000)
4. Конференция (крипто, азиа-, евро-, ...)
5. Характерные слова (для поиска по контексту типа "petadollars")
Так, чудо свершилось почти без Гугла, после долгого помутнения память прояснилась. Всё-таки правильно рассортировать проблему поиска по пунктам, помогает:
What is the Best Attack?[link7]
Orr Dunkelman, Echternach Symmetric Cryptography Seminar 2008 (Luxembourg), January 11, 2008
Если будет ещё содержательное обсуждение этих тезисов, то можно вынести в другую тему, ибо оффтопик или кого-то всё ещё S-блоки интересуют?
да, заодно можно обсудить методы оценки криптостойкости.
кстати, если к примеру подстановка 8-в-8, 256 элементов, то они должны быть псевдослучайной перестановкой, т.е. 8-битовым идеальным блочным шифром. Какие есть методы реализации такой псевдослуайной перестановки?
Расставляем по кругу числа от 1 до 256 через псевдослучайное число еще не заполненных мест каждое.
т.е. алгоритм генерации ПСЧ и есть алгоритм генерации ПСП? Типа как случайный оракул и идеальный блочный шифр ?
как сказали выше, сгенерировать перестановку для 256 бит тривиально. В псевдокоде примерно так:
Где rnd(i) — это какая-то криптостойкая функция для получения (псевдо)случайных чисел (истинно случайные — при обработке событий с внешних датчиков).
Перетасовки нужны, потому что на компьютера с двоичной логикой проще получать числа в диапазоне степеней двойки.
Если i можно теоретически проделать примерно 2128 * 2128 раз (размер ключа на размер блока), а rnd(i) — идеально стойкая PRF или RF, то заполненные таблицы — идеальный блочный шифр.
Поскольку затраты на заполнение и работу с такими таблицами будут больше затрат на атаку грубой силой против шифра, то это только теоретическая модель. На практике приходится использовать малые блоки замены (S-блоки), которые чаще всего являются перестановками и смешивать результат с их выходов линейной функцией (а перед ними линейно ксорить с подключом раунда).
Если S-блоки генерировать из ключа (делать их неизвестными противнику), то криптоанализ осложняется как для противника, так и для создателя шифра — труднее обосновать/"доказать" его стойкость. От шифров с зависящими от ключа S-блоками отказались после 90-х годов, отчасти конечно всвязи с тем, что новых шифров вообще не требуется, а те, что требовались нужны были как строительный блок в создании хэш-функций (где неизвестные S-блоки бесполезны), что является более актуальной задачей.
Есть ещё нишевое направление — сверхлёгкие блочные шифры, с малым запасом криптостойкости: для смарт-карт, сверхминиатюрных устройств. Там вообще S-блоков нет.
А пока в теоретических исследованиях доминируют принципы доказательства стойкости шифров в генерализованной (более общей) модели открытого ключа (и параллельные исследования в криптоанализе хэш-функций этому только помогают), то шифры с усложнённой раундовой функцией не требуются. Считается, что чем более генерализованная модель, тем сильнее доказательство стойкости и быстрее нахождение уязвимостей, дефектов дизайна (а признаком уязвимости считается любой различитель от идеальной модели, даже при знании ключа, а не только практические атаки). А модель незнания противником ключа теперь уже рассматривается как частный случай.
s/генерализованная/обобщённая/
s/генеральный/общий/
Функции — не директора :)
И фраза будет такая: "доминируют принципы доказательства стойкости шифров в обобщённой (более общей) модели"
Слова "генеральный" в тексте unknown'a нет вообще.
А вы, spinore, не редакор. Оставьте в покое стиль unknown'а, он и так из-за вас перестал тут переводы публиковать. Радуйтесь, что вообще вернулся!
[offtop]
Вы правы (показалось, что где-то видел, может быть, не здесь).Уже порадовался :)[link8] P.S.: должен же кто-то выполнять редакторскую работу :)
[/offtop]