dxdt.blog: занимательный интернет-журнал

Что ж, в Google хотя бы прямо признали, что проблема с тривиальными ключами была на их стороне тоже: требуемая базовая проверка для ECDSA вообще не выполнялась, поэтому тривиальные ключи от eMudhra прошли в программу и оставались незамеченными очень долго. Цитата:

However, prior to this incident, standard linting tools focused on algorithmic checks for RSA/DSA and blocklist checks for ECDSA; they had not implemented the Baby-Step Giant-Step (BSGS) discrete logarithm checks for small EC private scalars or pairwise EC key differences that paranoid_crypto includes.
(Тем не менее, до этого инцидента, типовые инструменты линтинга были сфокусированы на проверке RSA/DSA и списках заблокированных ключей для ECDSA; инструменты не поддерживали проверку методом малых и больших шагов для дискретного логарифма с малыми секретными скалярами или попарную разностную проверку, как это реализует paranoid_crypto.)

Пишут, что уже исправлено. Посмотрим.

Про реакцию вокруг истории Удостоверяющего Центра (УЦ) eMudhra, – его скомпрометированных, тривиальных ключей, – сейчас пишут много, и разное. Но образовался какой-то странный перекос. Вообще-то, в данной истории вылезла проблема вовсе не с одним конкретным УЦ, а с программой доверия в целом.

То есть, в доверенной, “коробочной” версии набора ключей, используемой браузерами и прочими системами, повсеместно, больше года находились ключи из пары, “секретная” часть которой не являлась секретной. Совсем не являлась секретной. Да, эти ключи предложили к размещению из одного конкретного УЦ. Однако полностью скомпрометирована оказалась вся программа: ключи туда приняли, они были подписаны другим УЦ, повсеместно включены автоматом в качестве доверенных. Действия одного УЦ – компрометация всей программы. Больше года – время реакции.

Не сомневайтесь, именно так и было: ключи промежуточных УЦ уже много лет, по условиям тех самых программ доверия браузеров, необходимо предъявлять сразу после выпуска, это строгое требование; на тривиальных ключах была поставлена кросс-подпись другого хорошо известного доверенного УЦ (Sectigo). Тут целый ряд авторитетных корпораций (Google, Mozilla, Microsoft, Apple) – законодатели мод и локомотивы разнообразных требований и рекомендаций, ограничивающих участие в программах доверия. Для безопасности.

Однако в программе явно “что-то пошло не так”. Поэтому реальная проблема – гораздо больше и основательнее.

Но почему-то заметают её под ковёр.

Кстати, насчёт доверенных меток логов Certificate Transparency и тривиальных ключей УЦ eMudhra: теперь соответствующих оконечных сертификатов в публичных CT-логах нашли уже больше 100 тысяч. Данные сертификаты (и пресертификаты), естественно, были выпущены после 20 октября (когда история с ключами стала совсем публичной). Понятно, что выпустить такой сертификат может всякий желающий. А пока операторы CT-логов не отозвали доверие – можно эти самые CT-логи данными сертификатами заливать.

Однако момент с успешным размещеннием в CT-логах подтверждает то, что получить SCT-метку, при желании, не составляло никакого труда. Да, отметка, скорее всего, появилась бы в CT-логах, но за этим не особенно-то следят даже операторы логов. Ну и более того – метки и сертификаты продолжают действовать в том ПО, настройки которого не поменялись. То есть, браузер, который не обновился, и который требует SCT-меток, будет признавать такой сертификат валидным; при прочих равных, конечно: должен быть период действия подходящий, не должен проверяться статус промежуточных сертификатов, должны в оконечном сертификате быть прописаны адреса точек проверки статуса – CRL и/или OCSP, – и т.д., и т.п., что, впрочем, ничуть не улучшает ситуацию.

Немного элементарных математических подробностей о “коротких ключах” УЦ eMudhra. Секретный ключ в ECDSA – это натуральное число в некотором заранее известном интервале, от 2 до N. Арифметика там довольно простая. Обозначим ключ d. Этот ключ d на техническом языке называют “секретным скаляром”, но, вообще говоря, от этого он не перестаёт быть натуральным числом (натуральные числа, если кто вдруг забыл, это “обычный” счёт: 1, 2, 3, 4, 5 и так “до самого большого числа”).

Открытый ключ в ECDSA получается из секретного умножением точки-генератора G на секретный скаляр; на техническом языке: [d]G. Точка-генератор – это точка, принадлежащая эллиптической кривой, используемой в данном наборе параметров криптосистемы. Умножение здесь вводится как повторное сложение: [2]G = G + G. Задача вычисления d по известной точке [d]G в произвольной группе точек кривой считается вычислительно сложной.

Минимальное значение 2 – оно очевидно из соображений умножения; понятно, 2 – это угадываемое число (см. важные детали ниже). Максимальное значение N – про него обычно пишут, что это “порядок группы точек”. Это, опять же, технический термин, который обозначает количество точек, потенциально доступных при операциях данной криптосистемы. Математически, эта самая группа точек так устроена, что всё её элементы образуются сложением генератора G с самим собой (сложение здесь – обозначение групповой операции; на техническом языке такая группа называется “циклической”). Это всё может показаться сложным, из-за терминов, но на практике это просто закольцованная цепочка значений (точек): складываете один элемент с самим собой – идёте последовательно по другим элементам, которые получаются в результате; на определённом шаге – процесс зацикливается, попадаете “в начало”, в нейтральный элемент (следом за которым будет опять генератор G, потому что G = G + 0). На практике нельзя брать именно порядок группы M в качестве максимального значения, берут, например, M-2, но это технические детали.

Точек кривой в практических криптосистемах ECDSA очень много. Их количество близко к разрядности записи, то есть, например, около 2^256. Очень много. Это определяющий момент: если бы точек было мало, то их можно было бы перебрать за обозримое время все, определив секретный скаляр. Да, практически так же, как в рассматриваемом случае нестойких ключей, но только универсальным образом.

Опять же, в упомянутом случае – набор точек называется P-384 (обычно говорят, что это “кривая P-384”), базовая разрядность – 384 бита. Точка кривой – это тоже два натуральных числа, из определённого интервала, связанных определённой формулой в пару координат. Точка-генератор G – всем известна, это открытый параметр криптосистемы. Обычно, хотя бы одна из координат G – это “большое” натуральное число. Но данные аспекты не относятся к обсуждаемой теме прямо. (Кстати, “большое” тут в кавычках, потому что с порядком в группе точек кривой всё не так просто, как хотелось бы.)

Соответственно, умножаем известную точку G на подбираемое значение d (это быстрая операция), получаем точку Q, представленную парой координат (натуральных чисел), сравниваем получившиеся координаты с атакуемым открытым ключом, если совпало – мы нашли секретный ключ, он равен d.

Итак, значение секретного ключа d, натуральное число, которое на практике должно лежать в некотором большом интервале. Казалось бы, идеально – равновероятное распределение по всем возможным значениям. Но тогда и угадываемое число 254 (например) оказывается столь же вероятным, как и все прочие, не так ли? Почему же подобные малые числа должны отбрасываться? Потому, что есть внешние допущения, связанные с битовым представлением. “Слишком много нулей” – это одна из сигнатур, связанных с дефектами в реализации алгоритмов. Такие сигнатуры накладываются на доступный интервал и оказывается, что атакующий может угадать 254 именно потому, что он будет перебирать варианты, в которых “слишком много нулей”. Если бы запись скаляра 254 не обладала отличительными чертами (все старшие биты – нуль), то и угадать его было бы не так легко. Представьте, что скаляры d “перетасовали” секретным идеальным способом и 254 перешло в какое-то произвольное значение – как теперь его найти? Только полным перебором.

Но если при выборе секретного ключа d заведомо берутся значения больше 255 (например), то что это означает? Ничего нового: теперь нужно перебирать 256, 257, 258 и т.д. То есть, тут важен не сам аспект, что “все старшие байты нулевые”, а наличие дополнительной информации о структуре распределения секретных ключей. Естественно, есть хорошо известные варианты, к которым и относится этот случай с последовательными нулевыми байтами. Это тривиальные ключи, подпадающие под универсальные ошибочные схемы. И эти случаи можно проверять без какой-то дополнительной информации. Но если, предположим, известно, что секретные ключи на сервере – это значение SHA-256 от текущего таймстемпа и IPv4-адреса сервера, то пространство перебора тоже не очень велико.

Напишу, пожалуй, несколько общих змечаний, касающихся компрометации ключей УЦ eMudhra.

Секретные ключи ECDSA, соответствующие нескольким промежуточным сертификатам данного УЦ, оказались угадываемыми. Буквально – их можно угадать, перебрав любым простым способом менее 255 натуральных чисел. Секретный ключ в ECDSA – это обычное натуральное число. При этом открытый ключ, соответствующий угадываемому секретному, на вид ничем не отличается от стойкого ключа. Потому что открытый ключ в ECDSA это точка на кривой (P-384, в данном случае), то есть, ещё пара натуральных чисел из определённого множества.

Однако утилиты, проверяющие нестойкие ключи, были и есть, но их, как мы видим, далеко не всегда используют (УЦ TLS из “коробочных версий” браузеров, в теории, должны использовать такие утилиты, но практика – далека от теории). Таким образом, ничего необычного в угадываемых ключах, вообще говоря, нет: ошибки, к сожалению, случаются, не следует переоценивать возможности “коробочного” TLS-окружения в вебе, как это принято делать.

Сертификаты промежуточных УЦ eMudhra с нестойкими ключами были опубликованы в прошлом году, такие сертификаты не являются секретными, а наоборот – о них УЦ должны заявлять. Но никто долгое время не замечал, что с ключами в данных сертификатах что-то не так (в том числе, и внутри УЦ никто не замечал). С одной стороны – это странно. С другой – мало кто следит за подобным, не удивляйтесь, такова реальность инфраструктуры TLS в вебе, тут уж ничего не поделать (зато есть квантовостойкие криптосистемы и хеш-деревья, да).

Угадываемый ключ означает, что можно взять открытый ключ из сертификата УЦ, найти за полсекунды секретный ключ, а потом начать самостоятельно выпускать доверенные TLS-сертификаты – то есть, сертификаты, в которые будет верить обычный браузер, в том числе, Chrome или “Яндекс.Браузер”; см. ниже про Certificate Transparency (CT). (И ещё тут всё будет работать, но за некоторыми исключениями: для ряда TLS-узлов может использоваться так называемый key pinning – то есть, привязка по ключам сервера или УЦ в цепочке, но это редкие детали.)

Если у вас есть доверенный сертификат, то можно активно перехватывать TLS-соединение: подменять практически любой HTTPS-узел, потому что дополнительной привязки ключей к именам, фактически, в вебе нет (DANE не используется, HPKP – запретили, и т.д.). Но для такого перехвата нужно контролировать канал. Расшифровать чужой, “не подменённый”, трафик доверенный сертификат не позволяет. Как только что отмечено, для особо важных узлов, типа некоторых сервисов Google, может использоваться упомянутый key pinning на уровне браузера, и тогда активная подмена сессии будет обнаружена браузером (и об этом может быть автоматически заявлено в Google, например).

В современных браузерах, в общем случае, доверие TLS-сертификату требует, чтобы в сертификате были доверенные SCT-метки, которые выдают операторы CT-логов. Метки подписаны. И подписаны они другими ключами, ключами оператора лога. Эти ключи – в другой цепочке доверия, которая никак к сертификатам УЦ не привязана. Поэтому компрометация ключа УЦ “от сертификатов” не позволяет подделать SCT-метку (для этого нужен секретный ключ лога; насколько “секретны” эти ключи – другой вопрос).

Однако в процессе выпуска сертификата можно предъявить соответствующий пресертификат оператору лога и получить доверенную SCT-метку, которую уже потом добавить в сам сертификат. Операторы логов принимают все подходящие по интервалу валидности сертификаты, выпущенные в цепочке от доверенных корней. Это доверие примерно эквивалентно доверию в браузере. Соответственно, если скомпрометирован ключ такого доверенного УЦ, то можно просто штатным образом предъявлять пресертификат с валидной подписью и получать SCT-метку (да, тут не оговорены разные возможные ограничения доступа к размещению пресертификатов, но это другая история; обычно, ограничений нет – главное, чтобы было доверие корню). Таким образом, получить SCT-метки и сделать сертификат доверенным с точки зрения браузера – возможно. Но останется отметка в CT-логе (в общем случае).

Следов сертификатов от скомпрометированных ключей eMudhra в CT-логах пока выявить не удалось. Это не означает, что сертификаты не были выпущены и использованы в приложениях, которые, в отличие от браузеров, не требуют SCT-меток при валидации. Таких приложений тоже немало: это разные утилиты для работы с вебом, почтовые системы и т.д. Кто, как и где использовал такие сертификаты, если использовал, – неизвестно. И это речь шла про TLS. Хуже всего, что есть сертификаты ключей подписи кода, и доверие там выстраивается похожим способом.

Ключи eMudhra были кросс-подписаны Sectigo. Это означает, что доверие распространялось от корней УЦ Sectigo. Кросс-подпись, в смысле доверия, зависит от ключа, а не от сертификата, так что с точки зрения компрометации – лучше не делает. Почему Sectigo не проверяли стойкость ключей, которые находятся в “их цепочке доверия”? Это тоже “большая загадка”. Но, опять же, таковы реалии инфраструктуры TLS-сертификатов в вебе.

Сертификаты скомпрометированных ключей можно и нужно отозвать. Это сделано. Проблема в том, что отзыв работает плохо, а CRL (списки отзыва) мало какие клиенты проверяют. Chrome – не проверяет. Однако в браузерах типа Chrome есть инструменты исключения доверия по отпечаткам ключей, новые отпечатки – распространяются с обновлением браузера. Именно так доверие данным ключам и было “снято” на днях. Однако тривиальный секретный ключ означает, что его, этот ключ, невозможно удержать в секрете.

Почему в браузеры (например) сразу не встроены подобные тривиальные ключи как недоверенные? Причин две. Первая – мало кто верил, что угадываемый ключ может быть использован полноценным УЦ, а каждая проверка по списку – это дополнительные такты процессора в программе, реализующей TLS-стек. Вторая причина – непонятно, на каком количестве ключей нужно остановиться: 128? 256? 2^16? И каждая итерация – довольно большие затраты вычислительного ресурса.

Вот.

Занятно, кстати, что секретные ключи скомпрометированного УЦ TLS eMudhra просто оказались угадываемыми – их значения лежали в интервале от 1 до 256:

The 8 impacted keys all used integers less than 256. (Все восемь затронутых ключей являлись целыми меньше 256.)

В УЦ, естественно, сертифицированные HSM и т.д., и т.п. Бывает. Байтовый скаляр можно угадать меньше чем за секунду, HSM “по FIPS” тут не мешает.

Недавно у меня студенты МГТУ делали курсовую работу по поиску секретных скаляров для ключей ECDSA на P-256 табличным методом: ну, что ж, вот вам очередной живой пример полезности данного метода (пусть и тривиального, с точки зрения теоретической математики).

В комментарии Beldmit прислал ссылку на описание того, что скомпрометированы ключи УЦ eMudhra, который находится в списках доверенных всех распространённых браузеров. В качестве доказательства там предъявлены подписи от этих ключей. Проблема большая: это означает, что тот, у кого есть секретные ключи, мог выпускать доверенные сертификаты для произвольных имён и выполнять атаку MITM. (Да, метки логов Certificate Transparency (SCT) – тоже можно было получать на такие сертификаты, это несложно.)

Кстати, что касается выгруженной OpenAI огромной пачки (больше 700 статей!) сгенерированных ИИ/LLM “решений важных математических задач”, которую уже называют “математическим” “помойкалипсисом” (Slopocalypse). В. И. Арнольд в статье “Что такое математика”, – которая выходила в виде книги, например, в 2002 году, – в подразделе, который называется “Математическое мракобесие против Абеля и Пуанкаре”, пересказывает определение математики “по Ю. И. Манину” (и Арнольд, и Манин – среди крупнейших математиков 20-го века). Пара цитат из статьи Арнольда:

“Математика, согласно Манину, – это отрасль лингвистики или филологии, занимающаяся преобразованием конечных цепочек символов некоторого конечного алфавита в другие такие цепочки при помощи конечного числа “грамматических” правил. Отличие от естественных языков, вроде китайского, английского или русского, состоит лишь в том, что в грамматике этого специального языка есть отсутствующие в живых языках правила (например, набор символов “1+2” можно заменить на символ “3”).”

“[…]ведь если в результате игры с символами и получается что-либо полезное, то это просто означает, что оно содержалось уже в исходных предпосылках”.

Дальше там речь про искусство “претендовать на открытия, которых не совершал” и т.д. Понятно, в этом есть существенная доля специального юмора и сарказма. И, понятно, в той статье и речи не идёт про ИИ-генерирование. Но всё же – удивительно, как хорошо подходит к текущей ситуации, заведённой OpenAI. Многие надеялись использовать новый мощный инструмент для того, чтобы с его помощью выпускать пачки собственных статей. Но сейчас всё выглядит так, что беспилотный бульдозер OpenAI запустили в самостоятельное приключение, и вот он уже едет сносить домики в университетских кампусах.

В Let’s Encrypt обещают с 10 февраля 2027 года начать выпускать TLS-сертификаты на 64 дня, вместо 90-дневных. Это как раз через четыре месяца (плюс-минус), то есть, как раз закончат действовать 90-дневные сертификаты, выпущенные в первой трети ноября 2026. Процесс сокращения должен быть незаметным, но нужно заранее озаботиться автоматизацией мониторинга, проверив, что он настроен (не)правильно.

Замечу, что dxdt.blog я некоторое время назад перевёл на “сверхкороткие” сертификаты со сроком действия 160 часов, так что dxdt.blog сокращение с 90 к 64 дням не коснётся: тут и так уже меньше недели. Естественно, заказ, получение и вывод сертификата на веб-сервер dxdt.blog – полностью автоматические. И за эти несколько месяцев заметная проблема была только один раз: очередной сертификат не выпустился потому, что, из-за неполадок с измерением времени на виртуальной машине, отвалился и не сработал корректно скрипт по таймеру Systemd; ну а тот момент, что сертификат не выпустился, был, к сожалению, “пойман” лишь спустя пару часов после того, как текущий сертификат завершился. Это, конечно, проблема коротких сертификатов: времени на реагирование очень мало, dxdt.blog я администрирую сам, мне вот времени и не хватило (ну и, опять же, как только УЦ перестанет выпускать сертификаты для каких-то доменов, соответствующие сайты очень быстро “потухнут” для браузеров – тут уж ничего не поделать, система выстраивается так, что сертификат будет токеном доступа). Но, в целом, пока что всё работает.

Монета в один доллар с изображением президента Трампа (действующего, между прочим) называется Semiquincentennial Dollar.

Здесь занимательно слово semiquincentennial – то есть, это полу- (semi) пяти- (quin) вековой (centennial) – “полупятивековой” доллар (не только с Трампом, не только доллар, хотя доллар с Трампом – максимально странный).

“Полупятивековой” – это половина от 500 лет. Довольно забавный способ именования, конечно. На горизонте пяти сотен лет – довольно странно отмечать половину отдельным словом, тем более, когда это история независимости от Англии. Независимость от королевства, заметьте, но на юбилейной монете изображение действующего президента, что не совсем типично для США (а в Англии – на монетах король).

И ведь можно было бы назвать “четвертьтысячелетний” – quartamillenium, а ещё лучше – quartamilliarum (тут даже немного повеяло игровой вселенной Warhammer, которая про Великобританию, впрочем).

Понятно, что латинская классическая форма, конечно, это никакой не “миллениум”, а просто ducenti quinquaginta anni – двести пятьдесят лет.

Кто бы сомневался, но, как и следовало ожидать, в октябрьском обновлении “Коуровской тетради” много задач, явно отмеченных как решённые “с использованием AI”. Есть там среди многих и решение для задачи 11.115 (“unverified AI solution”), про которую я писал: точно тот же контрпример, что упоминается и на dxdt.blog, но в записке про то, как я проверял возможности Claude Fable 5/Opus 5 по конструированию контрпримеров сразу с доказательством на Lean. У меня используется квадрат элемента группы, а в опубликованном контрпримере (M. Kinyon, J. Urban) – указана степень m≥2 – понятно, что m == 2 подходит. Цитата из моей записки:

[…] если кому-то интересны супертехнические подробности, то вот: построим подгруппу на словах с чётными и нечётными степенями (это отображение в Z/2Z), и подгруппу на соотношениях с a^2.

Надо заметить, что формулировку контрпримера, найденного Claude, я вводил и в ChatGPT. Я, конечно, найденный LLM контрпример никуда не отправлял (ну, кроме ChatGPT), так что понять, откуда результат взялся в выдаче LLM, как там пересеклись входные “промпты” от разных пользователей, – могут только операторы этих LLM. Но вот в том, что возможно найти контрпримеры для огромного количества старых задач с помощью LLM, при участии большого количества пользователей, задающих направления, – в этом я не сомневаюсь, а про “Коуровскую тетерадь”, как источник таких задач для LLM, я писал ещё в 2024 году (но это совершенно очевидный для специалиста выбор). Вот, кто-то занялся вплотную. Собственно, именно этот момент, взятый по модулю способа публикации (ну, представьте, что решения произвольно публикуются на персональных сайтах), и беспокоит сообщество.