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

4.1. Блочный шифр: структура и параметры

Блочный шифр предназначен для шифрования небольших блоков фиксированной длины. Длина блока большинства современных шифров составляет 64 или 128 бит. На выходе получается блок зашифрованного текста той же длины. Эта длина называется размером блока.

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

Рис. 4.1. Структура блочного шифра

Таким образом, различные блочные шифры отличаются следующими параметрами:

• Числом раундов n (c каждым новым раундом обработки надежность шифра повышается, но уменьшается скорость операций шифрования/дешифрования);
• Размером блока t (чем выше размер блока, тем больше надежность шифра, но скорость при этом снижается);
• Размером ключа k (чем он больше, тем более устойчив алгоритм к полному перебору);
• Алгоритмом генерации ключей раунда k₁ … k_n;
• Функцией раунда R. Именно эта функция является «сердцем» блочного шифра, определяющим параметры его надежности. Практически все функции раунда современных блочных алгоритмов шифрования строятся по одной из двух моделей: схема Файстеля или сеть подстановок и перестановок.

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

4.2. Диффузия и конфузия

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

Диффузия – каждый бит открытого текста должен влиять на каждый бит зашифрованного текста. Суть диффузии заключается в рассеянии статистических характеристик открытого текста внутри шифрованного текста.

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

Смысл обоих требований проще всего понять, вспомнив, как вскрывались классические шифры. Частотный анализ работал потому, что статистика открытого текста переходила в шифртекст без изменений: буква «о» оставалась самым частым символом, как ее ни переименовывай. Диффузия уничтожает эту возможность – если каждый бит шифртекста зависит от всех битов открытого текста, никакой локальной статистики, которую можно было бы сопоставить со статистикой языка, в шифртексте не остается. Атака же с известным открытым текстом на шифр Хилла удавалась потому, что между ключом и результатом существовала простая, линейная зависимость, позволявшая вычислить ключ решением системы уравнений. Конфузия закрывает эту дорогу: связь между ключом и шифртекстом должна быть настолько запутанной, чтобы никакое наблюдение за шифртекстом не сокращало перебор ключей.

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

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

4.3. Схема Файстеля

Многие блочные шифры построены на основе структуры шифра Файстеля, разработанного в 1973 году.

На вход алгоритма шифрования подается блок открытого текста, имеющий четную длину 2l и ключ K. Блок разделяется на две равные части – правую R₀ и левую L₀. Далее эти части проходят m раундов обработки, после чего снова объединяются в зашифрованный текст.

Каждый i-й раунд состоит в генерации подключа K_i (на основе общего ключа K) и применении к блоку R_i некоторого преобразования F, зависящего от ключа. Результат складывается с блоком L_i с помощью операции XOR (исключающее или) и получается блок R_i+1. Блок R_i без изменений берется в качестве блока L_i+1.

Таким образом, получаются следующие формулы:

L_i+1 = R_i

R_i+1 = L_i ⊕ F(K_i, R_i)

Рис. 4.2. Схема i-го раунда шифрования шифра Файстеля

Схема Файстеля не зависит от конкретного выбора функции F. Это ее ключевое преимущество. Шифрование одного блока происходит путем наложения на него преобразованного второго блока, а снимается это наложение тем же действием (благодаря самообратимости операции ⊕). Поэтому в обоих случаях используется прямое вычисление функции F, а значит, можно использовать сложные и криптографически сильные преобразования, которые не обязательно обратимы, что значительно упрощает разработку шифров.

Независимо от выбранной функции процесс дешифрования принципиально ничем не отличается от процесса шифрования. Просто на вход подается зашифрованный текст, а ключи K_i вычисляются в обратном порядке. Это крайне удобно с точки зрения реализации (особенно аппаратной).

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

Рассмотрим один i-ый раунд шифрования и соответствующий раунд дешифрования. Наша цель – показать, что если мы зашифруем (L_i , R_i), а затем расшифруем результат, то мы получим обратно (L_i , R_i).

Подаем для шифрования (L_i , R_i). Получаем результат (L_i+1 , R_i+1), где R_i+1 = L_i ⊕ F(K_i, R_i), в соответствии с приведенными выше формулами схемы Файстеля.

Дешифрование выполняется в обратном порядке раундов, то есть

В дешифровании используются те же ключи K_i, что и в шифровании, но в обратном порядке.

Подаем для дешифрования (L_i+1, R_i+1). Пусть получится результат (L′_i, R′_i), где R′_i = L_i+1, L′_i = R_i+1⊕ F(K_i, L_i+1). Покажем, что R′_i = R_i, L′_i = L_i

R′_i = L_i+1 = R_i (исходя непосредственно из формул схемы Файстеля).

L′_i = R_i+1⊕ F(K_i, L_i+1) = (L_i ⊕ F(K_i, R_i)) ⊕ F(K_i, L_i+1) = L_i ⊕ (F(K_i, R_i) ⊕ F(K_i, L_i+1)) = L_i ⊕ 0 = L_i

В доказательстве второго равенства последовательно использовались некоторые свойства операции ⊕, а именно: ассоциативность (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c), самообратимость a ⊕ a = 0, нейтральность a ⊕ 0 = a.

Таким образом, R′_i = R_i, L′_i = L_i. То есть после одного раунда шифрования и дешифрования мы возвращаемся к исходному состоянию, что и требовалось доказать. Далее по индукции доказательство распространяется на все раунды.

Схема Файстеля обладает и более сильным свойством, чем корректность. Доказано, что если функция раунда F безопасна, а ключи раундов независимы, то трехраундовая схема Файстеля неотличима от случайной перестановки для противника, способного подавать на вход произвольные открытые тексты. Четыре раунда дают более сильный результат: неотличимость сохраняется и тогда, когда противник вдобавок может запрашивать дешифрование выбранных им шифртекстов.

Под безопасной функцией в криптологии понимается такая функция, которую нельзя по выходу отличить от истинно случайной функции. Представим себе множество всех функций, которые переводят n-битный блок в другой n-битный блок. Можно представить каждую функцию таблицей вход-выход (т.е. набором значений). Всего таких функций невообразимо гигантское число (для 128-битного блока это 2¹²⁸ в степени 2¹²⁸). Среди них есть и те, которые заданы аналитически, то есть, некоторой формулой, правилом, например, функция f(x) = x. Зная это правило, мы легко вычисляем значение функции. Представим себе противника, который пытается отгадать это правило, подавая на вход функции различные значения и наблюдая за результатом. Если противник, совершая сколь угодно большое число попыток, не может это правило отгадать и научиться предсказывать значения нашей функции для тех входных данных, которые он еще не тестировал (другими словами не может отличить нашу функцию от истинно случайной функции, взятой из этого гигантского множества), то назовем такую функцию безопасной.

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

4.4. Алгоритм DES и S-матрицы

Долгое время самым популярным алгоритмом симметричного шифрования являлся DES (Data Encryption Standard), принятый в качестве федерального стандарта США в 1977 году. Этот алгоритм построен по схеме Файстеля и использует блок размером 64 бита, ключ длиной 56 бит и 16 раундов шифрования.

Преобразование F заключается в следующем:

1. 32-битовый блок R_i расширяется до 48 битов с помощью специальной таблицы путем дублирования определенных битов.

2. Полученный результат складывается с 48-битным подключом K_i операцией XOR.

3. Результат сложения разбивается на 8 шестибитовых блоков, и каждый из них преобразуется с помощью одной из восьми S-матриц.

4. Получившийся в итоге 32-битный блок подвергается жестко заданной в алгоритме перестановке.

Корректность алгоритма DES полностью основана на корректности схемы Файстеля, доказательство которой было приведено выше. Надежность же держится на устройстве преобразования F, а хороший лавинный эффект служит измеримым признаком того, что диффузия достигнута: изменение одного бита открытого текста или ключа приводит к изменению многих битов зашифрованного текста.

S-матрицы, ставшие популярными вместе с алгоритмом DES, превратились в один из криптографических примитивов – регулярно используемых строительных блоков шифров и других криптографических алгоритмов.

Идея S-матрицы очень проста. По сути, она представляет собой таблично заданную функцию: для каждого входного значения «вручную» указывается выходное значение.

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

Пусть m₁, m₂, … m_n – входные биты, а c₁, c₂ … c_n – выходные биты некоторого преобразования. Если для некоторых i найдутся такие a_i1 … a_in, что наблюдается равенство c_i = a_i1m₁ ⊕ a_i2m₂ ⊕  … ⊕ a_inm_n для всех входных сообщений, то будем говорить, что существует линейная зависимость между входными битами и выходным битом c_i. Для того, чтобы найти эту зависимость (т.е. a_i1 … a_in) достаточно решить систему уравнений с n неизвестными.

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

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

S-матрица – это способ задать вручную функцию, которую нельзя задать аналитически (в том числе с помощью линейных зависимостей). Например, одна из матриц алгоритма DES выглядит следующим образом:

Таблица 4.1. Одна из S-матриц алгоритма DES

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

В DES S-матрицы задают преобразование 6-битного блока в 4-битный. Входной блок делится на 2 части: номер строки (первый и последний бит, комбинация которых дает значения от 0 (00₂) до 3 (11₂)) и номер столбца (четыре средних бита, комбинация которых дает значения от 0 (0000₂) до 15 (1111₂)). Число на пересечении соответствующих строки и столбца (в двоичной записи) и есть результат преобразования. То же самое можно было записать в виде простой таблицы из 64 строк, указав соответствие для каждого входного блока.

S-матрицы считались самой сомнительной частью алгоритма DES, поскольку создатели алгоритма не раскрыли принципы их заполнения (почему выбраны именно эти матрицы и не содержит ли алгоритм «тайных ходов»). Однако за годы попыток взлома этого алгоритма была выявлена незначительная слабость лишь одной из этих матриц.

Найденные за четверть века атаки на DES – дифференциальная и линейная – формально быстрее полного перебора, но требуют такого объема перехваченного текста, какого не дает ни одна реальная система. Более того, со временем выяснилось, что его S-матрицы подобраны с прямым расчетом на противодействие дифференциальному криптоанализу – методу, который научное сообщество открыло лишь через полтора десятилетия после разработки шифра. Погубила DES не ошибка в конструкции, а короткая длина ключа: 56 бит, спорные уже при принятии стандарта, к концу 1990-х перебирались специализированным устройством за двое суток. Алгоритм не был взломан, он пал от прогресса вычислительных мощностей. Временной мерой стал тройной DES – троекратное применение того же алгоритма с двумя или тремя различными ключами, но такое решение втрое медленнее и сохраняет 64-битный блок, малый по современным меркам.

4.5. Сеть подстановок и перестановок

Сеть подстановок и перестановок – вторая популярная схема построения современных блочных шифров (рис. 4.3).

Рис. 4.3. Сеть подстановок и перестановок

На каждом раунде шифрования входной блок складывается по модулю 2 (XOR) с ключом раунда, а затем разбивается на фрагменты (внутренние блоки), к каждому из которых применяется некоторая подстановка. После этого биты блока меняются местами – выполняется перестановка. Подстановки и перестановки являются фиксированными (жестко заданными для конкретного алгоритма) и не зависящими от ключа.

Подстановки (по аналогии с S-матрицами), как правило, задаются в виде нелинейной табличной функции. Их называют S-подстановками.

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

При внешней простоте сеть подстановок и перестановок способна гарантированно обеспечить лавинный эффект. Представим, что во входном блоке изменился всего один бит. В первом раунде шифрования это изменение затронет только одну подстановку, но на выходе этой подстановки будут изменены уже несколько битов (в силу ее нелинейности). Измененные биты в результате воздействия перестановки разлетятся на несколько внутренних блоков второго раунда и попадут на вход уже нескольких подстановок. Через 3-4 раунда это изменение, так или иначе, затронет все внутренние блоки и скажется практически на каждом бите. Аналогичным образом обеспечивается свойство конфузии (изменение хотя бы одного бита ключа приведет к изменению хотя бы одного бита в ключах раунда, а после сложения с открытым текстом перед применением подстановок и перестановки мы получим тот же результат, что и при изменении бита открытого текста).

Сравним две схемы. Схема Файстеля не предъявляет к функции раунда никаких требований, кроме детерминированности: обратимость обеспечивается самой конструкцией, а не свойствами функции. Это позволяет использовать сколь угодно сложные функции раунда, но за каждое преобразование платит лишь половина блока – вторая половина в этом раунде переезжает налево нетронутой, поэтому для полного перемешивания требуется больше раундов. Сеть подстановок и перестановок, напротив, обрабатывает весь блок на каждом раунде и достигает лавинного эффекта быстрее, но требует, чтобы все ее элементы были обратимы, и делает дешифрование не тождественным шифрованию: нужны обратные подстановки и обратные перестановки, то есть, по сути, второй комплект таблиц. В аппаратной реализации, где важен объем схемы, это заметный недостаток; в программной он почти незаметен.

4.6. Алгоритм AES

К концу 1990-х годов необходимость замены DES стала очевидной. В 1997 году Национальный институт стандартов и технологий США объявил открытый конкурс на новый алгоритм шифрования, которому предстояло стать стандартом на ближайшие десятилетия. Заявки публиковались полностью, участники получали возможность анализировать работы конкурентов, и результаты этого анализа учитывались при отборе. Доверие к алгоритму обеспечивалось безуспешными попытками его сломать. Победитель конкурса был определен в 2000 году – им стал бельгийский шифр RIJNDAEL, который был переименован в AES (Advanced Encryption Standard).

AES построен на основе сети подстановок и перестановок. В нем используется 128-битный блок и 8-битные S-подстановки (16 внутренних блоков). Длина ключа K составляет 128, 192 или 256 бит. Число раундов шифрования зависит от длины ключа (10, 12 и 14 раундов соответственно).

Рассмотрим устройство одного раунда AES.

Обрабатываемый блок из 128 бит представляется в виде матрицы 4×4, которую называют состоянием; каждая ячейка содержит один байт. Раунд состоит из четырех шагов.

• SubBytes – подстановка. Каждый байт состояния независимо заменяется другим байтом по таблице (S-подстановке). Это единственный нелинейный шаг алгоритма, и именно он отвечает за конфузию.
• ShiftRows – перестановка. Строки матрицы циклически сдвигаются влево: нулевая – на ноль байтов, первая – на один, вторая – на два, третья – на три. Байты при этом переезжают из столбца в столбец.
• MixColumns – перемешивание. Каждый столбец матрицы преобразуется целиком: четыре новых байта получаются как линейные комбинации четырех старых, так что каждый байт столбца влияет на все четыре байта результата.
• AddRoundKey – наложение ключа. Состояние складывается по модулю 2 с ключом раунда.

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

В отличие от таблиц DES, заполненных по нераскрытым правилам, S-подстановка AES задана явной математической формулой: байт трактуется как элемент конечного поля из 256 элементов, для него берется обратный элемент (нулю сопоставляется ноль), после чего результат подвергается фиксированному аффинному преобразованию. Взятие обратного элемента дает сильную нелинейность, а аффинное преобразование разрушает алгебраическую простоту полученной зависимости. Такое построение прямо отвечает на главную претензию, предъявлявшуюся к DES: авторы AES не просто опубликовали таблицу, но и показали, откуда взялось каждое ее значение, тем самым лишив себя возможности что-либо в ней спрятать.

Обе рассмотренные схемы представлены в действующих стандартах. Так, российский стандарт блочного шифрования включает сразу два алгоритма, построенных по-разному. «Магма» – шифр с 64-битным блоком и 256-битным ключом, наследующий конструкцию Файстеля от стандарта 1989 года. «Кузнечик» – шифр со 128-битным блоком и тем же размером ключа, построенный как сеть подстановок и перестановок.

Третий популярный подход – шифры семейства ARX. Они не используют таблицы подстановки, а строятся на основе трех операций: сложения (A), циклического сдвига (R) и исключающего или (X), которые процессор выполняет быстро и, что существенно, за фиксированное время. Отсутствие обращений к таблицам делает такие шифры устойчивыми к атакам по времени выполнения, при которых противник получает информацию о ключе или открытом тексте, измеряя точное время выполнения операций программой. Наиболее известный представитель этого семейства – потоковый шифр ChaCha20, шифрующий поток бит, а не блоки фиксированной длины; он широко применяется там, где нет аппаратной поддержки AES. Среди блочных шифров тем же способом построены Threefish и XTEA.

Блочные шифры принципиально используют ту же комбинацию замены и перестановки, что и классические алгоритмы, просто выполняют ее над блоком двоичных данных и повторяют столько раз, сколько нужно, чтобы влияние каждого входного бита распространилось на все выходные. Способность ЭВМ многократно выполнять одни и те же операции без ошибок позволила перейти к планированию таких свойств алгоритма как диффузия, конфузия и лавинный эффект на этапе проектирования.