Блочные шифры: DES, AES и принципы построения

Блочный шифр (англ. block cipher) берёт блок фиксированной длины — 64 или 128 бит — и ключ, и возвращает блок той же длины. Всё остальное в симметричной криптографии строится поверх этой операции: режимы шифрования превращают её в шифрование произвольных данных (тема 7), коды аутентификации — в защиту целостности (тема 9), а аутентифицированное шифрование — в готовый инструмент. Поэтому блочный шифр — самый изученный и самый стандартизованный криптографический примитив: AES за четверть века не получил ни одной практически значимой атаки, хотя попыток было больше, чем против любого другого алгоритма.

Тема разбирает два поколения. Первое — DES: 64-битный блок, 56-битный ключ, сеть Фейстеля, шестнадцать раундов, история создания под давлением АНБ и публичного взлома в 1998 году. DES интересен не как рабочий алгоритм (он давно не используется), а как источник идей: сеть Фейстеля, S-боксы, дифференциальный и линейный криптоанализ — всё это выросло из его анализа. Второе — AES: 128-битный блок, ключи 128, 192 и 256 бит, SP-сеть, четыре преобразования в раунде, конкурс NIST и победа Rijndael. AES разбирается до уровня отдельного байта: подстановка через обращение в GF(2^8), сдвиг строк, умножение столбцов, расписание ключей — с проверкой на тестовом векторе FIPS 197.

Отдельно и подробно рассматриваются отечественные стандарты ГОСТ Р 34.12-2015: зачем понадобилась замена ГОСТ 28147-89, как устроены «Кузнечик» и «Магма», откуда взялся S-бокс «Кузнечика», что известно о стойкости обоих шифров и какие инженерные ловушки ждут реализатора. Затем — криптоанализ: дифференциальный, линейный, связанные ключи, атаки по сторонним каналам и роль аппаратных инструкций AES-NI. Завершает тему разговор о размерах блока: 64-битный блок при больших объёмах данных даёт коллизии, и это не теория, а атака Sweet32 на TLS и OpenVPN.

Паспорт темы. Нужно знать: темы 0, 2. Освоите: объяснять PRP и лавинный эффект; строить сеть Фейстеля; разбирать раунд AES по шагам; описывать «Магму» и «Кузнечик»; оценивать границы 64-битного блока; называть побочные каналы и меры против них. Проверяет: ЛР 6. Минимум: разделы 1–4. Углубление: разделы 5–6.

Блочный шифр как семейство перестановок

Определение и модель стойкости

Формально блочный шифр — это функция E: {0,1}^k × {0,1}^n → {0,1}^n, где k — длина ключа, n — длина блока. Для каждого фиксированного ключа K отображение E(K, ·) должно быть перестановкой на множестве блоков: обратимым и взаимно однозначным. Идеальная модель — семейство случайных перестановок (англ. pseudo-random permutation, PRP): противник, не знающий ключ, не может отличить E(K, ·) от случайно выбранной перестановки, даже если может запросить шифрование и расшифрование для любых блоков.

Стойкость PRP формулируется через игру, как и неразличимость из темы 2. Противник получает оракул, который либо шифрует настоящим ключом, либо реализует случайную перестановку, и должен угадать, что перед ним. Преимущество противника должно быть пренебрежимо мало. Отличие от IND-CPA в том, что здесь нет сообщений и шифртекстов в привычном смысле: противник видит отдельные блоки, а оракул детерминирован.

Из этой модели следует важное: блочный шифр сам по себе не является схемой шифрования. Он детерминирован, поэтому одинаковые блоки дают одинаковые шифртексты, и режим ECB (тема 7) немедленно выдаёт структуру данных. Блочный шифр — кирпич; схема шифрования — здание, и её свойства определяются режимом, а не только примитивом ¹².

У блочного шифра есть параметры, которые нельзя выбирать произвольно. Длина блока определяет границы применимости: 64-битный блок после 2^32 блоков даёт коллизии с высокой вероятностью, что ограничивает объём данных под одним ключом. Длина ключа определяет стойкость к перебору. Число раундов определяет запас против криптоанализа. Все три величины фиксируются стандартом, а не разработчиком приложения.

Принципы Шеннона: рассеивание и перемешивание

Клод Шеннон сформулировал два требования, которым должен удовлетворять стойкий шифр. Первое — рассеивание (англ. diffusion): изменение одного бита открытого текста должно менять много бит шифртекста, и наоборот. Второе — перемешивание (англ. confusion): связь между ключом и шифртекстом должна быть настолько сложной, чтобы статистика шифртекста не давала сведений о ключе.

Оба требования реализуются композицией простых операций. Замена (нелинейная, обычно через таблицу) даёт перемешивание: она разрушает линейные соотношения между битами. Перестановка (линейная, обычно сдвиг или транспозиция) даёт рассеивание: она разносит влияние каждого бита по всему блоку. Чередование замен и перестановок в нескольких раундах — универсальный рецепт, по которому построены DES, AES, «Кузнечик» и почти всё остальное.

Ключ входит в каждом раунде — обычно сложением с раундовым ключом. Отсюда требование к расписанию ключей (англ. key schedule): раундовые ключи должны быть различны и должны зависеть от всех бит основного ключа, иначе часть ключа окажется неиспользованной и пространство поиска сократится.

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

Лавинный эффект

Количественная мера рассеивания — лавинный эффект (англ. avalanche effect): при изменении одного бита входа половина бит выхода должна измениться, то есть около n/2 бит для блока длиной n. Для AES это 64 бита из 128.

Идеальное значение — биномиальное распределение с центром в n/2 и стандартным отклонением √(n)/2 = 5,66 для n = 128. Практически шифр считается хорошим, если после достаточного числа раундов распределение близко к этому.

В лабораторной работе измеряется на 1000 испытаниях: при инвертировании одного бита открытого текста среднее число изменённых бит шифртекста равно 64,00, минимум 46, максимум 86; при инвертировании одного бита ключа — среднее 63,77, минимум 41, максимум 84. Разброс объясняется тем, что полный AES — не идеальная случайная перестановка, а его выходы коррелированы на уровне, который статистика такого объёма уже замечает.

Распределение числа изменённых бит показано на схеме ниже: оно сосредоточено вокруг 64, а хвосты уходят к 46 и 86.

Лавинный эффект полезен как диагностика при реализации: если после одного раунда среднее число изменённых бит близко к 4–8, а после десяти — к 64, реализация, скорее всего, верна. Если после десяти раундов среднее остаётся низким, почти наверняка перепутано направление ShiftRows или потерян MixColumns в последнем раунде.

Сеть Фейстеля и DES

Устройство сети Фейстеля

Сеть Фейстеля (англ. Feistel network) — конструкция, которая делает блочный шифр обратимым без требования обратимости раундовой функции. Блок делится на две половины L и R, и раунд описывается двумя равенствами: L' = R и R' = L ⊕ F(R, K).

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

Обратимость проверяется в одну строку: из L' = R и R' = L ⊕ F(R, K) следует R = L', затем L = R' ⊕ F(L', K). Функция F может быть сколь угодно необратимой — она не обязана быть биекцией, потому что никогда не «расшифровывается» отдельно.

Это свойство дало DES и его наследникам два достоинства: раундовая функция может содержать необратимые операции (таблицы, усечения), и аппаратная реализация получается симметричной — один и тот же блок логики работает и на шифрование, и на расшифрование. Плата — скорость диффузии: за один раунд меняется только половина блока, поэтому нужно больше раундов, чем в SP-сети. DES делает 16, «Магма» — 32.

def feistel_encrypt(block, keys, f):
    left, right = block[:len(block) // 2], block[len(block) // 2:]
    for k in keys:
        left, right = right, bytes(a ^ b for a, b in zip(left, f(right, k)))
    return left + right


def feistel_decrypt(block, keys, f):
    left, right = block[:len(block) // 2], block[len(block) // 2:]
    for k in reversed(keys):
        left, right = right, bytes(a ^ b for a, b in zip(left, f(right, k)))
    return left + right

Функция f здесь может быть любой, даже возвращающей константу, — обратимость сохранится. Стойкость, разумеется, нет: если f игнорирует вход, шифр вырождается в перестановку половин с XOR константы. Именно поэтому лабораторная работа проверяет обратимость на заведомо необратимой f и отдельно — что при слабой f шифр ломается тривиально.

DES: параметры и раунд

DES (англ. Data Encryption Standard) принят как федеральный стандарт США в 1977 году ². Параметры: блок 64 бита, ключ 64 бита, из которых 8 — проверочные биты чётности, поэтому реальная длина ключа 56 бит; шестнадцать раундов; раундовая функция включает расширение 32 бит до 48, сложение с 48-битным раундовым ключом, восемь S-боксов по 6 входных бит и 4 выходных, и перестановку.

S-боксы — единственная нелинейная часть DES, и вокруг них была основная интрига: в конце 1980-х выяснилось, что они защищают от дифференциального криптоанализа, который в то время был известен только АНБ и переоткрыт Бихэмом и Шамиром лишь в 1990 году ⁴. Это важный исторический урок: критерии проектирования S-боксов были засекречены, и сообщество двадцать лет не знало, что они не случайны.

История создания DES показательна и сама по себе. Исходный алгоритм Lucifer от IBM имел 128-битный ключ; после участия АНБ ключ сократили до 56 бит, а S-боксы изменили. Публично это объяснялось требованиями к размеру кремния, и в 1977 году Диффи и Хеллман опубликовали работу, где оценили стоимость перебора 56-битного ключа в 20 миллионов долларов и предложили 3DES как замену ¹¹. Оценка оказалась завышенной, но направление — верным.

Взлом DES и встреча посередине

DES продержался двадцать лет, потому что 56-битный ключ был на границе возможного: перебор 2^56 операций в 1977 году был недоступен, а в 1998 году — уже нет. Машина EFF DES Cracker стоимостью около 250 тысяч долларов находила ключ в среднем за несколько дней ⁷, и после этого DES был объявлен устаревшим.

Стандартный способ продлить жизнь алгоритму — применить его несколько раз. Двойное шифрование DES (2DES) выглядит логично: C = E(K₂, E(K₁, P)), и ключ как будто 112 бит. Это ошибка, и ошибка классическая. Атака «встреча посередине» (англ. meet-in-the-middle) находит ключ за 2^56 операций и 2^56 памяти:

def meet_in_the_middle(encrypt, decrypt, plaintext, ciphertext, key_space):
    table = {}
    for k1 in key_space:
        table[encrypt(k1, plaintext)] = k1
    for k2 in key_space:
        cand = decrypt(k2, ciphertext)
        if cand in table:
            return table[cand], k2
    return None

Идея: для правильной пары (K₁, K₂) значение после первого шифрования совпадает со значением после первого расшифрования с другого конца. Перебирая все K₁ и запоминая промежуточные значения, а затем перебирая все K₂ и ища совпадение, получаем ключ за два перебора по 2^56 вместо одного по 2^112. Удвоение числа применений даёт лишь удвоение работы, а не возведение в квадрат.

Поэтому стандартом стал тройной DES (3DES) с вариантами на два ключа (K₁, K₂, K₁, 112 бит) и на три ключа (K₁, K₂, K₃, 168 бит). Против 3DES работают атаки сложности 2^112 и 2^168 соответственно, и он оставался допустимым до 2023 года, когда NIST окончательно запретил его для новых применений. Практическая причина отказа — не стойкость, а низкая скорость и малый размер блока: 64 бита дают коллизии после 2^32 блоков, а это всего 32 ГиБ данных.

AES

Конкурс NIST и Rijndael

К концу 1990-х стало ясно, что DES исчерпан, а 3DES неудобен. В 1997 году NIST объявил открытый конкурс на новый стандарт — Advanced Encryption Standard. Требования: блок 128 бит, ключи 128, 192 и 256 бит, скорость не ниже 3DES на всех платформах, простота анализа и возможность реализации в постоянном времени.

Из пятнадцати первоначальных заявок в финал 1999 года вышли пять: MARS, RC6, Serpent, Twofish и Rijndael. В 2000 году победил Rijndael — алгоритм Йоана Дэмена и Винсента Раймена ³. В 2001 году он опубликован как FIPS 197 ¹, а в 2001–2003 годах прошёл дополнительный период публичного анализа.

Показательно, что выбор был сделан по совокупности свойств, а не по «максимальной стойкости»: все пять финалистов считались стойкими, и решали скорость, размер кода, поведение на 8-битных платформах и простота анализа. Rijndael выиграл за счёт хорошей производительности на всём — от смарт-карт до серверов, — и за счёт того, что его структура поддаётся анализу (что одновременно означает, что её легче проверить).

Название «Rijndael» и «AES» не полностью совпадают: Rijndael поддерживает блоки 128, 192 и 256 бит, а AES фиксирует блок 128 бит. В AES-192 и AES-256 удлиняется только ключ, блок остаётся 128-битным.

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

Состояние и порядок раундов

Состояние AES — матрица 4×4 байта, всего 16 байт. Байты входного блока укладываются по столбцам: первый байт попадает в позицию (0,0), второй — в (1,0), пятый — в (0,1). Схема ниже показывает укладку и то, как ShiftRows сдвигает строки на разные величины.

Раунд AES состоит из четырёх преобразований:

• SubBytes — нелинейная замена каждого байта по таблице;
• ShiftRows — циклический сдвиг строк на 0, 1, 2 и 3 позиции;
• MixColumns — умножение каждого столбца на фиксированную матрицу в GF(2^8);
• AddRoundKey — XOR с раундовым ключом.

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

Схема ниже показывает полный путь одного раунда.

SubBytes: обращение в GF(2^8) и аффинное преобразование

SubBytes — единственная нелинейная часть AES, и устроена она элегантно: каждый байт b заменяется на S[b], где таблица S построена из двух шагов. Сначала вычисляется обратный элемент в GF(2^8) (для нуля результат считается нулём), затем к нему применяется аффинное преобразование над GF(2):

b' = a⁻¹ ⊕ rotl(a⁻¹, 1) ⊕ rotl(a⁻¹, 2) ⊕ rotl(a⁻¹, 3) ⊕ rotl(a⁻¹, 4) ⊕ 0x63

Нелинейность даёт обращение: a → a⁻¹ — не линейная функция над GF(2), и именно она обеспечивает перемешивание. Аффинное преобразование добавлено, чтобы убрать алгебраическую простоту: без него S-бокс был бы слишком «красивым» с точки зрения алгебраических атак.

Обращение реализуется либо как a^254 (по теореме Лагранжа для группы порядка 255, см. тему 4), либо через таблицу логарифмов, либо через расширенный алгоритм Евклида над многочленами. В лабораторной работе проверяются оба способа и их совпадение.

Полезное следствие для диагностики: S[0x00] = 0x63, S[0x01] = 0x7C, S[0x53] = 0xED. Если таблица в реализации начинается с 0x63, 0x7C, 0x77, 0x7B, она почти наверняка верна.

ShiftRows и MixColumns

ShiftRows — простая перестановка: строка 0 не сдвигается, строка 1 сдвигается влево на 1 байт, строка 2 — на 2, строка 3 — на 3. Она даёт рассеивание по столбцам: байт, стоявший в одном столбце, после сдвига оказывается в разных.

MixColumns — умножение каждого столбца на матрицу

2 3 1 1
1 2 3 1
1 1 2 3
3 1 1 2

все операции в GF(2^8) по модулю x^8 + x^4 + x^3 + x + 1. Умножение на 2 — это xtime, то есть сдвиг влево и XOR с 0x1B при переполнении; умножение на 3 — это xtime(a) ⊕ a. Матрица выбрана так, чтобы она была обратимой (её определитель не равен нулю в поле) и чтобы обеспечивать максимальное рассеивание за один раунд.

def xtime(a):
    a <<= 1
    if a & 0x100:
        a ^= 0x11B
    return a & 0xFF


def mix_columns(state):
    out = [0] * 16
    for c in range(4):
        col = state[c * 4:c * 4 + 4]
        out[c * 4 + 0] = xtime(col[0]) ^ (xtime(col[1]) ^ col[1]) ^ col[2] ^ col[3]
        out[c * 4 + 1] = col[0] ^ xtime(col[1]) ^ (xtime(col[2]) ^ col[2]) ^ col[3]
        out[c * 4 + 2] = col[0] ^ col[1] ^ xtime(col[2]) ^ (xtime(col[3]) ^ col[3])
        out[c * 4 + 3] = (xtime(col[0]) ^ col[0]) ^ col[1] ^ col[2] ^ xtime(col[3])
    return out

Комбинация ShiftRows и MixColumns даёт важное свойство: за два раунда каждый выходной байт зависит от всех шестнадцати входных. Это называют свойством полной диффузии, и именно оно объясняет, почему AES достигает лавинного эффекта за четыре раунда, тогда как DES — только за восемь.

Расписание ключей и разбор на тестовом векторе

Расписание ключей (англ. key expansion) разворачивает ключ в 4·(Nr + 1) слов по 32 бита. Для AES-128 это 44 слова: первые четыре — сам ключ, каждое следующее получается как XOR предыдущего с результатом g-функции от слова, отстоящего на четыре позиции назад, причём g применяется только к каждому четвёртому слову. Функция g состоит из циклического сдвига байт, SubBytes и XOR с константой раунда RCON.

def key_expansion(key):
    w = [list(key[i * 4:(i + 1) * 4]) for i in range(4)]
    for i in range(4, 44):
        temp = w[i - 1][:]
        if i % 4 == 0:
            temp = temp[1:] + temp[:1]
            temp = [SBOX[b] for b in temp]
            temp[0] ^= RCON[i // 4 - 1]
        w.append([w[i - 4][j] ^ temp[j] for j in range(4)])
    return [sum(w[4 * r:4 * r + 4], []) for r in range(11)]

Для ключа 2b7e151628aed2a6abf7158809cf4f3c (это ключ из приложения B стандарта FIPS 197) раундовые ключи начинаются так:

раунд 0  2b7e151628aed2a6abf7158809cf4f3c
раунд 1  a0fafe1788542cb123a339392a6c7605
раунд 2  f2c295f27a96b9435935807a7359f67f
…
раунд 10 d014f9a8c9ee2589e13f0cc8b6630ca6

Теперь полный тестовый вектор приложения B: открытый текст 3243f6a8885a308d313198a2e0370734, тот же ключ, шифртекст 3925841d02dc09fbdc118597196a0b32 ¹. Проверка по шагам первого раунда показывает, как состояние меняется после каждого преобразования, и это лучший способ найти ошибку в реализации: расхождение обнаруживается не в конце, а на конкретном шаге.

Второй вектор — приложение C.1, ключ 000102030405060708090a0b0c0d0e0f, открытый текст 00112233445566778899aabbccddeeff, шифртекст 69c4e0d86a7b0430d8cdb78070b4c55a. Он удобен тем, что все байты различимы, и ошибки перестановки видны сразу.

openssl enc -aes-128-ecb -K 000102030405060708090a0b0c0d0e0f -nopad \
  -in <(printf '\x00\x11\x22\x33\x44\x55\x66\x77\x88\x99\xaa\xbb\xcc\xdd\xee\xff') | xxd -p

Команда должна вывести 69c4e0d86a7b0430d8cdb78070b4c55a. Сверка с OpenSSL полезна не только как проверка результата, но и как проверка формата ключа: -K ожидает шестнадцатеричную строку без префикса 0x, а -iv для ECB не нужен — и если добавить его для GCM, ошибка будет совсем в другом месте.

Отечественные стандарты ГОСТ Р 34.12-2015

Стандарт 2015 года устроен необычно: в нём два блочных шифра с разными размерами блока. «Магма» — это ГОСТ 28147-89 с зафиксированными параметрами, «Кузнечик» — новый алгоритм. Такая пара отражает переходный период: старый шифр нужно было сохранить для совместимости, новый — дать системам, которым 64-битного блока уже мало. Ниже разбираются оба: зачем понадобилась замена, как устроены алгоритмы, откуда взялся S-бокс «Кузнечика», что известно о стойкости и какие инженерные ловушки ждут реализатора.

Зачем понадобился новый стандарт

ГОСТ 28147-89 разработан в 1970-х годах в Восьмом главном управлении КГБ СССР; работы над алгоритмом начались в 1976–1978 годах, опубликован он был только в 1989 году и введён в действие с 1 июля 1990 года. Параметры: блок 64 бита, ключ 256 бит, 32 раунда сети Фейстеля. Алгоритм пережил страну, которая его создала, и к 2010-м годам оставался обязательным для сертифицированных средств криптографической защиты информации (СКЗИ) в России и ряде стран СНГ.

К этому времени проявились три ограничения. Первое — размер блока. Как показано выше, 64-битный блок после 2^32 блоков даёт коллизии, то есть 32 ГиБ данных под одним ключом; для TLS-сессий, VPN и дискового шифрования это достижимо, и атака Sweet32 ⁸ показала это на практике. Второе — узлы замены. В ГОСТ 28147-89 они не были зафиксированы: стандарт предписывал поставлять их «в установленном порядке», и на практике существовало несколько наборов (CryptoPro-A, CryptoPro-B и другие). Один и тот же ключ с разными S-боксами даёт разные шифртексты, поэтому совместимость приходилось обеспечивать вручную, а проверить, что поставщик не подменил таблицы, было невозможно. Третье — расписание ключей: восемь подключей повторяются трижды, а затем идут в обратном порядке. Такая симметрия порождает атаки на основе отражений и неподвижных точек, и именно из-за слабостей расписания ГОСТ 28147-89 не был включён в ISO/IEC 18033 в 2010 году ²⁰.

Ответом стал ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры», утверждённый приказом Росстандарта 19 июня 2015 года ⁶. В нём два алгоритма: «Магма» — тот же ГОСТ 28147-89, но с зафиксированным S-боксом и другим порядком байтов, и «Кузнечик» — новый шифр со 128-битным блоком. Режимы работы и выработка имитовставки вынесены в отдельный стандарт ГОСТ Р 34.13-2015. В 2018 году принят межгосударственный ГОСТ 34.12-2018, а с 31 мая 2019 года ГОСТ 28147-89 в России отменён: с 1 июня 2019 года новые СКЗИ на нём не разрабатываются, использование допускается только для совместимости с уже существующими системами.

Важная особенность: стандарт разработан закрыто. Конкурса, подобного конкурсу NIST на AES, не было; критерии проектирования и обоснование выбора констант не опубликованы. Для AES rationale опубликован авторами отдельной книгой ³, для «Кузнечика» — нет. Это не делает шифр нестойким, но переносит часть риска с математики на доверие к разработчику, и ниже видно, почему этот вопрос возник не на пустом месте.

«Магма»: ГОСТ 28147-89 в новой редакции

«Магма» — сеть Фейстеля с блоком 64 бита, ключом 256 бит и 32 раундами ¹⁴. Раундовая функция g берёт 32-битное слово, складывает с раундовым ключом по модулю 2^32, пропускает через восемь 4-битных S-боксов (преобразование t) и циклически сдвигает результат на 11 бит влево. Раунд сети: G[k](a1, a0) = (a0, g[k](a0) ⊕ a1); последний раунд выполняется без перестановки половин, поэтому шифрование заканчивается функцией G*.

Расписание ключей простое до предела: 256-битный ключ читается как восемь 32-битных слов K1…K8, они повторяются трижды (K9…K24), а последние восемь идут в обратном порядке (K25…K32). Расшифрование — тот же алгоритм с обратным порядком подключей.

От ГОСТ 28147-89 «Магму» отличают ровно три вещи ¹⁴. Первая — S-боксы зафиксированы набором id-tc26-gost-28147-param-Z (приложение C RFC 7836); таблица стала частью стандарта, а не секретным параметром поставщика. Вторая — ключ читается как одно большое целое в прямом порядке байтов, а не в обратном. Третья — так же читаются и данные. Из-за смены порядка байтов те же 32 байта дают другие раундовые ключи, поэтому реализация, написанная по стандарту 1989 года, и реализация по стандарту 2015 года несовместимы, хотя алгоритм один и тот же. Это классическая ловушка: тестовый вектор из RFC 8891 ловит её сразу.

Тестовый вектор: ключ ffeeddccbbaa99887766554433221100f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff, открытый текст fedcba9876543210, шифртекст 4ee901e5c2d8ca3d ¹⁴. Для этого ключа K1 = ffeeddcc, K25 = fcfdfeff, K32 = ffeeddcc.

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

«Кузнечик»: SP-сеть со 128-битным блоком

«Кузнечик» — SP-сеть: блок 128 бит, ключ 256 бит, десять раундовых ключей ¹³. Раунд состоит из трёх преобразований, сокращённо LSX: сложение с раундовым ключом X[k](a) = k ⊕ a, побайтовая замена S по таблице π и линейное преобразование L. Шифрование — девять раундов LSX и завершающее сложение с ключом K10:

E(a) = X[K10] ∘ LSX[K9] ∘ … ∘ LSX[K2] ∘ LSX[K1](a)

Замена S — та же таблица π из 256 байт, что и в хеш-функции «Стрибог» (тема 8); это не совпадение, а сознательное решение разработчиков, и оно же стало предметом анализа ниже.

Линейное преобразование устроено как умножение на матрицу 16×16 над полем GF(2^8) с многочленом p(x) = x^8 + x^7 + x^6 + x + 1 (в шестнадцатеричной записи 0x1C3) ¹³. Формально L = R^16, где R(a15, …, a0) = l(a15, …, a0) || a15 || … || a1, а l — линейная форма с коэффициентами

l(a15,…,a0) = 148·a15 ⊕ 32·a14 ⊕ 133·a13 ⊕ 16·a12 ⊕ 194·a11 ⊕ 192·a10
            ⊕ 1·a9 ⊕ 251·a8 ⊕ 1·a7 ⊕ 192·a6 ⊕ 194·a5 ⊕ 16·a4
            ⊕ 133·a3 ⊕ 32·a2 ⊕ 148·a1 ⊕ 1·a0

Матрица обладает свойством MDS: любая ненулевая разность активирует не менее 17 байт в сумме на входе и выходе L. Отсюда ключевое отличие от сети Фейстеля: один раунд LSX перемешивает весь блок. Измерение, выполненное для этого курса, показывает, что уже после первого раунда инверсия одного бита меняет в среднем около 64 из 128 бит — диффузия полная, тогда как «Магме» для этого нужно восемь раундов.

Расписание ключей использует итерационные константы C_i = L(Vec128(i)), где i = 1…32 записывается в младшие биты 128-битного слова. Преобразование F[k](a1, a0) = (LSX[k](a1) ⊕ a0, a1) за восемь шагов превращает пару ключей в следующую пару; четыре цикла по восемь шагов дают ключи K3…K10. Первые два раундовых ключа — это буквально половины мастер-ключа: K1 — старшие 128 бит, K2 — младшие. Схема показана на рисунке.

Тестовый вектор из RFC 7801: ключ 8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef, открытый текст 1122334455667700ffeeddccbbaa9988, шифртекст 7f679d90bebc24305a468d42b9d4edcd. Первая константа C1 = 6ea276726c487ab85d27bd10dd849401, десятый раундовый ключ K10 = 72e9dd7416bcf45b755dbaa88e4a4043.

В записи линейного преобразования в RFC 7801 есть опечатка: второй член указан как 32·δ(a15) вместо 32·δ(a14). Ориентироваться нужно на текст стандарта и на тестовый вектор; реализация, собранная по RFC буквально, не совпадёт с вектором ни на одном блоке.

Откуда взялся S-бокс «Кузнечика»

Таблица π выглядит случайной, но ею не является. В 2016 году Бирюков, Перрен и Удовенко методами обратного проектирования восстановили её скрытую структуру ¹⁵. Оказалось, что π — это двухраундовая конструкция типа сети Фейстеля, в которой сложение по модулю два заменено умножением в поле GF(2^4), а вся конструкция закрыта двумя линейными слоями. Для вычисления таблицы достаточно пяти 4-битных S-боксов, мультиплексора, двух 8-битных линейных перестановок и двух умножений в GF(2^4). Разложение даёт выигрыш в аппаратной реализации — площадь меньше в 2,5 раза, задержка в 8 раз, — но сами 4-битные компоненты криптографически слабые: у одного из них дифференциальная вероятность равна 1. Структура была скрыта намеренно: разложение восстанавливается, а объяснения в стандарте нет.

Перрен и Удовенко показали, что π связан с S-боксом белорусского шифра BelT через класс «экспоненциальных» S-боксов ¹⁷. В 2019 году Перрен нашёл третье разложение: π оказался экземпляром небольшого семейства перестановок TKlog, тесно связанных с дискретным логарифмом в конечном поле. Такая перестановка отображает мультипликативные смежные классы подполя GF(2^4)* в аддитивные смежные классы, причём функция связи между классами всегда одна и та же ¹⁶. Автор работы делает вывод, что именно эта структура и была использована разработчиками сознательно.

Что это значит практически. Атаки, построенной на этом разложении, до сих пор не найдено; ни один из результатов не снижает стойкость «Кузнечика» ниже заявленной. Но принцип «nothing up my sleeve» — отсутствие козыря в рукаве — нарушен: для AES таблица выводится из обращения в поле и аффинного преобразования, и это можно проверить ³; для π происхождение скрыто, а восстановленная структура показывает, что разработчики строили её из слабых компонентов и маскировали линейными слоями. Пользователь стандарта не может отличить проектное решение от закладки — и это само по себе аргумент в пользу открытой стандартизации, независимо от того, есть ли закладка на самом деле.

Насколько они стойки: что известно к 2026 году

Для «Кузнечика» опубликованы атаки только на сокращённое число раундов. Раунды в литературе считают по числу применений LSX, поэтому полный шифр — это девять раундов, а завершающее сложение с K10 в счёт не идёт. Атака «встреча посередине» на пять раундов из девяти восстанавливает 256-битный ключ за 2^140,3 операций, 2^153,3 памяти и 2^113 выбранных шифртекстов ¹⁸. Связанные ключи дают практическую атаку на пять раундов: 2^32 операций, 2^30 памяти и 2^16 связанных ключей, но расписание ключей в ней сокращено до двух раундов из восьми ¹⁹. Полный шифр не вскрыт: лучшие результаты — различающие, а не восстанавливающие ключ. Препринт Станики, Дутты и Мандала (2025, обновлён в 2026 году) идёт другим путём: он изучает c-дифференциалы, в которых разность входов задаётся умножением на константу, и для двух раундов даёт точное восстановление 256-битного мастер-ключа с вероятностью отказа не выше 0,01 — ценой 226 512 выбранных пар и не более 240 669 запросов шифрования ²³. Выигрыш над классическими семействами на двух, трёх и четырёх раундах авторы измеряют в битах (5,2; 4,6 и около 1,6), а результаты для девяти раундов без предварительного отбеливания сами называют предварительными. Это работа о сокращённых раундах и о структуре S-бокса, а не вскрытие полного шифра.

Для «Магмы» картина иная: полный шифр вскрыт теоретически, хотя и с неосуществимыми ресурсами. Первая атака на полный ГОСТ 28147-89 с одним ключом — метод Исобэ: 2^224 операций, 2^32 данных и 2^64 памяти ²². Динур, Дункельман и Шамир улучшили её до 2^192 операций при 2^64 данных и 2^36 памяти, используя свойства отражения и неподвижных точек ²¹. Ашур, Бар-Он и Дункельман показали, что новая редакция унаследовала слабости расписания: атака неподвижной точки на полный шифр требует 2^237 операций, а отражение даёт 2^192 для класса слабых ключей размера 2^224 ²⁰. Именно эти свойства и были причиной отказа ISO в 2010 году.

Числа удобно свести в таблицу.

Как это читать. 2^192 операций — на 64 бита меньше перебора, и это настоящий теоретический выигрыш, а не ошибка оценки. Но атака требует 2^64 блоков данных под одним ключом, то есть 2^67 байт, или 128 ЭиБ, — объём, недостижимый не только сегодня, но и при любом мыслимом развитии техники. Практическая стойкость «Магмы» остаётся на уровне перебора 256-битного ключа; ограничение приходит не от криптоанализа, а от 64-битного блока, то есть от 2^32 блоков (32 ГиБ) под одним ключом.

Для «Кузнечика» теоретический запас выглядит прочнее: атаки останавливаются на пяти раундах из девяти, а для полного шифра нет ни восстановления ключа, ни общепризнанного различения. Но запас стойкости — не то же самое, что доверие: у AES за двадцать пять лет публичного анализа было на несколько порядков больше исследователей и атак, и именно объём анализа, а не только отсутствие результатов, является аргументом. «Кузнечик» и «Магма» такого объёма не имеют.

Криптоанализ и границы применимости

Дифференциальный и линейный криптоанализ

Два метода определили развитие блочных шифров в 1990-х. Дифференциальный криптоанализ, опубликованный Бихэмом и Шамиром в 1990 году, смотрит на пары открытых текстов с фиксированной разностью и ищет разности на выходе, которые встречаются чаще случайного ⁴. Если такая «дифференциальная характеристика» проходит через много раундов с заметной вероятностью, по ней восстанавливается последний раундовый ключ. Против DES полная атака требует 2^47 выбранных открытых текстов — то есть практически неосуществима, но это в 1990 году; против упрощённых версий и против шифров без специально подобранных S-боксов она работает.

Линейный криптоанализ Мацуи (1993) использует линейные приближения: ищется линейная комбинация бит открытого текста, шифртекста и ключа, которая выполняется с вероятностью, заметно отличающейся от 1/2 ⁵. Против DES полная атака требует около 2^43 известных открытых текстов — тоже много, но в 1994 году Мацуи реализовал её экспериментально на 12 компьютерах за 50 дней. Это был первый случай, когда DES был вскрыт аналитически, а не перебором.

Оба метода объясняют, почему S-боксы проектируются по специальным критериям: они должны иметь малые дифференциальные вероятности и малые линейные смещения. Открытие этих критериев в 1990-х показало, что S-боксы DES были спроектированы с их учётом, — и это единственная причина, по которой DES продержался двадцать лет.

Связанные ключи и другие направления

Атаки со связанными ключами (англ. related-key attacks) предполагают, что противник может шифровать одним ключом, а получать результат для другого ключа, отличающегося известным образом. В реальных протоколах такого оракула обычно нет, но в схемах с производными ключами (например, при неудачном расписании ключей) он появляется. На AES-256 известны атаки со связанными ключами сложности около 2^99, что не имеет практического значения, но показывает: запас раундов у AES-256 взят не зря.

Отдельное направление — алгебраические атаки, которые описывают шифр системой уравнений над полем и пытаются её решить. Для AES такие системы оказываются огромными и плотными, и лучшие результаты далеки от практических.

Атаки по сторонним каналам и AES-NI

Криптоанализ не обязан атаковать математику. Атака по времени (тема 4) и атака по кэшу используют то, что время выполнения и обращения к памяти зависят от данных. Классический пример — табличные реализации AES: SubBytes и MixColumns реализуются через таблицы в памяти, и обращение к T[state[i] ^ key[i]] даёт противнику возможность определить, в какую кэш-линию попал доступ, а значит, получить сведения о state[i] ^ key[i] ⁹.

Защита бывает двух видов. Программная — таблицы с «размазанными» индексами, доступ к полной таблице на каждый байт (bitslicing), константное время. Аппаратная — инструкции AES-NI, появившиеся в процессорах Intel в 2010 году ¹⁰. Они выполняют раунд целиком в кремнии, без таблиц в памяти, и работают за фиксированное число тактов: утечки по кэшу исчезают, а скорость вырастает на порядок.

Именно поэтому AES остаётся практичным выбором: не только стойкий математически, но и реализуемый так, что сторонние каналы закрываются. Для сравнения, «Кузнечик» аппаратных инструкций в распространённых процессорах не имеет, и корректная константная реализация на software требует аккуратности.

Размер блока и Sweet32

Последняя граница применимости — объём данных под одним ключом. У блочного шифра с блоком n бит после 2^(n/2) блоков с высокой вероятностью возникнет коллизия: два одинаковых шифртекста для разных открытых текстов. Для 64-битного блока это 2^32 блоков, то есть 32 ГиБ. Порог не теоретический: в режиме CBC коллизия даёт информацию о совпадении открытых текстов, а в режиме с явным счётчиком — позволяет восстановить часть данных.

Атака Sweet32 (2016) показала это на практике: длинные HTTPS-сессии с 64-битными шифрами (3DES, Blowfish) позволяли восстановить cookie аутентификации, потому что объём данных в одной сессии превышал 2^32 блоков ⁸. Вывод прост: 64-битный блок не годится для потоковых протоколов, где объём данных не ограничен, — и это одна из причин, по которой 3DES ушёл, а AES с его 128-битным блоком остаётся.

Правило, которое стоит запомнить: для блочного шифра с блоком n бит объём данных под одним ключом не должен превышать 2^(n/2) блоков, а с учётом запаса — 2^(n/2 − 1). Для AES-128 это 2^63 блоков, что недостижимо; для 3DES — 2^31, что вполне достижимо на практике.

Инженерные подводные камни ГОСТ-шифров

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

Размер блока и режимы

Главное ограничение «Магмы» — 64-битный блок. После 2^32 блоков под одним ключом вероятность коллизии шифртекстов становится заметной, поэтому безопасный объём данных на ключ — порядка 2^31 блоков, то есть 16 ГиБ, а не 32 ГиБ. Для дискового шифрования и долгоживущих VPN-туннелей это означает обязательную смену ключа задолго до исчерпания объёма; для TLS-сессий — ограничение на объём передачи в одном соединении. У «Кузнечика» блок 128 бит, и соответствующий предел — 2^63 блоков, что практически недостижимо.

Второе — режим. ГОСТ Р 34.13-2015 определяет для обоих шифров ECB, CBC, CFB, OFB, CTR и выработку имитовставки, но детали отличаются от международных: у CTR своя раскладка счётчика, имитовставка имеет настраиваемую длину и вырабатывается отдельным режимом, а не как надстройка над шифром. Это значит, что нельзя подставлять ГОСТ-шифр в код, написанный под AES-GCM: семантика nonce, счётчика и тега другая, и режимы подробно разбираются в теме 7, а аутентифицированное шифрование — в теме 9. Режим ECB не годится ни для чего, кроме шифрования ключей и проверки тестовых векторов: одинаковые блоки дают одинаковые шифртексты, и структура данных видна сразу.

Реализации, скорость и сторонние каналы

Ни у «Кузнечика», ни у «Магмы» нет аппаратных инструкций, аналогичных AES-NI ¹⁰. На практике это означает три следствия. Первое — скорость: программная реализация на порядки уступает AES с аппаратным ускорением, и на высокоскоростных каналах разница ощутима. Второе — сторонние каналы: быстрая реализация обычно строится на таблицах (для «Кузнечика» — несколько десятков килобайт T-таблиц), а обращение к таблице по индексу, зависящему от секретных данных, утекает через кэш ⁹. Третье — постоянное время: корректная реализация без таблиц возможна — бит-слайсинг, векторные перестановки pshufb, — но она сложнее и медленнее табличной.

Для «Магмы» ситуация немного легче: 4-битные S-боксы удобно реализовывать бит-слайсингом, а раунд состоит из сложения, подстановок и сдвига — операций, которые легко сделать независимыми от данных. Для «Кузнечика» сложнее и π, и линейное преобразование: умножение на матрицу над GF(2^8) в наивной реализации требует 16 умножений на байт. Именно поэтому в защищённых системах ГОСТ-шифры чаще реализуют аппаратно, а в программных — тщательно, с фиксированным доступом к памяти.

Ключи, байты и экосистема

Расписание ключей у «Кузнечика» обратимо: зная любую пару соседних раундовых ключей, можно восстановить мастер-ключ — K1 и K2 вообще являются половинами ключа. У «Магмы» раундовые ключи — это слова мастер-ключа, поэтому утечка любых восьми подряд идущих подключей раскрывает ключ целиком. Отсюда практическое правило: утечка раундовых ключей через сторонний канал равносильна утечке мастер-ключа, и защита реализации не может ограничиваться одним S-боксом. Вдобавок симметричное расписание «Магмы» делает схему уязвимой к атакам со связанными ключами, поэтому производные ключи нельзя получать простым XOR с константой — только через полноценную функцию выработки ключей (тема 10).

Следующая ловушка — порядок байтов. ГОСТ 28147-89 читает ключ и данные как числа в обратном порядке, «Магма» — в прямом. Один и тот же массив байтов даёт разные раундовые ключи, и реализация, перенесённая со старого кода, будет выдавать «правильные» на вид, но несовместимые шифртексты. Лекарство одно: тестовый вектор из RFC 8891 в систему проверки.

Ещё одна — экосистема. OpenSSL не содержит ГОСТ-шифров в базовой поставке: нужен отдельный провайдер gost-engine ²⁵. Без него команда openssl enc -kuznyechik-ecb … завершается ошибкой «Unknown option or cipher» — это проверено на OpenSSL 3.6. В Python ГОСТ-шифры есть в библиотеке pygost, а в cryptography их нет. На уровне протоколов ГОСТ-шифры закреплены в RFC 9189 — профиле TLS 1.2: наборы TLS_GOSTR341112_256_WITH_KUZNYECHIK_CTR_OMAC и TLS_GOSTR341112_256_WITH_MAGMA_CTR_OMAC используют «Кузнечик» и «Магму» в режиме CTR с имитовставкой OMAC, причём для «Магмы» тег короче — 8 байт против 16 ²⁴. Профиль TLS 1.3 вынесен в отдельный документ, который на момент публикации RFC оставался черновиком. Наконец, для сведений, составляющих государственную тайну, допускаются только сертифицированные СКЗИ; собственная реализация, даже совпадающая с векторами, годится для изучения и проверки, но не для защиты таких сведений.

Ловушки удобно свести в таблицу.

Эталонная реализация и проверка

Обе реализации ниже компактны, не используют внешних библиотек и совпадают с тестовыми векторами RFC 7801 и RFC 8891. Они учебные: табличные обращения к π и S-боксам не защищены от атак по кэшу, а скорость на Python не имеет отношения к реальной.

PI = (
    252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77,
    233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241, 187, 20, 205, 95, 193,
    249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79,
    5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31,
    235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204,
    181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135,
    21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177,
    50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87,
    223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3,
    224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74,
    167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65,
    173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59,
    7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137,
    225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97,
    32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82,
    89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182,
)

COEF = (148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148, 1)


def gf_mul(a, b):
    r = 0
    for _ in range(8):
        if b & 1:
            r ^= a
        hi = a & 0x80
        a = (a << 1) & 0xFF
        if hi:
            a ^= 0xC3
        b >>= 1
    return r


def l(block):
    r = 0
    for c, x in zip(COEF, block):
        r ^= gf_mul(c, x)
    return r


def R(block):
    return bytes([l(block)]) + block[:15]


def L(block):
    for _ in range(16):
        block = R(block)
    return block


def S(block):
    return bytes(PI[x] for x in block)


def X(k, a):
    return bytes(x ^ y for x, y in zip(k, a))


def kuznyechik_keys(key):
    keys = [key[:16], key[16:]]
    for i in range(4):
        a, b = keys[-2], keys[-1]
        for j in range(8):
            c = L(bytes(15) + bytes([8 * i + j + 1]))
            a, b = X(L(S(X(c, a))), b), a
        keys += [a, b]
    return keys[:10]


def kuznyechik_encrypt(key, block):
    keys = kuznyechik_keys(key)
    for k in keys[:9]:
        block = L(S(X(k, block)))
    return X(keys[9], block)


MAGMA_SBOX = (
    (12, 4, 6, 2, 10, 5, 11, 9, 14, 8, 13, 7, 0, 3, 15, 1),
    (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7, 11, 13, 0, 15),
    (11, 3, 5, 8, 2, 15, 10, 13, 14, 1, 7, 4, 12, 9, 6, 0),
    (12, 8, 2, 1, 13, 4, 15, 6, 7, 0, 10, 5, 3, 14, 9, 11),
    (7, 15, 5, 10, 8, 1, 6, 13, 0, 9, 3, 14, 11, 4, 2, 12),
    (5, 13, 15, 6, 9, 2, 12, 10, 11, 7, 8, 1, 4, 3, 14, 0),
    (8, 14, 2, 5, 6, 9, 1, 12, 15, 4, 11, 0, 13, 10, 3, 7),
    (1, 7, 14, 13, 0, 5, 8, 3, 4, 15, 10, 6, 9, 12, 11, 2),
)


def t(x):
    r = 0
    for i in range(8):
        r |= MAGMA_SBOX[i][(x >> (4 * i)) & 0xF] << (4 * i)
    return r


def g(k, a):
    x = t((a + k) & 0xFFFFFFFF)
    return ((x << 11) | (x >> 21)) & 0xFFFFFFFF


def magma_encrypt(key, block):
    k = [int.from_bytes(key[4 * i:4 * i + 4], "big") for i in range(8)]
    round_keys = k * 3 + k[::-1]
    a = int.from_bytes(block[:4], "big")
    b = int.from_bytes(block[4:], "big")
    for i in range(32):
        a, b = b, a ^ g(round_keys[i], b)
    return b.to_bytes(4, "big") + a.to_bytes(4, "big")

Проверка на векторах:

kuz_key = bytes.fromhex("8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef")
kuz_pt = bytes.fromhex("1122334455667700ffeeddccbbaa9988")
print(kuznyechik_encrypt(kuz_key, kuz_pt).hex())

mag_key = bytes.fromhex("ffeeddccbbaa99887766554433221100f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff")
mag_pt = bytes.fromhex("fedcba9876543210")
print(magma_encrypt(mag_key, mag_pt).hex())

7f679d90bebc24305a468d42b9d4edcd
4ee901e5c2d8ca3d

Первая строка совпадает с RFC 7801, вторая — с RFC 8891. Если «Кузнечик» не сходится, почти всегда виновата либо опечатка в коэффициентах l, либо порядок X и L в расписании ключей: F применяет LSX к первому элементу пары и только потом складывает со вторым.

Лавинный эффект у обоих шифров на полном числе раундов близок к идеалу. Измерение на 1000 случайных блоков даёт для «Кузнечика» среднее 64,0 изменённых бита из 128 (в разных выборках минимум 44, максимум 83), для «Магмы» — 31,9 из 64 (минимум 18, максимум 46). Разброс объясняется тем же, чем и для AES: конечной выборкой и тем, что шифр — не идеальная случайная перестановка. А вот зависимость от числа раундов устроена по-разному: у «Кузнечика» она выходит на плато уже после первого раунда, у «Магмы» — только после восьмого, и это прямое следствие SP-сети против сети Фейстеля.

Итоги темы

Блочный шифр — семейство перестановок на множестве блоков фиксированной длины, и его стойкость формулируется как неотличимость от случайной перестановки. Принципы Шеннона — рассеивание и перемешивание — реализуются чередованием нелинейных замен и линейных перестановок, а лавинный эффект служит количественной мерой рассеивания: для AES среднее число изменённых бит при инверсии одного входного бита равно 64 из 128, что подтверждается измерением на тысяче испытаний.

DES показал и силу, и предел сети Фейстеля: обратимость при любой раундовой функции делает конструкцию простой, но всего 56 бит ключа и 64 бита блока обрекли алгоритм, когда вычислительные мощности выросли. Двойное шифрование не спасает — атака «встреча посередине» сводит 2^112 к 2^56, потому что число применений удваивает работу, а не возводит её в квадрат. 3DES продлил жизнь DES, но унаследовал малый блок.

AES соединил SP-сеть с тщательно спроектированными преобразованиями: SubBytes даёт нелинейность через обращение в GF(2^8), ShiftRows и MixColumns — рассеивание, AddRoundKey — зависимость от ключа. Десять, двенадцать или четырнадцать раундов дают запас, который за двадцать лет публичного анализа не был исчерпан. ГОСТ Р 34.12-2015 предлагает два подхода: «Кузнечик» как SP-сеть с 128-битным блоком и «Магма» как сеть Фейстеля с 64-битным.

Отечественные стандарты стоит запомнить не как «два алгоритма из списка», а как пару с разной судьбой. «Магма» — это ГОСТ 28147-89, доведённый до современной записи: фиксированный S-бокс снял проблему совместимости, но 64-битный блок и симметричное расписание ключей остались, и именно они дают опубликованные атаки со сложностью 2^192–2^237, пусть и с недостижимыми объёмами данных. Практическое ограничение здесь — не криптоанализ, а 2^32 блоков под одним ключом. «Кузнечик» устроен современнее: 128-битный блок, MDS-матрица с ветвлением 17, полная диффузия за один раунд, отсутствие атак на полный шифр. Но его S-бокс не случаен, его структура была скрыта и восстановлена методами обратного проектирования, а происхождение таблицы не объяснено до сих пор. Это не взлом — это дефицит доверия, и он тем важнее, чем меньше у шифра публичного анализа.

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

Отсюда два практических вывода. Первый: выбирая шифр, сравнивают не только стойкость, но и объём независимого анализа, наличие аппаратной поддержки и стоимость защищённой реализации; по этим трём параметрам AES остаётся лучшим выбором там, где ГОСТ не обязателен по требованиям сертификации. Второй: у ГОСТ-шифров основная опасность — инженерная. Порядок байтов, отсутствие аппаратных инструкций, табличные реализации, обратимое расписание ключей и режимы с собственной семантикой ломают системы чаще, чем криптоанализ. Проверка тестовым вектором и измерение лавинного эффекта — минимальная гигиена, с которой начинается любая реализация. Следующая тема разбирает именно эту область — режимы работы блочных шифров, где одна и та же стойкая перестановка превращается то в надёжную схему, то в оракул расшифрования.

Литература

1. NIST. Advanced Encryption Standard (AES). — FIPS 197 (updated 2023), 2001. https://doi.org/10.6028/NIST.FIPS.197-upd1
2. NIST. Data Encryption Standard (DES). — FIPS 46-3, 1999 (withdrawn 2005). https://csrc.nist.gov/publications/detail/fips/46-3/final
3. Daemen J., Rijmen V. The Design of Rijndael: AES — The Advanced Encryption Standard. — Springer, 2002. DOI: 10.1007/978-3-662-04722-4
4. Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems. — Journal of Cryptology, 1991, Т. 4, № 1, С. 3–72. DOI: 10.1007/BF00630563
5. Matsui M. Linear Cryptanalysis Method for DES Cipher. — Advances in Cryptology — EUROCRYPT '93, Springer, 1994, С. 386–397. DOI: 10.1007/3-540-48285-7_33
6. ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры. — Стандартинформ, 2015.
7. Electronic Frontier Foundation. Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design. — O'Reilly & Associates, 1998.
8. Bhargavan K., Leurent G. On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN. — Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), 2016, С. 456–467. DOI: 10.1145/2976749.2978423
9. Bernstein D. J. Cache-Timing Attacks on AES. — 2005. https://cr.yp.to/antiforgery/cachetiming-20050414.pdf
10. Gueron S. Intel Advanced Encryption Standard (AES) New Instructions Set. — Intel Corporation, White Paper, 2010.
11. Diffie W., Hellman M. E. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. — Computer, 1977, Т. 10, № 6, С. 74–84. DOI: 10.1109/C-M.1977.217750
12. Katz J., Lindell Y. Introduction to Modern Cryptography. 3rd ed. — CRC Press, 2020.
13. Dolmatov V. (ed.). GOST R 34.12-2015: Block Cipher "Kuznyechik". — RFC 7801, IETF, 2016. https://www.rfc-editor.org/rfc/rfc7801
14. Dolmatov V., Baryshkov D. GOST R 34.12-2015: Block Cipher "Magma". — RFC 8891, IETF, 2020. https://www.rfc-editor.org/rfc/rfc8891
15. Biryukov A., Perrin L., Udovenko A. Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1. — EUROCRYPT 2016. https://eprint.iacr.org/2016/071
16. Perrin L. Partitions in the S-Box of Streebog and Kuznyechik. — IACR Transactions on Symmetric Cryptology, 2019, Т. 2019, № 1, С. 302–329. DOI: 10.13154/tosc.v2019.i1.302-329
17. Perrin L., Udovenko A. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog. — IACR Transactions on Symmetric Cryptology, 2016, Т. 2016, № 2, С. 99–124. DOI: 10.46586/tosc.v2016.i2.99-124
18. AlTawy R., Youssef A. M. A Meet in the Middle Attack on Reduced Round Kuznyechik. — IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2015, Т. E98-A, № 10. https://eprint.iacr.org/2015/096
19. Kiryukhin V. Related-key Attack on 5-Round Kuznyechik. — CTCrypt 2019. https://eprint.iacr.org/2019/1249
20. Ashur T., Bar-On A., Dunkelman O. Cryptanalysis of GOST2. — FSE 2017. https://eprint.iacr.org/2016/532
21. Dinur I., Dunkelman O., Shamir A. Improved Attacks on Full GOST. — FSE 2012. https://eprint.iacr.org/2011/558
22. Isobe T. A Single-Key Attack on the Full GOST Block Cipher. — Journal of Cryptology, 2013. DOI: 10.1007/s00145-012-9118-5
23. Stănică P., Dutta R., Mandal B. Extended Differential Cryptanalysis of Kuznyechik. — arXiv:2507.02181, 2025 (v4, 2026; препринт). https://arxiv.org/abs/2507.02181
24. Smyshlyaev S., Belyavskiy D., Alekseev E. GOST Cipher Suites for Transport Layer Security (TLS) Protocol Version 1.2. — RFC 9189, IETF, 2022. https://www.rfc-editor.org/rfc/rfc9189
25. gost-engine: Reference implementation of GOST cryptographic algorithms for OpenSSL. — GitHub. https://github.com/gost-engine/engine

Дополнительные материалы

Вопросы для самопроверки

1. Что такое псевдослучайная перестановка и чем её модель отличается от неразличимости шифрования?
2. Почему блочный шифр детерминирован и какие последствия это имеет для режима ECB?
3. Как формулируются принципы рассеивания и перемешивания и какими операциями они реализуются?
4. Почему замена должна быть нелинейной, а перестановка — линейной, и что будет, если поменять их местами?
5. Чему равно идеальное среднее число изменённых бит при инверсии одного входного бита для блока 64 и 128 бит?
6. Почему сеть Фейстеля требует больше раундов, чем SP-сеть, при той же длине блока?
7. Какие параметры DES и какая часть ключа фактически является секретной?
8. Почему S-боксы DES оказались устойчивы к дифференциальному криптоанализу и что это говорит о процессе стандартизации?
9. Почему двойное шифрование DES не даёт 112 бит стойкости?
10. Сколько раундов у AES-128, AES-192 и AES-256 и чем объясняется рост?
11. Почему SubBytes строится из обращения в поле, а не из произвольной таблицы?
12. Что произойдёт, если в реализации AES перепутать направление ShiftRows?
13. Чем «Кузнечик» отличается от AES по структуре и чем «Магма» отличается от «Кузнечика»?
14. Что такое атака по кэшу на AES и как от неё защищает AES-NI?
15. Почему 64-битный блок ограничивает объём данных под одним ключом и как это выражается числом?
16. Зачем понадобился ГОСТ Р 34.12-2015 и какие три ограничения ГОСТ 28147-89 он устранял?
17. Чем отличаются ГОСТ 28147-89 и «Магма» при одном и том же ключе и почему они несовместимы?
18. Что означает свойство MDS и почему «Кузнечику» достаточно одного раунда для полной диффузии?
19. Что было восстановлено в S-боксе «Кузнечика» и почему это не считается атакой?
20. Какие атаки на полный ГОСТ 28147-89 известны и почему они неприменимы на практике?
21. Почему утечка двух соседних раундовых ключей равносильна утечке мастер-ключа?

Глоссарий темы

Шпаргалка по инструментам

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

# AES-128 в ECB — только для проверки тестовых векторов, не для данных
key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
pt = bytes.fromhex("00112233445566778899aabbccddeeff")
enc = Cipher(algorithms.AES(key), modes.ECB()).encryptor()
print(enc.update(pt).hex())        # 69c4e0d86a7b0430d8cdb78070b4c55a

# проверка вектора FIPS 197 через OpenSSL
openssl enc -aes-128-ecb -K 000102030405060708090a0b0c0d0e0f -nopad \
  -in pt.bin | xxd -p

# скорость с аппаратными инструкциями и без них
openssl speed -seconds 2 -evp aes-128-gcm
OPENSSL_ia32cap="~0x200000200000000" openssl speed -seconds 2 -evp aes-128-gcm

# список поддерживаемых алгоритмов и реализаций
openssl list -cipher-algorithms

xtime(a)        сдвиг влево, при переполнении XOR с 0x1B
gmul(a, b)      умножение в GF(2^8) по модулю 0x11B
SBOX[0x00]      0x63
SBOX[0x53]      0xed
раундовые ключи 4·(Nr + 1) слов, g-функция на каждом четвёртом

ГОСТ-шифры в OpenSSL и Python:

# базовый OpenSSL не содержит ГОСТ: нужен провайдер gost-engine
openssl list -providers
openssl enc -kuznyechik-ecb -K 8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef \
  -nopad -in pt.bin | xxd -p

# без провайдера команда завершится ошибкой «Unknown option or cipher»

# вектор «Кузнечика»: 7f679d90bebc24305a468d42b9d4edcd
# вектор «Магмы»:     4ee901e5c2d8ca3d
# эталонные реализации — в разделе «Инженерные подводные камни ГОСТ-шифров»

MAGMA: K1..K8 = ключ, K9..K24 = повтор, K25..K32 = K8..K1
KUZ:   K1 = старшие 128 бит ключа, K2 = младшие
KUZ:   C_i = L(Vec128(i)), i = 1..32; L = R^16
KUZ:   F[k](a1, a0) = (LSX[k](a1) ⊕ a0, a1)

Типичные ошибки реализации:

Что почитать и посмотреть

• FIPS 197 (updated 2023). Сам стандарт: полное описание преобразований, расписание ключей, тестовые векторы в приложениях B и C. Читается за вечер, и это единственный источник, которому нужно верить при проверке реализации. https://doi.org/10.6028/NIST.FIPS.197-upd1
• Daemen J., Rijmen V. The Design of Rijndael (2002). Авторы о том, почему выбраны именно такие преобразования: критерии выбора MixColumns, аффинного преобразования и числа раундов. Лучший источник для ответа на вопрос «почему так, а не иначе».
• Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems (1991). Первоисточник дифференциального криптоанализа. Показывает, как из вероятностных характеристик получается ключ, и объясняет, зачем нужны специальные S-боксы.
• Matsui M. Linear Cryptanalysis Method for DES Cipher (1994). Симметричный по идее метод и, что важнее, полная реализация атаки на DES — редкий пример, когда криптоанализ доведён до эксперимента.
• Electronic Frontier Foundation. Cracking DES (1998). История постройки DES Cracker: инженерные детали, политический контекст и урок о том, что «дорого сейчас» не значит «дорого через двадцать лет».
• ГОСТ Р 34.12-2015. Текст стандарта с описанием «Кузнечика» и «Магмы». Полезно сравнить структуру с AES по первоисточнику, а не по пересказам.
• RFC 7801 (Kuznyechik) и RFC 8891 (Magma). Английские тексты стандарта с полными тестовыми векторами и пошаговыми примерами. Самый быстрый способ проверить реализацию: векторы короткие, а промежуточные значения приведены по шагам. https://www.rfc-editor.org/rfc/rfc7801 https://www.rfc-editor.org/rfc/rfc8891
• Biryukov A., Perrin L., Udovenko A. Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (2016). Как из таблицы 256 байт восстановили скрытую конструкцию и что это говорит о прозрачности стандарта. https://eprint.iacr.org/2016/071
• Perrin L. Partitions in the S-Box of Streebog and Kuznyechik (2019). Третье разложение S-бокса, семейство TKlog и вывод о сознательно скрытой структуре. Читается как детектив, но с линейной алгеброй. DOI: 10.13154/tosc.v2019.i1.302-329
• Ashur T., Bar-On A., Dunkelman O. Cryptanalysis of GOST2 (2017). Почему новая редакция ГОСТ унаследовала слабости расписания и что это значило для ISO. https://eprint.iacr.org/2016/532
• AlTawy R., Youssef A. M. A Meet in the Middle Attack on Reduced Round Kuznyechik (2015). Пример атаки на пять раундов: как оптимальная диффузия мешает криптоанализу и как её обходят. https://eprint.iacr.org/2015/096
• Bernstein D. J. Cache-Timing Attacks on AES (2005). Небольшая работа о том, как табличная реализация утекает через кэш и как это использовать. https://cr.yp.to/antiforgery/cachetiming-20050414.pdf
• Bhargavan K., Leurent G. Sweet32 (2016). Практическая атака на 64-битные блоки в TLS и OpenVPN: объём данных важнее алгоритма. Хорошее напоминание, что длина блока — параметр стойкости.
• Cryptopals, Set 1 (задачи 1–8). Разминка на XOR и ECB: обнаружение повторяющихся блоков, определение режима. Прямое продолжение части 1–2.

Углубление (по желанию)

Почему S-боксы DES были загадкой двадцать лет. Когда DES опубликовали в 1977 году, S-боксы выглядели подозрительно: они не были ни случайными, ни очевидно структурированными. Ходили версии о закладке. Разгадка пришла в 1990 году, когда Бихэм и Шамир построили дифференциальный криптоанализ и обнаружили, что S-боксы DES оптимизированы именно против него — то есть АНБ знало метод за десять лет до публикации и спроектировало алгоритм с запасом. Это редкий случай, когда засекреченные критерии проектирования работали в пользу стойкости, а не против неё; но проверить это сообщество смогло только задним числом, что само по себе аргумент в пользу открытой стандартизации.

Скрытая структура S-бокса «Кузнечика». История с π — зеркальное отражение истории DES, но с другим исходом. Здесь таблица тоже оказалась не случайной, и это удалось доказать: Бирюков, Перрен и Удовенко восстановили разложение через умножение в GF(2^4) и линейные слои (2016), а затем Перрен показал, что π — экземпляр семейства TKlog, связанного с дискретным логарифмом (2019). Разница в том, что для DES засекреченные критерии в итоге оказались защитой от известной спецслужбе атаки, а для π объяснения не опубликованы до сих пор. Восстановленная структура использует 4-битный S-бокс с дифференциальной вероятностью 1 — то есть компонент, который сам по себе криптографически бесполезен и держится только на маскирующих линейных слоях. Это не атака и не доказательство закладки; это доказательство того, что проектирование было намеренно непрозрачным. Для стандарта, который должен жить десятилетиями, непрозрачность — самостоятельный риск: она не даёт сообществу возможности отличить удачное решение от неудачного, пока не станет слишком поздно.

Rijndael и SP-сеть как общая идея. Структура Rijndael — не единственная возможная. Serpent использовал 32 раунда с битовыми перестановками, Twofish — сеть Фейстеля с зависимыми от ключа S-боксами, MARS — смесь ARX и SP-сети. Победил Rijndael во многом потому, что его диффузия достигается за два раунда, а не за три-четыре, и потому, что он хорошо ложится на любой размер регистра: на 8-битном контроллере, на 32-битном процессоре и на векторном блоке. Идея «чем меньше раундов для полной диффузии, тем проще анализ» оказалась важнее, чем кажется: простой алгоритм легче проверить, и это часть стойкости.

Что AES не защищает. AES — перестановка, а не схема шифрования. Он не даёт аутентификации, не защищает от подмены, не скрывает длину сообщения, не защищает от повтора сообщения целиком и не работает при повторе ключа счётчика в режиме CTR. Все реальные провалы AES-систем — это провалы режимов, протоколов и реализаций: padding oracle (тема 7), повтор nonce в GCM, атаки по сторонним каналам на таблицы. Когда говорят «AES взломан», почти всегда речь идёт о чём-то, что AES окружает, — и следующая тема разбирает именно это окружение.

Лабораторная работа 6. AES изнутри

• Раздел курса: тема 6 «Блочные шифры: DES, AES и принципы построения»

Введение

Тема 6 разобрала AES до уровня отдельного байта: подстановка через обращение в GF(2^8), сдвиг строк, умножение столбцов, расписание ключей. Лабораторная работа доводит этот разбор до работающего кода и проверяет каждое утверждение тестовым вектором стандарта. Пока реализация не совпала с FIPS 197 побайтово, разговор о стойкости преждевременен: ошибка в ShiftRows или потерянный MixColumns в последнем раунде дают алгоритм, который «работает», но шифрует не то.

Работа состоит из базовой части (части 1–3) и продвинутой (части 4–6). Базовая часть — реализация AES-128, пошаговый вывод состояния первого раунда и измерение лавинного эффекта. Продвинутая — учебная сеть Фейстеля, атака «встреча посередине» на двойное шифрование и измерение вклада аппаратных инструкций AES-NI в скорость. Атака на игрушечный шифр с 24-битным ключом не имеет отношения к реальной стойкости; она показывает сам принцип, из-за которого двойное шифрование бесполезно, — и этот принцип не зависит от размера ключа.

Учебная реализация AES в этой работе непригодна для реального применения: она не защищена от атак по времени и по кэшу. Для настоящих задач используется cryptography и OpenSSL; собственная реализация нужна, чтобы понимать, что происходит внутри, и уметь проверить чужой код.

Цель работы

Реализовать AES-128 на Python, сверить её с тестовыми векторами FIPS 197, измерить лавинный эффект и провести учебные атаки, показывающие, почему двойное шифрование не удваивает стойкость.

После выполнения работы можно будет:

• реализовать все четыре преобразования раунда AES и расписание ключей, сверив результат с FIPS 197;
• вывести состояние после каждого шага первого раунда и объяснить роль каждого преобразования;
• измерить лавинный эффект при инверсии бита открытого текста и ключа и сравнить с идеальным значением n/2;
• реализовать сеть Фейстеля и показать, что она обратима при необратимой раундовой функции;
• провести атаку «встреча посередине» на двойное шифрование игрушечным шифром;
• измерить разницу скорости AES с аппаратными инструкциями и без них и объяснить, откуда она берётся.

Уровни работы

• Минимум (обязательно): части 1–5. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: 6.
• Углубление (по желанию): векторы ГОСТ из дополнительного задания.

Теоретический минимум

Нужны разделы «Блочный шифр как семейство перестановок», «Сеть Фейстеля и DES», «AES», «Отечественные стандарты ГОСТ Р 34.12-2015» и «Инженерные подводные камни ГОСТ-шифров». Ниже — справка по параметрам и API.

SubBytes      S[b] — обращение в GF(2^8) и аффинное преобразование
ShiftRows     сдвиги строк влево на 0, 1, 2, 3 байта
MixColumns    умножение столбцов на матрицу [2 3 1 1; 1 2 3 1; 1 1 2 3; 3 1 1 2]
AddRoundKey   XOR состояния с раундовым ключом
xtime(a)      a·2 в GF(2^8): сдвиг влево, при переполнении XOR с 0x1B

Тестовые векторы, которые понадобятся:

FIPS 197, приложение B
ключ        2b7e151628aed2a6abf7158809cf4f3c
открытый    3243f6a8885a308d313198a2e0370734
шифртекст   3925841d02dc09fbdc118597196a0b32
ключ раунда 10  d014f9a8c9ee2589e13f0cc8b6630ca6

FIPS 197, приложение C.1
ключ        000102030405060708090a0b0c0d0e0f
открытый    00112233445566778899aabbccddeeff
шифртекст   69c4e0d86a7b0430d8cdb78070b4c55a

Перечень оснащения

• Ubuntu 24.04 (или WSL2), Python 3.10+, cryptography 3.4 или новее, OpenSSL 3.0 или новее. Права root не нужны.
• Архив окружения: lr-env.zip.

Ограничения ресурсов

1000 испытаний лавинного эффекта — 1000 блоков; скорость измеряется командой openssl speed, а не собственным кодом; память — единицы мегабайт. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-06; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

Порядок выполнения работы

mkdir -p ~/lab06 && cd ~/lab06
unzip /path/to/lr-env.zip
python3 check_aes.py -v

Проверки идут в том же порядке, что части работы. Пока не заполнены базовые преобразования, падают все — это нормально: начинать нужно с части 1 и не переходить дальше, пока вектор FIPS 197 не совпадёт.

Часть 1. Преобразования раунда и расписание ключей

Задание

1. Заполните sub_bytes, shift_rows, mix_columns, add_round_key. Таблица SBOX и RCON уже даны — их не нужно генерировать, но нужно понять, откуда они берутся.
2. Заполните key_expansion: 44 слова для AES-128, g-функция на каждом четвёртом слове.
3. Заполните encrypt_block: начальный AddRoundKey, девять полных раундов, десятый без MixColumns.
4. Проверьте расписание ключей на векторе приложения B: раунд 1 должен дать a0fafe1788542cb123a339392a6c7605, раунд 2 — f2c295f27a96b9435935807a7359f67f, раунд 10 — d014f9a8c9ee2589e13f0cc8b6630ca6.
5. Запустите check_aes.py и добейтесь совпадения с обоими векторами FIPS 197.

Что должно получиться

Реализация, совпадающая с приложением B (3925841d…) и с приложением C.1 (69c4e0d8…), и правильное расписание ключей. Если совпадает только один вектор, ошибка почти наверняка в MixColumns: приложение B и C.1 отличаются ключом, и ошибка в xtime проявляется по-разному.

Часть 2. Пошаговый вывод первого раунда

Задание

1. Дополните encrypt_block режимом трассировки: список состояний после каждого преобразования каждого раунда.
2. Выведите трассировку первого раунда для вектора приложения C.1 — она наиболее читаема, потому что все байты различны.
3. Для каждого шага объясните в журнале, что произошло: какие байты куда переехали, какие значения умножились на 2 и на 3.
4. Проверьте на трассировке два свойства: после ShiftRows байты одного столбца оказываются в разных столбцах; после MixColumns каждый выходной байт столбца зависит от всех четырёх входных.
5. Убедитесь, что в десятом раунде MixColumns отсутствует, и объясните, почему стандарт так поступает.

Что должно получиться

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

Часть 3. Лавинный эффект

Задание

1. Заполните функцию измерения: для 1000 случайных открытых текстов инвертируйте один случайный бит и посчитайте число различающихся бит шифртекстов.
2. Повторите опыт для инверсии одного бита ключа.
3. Постройте гистограмму распределения и запишите среднее, минимум и максимум.
4. Сравните с идеальными значениями: среднее 64 для блока 128 бит, стандартное отклонение √128 / 2 ≈ 5,66.
5. Повторите опыт для укороченной версии — с 1, 2, 3 и 4 раундами — и постройте зависимость среднего числа изменённых бит от числа раундов.

Что должно получиться

Две гистограммы и таблица «число раундов — среднее число изменённых бит». Ориентир для полного AES на 1000 испытаниях: при инверсии бита открытого текста среднее около 64,00 (минимум 46, максимум 86), при инверсии бита ключа — около 63,77 (минимум 41, максимум 84). Расхождение с идеалом объясняется конечным объёмом выборки и тем, что AES — не идеальная случайная перестановка.

Часть 4. Сеть Фейстеля и её обратимость

Задание

1. Заполните feistel_encrypt и feistel_decrypt из заготовки: половины блока, раундовая функция f, раундовые ключи.
2. Проверьте обратимость на заведомо необратимой функции — например, f(x, k) = (x & 0x0F) | (k & 0xF0), которая теряет половину бит входа.
3. Убедитесь, что для 8-раундовой сети расшифрование возвращает исходный блок при любом числе раундов.
4. Сделайте f константой и покажите, что шифр вырождается: два разных открытых текста с разными половинами дают предсказуемую связь шифртекстов.
5. Объясните в журнале, почему обратимость раундовой функции не требуется и что именно даёт стойкость в такой конструкции.

Что должно получиться

Работающие feistel_encrypt и feistel_decrypt, подтверждённая обратимость при необратимой f и разбор вырожденного случая. Вывод: обратимость конструкции и стойкость — разные свойства, и второе обеспечивается необратимостью раундовой функции по отношению к ключу.

Часть 5. Встреча посередине на двойном шифровании

Задание

1. Возьмите игрушечный шифр с 24-битным ключом: например, три раунда сети Фейстеля с 12-битными раундовыми ключами или XOR с потоком от LFSR длины 24.
2. Зашифруйте блок дважды с разными ключами: C = E(K₂, E(K₁, P)).
3. Реализуйте атаку «встреча посередине»: таблица промежуточных значений по всем K₁, затем поиск по всем K₂.
4. Измерьте число операций и объём таблицы. Сравните с полным перебором 2^24.
5. Повторите опыт для тройного шифрования и объясните, почему 3DES потребовал трёх ключей и почему атака на него имеет сложность порядка 2^112, а не 2^56.

Что должно получиться

Восстановленная пара ключей и таблица «способ — число операций — память». Ожидание перед опытом: два перебора по 2^12 и таблица на 2^12 элементов дают ключ за 2^13 операций вместо 2^24 — выигрыш в тысячу раз, и именно поэтому двойное шифрование не эквивалентно удвоению длины ключа.

Часть 6. Скорость и аппаратные инструкции

Задание

1. Измерьте скорость AES-128-GCM с аппаратными инструкциями:

openssl speed -seconds 2 -evp aes-128-gcm

2. Измерьте то же без них, отключив расширение через переменную окружения:

OPENSSL_ia32cap="~0x200000200000000" openssl speed -seconds 2 -evp aes-128-gcm

3. Сравните скорость на блоке 16 КБ. На машине автора разница составила около 22 раз: порядка 7,6 ГБ/с с инструкциями и 0,34 ГБ/с без них. На другой машине абсолютные числа будут другими, отношение — того же порядка.
4. Объясните разницу: инструкции выполняют раунд в кремнии, без таблиц в памяти и без ветвлений, зависящих от данных.
5. Сформулируйте, какую атаку закрывает аппаратная реализация и почему табличная уязвима.

Что должно получиться

Таблица «режим — скорость» и объяснение связи между скоростью, отсутствием таблиц и стойкостью к атакам по кэшу. Дополнительно полезно измерить скорость собственной реализации на Python и убедиться, что она медленнее в тысячи раз: это нормально и объясняет, почему криптография всегда реализуется на низком уровне.

Дополнительное задание. Векторы ГОСТ

Задание не входит в автоматические проверки check_aes.py и выполняется по желанию; код пишется с нуля по листингам темы.

1. Реализуйте «Кузнечик»: таблицу π, умножение в GF(2^8) с многочленом 0x1C3, преобразование L = R^16, расписание ключей с константами C_i = L(Vec128(i)) и шифрование. Сверьтесь с вектором RFC 7801: ключ 8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef, открытый текст 1122334455667700ffeeddccbbaa9988, шифртекст 7f679d90bebc24305a468d42b9d4edcd.
2. Реализуйте «Магму»: восемь S-боксов param-Z, сложение по модулю 2^32, сдвиг на 11 бит и расписание K1…K8, повторённое трижды, затем обратное. Сверьтесь с вектором RFC 8891: ключ ffeeddccbbaa99887766554433221100f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff, открытый текст fedcba9876543210, шифртекст 4ee901e5c2d8ca3d.
3. Измерьте лавинный эффект обоих шифров на 1000 испытаниях и сравните с 32 и 64 изменёнными битами. Ориентир: «Кузнечик» — около 64,0 (44–83), «Магма» — около 31,9 (18–46).
4. Постройте зависимость среднего числа изменённых бит от числа раундов для обоих шифров. Объясните, почему у «Кузнечика» плато наступает после первого раунда, а у «Магмы» — после восьмого.
5. Объясните в журнале, почему утечка двух соседних раундовых ключей равносильна утечке мастер-ключа и как это связано с тем, что первые два ключа «Кузнечика» — половины ключа.

Журнал работы

По каждой части: предсказание, команда, результат, объяснение. Для части 3 предсказание формулируется числом («среднее будет около 64, разброс 5–6 бит»), для части 5 — числом операций, для части 6 — отношением скоростей. Полезно сохранять трассировку раунда в файл: она пригодится в лабораторной работе 7, когда понадобится объяснять, что происходит с блоком в режиме CBC. В конце свести все измерения в одну таблицу и проверить, что ни одно число не взято из текста без проверки.

Критерии проверки

Работа считается выполненной, если:

• проверки check_aes.py завершаются без ошибок;
• раундовые ключи и шифртекст совпали с FIPS 197, инвертируемость сети Фейстеля показана, встреча посередине нашла ключ;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

Контрольные вопросы

1. Почему блочный шифр нельзя использовать как схему шифрования без режима, и что именно выдаёт режим ECB?
2. Что означает неотличимость блочного шифра от случайной перестановки и почему этой модели недостаточно для схемы шифрования?
3. Почему сеть Фейстеля обратима при необратимой раундовой функции?
4. Почему двойное шифрование с двумя независимыми ключами не даёт 112 бит стойкости?
5. Чему равно идеальное среднее число изменённых бит для блока 128 бит и почему реальное распределение имеет разброс?
6. Как обращение в GF(2^8) обеспечивает нелинейность SubBytes, и зачем добавлено аффинное преобразование?
7. Что даёт комбинация ShiftRows и MixColumns и почему без одной из них диффузия становится неполной?
8. Почему в последнем раунде AES отсутствует MixColumns?
9. Как длина ключа влияет на число раундов и почему запас растёт с длиной ключа?
10. Почему табличная реализация AES уязвима к атакам по кэшу, а реализация на AES-NI — нет?
11. Сколько блоков можно зашифровать одним ключом при 64-битном блоке и что происходит после этого порога?
12. Почему 3DES запрещён для новых применений, хотя его стойкость к перебору формально достаточна?
13. Чем «Магма» отличается от ГОСТ 28147-89 и почему две реализации одного алгоритма могут быть несовместимы?
14. Почему у «Кузнечика» полная диффузия достигается за один раунд, а у «Магмы» — за восемь?
15. Что означает свойство MDS и как оно связано с оценкой числа активных S-боксов?
16. Почему скрытая структура S-бокса «Кузнечика» считается проблемой доверия, а не взломом?