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

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

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

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

Определение

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

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

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

$E(F_p)=\{(X:Y:Z):Z{Y}^2=X^3+A{Z}^{2}X+Z^{3}B;4A^3+27B^2\ne 0,\mathrm{\forall }A,B\in F_p,Z\ne 0\}\cup \{O\}$

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

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

В простейшем случае (1), когда $P\ne 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^{\prime }$. Вводимая кривой является изоморфной основной кривой $E$ в поле $F_{p^2}$, но не в $F_p$. Таким образом :

$\mathrm{\forall }x\in F_p:g(x)\equiv x^3+ax+b\ne 0$,

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

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

1. Рассмотреть новую группу точек на $E$ таких что $y\in F_{p^2}$
2. Использовать абсциссу точки на кривой $E^{\prime }$, получая то же самое значение $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 ϵ$, обозначаемая $kP\oplus ϵ$, с вероятностью $1/2$ принадлежащая кривой. Само значение $ϵ$ злоумышленнику неизвестно, но может быть определено из соображений, что вносимая ошибка изменяет только первые $s$ регистров из $n$. За $2^{s}n/s$ можно подобрать $ϵ$, что довольно долго для больших значений $n$.

Но существует гораздо быстрый способом, который и предлагают использовать авторы. Злоумышленнику достаточно двух шагов атаки по ошибкам вычислений. Внеся в один и тот же результат различные ошибки $ϵ$ ${ϵ}^{\prime }$ можно понять какие именно регистры были изменены, таким образом получив возможность обойти проверку, а далее решить задачу дискретного логарифмирования для нахождения секретного ключа $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=\frac{2B+(A+x\frac{X_0}{Z_0})(x+\frac{X_0}{Z_0})-\frac{X_1}{Z_1}(x-\frac{X_0}{Z_0}{)}^2}{2y}$, где $(x,y)$ — координаты точки $(Q_1-Q_0)$

$y_0=\frac{2B{Z}_1{Z}_0^2+Z_1(A{Z}_0+x{X}_0)(x{Z}_0+X_0)-X_1(x{Z}_0-X_0{)}^2}{2y{Z}_1{Z}_0^2}=\frac{{Y_0}^{\prime }}{{Z_0}^{\prime }}$

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

Дополнительно можно вычислить, ${X_0}^{\prime }=2y{X}_0{Z}_1{Z}_0$ и произвести подстановку в уравнение кривой, получив проверочное соотношение:

$Z^{\prime }(Y{\text{'}}^2-BZ{\text{'}}^2)=X^{\prime }(X{\text{'}}^2+A{Z}^{\prime })$

Алгоритм 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]