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

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

Чуть менее очевидный эффект времени состоит в том, что каждой криптографической операции, связанной с использованием секретного ключа, обычно соспоставлено некоторое ожидаемое “время стойкости”: то есть, предположим, есть секретный ключ протокола Диффи-Хеллмана, он использовался один раз, соответствующий открытый параметр известен третьей стороне, примем, что эта третья сторона может вычислить секретный ключ по открытому за сто лет (тут это условное значение, но есть и куда более строгие оценки стойкости). Параметр вполне себе практический: например, уязвимые реализации ECDSA могут позволять вычислить секретный ключ по нескольким значениям подписи, но чем меньше значений – тем больше вариантов перебирать. И всякий процесс перебора тут эквивалентен указанию времени. Более того, время возникает и в момент сбора значений подписей, которые нужны для успешного подбора: предположим, что уязвимая реализация выпускает одну подпись в месяц, а собрать нужно две сотни значений.

Всё то же самое применимо и к симметричным алгоритмам: можно построить некоторое ожидание стойкости – например, 64-битный симметричный ключ для какого-то алгоритма можно считать стойким в течение недели. Опять же, условная оценка – многое как раз зависит от алгоритма, от доступных оптимизаций. 2^64 это не так мало, как может показаться: представьте, что специализированный вычислитель проверяет 1000 значений за один такт и работает на тактовой частоте 5 ГГц (зедесь и 1000, и гигагерцы – это всё время), тогда для перебора 2^64 значений потребуется полтора месяца. (А если проверка одного значения занимает много тактов, то и полный перебор сильно затянется для 2^64.)

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

В качестве илллюстрации годится хрестоматийный случай, с которого сейчас начинаются курсы по разработке прикладных криптографических программ – утечка секретов при неверной реализации операции сравнения битовых (или байтовых) строк, когда сравнение прекращается в момент обнаружения первого расхождения. Здесь время (точнее – количество тактов), требуемое для вывода результата сравнения с секретным значением, зависит от входных данных. Если атакующая сторона может направлять произвольные данные в систему и измерять время обработки, то атакующая сторона может раскрыть секрет. Пусть секрет имеет длину 128 бит. Может показаться, что для полного перебора с гарантированным нахождением секрета нужно выполнить 2^128 запросов, то есть, потратить очень много времени. Но если реализация уязвима, имеет утчеки “по каналам времени” исполнения с разрешением в один бит, то перебрать гарантированно 128 бит побитно – можно за 128 запросов.

Но всё это – время, и в случае утечек оно играет даже две роли одновременно: утечка “по каналу времени” позволяет сократить время перебора.

В продолжение предыдущей записки, про LLM и математические задачи. Google пока тоже не публикует технических подробностей о том, кто там и как перебирал и форматировал решения задач Международной математической олимпиады, чтобы получилась “золотая медаль”, однако, в отличие от OpenAI, в официальном новостном сообщении, есть, хотя бы, небольшие и довольно занятные намёки.

Во-первых, пишут, что использовалась некоторая “параллельная обработка” (parallel thinking) внутри модели, но, насколько можно понять, для подбора готовых решений. Цитата: “Эта конфигурация позволяет модели одновременно рассматривать и комбинировать многие возможные решения до выдачи окончательного ответа, вместо того, чтобы действовать по единственной, линейной цепочке рассуждений”. (This setup enables the model to simultaneously explore and combine multiple possible solutions before giving a final answer, rather than pursuing a single, linear chain of thought.)

Во-вторых, для получения решений провели “дополнительное обучение”, подстроенное для подходящих типов задач, и ввели инструкции, подобранные конкретно под задачи ММО (видимо, этого года – иначе нет смысла уточнять дважды). Цитата: “Мы также предоставили Gemini доступ к корпусу специально отобранных высококачественных решений математических задач и добавили в инструкции некоторые подсказки и советы общего характера о том, как решать задачи ММО”. (We also provided Gemini with access to a curated corpus of high-quality solutions to mathematics problems, and added some general hints and tips on how to approach IMO problems to its instructions.) Это самый интересный кусок из официального сообщения. Его можно понимать и так, что добавили базу с содержанием решений задач именно такого типа, как потом спрашивали, а позже ввели “советы” с ответами конкретных задач. А можно понять и так, что в процессе “настройки” корректировали входные данные, направляя вывод генерации к текстам верных доказательств (перечитайте в исходнике: a curated corpus of high-quality solutions).

Проще говоря, подробного описания процесса нет, а так – это уж слишком сильно напоминает улучшенный вариант традиционного уже упражения “ИИ сдаёт ЕГЭ” – выбираем тот сгенерированный текст из десятков выданных LLM вариантов, который набирает больше баллов.

В продолжение предыдущей записки, про решение задач с Международной олимпиады средствами LLM: самое забавное, что, например, решение для первой задачи ММО-2025, которое сгенерировала “экспериментальная модель”, почему-то содержит ответ в самом начале – то есть, буквально, написано: смысл решения – доказать, что правильный ответ – правильный. Вот этот фрагмент, в виде скриншота (потому что там нужно “рендерить” LaTeX и Markdown):

Далее там идёт очень большой и не очень внятный сгенерированный текст доказательства, перегруженный отступлениями, понимать который довольно сложно, но не потому, что задача сложная, а потому, что много лишнего в “рассуждениях”. Сомневаюсь, что полезно делать его полный разбор. (Нет, сама исходная задача не требует таких больших объёмов для записи решения.)

Небольшое техническое пояснение: первая задача IMO 2025 это комбинаторная геометрия, нужно посчитать возможные варианты покрытия целых точек на решётке прямыми – это один из самых популяных “сеттингов” для олимпиадных задач; соответственно, набор возможных вариантов – {0, 1, 3} – появляется в процессе решения, поскольку составляет основную содержательную часть этого решения: надо понять, что других чисел (это количество подходящих прямых) там не может появиться; и то, что отсутствует 2, это, вообще говоря, не самый тривиальный момент (но и не самый сложный). Так что то, что решение от LLM OpenAI построено на доказательстве верности состава ответа, без указания на то, как этот состав получен, – почему, хотя бы, там не {1, 2, 3}, – выглядит весьма странно.

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

Слушать эфир можно как каким-то одним из имеющихся радиотрактов (WiFi, Bluetooth/BLE, GNSS, GSM и т.д.) или всеми сразу. Современные радиомодули очень чувствительные и избирательные. Если использовать непосредственно функции прошивки радиомодуля, то, вообще говоря, принимать можно далеко не только “логический WiFi”, но и разнообразные другие сигналы, в том числе, сигналы радаров, спутниковых передачиков (подтверждается Starlink) и т.д., и т.п. Да, приниматься могут быть гармоники побочных утечек, но для данной задачи это не важно. Если сомневаетесь, то вспомните историю появления такого направления, как RTL-SDR – там аппаратной основной вообще послужил бюджетный ТВ-тюнер. (Замечу, в скобках, что даже если в пользовательском интерфейсе смартфона указано, что соответствующие радиомодули “отключены”, это не означает, что они реально отключены – реально отключить можно было бы только в специальной архитектуре, аппаратной кнопкой, но таким практически никто не пользуется, да и кнопка не даёт полной гарантии.)

Устройства-наблюдатели по данной теме больше ничего не делают, поэтому их активность снаружи выглядит вполне себе обычно (это, собственно, просто логика протоколов класса LTE). Однако собранные сведения из эфира принимает какое-нибудь внешнее устройство-монитор, специально предназначенное для этого. Принимает тогда, когда удалось что-то принять. Монитором может быть и другой, скомпрометированный, смартфон, и штатно подготовленный приёмник “базовой станции” с нужной прошивкой – не так важно, но возможности, конечно, различаются. Монитор знает собственное местоположение, может знать направление, с которого получен очередной блок данных (это больше относится к “базовым станциям”). Полученные от наблюдателей данные монитор передаёт на удалённый центральный сервер. Этот сервер агрегирует данные от многих мониторов.

Теперь на сервере, зная возможности приёма и принципы распространения радиоволн, можно вычислять где какие метки в эфире были видны – то есть, выполнять геолокацию идентификаторов. Устройства-наблюдатели ведь будут видеть и друг друга, и базовые станции сетей мобильной связи. Сопоставляя данные от разных мониторов, географические координаты которых известны точно, получится определить, где находились и устройства-наблюдатели, и источники радиосигналов, которые эти наблюдатели обнаружили в эфире. Метод основан на переборе конфигураций, в которых многие наблюдатели могли принимать одни и те же сигналы, чтобы в итоге получилась такая же картина, как та, что поступила с нескольких мониторов.

Да, такая задача сопоставления меток времени и возможностей приёма – вычислительно сложная, но и компьютеры сейчас мощные. Алгоритмы вычисления идентификаторов сигналов (специализированные “хеш-функции”, упомянутые в самом начале) должны быть так устроены, чтобы близкие по физическим характеристикам радиосигналы получали близкие по значению идентификаторы. Это и позволит найти следы одного и того же источника в массивах идентификаторов, полученных от разных мониторов. Результат не самый точный, но, во-первых, чем больше источников данных, тем выше точность; во-вторых, других вариантов сбора данных может и не быть, однако если они есть, то накопленный по описанной схеме массив идентификаторов позволяет эти другие данные подтвердить или опровергнуть с очень высокой степенью достоверности.

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

Попалось тут снова утверждение, что, мол, если количество уязвимостей в библиотеках с открытым исходным кодом выросло в два раза, а количество самих библиотек за тот же период – только на четверть, то это означает, что количество “угроз” растёт в четыре раза быстрее, чем “объём компонент” с открытым кодом.

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

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

Естественно, подобная статистика уязвимостей в ПО ведётся по обнаруженным уязвимостям, о которых опубликована информация. То, что уязвимость не обнаружена, не означает, что в коде нет уязвимостей. А обнаружение уязвимости – не гарантирует, что их в исследуемом коде много. Именно поэтому угрозы, как таковые, нельзя расставлять по обнаруженным уязвимостям. Но, конечно, в списке должны быть две-три угрозы, связанные с возможностью эксплуатации известных уязвимостей при помощи автоматических инструментов – это достаточно очевидно. Вот только количество этих угроз не растёт вместе с ростом публикаций CVE – максимум, угрозы эти можно разделить по библиотекам, то есть, максимум на четверть они вырастут, если все новые библиотеки строго тянуть в свою модель угроз (но зачем? вопрос риторический).

Во-первых, вот уже лет пять как начали присваивать статус “признанной уязвимости”, “с кодом CVE”, даже самым мелким обнаруженным дефектам, практическое значение которых при проведении атак довольно сомнительно.

Во-вторых, сейчас сам поиск уязвимостей стал настолько массовым, что, действительно, находить их стали больше, в том числе, существенных (это и капитан Очевидность подтверждает). Рост интереса исследователей – вот единственный параметр, о котором можно судить, косвенно, по количеству публикаций уязвимостей. Да, находят весьма и весьма существенные уязвимости, которым десять и более лет – внимание, вопрос: когда эти уязвимости преобразовались в угрозы, если преобразовались? В момент внесения в код, или когда об этом в газетах написали, десять лет спустя?

В-третьих, уязвимости сильно различаются по тому контексту, который их вообще делает уязвимостями и создаёт возможность установления связи с угрозами (угрозы, на минуточку, и определяются-то не по уязвимостям – см. выше). Эффект от одной и той же “уязвимости с CVE” может сильно различаться в зависимости от модели угроз (учитывается ли подключение системы к внешним вычислительным сетям; учитывается ли наличие USB-портов и возможность физического доступа, и т.д.).

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

P.S. Пожалуй, тут нужно привести конкретный пример. Представьте, что у вас определена следующая внутренняя угроза: “Локальный непривилегированный пользователь через уязвимость библиотеки в системном сервисе повышает права своего аккаунта и удаляет все защищаемые данные”. Зависит ли определение (хотя бы описание) этой угрозы от того, что в утилите sudo найдена уязвимость, позволяющая поднять права до суперпользователя? Нет, не зависит, хоть в определении угрозы и используется слово “уязвимость” – рассматривать такую угрозу нужно даже в том случае, если sudo вообще нет в системе. Поэтому про sudo в определении угрозы ничего нет, определение не зависит от конкретных уязвимостей, так как они рассматриваются в самом общем смысле. Появилась ли эта угроза лишь после того, как опубликовали данные об уязвимости в sudo и демонстратор (PoC)? Нет, конечно – угроза была и раньше. Появление информации о новой уязвимости (плюс один к количеству индексов в базе сканера), тут никак не повлияло на количество угроз.

Почему-то очередную “кросс-протокольную” атаку под названием Opossum стали в новостных сообщениях называть “атакой на TLS”. Но к TLS эта атака имеет примерно такое же отношение, как автомобиль – к дороге. Причём, сами авторы не утверждают, что это атака на TLS – на сайте она классифицирована как “кросс-протокольная атака десинхронизации на прикладном уровне”, а применима к прикладным протоколам, использующим TLS и напрямую, и “приспособительно” (opportunistic) на одном и том же логическом узле.

О чём тут идёт речь? Существуют протоколы обмена командами и данным, в которых использование TLS встроено в схему протокола. То есть, на верхнем логическом уровне, не сам обмен протокола полностью и прозрачно завернут в TLS (как HTTP в HTTPS, скажем), а TLS можно включить, при наличии возможности, уже в контексте самого протокола – пример: SMTP + STARTTLS. То есть, сеанс в рамках атакуемого протокола обязательно начинается в открытом и незащищённом варианте. Это позволяет атакующему подменить начальные сообщения той или иной стороны, а потом переключить трафик на использование TLS: либо штатными средствами протокола, либо – перенаправив трафик на другой номер порта. Атакующий при этом должен активно перехватывать сетевое соединение, подменять пакеты и прозрачно перенаправлять трафик на разные номера портов. (В исходной публикации, для одного из сценариев, ещё и требуют выполнения атакующей стороной произвольного кода в контексте веб-страницы внутри браузера.)

Так, механизм STARTTLS для SMTP – тут сервер может предложить поддержку TLS в самом начале SMTP-сессии, а клиент, если он поддерживает TLS, может тут же начать переход на защищённое соединение, просигнализировав об этом серверу. Если переход на TLS произошёл, то SMTP-сессия начинается, фактически, заново – пусть и в том же сокете, но уже внутри TLS. Но для SMTP есть и вариант с прямым TLS-подключением, то есть, сразу по TLS на другом выделенном номере порта (например, 587, а не 25). Для осуществления атаки требуется, чтобы на сервере были доступны оба способа подключения – смысл и состоит в “перекидывании” сессии между открытым соединением и подставным TLS-соединением.

Атака Opossum для SMTP предлагает атакующему возможность обмануть клиентскую программу, которая пытается подключиться с использованием STARTTLS: атакующий перехватывает соединение этой программы и отвечает вместо сервера, отправляя собственное серверное SMTP-приветствие и опцию, указывающую на STARTTLS; далее, как только клиентская программа начнёт инициировать TLS-соединение, атакующий перенаправляет начальное TLS-сообщение клиента на выделенный для TLS номер порта легитимного сервера; сервер считает, что это просто прямое подключение TLS и обрабатывает его обычным образом. Получается, что клиент прочитал подставное SMTP-приветствие и подставной список SMTP-опций, а потом начал SMTP-сессию через TLS, что для сервера выглядит обычной новой сессией. Таким образом, контекст на сервере как бы отличается от контекста на клиенте. Насколько это критично с практической точки зрения, особенно, на фоне того, что атакующий мог вообще скрыть поддержку TLS сервером, – отдельный вопрос. Но никакой атаки на TLS тут нет, TLS сработал так, как и планировалось, однако шаги штатного протокола на стороне клиента и на стороне сервера теперь не синхронизированы, из-за вмешательства атакующего – запросы и ответы переставлены на полуход. В публикации Opossum это, что логично, так и называется: “десинхронизация прикладного уровня”.

(Иллюстрация из исходной работы.)

Как ни странно, но TLS в “приспособительном” режиме возможен, – в теории, – и для HTTP. Этот вариант, впрочем, практически не встречается на веб-серверах: смысл для HTTP – тёмен, а настраивать нужно отдельно. Для случая HTTP последовательность данной атаки другая: атакующий модифицирует запросы, ответы и задерживает TLS-трафик так, что внутри TLS-сеанса оказывается ответ сервера не на легитимный запрос клиента, а на предыдущий запрос, поступивший к серверу от атакующего в открытом виде. TLS-опять же, атака не касается. Но, как и отмечено в исходной работе, все перечисленные атаки возможны потому, что TLS не предоставляет способа аутентифицировать состояние внешнего протокола на стороне сервера и клиента, а аутентифицирует только имена и адреса. Это так. Однако подобная расширенная аутентификация и не входит в модель TLS: несмотря на наличие расширений типа ALPN, TLS работает только на своём уровне. (Кстати, на ALPN описание атаки Opossum как раз ссылается: с ALPN связана вспомогательная часть и предыдущая атака по теме.)

ChatGPT, к сожалению, продолжает зацикливаться странным образом. Мне вот выдало зацикленный код LaTeX, в весьма простом случае – см. скриншот.

“\boxed{…” – выводилось в браузер несколько минут, но ничего кроме “\boxed{…” не появилось, так что пришлось остановить, переключив чат.

Опубликовал на “Хабре” статью о шумеро-вавилонской шестидесятеричной системе счисления и её арифметических преимуществах. В тексте, естественно, много раз используются клинописные цифры. И вот в комментарии к статье написали, что эти цифры видны не всем – кому-то браузер их не показывает. Что, конечно, не очень-то хорошо, так как сильно затрудняет понимание текста, который и так-то не самый простой. Клинописные знаки, – в том числе, цифры, нужные для статьи, – давно есть в Unicode. Не добавили ещё только самый древний вариант (“протоклинопись”), упомянутый в предыдущей записке. Но поддерживают соответствующий блок, конечно, далеко не все шрифты.

Я предполагал, что такое может быть, но решил попробовать – у меня-то шрифты есть и цифры отображаются. Вообще, основные опасения касались того, что веб-интерфейс “Хабра” не пропустит “клинья” – но в этой части всё как раз сработало нормально. Чтобы увеличить шансы на корректную обработку, я все клинописные цифры обернул в LaTeX-выражения. “Хабр” такие выражения “рендерит” отдельно в SVG. Но, понятно, в SVG указан обычный текстовый блок – <text></text>, без всяких дополнительных параметров и шрифтов, которые могли бы помочь в отображении, так что – не сработало тоже, к сожалению.

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

Dual EC DRBG (“Сдвоенный детерминированный генератор случайных битов на эллиптической кривой”) – нашумевшая схема генератора псевдослучайных чисел, в которой встроен (потенциальный) математический бэкдор. Несмотря на сразу же возникшие подозрения о бэкдоре, эта схема была без проблем стандартизована NIST в 2006-2007 годах и достаточно широко использовалась. Соответствующий стандарт позже официально отозван NIST.

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

Важнейшей особенностью криптографических генераторов (псевдо)случайных чисел является то, что выдача генератора детерминирована внутри – то есть, выдаваемые значения определяются внутренним состоянием (пояснение от 28/01/26: это только для внешнего наблюдателя генерируемая последовательность выглядит как случайная). Именно этот аспект служит фундаментом для построения бекдора в Dual EC DRBG. Криптографические генераторы псевдослучайных чисел имеют важнейшее значение не только для теоретической, но и для прикладной криптографии – это краеугольный камень всех практических систем криптографической защиты.

Несмотря на то, что с точки зрения теории криптографии схема, о которой идёт речь, предоставляет потенциальный бэкдор, её свойства можно трактовать и как инструмент “депонирования” ключей – то есть, при реализации конкретного экземпляра генератора выбираются такие параметры, что уполномоченная сторона может его “взламывать”. Однако уже сам факт того, что возможно провести в статус стандарта такую схему генератора, которая содержит механизм построения бэкдора на уровне алгоритма и описание этого бэкдора опубликовано на момент стандартизации, имеет большое историческое значение. Ещё более показательна и интересна сугубо математическая часть данного бэкдора. Настоящая статья посвящена именно математике бэкдора и в деталях объясняет то, почему он работает.

По сути, бэкдор в Dual_EC_DRBG – это реализация протокола Диффи-Хеллмана (DH) на эллиптической кривой: секретный ключ находится у стороны, контролирующей бэкдор через параметры протокола, что позволяет этой стороне получать внутреннее состояние генератора псевдослучайных чисел, наблюдая его выдачу. Знание внутреннего состояния приводит к раскрытию всей последующей выдачи генератора. При этом, математически, пользователь Dual EC DRBG неявно выполняет обмен DH с контролирующей параметры генератора стороной. Это важное свойство штатных схем построения “надёжных бэкдоров”: доступ к бэкдору должен быть только у той сторны, которая знает секретный параметр – секретный ключ. Есть и другое важное свойство: если секретный параметр не был раскрыт, то строго доказать, что бэкдор действительно встроен в конкретную реализацию – нельзя. Это не отменяет возможности тсрогого описания для механизма такого бэкдора.

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

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

На схеме: S_n – внутренние состояния генератора; φ() – функция, преобразующая состояние S_n в S_n+1; ξ() – функция, преобразующая состояние S_n в выдачу генератора B_n на данном шаге. Биты пошаговой выдачи B_n могут конкатенироваться для получения псевдослучайной последовательности нужной длины (на схеме: RND[…]) – это типовой способ прикладного использования генератора.

Криптографические генераторы псевдослучайных чисел, помимо общих “статистических” требований к неотличимости выдачи от случайной, имеют ряд особенностей. Прежде всего – выдача должна быть необратимой. А именно: состояния S_n являются секретными параметрами, поскольку позволяют раскрыть будущую выдачу генератора. При этом выдача генератора (B_n) на каждом шаге – публична. Из этого нетрудно сделать вывод, что функции φ и ξ должны быть односторонними (однонаправленными – по значению сложно определить аргумент): если это не так, то по публично доступным данным (B_n) легко вычислить состояние генератора. В чём и состоит логический смысл описываемого бэкдора.

Почему односторонней должна быть и функция φ, которая переводит текущее внутреннее состояние в следующее? Это нужно для того, чтобы по утекшей информации о внутреннем состоянии на каком-то шаге было вычислительно сложно восстановить предыдущую выдачу генератора. Одно из базовых требований к криптографически стойким генераторам псевдослучайных чисел состоит в минимизации возможностей по раскрытию данных. Например, если есть бэкдор, позволяющий обратить ξ, то, при условии обратимости φ, взяв любую точку можно раскрыть сколько угодно данных – и предыдущие, и следующие. При этом обратимость ξ может являться следствием не бэкдора, а обычной уязвимости, в том числе, уязвимости реализации алгоритма. Предположим, эта уязвимость ξ срабатывает лишь на каких-от редких данных: соответственно, если подобрать такие данные удалось, но φ осталась необратимой, атакующий сможет вычислить только следующие состояния генератора и все предыдущие секреты останутся защищены.

Математической особенностью описываемого бэкдора является то, что он вовсе и не позволяет обратить функции ξ и φ – они остаются односторонними, но бэкдор открывает возможность простого вычисления следующего внутреннего состояния генератора по известной выдаче ξ. Это возможно потому, что алгоритм содержит дополнительную структуру, связывающую функции ξ и φ.

Псевдослучайная выдача в криптографических протоколах постоянно используется в открытом виде. Например, в открытом виде передаются векторы инициализации для схем зашифрования (GCM и пр.), псевдослучайные векторы в сообщениях TLS (поля ClientRandom и ServerRandom) и др. Поэтому нетрудно извлечь значения из трафика, сопоставить их с выдачей генератора псевдослучайных чисел, раскрыть внутреннее состояние генератора и получить последующие биты выдачи, которые, например, были использованы тем же приложением для получения секретных ключей шифров, защищающих трафик – это позволит восстановить секретные ключи и расшифровать трафик в пассивном режиме.

Dual EC DRBG работает на эллиптической кривой (над конечным полем), а в качестве односторонних функций использует умножение точки эллиптической кривой на скаляр: x∘P. Далее умножение на скаляр обозначается “блобом” (∘). Стойкость к обращению здесь основана на задаче дискретного логарифмирования: то есть, по значению Q = x∘P – вычислительно трудно найти x.

Вспомним, что умножение на скаляр – обычное для эллиптической криптографии последовательное сложение точки кривой с самой собой. Сложение – операция, которая введена на точках кривой. А именно: точкой кривой называется пара (X, Y) значений “координат”, соответствующих уравнению кривой. Здесь X и Y – это элементы подлежащего конечного поля, которое входит в параметры криптосистемы. В данном конкретном случае (например, для кривой P-256) используемое конечное поле – это вычеты, то есть “остатки” по модулю простого числа. Сложение точек P + Q = R позволяет по паре координат точки Q (X_Q, Y_Q) и паре координат точки P (X_P, Y_P) Получить координату точки R (X_R, Y_R). Скаляр – это целое число. Умножение на скаляр 3 означает, что точка складывается сама с сбой в трёх экземплярах: 3∘P = P + P + P (плюс – это сложение точек). По такому сложению точки всякой эллиптической кривой всегда образуют группу (по определению эллиптической кривой).

В алгоритме Dual EC DRBG используется две точки кривой: P и Q. Точка P – задаёт последовательность внутренних состояний. Внутреннее состояние S_n в Dual EC DRBG – целое число, которое соответствует координате X точки кривой, полученной умножением P на значение предыдущего состояния, как на скаляр. Вторая точка, Q – задаёт “ответвления”, то есть, выдачу генератора по каждому из состояний, и используется в качестве основания на каждом шаге. Ниже представлена упрощённая схема Dual EC DRBG.

На этой схеме: S_n – внутреннее состояние; для получения следующего состояния из текущего – точка P умножается на значение состояния (скаляр: S_n∘P), а координата X получившейся точки – выводится в качестве нового состояния генератора; для вывода случайных значений – вторая точка, то есть – точка Q, умножается на состояние (S_n∘Q) и выводится координата X получившейся точки. То есть, используется две одинаковых функции с разным основанием: P и Q. Раз стойкость этих функций основана на дискретном логарифмировании, то они односторонние, как и требуется.

Математический смысл бэкдора не нарушает стойкость конкретных операций с точками P и Q, он несколько хитрее и строится на в соотношении между точками P и Q. Допустим, атакующей стороне известно такое значение δ, что P = δ∘Q. Выдача генератора – это X-координата точки S_n∘Q. Атакующий находит подходящую Y-координату, подставив значение в уравнение кривой (точек с подходящими координатами будет две, алгоритм знак координаты Y не различает, но выбор точки, очевидно, не представляет труда). Таким образом атакующий легко восстанавливает точку кривой, подходящую для выдачи генератора. Далее – умножаем на δ.

δ∘(S_n∘Q) = S_n∘(δ∘Q) = S_n∘P   (1)

Рассмотрим формулу (1) подробнее. Почему она работает? Потому что скаляры – это целые числа. Из-за коммутативности группы точек кривой к скалярам применимы арифметические свойства целых чисел. В алгебре такая конструкция называется ℤ-модулем. Всякая коммутативная группа является ℤ-модулем. (Некоторые алгебраисты из-за этого даже не считают коммутативные группы “настоящими” группами.) Применительно к эллиптической кривой: 3∘P = P + P + P, а 5∘P = P + P + P + P + P. Но тогда (3+2)∘P = 5∘P = P + P + P + P + P, что следует из свойств групповой операции – просто поставим скобки: (P + P) + (P + P + P), получив, таким образом, две точки (P + P) = 2∘P и (P + P + P) = 3∘P. 3∘P + 2∘P = 5∘P. Обратите внимание, что здесь знак “плюс” используется в двух значениях: и для обозначения сложения точек кривой, и для обозначения привычного сложения в целых числах (3+2). А раз схема работает для сложения целых чисел, то она обязательно работает и для умножения целых чисел, потому что умножение в целых числах можно построить через сложение (собственно, при корректном преобразовании 0 и 1, сложение и умножение в целых числах просто могут быть переведены одно в другое, как операции). Но тогда и (3*2)∘P = (P + P) + (P + P) + (P + P) = 3∘(2∘P) = 6∘P. Что и используется в формуле (1), вместе с коммутативностью умножения в целых числах: 2 * 3 = 3 * 2.

Таким образом, атакующая сторона, которая знает секретный скаляр δ, получила значение следующего состояния генератора, вычислив Χ-координату точки S_n∘P (см. схему). Формула (1) вообще очень похожа на реализацию протокола Диффи-Хеллмана (DH) на эллиптической кривой. То есть, пользователь генератора псведослучайных чисел, можно сказать, обменялся с атакующей стороной открытыми параметрами Диффи-Хеллмана. А именно: открытый параметр атакующей стороны, статический ключ, зашит в константы протокола – P = δ∘Q, где секретный ключ – δ; открытый параметр DH пользователя – это динамическая выдача основного алгоритма – S_n∘Q, где секретный ключ S_n. “Открытые параметры DH” пользователя атакующая сторона наблюдает в трафике. Важное отличие от практического DH состоит в том, что “общий секрет” тут не должен становиться “общим” с атакующей стороной.

Итак, для внедрения бэкдора нужно выбрать такие P и Q, что P = δ∘Q. Полученные точки – это параметры конкретной реализации алгоритма, но они могут быть закреплены в стандарте (что и было сделано). Но в спецификации Dual EC DRBG для кривой P-256 в качестве точки P строго указана базовая точка группы кривой, которая используется в спецификации P-256. То есть, произвольно выбрать P нельзя. Оказывается, в том случае, если одна из точек P или Q заранее строго задана, то определить нужное значение δ можно при помощи вычисления мультипликативного обратного по модулю порядка группы точек. Важно, чтобы порядок был простым числом. Но это стандартная практика для прикладной криптографии. Например, для кривой P-256 – соответствующий порядок простой.

Чтобы получить бэкдор, нужно определить δ из P = δ∘Q. Может показаться, что если точка P зафиксирована, – соответственно, выбрать эту точку умножением какой-то точки Q на произвольный скаляр нельзя, – то требуется решить сложную задачу отыскания дискретного логарифма. Но это не так, поскольку мы всё равно можем выбрать произвольную точку Q. Чтобы согласовать точки, возьмём произвольное значение ε в интервале от 2 до порядка группы, генерируемой P, а потом возьмём δ = ε^(-1) по модулю порядка. Пусть порядок P – то есть, количество точек в используемой группе, – это простое число n. Тогда нужно найти ε * δ = 1 (mod n). (Например, 2 – обратный по умножению элемент к 4 по модулю 7, так как 2 * 4 = 1 (mod 7).) Задача нахождения мультипликативного обратного по модулю простого числа здесь вычислительно несложная. Определив δ = ε^(-1), в качестве точки Q выберем ε∘P. Тогда: δ∘Q = δ∘(ε∘P) = (ε^(-1)*ε)∘P = P. Следовательно, мы нашли такое δ, что P = δ∘Q.

То есть, если можно выбрать оба параметра – точки P и Q, – то выбираем так, что P = δ∘Q, а если одна из точек зафиксирована – выбираем δ = ε^(-1) по модулю (простого) порядка группы точек, это всегда можно сделать из-за особенностей спецификации: подлежащие группы имеют простой порядок. (Не забывайте, что в формулах выше используется два умножения – умножение точки на скаляр и умножение целых чисел (δ = ε^(-1); 1 = ε^(-1)*ε). Это работает потому, что скаляры – целые числа, но по модулю порядка группы.)

В Dual EC DRBG битовый вывод генератора, – то есть, X-координата S_n∘Q, – урезается: из него удаляются 16 старших битов. Это означает, что прямо использовать результат для вычисления координат исходной точки нельзя. Но 16 бит можно быстро перебрать, проверяя, для всех значений подряд, лежит ли на кривой точка с соответствующей X-координатой. Вычисление значений по уравнению кривой тоже не составляет проблемы – уравнение известно, а используемые там операции обязательно быстрые.

Естественно, полученная перебором точка может оказаться неверной. То есть, точка не будет являться S_n∘Q. На этом шаге “через бэкдор” у атакующего нет никакого способа проверить, что точки совпали. Но это не сильно затрудняет атаку. Значения секретного состояния нужно вычислить для всех возможных точек, которые соответствуют сокращённому битовому значению, а результат по каждой точке – сопоставить с дальнейшим анализом трафика. Например, если выдача генератора используется для получения секретного ключа, то выбрать его верное значение можно при помощи пробного расшифрования. В любом случае, анализ 2^16 числовых значений при помощи перебора не представляет здесь вычислительной проблемы.

В ранней версии стандарта NIST на Dual EC DRBG реализация использовала подмешивание дополнительной маски на каждом шаге вычисления псевдослучайных чисел. Это делало описанный бэкдор нерабочим. Однако стандарт был быстро обновлён, точка подмешивания дополнительной маски перенесена, и использование бэкдора стало снова возможным. Поэтому данная особенность здесь не рассматривается.

Проблема алгоритма Dual EC DRBG, как криптографического генератора псевдослучайных чисел, помимо низкой производительности, в том, что внутри его конструкции есть жесткая структура, зависящая от внешних параметров. Из-за алгебраических свойств эллиптических кривых, в практической реализации – точки P и Q всегда связаны. Да, иногда, если специально постараться, они могут быть получены способом, дающим некоторую гарантию того, что связующий скаляр никому не известен. Либо, P и Q может генерировать конкретный пользователь, в качестве параметра для своей локальной версии генератора. Стандарт NIST разрешал такой вариант, но не рекомендовал его, а для соответствия строгим требованиям FIPS допускались только параметры из спецификации.

(Это расширенная версия статьи, которую я недавно опубликовал на “Хабре”.)

Пишут, что некоторые китайские автомобили (Lixiang), “неправильно” ввезённые в Россию, начали дистанционно отключать при помощи обновления ПО от производителя. Насколько это верно для данного конкретного случая – не очень понятно, но, вообще, механизм такой есть, и есть он у многих современных марок и моделей.

Прецеденты использования были тоже, не единичные, и это не только относительно недавние случаи блокирования отдельных функций BMW, но и достаточно старая история в Штатах с встроенными в системы двигателя “иммобилайзерами”, управляемыми страховыми компаниями. Интересно другое: понятно, что раз механизм имеется, то задействовать его будут и по всяким другим, – произвольным, вообще говоря, – причинам, а не только на основании региона использования автомобиля. Например, пользователь автомобиля поехал в правильном регионе, но “не туда”, “не в то время”, вообще – пользователь спросил у встроенного в смартфон “ИИ-сервиса” о том, как можно преодолеть действие дистанционно подаваемой команды. Впрочем, это сейчас мало кого беспокоит.

Некоторое время назад я написал на “Хабр” о попытке использовать ChatGPT для генерирования кода OpenSCAD: задача была – сгенерировать код, описывающий простейший Y-образный разветвитель шлангов; для этого я составил подробнейший “промпт” на естественном языке (есть в статье).

Конечно, выдача ChatGPT оказалась абсолютно бесполезной – в статье есть скриншоты рендеринга того, что сгенерировала LLM. В комментариях спросили, почему я выбрал “чат-бот”, вместо “специализированной модели”. Скопирую сюда свой подробный ответ, чтобы он не потерялся:

Есть целый ряд причин.

Во-первых, эта штука не написала в ответ, что, мол, “вижу, тут требуется 3D-объект, но я всего лишь чат-бот – обратитесь к специализированной системе”. Напротив – оно прямо и уверенно пишет, что точно умеет в OpenSCAD, знает все детали, приводит примеры (я спрашивал), а также предлагает проверить, что всё в коде корректно и верно при помощи рендеринга в OpenSCAD (да, такой вот “напор” демонстрирует). Опять же – что такое “чат-бот”? Если это средство занять назойливых клиентов в чате технической поддержки пустопорожним переливанием запроса в ответ – ну, да, тогда с OpenSCAD лучше не подходить. Но позиционируется-то этот инструмент явно иначе.

Во-вторых, не то чтобы была у меня какая-то уверенность, но я предположил, что в эту систему, – возможно! – уже успели-таки встроить “специализированное решение для 3D”. Это разумное предположение: такая возможность, без сомнения, полезна, системы постоянно обновляют, ждут в этом году “универсальный ИИ”, то и дело утверждается, что оно успешно решает задачи по геометрии на уровне “продвинутого старшеклассника”. Вот и проверили. Если бы оно справилось, это бы не сделало его интеллектом, но результат бы порадовал.

В-третьих, программное, процедурное задание простейших 3D-объектов – вообще-то не сложнее, скажем, реализации алгоритмов быстрой сортировки больших массивов, алгоритмов обработки графов, алгоритмов балансировки параллельной работы с данными и т.д., и т.п. В компьютерной геометрии есть свои сложности, но они точно не в генерировании описания трёх цлиндрических трубочек и параллелепипеда (предположим). Вся такая простая 3D-геометрия – выписывается в векторах, если хотите. С этой геометрией в видеоиграх справляются те же видеокарты, на которых запускают эти же LLM. Задача процедурного определения простейшего 3D-объекта, между прочим, не сложнее и поиска “уязвимостей в ПО”. И уж тем более теряется сложность на фоне разговоров о генерировании видео по текстовому описанию. Конечно, всё это верно только в том случае, если там настоящий интеллект, который именно решает задачу, а не синонимайзер, замещающий решение сгенерированным текстом (или иерархией кластеров пикселей – не важно). Собственно, поэтому-то тут и возможны специализированные решения.

В-четвёртых, постоянно вижу и слышу, как LLM типа “чат-бот” используют для генерации программного кода – для этого ведь даже есть плагины в средах разработки. Код OpenSCAD – это чисто программный код, я же не просил рисовать чертёж в изометрии. Всё подходит.

Наконец, в-пятых: в качестве специализированной системы – я бы всё же предпочёл использовать тот или иной готовый инструмент для параметрического задания типовых объектов в OpenSCAD (Y-образный адаптер к ним тоже относится). Такие инструменты есть. Они детерминированы. Они проще. Натыкать в интерфейсе размеры – быстро. Но они – не LLM, на которых обещают “универсальный интеллект”. Собственно, есть ведь и немало инструментов “визуального программирования”. Даже для специальных систем, типа GNU Radio, но почему-то сейчас про них вообще забыли, а рассказывают именно про генерирование кода LLM, на которые всех заменят.