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

На dxdt.ru есть страница “Избранные записки” – добавил на эту страницу несколько новых ссылок. Конечно, записки сейчас выходят редко, тем не менее, потихоньку, но набралось количество, достаточное для обновления перечня избранных публикаций.

На dxdt.ru с 2016 года опубликована небольшая криптографическая библиотека для Arduino, построенная на российском шифре “Магма”. Мне иногда присылают сообщения о проблемах (ошибках, выводимых компилятором), которые возникают при сборке в новых версиях Arduino IDE. Собственно, решение упоминается в комментариях к странице, но я всё же добавил в основной текст подробное пояснение о причине трудностей и о том, как эти трудности победить. Кратко: проблема не в коде библиотеки, а в установленном по умолчанию уровне оптимизации компилятора – в старых версиях Arduino IDE установки были другие. Библиотеку можно использовать без изменений, но нужно подредактировать настройки IDE (штатным способом); второй вариант – использовать обновлённую библиотеку, где параметры оптимизации указаны в исходном коде. Подробности – на странице библиотеки.

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

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

Одним из весьма эффективных вариантов оказывается использование в качестве источника такого сигнала большого количества космических аппаратов с общими синхронными часами, находящихся на низкой орбите, с которыми возможен обмен широкополосными сигналами. То есть, это уже не GPS. Это – в точности схема “спутникового Интернета”, предложенная, например, SpaceX (Starlink).

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

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

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

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

Именно эти три аспекта, если их сложить вместе, позволяют создать хорошо защищённую от помех точную навигационную систему. Скорее всего, как отмечено выше, система будет комбинированной: спутниковый сигнал служит для коррекции автономных инерциальных систем. При этом спутниковые терминалы, требующие достаточно больших по размерам и тяжёлых антенн (ФАР), могут находиться на опорных станциях, например, на автомобилях или самоходных роботах, а носимый вариант навигатора, также имеющий встроенную инерциальную систему, будет взаимодействовать по радио с опорной станцией.

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

Естественно, Starlink – только один из примеров реализации подходящей технологии.

(Кстати, в 2012 году я писал о гипотетическом навигаторе, работающем без GPS.)

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

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

Что именно отображено на картинке (см. рисунок выше)? Каждой точке соответствует пара значений — элементов конечного поля. Сами эти элементы, обозначенные натуральными числами, формируют горизонтальную и вертикальную оси. А поскольку значения отображаются парами, то вся картинка соответствует F×F. Пары элементов — это пары, удовлетворяющие уравнению кривой: y² = x³ + 2020x² + x. Обратите внимание, что слева здесь квадрат, и уже из этого вытекает необходимость симметрии на картинке.

Возьмём более наглядный пример. На картинке ниже – нарисованы точки эллиптической кривой y² = x³ + 17x² + 1 над полем из 101 элемента; горизонтальная черта – разделяет “график” на верхнюю и нижнюю части (симметричные). Для двух точек – написаны их координаты: (26, 53) и (26, 48).

Почему точки симметричны? Потому что они обратные, их сумма в группе точек эллиптической кривой равна нулю (нейтральному элементу группы). Координаты X у этих точек совпадают, а координаты Y – обратные по сложению в базовом поле: 53 + 48 == 101, а это 0 (mod 101). Как уже упоминалось выше, левая часть уравнения – квадрат. Это означает, что у нас обязательно есть два элемента поля, соответствующих подстановке элемента 26 в правую часть. Полностью аналогично привычному 2² == (-2)² == 4. Проверяем: 53² (mod 101) == 48² (mod 101) == 82, а 82 == (26³ + 17*26² + 1) (mod 101). Понятно, что в группе, по определению, у каждого элемента есть обратный, поэтому картинка “ветвится” таким образом.

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

В качестве развития технологии ESNI, которая так и не вышла из статуса черновика (draft), сейчас разрабатывается вариант с передачей полного дополнительного сообщения ClientHello, но в зашифрованном виде. Предлагаемая сейчас схема выглядит чрезмерно сложной, в основном, из-за того, что логические составляющие вложены одна в другую, при этом есть ссылки из внутреннего сообщения на элементы внешнего. Вряд ли это удастся реализовать без множества ошибок, порождающих уязвимости. Тем не менее, само направление интересное. Вообще, в теории, большинство прикладных протоколов современной Сети можно сделать полностью зашифрованными, включая этап установления соединения. Конечно, на практике такое если и возможно, то не скоро, однако можно рассмотреть гипотетическую картину, которая возникнет, если схему всё же воплотить. Сейчас, в TLS 1.3, зашифрованы не все сообщения, но, если сравнить с предыдущими версиями, то на защищённый обмен стороны переходят гораздо раньше. Например, в случае развития TLS в выбранном направлении, первое же сообщение клиента будет передаваться полностью в зашифрованном виде.

Возникает традиционная проблема: где клиенту взять ключи? Ключи для такой схемы публикуются в DNS. При этом, использование DNSSEC – позволяет защитить данные от подмены, а доставка запросов и ответов DNS через TLS – защищает от прослушивания трафика.

То есть, опять же, на примере TLS, – клиент извлекает серверные криптографические параметры для установления соединения из DNS, генерирует нужные ключи и зашифровывает первое же сообщение, которое направляет серверу. Это сообщение может вообще не содержать фиксированных заголовков в открытом виде (кроме, понятно, относящихся к TCP/IP или UDP). Третья сторона видит только факт обмена узлов псевдослучайными данными. Более того, даже на уровне DNS – тоже видны только псевдослучайные данные, поскольку обмен защищён TLS, в том числе, на пути между рекурсивным резолвером и авторитативным сервером.

Основных проблем у такой схемы, если она внедрена повсеместно, несколько. Во-первых, сервер должен принимать и пытаться расшифровать любые входящие пакеты. Это очень затратно в вычислительном плане. Конечно, криптография сейчас довольно быстрая, но нагрузки всё равно возрастут в тысячи раз (и более). Нужно учитывать, что быстрые решения по фильтрации пакетов на уровне протоколов, доступные сейчас и работающие с данными в открытом виде, работать перестанут: для фильтрации в таком режиме окажутся доступны только параметры уровня номера порта и IP-адреса (ну, ещё ряд параметров TCP), а для обработки протоколов – придётся выгружать ключи на узлы балансировки и фильтрации. (Это можно сделать, но потребует очень больших затрат; которым, впрочем, наверняка будут рады крупнейшие производители сетевого оборудования.)

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

В-третьих, полностью исчезнут современные возможности по приоритизации разных типов трафика силами DPI: никаких сигнатур отдельных протоколов не останется, кроме самых базовых – номеров портов и IP-адресов (ну, ещё количество потоков можно как-то измерить).

Кроме того, гораздо сложнее станет отлаживать работу сетевого ПО и обнаруживать ошибки, поскольку типы прикладного трафика полностью потеряют “различимость”. Недоступным окажется пассивное блокирование ресурсов на уровне протокола (опять же, с использованием DPI).

И тем не менее, переход на такой уровень – вполне возможен в ближайшие годы.

По адресу audit.statdom.ru заработал полезный сервис Технического центра Интернет (ТЦИ), позволяющий автоматически проверить многие настройки веб-узла, с точки зрения их соответствия современным рекомендациям. Вводите имя (хостнейм, в формате test.ru) – робот опрашивает соответствующие узлы и выводит подробный отчёт, содержащий параметры TLS, HTTP/HTTPS (заголовки безопасности), DNS и MX, с рекомендациями: что включить и что работает не так, как ожидается. Кроме того, вычисляется рейтинг узла в баллах. Одной из особенностей этого сервиса является подробная проверка DNS, например, есть обнаружение доступности DNS-over-TLS (DoT) на авторитативных серверах.

Обратите внимание, что отправной точкой для исследования параметров является введённое имя хоста (имя сервера), при этом робот не следует HTTP-редиректам, а выводит результат для того имени, которое задано. Это означает, что если вы хотите проверить узел www.test.ru, для которого настроен редирект test.ru -> www.test.ru, то вводить нужно имя с www.

Ссылка: audit.statdom.ru.

(Я имею непосредственное отношение к разработке данного сервиса.)

Написал про HTTP-заголовки, связанные с обеспечением безопасности доступа браузеров (и не только) к веб-узлам, – статья опубликована на сайте ТЦИ.

Авторитативные серверы DNS – это серверы, которым делегирована поддержка заданной доменной зоны. Другими словами, это основные серверы, служащие первоисточником информации об адресации внутри доменной зоны. Именно к авторитативным серверам должен обращаться рекурсивный резолвер при поиске значений DNS-записей.

DNS-over-TLS – технология, защищающая трафик DNS-запросов при помощи TLS. Обычно, DNS-запросы и DNS-ответы передаются по протоколу UDP (реже – TCP) в открытом и незащищённом виде. Существует технология DNSSEC, которая позволяет снабдить содержание DNS-ответов электронной подписью, затруднив, таким образом, подмену информации. Но DNSSEC не скрывает сам трафик: то есть, третья сторона всё равно будет видеть состав запросов и ответов. Кроме того, DNSSEC аутентифицирует только передаваемые данные, привязывая их к некоторому открытому ключу, но не позволяет аутентифицировать сервер, который данные передал. В принципе, в модели угроз DNSSEC аутентификация сервера и не требуется: основная идея этой технологии состоит в том, что не имеет значения, каким маршрутом и от какого узла DNS-данные попали к клиенту – если данным соответствует валидная подпись от доверенного ключа, то они, так или иначе, достоверны. То есть, с точки зрения достоверности, канал получения DNS-информации для DNSSEC не важен. Если данные, защищённые DNSSEC, будут как-то изменены на транзитном узле, то клиент сможет обнаружить подмену. С DNS-over-TLS (или DoT) – другая история. Эта технология оборачивает обычный трафик DNS в TLS, создавая защищённый канал связи. DoT позволяет узлам, которые намерены обменяться DNS-запросом и DNS-ответом, аутентифицировать друг друга до отправки запроса. В подавляющем большинстве случаев, конечно, будет использоваться только аутентификация сервера клиентом.

В DNS, как в сервисе, большое значение имеет взаимодействие рекурсивного резолвера с так называемым stub-резолвером. Последний представляет собой самый простой вариант резолвера, который не выполняет поиска в DNS, а лишь перенаправляет запросы рекурсивному резолверу. Stub-резолвер – это типовой резолвер в подавляющем большинстве конфигураций операционных систем. Сервис же рекурсивного резолвера предоставляется либо провайдером доступа, либо отдельным провайдером DNS, как, например, в случае общедоступных резолверов Cloudflare (1.1.1.1) и Google (8.8.8.8).

Так вот, сейчас часто приходится слышать, что технология DNS-over-TLS предназначена лишь для защиты DNS-трафика на пути от stub-резолвера до рекурсивного резолвера, а на авторитативных серверах – не нужна. Это не так. Авторитативным серверам тоже рекомендована поддержка DNS-over-TLS, так как такая поддержка позволит защитить обмен информацией с рекурсивными резолверами. Дело в том, что прослушивание DNS-запросов или подмена данных – возможны и для трафика рекурсивного резолвера, адресованного не клиенту, а авторитативному серверу. Другое дело, что реализовать избирательность такой атаки становится сложнее, поскольку точно не известно, какие запросы какому клиенту соответствуют. Но, например, если используется популярный сервис DNS, то IP-адреса его узлов-резолверов известны, поэтому подмена может осуществляться избирательно. Впрочем, атакующему придётся каким-то образом встать своим транзитным узлом между авторитативным сервером и сервером DNS-резолвера. Это сложно, но возможно. Причём, разными способами. А не раз продемонстрированные на практике BGP-атаки позволяют перехватить трафик между сетями, которые, в смысле маршрутизации, находятся “далеко” от точки перехвата.

Поддержка DoT на авторитативных серверах пока что является большой редкостью и встречается существенно реже, чем даже поддержка DNSSEC. Тем не менее, один масштабный пример внедрения DoT здесь уже есть: технология поддерживается авторитативными серверами Facebook, на которые делегирована зона facebook.com.

Мы рассмотрим конкретный (хоть и игрушечный) пример реализации протокола Диффи-Хеллмана (DH) в группе точек эллиптической кривой (ECDH), а потом проведём на этот пример элементарную алгебраическую атаку, основанную на свойствах выбранных параметров, тем самым выясним, что параметры требуется выбирать аккуратно.

В качестве базового поля выберем GF(8191) – конечное поле порядка 8191 (8191 – простое число). Это поле изоморфно вычетам по модулю 8191, то есть, мы рассматриваем остатки от деления на 8191: 0, 1, 2… – поэтому далее элементы поля обозначаются целыми числами.

Выберем уравнение, задающее эллиптическую кривую E:
y² = x³ + 2020x² + x.
Это уравнение в форме Монтгомери, общий вид таких уравнений:
y² = x³ + Ax² + x, где A – элемент базового поля; в нашем примере A == 2020.
Не всякую эллиптическую кривую над конечным полем можно представить в форме Монтгомери. (Нетрудно заметить, что все кривые в форме Монтгомери вполне определяются значением коэффициента А, это удобно.)

Точки кривой соответствуют парам (X, Y) элементов базового поля, удовлетворяющим уравнению, включая особую точку “бесконечность”, которая в группе точек является нейтральным элементом. Пример точки: (839, 7305). Можно проверить (например, в WoframAlpha), что 7305² (mod 8191) == (839³ + 2020*839² + 839) (mod 8191). Заметьте, что пара (0,0) лежит на кривой, но не является нейтральным элементом! Нейтральный элемент мы будем обозначать пустой парой () или буквой O, а точка (0,0), если её сложить с точкой (839, 7305), даст точку (1523,5367). Групповую операцию на E обозначим символом “+”.

Группа точек нашей кривой E имеет порядок 8176, то есть, состоит из 8176 элементов. Сразу заметим, что эта кривая не подходит для практического использования, и не только потому, что здесь “мало точек”, но и из-за разложения числа 8176 == 2⁴ * 7 * 73. Однако для нашего примера – именно это и нужно. Кроме базового поля и эллиптической кривой, параметры протокола ECDH включают точку кривой, которая называется генератором. Поскольку генератор – это точка на кривой, он является элементом её группы. Выбираем точку (1029, 895) на роль генератора. Обозначим генератор буквой G. Если генератор G складывать с самой собой, то на каком-то шаге получим нейтральный элемент группы. Количество экземпляров G, которые нужно сложить, чтобы получить нейтральный элемент, называется порядком элемента. Для выбранного значения G порядок равен 1022. Обратите внимание, что порядок точки-генератора меньше порядка группы. G – генерирует подгруппу в E, порядок подгруппы всегда делит порядок группы (теорема Лагранжа): 8176 == 8*1022.

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

Итак, мы выбрали поле GF(8191), уравнение кривой E y² = x³ + 2020x² + x, и генератор G = (1029, 895).

Введём умножение на скаляр: G + G + G = [3]G == 3*G. То есть, мы определили, что сложение трёх экземпляров точки с самой собой – записывается как 3*G. Важно заметить, что такое умножение – это не операция в группе точек кривой, а некоторая дополнительная конструкция.

Перейдём к протоколу ECDH между двумя сторонами. Стороны выбирают секретные скаляры – m и n, это целые положительные числа, меньшие порядка генератора G (понятно, что брать в качестве секретного скаляра единицу – особого смысла тоже нет). Стороны обмениваются по открытому каналу значениями m*G и n*G. Эти значения – точки на кривой, соответствующие n- и m-кратному сложению генератора G. Общий секрет стороны вычисляют так: m*(n*G) == n*(m*G) == (n*m)*G. Ограничение по порядку генератора вызвано тем, что нет смысла использовать числа, превышающие порядок: соответствующая точка всё равно будет находиться в подгруппе генератора.

Пример в числах:

m = 731
n = 395

m*G == (5720, 2990)
n*G == (6695, 8044)

m*(n*G) = [731](6695, 8044) == (4647, 2580) == n*(m*G) = [395](5720, 2990)

Таким образом, стороны получили общий секрет – точку на кривой с координатами (4647, 2580). Эта точка равна точке [731*395]G. Обратите внимание, что произведение 731 * 395 == 288745, можно привести по модулю 1022, то есть, по модулю порядка генератора G. (Но можно и не приводить – результат не изменится.) Значение общего секрета используется в качестве входных данных для вычисления ключей симметричного шифра. Именно так ECDH применяется в TLS. Точке соответствует пара (X, Y) элементов поля, но в качестве источника данных для ключа может использоваться только один элемент, обычно, это X-координата.

Сторона, прослушивающая канал, получила значения n*G и m*G, знает параметры поля, кривую, значение G, но не знает n и/или m. Вычисление n (или m) по известному n*G (или m*G) – называется задачей дискретного логарифмирования в конечной группе и, для произвольных групп точек эллиптической кривой достаточно большого порядка, вычислительно трудна. На практике используются параметры с порядками, близкими к 2²⁵⁶ (и более). Методов, позволяющих даже на специализированном суперкомпьютере за разумное время решить задачу дискретного логарифмирования для произвольных параметров и групп таких порядков – пока не найдено. Однако для некоторых специальных случаев – методы известны. Некоторые из этих методов элементарны, как будет видно из примера ниже.

Попробуем теперь взломать нашу “криптосистему” ECDH на эллиптической кривой. Конечно, в случае использованных параметров, не составляет труда простым перебором найти нужное значение секретного скаляра (оно лежит в интервале [2..1021]). Однако простой перебор здесь работает только потому, что порядок далёк от практических значений. Но есть гораздо более эффективный метод, который, с некоторыми упрощениям, и описан ниже.

Заметим, что число 1022 == 2 * 7 * 73. Это означает, что внутри нашей подгруппы генератора G могут быть меньшие подгруппы, порядок которых делит порядок генератора. Всякий элемент подгруппы представим в виде l*G – то есть: G + G+…+ G (l раз). Так что, возможно, найдутся такие элементы, которые конструируются из G, но при этом их порядок гораздо меньше 1022. Пусть такой элемент – P = (6736, 4842) == 14*G, где 14 == 1022/73 == 2 * 7. Используя P, мы можем “разбить” все элементы подгруппы генератора на подмножества с меньшим количеством элементов, каждый из которых соответствует той или иной “кратности” P. P имеет порядок 73, то есть 73*P == O, где O – нейтральный элемент группы (или, в других обозначениях: P + P + … + P = O). Это всего 73 различных значения (включая нейтральный элемент). Атака работает следующим способом. Сгенерируем и запишем в опорную таблицу все пары (k, k*P), где k пробегает [1..72]. Получив значение m*G (открытый ключ ECDH Q == m*G), мы будем вычитать из него G до тех пор, пока не обнаружим элемент, кратный P, который находится в опорной таблице. (Вычитание в группе эквивалентно сложению с обратным элементом, то есть -G, обратный к данному элемент группы кривой нетрудно вычислить.) Пусть мы на шаге q последовательного вычитания нашли подходящее k*P в таблице, тогда, зная k, мы можем вычислить секретный скаляр m == k * 1022/73 + q.

Проверим для m == 731, как в примере выше.

731*G == (5720, 2990). Вычитаем генератор G равный (1029, 895). Обратная к G точка – (1029, 7296), т.к. 7296 + 895 = 0 (mod 8191).

(5720, 2990) + (1029, 7296) == (5623, 8124)
(5623, 8124) + (1029, 7296) == (6316, 6614)
(6316, 6614) + (1029, 7296) == (7183, 6772)

Точка (7183, 6772) является кратной точкой для элемента P, который выбран нами выше в качестве опорного: [52]P == (7183, 6772). Таким образом, мы провели три операции сложения точек кривой (q == 3) и нашли заранее вычисленную опорную точку. Теперь мы можем определить секретный скаляр: 52 * 1022/73 + 3 == 731. Заметьте, что в одно значение P как бы “входит” 14 экземпляров G, то есть, чтобы гарантированно попасть в одну из точек опорной таблицы, потребуется не более 13 операций сложения точек. Для определения значения m == 731 прямым полным перебором – пришлось бы выполнить 730 сложений (если, конечно, не оптимизировать процесс поиска другим способом). Очевидно, что можно использовать и другие подгруппы для этой атаки – в каких-то случаях потребуется больше памяти для хранения опорной таблицы, но меньше операций с точками для поиска элемента таблицы; в других случаях – меньше памяти, но больше операций с точками.

Посмотрим, почему это работает, с другой стороны. В группе точек генератора все элементы представимы в виде l*G, для некоторого целочисленного l. Мы выбрали точку P == l*G. На следующем шаге мы вычисляем все значения k*P (их конечное количество) и записываем их в таблицу вместе с соответствующим k. То есть, мы построили таблицу дискретных логарифмов для P. Каждое из значений в таблице равно k*(l*G), что можно переписать как (k*l)*G (важно понимать, что здесь использованы два различных умножения: в целых числах, для k*l, и умножение скаляра на точку кривой для G). Соответственно, открытый ключ ECDH Q == m*G можно переписать как (k*l + r)*G, где k*l + r == m – представление целого m, где r – остаток от деления на l (0 <= r < l). Перепишем выражение: Q = (k*l)*G + r*G. (Здесь знак “+” уже превратился в обозначение операции сложения точек, но общий смысл не поменялся.) Мы вычитаем из значения Q генератор G до тех пор, пока полученный результат не совпадёт с каким-то из элементов нашей таблицы логарифмов для P, таким образом – подсчитывается значение остатка r. Как только мы нашли подходящий элемент в таблице, мы знаем все значения, нужные для вычисления секретного ключа m: значение k – из таблицы, l – известно из построения P, r – остаток, равный количеству операций вычитания, потребовавшихся для того, чтобы Q указало на тот или иной элемент таблицы. Таблица логарифмов содержит всего 72 элемента, что значительно меньше, чем 1022.

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