Нетрадиционное руководство для неспециалистов по расширенному стандарту шифрования (часть 2)
Мгновенный AESnack: Sub, Shift, Mix и Add
О, привет! И снова это время — вторая часть нашей крипто-саги. Ладно, может быть, мы кнут и фетровая шляпа, а не сага, но вы поняли идею. Ранее вы познакомились с математической терминологией, которая, несмотря на почти нэшевскую коннотацию вуду, была представлена в манере Joe McEasyBakeOven. Теперь, когда мы упростили общие вопросы, такие как циклическое преобразование и ключевое расписание, давайте поместим их под микроскоп и посмотрим, что еще мы можем проанализировать. Когда я закончу эту статью, я закончу, предоставив ссылки для тех из вас, кто может оспаривать, сказав: «Я специализируюсь на математике — дайте мне больше теории!»
Еще немного раствора между еще несколькими фундаментными кирпичами
Что ж, я выпил свой сладкий чай со льдом — нектар этого южного криптографа — и при свете катодного луча, с мастерком в руке, я готов. Я предполагаю, что некоторые из вас задаются вопросом о неясных ссылках на каменную кладку (т. е. раствор, кирпичи и мастерок). Не удивляйтесь больше; здесь появляется первый новый термин: перестановка каменщика. Есть некоторые контекстуальные, обязательные приправы, которые мне нужно посыпать в первую очередь. Более примитивно нам нужно определить функцию каменщика. Мы можем разложить эту функцию на ряд булевых функций, которые независимо работают с подмножествами битов входного вектора; раздел битов входного вектора формируется этими подмножествами. Чтобы быть более конкретным, они разделены на пакеты (т. е. 8-битные байты и 32-битные столбцы в Rijndael). По сути, то, что у вас есть, состоит из нескольких логических функций, которые работают с меньшими входными данными, применяемыми параллельно.
Когда мы рассматриваем функцию каменщика, которая работает с состоянием, мы называем это преобразованием каменщика ; состояние относится к промежуточной информации, с которой оперируют шаги Rijndael во время процедур шифрования и дешифрования. Это может помочь взглянуть на это следующим образом. Когда вы передаете открытый текст алгоритму шифрования, состояние является промежуточным результатом до тех пор, пока зашифрованный текст не будет выплюнут или извлечен из состояния; когда вы передаете зашифрованный текст алгоритма дешифрования, состояние является промежуточным результатом до тех пор, пока открытый текст не будет выплюнут или извлечен из состояния. Вернемся к кладке кирпичей. Преобразование каменщика определяет раздел пакета, поскольку оно работает независимо с рядом подмножеств этого состояния; отсюда следует, что преобразования компонентов преобразования каменщика действуют независимо на ряд связок.
Если бы я был любителем азартных игр, я бы поставил свой кошелек на пари, что по крайней мере некоторые из вас слышат эти термины впервые. Возможно, следующее напомнит вам: если эти булевы функции нелинейны, их очень ласково называют S-блоками. Вы можете спросить: «А что, если булевы функции линейны?» «Ну, — отвечал я, — если они линейные, их называют D-блоками ». О, и чтобы смягчить путаницу, которая, возможно, витает над вами, из-за этого соглашения об именах алфавитного супа, S означает замену, а D означает распространение. Крайне важно, чтобы и S-блоки, и D-блоки были перестановками, чтобы преобразование каменщика было обратимым; именно эту обратимую перестановку каменщика мы называем перестановкой каменщика.
Вышеупомянутый звонок, который должен звонить, — это S-box, поскольку вы найдете его в большинстве блочных шифров, таких как DES, Blowfish, Twofish и Serpent. Как и в случае с расписанием ключей, существует множество подходов к построению S-блоков с учетом криптоаналитической устойчивости. Если вы думали, что у Баскин Роббинс есть из чего выбирать, я приглашаю вас ознакомиться с некоторыми из множества интересных вариантов дизайна S-box. Если вы готовы к интенсивному теоретическому нокауту, изучите некоторые исследования Кайсы Найберг; тем не менее, он обладает ментальным ударом в стиле Шугара Рэя Леонарда, так что будьте готовы. Еще одна вещь — когда мы начинаем, имейте в виду, что мы имеем дело с Rijndael в том виде, в каком он реализован в спецификации AES, которая фиксирует длину блока на уровне 128 бит.
Делаем наш первый шаг с Rijndael – буквально
Теперь, когда мы завершили свою работу в качестве символических каменщиков, давайте осмотрим шестерни, которые заставляют Рийндаэля вращаться. Я избавлю вас от лишних слов и перейду сразу к первому шагу Rijndael, получившему название SubBytes. На самом деле, этот шаг — единственное нелинейное преобразование, которое вы найдете в Rijndael; это перестановка каменщика, и если вы добавите к ней «нелинейный», вы можете спросить, не задействован ли S-блок. Вы были бы правы, если бы спросили, поскольку SubBytes, по сути, состоит из S-блока. Этот S-блок работает с отдельными байтами состояния или 8-битными пакетами, и критерии проектирования, лежащие в его основе, направлены на сопротивление линейному криптоанализу и дифференциальному криптоанализу, а также интерполяционным атакам. В данном случае работа Найберга оказала большое влияние.
Криптографический водоворот – метафорические приливы циклически меняются
Следующим на очереди у нас есть ShiftRows. Этот шаг представляет собой перестановку байтов, при которой строки состояния циклически сдвигаются в соответствии с указанными смещениями (т. е. 0, 1, 2 и 3 для 128-битного блока). Эти смещения были выбраны на основе таких критериев, как простота, устойчивость к усеченным дифференциальным атакам и атакам насыщения, а также оптимальность распространения (т. е. все смещения различны) в отношении сопротивления линейному криптоанализу и дифференциальному криптоанализу. Хотя этот раздел был быстрым, как Road Runner, это, по меньшей мере, важный шаг в круглом преобразовании.
Где Бетти Крокер? Колонки нуждаются в смешивании
ShiftRows уже имеет дело со строками, а функция MixColumns работает со столбцами. Таким образом, мы можем определить MixColumns как перестановку каменщика, которая работает со столбцами состояния или 32-битными пакетами. Вы уже встречали термин «каменщик» некоторое время назад, когда мы определяли SubBytes. В то время как SubBytes и MixColumns оба являются перестановками каменщика, первый нелинейный, а второй — линейный. Если вы следили за этим, вы могли задаться вопросом: «Ну, если «нелинейный» соответствует S-блоку, то, возможно, это линейное преобразование является тем местом, где появляется D-блок». Еще раз, вы были бы на правильном пути. Чтобы сопоставить их немного больше, в то время как нелинейные S-блоки SubBytes работают с байтами состояния независимо, линейные D-блоки MixColumns работают со столбцами состояния независимо.
Критерий линейности, наряду с критерием диффузии, являются продуктами стратегии широкого следа, которые, если хотите, являются «чертежами», по которым был построен Рейндал. Галуа, возможно, и не был гаучо, но, чтобы отдать ему должное, пора оседлать и отправиться в полиномиальные пампасы. Давайте посмотрим на столбцы состояния как на полиномы над GF(2 8 ), где «GF» означает просто «поле Галуа». Эти столбцы умножаются по модулю x 4 + 1 на фиксированный полином 03 * x 3 + 01 * x 2 + 01 * x + 02, который, будучи взаимно простым с x 4 + 1, обратим. Коэффициенты были тщательно подобраны таким образом, чтобы число ветвей MixColumns было равно пяти, что является максимальным, учитывая размеры преобразования. Вы можете сказать, что ShiftRows — это Робин для Бэтмена MixColumns, только без колготок; вместе, с их рассеивающими способностями, они мешают линейным и дифференциальным криптоаналитическим врагам математики и хаоса.
Кто-нибудь видел мои круглые ключи? Я думал, что оставил их на прилавке
Концептуально это должно быть довольно простым объяснением. Последний шаг, который мы рассмотрим, называется AddRoundKey. Круглый ключ и длина блока равны. Состояние объединяется с помощью XOR с круглым ключом. Расширенный ключ, на который сопоставляется «главный» ключ шифрования, представляет собой коллективный массив раундовых ключей, которые выбираются из расширенного ключа. Это происходит во время ключевого планирования.
Для каждого раунда нужен круглый ключ. Для AES с 10 раундами, что подразумевает фиксированную длину блока 128 бит и длину ключа 128 бит, необходимо 1408 бит материала ключа раунда; эти 1408 бит составляют вышеупомянутый расширенный ключ. Не нужно ломать свой TI-83+, чтобы понять это. Добавьте единицу к количеству раундов (10 + 1 = 11), затем умножьте это на длину блока (11 * 128 = 1408); именно столько бит будет в расширенном ключе. Таким образом, расширенный ключ — это последовательное объединение раундовых ключей.
Ключевые расписания сами по себе представляют собой запутанные машины. Не существует универсальной дисциплины того, как они должны быть спроектированы, но, тем не менее, они занимают довольно важные позиции. В случае с Rijndael это проявляется по-разному. Для предотвращения атак и слабых мест (т. е. слабых ключей), использующих симметрию в раундовом преобразовании и между раундами, в рекурсивную функцию раскрытия ключа вводится асимметрия.
Прежде чем вы начнете бурно реагировать: «Воу, воу, воу — асимметрия? Я думал, что Rijndael — это симметричный блочный шифр? Это. Остыть. Без проблем. «Симметрия» в этом контексте относится к наблюдению, что циклическое преобразование Райндаэля обрабатывает все байты состояний, в основном, одним и тем же способом; преобразование раунда также одинаково, раунд за раундом, за исключением последнего раунда. Зависящие от раунда константы раунда в ключевом расписании устраняют симметрию, налагаемую этими наблюдениями; то есть они устраняют симметрию или вводят асимметрию. Атаки со скольжением, например, основаны на такой симметрии.
Независимый от ключа S-блок SubByte обеспечивает нелинейность, которая предотвращает существование слабых ключей, таких как найденные в IDEA, и, наряду с распространением, направлена на защиту от атак с использованием связанных ключей. Кроме того, расписание ключей имеет защиту от сценариев, в которых ключ может быть известен частично, полностью или даже выбран, например, когда блочный шифр используется в качестве функции сжатия хеш-функции. На самом деле это химера компонентов, которая сочетает в себе простоту и хорошую гибкость клавиш.
Ветки без деревьев, широкие тропы и теория Маркова за 500 долларов, пожалуйста
В моей вечной одиссее по изучению более близких личностей криптографии я исключим византийскую родословную, которая находится в самой глубинной сердцевине основания Rijndael; впрочем, справедливости ради, я приоткрою дверь — оттуда можно забрать. Номер ответвления из нескольких разделов назад соответствует свойству диффузии, которое определяется несколько иначе в контексте стратегии широкого следа, в отличие от определения Шеннона, с которым многие из вас должны быть знакомы; номер ветви соответствует линейной корреляции следа и дифференциальной вероятности следа в отношении предоставления границ для них.
Структура чередования ключей, с которой вы познакомились в предыдущем эпизоде, нацелена на обеспечение устойчивости к линейному и дифференциальному криптоанализу; это стратегия широкого следа, которая вращается вокруг философии проектирования циклических преобразований в блочном шифре, демонстрирующих эту структуру. Общая предпосылка — быть эффективным и устойчивым к криптоанализу. Шифр Маркова, такой как Rijndael, является итеративным и содержит циклическое преобразование, которое удовлетворяет критерию, связанному со средней вероятностью распространения разности, что особенно важно в дифференциальном криптоанализе. Стоит отметить, в двух разных отчетах, что теория марковского шифра распространяется и на линейный криптоанализ, а стратегия широкого следа не ограничивается блочными шифрами с чередованием ключей.
Хотя я представил некоторые принципы проектирования Rijndael, вы обнаружите, что существует анализ вариантов Rijndael с уменьшенным числом раундов. Итак, для вас, математиков-крестоносцев с аппетитом к большему, я рекомендую работы Лая, Мэсси и Мерфи по теории марковского шифра, а также взгляды Раймена и Деймена на нее, а также их исследования в области стратегии проектирования широких следов.. Работы Бихама, Келси и Фергюсона являются фундаментальными отправными точками для ознакомления с атаками со связанными ключами в целом и тем, как они применимы к криптоанализу Рейндаля, например, криптоанализ Фергюсона, Келси, Лакса, Шнайера, Стей, Вагнера. и Уайтинг.
Ознакомьтесь с работой Якобсена и Кнудсена по атакам с интерполяцией, работой Бирюкова и Вагнера по атакам со скольжением и работой Лакса по атакам с насыщением, из которых вы увидите аналогичные исследования, касающиеся атаки «Квадрат» Кнудсена, «структурной» атаки Бирюкова и Шамира и атаки Фергюсона. достижения. Вот некоторые названия, которые следует иметь в виду, когда вы просматриваете множество полезных аналитических материалов, применяющих философию дизайна Rijndael, и анализ, ориентированный на Rijndael, который родился во время конкурса AES.
Криптографические стандарты имеют хороший криптографический смысл
Прежде чем я выкину полотенце из этой серии статей о Advanced Encryption Standard, я хотел бы поделиться своим мнением о некоторых опасениях тех, кто живет в нескольких домах от криптографии, но не совсем в ней разбирается. Что общего у Starbucks и необоснованных, спекулятивных, параноидальных утверждений о криптографии? Они повсюду. Политика – я пощажу тебя. Так просто, как я могу произнести эти слова: используйте AES. То есть, если это не подходит для ваших критериев дизайна, я предлагаю использовать его, когда это возможно. Неспециалист по безопасности делегирует содержание своего доверия тем, кто имеет опыт в области безопасности; то же самое справедливо и для междисциплинарной области криптографии. Слишком часто я слышу: «Это федеральный стандарт, поэтому он должен быть слабым. Правительство никогда не будет продвигать что-то, что на самом деле слишком прочно, чтобы его сломать». Я даю им секунду, чтобы поправить свой берет из фольги после того, как он сместится из-за их оживленного разглагольствования.
После этого я объясню простую логику, которой поделюсь с вами. Обращаясь к нам, общественности, академическому сообществу и АНБ, частному агентству, мы можем сказать, что есть два типа криптографов: наши и их. Очевидно, поскольку мы публичны, у всех нас есть доступ к собственному криптоанализу. Однако, поскольку они частные, у нас нет доступа к их криптоанализу. У них есть доступ не только к их собственному частному криптоанализу, но и к нашему общедоступному криптоанализу. Это лишь некоторые очевидные наблюдения; мы ничего не должны передавать Шерлоку. Конечно, нам не имеет смысла говорить, что им невозможно быть далеко впереди; точно так же нам не имеет смысла говорить, что мы оба не можем быть ноздря в ноздрю. Это не то, что можно решить, учитывая то немногое, что мы знаем о фактах, и спекуляции не имеют доказуемой отдачи. Независимо от того, как вы на это смотрите, этот факт имеет место.
Криптоанализ — это добродетель
Таким образом, я доверяю криптографам, участвовавшим в разработке и анализе конкурса, победителем которого стал AES. Лично NIST сделал выбор, с которым я согласен. В целом, AES — это история криптографического успеха. Итак, как только Rijndael был выбран, он стал объектом криптоанализа. Когда оно стало синонимом слова «стандарт», оно также стало еще большим вакуумом внимания. На Rijndael было обращено больше взглядов криптоаналитиков, чем на любого другого финалиста AES. Почему? Потому что это цель. Почему это цель? Потому что это стандарт, на основе которого будут построены многие новые протоколы и на который будут переходить многие старые протоколы. Чтобы блочный шифр или любой другой примитив, если уж на то пошло, «заработал свои кости», так сказать, он должен выдержать криптоанализ. Почему? Потому что криптоанализ — это добродетель. Ждать; это добродетель.
Хотя я думаю, что практическая паранойя — это хорошо, я не из тех, кто покупает акции в спекуляциях, особенно когда за ними нет никакого основания, рациональности или содержания внутри них. Не поймите меня неправильно; нельзя отрицать, что криптографы полагаются на предположения для безопасности, которые не имеют абсолютного доказательства. Имейте в виду, однако, что есть разница между этими обоснованными предположениями, основанными на академических исследованиях, и теориями заговора, основанными на некомпетентности. Первое — лучшее, что у нас есть, и я согласен с этим, потому что я знаю, что если Всевидящее Око (TM) захочет увидеть открытый текст, почти всегда есть более простой, некриптографический способ получить его.. Это побочный продукт того факта, что криптография редко бывает самой слабой горошиной в системе безопасности.
В заключение я возьму последнее предложение предыдущего абзаца и продолжу его. Если кто-то из вас может сказать, что хорошая, правильно реализованная криптография (т. е. AES в режиме CTR и CMAC-AES) является самым слабым компонентом вашей инфраструктуры, пришлите мне по электронной почте свой почтовый адрес, чтобы я мог отправить вам Кресло Lay-Z-Boy, в котором вы можете расслабиться, зная, что у вас одна из самых надежных систем. Несмотря на то, что нужно следовать одной чертовски сложной метрике проектирования — то есть построению систем, в которых криптография является самым слабым звеном, — обычно все наоборот. После взвешивания этих факторов кажется достаточно логичным сделать наилучшее криптографическое суждение, которое мы можем, учитывая возможности, которые предоставили нам наши современные исследования. Rijndael имеет хороший криптографический смысл и считает, что плюсы перевешивают любые потенциальные минусы, которые некоторые могут бросить ему на пути; его философия дизайна, на мой взгляд, консервативна, как и обоснование использования стандарта, который принимает и выдерживает криптоанализ.
Не поймите меня неправильно – я сторонник многих принципов дизайна Twofish и Serpent, которые, по-разному, разработаны гораздо более консервативно. Принимая во внимание все обстоятельства, процесс выбора AES является воплощением того, как должна происходить стандартизация, и он способствует строгому криптоанализу, который Rijndael использует в своих интересах, и это справедливо. NIST и академические круги объединились для определения того, что было предпочтительной метрикой проектирования для будущих процессов криптографического проектирования. Резюмируя: криптоанализ — это добродетель, если хотите, «зарабатывание костей» примитива. Rijndael — самая интересная цель для криптоанализа — магнит для изучения, который подвергается большему изучению, чем любой другой кандидат в процессе отбора AES. Если вы можете использовать Rijndael — делайте это. А теперь извините меня, дорогие ребята, обед зовет, так что я вас всех скоро догоню. Чау!