Поточные шифры: LFSR, RC4 и ChaCha20

Блочный шифр обрабатывает данные порциями фиксированной длины, а поточный шифр (англ. stream cipher) вырабатывает последовательность бит — ключевой поток (англ. keystream) — и складывает её с сообщением побитово. Такая схема не требует дополнения, работает с данными произвольной длины и не задерживает выдачу: байт шифртекста появляется сразу, как только пришёл байт открытого текста. Именно поэтому поточные шифры применяются там, где важна задержка и объём: в мобильной связи, в спутниковых каналах, в TLS для больших потоков, в протоколах защищённой передачи медиа.

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

Тема устроена как разбор трёх поколений: сначала — общая схема и её требования, затем — LFSR с алгоритмом Берлекэмпа — Мэсси и взломом регистра по известному началу сообщения, далее — RC4 и его смещения, наконец — ChaCha20 по RFC 8439 с разбором тестового вектора. Завершает тему то, ради чего она, собственно, нужна: почему поточный шифр без аутентификации опасен (ковкость XOR) и почему повтор пары «ключ, nonce» уничтожает защиту полностью. Обе ошибки — не теоретические: на них построены атаки на WEP, на WPA2 и на несколько поколений TLS.

Паспорт темы. Нужно знать: темы 0, 2. Освоите: описывать LFSR и восстанавливать его по выходу; объяснять смещения RC4; реализовывать ChaCha20 по RFC 8439; формулировать требование уникальности пары «ключ, nonce»; показывать ковкость поточного шифрования. Проверяет: ЛР 5. Минимум: разделы 1–4. Углубление: раздел 5.

Идея поточного шифра

Ключевой поток и операция XOR

Пусть в распоряжении есть секретный ключ k и открытое значение nonce. Генератор потока (англ. keystream generator) вырабатывает последовательность s₁, s₂, s₃, …, и шифрование сводится к трём формулам: cᵢ = mᵢ ⊕ sᵢ, mᵢ = cᵢ ⊕ sᵢ и s = PRF(k, nonce).

Расшифрование совпадает с шифрованием, потому что XOR обратим сам по себе: mᵢ ⊕ sᵢ ⊕ sᵢ = mᵢ. Это достоинство и одновременно источник главной уязвимости: у операции нет никакой памяти и никакой нелинейности, поэтому всё, что нужно знать противнику, — ключевой поток. Схема ниже показывает поток в целом и подчёркивает, что секрет находится целиком в генераторе: как только поток известен, сообщение восстановлено независимо от длины ключа.

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

От блочного шифра поточный отличается и по модели применения. Блочный шифр в режиме CTR тоже превращается в поточный: он шифрует счётчик и получает блоки потока. Разница в том, что поточный шифр спроектирован для этого изначально — у него нет «режима», нет зависимости от длины блока и нет дополнения. В теме 7 будет показано, что CTR из блочного шифра требует тех же предосторожностей с nonce, что и ChaCha20, и ломается ровно так же.

Синхронные и самосинхронизирующиеся шифры

Синхронный поточный шифр (англ. synchronous stream cipher) вырабатывает поток независимо от сообщения: генератор видит только ключ и nonce, а открытый текст на него не влияет. ChaCha20, RC4 и все LFSR-конструкции из этой темы — синхронные. Их достоинство — отсутствие размножения ошибок: искажение одного бита шифртекста портит ровно один бит открытого текста, что важно для каналов с помехами. Недостаток — потеря синхронизации: если приёмник отстал на байт, весь дальнейший текст расшифровывается в мусор, пока синхронизация не восстановлена, и приходится передавать nonce или метку позиции заново.

Самосинхронизирующийся шифр (англ. self-synchronizing или asynchronous stream cipher) строит поток из предыдущих байт шифртекста. Здесь открытый текст входит в обратную связь, и приёмник «догоняет» передатчик автоматически: после потери n байт достаточно n байт, чтобы состояние восстановилось. Плата — размножение ошибок: один испорченный байт шифртекста портит несколько байт открытого текста. Исторически так работал режим CFB блочного шифра; в современной практике самосинхронизирующиеся схемы почти вытеснены AEAD-режимами, которые решают задачу иначе — обнаружением искажения вместо его прощения.

Практический вывод для выбора: если канал надёжен и потеря байт маловероятна (TLS поверх TCP), синхронная схема проще и быстрее; если канал теряет данные (спутник, радио), нужна либо самосинхронизация, либо кадрирование с явной нумерацией.

Требования к паре «ключ, nonce»

Главное требование ко всей конструкции формулируется одной строкой: пара (ключ, nonce) не должна повторяться ни при каких обстоятельствах. Не «желательно», а обязательно, потому что при повторе поток совпадает и схема теряет конфиденциальность мгновенно, без всякого криптоанализа.

Отсюда две практики. Первая — счётчик: если обе стороны знают номер сообщения, nonce выбирается как номер, и уникальность гарантирована структурой протокола. Вторая — случайный nonce достаточной длины: при 96-битном случайном nonce вероятность коллизии после 2^32 сообщений одного ключа составляет около 2^-33, что считается приемлемым, а после 2^48 — уже около 2^-1, то есть катастрофой. Именно поэтому в рекомендациях фигурируют пределы на число сообщений под одним ключом.

Важно различать роли ключа и nonce. Ключ — секрет, его знают только участники. Nonce — не секрет, он передаётся открыто, но должен быть уникален. Если nonce сделан секретным, это не добавляет стойкости, но создаёт иллюзию, что его можно переиспользовать незаметно. Если nonce уникален, но предсказуем, схема остаётся стойкой — предсказуемость опасна только в схемах, где nonce входит в ключ иначе (например, в GCM при неудачной реализации).

Регистры сдвига с линейной обратной связью

Устройство и период

Регистр сдвига с линейной обратной связью (англ. linear feedback shift register, LFSR) — это последовательность из L бит, которая на каждом такте сдвигается, а в освободившуюся позицию записывается XOR нескольких выбранных бит. Набор позиций, участвующих в обратной связи, называют отводами (англ. taps).

Формально последовательность удовлетворяет линейной рекуррентности порядка L:

s(n) = c₁·s(n−1) ⊕ c₂·s(n−2) ⊕ … ⊕ c_L·s(n−L)

Коэффициенты cᵢ задают многочлен связей C(x) = 1 + c₁x + … + c_L x^L. Если этот многочлен примитивен над GF(2), период последовательности максимален и равен 2^L − 1 — все ненулевые состояния регистра обходятся прежде, чем последовательность повторится. Именно поэтому LFSR так любят в железе: L триггеров и несколько XOR дают гигантский период при минимальной стоимости.

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

Реализация на Python проста, и её стоит написать, чтобы увидеть, насколько мало в ней «криптографии»:

def lfsr_sequence(taps, init, n):
    """taps — номера отводов (1 = предыдущий бит), init — начальное состояние."""
    s = list(init)
    while len(s) < n:
        b = 0
        for t in taps:
            b ^= s[len(s) - t]
        s.append(b)
    return s[:n]

Проверка периода — отдельная задача: последовательность нужно прогонять до повторения состояния, и для L = 20 это около миллиона шагов, а для L = 64 — уже недостижимо. Поэтому на практике максимальность периода не проверяют экспериментально, а обеспечивают выбором примитивного многочлена из таблицы.

Линейная сложность и алгоритм Берлекэмпа — Мэсси

Линейная сложность последовательности — длина самого короткого LFSR, который её порождает. Для случайной последовательности она примерно равна половине её длины, для LFSR-последовательности — равна L. Это и есть мера её предсказуемости.

Алгоритм Берлекэмпа — Мэсси находит минимальный многочлен связей по первым 2L битам последовательности за O(L²) операций ³. Идея: алгоритм последовательно наращивает предполагаемый регистр, и при первом расхождении предсказания с наблюдением корректирует многочлен так, чтобы исправить расхождение с минимальным увеличением длины. Классический результат Мэсси состоит в том, что такой жадный алгоритм оптимален: он всегда даёт регистр минимальной длины.

Практическое следствие для криптографии жёсткое: любой LFSR вскрывается по 2L битам выхода за квадратичное время. Для L = 64 это 128 бит ключевого потока и несколько тысяч операций — работа, которую машина выполняет незаметно. Схема «взять LFSR с большим периодом и считать его шифром» не даёт стойкости вообще: период 2^64 впечатляет, а стойкость измеряется не периодом, а линейной сложностью.

В лабораторной работе это демонстрируется на учебном письме: известен заголовок (От:, Кому:, Тема:), из него получается фрагмент ключевого потока длиной в сотни бит, алгоритм находит L = 53 и многочлен связей, после чего поток достраивается на всю длину письма и текст восстанавливается целиком. Никакого перебора ключей не происходит.

Почему LFSR непригоден и что строят вместо него

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

Обходной путь — нелинейная комбинация нескольких LFSR. Фильтрующая функция берёт биты с выходов нескольких регистров и пропускает их через нелинейную булеву функцию; комбинирующая функция смешивает выходы с разными периодами. Такие схемы (например, A5/1 в GSM с тремя регистрами длин 19, 22 и 23 бита) выглядят убедительно, но их стойкость не доказана, а практика оказалась суровой: A5/1 был вскрыт, и атаки требуют лишь нескольких секунд известного ключевого потока, полученного по открытому каналу.

Современное решение — вообще отказаться от линейной структуры и строить поток из арифметических операций, нелинейных относительно GF(2): сложения по модулю 2^32, циклических сдвигов и XOR. Так устроены Salsa20 и ChaCha20, и именно отсутствие линейности делает линейный криптоанализ к ним неприменимым. Альтернатива — LFSR с нелинейной фильтрацией, сертифицированная в конкретном стандарте (например, «Кузнечик» и «Магма» в ГОСТ используют другие конструкции), но для новой разработки выбирают ARX.

RC4 и его смещения

Алгоритм

RC4 (англ. Rivest Cipher 4, также ARC4) появился в 1987 году как торговый секрет и был опубликован в 1994-м. Он состоит из двух частей: планировщика ключа (англ. key scheduling algorithm, KSA), который перемешивает 256-байтовый массив S ключом, и генератора (англ. pseudo-random generation algorithm, PRGA), который на каждом шаге меняет местами два элемента и выдаёт один байт.

def rc4_ksa(key):
    S = list(range(256))
    j = 0
    for i in range(256):
        j = (j + S[i] + key[i % len(key)]) % 256
        S[i], S[j] = S[j], S[i]
    return S


def rc4_prga(S, n):
    out = bytearray()
    i = j = 0
    for _ in range(n):
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        out.append(S[(S[i] + S[j]) % 256])
    return bytes(out)

Алгоритм красив своей простотой: два счётчика, один массив, три сложения и обмен. Именно поэтому он был встроен во всё, что передавало данные: WEP, WPA-TKIP, SSL/TLS, Microsoft Office, PDF, Lotus Notes.

Смещения в ключевом потоке

Простота обернулась смещениями — отклонениями от равномерного распределения в первых байтах потока. Первый байт выдаёт себя сильнее всего: P(S[1] = 0) ≈ 2/256, то есть вдвое больше ожидаемого, и причина в том, что KSA не успевает перемешать массив — при i = 1 обмен затрагивает только что тронутые позиции. На этом смещении построена атака FMS против WEP ⁸⁹.

Второй байт ведёт себя так же: P(Z₂ = 0) ≈ 2/256 ⁵. Дальше распределение выравнивается, но не полностью: существуют долгоживущие смещения, которые накапливаются при большом объёме данных. Известные атаки перечислены в таблице.

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

Запрет в TLS и уроки

История RC4 в TLS показательна. В 2013 году атаки стали практическими, и RFC 7465 запретил наборы шифров с RC4 ⁶. Но запрет был выпущен в 2015 году, а исключены наборы из популярных браузеров только к 2016-му; ещё несколько лет RC4 оставался включённым как «совместимый вариант» и включался при сбое рукопожатия. Это типичная динамика: алгоритм живёт в коде дольше, чем в стандартах.

Урок первый: статистические дефекты не лечатся увеличением ключа. RC4 с 256-битным ключом так же уязвим, как с 40-битным, потому что атака использует структуру KSA и первые байты потока, а не длину ключа.

Урок второй: отбрасывание первых байт потока (распространённая «заплатка» — отбросить 256 или 768 байт) уменьшает смещения, но не устраняет их и не даёт гарантий. Это ровно тот случай, когда инженерная мера маскирует проблему, оставляя систему в неизвестном состоянии.

Урок третий: «прошло все статистические тесты» — не аргумент. RC4 проходил тесты NIST и умирал от атак, которые эти тесты не проверяют, потому что они смотрят на распределение одного потока, а не на корреляции между потоками с разными IV.

ChaCha20

Состояние и четверть-раунд

ChaCha20 предложен Дэниелом Бернстайном в 2008 году как развитие Salsa20 ²; семейство вошло в портфель eSTREAM и стало одним из двух рекомендованных поточных шифров ¹¹. Состояние — матрица 4×4 из 32-битных слов, всего 16 слов:

константы  c₀ c₁ c₂ c₃     "expand 32-byte k"
ключ       k₀ k₁ k₂ k₃
ключ       k₄ k₅ k₆ k₇
счётчик    b₀ | nonce n₀ n₁ n₂

Первые четыре слова — константы, следующие восемь — ключ, последние четыре — счётчик (одно слово) и nonce (три слова). Число 20 в названии — число раундов: десять двойных раундов, каждый из которых состоит из четырёх четверть-раундов над столбцами и четырёх над диагоналями.

Четверть-раунд (англ. quarter round) — сердце конструкции. Он берёт четыре слова, выполняет четыре сложения по модулю 2^32, четыре XOR и четыре циклических сдвига:

def rotl32(x, n):
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF


def quarter_round(a, b, c, d):
    a = (a + b) & 0xFFFFFFFF; d ^= a; d = rotl32(d, 16)
    c = (c + d) & 0xFFFFFFFF; b ^= c; b = rotl32(b, 12)
    a = (a + b) & 0xFFFFFFFF; d ^= a; d = rotl32(d, 8)
    c = (c + d) & 0xFFFFFFFF; b ^= c; b = rotl32(b, 7)
    return a, b, c, d

Такая схема называется ARX — от англ. add, rotate, xor. Схема ниже показывает четверть-раунд как цепочку из четырёх шагов.

Почему это работает лучше RC4 и LFSR. Сложение по модулю 2^32 нелинейно относительно GF(2): перенос из младшего разряда в старший зависит от данных, и именно переносы разрушают линейные соотношения между битами. Циклические сдвиги на разные величины обеспечивают диффузию: бит, попавший в результат одного шага, за четыре шага влияет уже на несколько слов. После двадцати раундов каждый выходной бит зависит от всех входных.

Счётчик, nonce и число сообщений

Одно слово состояния — счётчик блоков, три слова — nonce. Для 96-битного nonce и 32-битного счётчика предельный объём одного сообщения равен 2^32 блоков по 64 байта, то есть 256 ГиБ. Это ограничение существенно: при переполнении счётчика поток начинает повторяться, и схема ломается ровно так же, как при повторе nonce. Реализации обязаны либо ограничивать длину сообщения, либо использовать вариант с 64-битным счётчиком и 64-битным nonce.

После двадцати раундов состояние складывается с исходным (это называется «финальным сложением») и выдаётся как 64 байта потока. Финальное сложение не декоративно: без него раундовая функция была бы обратима, и по выходу можно было бы пройти раунды назад к ключу.

Разбор тестового вектора

RFC 8439 приводит полный тестовый вектор для одного блока ¹. Ключ — байты от 00 до 1f, nonce — 00 00 00 00 00 00 00 4a 00 00 00 00, счётчик равен 1. Открытый текст — строка из 114 байт, шифртекст по стандарту приведён рядом:

открытый текст
Ladies and Gentlemen of the class of '99: If I could offer you
only one tip for the future, sunscreen would be it.

шифртекст (RFC 8439, раздел 2.4.2)
6e2e359a2568f98041ba0728dd0d6981e97e7aec1d4360c20a27afccfd9fae0b
f91b65c5524733ab8f593dabcd62b3571639d624e65152ab8f530c359f0861d
807ca0dbf500d6a6156a38e088a22b65e52bc514d16ccf806818ce91ab77937
365af90bbf74a35be6b40b8eedf2785e42874d

Сверка с библиотекой cryptography подтверждает эти значения побайтово:

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

key = bytes(range(32))
nonce = (1).to_bytes(4, "little") + bytes.fromhex("000000000000004a00000000")
pt = b"Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it."

enc = Cipher(algorithms.ChaCha20(key, nonce), mode=None).encryptor()
print(enc.update(pt).hex())

Обратите внимание на несовпадение форматов: RFC 8439 передаёт счётчик отдельным параметром и 12-байтный nonce, а cryptography ожидает 16-байтное значение, в котором первые четыре байта — счётчик в little-endian. Такие расхождения в интерфейсах — обычная причина ошибок; правильный порядок действий — сверить с тестовым вектором, а не догадываться по названию параметра.

Ошибки применения

Ковкость и подмена битов

XOR линеен, и это делает поточный шифр ковким (англ. malleable): противник, не знающий ключа, может изменить открытый текст предсказуемым образом, изменив шифртекст в нужных позициях. Если он знает структуру сообщения, ему достаточно вычислить разность Δ = m ⊕ m' и применить c' = c ⊕ Δ.

Покажем на учебном «платёжном поручении». Пусть в сообщении есть поле сумма=1000.00, а противник хочет сумма=9000.00. Он не знает поток s, но знает, что c = m ⊕ s, а значит c' = m' ⊕ s = c ⊕ m ⊕ m'. Разность вычисляется по известному формату поля, и получатель увидит валидное по форме поручение с другой суммой. Схема ниже показывает это тождество.

Защита — аутентификация: к шифртексту добавляется код аутентификации сообщения (MAC) или используется аутентифицированное шифрование (AEAD), которое проверяет целостность до выдачи открытого текста. Важен порядок: сначала проверить тег, потом расшифровывать. Обратный порядок даёт оракул, на котором построены атаки на TLS и SSH (подробно — в теме 9).

Повтор nonce и его последствия

Повтор пары «ключ, nonce» — самая разрушительная ошибка в поточной криптографии. Если два сообщения зашифрованы одним потоком, то c₁ ⊕ c₂ = (m₁ ⊕ s) ⊕ (m₂ ⊕ s) = m₁ ⊕ m₂.

Поток сокращается, и противник получает XOR двух открытых текстов. Для текстов на естественном языке этого достаточно: в ASCII пробел равен 0x20 и «обнуляет» регистр буквы, поэтому XOR отчётливо показывает границы слов; для русского текста в UTF-8 структура другая, но избыточность всё равно позволяет восстановление.

Схема ниже показывает сокращение потока при повторе nonce.

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

В AEAD последствия тяжелее. В ChaCha20-Poly1305 ключ Poly1305 выводится из первого блока потока, поэтому повтор nonce означает повтор ключа аутентификации, и противник может подделать тег для любого сообщения с тем же nonce. В AES-GCM повтор nonce позволяет восстановить ключ аутентификации H и подделывать теги для всех сообщений. Именно это произошло в атаке KRACK на WPA2: принудительная реинициализация nonce превращала защищённый протокол в открытый ⁷.

Чем это лечится

Три меры, и все три обязательны в правильной реализации ¹². Первая — AEAD вместо «шифр плюс отдельный MAC, собранный вручную»: библиотека проверяет порядок операций и не даёт расшифровать данные с неверным тегом. Вторая — дисциплина nonce: счётчик с явной проверкой на переполнение либо случайный nonce с ограничением на число сообщений под ключом. Третья — ротация ключей: даже при идеальной дисциплине стоит менять ключ задолго до исчерпания счётчика, потому что любая ошибка в учёте сообщений накапливается.

Полезно помнить, что все три меры — про целостность и уникальность, а не про «силу алгоритма». Поточный шифр с 256-битным ключом и повторяющимся nonce слабее, чем 128-битный AEAD с аккуратным счётчиком. Именно этот сдвиг внимания — от примитива к протоколу — и составляет главный практический вывод темы.

Итоги темы

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

Первое поколение поточных шифров строилось на LFSR. Эти регистры дешевы, имеют огромный период и хорошо изучены — и именно поэтому непригодны: линейная структура позволяет восстановить регистр по 2L битам выхода алгоритмом Берлекэмпа — Мэсси за квадратичное время. Нелинейные комбинации нескольких LFSR не дают доказуемой стойкости, что подтвердила история A5/1.

RC4 прожил три десятилетия и был запрещён из-за статистических смещений в начале потока: атаки FMS, Tews–Weinmann–Pyshkin, AlFardan и другие показали, что «простой и быстрый» не означает «стойкий», а увеличение ключа не помогает, когда атака использует структуру алгоритма. Запрет в RFC 7465 закрыл тему, но код с RC4 встречался ещё годы.

ChaCha20 — современный стандарт: ARX-арифметика, нелинейная относительно GF(2), двадцать раундов, счётчик и nonce в состоянии, тестовый вектор RFC 8439 для побайтовой проверки. Его слабое место — не алгоритм, а дисциплина применения: переполнение счётчика и повтор nonce ломают и его.

Следующая тема переходит к блочным шифрам — DES и AES, — где данные обрабатываются порциями и где требование к nonce появляется снова, но уже в режимах: CBC, CTR, GCM. Ковкость XOR и повтор nonce там выглядят иначе, но приводят к тем же последствиям, а атака padding oracle в теме 7 покажет, как ошибка обработки превращает стойкий шифр в оракул расшифрования.

Литература

1. Nir Y., Langley A. ChaCha20 and Poly1305 for IETF Protocols. — RFC 8439, IETF, 2018. https://www.rfc-editor.org/rfc/rfc8439
2. Bernstein D. J. ChaCha, a Variant of Salsa20. — Workshop Record of SASC 2008: The State of the Art of Stream Ciphers, 2008. https://cr.yp.to/chacha/chacha-20080128.pdf
3. Massey J. L. Shift-Register Synthesis and BCH Decoding. — IEEE Transactions on Information Theory, 1969, Т. 15, № 1, С. 122–127. DOI: 10.1109/TIT.1969.1054260
4. Tews E., Weinmann R.-P., Pyshkin A. Breaking 104 Bit WEP in Less Than 60 Seconds. — Information Security Applications (WISA 2007), Springer, 2007, С. 188–202. DOI: 10.1007/978-3-540-77535-5_14
5. Fluhrer S., McGrew D. Statistical Analysis of the Alleged RC4 Keystream Generator. — Fast Software Encryption (FSE 2000), Springer, 2001, С. 19–30. DOI: 10.1007/3-540-44706-7_2
6. Popov A. Prohibiting RC4 Cipher Suites. — RFC 7465, IETF, 2015. https://www.rfc-editor.org/rfc/rfc7465
7. Vanhoef M., Piessens F. Key Reinstallation Attacks: Forcing Nonce Reuse in WPA2. — Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), 2017, С. 1313–1328. DOI: 10.1145/3133956.3134027
8. Fluhrer S., Mantin I., Shamir A. Weaknesses in the Key Scheduling Algorithm of RC4. — Selected Areas in Cryptography (SAC 2001), Springer, 2001, С. 1–24. DOI: 10.1007/3-540-45537-X_1
9. Borisov N., Goldberg I., Wagner D. Intercepting Mobile Communications: The Insecurity of 802.11. — Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom), 2001, С. 180–189. DOI: 10.1145/381677.381695
10. AlFardan N. J., Bernstein D. J., Paterson K. G., Poettering B., Schuldt J. C. N. On the Security of RC4 in TLS. — 22nd USENIX Security Symposium, 2013, С. 327–338. https://www.usenix.org/conference/usenixsecurity13/technical-sessions/paper/alfardan
11. Babbage S., et al. The eSTREAM Portfolio in 2012. — eSTREAM project report, 2012. https://www.ecrypt.eu.org/stream/
12. Aumasson J.-P. Serious Cryptography: A Practical Introduction to Modern Encryption. 2nd ed. — No Starch Press, 2024.

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

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

1. Почему поточный шифр не требует дополнения, а блочный в режиме ECB требует, и как это связано с моделью данных?
2. Какие три требования предъявляются к ключевому потоку и какое из них нарушается при повторе nonce?
3. Чем синхронный поточный шифр отличается от самосинхронизирующегося по размножению ошибок и по восстановлению после сбоя?
4. Почему потеря одного байта в синхронной схеме ломает весь дальнейший текст, а в самосинхронизирующейся — только несколько байт?
5. Что означает максимальный период LFSR и при каком условии на многочлен связей он достигается?
6. Почему линейная сложность, а не период, является мерой предсказуемости LFSR-последовательности?
7. Сколько бит выхода и какого времени требует восстановление LFSR алгоритмом Берлекэмпа — Мэсси?
8. Почему нелинейная комбинация нескольких LFSR не даёт доказуемой стойкости? Приведите пример взломанной конструкции.
9. В чём причина смещения первого и второго байтов RC4 и почему смещения сохраняются в потоке даже после прогрева?
10. Почему атаки на RC4 в TLS требовали множества сессий, а не одного длинного потока?
11. Что такое ARX и почему сложение по модулю 2^32 считается нелинейным относительно GF(2)?
12. Зачем в ChaCha20 финальное сложение состояния с исходным и что произойдёт, если его убрать?
13. Почему переполнение счётчика в ChaCha20 эквивалентно повтору nonce?
14. Почему XOR шифртекста с разностью открытых текстов даёт валидную подмену и какая мера это предотвращает?
15. Почему в AEAD повтор nonce ломает и целостность, а не только конфиденциальность?

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

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

# поток и XOR
ks = chacha20_encrypt(key, 1, nonce, bytes(len(msg)))   # поток той же длины
ct = bytes(a ^ b for a, b in zip(msg, ks))
assert bytes(a ^ b for a, b in zip(ct, ks)) == msg

# биты и байты (соглашение: старший бит первым)
bits = [(b >> i) & 1 for b in data for i in range(7, -1, -1)]

# XOR двух шифртекстов при повторе nonce
x = bytes(a ^ b for a, b in zip(ct1, ct2))
print(x[:80])            # = m1 ^ m2, поток сократился

# ChaCha20 через OpenSSL: ключ и iv задаются в hex
openssl enc -chacha20 -K 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f \
  -iv 01000000000000004a00000000000000 -in msg.bin -out ct.bin

# расшифрование — те же параметры
openssl enc -d -chacha20 -K ... -iv ... -in ct.bin -out msg.bin

# сверка ChaCha20 с библиотекой: 16-байтное значение = счётчик (4, little-endian) + nonce (12)
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms
nonce16 = counter.to_bytes(4, "little") + nonce12
enc = Cipher(algorithms.ChaCha20(key, nonce16), mode=None).encryptor()

Типичные ошибки:

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

• RFC 8439. ChaCha20 and Poly1305 for IETF Protocols. Первоисточник по ChaCha20: полное описание состояния, четверть-раунда, тестовые векторы для блока и для AEAD. Читать с карандашом, сверяя каждый шаг с собственной реализацией. https://www.rfc-editor.org/rfc/rfc8439
• Bernstein D. J. ChaCha, a variant of Salsa20 (2008). Короткая статья автора: чем ChaCha отличается от Salsa20 и почему изменение расположения слов улучшает диффузию. https://cr.yp.to/chacha/chacha-20080128.pdf
• Fluhrer S., McGrew D. Statistical Analysis of the Alleged RC4 Keystream Generator (FSE 2000). Аккуратный разбор смещений RC4: какие байты, насколько и на каком расстоянии. Лучший источник, чтобы понять, откуда берётся 2/256 для второго байта.
• AlFardan N. J. et al. On the Security of RC4 in TLS (USENIX Security 2013). Как статистическое смещение превращается в практическую атаку на протокол: восстановление cookie за 2^26 запросов. Полезно как пример разницы между «теоретической слабостью» и «работающим эксплойтом».
• Vanhoef M., Piessens F. Key Reinstallation Attacks (CCS 2017). История KRACK: как принудительная реинициализация nonce в WPA2 ломает и конфиденциальность, и целостность. Разбор протокольного уровня, а не алгоритма. https://www.krackattacks.com/
• Massey J. L. Shift-Register Synthesis and BCH Decoding (1969). Первоисточник алгоритма Берлекэмпа — Мэсси. Тяжелее учебника, но именно здесь доказывается оптимальность жадного подхода.
• eSTREAM Portfolio. Итоги европейского конкурса поточных шифров: какие конструкции выжили, какие были взломаны и почему. Хороший обзор современного состояния области. https://www.ecrypt.eu.org/stream/
• Aumasson J.-P. Serious Cryptography, главы о поточных шифрах и nonce. Инженерный взгляд: как выбирать nonce, как считать пределы на число сообщений, что происходит при ошибке.
• Cryptopals, Set 3 (задачи 19–24). Практика на повторе nonce и на XOR двух текстов: автоматическое восстановление текстов на английском языке. Хорошее продолжение части 6.

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

Как A5/1 продержался тридцать лет. Шифр GSM был спроектирован в конце 1980-х для аппаратной реализации: три LFSR длин 19, 22 и 23 бита, нерегулярное тактирование, 64-битный ключ. Он казался достаточно сложным для тогдашних вычислительных мощностей. Первые серьёзные результаты появились в конце 1990-х, а в 2009–2010 годах были опубликованы атаки, работающие за минуты на обычном компьютере при наличии небольшого известного фрагмента ключевого потока — а такой фрагмент легко получить, зная структуру кадров GSM. Урок не в том, что авторы ошиблись в деталях, а в том, что стойкость нелинейной комбинации регистров не поддаётся анализу, и «сложно выглядит» не заменяет доказательства. Именно этот аргумент привёл к отказу от LFSR-конструкций в новых стандартах.

Почему ARX захватил мир. Сложение по модулю 2^32 нелинейно над GF(2), но линейно над Z/2^32. Эта двойственность делает ARX-шифры неудобными для алгебраических атак: нужно одновременно работать с двумя структурами. При этом ARX идеально ложится на процессор — нет таблиц, нет обращений к памяти, значит, нет и кэш-атак вроде тех, что работают против AES с табличными реализациями. Отсюда три свойства, из-за которых ChaCha20 популярен: скорость в софте, отсутствие секретно-зависимых обращений к памяти и простота проверки. Poly1305 дополняет его по той же логике — арифметика по простому модулю 2^130 − 5 вместо таблиц.

Номер сообщения как часть протокола. Многие ошибки с nonce возникают не в шифре, а в протоколе: счётчик хранится в памяти, при перезапуске сбрасывается в нуль, и два сообщения получают один nonce. В TLS 1.3 эту проблему решают, выводя ключ каждого сообщения из последовательности ключей (key schedule), а не из счётчика: сброс состояния соединения приводит к новому секрету, а не к повтору потока. Это общая идея — если состояние можно потерять, безопаснее выводить ключи заново, чем надеяться на аккуратность счётчика. Тема 15 разберёт key schedule TLS 1.3 подробно, и там эта мысль прозвучит снова.

Лабораторная работа 5. От LFSR до ChaCha20

• Раздел курса: тема 5 «Поточные шифры: LFSR, RC4 и ChaCha20»

Введение

Тема 5 проследила, как поточная криптография прошла путь от регистров сдвига до ARX-конструкций. Лабораторная работа повторяет этот путь руками: сначала регистр сдвига и его период, затем вскрытие регистра по известному началу сообщения, затем RC4 с измерением смещения второго байта, затем ChaCha20 по тестовому вектору RFC 8439. Завершают работу две атаки на неправильное применение: подмена открытого текста через XOR и восстановление двух сообщений при повторе nonce. Обе атаки не касаются алгоритмов — они бьют по протоколу, и именно поэтому вынесены в отдельные части.

Работа опирается на тему 2 (одноразовый блокнот и требование уникальности ключа) и готовит тему 9: станет понятно, почему конфиденциальность без целостности недостаточна и откуда берётся требование проверять тег до расшифрования.

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

Цель работы

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

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

• реализовать LFSR по заданным отводам и проверить период для примитивного и непримитивного многочлена;
• восстановить структуру LFSR по фрагменту ключевого потока алгоритмом Берлекэмпа — Мэсси и расшифровать текст без перебора ключей;
• реализовать RC4 и измерить смещение второго байта, сравнив его с равномерным распределением;
• реализовать ChaCha20 по RFC 8439 и сверить результат с тестовым вектором и с библиотекой cryptography;
• провести подмену поля в шифртексте без знания ключа и объяснить, какая мера её предотвращает;
• восстановить два открытых текста при повторе пары «ключ, nonce» и объяснить, почему в AEAD последствия тяжелее.

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

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

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

Нужны разделы «Идея поточного шифра», «Регистры сдвига с линейной обратной связью», «RC4 и его смещения», «ChaCha20» и «Ошибки применения». Ниже — справка по данным и API.

Основные формулы и соглашения:

шифрование           cᵢ = mᵢ ⊕ sᵢ
повтор nonce         c₁ ⊕ c₂ = m₁ ⊕ m₂
период LFSR          не больше 2^L − 1, равен при примитивном многочлене
линейная сложность   L; для восстановления нужно 2L бит выхода
смещение RC4         P(Z₂ = 0) ≈ 2/256 вместо 1/256
ChaCha20             состояние 4×4 слов, 20 раундов, счётчик + 96-битный nonce

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

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

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

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

LFSR — до 2^16 состояний; RC4 — около 2·10^5 байт потока; ChaCha20 проверяется по вектору RFC 8439. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

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

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

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

mkdir -p ~/lab05 && cd ~/lab05
unzip /path/to/lr-env.zip
python3 check_lfsr.py -v
python3 check_rc4.py -v
python3 check_chacha20.py -v

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

python3 gen_data.py --seed 17

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

Часть 1. LFSR: последовательность, период, отводы

Задание

1. Заполните lfsr_sequence(taps, init, n): рекуррентное соотношение s[n] = XOR s[n − t] по всем t из taps.
2. Заполните lfsr_period(taps, init): прогон до повторения начального состояния. Для L = 20 это до миллиона шагов.
3. Запустите check_lfsr.py. Проверки сверяют последовательность с эталонной и период с теоретическим.
4. Прогоните три набора отводов: примитивный многочлен (период 2^L − 1), непримитивный (период меньше) и вырожденный (нулевое состояние). Запишите три периода.
5. Объясните в журнале, почему нулевое состояние — ловушка: из него регистр уже не выйдет.

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

Работающие функции, зелёные проверки и таблица из трёх строк «многочлен — L — период». Ожидание перед опытом: для примитивного многочлена степени L период равен 2^L − 1, то есть для L = 20 — 1 048 575 шагов.

Часть 2. Восстановление LFSR по известному началу

Задание

1. Скопируйте lfsr_break_template.py в lfsr_break.py и заполните три TODO.
2. Из data/lfsr_secret.json возьмите header и ciphertext_hex. Сложите первые байты шифртекста с заголовком — получится фрагмент ключевого потока.
3. Примените berlekamp_massey к битам фрагмента. Запишите найденные L и многочлен связей.
4. Достройте поток на всю длину шифртекста и расшифруйте письмо. Сверьте sha256 результата с полем plaintext_sha256 в файле — обратите внимание, что хеш считается от текста без завершающего перевода строки.
5. Найдите в конце письма контрольное слово вида СЛОВО-123 и запишите его.

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

Восстановленный текст письма и контрольное слово. Ожидание перед опытом: для заголовка длиной 67 байт доступно 536 бит потока, а для восстановления регистра нужно 2L; значит, рабочая длина регистра не должна превышать 268 бит, и результат заведомо помещается в известный фрагмент.

Часть 3. RC4 и смещение второго байта

Задание

1. Заполните rc4_ksa и rc4_prga. Проверьте на известном векторе: ключ Key, поток начинается с байтов eb 9f 77 81 b2 ....
2. Запустите check_rc4.py.
3. Постройте распределение второго байта потока: для 100 000 случайных ключей по 16 байт соберите значения Z₂ и посчитайте частоту каждого. Запишите долю нулевого значения.
4. Сравните с равномерным распределением: 1/256 ≈ 0.0039. Ожидание — примерно 2/256 ≈ 0.0078, то есть вдвое больше.
5. Постройте такую же таблицу для 256-го байта и убедитесь, что смещение там существенно меньше.

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

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

Часть 4. ChaCha20 по RFC 8439

Задание

1. Заполните rotl32, quarter_round, initial_state, chacha20_block, chacha20_encrypt.
2. Проверьте блок по тестовому вектору RFC 8439, раздел 2.3.2: при ключе 00..1f, счётчике 1 и nonce 000000090000004a00000000 блок начинается с 10f1e7e4d13b5915500fdd1fa32071c4. Обратите внимание, что в этом разделе nonce отличается от того, что используется в примере с открытым текстом (раздел 2.4.2) — это разные векторы, и путать их нельзя.
3. Проверьте полный вектор из раздела 2.4.2 на строке про sunscreen — шифртекст должен совпасть побайтово.
4. Сверьте с библиотекой cryptography. Не забывайте, что она ожидает 16-байтное значение, где первые четыре байта — счётчик в little-endian:

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

key = bytes(range(32))
nonce = (1).to_bytes(4, "little") + bytes.fromhex("000000000000004a00000000")
pt = b"Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it."
enc = Cipher(algorithms.ChaCha20(key, nonce), mode=None).encryptor()
print(enc.update(pt).hex()[:64])

5. Сверьте с OpenSSL, собрав те же параметры в командной строке, и объясните, почему -iv там 16 байт.

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

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

Часть 5. Подмена открытого текста без ключа

Задание

1. Возьмите учебное «платёжное поручение» из данных варианта: поле суммы, поле получателя, поле назначения.
2. Зашифруйте его ChaCha20 с произвольным ключом и nonce — так, как это сделал бы наивный разработчик, без MAC.
3. Не зная ключа, постройте Δ = m ⊕ m' для исходного и желаемого сообщений и примените c' = c ⊕ Δ.
4. Расшифруйте c' тем же ключом и покажите, что получилось валидное по форме поручение с другой суммой.
5. Повторите опыт, добавив Poly1305 или HMAC: убедитесь, что получатель отвергает подделку до расшифрования.

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

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

Часть 6. Повтор nonce

Задание

1. Из data/nonce_reuse.json возьмите ct1_hex, ct2_hex и pt1.
2. Вычислите ct1 ⊕ ct2 и убедитесь, что результат равен pt1 ⊕ pt2, то есть поток сократился.
3. Восстановите pt2, зная pt1. Сверьте с префиксом, хеш которого лежит в файле.
4. Для второго опыта возьмите два сообщения на русском языке, зашифрованных тем же способом, и восстановите оба, не зная ни одного: используйте то, что в UTF-8 кириллица занимает два байта и старший байт пары ограничен диапазоном.
5. Сформулируйте, что произойдёт в ChaCha20-Poly1305 при таком повторе: почему ломается не только конфиденциальность, но и целостность.

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

Восстановленный второй текст и объяснение последствий для AEAD. Вывод: повтор пары «ключ, nonce» — не ослабление, а полная потеря защиты, поэтому nonce в протоколе должен быть либо счётчиком с проверкой переполнения, либо случайным с ограничением на число сообщений.

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

По каждой части: предсказание числом («период 1 048 575», «L не больше 268», «доля нулей около 0.0078», «шифртекст совпадёт побайтово»), затем запуск, затем фактический результат, затем объяснение. Смена варианта данных (gen_data.py --seed N) — хороший способ проверить, что в решении нет подогнанных констант: после смены все части должны работать без правок. В конце полезно свести таблицу «поколение — алгоритм — что его ломает» и проверить, что каждая строка подтверждена собственным опытом, а не взята из текста.

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

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

• проверки check_lfsr.py, check_rc4.py и check_chacha20.py завершаются без ошибок;
• период LFSR измерен, LFSR восстановлен, смещение RC4 статистически значимо, поток ChaCha20 совпал с вектором;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

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

1. Почему расшифрование в поточном шифре совпадает с шифрованием и какие последствия это имеет для целостности?
2. Чем синхронный поточный шифр отличается от самосинхронизирующегося по реакции на потерю байт и на искажение?
3. Почему период LFSR 2^64 не означает стойкости 64 бита? Какая величина измеряет предсказуемость?
4. Сколько бит выхода LFSR нужно для восстановления регистра длины L и почему именно столько?
5. Почему нелинейная фильтрация выходов нескольких LFSR не даёт доказуемой стойкости?
6. В чём причина смещения второго байта RC4 и почему отбрасывание первых байт потока не решает проблему?
7. Почему увеличение ключа RC4 не повышает стойкость против атак FMS и AlFardan?
8. Что даёт финальное сложение в ChaCha20 и что произойдёт, если его убрать?
9. Почему в ChaCha20 нельзя продолжать поток после переполнения счётчика?
10. Как из двух шифртекстов, зашифрованных одним потоком, получить XOR открытых текстов и что с ним делать дальше?
11. Почему в ChaCha20-Poly1305 повтор nonce ломает и аутентификацию, а не только конфиденциальность?
12. Какие три меры делают применение поточного шифра корректным и почему ни одна из них не заменяет остальные?