Атака по ошибкам вычислений на эллиптические кривые, использующие алгоритм Монтгомери

Атака по ошибкам вычислений на эллиптические кривые, использующие алгоритм Монтгомери — один из способов атаки по сторонним каналам, направленный на конкретный алгоритм скалярного умножения (алгоритм Монтгомери), использующийся в криптосистемах построенных на эллиптических кривых.

Краткие сведения об эллиптических кривых

Эллиптические кривые являются надёжным инструментом, при помощи которого можно построить криптосистему с открытым ключом .

Определение

Предполагается, что существует конечное поле нечётной характеристики $p>3$, обозначаемое $F_{p}$ . Тогда в поле $F_{p}\cup \{O\}$ может быть задана ЭК в форме Вейерштрасса:

$E(F_{p})=\{(x,y):\;y^{2}=x^{3}+Ax+B;\;4A^{3}+27B^{2}\neq 0,\;\forall A,B\in F_{p}\}\cup \{O\}$

Для удобства вычислений данный вид может быть преобразован переходом к проективным координатам Якоби. В таком случае эллиптическая кривая будет иметь вид:

$E(F_{p})=\{(X:Y:Z):\;ZY^{2}=X^{3}+AZ^{2}X+Z^{3}B;\;4A^{3}+27B^{2}\neq 0,\;\forall A,B\in F_{p},\;Z\neq 0\}\cup \{O\}$

Сложение двух точек эллиптической кривой

Сложение двух точек $P$ и $Q$ на эллиптической кривой легче всего понять при помощи геометрической иллюстрации.

В простейшем случае (1), когда $P\neq Q$ сложение производится путём проведения прямой через суммируемые точки . Данная прямая пересечёт эллиптическую кривую в третьей точке $R$. Тогда симметричную эй точку $-R$ и называют суммой двух точек $P$ и $Q$ на эллиптической кривой.

Существуют и другие ситуации" (2-4), определение сложения в которых требует особого рассмотрения:

Случай (2) отражает ситуацию, в которой прямая, проходящая через суммируемые точки оказалась касательной к эллиптической кривой. Здесь полагают, что в точке Q прямая не касается эллиптической кривой, а пересекает её в двух очень близких точках так, что обе можно считать равными $Q$. Тогда можно сказать, что $Q+Q=-P$, другими словами $P+Q=-Q$

Особенность (3) в том, что получившаяся прямая параллельна оси ординат, вследствие чего третьей точки, которая бы принадлежала и прямой и эллиптической кривой не существует. Но, поскольку $Q=-P$ получается, что $P+Q=O$

Последний случай (4) — комбинация (2) и (3). Получаем, что $P+P=O$.

Скалярное умножение

Далее определим операцию умножения точек эллиптической кривой на число. Пускай выбрана точка $P$ на эллиптической кривой и целое число $k$ длиной $n$ бит. Затем путём $k$-кратного сложения точки $P$ самой с собой получается точка $kP$, лежащая на той же эллиптической кривой, в силу свойств поля, в котором производится операция многократного сложения.

Пример простейшего алгоритма скалярного умножения:

Input: k, P
Output: kP

1: Q = P
2: for i = n-2 down to 0:
3:     Q = 2Q
4:     if k[i] == 1:
5:         Q = Q + P
6: return Q

Предложенная атака

В 2008 году в статье Пьера-Алана Форке была обнаружена уязвимость алгоритма Монтгомери.

Авторы отметили, что недостаток алгоритма Монтгомери заключается в том, что вычисление значения точки на кривой производится лишь на последней итерации цикла, а во время промежуточных шагов принадлежность полученной точки эллиптической кривой не подтверждается . Отсюда возникает возможность для атаки по ошибке вычислений.

В статье предлагается использовать вспомогательную кривую $E'$. Вводимая кривой является изоморфной основной кривой $E$ в поле $F_{p^{2}}$, но не в $F_{p}$. Таким образом :

$\forall x\in F_{p}:g(x)\equiv x^{3}+ax+b\neq 0$,

если $g(x)$ является квадратичным остатком, то $x$ будет являться абсциссой точки на $E$.

В противном случае существует две возможности:

1. Рассмотреть новую группу точек на $E$ таких что $y\in F_{p^{2}}$
2. Использовать абсциссу точки на кривой $E'$, получая то же самое значение $y$

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

В своем оригинальном варианте алгоритм Монтгомери не проводил проверку принадлежности результата исходной эллиптической кривой, вследствие чего злоумышленнику необходимо было вносить ошибку лишь в самом начале вычислений. Авторы статьи про атаку предложили простое решение данной проблемы, а именно проверку того, что результат принадлежит исходной кривой. Таким образом алгоритм выглядит следующим образом:

Input: k, P
Output: kP

1: compute kP
2: if kP is on the curve, i.e. <math>x^3 + ax + b</math> is a square:
3:     return kP
4: else:
5:     return Error

.

Эта мера оказалась недостаточной, поскольку далее авторы приводят способ преодоления данной проверки.. Идея основана на изменении результата вычислений прямо перед проведением проверки. Абсцисса $x$ результата вычислений $kP$ может быть изменена злоумышленником при помощи побитового сложения $x\oplus \epsilon$, обозначаемая $kP\oplus \epsilon$, с вероятностью $1/2$ принадлежащая кривой. Само значение $\epsilon$ злоумышленнику неизвестно, но может быть определено из соображений, что вносимая ошибка изменяет только первые $s$ регистров из $n$. За $2^{s}n/s$ можно подобрать $\epsilon$, что довольно долго для больших значений $n$.

Но существует гораздо быстрый способом, который и предлагают использовать авторы. Злоумышленнику достаточно двух шагов атаки по ошибкам вычислений. Внеся в один и тот же результат различные ошибки $\epsilon$ $\epsilon '$ можно понять какие именно регистры были изменены, таким образом получив возможность обойти проверку, а далее решить задачу дискретного логарифмирования для нахождения секретного ключа $k$.

А прямо перед окончанием вычислений вносится ещё одна ошибка, для перемещения точки обратно на основную кривую.

Учитывая особенности алгоритма Монтгомери такой перенос будет незаметным с точки зрения вычислений. Дополнительно будет пройдена одна из самых часто встречающихся проверок: принадлежность итоговой точки исходной кривой.

Способы отражения атаки

Простейшей идеей является проверка промежуточных значений $Q_{0}$. Но поскольку все операции производятся в проективных координатах, непосредственное нахождение значения в точке на каждой итерации цикла будет вычислительно сложной задачей, что значительно снизит эффективность алгоритма, полученную за счёт отказа от $y$-координаты. Поэтому необходимы другие способы отражения атаки .

Защита Эбейд-Ламберта

Для избавления от дорогостоящих вычислений, предлагается оценивать значение точки $Q_{0}=(x_{0},y_{0})=(X_{0}:Y_{0}:Z_{0})$ в проективных координатах, а именно $Y_{0}$. После этого с помощью всего одной операции инверсии получится нужное для проверки $y_{0}$. Для начала, формулу для вычисления значения $y_{0}$ приводится к следующему виду, путём подстановки проективных координат точек $Q_{0}=(X_{0}:\;.\;:Z_{0})$ и $Q_{1}=(X_{1}:\;.\;:Z_{1})$:

$y_{0}={\dfrac {2B+(A+x{\dfrac {X_{0}}{Z_{0}}})(x+{\dfrac {X_{0}}{Z_{0}}})-{\dfrac {X_{1}}{Z_{1}}}(x-{\dfrac {X_{0}}{Z_{0}}})^{2}}{2y}}$, где $(x,y)$ — координаты точки $(Q_{1}-Q_{0})$

$y_{0}={\dfrac {2BZ_{1}Z_{0}^{2}+Z_{1}(AZ_{0}+xX_{0})(xZ_{0}+X_{0})-X_{1}(xZ_{0}-X_{0})^{2}}{2yZ_{1}Z_{0}^{2}}}={\dfrac {Y_{0}'}{Z_{0}'}}$

Далее с помощью одной операции инверсии получается искомое проверочное значение для $y_{0}$.

Дополнительно можно вычислить, $X_{0}'=2yX_{0}Z_{1}Z_{0}$ и произвести подстановку в уравнение кривой, получив проверочное соотношение:

$Z'(Y'^{2}-BZ'^{2})=X'(X'^{2}+AZ')$

Алгоритм LOEDAR

Более эффективным способом отражения описанной выше атаки является алгоритм LOEDAR. Авторы заявляют, что простейшей идеей являлась бы проверка того, что на каждом шаге выполнено равенство $Q_{0}+P\equiv Q_{1}$. Однако проведение такой проверки в исходных координатах затруднительно, поскольку требует непосредственного вычисления $y$-координат всех трёх точек. В проективных координатах необходимо знать $Q_{1}-P=(X_{Q_{1}-P}:\;.\;:Z_{Q_{1}-P})$, что также требует дополнительных вычислений

Предлагается использовать «верификационную точку» $Q_{v}$. Особенность заключается в том, что все вычисления и проверки будут по-прежнему осуществляться в проективных координатах $(X:\;.\;:Z)$, поскольку на любом шаге алгоритма выполняется соотношение $Q_{1}+Q_{v}=2Q_{0}$. Таким образом алгоритм будет выглядеть следующим образом:

Input: k, P
Output: kP
Commentary: Q[2] := Q_v

1: Q[0] = P, Q[1] = 2P, Q[2] = 0
2: for i = k-2 down to 0:
3:     Q[1 - k[i]] = Q[0] + Q[1]
4:     Q[k[i]] = 2Q[k[i]]
5:     Q[2] = Q[2] + Q[k[i]]
6:     # verification part
7:     (Q[2] + Q[1] == 2Q[0]) ? continue : break     
8: return Q[0]