Поточные шифры: bit-flipping и повтор ключа

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

Тема опирается на тему 5 основного курса (LFSR, RC4, ChaCha20) и готовит тему 6 (AEAD): именно здесь видно, почему конфиденциальность без целостности недостаточна. Атаки на TLS-режимы и WEP используются как исторические примеры.

Как устроен поточный шифр

Ключевой поток и XOR

Схема: c_i = m_i ⊕ s_i, где s_i — i-й байт ключевого потока, выработанного из ключа k и nonce n. Расшифрование — та же операция: m_i = c_i ⊕ s_i. Синхронный поточный шифр вырабатывает поток независимо от сообщения; самосинхронизирующийся использует предыдущие байты шифртекста и восстанавливается после потери синхронизации.

Требования к паре (k, n): она должна быть уникальной для каждого сообщения. Если nonce повторяется с тем же ключом, поток повторяется, и c1 ⊕ c2 = m1 ⊕ m2 — ключ исчезает из уравнения (рисунок 2).

Это не «ослабление», а полная потеря конфиденциальности для пары сообщений.

Линейность и её последствия

XOR линеен: изменение бита шифртекста на позиции i меняет ровно тот же бит открытого текста. Противнику не нужно знать ключ, чтобы превратить role=guest в role=admin, если он знает структуру сообщения. Достаточно вычислить Δ = m ⊕ m' и применить c' = c ⊕ Δ. Целостность при этом не нарушается с точки зрения расшифрования: получатель увидит валидный по форме, но подменённый текст. Защита — MAC или AEAD, которые проверяют целостность до использования открытого текста. Схема на рисунке 1 показывает, что ключ в подмене вообще не участвует.

LFSR и линейная сложность

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

LFSR из L бит хранит состояние и на каждом такте сдвигается, добавляя в старший бит XOR выбранных отводов. Выход — один бит за такт. Период максимален (2^L − 1), если многочлен обратной связи примитивен. LFSR быстры, но линейны: последовательность удовлетворяет линейной рекуррентности порядка L.

Алгоритм Берлекэмпа — Мэсси

По 2L битам выхода LFSR восстанавливается его структура: алгоритм находит минимальный многочлен, порождающий последовательность, за O(L^2) операций ². После этого предсказывается весь дальнейший поток. Именно поэтому чистый LFSR непригоден как шифр: сложность взлома растёт квадратично, а не экспоненциально.

Нелинейные комбинации нескольких LFSR (фильтрующая или комбинирующая функция) усложняют атаку, но не дают доказуемой стойкости; A5/1 в GSM — пример, который был взломан. Современный стандарт — ARX-шифры, построенные на сложении, вращении и XOR: чистой линейности над GF(2) у них нет, но это не означает, что линейный и дифференциальный криптоанализ к ним неприменим. Для ARX разработаны специализированные варианты — анализ по модулю сложения, дифференциалы с учётом переносов через границы слов, — и именно ими оценивают Salsa20 и ChaCha20. Меняется не наличие метода, а его рабочая модель.

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

Алгоритм

RC4 состоит из KSA (key scheduling algorithm), который перемешивает 256-байтовый массив S ключом, и PRGA, который на каждом шаге меняет местами два элемента и выдаёт S[(S[i] + S[j]) mod 256]. Он прост, быстр и десятилетиями использовался в WEP, WPA-TKIP и TLS.

Смещения и атаки

Выход RC4 не равномерен: второй байт ключевого потока равен нулю с вероятностью около 2/256 вместо 1/256, а первые байты коррелируют с ключом. FMS-атака на WEP использует слабость первых байтов и IV, чтобы восстановить ключ по многим пакетам; в TLS атаки на RC4 (RC4 NOMORE и другие) эксплуатируют смещения в статистике. В 2015 году RFC 7465 запретил RC4 в TLS ⁴. Восстановление ключа RC4 по внутреннему состоянию разобрано в работе Бихама и Кармели ⁸.

Практический вывод: «алгоритм выглядит случайным» не означает «выход неотличим от случайного». Смещения в первых байтах достаточно, чтобы сломать протокол, использующий RC4 с разными nonce.

ChaCha20

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

ChaCha20 (RFC 8439) использует состояние 4×4 из 32-битных слов: константы "expand 32-byte k", ключ (8 слов), счётчик (1 слово) и nonce (3 слова). Раунд состоит из четырёх четверть-раундов над диагоналями и столбцами; каждый четверть-раунд — четыре сложения, четыре XOR и четыре циклических сдвига (ARX). За 20 раундов (10 двойных) состояние тщательно перемешивается, после чего прибавляется к исходному и выдаётся как блок потока ³.

Семейство Salsa20/ChaCha20 предложено Дэниелом Бернстайном и стало основой eSTREAM ⁵; ARX-операции нелинейны относительно GF(2), поэтому линейный криптоанализ неприменим; лучшие известные атаки на ChaCha20 не практичны. Важны детали реализации: счётчик увеличивается на каждый блок, nonce уникален для ключа, при переполнении счётчика поток нельзя продолжать ⁶.

Почему повтор nonce фатален

Повтор nonce даёт тот же поток. Тогда c1 ⊕ c2 = m1 ⊕ m2, и при известном одном сообщении второе восстанавливается полностью. В ChaCha20-Poly1305 повтор nonce ломает и аутентификацию: Poly1305 использует одноразовый ключ, выведенный из потока, и его повтор позволяет подделать тег (подробно — в теме 6).

Bit-flipping на практике

Подмена поля в токене

Пусть сервер выдаёт cookie role=guest;uid=42, зашифрованную поточным шифром, и доверяет расшифрованному содержимому. Противник знает формат и хочет role=admin;uid=42. Он вычисляет Δ для первых десяти байт и применяет к шифртексту. Сервер расшифрует валидную строку с правами администратора.

Защита: AEAD с проверкой тега, подпись cookie, серверная сессия. Поточный шифр без MAC не даёт целостности, и никакая длина ключа этого не исправляет.

Почему MAC обязателен

Шифрование и аутентификация — разные задачи. Поточный шифр скрывает содержимое, но не мешает изменению. MAC вычисляется по шифртексту (encrypt-then-MAC) или по открытому тексту (MAC-then-encrypt) с разными последствиями; безопасный вариант — AEAD, где тег проверяется до расшифрования ⁷. Об этом — темы 6 и 9 основного курса.

Повтор ключа и crib-dragging

Two-time pad

Если два сообщения зашифрованы одним потоком, c1 ⊕ c2 = m1 ⊕ m2. Для текстов на естественном языке этого достаточно, чтобы восстановить оба: пробел XOR буква даёт букву в другом регистре, а позиции пробелов угадываются по частотным аномалиям. Метод crib-dragging перебирает предполагаемое слово в одном сообщении и проверяет, даёт ли результат осмысленный текст во втором.

Проект «Venona»

Исторический пример — перехваты советских сообщений в проекте Venona: повторное использование ключей одноразовых блокнотов позволило американским криптоаналитикам частично восстановить текст. Это иллюстрация того, что «одноразовый» блокнот, использованный дважды, перестаёт быть одноразовым ¹.

Автоматизация

В лабораторной работе реализуется crib-dragging: для каждого смещения crib накладывается на c1 ⊕ c2, оценивается правдоподобность результата (доля печатных символов, частые слова) и выводятся кандидаты. Затем вручную или эвристикой восстанавливаются пробелы и оба текста.

Итоги темы

Поточный шифр быстр, но линеен: XOR позволяет менять открытый текст, не зная ключа, а повтор nonce уничтожает поток. LFSR ломается алгоритмом Берлекэмпа — Мэсси по 2L битам; RC4 имеет смещения, достаточные для атак на WEP и TLS; ChaCha20 свободен от известных практических атак, но требует уникального nonce и MAC.

Ключевой вывод: конфиденциальность и целостность — разные свойства, и поточный шифр даёт только первое. Следующая тема — блочные шифры и режимы — покажет, как те же ошибки (детерминированность, отсутствие целостности) проявляются в ECB, CBC и padding oracle.

Литература

1. Kahn D. The Codebreakers. — Scribner, 1996.
2. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. https://cacr.uwaterloo.ca/hac/
3. Nir Y., Langley A. ChaCha20 and Poly1305 for IETF Protocols. — RFC 8439, IETF, 2018. https://www.rfc-editor.org/rfc/rfc8439
4. Popov A. Prohibiting RC4 Cipher Suites. — RFC 7465, IETF, 2015. https://www.rfc-editor.org/rfc/rfc7465
5. Bernstein D. J. The Salsa20 Family of Stream Ciphers. — в кн. New Stream Cipher Designs, Springer, 2008, С. 84–97. DOI: 10.1007/978-3-540-68351-3_8
6. Aumasson J.-P. Serious Cryptography. — 2-е изд. — No Starch Press, 2024.
7. Ferguson N., Schneier B., Kohno T. Cryptography Engineering. — Wiley, 2010.
8. Biham E., Carmeli Y. Efficient Reconstruction of RC4 Keys from Internal States. — FSE 2008, DOI: 10.1007/978-3-540-71095-0_25

Дополнительные материалы к апокрифу 4

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

1. Почему в поточном шифре изменение одного бита ciphertext меняет ровно один бит открытого текста?
2. Что такое линейная сложность последовательности и почему она ограничивает применимость LFSR?
3. Сколько битов потока нужно для восстановления регистра длины L?
4. Почему секретные отводы LFSR не спасают положение?
5. Как смещение второго байта RC4 связано с утечкой первых байтов открытого текста?
6. Зачем в ChaCha20 счётчик отделён от nonce?
7. Что именно обеспечивает Poly1305 и чего не обеспечивает ChaCha20 сам по себе?
8. Почему формат nonce || ciphertext без тега не позволяет обнаружить подделку?
9. Как из c1 XOR c2 получается m1 XOR m2 и почему ключ исчезает?
10. Почему пробел — лучший маркер при переносе шпаргалки?
11. Чем последствия изменения бита в CTR отличаются от CBC?
12. Почему повтор nonce в GCM катастрофичен, а в CBC повтор IV — тоже плохо, но иначе?
13. Что добавляет AEAD к конфиденциальности и почему этого нельзя добиться порядком операций шифрования?
14. Почему в TLS 1.3 остались только AEAD-шифры?

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

Шпаргалка

cp lfsr_template.py lfsr.py          && python3 check_lfsr.py -v
cp rc4_template.py rc4.py            && python3 check_rc4.py
python3 rc4.py 200000
cp chacha20_template.py chacha20.py  && python3 check_chacha20.py
cp bitflip_template.py bitflip.py    && python3 check_bitflip.py -v
cp cribdrag_template.py cribdrag.py  && python3 cribdrag.py
python3 check_two_time.py recovered.txt

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

• RFC 8439 — ChaCha20 и Poly1305 с полными тестовыми векторами; лучший способ проверить реализацию.
• RFC 6229 — тестовые векторы RC4; там же видно, как смещения распределены по смещениям потока.
• Mantin, Shamir. «A Practical Attack on Broadcast RC4» (2001) — откуда берётся 2/256.
• RFC 7465 — запрет RC4 в TLS с перечнем атак.
• Massey. «Shift-Register Synthesis and BCH Decoding» (1969) — исходная статья алгоритма.
• Boneh. «The Legend of the Solitaire Cipher» и материалы по two-time pad — почему повтор потока равносилен публикации разности.
• Rogaway. «Evaluation of Some Blockcipher Modes of Operation» — сравнение режимов по свойствам, включая malleability.
• NIST SP 800-38D — GCM, требования к nonce и последствия повтора.
• Документация cryptography по AEAD — https://cryptography.io/en/latest/hazmat/primitives/aead/.

Углубление: почему повтор потока — это не «небольшая ошибка»

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

Формально это видно через условную энтропию. Пока поток не повторяется, H(M | C) = H(M): шифртекст не сообщает об открытом тексте ничего. После повтора H(M1, M2 | C1, C2) = H(M1, M2 | M1 XOR M2), и остаток неопределённости определяется избыточностью языка, а не длиной ключа. Для английского текста избыточность около 3,2 бита на символ, поэтому даже сотни байт разности достаточно для полного восстановления. Ключ при этом остаётся секретным — и совершенно бесполезным.

Отсюда два практических следствия. Первое: уникальность nonce — такое же жёсткое требование, как секретность ключа, и в GCM, и в ChaCha20-Poly1305 повтор nonce раскрывает не только разность открытых текстов, но и ключ аутентификации. Второе: любое шифрование без проверки целостности оставляет активному противнику возможность менять данные предсказуемо, поэтому современные протоколы не предлагают «просто шифрование» как отдельную опцию — только AEAD.

Углубление: почему LFSR не спасают даже секретные отводы

Частое заблуждение: если держать многочлен связей в секрете, регистр станет стойким. Алгоритм Берлекэмпа — Мэсси восстанавливает минимальный многочлен по 2L битам потока независимо от того, известен он заранее или нет. Более того, для последовательности, порождённой регистром длины L, линейная сложность не превосходит L, и это свойство проверяется статистически: чем длиннее наблюдаемый фрагмент, тем точнее оценка. Секретность многочлена даёт выигрыш не более чем в число вариантов отводов, то есть полиномиальный, а не экспоненциальный.

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

Лабораторная работа 4. Ключевой поток, который можно сложить

• Раздел курса: апокриф 4 «Поточные шифры: bit-flipping и повтор ключа»

Введение

В «Сейфе» сессионный токен выпускает сервер: шестнадцать байт nonce, дальше AES в режиме CTR и открытый текст вида role=guest;uid=42. Разработчик считает, что раз шифр стойкий, то и токен защищён. Мэллори не подбирает ключ — она переворачивает один бит в ciphertext и получает role=admin, потому что в поточном шифре каждый бит открытого текста связан ровно с одним битом шифртекста.

Работа идёт от примитива к последствиям. Сначала регистр сдвига с линейной обратной связью и алгоритм Берлекэмпа — Мэсси: как по двумстам битам потока восстановить весь генератор. Затем RC4 и его смещение второго байта, ChaCha20 по тестовому вектору RFC 8439, подделка сессионной cookie и классический повтор одноразового блокнота, который ломается переносом «шпаргалки» (crib-dragging). В продвинутой части сравниваются поточный шифр и режим CBC по способности сопротивляться изменению ciphertext, и формулируется, что именно даёт аутентифицированное шифрование.

Части: LFSR и Берлекэмп — Мэсси, RC4, ChaCha20, подделка токена, повтор ключа, продвинутая.

Цель работы

Научиться показывать отсутствие аутентификации в поточном шифре как рабочую атаку и объяснять, почему стойкость примитива не спасает протокол.

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

• восстанавливать многочлен связей LFSR по фрагменту потока и предсказывать следующие биты;
• объяснять, почему линейность LFSR делает его непригодным как генератор ключевого потока;
• измерять смещение второго байта RC4 и оценивать, как оно превращается в утечку;
• реализовывать ChaCha20 и сверять его с тестовым вектором;
• подделывать сессионный токен, меняя один бит ciphertext, без знания ключа;
• восстанавливать два сообщения, зашифрованные одним ключевым потоком;
• формулировать, какое минимальное изменение протокола закрывает каждую атаку.

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

Разделы «Поточный шифр как XOR с ключевым потоком», «Линейные регистры и почему они не годятся», «RC4: смещения и запрет», «ChaCha20 и Poly1305», «Повтор ключевого потока (two-time pad)», «Чем это лечится» апокрифа 4. Ключевые соотношения:

c = m XOR ks            шифрование
m = c XOR ks            расшифрование
c1 XOR c2 = m1 XOR m2   повтор ключевого потока: ключ сокращается

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

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

Ubuntu 24.04, Python 3.10+, cryptography, openssl. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-04 && cd ~/lab-apocrypha-04
unzip ~/lr-env.zip
cp lfsr_template.py lfsr.py
python3 check_lfsr.py -v

Заготовки копируются в файлы без суффикса _template: lfsr.py, rc4.py, chacha20.py, bitflip.py, cribdrag.py. Проверки ищут именно эти имена, а при их отсутствии падают обратно на заготовку и печатают честное «не реализовано».

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

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

Часть 1. Регистр сдвига и Берлекэмп — Мэсси

Задание

1. Реализуйте lfsr_sequence(taps, init, n), lfsr_period(taps, init) и проверьте период на многочлене x^4 + x + 1: он должен быть равен 15.
2. Реализуйте berlekamp_massey(bits): по фрагменту потока постройте минимальный многочлен связей. Функция возвращает пару «многочлен, длина регистра».
3. Сгенерируйте 200 бит известным регистром, оборвите поток на 40-м бите, восстановите многочлен по этим 40 битам и предскажите биты с 41-го по 200-й. Совпадение должно быть полным.
4. Ответьте: сколько битов потока нужно, чтобы однозначно восстановить регистр длины L, и почему это число вдвое больше L.
5. Объясните, почему для LFSR нельзя построить стойкий шифр, даже если отводы держать в секрете.
6. Возьмите data/lfsr_secret.json: письмо зашифровано XOR с потоком регистра неизвестной длины, начало письма известно. Вычтите известный заголовок из ciphertext — получите первые байты потока. Восстановите многочлен по 2L битам, достройте поток на всю длину письма и расшифруйте остаток.
7. Сохраните расшифрованный текст без завершающего перевода строки в файл lfsr_secret_plain.txt в каталоге работы и запустите python3 check_lfsr.py: появится строка «часть 2: расшифрованный текст совпадает с исходным». Найдите в письме контрольное слово — оно понадобится для отчёта.

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

Работающие lfsr.py и check_lfsr.py без ошибок, восстановленный многочлен, число битов, после которого предсказание стало точным, и вывод о линейности как структурной слабости, а не о неудачном выборе параметров.

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

Задание

1. Реализуйте rc4_ksa, rc4_prga, rc4. Сверьтесь с тестовыми векторами RFC 6229: ключ 0102030405, смещение 0, первые шестнадцать байт потока — b2396305f03dc027ccc3524a0a1118a8.
2. Запустите измерение: python3 rc4.py 200000. Для случайного ключа и нулевого открытого текста второй байт потока равен нулю заметно чаще, чем 1/256.
3. Запишите измеренную частоту и сравните с теоретической оценкой 2/256 из работы Мантина и Шамира.
4. Объясните, как эта частота превращается в атаку на первые байты cookie, если протокол шифрует сессионный идентификатор с нулевого смещения.
5. Проверьте, что в openssl RC4 отключён: openssl list -cipher-algorithms | grep -i rc4 и python3 -c "from cryptography.hazmat.primitives.ciphers import algorithms; print(hasattr(algorithms, 'ARC4'))". Объясните причину запрета в RFC 7465.

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

Реализация, совпадающая с вектором, измеренная частота, отличающаяся от 1/256 статистически значимо, и вывод о том, что смещение — свойство самого генератора, а не ошибка конкретной реализации.

Часть 3. ChaCha20 по тестовому вектору

Задание

1. Реализуйте rotl32, quarter_round, initial_state, chacha20_block, chacha20_encrypt.
2. Сверьте блок с тестовым вектором RFC 8439, раздел 2.3.2: ключ из 32 байт 00..1f, nonce 000000090000004a00000000, счётчик 1. Первые шестнадцать байт выхода: 10f1e7e4d13b5915500fdd1fa32071c4.
3. Зашифруйте строку Ladies and Gentlemen of the class of '99 с ключом и nonce из RFC 8439, раздел 2.4.2. Сверьте результат с вектором.
4. Разберите, зачем в ChaCha20 счётчик блока отделён от nonce и что произойдёт, если два сообщения получат один и тот же nonce и счётчик.
5. Ответьте: ChaCha20 обеспечивает конфиденциальность, целостность, и то и другое, или ничего из перечисленного?
6. Откройте data/nonce_reuse.json: два сообщения зашифрованы ChaCha20 с одним ключом и одним nonce, открытый текст первого известно. Сложите ct1 XOR ct2, вычтите известный pt1 и восстановите начало второго сообщения. Сверьтесь с pt2_prefix_sha256.
7. Сравните этот случай с частью 5: чем атака на ChaCha20 при повторе nonce отличается от атаки на two-time pad? Что даёт знание алгоритма помимо разности открытых текстов?

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

Совпадение с обоими векторами, объяснение структуры состояния 4+8+4 слова и точный ответ на вопрос 5: только конфиденциальность, целостность появляется лишь вместе с Poly1305.

Часть 4. Подделка сессионного токена

Задание

1. Изучите token_service.py: issue(plaintext) возвращает nonce || ciphertext, где nonce шестнадцать нулевых байт, а parse(token) расшифровывает и возвращает строку.
2. Реализуйте xor_bytes и forge(token, known, target). Известный фрагмент открытого текста — role=guest, желаемый — role=admin. Разность known XOR target накладывается на ciphertext начиная с байта 16.
3. Запустите python3 check_bitflip.py -v. Проверка выпускает настоящий токен, подделывает его и скармливает серверу.
4. Убедитесь, что parse возвращает role=admin;uid=42, что nonce не изменился и что длина сохранена.
5. Объясните, почему сервер не может отличить подделку: что именно отсутствует в формате токена.
6. Предложите два исправления: одно на уровне примитива (AEAD), одно на уровне протокола (подпись токена). Для каждого укажите, что именно оно добавляет.

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

Проходящая проверка, поддельный токен с role=admin, сохранённый nonce и формулировка: сервер расшифровывает и верит результату, потому что никто не проверяет целостность до разбора полей.

Часть 5. Повтор ключевого потока

Задание

1. Откройте data/two_time.json: три сообщения зашифрованы одним ключевым потоком, открытый текст первого опубликован (это пресс-релиз), остальные два — служебные. Шифртексты лежат в data/two_time_1.hex … two_time_3.hex.
2. Восстановите ключевой поток: key = ct1 XOR pt1. Убедитесь, что его длина равна длине самого длинного сообщения — иначе последние байты второго и третьего сообщений останутся неизвестными.
3. Расшифруйте второе и третье сообщения тем же потоком. Сохраните все три строки (первая — опубликованный текст) в recovered.txt по одному сообщению на строку.
4. Запустите python3 check_two_time.py recovered.txt. Все три строки должны совпасть: первая — с опубликованным текстом, остальные — по SHA-256.
5. Теперь усложните условие: считайте первое сообщение неизвестным. Запустите python3 cribdrag.py, выполните auto и посмотрите, какие позиции восстановились уверенно. Протащите шпаргалку the командой drag 1 2 "the ".
6. Объясните, почему при неизвестных открытых текстах задача сводится к языковой: сколько битов неопределённости остаётся на символ при избыточности английского около 3,2 бита.
7. Ответьте, почему длина ключа должна покрывать самое длинное сообщение и что произойдёт, если «экономить» и шифровать коротким потоком.

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

Три восстановленных сообщения, совпадающих с data/two_time.json, понимание, что ключ здесь не подбирается, а сокращается при вычитании, и вывод о том, что повтор потока превращает криптографическую задачу в задачу о языке.

Часть 6. Продвинутая: чем поточный шифр отличается от CBC по последствиям

Задание

1. Возьмите cryptography и зашифруйте строку role=guest;uid=42 двумя способами: AES-CTR и AES-CBC с PKCS7. Для CBC используйте случайный ключ и случайный IV.
2. Поменяйте один бит в блоке ciphertext и посмотрите, что произойдёт при расшифровании: в CTR испортится ровно один бит открытого текста, в CBC — весь блок и один бит следующего.
3. Объясните, почему CBC при этом тоже не даёт целостности: измените бит в предпоследнем блоке и покажите, что открытый текст меняется предсказуемо, если структура известна.
4. Сравните: в каком режиме подделка role=guest → role=admin требует знания открытого текста, а в каком — ещё и выравнивания по блоку.
5. Сформулируйте общее правило: конфиденциальность без аутентификации даёт активному противнику возможность изменять данные предсказуемо. Приведите пример из TLS 1.3, где это правило реализовано в дизайне протокола.
6. Проверьте вывод на практике: соберите AES-GCM токен с тем же открытым текстом и повторите попытку подделки. Зафиксируйте, на каком шаге проверка целостности отвергает изменение.

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

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

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

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

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

1. Почему в поточном шифре изменение бита ciphertext меняет ровно один бит открытого текста?
2. Что такое линейная сложность последовательности и почему она ограничивает LFSR?
3. Сколько битов нужно для восстановления регистра длины L и откуда берётся эта оценка?
4. Как смещение второго байта RC4 превращается в утечку открытого текста?
5. Почему ChaCha20 без Poly1305 не годится для токенов?
6. Что именно проверяет сервер, если формат токена — nonce || ciphertext без тега?
7. Почему при повторе ключевого потока c1 XOR c2 = m1 XOR m2?
8. Как работает перенос шпаргалки и почему пробел — лучший маркер?
9. Чем отличается последствие изменения бита в CTR и в CBC?
10. Почему AEAD закрывает целый класс атак, а не отдельный случай?
11. Что произойдёт, если в GCM повторить nonce при том же ключе?
12. Какое минимальное изменение протокола закрывает атаку из части 4?