ChaCha20 и Poly1305: устройство связки и почему она такая

Связка, которую собрал не автор

ChaCha20-Poly1305 стоит сегодня в TLS 1.3 и QUIC, в WireGuard, в OpenSSH, в генераторе случайных чисел ядра Linux и в arc4random систем BSD. При этом связки как замысла не существовало: ChaCha и Poly1305 написаны порознь, с разницей в три года, под разные задачи, и в пару их свёл не автор алгоритмов, а потребитель — Google в 2013–2014 годах, под конкретный класс железа: мобильные процессоры без аппаратного ускорения AES. Всё, что выглядит цельной конструкцией, на деле стык двух независимых линий, и стык этот держится на одном свойстве Poly1305, заложенном туда за восемь лет до того, как оно понадобилось.

Эта статья — про механизм и про причины. Почти каждое решение внутри обеих половин имеет прослеживаемую причину и названную цену: отказ от таблиц подстановки — ответ на кэш-тайминговую атаку на AES, отказ от умножения — на то, что умножение в постоянном времени медленнее обычного, выбор простого поля в Poly1305 — на отсутствие в процессорах 2005 года команды умножения без переносов, обрезка ключа — на разрядность частичных произведений. Пересказывать псевдокод из RFC 8439 здесь незачем, он и так читается за полчаса; интересно, почему он такой.

Это вторая статья цикла crypto-*. Понятия ключа, nonce, AAD, тега и лимитов на объём введены в заметке про AEAD и здесь не переопределяются; откуда берётся сам ключ — в заметке про обмен ключами. Сравнение с AES-GCM — предмет следующей статьи цикла, и здесь оно появляется только там, где без него не объяснить устройство.

Две линии происхождения

Salsa20 и eSTREAM

Первая линия начинается в 2005 году с Salsa20 — поточного шифра, поданного Бернштейном на конкурс eSTREAM. Конкурс возник из констатации, записанной в самом призыве подавать примитивы (версия 1.3, 12 апреля 2005 года): «The cryptographic community is well served by a variety of efficient and trusted block ciphers. However the same does not seem to hold for stream ciphers». За два года до того европейский проект NESSIE закончил свою работу итоговым решением от 27 февраля 2003 года, где раздел про поточные шифры состоит из одной строки: «The NESSIE portfolio in this category is empty». Ни один поданный поточный шифр в портфель не попал.

eSTREAM шёл больше трёх лет и закончился портфелем от 15 апреля 2008 года. Salsa20 попала туда в программный профиль, но не в двадцатираундовом варианте: комитет выбрал Salsa20/12, объяснив это балансом — «Eight and twenty round versions were also considered during the eSTREAM process, but we feel that Salsa20/12 offers the best balance». Сам портфель авторы просили не читать как список победителей: «We prefer not to use the word "winners"».

Существенно то, что ChaCha в этой истории не участвовала. Она опубликована отдельной шестистраничной запиской 28 января 2008 года, внутри финальной фазы конкурса: третья фаза началась в апреле 2007 года, и до портфеля оставалось два с половиной месяца. Но подана на eSTREAM ChaCha не была, там не оценивалась и формального знака качества оттуда не имеет — и это довод, а не дата выхода записки. Обратное регулярно подразумевается, когда ChaCha20 называют «шифром из портфеля eSTREAM»: в портфеле лежит её предшественница, и притом в сокращённом до двенадцати раундов виде. Реализации ChaCha8, ChaCha12 и ChaCha20 Бернштейн выложил в каталог Salsa20 бенчмарочного набора eSTREAM, и это единственная связь.

Poly1305-AES

Вторая линия старше ChaCha на три года. Poly1305-AES представлен на FSE 2005 как самостоятельный код аутентификации сообщений, и AES играл в нём служебную роль: им зашифровывался nonce, чтобы получить одноразовую маску. Заменяемость этой части объявлена прямо в статье — «If that happens, users should switch to Poly1305-AnotherFunction. Poly1305-AnotherFunction provides the same security guarantee relative to the security of AnotherFunction». Заготовка, оставленная на случай, если AES сломают, через восемь лет пригодилась совсем для другого: IETF выкинула AES не потому, что он сломался, а потому, что под рукой уже была гамма ChaCha20.

ARX — ответ на кэш-тайминг, а не эстетика

Это главная причинно-следственная связь темы, и без неё вся конструкция выглядит произвольной.

В 2005 году Бернштейн опубликовал кэш-тайминговую атаку на AES. Механизм её в том, что быстрая программная реализация AES индексирует таблицы подстановки — «typical high-speed AES software has several 1024-byte S-boxes» — байтами, зависящими от секрета. Какие строки кэша при этом окажутся горячими, зависит от ключа, а время ответа зависит от того, какие строки горячие. В статье о семействе Salsa20 (§2.3) вывод сформулирован без смягчений:

A further argument against S-box lookups is that, on most platforms, they are vulnerable to timing attacks. NIST's statement to the contrary in [19, Section 3.6.2] (table lookup is "not vulnerable to timing attacks") is erroneous.

И дальше, там же: «For me, the timing-attack problem is decisive».

Отсюда набор операций. Salsa20 и ChaCha строятся на трёх действиях над 32-битными словами: сложение по модулю 2³², XOR и вращение на постоянное число бит (§2.1 той же статьи) — отсюда и название класса, ARX. Ни таблиц, ни умножений, ни сдвигов на переменное расстояние. У каждого отказа своя причина, и причины разные.

Таблицы отвергнуты из-за тайминга, как выше. Умножение — сначала просто по скорости: оно «takes several cycles on the fastest CPUs, and many more cycles on other CPUs», и выигрыш в перемешивании не окупает «massive speed penalty on other CPUs». Ровно этим доводом, прямо следующей фразой, отвергнуты 64-битные сложения, 32-битные умножения и вращения на переменное («зависящее от данных») расстояние. И только дальше, отдельным абзацем со словами «A further argument», вводится тайминг — соображение более тонкое, и оно объясняет, почему «в процессоре же есть умножитель» не аргумент: «What really matters is not the speed of integer multiplication, but the speed of constant-time integer multiplication, which is often much slower». В доказательство Бернштейн приводит PowerPC 7450, где команда mull обычно занимает два такта, но всего один, если старшие 15 бит второго операнда все нули или все единицы, — то есть время выполнения зависит от данных.

Существенно здесь вот что: постоянство времени в ARX-шифре обеспечивает структура алгоритма, а не аккуратность реализатора и не наличие подходящей команды в процессоре. Сложение, XOR и вращение на константу выполняются за фиксированное время на любом процессоре, который их вообще умеет; чтобы получить утечку, нужно постараться. AES в этом месте устроен наоборот: обойти утечку в программной реализации тяжело и дорого — «It is extremely difficult to work around this problem without sacrificing a tremendous amount of speed» (§2.3), а в статье про Poly1305-AES то же сказано ещё прямее: «It is extremely difficult to write high-speed constant-time AES software». Постоянное время там даёт либо аппаратная команда, либо специальная техника реализации, и ни то, ни другое не следует из спецификации шифра. Это и есть разница между «алгоритм можно реализовать безопасно» и «алгоритм трудно реализовать небезопасно».

У Salsa20 и ChaCha есть ещё одно свойство, важное дальше по тексту: расписания ключа нет вовсе. «Salsa20 does not preprocess the key before generating a block; each block uses the key directly as input» (§3.1). Никакой предвычисленной на ключ структуры не существует, а значит, добавление тысячного ключа не стоит ничего — ни памяти, ни промахов кэша. Через раздел выяснится, что у Poly1305 ровно многоключевая работа была заявленной главной целью, и совпадение двух решений — единственное, что делает связку не случайной.

Что именно изменила ChaCha

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

Четверть-раунд обновляет каждое слово дважды

Четверть-раунд Salsa20 обновляет каждое из четырёх слов состояния по одному разу. Четверть-раунд ChaCha за то же число операций обновляет каждое слово дважды:

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

Здесь <<<= — вращение влево на постоянное число бит, а += — сложение по модулю 2³². Четыре сложения, четыре XOR, четыре вращения — ровно столько же, сколько у Salsa20.

Эффект измерен перебором однобитных входных разностей: «in the absence of carries, the ChaCha quarter-round changes (on average) 12.5 output bits, while the Salsa20 quarter-round changes 8 output bits». Цена при этом нулевая и даже отрицательная: раунд состоит из тех же 16 сложений, 16 XOR и 16 вращений, сохраняет ту же векторизуемость, а реализация экономит один из 17 регистров, которые нужны «естественной» реализации Salsa20.

Вращения при этом изменены с 7, 9, 13, 18 на 16, 12, 8, 7, и вот здесь автор осторожен: «The difference in security appears to be negligible… The change boosts speed slightly on some platforms while making no difference on other platforms». Ходовое объяснение — что кратные восьми расстояния позволяют выполнить вращение байтовой перестановкой SIMD вместо пары сдвигов, — в статье не утверждается ни в каком виде. Оно правдоподобно и согласуется с тем, что три из четырёх новых констант кратны восьми, но это интерпретация, а не цитата, и подавать её как замысел автора нельзя.

Матрица и порядок обхода

Состояние — 4×4 слова по 32 бита, то есть 64 байта. У Salsa20 константы, ключ и подконтрольный атакующему вход рассыпаны по матрице по диагонали; ChaCha собирает их в строки: константы сверху, восемь слов ключа посередине, счётчик блока и nonce — в нижней строке. Константы — это фиксированная строка expand 32-byte k, разложенная на четыре 32-битных слова: 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574 (RFC 8439, §2.3). ChaCha берёт их у Salsa20 без изменений, и они одни и те же при любом ключе, nonce и номере блока — это единственная строка матрицы, которую не задаёт ни владелец ключа, ни подконтрольный атакующему вход. Раунды чередуются: первый обрабатывает четыре столбца, второй — четыре юго-восточные диагонали, и так двадцать раз; после этого результат складывается с исходной матрицей, что и делает блочную функцию необратимой.

Перестановка слов не косметика: она устраняет необходимость внутренней перестановки матрицы, которую SIMD-реализации Salsa20 делали руками, чтобы превратить диагонали в столбцы. Про выбор позиций Бернштейн высказывается честнее, чем принято цитировать: разброс входов в Salsa20 он выбирал ради удобства собственного анализа, а в ChaCha считает, что «the spread of positions in Salsa20 gave unnecessary flexibility to attackers», не утверждая, что новая раскладка что-то улучшает — «I don't see any evidence that it actually improves security».

Скорости, о которых пересказы молчат

Считается, что ChaCha быстрее Salsa20. Таблица 1.3 в статье самого автора говорит иначе, и это стоит прочитать внимательно, потому что цифры там приведены для восьми, двенадцати и двадцати раундов, а проценты в тексте — только для восьми.

На двадцати раундах Core 2 Duo даёт 3,95 такта на байт у ChaCha20 против 3,90 у Salsa20/20 — то есть ChaCha чуть медленнее. PowerPC G4 даёт 4,13 против 4,24, то есть чуть быстрее. Pentium 4 даёт 15,03 против 11,74. В процентах, посчитанных автором для восьмираундовых вариантов, картина та же: от «28% быстрее» на Pentium D до «31% медленнее» на Pentium 4, с оговоркой «I expect these numbers to change with further tuning».

Вывод отсюда простой и он не про скорость: приобретение ChaCha — запас по диффузии, а не такты. Двадцать раундов вместо двенадцати в портфеле eSTREAM — это тот же запас, купленный ещё раз и уже деньгами. Реальный разрыв в производительности, ради которого ChaCha20-Poly1305 внедряли в 2014 году, возник не между ChaCha и Salsa20, а между ARX-шифром и AES на процессорах без аппаратного AES.

Poly1305: MAC, спроектированный под многоключевой сервер

Многочлен и маска

Poly1305 — одноразовый аутентификатор в духе Картера–Вегмана. Сообщение режется на 16-байтные блоки, каждый дополняется единичным битом сверху и читается как целое число; получившиеся числа берутся коэффициентами многочлена, который вычисляется в секретной точке r по модулю простого 2¹³⁰ − 5; результат приводится по модулю 2¹²⁸ и складывается с секретной маской. В исходном Poly1305-AES маска — это AES_k(n) для nonce сообщения, и одноразовость обеспечивает именно она: r живёт долго, меняется только маска.

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

Гарантия сформулирована количественно и без обращения к «вычислительной трудности»: если m и m' — различные сообщения длиной не больше L, то вероятность того, что их хэши отличаются на заданную величину, не превышает 8⌈L/16⌉/2¹⁰⁶. Отсюда граница на подделку: при D попытках и C ≤ 2⁶⁴ подписанных сообщениях шанс противника не больше ε + 14·D·⌈L/16⌉/2¹⁰⁶, где ε — преимущество противника в различении AES_k и случайной перестановки; в связке с ChaCha20 на это место встаёт предположение, что блочная функция ChaCha20 неотличима от случайной функции.

Почему простое поле, а не GF(2¹²⁸)

Это ровно то место, где расходятся Poly1305 и GHASH, аутентификатор AES-GCM. Оба — полиномиальные MAC; различие в том, над каким полем считается многочлен. GHASH работает в двоичном поле GF(2¹²⁸), где умножение — это умножение без переносов, а Poly1305 — в простом поле, где умножение обычное, целочисленное.

Причина названа в статье: «Polynomial-evaluation MACs over prime fields can exploit the multipliers built into many current CPUs, achieving substantially better performance than polynomial-evaluation MACs over binary fields». В 2005 году целочисленный умножитель был в любом процессоре, а команды умножения без переносов не было нигде: PCLMULQDQ появилась у Intel только в 2010 году, в микроархитектуре Westmere, и в том же поколении, что AES-NI. То есть команда, без которой двоичное поле не даёт своей скорости, появилась через пять лет после статьи про Poly1305, а Poly1305 работал сразу и везде. Это же объясняет, почему сегодня, когда обе команды есть, разрыв выглядит иначе, — но это тема следующей статьи.

Здесь же связка сводит в одну реализацию два противоположных довода, и это стоит назвать вслух. Умножение Бернштейн отверг в шифре именно потому, что важна скорость «constant-time integer multiplication, which is often much slower», — а Poly1305 построен на целочисленном умножении. Противоречия нет только потому, что гарантии у двух половин разной природы: у ARX-шифра постоянное время следует из набора операций, а в Poly1305 его обеспечивает реализатор. В описании финальной редукции это сказано прямым текстом: вычесть 2¹³⁰ − 5 и оставить результат, если он неотрицателен, надо, «being careful to use constant-time operations so that no information is leaked through timing». Структурная гарантия, иными словами, есть у шифра и отсутствует у MAC. Практически это терпимо — аккуратности требует не весь код, а несколько ветвлений в конце, — но вывод «в ARX постоянное время получается само» на всю связку не распространяется.

Главная цель: тысячи ключей одновременно

Самое интересное про Poly1305 в том, что он проектировался под профиль нагрузки, который стал нормой десятью годами позже. Автор называет цель прямым текстом:

Key agility. […] Poly1305-AES can fit thousands of simultaneous keys into cache, and remains fast even when keys are out of cache. This was my primary design goal for Poly1305-AES. Almost all competing functions use a large table for each key; as the number of keys grows, those functions miss the cache and slow down dramatically.

Речь о том, что у Poly1305 нет предвычисленной на ключ структуры: ключ — это 32 байта, которые используются как есть. Предшественник того же автора, hash127, ради скорости заводил на каждый ключ несколько килобайт таблиц, и Бернштейн называет это прямо: «this is a disaster for applications handling many keys simultaneously, but I didn't think beyond a single key».

Сопоставьте это с отсутствием расписания ключа у Salsa20 и ChaCha — и станет видно, что обе половины связки решают одну и ту же задачу: держать много живых ключей одновременно, не платя за каждый. Оговорка здесь обязательна, потому что на этом сопоставлении держится вся статья: целью многоключевая работа названа только у Poly1305, а у Salsa20 отсутствие предвычислений подано как свойство конструкции — «There are no hidden preprocessing costs in Salsa20» (§3.1), — и про тысячи одновременных ключей там не сказано ничего. Сведение двух решений к одной задаче — интерпретация, а не утверждение источника. Веб-сервер с десятками тысяч TLS-соединений — ровно этот случай, и именно он сделал пару осмысленной, хотя собирали её вообще не поэтому.

Обрезка ключа: 22 бита, которые платит реализация

Ключ r используется не целиком. Четыре его байта обязаны иметь нулевые четыре старших бита, ещё три — нулевые два младших; всего сброшено 22 бита, и остаётся 2¹⁰⁶ возможных значений r вместо 2¹²⁸. Эта обрезка (clamping) — чистая уступка реализации: нули в старших битах ограничивают разрядность частичных произведений, нули в младших позволяют ленивую редукцию. Автор называет цену и признаёт её: «I constrained r to simplify and accelerate implementations… A wider range of r — e.g., all 128-bit integers — would allow a quantitatively better security bound, but the current bound DL/2¹⁰⁶ will be perfectly satisfactory for the foreseeable future».

Двадцать два бита — не абстрактная потеря. В многопользовательском анализе связки (CCS 2021) именно они попадают в доминирующий член границы: размер тега «is effectively further reduced by the factor 2²⁵ due to the clamping of 22 bits in the hash key r». Две величины тут легко перепутать, и они разные. 2¹⁰⁶ — мощность множества значений r, она же знаменатель бернштейновской границы DL/2¹⁰⁶. А стойкость аутентификации при 128-битном теге упирается в 103 бита: доминирующий член границы — это число попыток подделки, умноженное на 2²⁵·ℓ и делённое на 2¹²⁸, то есть q_v·ℓ/2¹⁰³. Ровно это число записано в заметке про AEAD как IA ≤ (v·(L' + 1))/2¹⁰³, и оно же получается из границы самого Бернштейна: 8⌈L/16⌉/2¹⁰⁶ — это ⌈L/16⌉/2¹⁰³. Оба числа — прямое следствие решения, принятого ради скорости на процессорах 2005 года.

Страшно это не становится по одной причине: в связке r одноразовый. У исходного Poly1305-AES r жил долго, и 22 бита были платой навсегда; в конструкции IETF и r, и маска выводятся заново для каждого nonce, так что противнику негде накапливать наблюдения об одном и том же r.

Как их свели вместе

Кто и зачем

В марте 2013 года Адам Лэнгли, Ван-Тэ Чанг и Бен Лори начали реализовывать ChaCha20 и Poly1305 в OpenSSL и NSS. Мотив назван в отчёте Google от 24 апреля 2014 года: нужен был шифр, который «operates three times faster than AES-GCM on devices that don't have AES hardware acceleration, including most Android phones, wearable devices such as Google Glass and older computers». В их замерах на Snapdragon S4 Pro AES-GCM давал 41,5 МБ/с, а ChaCha20-Poly1305 — 130,9 МБ/с. К февралю 2014 года через новую связку шли почти все HTTPS-соединения Chrome на Android к сервисам Google.

Дальше картина расходится на две ветки, и это стоит держать в голове, потому что совместимости между ними нет.

В январе 2014 года OpenSSH 6.5 ввёл собственный шифр chacha20-poly1305@openssh.com, основанный на тогдашнем черновике Лэнгли, но отличающийся «in the layout of data passed to the MAC and in the addition of encryption of the packet lengths». У него два независимо ключуемых экземпляра ChaCha20: один шифрует только четырёхбайтовое поле длины пакета, второй — полезную нагрузку и работает в паре с Poly1305. Причина в том, что длину надо расшифровать до проверки тега, и «by using an independently-keyed cipher instance to encrypt the length, an active attacker seeking to exploit the packet input handling as a decryption oracle can learn nothing about the payload contents or its MAC».

Ветка IETF пошла через CFRG: RFC 7539 (май 2015, информационный), затем RFC 7905 с шифрсьютами для TLS (июнь 2016, стандарт) и, наконец, RFC 8439 (июнь 2018), отменивший 7539. В TLS 1.3 связка осталась рекомендованной, но не обязательной: RFC 9846, §9.1, требует TLS_AES_128_GCM_SHA256 и лишь рекомендует TLS_CHACHA20_POLY1305_SHA256.

Конструкция AEAD

Собственно связка описана в §2.8 RFC 8439 и устроена так. Блок гаммы с номером 0 не шифрует ничего: его первые 32 байта становятся одноразовым ключом Poly1305 — первые 16 после обрезки дают r, следующие 16 дают маску, — а оставшиеся 32 байта выбрасываются. Шифрование начинается с блока 1. Тег считается по входу из пяти частей.

AAD ‖ pad₁ ‖ шифртекст ‖ pad₂ ‖ len(AAD) ‖ len(CT)

Выравнивания pad₁ и pad₂ дополняют нулями до кратности 16 байт, длины — 64-битные little-endian числа. Зачем в тег входят длины и почему без них граница между AAD и шифртекстом становится подвижной, разобрано в статье про AEAD — здесь достаточно сказать, что эта часть не специфична для ChaCha20 и ровно так же устроена в GCM.

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

Что IETF изменила против оригинала и чем это обошлось

Оригинальная ChaCha делит нижнюю строку матрицы пополам: 64 бита на счётчик блока и 64 на nonce. RFC 8439 изменил пропорцию на 32 и 96 бит, объяснив это одной фразой: «We have modified this here to be more consistent with recommendations in Section 3.2 of [RFC5116]».

Заплачено за это дважды. Во-первых, 32-битный счётчик блока ограничивает объём, зашифрованный под одной парой (ключ, nonce), до 2³² блоков по 64 байта, то есть 2³⁸ байт, — «256 GB, but that is enough for most uses» по формулировке RFC; для сетевого пакета это бесконечность, для шифрования диска или большого файла — нет. Во-вторых, 96-битный nonce слишком короток, чтобы выбирать его случайно без учёта числа сообщений, и отсюда выросла отдельная ветка XChaCha20 с 192-битным nonce. Арифметика, стоящая за словом «слишком короток», и разбор XChaCha20 — в статье про AEAD; здесь важно происхождение проблемы: она не свойство ChaCha, а следствие того, где IETF провела границу между счётчиком и nonce.

Само же RFC 8439 отмечает, что дорога назад открыта: «we can return to the original design, reduce the nonce to 64 bits, and use the integer at position 13 as the top 32 bits of a 64-bit block counter». По этой дороге никогда и не уходил OpenSSH: его конструкция старше RFC на полтора года и берёт исходное деление, где nonce — 64-битный номер пакета. WireGuard пришёл к тому же с другой стороны: у него штатный 96-битный nonce, но собран он из 32 нулевых бит и 64-битного счётчика пакетов, то есть верхняя треть не используется вовсе.

Состояние криптоанализа

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

ChaCha20 — это двадцать раундов. Лучшие опубликованные атаки доходят до семи и семи с половиной, то есть запас составляет двенадцать с половиной раундов. Числа ниже — из работы Флореса-Гутьерреса и Тодо (EUROCRYPT 2025), которая ввела в эту область метод bit puncturing вместо доминировавших с 2008 года вероятностно нейтральных бит (PNB), и из последующих работ, сверенных на дату сверки.

Строку про ASIACRYPT 2025 нужно читать с оговоркой: сама работа доступна только за платным доступом издателя, и оба числа взяты из сводной таблицы препринта eprint 2025/1830, а не из первоисточника. По данным она совпадает с работой EUROCRYPT — те же 2¹²⁷·¹, — а по времени дешевле, то есть при одинаковом объёме данных строго её улучшает.

Читать эту таблицу нужно по двум колонкам сразу, иначе выводы получаются неверные. Формально 2¹⁴⁸ меньше перебора 256-битного ключа на сто бит — но требование 2¹²⁷·⁷ блоков данных означает, что противнику нужна почти вся гамма, вообще существующая под одним ключом: у ChaCha20 в редакции RFC 8439 нижняя строка матрицы даёт 2³² значений счётчика на 2⁹⁶ значений nonce, то есть 2¹²⁸ блоков всего. Фронт при этом не из двух крайних точек: та же работа даёт 2¹⁰²·⁹ блоков при времени 2¹⁵⁴·², а атака, укладывающаяся в мыслимый объём данных (2⁶⁸·⁹ блоков — это уже конечное число), стоит 2¹⁶⁷·⁹, что неисполнимо по времени. Практических следствий у всего этого ноль; ценность в другом — в том, что за восемнадцать лет фронт сдвинулся с семи раундов до семи с половиной, и это хорошая мера консервативности двадцатираундового выбора.

Что действительно стоит отслеживать: не улучшение времени на семи раундах, а появление атаки на восьми. Его пока нет.

Отдельная линия — доказательства самой композиции, а не её половин. Их два. Проктер в заметке 2014 года свёл стойкость связки к тому, что ChaCha20 — псевдослучайная функция, Poly1305 — почти-Δ-универсальная хэш-функция, а противник не повторяет nonce. Семь лет спустя Дегабриеле, Говинден, Гюнтер и Патерсон показали, что в этом доказательстве есть дефект, починили его и заодно доказали стойкость в многопользовательской постановке — той, где противник атакует много соединений сразу и выигрывает, сломав любое.

Из этой работы следуют два вывода, полезные на практике и неочевидных. Первый: учащение перевыработки ключа не улучшает многопользовательскую стойкость ChaCha20-Poly1305, потому что в границе нет ни одного члена, зависящего от объёма или числа запросов на пользователя, — тогда как у GCM такой член есть и перевыработка помогает. Авторы объясняют это тем, что «under the hood ChaCha20 is based on a permutation and not a block cipher in counter mode», и приводят атаки, показывающие, что граница плотная. Второй: доминирующий член зависит от числа попыток подделки и длины тега, а не от объёма зашифрованного. Это и есть формальное основание того, что в заметке про AEAD записано как «CA ≤ 0 при живом лимите на подделки»: считать в ChaCha20-Poly1305 надо не байты, а неудачные расшифровки, и потому у QUIC лимит на подделки есть, а лимит на объём выключен.

Урок Terrapin: почему именно эта конструкция

Terrapin (CVE-2023-48795) разобран в статье про AEAD — там механика атаки, роль номера пакета и то, почему ни один шифр в этой истории не подвёл. Здесь стоит ответить на другой вопрос: почему из всех шифров SSH особенно чувствительным оказался именно chacha20-poly1305@openssh.com.

Ответ записан в Security Considerations черновика, стандартизующего эту конструкцию, и он структурный:

This specification modifies the SSH binary packet protocol in a way that makes the encryption and authentication of every packet independent: instead of generating a single continuous cipher stream and dividing it at packet boundaries, a fresh cipher stream is started for each packet based on that packet's sequence number.

То есть nonce здесь — номер пакета, и ничего больше. Каждый пакет шифруется собственной гаммой, начинающейся с блока 0 для своего номера; связи между пакетами нет никакой. У традиционных для SSH режимов вроде CTR гамма непрерывна и режется по границам пакетов, поэтому удаление пакета сбивает сдвиг и всё последующее превращается в мусор. Здесь же вырезание пакета не портит ничего, если удалось подвинуть представление принимающей стороны о номере, — а подвинуть его удаётся вставкой SSH_MSG_IGNORE в открытую часть до включения шифрования.

Картина при этом не двоичная, и соседняя заметка перечисляет среди уязвимых не только ChaCha20, но и CBC в связке с ETM. Противоречия нет: «уязвим» и «эксплуатируется» — разные вещи. В режимах Encrypt-and-MAC тег считается по открытому тексту, поэтому после выреза проверка падает сразу. В Encrypt-then-MAC он считается по шифртексту, номеру пакета и незашифрованному полю длины — проверка проходит, и дальше всё решает состояние шифра: у CTR гамма сбита навсегда и мусором становится весь поток, у CBC сцепление восстанавливается через один блок, так что испорчен только первый блок первого уцелевшего пакета. Отсюда и градация авторов Terrapin: ChaCha20-Poly1305 эксплуатируется всегда, CBC+ETM — с заметной вероятностью, CTR+ETM — почти никогда.

Независимость пакетов — не дефект, а осознанное свойство: она нужна, чтобы поле длины можно было расшифровать отдельным ключом и не создать оракул. Дефект в том, что номер пакета ни к чему не привязан и пересекает границу включения шифрования. Лечится это на уровне протокола: strict KEX сбрасывает номера после обмена ключами и запрещает посторонние сообщения во время рукопожатия. Черновик требует обеих мер сразу и в императивной форме — «Implementations MUST implement both countermeasures to be safe».

Статус черновика на дату сверки: draft-ietf-sshm-chacha20-poly1305-04 от 26 мая 2026 года, в WG Last Call, намеченный статус — Standards Track. Он стандартизует ровно конструкцию OpenSSH под именем без суффикса @openssh.com и заодно фиксирует деталь, которую легко пропустить: в исходном Poly1305-AES между сообщениями переиспользуется r, а меняется только маска, тогда как здесь «both values change in every message».

Где встречается и почему именно там

Про QUIC стоит сказать отдельно, потому что там ChaCha20 используется не как AEAD. Защита заголовка (RFC 9001, §5.4.4) берёт 16 байт из шифртекста пакета и подставляет их прямо в нижнюю строку матрицы: первые четыре байта — счётчик блока, остальные двенадцать — nonce. Затем блочная функция вызывается один раз, чтобы зашифровать пять нулевых байт. Это иллюстрация свойства, о котором легко забыть: блочная функция ChaCha20 самодостаточна как псевдослучайная функция, и её можно вызывать напрямую там, где нужен PRF на 512-битном состоянии.

Про arc4random тоже стоит уточнить, потому что утверждение «arc4random — это ChaCha20» верно не везде. В OpenBSD RC4 заменён на ChaCha20 в версии 5.5, и man-страница прямо предупреждает, что имя историческое: «A good mnemonic is "A Replacement Call for Random"». Тот же код с периодической перевыработкой ключа лежит в libbsd и в libc FreeBSD. А вот в glibc эти функции появились только в версии 2.36 (август 2022 года) и устроены иначе: они «wrap getrandom and/or /dev/urandom to return high-quality randomness from the kernel», то есть никакой ChaCha20 в пользовательском процессе там нет — шифр работает уровнем ниже, в ядре. Разница видна, если спросить, что произойдёт при форке или при снепшоте виртуальной машины: реализация с собственным состоянием в процессе обязана это состояние чинить сама, реализация-обёртка получает поведение ядра бесплатно.

Ядро, кстати, использует ту же идею, что и AEAD-конструкция: блок гаммы с нулевым счётчиком порождает не выход, а новый ключ. В drivers/char/random.c это называется fast key erasure — первые 32 байта первого блока становятся новым ключом взамен старого, остальное отдаётся потребителю. Мотив другой (стойкость назад во времени, а не одноразовый MAC), механика та же.

Сводка решений

Источники

• RFC 8439 — ChaCha20 и Poly1305 для протоколов IETF (июнь 2018, отменяет RFC 7539): раскладка состояния и смена пропорции nonce и счётчика (§2.3), генерация одноразового ключа Poly1305 (§2.6), конструкция AEAD и вход тега (§2.8), лимит 256 ГБ и путь назад к 64-битному счётчику
• RFC 7539 — первая редакция того же документа (май 2015, IRTF/CFRG, информационный)
• RFC 7905 — шифрсьюты ChaCha20-Poly1305 для TLS и DTLS (июнь 2016): мотивация замены RC4 и CBC
• RFC 9846 — TLS 1.3 (июль 2026): обязательные и рекомендованные шифрсьюты (§9.1)
• RFC 9001 — QUIC поверх TLS: защита заголовка сырой ChaCha20 (§5.4.4)
• D. J. Bernstein, ChaCha, a variant of Salsa20 (28 января 2008) — четверть-раунд с двойным обновлением и оценка 12,5 против 8 бит (§2.2), смена вращений и оговорка о пренебрежимой разнице в стойкости, раскладка матрицы и порядок обхода (§3.2), таблица скоростей 1.3
• D. J. Bernstein, The Salsa20 family of stream ciphers (25 декабря 2007) — три операции ARX (§2.1), аргумент против умножения и пример PowerPC 7450 (§2.2), S-box и тайминг с цитатой про ошибку NIST (§2.3), отсутствие расписания ключа (§3.1)
• D. J. Bernstein, Cache-timing attacks on AES (14 апреля 2005) — та самая атака, из-за которой в ARX-шифрах нет таблиц подстановки
• D. J. Bernstein, The Poly1305-AES message-authentication code (29 марта 2005, FSE 2005) — формат ключа и обрезка, вычисление многочлена по модулю 2¹³⁰ − 5, ключевая гибкость как главная цель дизайна, граница 8⌈L/16⌉/2¹⁰⁶, обоснование выбора простого поля, заменяемость шифра, требование постоянного времени в финальной редукции и трудность constant-time AES
• Улучшенный криптоанализ ChaCha: bit puncturing — Флорес-Гутьеррес и Тодо, EUROCRYPT 2025: таблица 1 со сводкой атак, 2¹⁴⁸·² на семи раундах и 2²⁵⁰·² на семи с половиной
• Новый подход к PNB-атакам на ChaCha и Salsa — препринт (на дату сверки не опубликован): 2¹⁶⁷·⁹ на семи раундах при данных 2⁶⁸·⁹, сводная таблица с результатами ASIACRYPT 2025
• G. Procter, A Security Analysis of the Composition of ChaCha20 and Poly1305 — первое доказательство композиции, однопользовательское
• J. P. Degabriele, J. Govinden, F. Günther, K. G. Paterson, The Security of ChaCha20-Poly1305 in the Multi-user Setting — ACM CCS 2021: дефект в доказательстве Проктера, многопользовательская граница, независимость от объёма на пользователя, вклад обрезки в доминирующий член
• Terrapin Attack: Breaking SSH Channel Integrity By Sequence Number Manipulation — Боймер, Бринкман и Швенк, USENIX Security 2024: разбор режимов шифрования SSH по отдельности, различие между «уязвим» и «эксплуатируется», поведение CBC-EtM и CTR-EtM после вырезания префикса
• draft-ietf-sshm-chacha20-poly1305 — стандартизация конструкции OpenSSH (ревизия 04, 26 мая 2026, WG Last Call): независимость гаммы каждого пакета как причина чувствительности к Terrapin, требование обеих мер strict KEX, различие с оригинальным Poly1305-AES в переиспользовании r
• PROTOCOL.chacha20poly1305 — описание конструкции OpenSSH: два экземпляра шифра и зачем отдельный ключ для поля длины
• OpenSSH 6.5 release notes — появление chacha20-poly1305@openssh.com (январь 2014)
• Google Online Security Blog: Speeding up and strengthening HTTPS connections for Chrome on Android (24 апреля 2014) — кто и когда реализовал связку, мотив, замеры на Snapdragon S4 Pro, доля соединений к февралю 2014 года
• Call for Stream Cipher Primitives — призыв eSTREAM версии 1.3 (12 апреля 2005), профили и мотивация; страница проекта на дату сверки не отвечает, ссылка ведёт на архивную копию
• Timetable, eSTREAM — даты фаз проекта: начало третьей (финальной) фазы в апреле 2007 года; архивная копия
• The eSTREAM Portfolio (15 апреля 2008) — состав портфеля, Salsa20/12 в программном профиле и обоснование выбора двенадцати раундов; архивная копия по той же причине
• NESSIE: Portfolio of recommended cryptographic primitives (27 февраля 2003) — пустой портфель поточных шифров; архивная копия, сайт проекта не отвечает
• Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode — появление PCLMULQDQ в микроархитектуре Westmere (2010)
• WireGuard: Next Generation Kernel Network Tunnel — отказ от криптографической гибкости, состав примитивов
• libsodium: AEAD constructions — три варианта связки в одной библиотеке и таблица лимитов на каждый
• drivers/char/random.c — CRNG ядра Linux: ChaCha20 и fast key erasure; ChaCha20 появился в 4.8, BLAKE2s в извлечении — в 5.17
• fscrypt: Encryption modes and usage — Adiantum на XChaCha12 как ответ на отсутствие аппаратного AES
• arc4random(3), OpenBSD — замена RC4 на ChaCha20 в OpenBSD 5.5 и происхождение имени
• glibc, stdlib/arc4random.c и NEWS для 2.36 — реализация через getrandom(2), без собственного шифра

Связанные заметки

• AEAD: аутентифицированное шифрование, nonce и лимиты — интерфейс, в который эта связка вставляется: nonce, AAD, тег, лимиты, XChaCha20 и разбор Terrapin
• Обмен ключами: X25519, KEM, вывод ключей и привязка к транскрипту — откуда берутся 256 бит ключа, которые здесь считаются готовыми
• SSH углублённо — chacha20-poly1305@openssh.com в списке шифров OpenSSH и умолчания по обмену ключами
• OpenVPN против WireGuard — WireGuard как пример протокола с единственным AEAD и без согласования шифров
• AES-GCM против ChaCha20-Poly1305: как выбирать — что из разобранного здесь устройства решает при выборе между этой связкой и AES-GCM и почему ответ зависит от процессора
• Криптографические примитивы — план цикла статей — состав цикла, порядок статей и сквозные решения; там же запланирована статья про генерацию случайных чисел, которой принадлежит материал про CRNG ядра