Атака по времени

Алгоритм быстрого возведения в степень, используемый алгоритмами Диффи-Хеллмана и RSA, выполняет следующую операцию с секретным ключом ${\displaystyle R=y^{x}{\bmod {n}}}$ , где n — часть открытого ключа (RSA) или константа (Диффи-Хеллман) и y может быть подслушан. Цель атакующего — получить секретный ключ x. Жертва вычисляет ${\displaystyle y^{x}{\bmod {n}}}$ для нескольких значений y. w — битовая длина ключа x.

${\displaystyle Let~s_{0}~=~1}$
${\displaystyle For~k=0~upto~w-1:}$
  ${\displaystyle If~(bit~k~of~x)~is~1~then}$
     ${\displaystyle LetR_{k}=(s_{k}\cdot y){\bmod {n}}}$
  ${\displaystyle Else}$
    ${\displaystyle Let~R_{k}~=~s_{k}}$
  ${\displaystyle Let~s_{k+1}=R_{k}^{2}{\bmod {n}}}$
${\displaystyle EndFor}$
${\displaystyle Return~(R_{w-1})}$

Атака позволяет, зная биты 0..(b-1), найти бит b. Чтобы получить весь показатель степени, можно начать с b=0 и продолжать до тех пор, пока вся экспонента не станет известна.

Зная первые b бит числа x, атакующий может вычислить первые b итераций цикла ${\displaystyle For}$ и найти значение ${\displaystyle s_{b}}$. Следующая итерация задействует первый неизвестный бит x. Если он равен 1, будет произведено вычисление ${\displaystyle R_{b}=(s_{b}\cdot y){\bmod {n}}}$, если 0, то операция будет пропущена.

Для оптимизации операций с секретным ключом в RSA часто используется Китайская теорема об остатках. Сначала вычисляются ${\displaystyle y{\bmod {p}}}$ и ${\displaystyle y{\bmod {q}}}$, где y — сообщение. Простейшая атака заключается в выборе y, близких к p или q. Если y меньше p, ${\displaystyle y{\bmod {p}}}$ не сделает ничего, а если ${\displaystyle y>p}$, потребуется вычесть p из y хотя бы один раз. Также, если y незначительно больше p, то ${\displaystyle y{\bmod {p}}}$ будет иметь старшие биты равными нулю, что может сократить время первого умножения. Специфические временные характеристики зависят от реализации.

Примеры атак на RSA: Timing attacks on RSA и Атака по времени выполнения на RSA

Алгоритм Digital Signature Standard вычисляет ${\displaystyle s=(k^{-1}(H(m)+x\cdot r)){\bmod {q}}}$, где p и q известны атакующему, а ${\displaystyle k^{-1}}$ вычислено заранее, H(m) — хеш сообщения, x -секретный ключ. На практике сначала вычисляется ${\displaystyle (H(m)+x\cdot r){\bmod {q}}}$ а затем домножается на ${\displaystyle k^{-1}{\bmod {q}}}$. Атакующий может вычислить H(m) и сделать соответствующую поправку. Так как H(m) примерно такого же размера как и q, сложение оказывает незначительное влияние на операцию редуцирования в методе возведения в степень Монтгомери (en). Наибольшее значение будут иметь старшие биты ${\displaystyle x\cdot r}$. Значение r известно. Между старшими битами x и временем выполнения операции редуцирования Монтгомери существует взаимосвязь. Если ${\displaystyle k^{-1}}$ вычислено заранее, подпись сообщения требует только двух операций модульного умножения, таким образом количество дополнительно вносимого шума становится относительно небольшим.

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

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

Приёмы, используемые для создания слепых подписей (см. также Blinding) могут быть приспособлены для предотвращения раскрытия атакующим входных данных для операции возведения в степень по модулю. Перед вычислением модульной экспоненты выберем случайную пару ${\displaystyle (v_{i},v_{f})}$, такую что ${\displaystyle v_{f}^{-1}=v_{i}^{x}{\bmod {n}}}$. Для Диффи-Хеллмана проще сначала выбрать случайное ${\displaystyle v_{i}}$ а затем вычислить ${\displaystyle v_{f}={(v_{i}^{-1})^{x}}{\bmod {n}}}$. Для RSA быстрее выбрать случайное ${\displaystyle v_{f}}$ взаимо-простое с n, а затем вычислить ${\displaystyle v_{i}={(v_{f}^{-1})}^{e}{\bmod {n}}}$, где e — часть открытого ключа. Перед выполнением операции возведения в степень по модулю, входное сообщение должно быть умножено на ${\displaystyle v_{i}{\pmod {n}}}$, а затем результат должен быть исправлен умножением на ${\displaystyle v_{f}{\pmod {n}}}$. Система должна отбрасывать сообщения равные ${\displaystyle 0{\pmod {n}}}$.

Вычисление обратного по модулю считается медленной операцией, поэтому часто генерирование новой пары ${\displaystyle (v_{i},v_{f})}$ для каждой операции возведения в степень является непрактичным. Однако их и нельзя использовать повторно, так как они сами могут быть подвергнуты атаке по времени. Существует решение: обновлять ${\displaystyle v_{i}}$ и ${\displaystyle v_{f}}$ перед каждой операцией возведения в степень, вычисляя ${\displaystyle v_{i}^{'}=v_{i}^{2}}$ и ${\displaystyle v_{f}^{'}=v_{f}^{2}}$.

• Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996: 104—113.
• David Brumley, Dan Boneh. Remote timing attacks are practical. USENIX Security Symposium, August 2003.