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

Где именно в криптосистеме электронной подписи ECDSA “работает” эллиптическая кривая?

Посмотрим, для начала, на значение подписи, которое состоит из двух параметров – (R, S). Здесь R – это координата X точки на используемой эллиптической кривой, а именно, X-координата точки k∘G, где G – точка кривой, называемая генератором (зафиксированный параметр криптосистемы), а k – секретное уникальное значение (ECDSA nonce). Запись k∘G, – “умножение на скаляр”, – означает повторное сложение точек: G⊕G⊕G⊕…⊕G, где G встречается k раз, а “⊕” – обозначает операцию в группе точек кривой, то есть, сложение точек. (Умножение тут лучше было бы записать [k]G, например, но это детали.)

На значение k накладываются различные ограничения, но это всего лишь натуральное число (конечно, так можно сказать про всё, что встречается “в компьютерах”). Структура кривой такова, что есть пары точек с совпадающими X-координатами, но различными Y-координатами. Этот момент нередко используется в атаках на реализации ECDSA. В данном случае – R это именно X-координата.

Эллиптическая кривая непосредственно использована для вычисления одного параметра подписи – R, который, впрочем, сразу “превращается” из точки, как кортежа значений, задаваемых дополнительной структурой уравнения кривой, в единственное число.

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

Это основная математическая идея ECDSA: базовое уравнение так устроено, что части структуры преобразования, вынесенные наружу в составе публичных значений, сокращаются, если ключ проверки соответствует подписи (и параметрам), но не сокращаются в прочих случаях.

Сокращающиеся структуры не видны, а вычислить их, – то есть, обратить, – по открытым значениям и параметрам, сложно. Концептуально это напоминает, например, RSA, где внутри открытого ключа всегда содержится структура, связанная с разложением на простые множители, благодаря которой криптосистема работает. Тут необходимо обратить внимание на то, что, во многих практических реализациях, значение k может вычисляться с использованием и подписываемого сообщения, и секретного ключа – например, так делается в схеме детерминированной ECDSA. Но “классическая” ECDSA такого, вообще говоря, не требует. Это, впрочем, один из самых проблемных моментов реализаций данной криптосистемы – так, если третья сторона знает параметры генератора псевдослучайных чисел, который использовался для получения k, то эта третья сторона без особых трудностей может вычислить секретный ключ по значению подписи и подписанного сообщения (см. ниже).

Итак, эллиптическая кривая, заданная для ECDSA, использовалась для вычисления R. Где ещё встречаются операции с точками? Прежде всего – вычисление открытого ключа. Открытый ключ в ECDSA это точка на кривой, а получается он из секретного значения d путём умножения генератора: Q == d∘G. То есть, d – целое число. Принцип эквивалентен вычислению r. Однако, в отличие от r, открытый ключ Q повсеместно записывают как пару координат (X,Y), но это только способ записи, потому что достаточно сохранять X и один “бит знака” для Y.

Вторая часть подписи ECDSA – параметр s. И значение этого параметра вычисляется уже без использования операций с точками кривой. Уравнение для s следующее:

S == k^(-1)*(H + Rd)

– здесь, кроме уже определённых k, R и d (d – секретный ключ), используется значение H – это и есть подписываемое сообщение (технически, это значение хеш-функции от сообщения).

Все значения в данной формуле – это натуральные числа (даже k^(-1)), а не точки. Поэтому тут использованы другие значки для обозначения операций: “+”, “*”, “^(-1)” – это “обычные” операции сложения, умножения и взятия обратного по умножению. “Обычные” в кавычках по той причине, что вычисления проводятся по модулю некоторого числа. То есть, это привычная арифметика остатков. Положительное число, по модулю которого проводятся операции, это так называемый порядок группы точек кривой. Можно считать, что порядок – это количество доступных для вычислений точек кривой. Порядок обозначают, например, P, а тот факт, что это арифметика остатков “по P” записывают как (mod P). Так что свойства кривой тут участвуют только косвенно. Взятие обратного по умножению – k^(-1) – это нахождение такого числа, которое даст 1 (mod P) при умножении на k. Так как вычисления выполняются (mod q), то k^(-1) тоже будет целым числом. Пример: 4*2 == 1 (mod 7) – так как 8/7 – даст остаток 1. Обратите внимание, что все вычисления дальше – тоже (mod P), но отдельно этот момент упоминаться не будет, так как, для практических целей ECDSA и для простого P, свойства вычислений совпадают с привычными операциями в рациональных числах (кроме сложения точек кривой).

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

Проверка подписи в ECDSA использует следующее уравнение:

C == (H*S^(-1))∘G ⊕ (R*S^(-1))∘Q

– обратите внимание, что тут разные обозначения операций, чтобы можно было различить операции с точками и операции с числами; а значение Q, – открытый ключ, – это d∘G. Работает вся эта схема потому, что, из-за свойств сложения в группе точек кривой, можно операцию сложения точек ⊕ спустить в натуральные числа, вот как: 3∘G ⊕ 5∘G == (G⊕G⊕G)⊕(G⊕G⊕G⊕G⊕G) == 8∘G. При этом, если подставить вместо S формулу вычисления S (см. выше), то в правой части сократится всё, кроме k∘G. Получим, что C == k∘G, а X-координата C должна совпасть с R, если, конечно, подпись верна и вычисления верны. И здесь эллиптическая кривая используется непосредственно для вычисления итогового значения, а именно – умножение на скаляры точек G (генератор) и Q (открытый ключ), сложение получившихся точек.

Воскресное чтение манускриптов. Впрочем, в этот раз опять рассматривание иллюстраций. Недавно уже встречался иллюстрированный манускрипт с описанием метода разрушения крепостных стен при помощи загадочной “огненной машины” из труда “Полиоркетика” Аполлодора Дамасского. Такая же иллюстрация (но с несколько большей детализацией – см. скриншот ниже) и такой же фрагмент текста встречаются в манускрипте Vat.gr.1605 (11 век) из Ватиканской Апостольской библиотеки. Считается, что исходный текст для этого манускрипта подготовлен в 10 веке неустановленным автором, которого называют то Византийским Героном (не перепутайте с Героном Александрийским), то Героном Младшим, то просто византийским Анонимом.

Кстати, из прошлой записки не совсем понятно, но по этой картинке уже можно догадаться, что тут на стене закрепляется некоторая глиняная “топка” с углём (ἄνθραξ), в которую при помощи мехов (ἄσκωμα) нагнетают воздух для повышения интенсивности горения (что, собственно, и описано в тексте манускрипта).

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

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

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

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

Кстати, серверы Google (например) уже поддерживают X25519Kyber768 – см. скриншот ниже, – а это означает, что можно найти новые уязвимости, связанные с поддержкой этой криптосистемы.

В Chrome версии 124 всё же включили по умолчанию гибридную криптосистему с постквантовой стойкостью X25519Kyber768 для TLS. Проверить можно на тестовом TLS 1.3 сервере: tls13.1d.pw – там поддержка есть с сентября прошлого года.

(Поскольку “Яндекс.Браузер” является клоном Chrome/Chromium, то поддержка X25519Kyber768 по умолчанию должна появиться и там.)

Сообщают, что “Яндекс”, вместо поиска сайтов с выдачей ссылок на найденное, переходит к использованию синонимайзера, который будет пользователю тут же, в приложении от “Яндекса”, показывать переписанный текст, “найденный в Интернете”, – то есть, скопированный с тех же сайтов, – но уже без того, чтобы пользователь куда-то там переходил, на какие-то сайты-источники текстов для “Яндекса”. Решение называется “Нейро” и относится к модному классу ИИ LLM. Да, формально, там всё ещё упоминается “отдельный блок ссылок” на источники, но “задача пользователя” уже формируется как получение ответа в виде развернутого текста тут же.

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

Многие используют PuTTY, а также – ключи на кривой NIST P-521, потому что считают (не без оснований), что здесь бо́льшая разрядность (например, по сравнению с кривой P-256) обеспечивает бо́льшую стойкость. В PuTTY выявлен дефект реализации ECDSA на данной кривой, который приводит к раскрытию секретного ключа по набору подписей, полученных от него – то есть, большее количество разрядов не только не помогло, но и сыграло в сторону ухудшения. Это CVE-2024-31497.

Математический смысл уязвимости следующий. Алгоритм вычисления подписи в ECDSA использует nonce – это секретный, (псевдо)случайный параметр, который обычно обозначают k. Здесь в nonce, из-за ошибки в коде, зафиксировали девять битов в начале (или в конце) записи. (Девять, видимо, потому, что 521-512 == 9.) Речь тут не про секретный ключ, а про дополнительное значение: секретный ключ в обычной ECDSA не меняется от подписи к подписи, что для данной атаки имеет определяющее значение, а вот параметр/nonce, при этом, меняется. Однако, если известно дополнительное распределение для k, как в случае данного дефекта, то часто можно вычислить секретный ключ, задействовав некоторое количество значений подписей. В случае CVE-2024-31497, девять фиксированных последовательных битов позволяют раскрыть секретный ключ за, как пишут, примерно, 60 подписей.

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

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

Понятно, что в статье обнаружатся ошибки и она потребует, как минимум, уточнений. Так, сегодня опубликована записка (Omri Shmueli), указывающая на недостижимые значения параметров, которые использованы в доказательстве корректности алгоритма. Это, впрочем, только добавляет арифметической занимательности, поскольку доказательство недостижимости основано на оценке количества простых чисел, меньших заданного. Дело в том, что описанная версия алгоритма, для корректной работы, требует построения набора из некоторого количества попарно простых натуральных чисел, меньших заданного порогового значения – но для определённых значений параметров таких чисел может не найтись в нужном количестве, поскольку не хватит простых. Если алгоритм нельзя исправить (это ещё тоже не факт) и это удастся доказать, то может даже так оказаться, что постквантовая стойкость криптологических задач теории решёток зависит от количества простых чисел, меньших заданного порога. А это весьма сильное и интересное ограничение. (Но, конечно, вряд ли это так.)

(Update, 13/10/2024: в исходной работе довольно быстро обнаружилась критическая ошибка и автор пока не нашёл способа эту ошибку исправить. Из этого не следует вывод, что “задачи на решётках” обладают строго доказанной стойкостью к “квантовым атакам”.)

На сайте журнала “Интернет изнутри” доступен свежий номер в формате PDF. Отдельно порекомендую статью «Квантовые коммуникации: “пик хайпа” или “плато продуктивности” с точки зрения дилетанта» (с. 31) и, конечно, исключительный рассказ из первых рук про историю РосНИИРОС и домена RU (с. 59).

Воскресное чтение манускриптов. В одной из прошлых записок по теме рассматривался текст варианта записи труда Клеомеда “Учение о круговращении небесных тел” (13 в., Adv.MS.18.7.15), с описанием метода, применённого древним греком Эратосфеном для определения размеров Земли. В этот раз – посмотрим на тот же фрагмент текста Клеомеда, где указана длина окружности в стадиях, но в записи другого манускрипта: Pal. gr. 018 (часть Cleomedes, Cyclia/Caelestia) – из библиотеки Гейдельбергского университета. (Далее эти два манускрипта здесь называются просто Pl (Pal. gr. 018) и MS.)

Итак, Pl – манускрипт начала 14 века на древнегреческом, здесь нет чертежа, как в MS, а в записи, кроме такого же “скорописного” стиля, использовано множество сокращений (см. ниже), так что выглядит всё ничуть не менее загадочно, чем вариант из предыдущего MS (хоть тот и 13 века). Новый скриншот:

Подчёркнута (зелёным) строка, в которой и указана длина окружности Земли по меридиану – двадцать пять мириад. В предыдущем варианте, то есть в MS, строка, сообщающая о расчётной длине меридиана в 250 тыс. стадиев, если символы перевести в современную типографику, выглядит так: “ὁ ἄρα σύμπας κύκλος γίνεται μυριάδων εἴκοσι πέντε” . Но на скриншоте манускрипта Pl запись отличается. Вот два варианта на одной картинке (вверху – Pl, а внизу – та же строка из MS, см. прошлую записку по теме):

Думаю, что “ὁ ἄρα” – теперь нетрудно прочитать, как и лигатуру σύ со “смайликом”, построенным на диерезисе. Остальное, конечно, читается сильно сложнее. Однако, когда два варианта выставлены рядом, становится очевидно, что для опытного читателя, – возможно, инквизитора, – зашедшего в средневековый скрипторий, тут всего лишь два почерка, отличающихся в некоторых привычных деталях. Кроме, разве что, последних слов фрагмента.

Дело в том, что на манускрипте Pl слова “εἴκοσι πέντε” из записи “двадцати пяти” – отсутствуют (самый конец верхней строки). Вместо этого число 25 записано древнегреческими цифрами, вот так: κε – что и обозначает 20 (κ) + 5 (ε).

Утечки по побочным каналам (ПЭМИН) в видеокамерах смартфонов, веб-камерах и в прочих цифровых камерах, вызванные работой интерфейса передачи данных от приёмной матрицы. Не то чтобы это было неожиданностью: канал известен, для компьютерных мониторов аналогичный канал является типовым при оценке защищённости помещений и рабочих мест с ПК. Однако тут исследователи пишут об успешном приёме и декодировании утечки видеосигнала, – иногда, на расстоянии в несколько метров, – с использованием самого рядового оборудования: ноутбука и недорогого SDR-приёмника. Есть сайт EM Eye с подробным описанием и примерами кода, а также исходная публикация.

Методы защиты всё те же: шумогенератор, экранирование, ну и переход на не столь “прозрачные” протоколы передачи данных – тут эффективно внесение псевдослучайного “шума” на уровне кодирования прямо в аппаратный интерфейс.

(via)