elikaski/ecc_attacksИзвестные атаки на криптографию на эллиптических кривых
В последние годы подход криптографии на эллиптических кривых стал популярным благодаря своей высокой эффективности и высокой стойкости. Цель этой статьи — представить данную тему в относительно более ясном виде, чем она представлена сегодня в интернете.
В этой статье я расскажу, что такое эллиптические кривые, какие основные операции можно выполнять над ними и как их можно использовать в криптографическом контексте. Большая часть статьи состоит из примеров известных атак на некорректные реализации или неправильные применения этих кривых. На протяжении всей статьи я стараюсь разделять объяснение на интуитивно понятную часть высокого уровня и математическую часть, в которой рассматриваются более детальные аспекты. Читателю предлагается сосредоточиться на той части, которая интересует его в данном месте, и пропустить менее интересные.
Приятного чтения!
В общем случае эллиптическая кривая — это некоторая изогнутая линия. Примером такой линии является парабола, уравнение которой имеет вид $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$, и выглядит она так:
В контексте криптографии принято использовать эллиптические кривые, уравнение которых имеет вид
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Например, эллиптическая кривая, соответствующая уравнению $𝑦^2 = 𝑥^3 − 3𝑥 + 3$, выглядит так:
Уравнение кривой определяет связь между координатой 𝑥 точки на кривой и её координатой 𝑦. В криптографическом контексте мы ограничиваем 𝑥, 𝑦, 𝑎, 𝑏 целыми числами и выполняем вычисления по модулю некоторого большого простого числа. Таким образом, уравнение эллиптической кривой имеет вид:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Это означает, что на кривой имеется конечное число точек. На математическом языке говорят, что кривая определена над конечным полем порядка 𝑝. В результате теперь не обязательно каждой координате 𝑥 будет соответствовать точка на кривой, поскольку соответствующая ей координата 𝑦 может не быть целым числом.
Множество точек на кривой состоит из пар целых чисел (𝑥, 𝑦), удовлетворяющих уравнению кривой. Помимо этих точек, определяется ещё одна особая точка, называемая «бесконечностью», которая обозначается через 𝒪. На математическом языке эта точка является нейтральным элементом множества точек на кривой относительно операции сложения, которую мы определим в следующем разделе. Число точек на кривой (включая точку 𝒪) называется «порядком кривой».
Ещё одно наблюдение заключается в том, что эллиптические кривые симметричны относительно оси X. Это означает, что если точка 𝑃 = (𝑥, 𝑦) находится на кривой, то точка −𝑃 = (𝑥, −𝑦) также находится на кривой. Фактически эти точки считаются «обратными» друг другу (отсюда обозначение −𝑃 для второй точки), и результат операции сложения между ними определяется как нейтральный элемент 𝒪.
Теорема, называемая теоремой Хассе, даёт оценку #𝐸 — порядка кривой, который имеет порядок величины Θ(𝑝). Более точно:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Имея две точки на кривой, можно определить операцию сложения между ними, результатом которой является третья точка, также лежащая на кривой. Чтобы найти эту точку геометрически, мы проводим линию между двумя заданными точками и продолжаем её до тех пор, пока она не пересечёт кривую в третьей точке. Эта точка отражается относительно оси 𝑋, и полученная точка определяется как результат сложения.
Вот диаграмма, показывающая, как, имея точки 𝑃 и 𝑄, можно найти точку 𝑃 + 𝑄:
Вопрос, который может возникнуть из этого описания: что произойдёт, если линия, проведённая между двумя точками, больше не пересечёт кривую? В этом случае говорят, что линия пересекает кривую в «бесконечности», и результатом сложения является точка 𝒪. Заметим, что этот случай возникает, если проведённая линия вертикальна, то есть мы пытаемся сложить точку 𝑃 с обратной ей точкой, −𝑃:
Из этого выводятся два основных тождества. Для каждой точки 𝑃 выполняется:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Ещё один вопрос, возникающий из геометрического описания: как сложить точку саму с собой? Мы видели, что для сложения двух различных точек 𝑃 и 𝑄 мы проводим линию между ними и смотрим на точку пересечения её продолжения с кривой. Интуитивно мы оставим 𝑃 неизменной и будем рассматривать линию, которая образуется по мере того, как 𝑄 приближается «всё ближе и ближе» к 𝑃, пока 𝑄 не сольётся с 𝑃. В результате мы получим линию, которая становится всё более «касательной» к кривой в точке 𝑃, и именно эту линию мы будем рассматривать, когда захотим сложить 𝑃 саму с собой:
Чтобы сложить точку 𝑃 саму с собой, мы проводим касательную к кривой в точке 𝑃 и продолжаем её до пересечения с кривой во второй точке. Эта точка отражается относительно оси 𝑋, и полученная точка определяется как результат сложения. Результат сложения принято обозначать как 𝑃 + 𝑃 = 2𝑃. Опять же, если касательная не пересекает кривую во второй точке, то говорят, что она пересекает кривую в «бесконечности», и в этом случае результатом сложения является точка 𝒪.
Эти наглядные геометрические описания хорошо иллюстрируют и помогают понять, как работает сложение точек. Но как же мы вычисляем его на самом деле? Конечно же, с помощью математических уравнений!
Пусть даны точки $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ и $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$. Результатом их сложения является точка $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ такая, что:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
где 𝜆 определяется как наклон линии, соединяющей точки, если они различны, и как наклон касательной к кривой в точке, если точка складывается сама с собой. Формально:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
Математические вычисления, стоящие за сложением точек, не являются критически важными для остальной части статьи. В этом отношении мы можем рассматривать сложение точек как чёрный ящик, который принимает две точки на кривой и возвращает третью точку, также лежащую на кривой.
Мы видели, что точку 𝑃 можно сложить саму с собой, и обозначили полученную точку через 2𝑃. Если снова прибавить точку 𝑃 к этому результату, мы достигнем точки, обозначаемой 3𝑃, и так далее. Таким образом можно определить «умножение» точки на константу путём многократного прибавления точки к самой себе (аналогично умножению чисел):
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
Казалось бы, чтобы умножить точку на число 𝑛, нам нужно выполнить 𝑛 операций сложения точек. Это связано с тем, что, имея начальную точку, трудно заранее узнать, где окажется «последняя» точка, не достигнув её «шаг за шагом». Такое вычисление было бы крайне неэффективным, поскольку 𝑛 может быть очень большим.
Для этой цели существует алгоритм Double And Add, в котором мы начинаем с точки 𝑃, затем для каждого бита в двоичном представлении числа 𝑛 текущая точка умножается на 2 (то есть складывается сама с собой) и прибавляется к результату, если значение бита равно 1. Временная сложность этого алгоритма составляет 𝑂(log 𝑛), и он позволяет эффективно умножать точки на очень большие числа.
Важное свойство умножения точек, которое мы будем использовать далее, заключается в том, что для каждой точки 𝑃 и пары чисел 𝑎, 𝑏 выполняется:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
Интуитивно, предположим, что мы начинаем с точки 𝑃, делаем от неё 𝑎 шагов и достигаем точки 𝑎𝑃. От этой точки мы делаем 𝑏 шагов «размером» 𝑎 и достигаем точки 𝑏(𝑎𝑃). Альтернативно, в другом сценарии, мы могли бы начать с точки 𝑃, сделать от неё 𝑏 шагов и достичь точки 𝑏𝑃. От этой точки делаем 𝑎 шагов «размером» 𝑏 и достигаем точки 𝑎(𝑏𝑃).
В обоих сценариях мы в общей сложности сделали от точки 𝑃 одинаковое количество шагов — 𝑎𝑏, поэтому в обоих сценариях мы достигли одной и той же конечной точки. С математической точки зрения умножение точки на константу ассоциативно.
Если начать с точки 𝑃 и снова и снова прибавлять её к самой себе, то на каждом таком шаге мы будем достигать некоторой новой точки на кривой. Поскольку число точек на кривой конечно, на некотором этапе мы снова достигнем точек, которые уже встречали, и окажемся в своего рода цикле, или «круге». Более точно: на некотором этапе мы достигнем точки -𝑃, на следующем шаге — точки 𝒪, а ещё через шаг снова достигнем точки 𝑃, с которой начали.
Точка, которая образует такой «круг», называется генератором, поскольку из неё можно породить весь «круг», и её принято обозначать буквой 𝐺. Число точек в «круге» (включая точку 𝒪) называется «порядком генератора 𝐺» и обычно обозначается через 𝑛. Каждая точка на кривой образует «круг» того или иного рода. С математической точки зрения множество точек этого «круга» является циклической группой.
Интересное свойство, вытекающее из этого, заключается в том, что умножение точки 𝐺 на её порядок 𝑛 даёт точку бесконечности:
𝑛𝐺 = 𝒪
«Даны точки 𝑃 и 𝑄, такие что 𝑄 = 𝑥𝑃 для некоторого 𝑥. Найти 𝑥 трудно.»
А словами: предположим, кто-то начал с некоторой начальной точки, сделал от неё определённое количество шагов и достиг конечной точки. Имея начальную и конечную точки, как мы узнаем, сколько шагов было сделано?
Ответ на этот вопрос не так очевиден, поскольку заранее трудно предсказать, какие точки будут достигнуты при шагах от начальной точки. Наивное решение могло бы состоять в том, чтобы самим начать с 𝑃, продвигаться от неё вперёд по одному шагу и считать сделанные шаги, пока мы не достигнем 𝑄. Сложность такого решения составляет 𝑂(𝑥), и оно неосуществимо, если известно, что 𝑥 — большое число, например если 𝑥 имеет размер 256 bit.
Эта задача называется задачей дискретного логарифма на эллиптической кривой (ECDLP), и она является трудной. Но насколько она трудна?
В криптографическом контексте принято измерять «трудность задач» или «стойкость криптографической системы» метрикой, называемой Security Level. В этой метрике говорят, что задача имеет «𝑛 бит безопасности», если наилучшая известная атака решает её за $𝑂(2^𝑛)$ шагов.
В настоящее время лучший алгоритм решения задачи ECDLP выполняет это со сложностью $𝑂(\sqrt n)$, где 𝑛 — порядок точки 𝑃, и делает это с помощью атаки «встреча посередине» (Meet In The Middle). Когда выбрана точка с достаточно большим порядком, её решение становится неосуществимым — в этом и заключается стойкость задачи.
Например, если выбрать 𝑛 размером 256 bit, мы получим, что задача ECDLP имеет уровень безопасности 128 bit. Для сравнения: чтобы достичь того же уровня безопасности 128 bit в шифровании RSA, которое основано на задаче разложения целых чисел на множители, требуется открытый ключ размером 3072 bit. Это делает использование эллиптических кривых относительно более вычислительно эффективным.
После всего этого введения в мир эллиптических кривых перейдём к тому, что можно делать с ними в криптографическом контексте. Как мы знаем, криптографические системы обычно основаны на «трудной задаче», которую сложно решить. Например, RSA — на задаче разложения числа на множители, о которой мы упоминали, или протокол Диффи — Хеллмана — на задаче дискретного логарифма. Криптографическая система, основанная на задаче ECDLP на эллиптической кривой, относится к семейству криптографии на эллиптических кривых, или сокращённо ECC.
Начнём с истории. Представьте, что вы на вечеринке — в комнате, полной людей, где каждый может говорить с каждым и каждый слышит всех. В этой комнате также находятся Алиса и Боб, которые никогда раньше не встречались. Алисе нравится Боб, и она хочет пригласить его на свидание. Алиса немного застенчива, поэтому она хочет передать Бобу это секретное сообщение так, чтобы её не услышали остальные гости. Алиса и Боб заранее ни о чём не договаривались, и всё, что Алиса скажет Бобу, услышат все остальные гости на вечеринке. Как Алиса может передать сообщение Бобу, чтобы никто другой его не услышал?
Если вы ответили «эллиптические кривые», то вы правы!
Алиса выберет некоторую эллиптическую кривую и генератор на ней и сообщит их Бобу. А именно, Алиса передаст Бобу (и всем остальным в комнате) два параметра кривой 𝑎, 𝑏, модуль 𝑝 и генератор 𝐺. Кроме того, Алиса выберет некоторое значение $𝑑_𝐴$ в диапазоне $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$, где 𝑛 — порядок 𝐺. Значение $𝑑_𝐴$ называется закрытым ключом Алисы. Алиса вычислит точку $𝐴 = 𝑑_𝐴𝐺$, которая называется открытым ключом Алисы, и сообщит её Бобу. Аналогично Боб выберет закрытый ключ $𝑑_𝐵$, вычислит точку $𝐵 = 𝑑_𝐵𝐺$, которая называется открытым ключом Боба, и сообщит её Алисе.
Алиса возьмёт открытый ключ Боба, умножит эту точку на свой закрытый ключ и получит третью точку $𝑃_𝐴 = 𝑑_𝐴𝐵$. Аналогично Боб возьмёт открытый ключ Алисы, умножит его на свой закрытый ключ и получит свою третью точку $𝑃_𝐵 = 𝑑_𝐵𝐴$. Если мы рассмотрим точки, которые получили Алиса и Боб по отдельности, то обнаружим, что они получили одну и ту же точку! Этот факт следует из свойства ассоциативности умножения точки на константу, которое мы видели ранее:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
По завершении всего процесса Алиса и Боб смогли прийти к соглашению о некоторой точке на кривой, и ни на одном этапе ни один из них не передал эту точку другому. Информация, которую услышали все, такова: 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵. Человек, находящийся в комнате и слышащий эту информацию, не может с её помощью найти точку, о которой договорились Алиса и Боб.
Это потому, что если бы другой человек в комнате захотел найти эту точку, ему нужно было бы знать либо закрытый ключ Алисы, либо закрытый ключ Боба, чтобы умножить на них 𝐵 или 𝐴. Чтобы найти, например, закрытый ключ Алисы, он рассмотрит $𝐴 = 𝑑_𝐴𝐺$, поскольку это единственная отправленная информация, которая «содержит» закрытый ключ Алисы. Имея 𝐺 и $𝑑_𝐴𝐺$, найти $𝑑_𝐴$ эквивалентно решению задачи дискретного логарифма на эллиптических кривых, которая, как уже упоминалось, является трудной задачей.
Этот красивый протокол называется: Диффи — Хеллман на эллиптических кривых (ECDH).
Мы ещё не закончили нашу историю. Хотя Алиса и Боб договорились об общей секретной точке, Алиса так и не пригласила Боба на свидание, которого она так сильно хотела.
После того как стороны договорились об общей секретной точке, они могут использовать её в качестве ключа шифрования любого метода шифрования, например AES, и с этого момента безопасно общаться с помощью шифрования.
Обычно берут одну из координат 𝑥 или 𝑦 точки и используют её. Для обеспечения безопасности рекомендуется хешировать выбранное значение и использовать в качестве ключа шифрования только результат хеширования. На практике иногда значение слишком велико, чтобы использовать его в качестве ключа шифрования. Например, если используемая хеш-функция — SHA-1, длина её выхода составляет 160 bit, в то время как для шифрования AES требуется всего 128 bit. В таком случае принято использовать только 128 bits из 160, а остальные отбрасывать.
В любом случае, на этом этапе Алиса и Боб договариваются о ключе шифрования, и только они его знают. С этого момента они общаются с помощью шифрования, и любой подслушивающий в комнате не может понять, о чём они говорят.
Вот диаграмма протокола:
Используя согласованный ключ, Алиса шифрует сообщение «Эй, Боб, не хочешь ли ты завтра вечером сходить выпить кофе?» и передаёт зашифрованное сообщение Бобу. Боб расшифровывает сообщение ключом, который он тоже знает. Алиса надеется, что Боб ответит «да», но это не часть протокола.
В известном протоколе Диффи — Хеллмана (DH) стороны открыто передают простое число 𝑝 и генератор 𝑔, принадлежащий группе, соответствующей значению 𝑝. Алиса случайным образом генерирует закрытый ключ 𝑎 и открыто передаёт свой открытый ключ $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. Аналогично Боб случайным образом генерирует закрытый ключ 𝑏 и открыто передаёт свой открытый ключ $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. Затем Алиса берёт открытый ключ Боба и возводит его в степень своего закрытого ключа, вычисляя таким образом значение $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Точно так же Боб вычисляет значение $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. По завершении процесса Алиса и Боб смогли договориться об общем значении 𝐾, не передавая его друг другу.
Атакующий, подслушивающий их, не может найти 𝐾, имея переданные значения 𝑝, 𝑔, 𝐴, 𝐵. Для этого ему придётся найти либо закрытый ключ Алисы, либо закрытый ключ Боба. Чтобы вычислить, например, закрытый ключ Алисы, ему нужно найти 𝑎, имея 𝑔 и $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$, что является трудной задачей. Эта задача называется задачей дискретного логарифма (DLP).
Между DH, основанным на DLP, и ECDH, основанным на ECDLP, существует очень явное сходство (по сути, это одно и то же, только с префиксом EC). В обоих протоколах две стороны, общающиеся друг с другом, могут договориться о некотором общем секретном значении, заранее ничего не согласовывая. Любой, кто слушает сообщения между сторонами, будет иметь доступ к открытой информации, которую они передают друг другу, но не сможет вычислить секретное значение, общее для обеих сторон.### Второе применение эллиптических кривых — подпись сообщения Продолжим нашу историю. Скажем, Алиса и Боб сходили на свидание и приятно провели вечер вместе. На следующий день Алиса получает сообщение: «Привет, Алиса, это Боб, мне было очень хорошо с тобой вчера, и я бы хотел встретиться с тобой снова на этих выходных». Алиса подозревает, что сообщение отправил не Боб, потому что она знает, что Бобу так понравилось с ней вчера, что он не станет ждать выходных, а захочет встретиться с ней завтра! Как Алиса может убедиться, что сообщение написал именно Боб?
Если вы ответили «эллиптические кривые», то вы снова правы!
Сложность задачи ECDLP также можно использовать для подписи сообщений. Во время свидания Алиса и Боб договорились о некоторой эллиптической кривой и генераторе 𝐺 на ней. Боб сгенерировал некоторое значение $𝑑_𝐵$, называемое закрытым ключом Боба, и вычислил точку $𝑃_𝐵 = 𝑑_𝐵𝐺$, называемую открытым ключом Боба. Боб передал Алисе свой открытый ключ, чтобы она могла впоследствии проверить, действительно ли сообщение, которое она получает, подписано им.
Допустим, Боб хочет подписать некое сообщение 𝑚. Он вычислит значение $z = hash(m)$, используя некоторую безопасную хеш-функцию, и оставит из результата количество бит, равное битовой длине n — порядка генератора 𝐺. Боб сгенерирует случайное значение 𝑘 в диапазоне $1 ≤ 𝑘 ≤ 𝑛 − 1$. Затем Боб вычислит точку $𝑘𝐺 = (𝑥_1, 𝑦_1)$, возьмёт её 𝑥-координату и вычислит $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. Наконец, Боб вычислит значение $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.
Подписью сообщения 𝑚 называется пара вычисленных значений 𝑟 и 𝑠.
Предположим, что Алиса получила некое сообщение 𝑚, и его подпись состоит из пары значений 𝑟 и 𝑠. Алиса хочет убедиться, что сообщение подписал именно Боб. Алиса вычислит значение $z = hash(m)$ так же, как и Боб. Затем Алиса вычислит значения $𝑢_1 = 𝑧𝑠^{−1}$ и $𝑢_2 = 𝑟𝑠^{−1}$. Наконец, Алиса воспользуется открытым ключом Боба $𝑃_𝐵$ и вычислит точку $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. Подпись будет считаться действительной, если выполняется $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. Причина, по которой это корректно, заключается в том, что выполняется:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
Если подпись действительна, 𝑥-координата этой точки действительно должна быть равна 𝑟, как она определена в подписи сообщения. Следует отметить, что порядок генератора 𝐺, обозначаемый буквой 𝑛, должен быть простым числом; это необходимо для того, чтобы действительно можно было вычислять обратные числа в алгоритмах подписи и проверки.
Видно, что только тот, кто владеет закрытым ключом $𝑑_𝐵$, может создать действительную подпись для открытого ключа $𝑃_𝐵$. Злоумышленник, не обладающий значением $𝑑_𝐵$, не может вычислить значение 𝑠, соответствующее $𝑃_𝐵$ в подписи. Если злоумышленник захочет создать подпись для некоторого сообщения, ему придётся решить задачу ECDLP, то есть найти закрытый ключ $𝑑_𝐵$ по известным $𝐺$ и $𝑃_𝐵 = 𝑑_𝐵𝐺$, а это трудная задача.
Этот протокол подписи называется алгоритмом цифровой подписи на эллиптических кривых — Elliptic Curve Digital Signature Algorithm, сокращённо ECDSA. Протокол гарантирует, что подписанные сообщения не были изменены или подделаны, а также гарантирует, что подписавший сообщение не может отрицать, что создал его.
В отличие от протокола ECDH, где сторонам не нужно было заранее ничего согласовывать, в протоколе ECDSA стороны должны заранее договориться об открытом ключе. Только после того, как каждая сторона точно знает, что открытый ключ, которым она владеет, действительно принадлежит человеку, с которым она хочет общаться, протокол можно использовать. В противном случае проверка подписи с помощью открытого ключа, которым владеет каждая сторона, не имеет смысла.
Вернёмся к нашей истории. Алиса точно знает, что открытый ключ $𝑃_𝐵$ в её распоряжении действительно принадлежит Бобу, потому что Боб явно дал ей его на свидании. Алиса пытается проверить сообщение с его помощью и обнаруживает, что совпадения нет. конечно же! Сообщение создал и подписал кто-то другой, как Алиса и подозревала.
Вот схема протокола:
В протоколе ElGamal для подписи сообщений стороны договариваются о большом простом числе 𝑝 и генераторе 𝑔. Подписывающая сторона генерирует некоторое значение 𝑑 в диапазоне $1 ≤ 𝑑 < 𝑝 − 1$, называемое закрытым ключом, вычисляет значение $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$, называемое открытым ключом, и публикует его.
Чтобы подписать некоторое сообщение, она вычисляет значение $z = hash(m)$ и генерирует случайное значение 𝑘 в диапазоне $1 ≤ 𝑘 < 𝑝 − 1$, взаимно простое с $(p-1)$. Она вычисляет $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ и $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. Подписью сообщения m называется пара вычисленных значений 𝑟 и 𝑠.
Сторона, которая получила некое сообщение 𝑚 и его подпись, состоящую из пары значений 𝑟 и 𝑠, использует открытый ключ 𝑦 для проверки подписи, вычисляя значения $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ и $𝑢_2 = 𝑔^𝑧$. Подпись будет считаться действительной, если $𝑢_1 = 𝑢_2$. Это объясняется тем, что согласно определению 𝑠 обозначает:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, поэтому $𝑘𝑠 = 𝑧 − 𝑑𝑟$, откуда $𝑧 = 𝑘𝑠 + 𝑑𝑟$. Следовательно:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
Злоумышленник не может создать действительную подпись для открытого ключа 𝑦, не зная закрытого ключа 𝑑. Чтобы получить закрытый ключ по открытому ключу, злоумышленнику пришлось бы решить задачу DLP, которая является трудной задачей.
Здесь тоже прослеживается явное сходство между ECDSA, основанным на ECDLP, и ElGamal, основанным на DLP. В обоих случаях стороны должны заранее согласовать открытый ключ, и при каждой подписи нового сообщения необходимо генерировать случайное значение 𝑘. Кроме того, в обоих случаях злоумышленник, прослушивающий сообщения между сторонами, не может извлечь полезную информацию, которая позволила бы ему подделать подписи.
Мы увидели, как эллиптические кривые могут использоваться в криптографических системах для согласования секретного значения и для подписи сообщений. Как и всё в жизни, когда дело доходит до применения чего-либо на практике, всё не всегда идёт по плану. В остальной части статьи я представлю различные способы атаки на криптографические системы на основе ECC, которые были неправильно использованы пользователем или реализованы небезопасным образом.
Естественно, я разделяю эту часть на атаки на ECDH и атаки на ECDSA. В обоих случаях будем считать, что нам «удалась» атака, если мы находим закрытый ключ одной из сторон, и на этом остановимся. В случае ECDH этого достаточно, поскольку, имея закрытый ключ, можно вычислить общее секретное значение и всю информацию, зашифрованную с его помощью в дальнейшем. В случае ECDSA этого достаточно, потому что закрытый ключ можно использовать для подписи сообщений по нашему желанию.
SageMath — это свободное математическое программное обеспечение с открытым исходным кодом. Оно может использовать почти тот же синтаксис, что и Python, а также может использоваться как библиотека Python. Эта библиотека реализует полезные функции, связанные с эллиптическими кривыми, и поэтому очень полезна для вычислений, которые нам нужно выполнять в контексте ECC. В рамках этой статьи я предоставляю фрагменты кода, написанные на этой библиотеке. Мне показалось, что проще всего установить её в операционной системе Ubuntu, а именно версии 22.04. Для установки достаточно выполнить команду: sudo apt install sagemath.
Чтобы запустить файл, содержащий код, сохраните файл с расширением .sage и выполните команду: sage file.sage.
Кроме того, можно использовать интерпретатор, аналогично интерпретатору Python, выполнив команду: sage. Также можно создавать .py-файлы, в которых импортируется библиотека sage.all, и запускать их командой python3 file.py. Обратите внимание: при запуске файла командой sage обозначение ^ интерпретируется как возведение в степень, а при запуске через python3 — как исключающее ИЛИ (xor).
В этой статье я в основном использую следующие функции SageMath:
E.gens() - поиск генераторов на кривой EG.order() - вычисление порядка генератора Gn*G - умножение генератора G на число nn.factor() - разложение числа n на множители - функция возвращает список пар (𝑝, 𝑒), где 𝑝 — простой множитель, а 𝑒 — его показатель степени, то есть количество раз, которое 𝑝 встречается в разложении ncrt - решение системы уравнений по китайской теореме об остаткахПожалуй, самое лёгкое для атаки неправильное использование ECDH — это выбор генератора с слишком малым порядком n.
Как уже упоминалось, задачу ECDLP можно решить со сложностью $O(\sqrt{n})$. Когда 𝑛 слишком мал, например 32 бита, решение этой задачи становится реальным. Существует несколько алгоритмов, решающих эту задачу, включая Baby-Step Giant-Step, Pollard's Rho и Pollard's Lambda. Эти алгоритмы можно запускать как чёрный ящик с помощью SageMath, используя функцию discrete_log:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
В этом фрагменте кода мы выбираем параметры кривой случайным образом с ограничением, что `𝑝` имеет длину 32 бита. Это ограничение гарантирует нам, что количество точек на кривой равно $O(2^{32})$, а следовательно, порядок каждой точки на ней также не превышает $O(2^{32})$. После этого мы создаём кривую, выбираем на ней некоторый генератор, генерируем случайный закрытый ключ и вычисляем открытый ключ. Наконец, на основе генератора и открытого ключа мы вычисляем дискретный логарифм, чтобы найти закрытый ключ, и проверяем, что найденный ключ действительно корректен. Этот код занимает не более нескольких секунд для нахождения закрытого ключа.
## Порядок генератора — гладкое число
Как уже упоминалось, порядок генератора определяется как количество точек в «окружности», образованной при многократном прибавлении точки генератора к самой себе, и обозначается как `𝑛`. Если `𝑛` — составное число, которое можно разложить на меньшие простые множители, то ECDLP можно решить эффективно. Такое число называется гладким числом, и для целей этой статьи это число, которое можно разложить на достаточное количество простых множителей, каждый из которых достаточно мал, чтобы наша атака сработала. Формальное определение гладкого числа немного отличается и для нас не важно.
Интуитивно это делается путём «атаки» на каждый простой множитель по отдельности. Дана точка генератора `𝐺`, образующая очень большую «окружность», и некоторая точка `𝑃` в этой «окружности», такая что `𝑃 = 𝑘𝐺`. Большую «окружность» можно разобрать на несколько маленьких «окружностей», каждая размером с один простой множитель числа `𝑛`. В каждой маленькой «окружности» мы можем отобразить `G` и `P` в другие соответствующие точки `G'` и `P'`, которые находятся в маленькой «окружности» и удовлетворяют условию `𝑃′ = 𝑘′𝐺′`. Поскольку «окружность» мала, решить задачу и найти `𝑘′` относительно легко. Наконец, мы можем объединить все найденные маленькие `𝑘′` в искомый `𝑘` в исходной «окружности».
Алгоритм, который выполняет описанное мной, называется алгоритмом Полига — Хеллмана. Его временная сложность равна $O(\sqrt{p_{max}})$, где $p_{max}$ — наибольший простой множитель в разложении `𝑛`. Это также логично, потому что самая «тяжёлая» часть алгоритма — решение задачи ECDLP в самой большой «окружности» среди меньших «окружностей». Например, `n` может быть 128-битным числом и раскладываться на простые множители так, что наибольший из них — 30-битное число. Алгоритм снижает сложность решения задачи с $2^{64}$ до $2^{15}$, превращая её тем самым из неосуществимой в осуществимую.
К счастью, функция `discrete_log` в SageMath реализует этот алгоритм. Для запуска атаки можно просто вызвать функцию:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
В этом фрагменте кода мы определяем эллиптическую кривую и генератор в ней, и выводим простые множители её порядка. Вывод:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
Видно, что хотя порядок генератора имеет длину 128 бит, он раскладывается на простые множители так, что наибольший простой множитель равен 32 битам.
После этого, как и в предыдущей атаке, мы выбираем случайный закрытый ключ, вычисляем из него открытый ключ, а затем, имея генератор и открытый ключ, вычисляем закрытый ключ и проверяем его корректность.
Хотя мы закончили, мы ещё не увидели, как определяются «маленькие» окружности, как отобразить точки `𝐺` и `𝑃` в соответствующие точки `𝐺′` и `𝑃′`, и как объединить все маленькие решения в большое решение. Я постараюсь объяснить это здесь интуитивно, потому что следующая атака также основана на этой части.
Предположим, у нас есть «окружность» порядка `3𝑥5𝑥7 = 105`, и её генератор — `𝐺`. Мы определим точку `𝐺′ = (5𝑥7)𝐺 = 35𝐺` и рассмотрим «окружность», порождённую ею. Если мы сделаем от `𝐺′` один «шаг», то есть прибавим `𝐺′` к самой себе, это будет подобно продвижению на 35 шагов от точки `35𝐺` в исходной «окружности», и мы достигнем точки `2𝐺′ = 70𝐺`. Если мы сделаем ещё один «шаг», мы достигнем точки `3𝐺′ = 105𝐺 = 𝒪`, а если сделать ещё один «шаг» от неё, мы достигнем точки `4𝐺′ = 35𝐺 = 𝐺′`, то есть вернёмся в начальную точку. «Окружность», образованная `G′`, имеет порядок `3`, и это не совпадение, потому что по «окружности» порядка `105` можно сделать ровно `3` «шага» размером `35`. Аналогично, мы могли бы создать «окружность» порядка `5`, определив точку `𝐺′ = (3𝑥7)𝐺 = 21𝐺`, и окружность порядка `5`, определив `𝐺′ = (3𝑥5)𝐺 = 15𝐺`.
Когда мы смотрим на это с другой стороны, становится интереснее. Предположим, что в исходной «окружности» мы сделали `𝑛` шагов от точки `G` и достигли точки `𝑛𝐺`. Если в маленькой «окружности» мы также сделаем `𝑛` шагов от точки `𝐺′`, то достигнем точки `𝑛′𝐺′` такой, что `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. И почему это интересно? Потому что порядок `𝐺′` намного меньше порядка `𝐺`, и поэтому, имея `𝐺′` и `𝑛′𝐺′`, мы можем относительно легко найти `𝑛′`. Если мы сделаем это, а также сделаем это для двух других простых множителей порядка «окружности», а именно `5` и `7`, мы получим следующие значения:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
Из этих трёх значений `𝑛` легко находится с помощью китайской теоремы об остатках, и таким образом мы решаем исходную задачу.
## Порядок генератора — почти гладкое число, а закрытый ключ мал
Предположим, что, как и в предыдущей атаке, мы получили кривую, в которой порядок генератора раскладывается на простые множители, но на этот раз наибольший простой множитель слишком велик, чтобы решать её ECDLP было практично. Например, если порядок генератора равен `256 бит`, а наибольший простой множитель равен `128 бит`.
Алгоритм Полига-Хеллмана потребует около $O(2^{64})$ операций для нахождения закрытого ключа, что неосуществимо.
Если мы знаем, что используемый закрытый ключ относительно мал, его всё равно можно найти эффективно.
Предположим, что закрытый ключ имеет длину `64 бит` (вместо `256 бит`). Когда создаётся открытый ключ, генератор умножается на закрытый ключ, и вы получаете некоторую точку в «окружности», которую создаёт генератор. Хотя размер «окружности» составляет около $2^{256}$ точек, эта точка «попадёт» куда-то в «первые» $2^{64}$ точек. Между закрытым ключом и точками в «окружности», соответствующими большим значениям, нет никакого «взаимодействия».
Можно запустить алгоритм Полига-Хеллмана, но «отбросить» слишком большие «окружности», при условии, что произведение порядков оставшихся «окружностей» будет не меньше длины закрытого ключа. Если найдено достаточно малых простых множителей, произведение которых составляет не менее `64 бит`, то соответствующих «окружностей» будет достаточно, чтобы выполнить ту же атаку, которую мы видели ранее.
Если раньше нам было легко в смысле написания кода, то на этот раз нам придётся реализовывать всё самостоятельно, потому что функция `discrete_log` в SageMath не знает, что мы хотим «отбросить» некоторые простые множители. Следующий фрагмент кода делает это:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
В этом фрагменте кода мы определяем эллиптическую кривую и генератор на ней, а затем выводим простые множители её порядка. Результат:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
Порядок генератора равен `256 bit`, и он раскладывается на несколько простых множителей, причём два самых больших из них — `77 bit` и `107 bit`. Они достаточно велики, чтобы решение ECDLP было непрактичным. Затем случайным образом генерируется закрытый ключ размером `64 bit`, и вычисляется открытый ключ. На следующем шаге мы «набираем» достаточно простых множителей, пока не получим порядок длиной не менее `64 bit`. Результат:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
Можно видеть, что два наибольших множителя являются избыточными, и наибольший оставшийся множитель — 40 bit. На следующем шаге для каждого из оставшихся множителей мы вычисляем точки 𝐺′ и 𝑃′, как я объяснял ранее, и для каждой из них решаем ECDLP. Результаты и простые множители сохраняются в списках subsolutions и subgroups соответственно. Наконец, все результаты объединяются с помощью китайской теоремы об остатках в закрытый ключ, и мы проверяем, что он действительно корректен.
Изучая определение сложения точек на эллиптических кривых, мы замечаем интересное свойство: при сложении точек значение 𝑏 не используется, а используются только значения 𝑎 и 𝑝. Это означает, что сложение точек, лежащих на одной кривой, может быть осмысленным и для другой кривой, которая отличается от неё только значением 𝑏. Это, конечно, справедливо и для умножения точки на число. Если пользователь не проверяет, что точка, полученная от другой стороны в качестве открытого ключа, действительно лежит на его кривой, то он подвергает себя атаке Invalid Curve Attack.
Предположим, две стороны договорились об некоторой эллиптической кривой $E_1$. Атакующий может создать вредоносную кривую $𝐸_2$, у которой те же значения 𝑎 и 𝑝, что и у $𝐸_1$, но другое значение 𝑏. На кривой $𝐸_2$ атакующий выберет точку 𝑃, порядок которой мал, например 3. Разумеется, точка 𝑃 не будет лежать на $𝐸_1$, поскольку она удовлетворяет уравнению с другим значением 𝑏, отличным от значения из $𝐸_1$. Атакующий отправит точку 𝑃 пользователю в качестве своего открытого ключа. Допустим, пользователь не утруждает себя проверкой того, что полученная точка действительно лежит на кривой $𝐸_1$, о которой договорились стороны. Пользователь возьмёт открытый ключ, полученный от атакующего, умножит его на свой закрытый ключ и получит точку, которая должна быть общей секретной точкой, как мы видели в определении протокола ECDH. С точки зрения пользователя, он выполняет операцию умножения на кривой $𝐸_1$. Но поскольку точка 𝑃 вовсе не лежит на ней, а на $𝐸_2$, пользователь фактически вычислит операцию умножения на кривой $𝐸_2$. Затем пользователь использует общую секретную точку для продолжения связи с атакующим. Предположим, стороны используют 𝑥-координату точки в качестве ключа шифрования AES. В этом случае пользователь зашифрует некоторое сообщение и отправит его атакующему.
Поскольку порядок 𝑃 равен 3, существует только 3 возможных общих точек, которые может вычислить пользователь. Атакующий переберёт эти возможные точки и найдёт ту из них, которая соответствует ключу, успешно расшифровывающему зашифрованное сообщение, отправленное пользователем. Имея эту точку и начальную точку 𝑃, атакующий может вычислить остаток от деления закрытого ключа пользователя на число 3. Атакующий может отправлять пользователю дополнительные вредоносные точки 𝑃 с возрастающими порядками, например 5, 7 и так далее. Таким образом атакующий может собрать достаточно значений, представляющих остатки от деления закрытого ключа пользователя на небольшие числа. Наконец, атакующий может использовать китайскую теорему об остатках для вычисления закрытого ключа пользователя, так же как мы видели в предыдущей атаке.
Вот более интуитивное объяснение: атакующий может предоставить пользователю точку на очень маленькой «окружности», например длины 2. Пользователь продвинется вперёд по этой «окружности» на любое число шагов и достигнет конечной точки. Атакующий знает конечную точку пользователя, которая может быть одной из 2 возможностей. Поэтому атакующий может определить, сделал ли пользователь чётное или нечётное число шагов по окружности. Атакующий может предоставить пользователю дополнительные точки на «окружностях» длин 3, 5, 7 и так далее. Пока у атакующего не накопится достаточно таких множителей, каждый из которых содержит немного информации о числе шагов, сделанных пользователем. Наконец, атакующий может объединить все эти значения в точное число шагов, сделанных пользователем, которое и является его закрытым ключом.
Следующий код демонстрирует атаку:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
В этом фрагменте кода выбирается кривая и генератор, пользователь случайным образом генерирует закрытый ключ и использует его для всех применений протокола ECDH. Функция `find_curves_with_small_subgroup` находит пары точек и порядков, такие, что порядок каждой точки относительно мал, и точка лежит на некоторой кривой, отличающейся от исходной только значением `𝑏`. Код генерирует такие пары до тех пор, пока не будет найдено достаточное количество. Для каждой пары пользователю отправляется открытый ключ, а от него получается зашифрованное сообщение.
По зашифрованному сообщению выполняется полный перебор, чтобы найти значение закрытого ключа пользователя по модулю текущего порядка. Все эти результаты сохраняются, и в конце мы используем Китайскую теорему об остатках, чтобы вычислить закрытый ключ пользователя и проверить его корректность. В данном случае стороны договорились, что связь будет осуществляться с использованием AES, где ключ шифрования — координата `x` общей секретной точки, а IV — её координата `𝑦`.
Сложность атаки составляет $𝑂(𝑛_{𝑚𝑎𝑥})$, где $𝑛_{𝑚𝑎𝑥}$ — наибольший порядок среди порядков вредоносных точек. Это связано с тем, что самая "тяжёлая" часть атаки — полный перебор по самому большому "кругу" среди маленьких "кругов", и, к счастью для атакующего, он может почти полностью контролировать это значение. Поэтому данная атака относительно эффективна с точки зрения сложности. Как уже упоминалось, корень проблемы в данном случае в том, что пользователь не проверяет, лежит ли полученная точка вообще на кривой, с которой он работает. Кроме того, пользователь использует один и тот же закрытый ключ при каждом новом использовании ECDH, что не очень безопасно.
## Кривая сингулярна
Одно из важных свойств, которым должна обладать эллиптическая кривая для криптографической безопасности, — несингулярность. Несингулярная кривая — это кривая, у которой некоторая величина, называемая "дискриминантом" кривой, не равна нулю. Это выполняется, когда её параметры `𝑎` и `𝑏` удовлетворяют неравенству:
$4a^3 + 27b^2 ≠ 0$
Кривая, не удовлетворяющая этому неравенству, имеет "проблемную" точку, называемую `сингулярной точкой`. Существует два типа таких точек: узел (node) и касп (cusp). Узловая точка существует на кривой, имеющей своего рода петлю, которая самопересекается в сингулярной точке, и через эту точку можно провести две различные касательные к кривой.
Точка каспа — это точка, где кривая "заострена", как будто из неё выходят две линии, но в этой точке существует только одна касательная.
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
В точке типа узла имеется двойной корень, поэтому уравнение кривой можно записать в виде:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
Кривую можно "сдвинуть" влево, заменив переменную $x$ на переменную $(𝑥 + 𝑥_0)$, и привести к виду:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
Таким образом, теперь сингулярная точка находится в начале координат. Численное значение $t = (x_0-x_1)$ можно использовать для построения отображения между точками кривой и целыми числами, таким образом, что операция сложения точек на кривой будет эквивалентна операции умножения чисел. Каждой точке `(𝑥, 𝑦)` мы сопоставим число
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. В частности, паре точек `𝐺` и `𝑄` таких, что `𝑄 = 𝑛𝐺`, мы можем сопоставить числа `𝑔` и `𝑞` такие, что $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$, и это уже "обычная" проблема DLP. Чтобы проиллюстрировать этот процесс, я добавил ссылку на пример с маленькими числами в списке литературы в конце статьи. В построенном отображении мы использовали уравнения линейных прямых $y+\sqrt{t}x$ и $y-\sqrt{t}x$, и именно эти прямые соответствуют двум касательным, которые можно провести в сингулярной точке (после того как мы "сдвинули" кривую), что, по сути, и объясняет возможность применения этой атаки.
Такую проблему DLP можно эффективно решить с помощью алгоритма Полига–Хеллмана, который мы уже видели ранее, поскольку он может применяться и к целым числам, а не только к точкам кривой. В контексте точек мы видели, что алгоритм полезен, когда порядок генератора является гладким числом. В отличие от "круга" точек на кривой, который может иметь любой порядок, в поле целых чисел по модулю простого числа `𝑝` порядок равен `𝑝 − 1`. Если `𝑝 − 1` — гладкое число, то алгоритм эффективно решит проблему DLP и, таким образом, найдёт закрытый ключ `n`.
Это делает следующий фрагмент кода:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
В этом фрагменте кода мы задаём параметры эллиптической кривой и проверяем, что она действительно вырожденная. Мы находим корни полинома, соответствующего кривой, и определяем, какой из них является двойным корнем. Мы используем двойной корень, чтобы «сдвинуть» кривую, и получаем «сдвинутые» точки 𝐺 и 𝑄. Затем вычисляем $\sqrt{t}$ из найденных корней и используем его для отображения точек 𝐺 и 𝑄 в числа 𝑔 и 𝑞. Мы выводим разложение 𝑝 − 1 на простые множители (чтобы убедиться, что DLP действительно можно эффективно решить). Наконец, мы вычисляем DLP и интерпретируем результат как строку.
Результат: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
На этот раз я спрятал сообщение в самом закрытом ключе. Следует отметить, что из-за того, что это сингулярная кривая, в SageMath невозможно создать её обычным способом, определить на ней точки и выполнять с ними операции, как мы делали раньше. В этом коде я определил координаты точек как константные переменные. Чтобы вычислить точку `𝑄`, я умножил закрытый ключ на генератор самостоятельно, используя собственную реализацию алгоритма Double And Add.
## Кривая является суперсингулярной
Для эллиптической кривой по модулю `𝑝` и генератора порядка `𝑛` степень вложения кривой относительно генератора определяется как наименьшее число `k`, удовлетворяющее уравнению $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. С помощью определённых преобразований задача ECDLP может быть сведена к задаче DLP в поле порядка $𝑝^𝑘$. Обычно значение `𝑘` является очень большим числом (примерно того же размера, что и само `𝑝`), но когда оно относительно мало (скажем, меньше `6`), кривая называется `supersingular`, и решить эту задачу DLP становится возможным эффективно. Эта атака называется MOV-атакой, по имени трёх её авторов (Menezes-Okamoto-Vanstone).
Упомянутые мной преобразования — это функции, которые принимают две точки и возвращают некоторое число в поле комплексных чисел. В качестве таких преобразований можно использовать спаривание Вейля или спаривание Тейта, и мы будем использовать их как чёрный ящик. Такое преобразование `𝑇` удовлетворяет следующему свойству для любой пары точек `𝑃`, `𝑄`:
$T(mP, nQ)=T(P,Q)^{mn}$
Следовательно, имея две точки `𝐺` и `𝑄 = 𝑚𝐺`, мы можем случайным образом выбрать третью точку `𝑅` и вычислить два значения: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
Отсюда мы можем решить задачу DLP для `𝑔` и `𝑞` в поле порядка $p^k$, найдя таким образом закрытый ключ `𝑚`. Я добавил ссылку на более подробное объяснение математики, лежащей в основе этой атаки, в список литературы в конце статьи.
Следующий фрагмент кода выполняет эту атаку:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
В этом фрагменте кода мы определяем кривую и её генератор, и вычисляем значение её степени вложения, которое в данном случае равно 2, поэтому атаку практично выполнить. Мы определяем кривую, идентичную исходной кривой, за исключением того, что вычисления выполняются по модулю $𝑝^𝑘$ вместо модуля $𝑝$. Точки 𝐺 и 𝑄 также находятся на новой кривой. Затем мы находим третью точку, порядок которой делит 𝑛.
Используя третью точку, мы отображаем точки 𝐺 и 𝑄 в числа 𝑔 и 𝑞 и вычисляем для них дискретный логарифм. Наконец, мы проверяем, что полученный результат действительно корректен.
Вывод:``` Found k: 2 Calculating private key... success! The private key is: Festivus
С вычислительной точки зрения, сегодня существуют алгоритмы индексного исчисления, которые могут решить задачу DLP относительно эффективным способом, и делают это со сложностью $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. Это выражение может показаться пугающим, но по сравнению с алгоритмами ECDLP, сложность которых равна $O(\sqrt{p})=e^{O(log\ p)}$, можно видеть, что задачу DLP решить легче, при условии, что степень вложения (обозначаемая через `𝑘`) действительно мала.
## Кривая является аномальной
Если некоторая кривая обладает свойством, что порядок кривой (число точек на ней) в точности равен модулю `𝑝`, то она называется `аномальной кривой` и уязвима к атаке, называемой атакой Смарта. Эта атака использует `𝑝-адические числа`. Такое число может быть представлено в виде суммы степеней `p` (положительных и отрицательных) с коэффициентами. Формально такое число `s` представляет собой ряд вида:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
Когда коэффициенты являются целыми числами в диапазоне $0 ≤ 𝑎_𝑖 < 𝑝$, а сумма может быть бесконечной в сторону положительных степеней `p`. В таких числах мы «смотрим» на цифры справа налево, а не слева направо, и поэтому такой ряд может сходиться к некоторому значению. Такие числа принадлежат к иной системе счисления, отличной от той, к которой мы привыкли, и ведут себя совершенно иначе, чем «обычные» математические правила. Об этой теме можно написать целую отдельную статью, и для тех, кому это интересно, я включил в ссылки в конце статьи ссылку на видео, в котором этот материал изложен относительно понятно.
В любом случае, в этой атаке из заданной кривой создаётся новая кривая, которая определена над p-адическими числами. Имея две точки `𝐺` и `𝑄 = 𝑚𝐺` на исходной кривой, мы отображаем их в соответствующие точки на новой кривой. По координатам полученных точек легко вычислить `𝑚`.
Следующий код выполняет атаку:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
В этом фрагменте кода определяется функция lift, которая принимает точку на исходной кривой и сопоставляет ей точку на новой кривой. Затем мы задаём эллиптическую кривую и генератор на ней, и проверяем, что порядок кривой действительно равен p. Мы выбираем закрытый ключ и вычисляем соответствующий открытый ключ, после чего выполняем атаку. Мы определяем новую кривую над 𝑝-адическими числами и отображаем исходные точки 𝐺 и 𝑃 в соответствующие точки на новой кривой с помощью функции lift и умножения их на 𝑝.
Для каждой новой точки мы вычисляем отношение между её координатой 𝑥 и координатой 𝑦. Частное этих двух значений является решением ECDLP для исходных точек.
Результат:``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
Причина, по которой это вычисление работает, связана с тем, что количество точек на кривой равно ровно `𝑝`. Это свойство позволяет нам выполнить несколько отображений, последнее из которых отображает точки на кривой над 𝑝-адическими числами в числа по модулю $p^2$. Это отображение обладает свойством, что отношение между парой чисел, соответствующих двум исходным точкам, является в точности результатом логарифма этих двух точек. Мы оставим все эти отображения как чёрный ящик, но в конце статьи я добавил ссылки на соответствующие математические объяснения.
# Атаки на ECDSA
## Отсутствие хеширования сообщения перед подписанием
Мы видели, что в процессе подписания сообщения сначала вычисляется хеш сообщения, и старшие биты хеша используются в вычислении подписи. Предположим, что в некоторой реализации подписания и проверки подписи этот шаг хеширования пропущен, и вместо старших битов хеша берутся биты непосредственно из сообщения. В такой реализации единственная часть сообщения, которая влияет на его подпись, — это начало сообщения. Другими словами, если у нас есть сообщение и его подпись, мы можем сохранить начало сообщения и изменить остальную его часть, и подпись останется действительной. Это действительно простая атака.
Предположим, например, что вы пишете следующее сообщение своему банку и подписываете его без хеширования:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
Банк успешно проверит это сообщение и выполнит действие. Некоторый ... злоумышленник ... мог бы создать следующее сообщение:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
И используйте подпись, которую вы только что создали. Подпись также будет действительна для этого сообщения, и банк выполнит действие. Нехорошо (ну, зависит от того, для кого).
Следующий код демонстрирует атаку:```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
В этом фрагменте кода используется библиотека ecdsa и известная кривая. Мы определяем класс, который должен реализовывать хеш-функцию, но не делает этого, а оставляет сообщение как есть. Поэтому при подписании сообщения используются только первые биты исходного сообщения, а не его хеша. Затем сообщение подписывается и успешно проверяется. Далее создаётся вредоносное сообщение, и код проверяет, что подпись исходного сообщения также соответствует вредоносному сообщению.
В таком сценарии мы могли не получить закрытый ключ для генерации собственных новых подписей, но, имея одну подпись, мы можем подписывать сколько угодно сообщений, при условии, что они начинаются с одного и того же префикса.
k в разных подписяхВ рамках процесса подписания сообщения пользователь должен случайным образом сгенерировать значение 𝑘 и использовать его для подписи сообщения. Очень важно использовать разные значения 𝑘 для разных подписей. В противном случае, если пользователь использовал одно и то же значение 𝑘 в двух подписанных сообщениях вместо его повторной генерации, злоумышленник сможет вычислить закрытый ключ пользователя.
Как уже упоминалось, при подписании сообщения пользователь публично отправляет $r=x_1\ \ \ \ (mod\ p)$ и $s=k^{-1}(z+rd_A)$. Предположим, что пользователь подписал два разных сообщения, соответствующих $𝑧_1$ и $𝑧_2$, и публично отправил две пары значений $𝑟, 𝑠_1$ и $𝑟, 𝑠_2$, то есть использовал одно и то же значение 𝑘 в этих двух подписях. Заметим, что:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
Отсюда злоумышленник может найти значение 𝑘, вычислив:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
После того как злоумышленник нашёл 𝑘, он может вычислить закрытый ключ пользователя из одной из подписей. Заметим, что:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
Имея значения 𝑟, 𝑠 и 𝑧 сообщения и его подписи, а также значение 𝑘, найденное злоумышленником, злоумышленник может вычислить $d_A=r^{-1}(ks-z)$. С этого момента злоумышленник может подписывать любые сообщения от имени пользователя, чей закрытый ключ он получил.
Следующий фрагмент кода выполняет эту атаку:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
В этом фрагменте кода используется библиотека ecdsa вместе с известной кривой. Мы определяем закрытый ключ и используем его для подписания двух сообщений. Значение `𝑘` генерируется случайным образом, но остаётся одинаковым для двух подписей. Имея два сообщения и их подписи, код выполняет вычисление, которое мы рассмотрели, чтобы найти `𝑘`. Наконец, мы используем найденное значение `𝑘` для вычисления закрытого ключа, как мы видели. Вывод:```
Success!
The secret is: Mistakes were made
Интересно отметить, что эта атака фактически использовалась в 2010 году, когда Sony небезопасно реализовала свой механизм подписи в программном обеспечении консоли PlayStation. Sony использовала статическое значение 𝑘 для своих подписей, что позволило атакующим получить закрытый ключ Sony с помощью приведённых выше вычислений. Это привело к возможности подписывать любой код и заставлять PlayStation соглашаться на его выполнение. Позднее эта возможность использовалась для установки пиратских и неофициальных игр на консоль.
kЕсли пользователь выбирает 𝑘 недостаточно случайным образом, закрытый ключ может быть найден. Например, если атакующий знает, что 𝑘 находится в очень малом диапазоне значений, или некоторые байты 𝑘 известны атакующему, то можно простым перебором найти закрытый ключ пользователя по одному подписанному сообщению. Атакующий будет выполнять вычисления, которые мы видели в предыдущей атаке, для различных значений 𝑘, пока не достигнет правильного значения и не получит из него закрытый ключ.
Чтобы преодолеть эту проблему, иногда пользователи случайным образом генерируют некоторое значение, вычисляют его хеш с помощью некоторой хеш-функции и используют результат в качестве 𝑘. Этот метод может вызывать проблемы. Предположим, например, что порядок генератора 𝑛 равен 256 бит, а выбранная хеш-функция — SHA-1. Выход этой функции — число размером 160 бит. В вычислениях по модулю 𝑛 известно, что значение 𝑘 содержит 96 нулей в начале, то есть 𝑘 — относительно небольшое число. В такой ситуации говорят, что значения 𝑘 являются смещёнными, и по нескольким сообщениям, подписанным одним и тем же закрытым ключом, закрытый ключ может быть найден.
Атака основана на алгебраической структуре, называемой решёткой. Неформально решётку можно представить как множество векторов в 𝑚-мерном пространстве, которые могут быть выражены как линейная комбинация «базисных» векторов с целыми коэффициентами. Математически, если $\{b_1,\dots,b_d\}$ — базисные векторы в $ℝ^𝑚$, то соответствующая им решётка равна $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$. В этой структуре существует известная проблема: по базису решётки найти кратчайший вектор, существующий в решётке. В данном контексте неформально «короткий вектор» — это вектор, элементы которого максимально близки к нулю. Эта проблема называется проблемой кратчайшего вектора (SVP) и считается NP-трудной. Существуют алгоритмы, решающие похожую, но более простую задачу — поиск некоторого короткого вектора, то есть вектора, относительно «близкого» к кратчайшему вектору в решётке. Эта проблема называется проблемой ближайшего вектора (CVP), и один из алгоритмов, решающих её, называется алгоритмом Ленстры — Ленстры — Ловаса (LLL). В этой атаке мы будем использовать этот алгоритм как чёрный ящик.
Имея 𝑑 подписанных сообщений, можно построить решётку, содержащую вектор $(𝑘_1, \dots , 𝑘_𝑑)$, где каждый элемент вектора — значение 𝑘, соответствующее одной подписи. Алгоритм LLL найдёт приближение к кратчайшему вектору в этой решётке. Поскольку известно, что значения 𝑘 малы, существует высокая вероятность, что короткий вектор, найденный алгоритмом, будет содержать по крайней мере один правильный элемент k. Как только правильное 𝑘 найдено, закрытый ключ может быть вычислен, как мы видели в предыдущей атаке.
Чтобы построить эту решётку, необходимо определить её базисные векторы. В ссылках в конце статьи я привёл ссылку на статью, объясняющую, как определяются эти базисные векторы. Технически базисные векторы решётки могут быть представлены в виде матрицы, где каждая строка состоит из элементов одного базисного вектора. Чтобы повысить точность алгоритма LLL, рекомендуется добавить к этой матрице два столбца, содержащих информацию об ожидаемом размере значений 𝑘 и о соотношении между 𝑘 и 𝑛. Это улучшение также объясняется в приложенной мной ссылке. Следующий фрагмент кода демонстрирует эту атаку:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
В этом фрагменте кода используется стандартная кривая, выбирается закрытый ключ и из него вычисляется соответствующий открытый ключ. Создаются 3 сообщения, которые подписываются 3 случайными значениями `k`, полученными в результате работы хеш-функции SHA-1. Затем мы строим матрицу, соответствующую базису решётки, как описано в статье, и применяем к ней алгоритм LLL. После этого мы проходим по строкам полученной матрицы и проверяем, не содержится ли в одной из них корректное значение какого-либо `𝑘`.
Проверка выполняется путём вычисления закрытого ключа из потенциального `𝑘`, как мы видели в предыдущей атаке, и проверки того, что полученный ключ действительно корректен. Наконец, мы убеждаемся, что найденный закрытый ключ действительно верен. Результат выглядит так:```
success!
The secret is: I am Jack's broken heart
Сложность этой атаки равна сложности алгоритма LLL, то есть $O(d^6\ \log^3B)$, где 𝐵 — длина смещения (bias) значения 𝑘 ($2^{160}$ в нашем случае), а 𝑑 — количество подписанных сообщений (3 в нашем случае). Возникает вопрос: каково минимальное количество подписанных сообщений, которое требуется использовать, чтобы иметь возможность запустить атаку? Ответ таков:
$\displaystyle d=O(\frac {\log n}{\log n-\log B})$, где 𝑛 — порядок генератора, а 𝐵 — смещение. Объяснение этому приведено во второй ссылке из списка литературы, который я приложил к этой теме в конце статьи.
На практике вариант этой атаки можно также запускать в случаях, когда известны старшие биты 𝑘 или просто любые биты 𝑘. Атаку можно выполнить, даже если известно значение лишь одного бита, или даже если значение лишь одного бита известно с вероятностью более 50%! Но, конечно, в этих случаях для выполнения атаки требуется гораздо больше подписанных сообщений.
Мы видели, что в процессе проверки подписи подписывающая сторона отправляет проверяющей стороне пару значений 𝑟 и 𝑠. В браузерах, реализующих протокол HTTPS, например, принято передавать эту пару значений в сертификате, который также может содержать данные о кривой, которую использовала подписывающая сторона. Проверяющая сторона должна убедиться, что данные о кривой, найденные в сертификате, действительно соответствуют заранее согласованной кривой. Если это не так, могут возникнуть проблемы.
Предположим, что на некоторой кривой у Алисы есть закрытый ключ $d_A$ и соответствующий ему открытый ключ $𝑃_𝐴$, что означает $𝑃_𝐴 = 𝑑_𝐴𝐺$ для генератора 𝐺 на этой кривой. С помощью закрытого ключа $𝑑_𝐴$ Алиса может подписывать свои сообщения, как мы видели в описании протокола ECDSA. Предположим, что сторона, проверяющая подпись, также получает генератор 𝐺 от пользователя и не проверяет, что полученный от пользователя генератор действительно является согласованным генератором. Злоумышленник может отправить в качестве генератора точку, являющуюся открытым ключом Алисы, $𝐺^′ = 𝑃_𝐴$. Злоумышленник выберет в качестве «фальшивого» закрытого ключа значение $𝑑_𝐴^′ = 1$, и тогда очевидно, что $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$. Это означает, что злоумышленник может «доказать», что владеет закрытым ключом, соответствующим открытому ключу Алисы. Таким образом, злоумышленник может создать любое желаемое сообщение и вычислить для него пару значений 𝑟 и 𝑠 обычным способом с использованием $𝑑_𝐴^′$, и полученная подпись будет успешно проверена.
Интуитивно, в процессе проверки подписи подписывающая сторона доказывает, что она действительно является «владельцем» открытого ключа, который фактически является «точкой назначения» на кривой. Это связано с тем, что только подписант знает, сколько шагов нужно сделать от начальной точки, чтобы достичь точки назначения. Если проверяющая сторона не проверяет, что начальная точка, полученная от пользователя, действительно является истинной начальной точкой, то злоумышленник может решить, что начальная точка — это и есть точка назначения, а количество шагов от неё равно нулю. Все остальные части проверки подписи остаются прежними, и подпись будет успешно проверена. Эта атака называется Curveball.
Эту атаку можно обобщить с дополнительными значениями. Злоумышленник выберет некоторое значение 𝑥 и вычислит $𝐺^′ = 𝑥𝑃_𝐴$. Фальшивым закрытым ключом будет $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$. Тогда очевидно, что $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.
Следующий код демонстрирует эту атаку:```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)