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

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

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

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

Определение

Предполагается, что существует конечное поле нечетной характеристики $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

Алгоритм Монтгомери

Недостатки предыдущих алгоритмов

Описанный выше алгоритм скалярного умножения не рекомендуется использовать при просторении криптосистем на эллиптических кривых, поскольку он подвержен атаке по энергопотреблению . Шаги 3: и 5: позволяют злоумышленнику, перехватывающему значения $Q$ на очередной итерации цикла, побитово восстановить значение секретного ключа $k$.

Аналогичным проблемам подвержены более сложные алгоритмы скалярного умножения, использующие $y$-координату. Существует множество вариантов атак по ошибкам вычисления. Например можно применять атаку смены знака .

Описание алгоритма Монтгомери

Монтгомери предложил алгоритм , в котором не требуется использование $y$-координаты, что позволило значительно ускорить создание открытого ключа, а также полностью защититься от атак по энергопотреблению:

Input: k, P
Output: kP

1: Q[0] = P, Q[1] = 2P
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: return Q[0]

Предлагается в самом начале помимо точки $Q_{0}=P$ рассчитывать также точку $Q_{1}=2P$. Основная идея заключается в том, что во время очередной итерации цикла разница между точками $Q_{0}$ и $Q_{1}$ остается неизменно равной $P$. Это позволяет при помощи проективных координат быстро вычислять значение в точках $(X_{Q_{0}+Q_{1}}:\;.\;:Z_{Q_{0}+Q_{1}})$ и $(X_{2Q_{0}}:\;.\;:Z_{2Q_{0}})$, с помощью которых обновляются значения $Q_{0}$ и $Q_{1}$. В самом же конце используя $(X_{kP}:\;.\;:Z_{kP})$ вычисляется значение открытого ключа $kP$.

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

Особенность реализации

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

В статье приводится полное подробное описание вычисления проективных координат, получающихся удвоением и суммированием соответствующих значений. Всего требуется 18 операций умножения, 13 сложения и 4 возведения в квадрат для случая $A\neq -3$, и, соответственно, 23 умножения, 11 сложения и 4 возведения в квадрат иначе.

Области применения

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

Основным преимуществом криптосистемы , использующей эллиптические кривые, является относительно небольшая длина закрытого ключа (минимум 163 бита). Для примера в алгоритме RSA минимальная длина секретного ключа составляет 1024 бит. Данная возможность появляется благодаря особенности вычисления открытого ключа, задача дискретного логарифмирования для которого решается намного сложнее, чем для алгоритмов, построенных на целых числах.

RFID метки

На практике алгоритм Монтгомери применяется в RFID метках. Данные устройства применяются повсеместно для автоматической идентификации объектов. Они оснащены сильно ограниченным количеством памяти, при этом оно должно быть защищенным от злоумышленников. Также процесс считывания должен происходить быстро, например в момент оплаты или проверки автомобиля во время проезда через пропускной пункт. Здесь и помогает алгоритм Монтгомери, поскольку он эффективнее других алгоритмов с точки зрения аппаратной части (время, ресурсы), а также дает защиту от большинства атак по сторонним каналам на эллиптические кривые.

Сенсорные сети

Другим интересным применением данного алгоритма являются беспроводные сенсорные сети. Как и в случае RFID меток. Устройства сети оснащены компактными энергетически эффективными процессорами, в которых спроектированы специальные Modular Arithmetic Logic Units(MALU) для проведения вычислений на кривой, в том числе скалярного умножения. Это помогает производить безопасные и экономные вычисления.

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

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

В статье предлагается использовать вспомогательную кривую $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$

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

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

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

Простейшей идеей является проверка промежуточных значений $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]