Advanced Encryption Standard (AES) – Часть 2.Описание AES

Блочные шифры

AES - симметричный алгоритм блочного шифрования, поэтому рассмотрим подробнее блочные шифры.

Блочный шифр — разновидность симметричного шифра. Особенностью блочного шифра является обработка блока нескольких байт за одну итерацию (как правило 8 или 16).Блочные криптосистемы разбивают текст сообщения на отдельные блоки и затем осуществляют преобразование этих блоков с использованием ключа.

Преобразование должно использовать следующие принципы:

• Рассеивание (diffusion) - т.е изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;
• Перемешивание (confusion) - использование преобразований, затрудняющих получение статистических зависимостей между шифротектстом и открытым текстом.

К достоинствам блочных шифров относят похожесть процедур шифрования и расшифрования, которые, как правило, отличаются лишь порядком действий. Это упрощает создание устройств шифрования, так как позволяет использовать одни и те же блоки в цепях шифрования и дешифрования.

Блочный шифр состоит из двух взаимосвязанных алгоритмов: алгоритм шифрования E и алгоритм расшифрования E^-1. Входными данными служат блок размером n бит и k-битный ключ. На выходе получается n-битный зашифрованный блок. Для любого фиксированного ключа функция расшифрования является обратной к функции шифрования для любого блока M и ключа K.

Для любого ключа K, E_K — перестановка набора входных блоков. Ключ выбирается из 2ⁿ! возможных перестановок.

Размер блока n — это фиксированный параметр блочного шифра, обычно равный 64 или 128 битам, хотя некоторые шифры допускают несколько различных значений. Длина 64 бита была приемлема до середины 90-х годов, затем использовалась длина 128 бит и более. Различные схемы шифрования позволяют зашифровывать открытый текст произвольной длины. Каждая имеет определенные характеристики: вероятность ошибки, простота доступа, уязвимость к атакам. Типичными размера ключа являются 40, 56, 64, 80, 128, 192 и 256 бит. В 2006 г. 80-битный ключ способен был предотвратить атаку грубой силой.

Описание AES

Алгоритм

С математической точки зрения, метод Rijndael основывается на теории полей Галуа, благодаря чему можно строго доказать некоторые его свойства, касающиеся секретности. Тем не менее, можно рассматривать его и с точки зрения кода программы на языке С, не вдаваясь в математические подробности. Как и в DES, в Rijndael применяются замены и перестановки. И там, и там используются несколько итераций, их число зависит от размера ключа и блока и равно 10 для 128-разрядного ключа и 128-битных блоков; для максимального размера ключа и блоков число итераций равно 14. Однако, в отличие от DES, все операции выполняются над целыми байтами, что позволяет создавать эффективные реализации как в аппаратном, так и в программном исполнении. Схематичный алгоритм метода Rijndael приведен ниже

У функции rijndael три аргумента: plaintext — массив размером 16 байт, содержащий входные данные, ciphertext — массив размером 16 байт, в который будет возвращен шифр, а также key — 16-разрядный ключ. В процессе вычислений текущее состояние данных сохраняется в байтовом массиве state, размер которого равен NROWS х NCOLS. Для 128-битных блоков данных размер этого массива равен 4x4 байта. В 16 байтах целиком уместится один блок. Массив state изначально содержит открытый текст и модифицируется на каждом этапе вычислений. На некоторых этапах выполняется побайтовая подстановка. На других этапах — перестановка байтов внутри массива. Могут выполняться и другие преобразования. В конечном итоге содержимое state представляет собой зашифрованный текст, который и возвращается в качестве результата функции. Алгоритм начинается с распространения ключа по 11 массивам одинакового размера, представляющим состояние (state). Эти массивы хранятся в гк — массиве структур, содержащих массивы состояний. Одна из этих структур будет использована в начале вычислений, а остальные 10 — во время 10 итераций (по одной на итерацию). Вычисление ключа для каждой итерации производится довольно сложным образом, и мы не будем рассматривать детали этого процесса. Достаточно сказать, что для этого осуществляются циклические повороты и суммирования по модулю 2 различных групп разрядов ключа. Следующий шаг состоит в копировании открытого текста в массив state для того, чтобы его можно было обрабатывать во время последующих итераций. Копируется текст в колонки по 4 байта: первые 4 байта попадают в колонку 0, вторые — в колонку 1 и т. д. И колонки, и строки нумеруются с нуля, а итерации — с единицы. Процесс создания 12 байтовых массивов размером 4x4 показан на рис.

Перед началом основного цикла вычислений производится еще одно действие: rk[0] поразрядно складывается по модулю 2 с массивом state. Другими словами, каждый из 16 байт в массиве state заменяется суммой по модулю 2 от него самого и соответствующего байта в rk[0]. ТОЛЬКО после этого начинается главное развлечение. В цикле проводятся 10 итераций, в каждой из которых массив state подвергается преобразованию. Каждый раунд (итерация) состоит из четырех шагов. На шаге 1 в state производится посимвольная подстановка. Каждый байт по очереди используется в качестве индекса для S-блока, заменяющего его значение на соответствующую запись S-блока. На этом шаге получается прямой моноалфавитный подстановочный шифр. В отличие от DES, где используются несколько S-блоков, в Rijndael S-блок всего один. На шаге 2 каждая из четырех строк поворачивается влево. Строка 0 поворачивается на 0 байт (то есть не изменяется), строка 1 — на 1 байт, строка 2 — на 2 байта, а строка 3 — на 3 байта. Смысл заключается в разбрасывании данных вокруг блока. Это аналогично перестановкам, показанным на рис. 8.5. На шаге 3 происходит независимое перемешивание всех колонок. Делается это с помощью операции матричного умножения, в результате которого каждая новая колонка оказывается равной произведению старой колонки на постоянную матрицу. При этом умножение выполняется с использованием конечного поля Галуа, GF(2S). Несмотря на то, что все это кажется довольно сложным, алгоритм устроен так, что каждый элемент матрицы вычисляется посредством всего лишь двух обращений к таблице и трех суммирований по модулю 2. Наконец, на шаге 4 ключ данной итерации складывается по модулю 2 с массивом state. Благодаря обратимости всех действий расшифровка может быть выполнена с помощью такого же алгоритма, но с обратным порядком следования всех шагов. Однако есть одна хитрость, которая позволяет заниматься расшифровкой, используя алгоритм шифрования с измененными таблицами. Данный алгоритм обладает не только очень высокой защищенностью, но и очень высокой скоростью. Хорошая программная реализация на машине с частотой 2 ГГц может шифровать данные со скоростью 700 Мбит/с. Такой скорости достаточно для шифрации видео в формате MPEG-2 в реальном масштабе времени. Аппаратные реализации работают еще быстрее.

Режим шифрования

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

Electronic Code Book (ECB)

Сообщение делится на блоки. Каждый блок шифруется отдельно (независимо от других и на одном ключе). Этот режим называется режимом электронной кодовой книги, так как существует возможность создать книгу, в которой каждому блоку открытого текста будет сопоставлен блок зашифрованного текста. Однако создать книгу - нетривиальная задача. Если размер блока равен x бит, то в книге будет содержаться 2^x записей, и каждая книга будет соответствовать одному ключу.

Зашифрование может быть описано следующим образом : C_i = F(P_i) для любых i от 1 до N. Здесь C_i и P_i - блоки зашифрованного и открытого текстов соответственно, а F - функция блочного шифрования. Расшифровка по той же схеме. То есть P_i = F ^{− 1}(C_i).

Шифрование в режиме ECB

Дешифрование в режиме ECB

Недостатки:

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

Cipher Block Chaining (CBC)

Для сцепления используется механизм обратной связи, поскольку результат шифрации предыдущих блоков используется для шифрации текущего блока. Таким образом любой блок шифра зависит не только от исходного текста, но и от всех предыдущих блоков текста. В Cipher Block Chaining (CBC) текст XOR’ится с предыдущим шифр. блоком перед шифрацией. Дешифрация проводится аналогично. Математическая запись:

Ci = Ek (Pi XOR Ci-1)

Pi = Ci-1 XOR Dk(Ci)

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

Шифрование в режиме CBC

Дешифрование в режиме CBC

Большинство сообщений не делятся нацело на 64-битные блоки, обычно остается короткий блок в конце. Можно по-разному бороться с этим. Простейший метод – padding (дополнение до полного блока). Если надо потом убирать мусор, то достаточно просто последним байтом обозначить количество лишних байтов. Можно также обозначать последний байт текста символом конца файла. Это не всегда можно сделать (напр., если надо расшифровать блок и поставить его куда - нибудь в память). Тогда применяется следующая схема шифрования: предположим, в последнем блоке j бит. После зашифровки последнего целого блока, зашифруем шифрованный блок еще раз, выберем j начальных битов полученного текста и по XOR’им с исходным текстом. Это и есть шифр для неполного блока.

Cipher Feedback (CFB)

Режим (CFB) обратной связи шифра, близкий родственник CBC, превращает блочный шифр в самосинхронизирующийся шифр потока. Операция очень похожа на предыдущую; в частности расшифровка CFB почти идентична расшифровке CBC, выполненной наоборот:

C₀ = IV

где IV - вектор инициализации

Как режим CBC, изменения в открытом тексте распространяется повсюду в зашифрованном тексте, и в кодировании нельзя найти что-либо подобное. Также как и в CBC, в расшифровке можно найти что-либо подобное. Расшифровывая, однобитовое изменение в зашифрованном тексте затрагивает два блока открытого текста: однобитовое изменение в соответствующем блоке открытого текста, и полном искажении следующего блока открытого текста. Более поздние блоки открытого текста будут расшифрованы как обычно.

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

CFB совместно использует два преимущества перед режимом CBC с режимами OFB шифра потока и CTR: блочный шифр только когда-либо используется в направлении шифровки, и сообщение не должно быть дополнено к кратному числу размера блока шифра.

Output Feedback (OFB)

Режим (OFB) обратной связи вывода превращает блочный шифр в синхронный шифрпотока: это генерирует ключевые блоки, которые являются результатом сложения с блоками открытого текста, чтобы получить зашифрованный текст. Так же, как с другими шифрами потока, зеркальное отражение в зашифрованном тексте производит зеркально отраженный бит в открытом тексте в том же самом местоположении. Это свойство позволяет многим кодам с исправлением ошибок функционировать как обычно, даже когда исправление ошибок применено перед кодированием.

Из-за симметрии операции сложения, кодирование и расшифровка похожи:

O_i = E_k(O_{i − 1})

O₀ = IV

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

Уязвимость

Как и предполагали эксперты, после принятия алгоритма Rijndael в качестве стандарта AES попытки вскрытия данного алгоритма существенно усилились.

Можно сказать, что криптоанализ алгоритма AES стал развиваться, в основном, в следующих четырех направлениях:

Во-первых, попытки усиления «классических» атак или применения других известных атак к данному алгоритму. Например, была предложена атака методом бумеранга на 6-раундовую версию алгоритма со 128-битным ключом, для выполнения которой требуется 2³⁹ выбранных открытых текстов, 2⁷¹ шифртекстов с адаптивным выбором и 2⁷¹ операций шифрования.

Во-вторых, применение различных методов криптоанализа на связанных ключах, в частности были предложены следующие атаки:

• Было предложено несколько вариантов атак на связанных ключах на 7- и 8-раундовый AES-192 с использованием невозможных дифференциалов.
• Комбинация метода бумеранга и связанных ключей: 9-раундовый AES-192 атакуется при наличии 2⁷⁹ выбранных открытых текстов, каждый из которых шифруется на 256 связанных ключах, выполнением 2¹²⁵ операций шифрования; для атаки на 10-раундовый AES-256 требуется 2^114,9 выбранных открытых текстов (включая зашифрование на 256 связанных ключах) и 2^171,8 операций. Данная атака использует слабость процедуры расширения ключа, состоящую в ее недостаточной нелинейности.
• Предлагается атака на 10-раундовый алгоритм AES-192, для которой требуется 2¹²⁵ выбранных открытых текстов (на 256 связанных ключах) и 2^146,7 операций.

Несмотря на то, что предложенные атаки на связанных ключах являются весьма непрактичными, настораживает тот факт, что атаке подвержены уже 10 из 12 раундов алгоритма AES-192 (и это после всего 5 лет после принятия стандарта AES!) – возникает опасение, что эксперты (указывающие на недостаточность раундов в алгоритме Rijndael) были правы и полнораундовый алгоритм AES будет вскрыт существенно раньше, чем предполагали эксперты института NIST.

В-третьих, многие исследования посвящены алгебраической структуре алгоритма Rijndael, например:

• Найдены линейные соотношения в таблице замен Rijndael (т.е. в единственном нелинейном элементе алгоритма). Однако, как и в других аналогичных работах, каких-либо практических возможностей использования данного свойства не предложено.
• Зашифрование с помощью Rijndael можно выразить относительно (особенно по сравнению с другими «серьезными» алгоритмами шифрования) простой формулой. Авторы не нашли практического применения данной формулы, но предположили, что она будет использована в реальных атаках в течение ближайших примерно 20 лет.
• Показано, что вскрытие алгоритма AES эквивалентно решению системы квадратичных уравнений в конечном поле GF(28).

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

• Много работ содержат примеры успешного вскрытия различных реализаций полнораундового алгоритма AES с помощью атак по времени исполнения, потребляемой мощности и атак на основе сбоев.