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

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

Криптосистемы часто тратят немного разное количество времени на обработку различных входных данных. Причинами тому могут быть оптимизации производительности, пропускающие лишние операции, ветвление и условные выражения (condition statements), чтение данных из кэша в оперативной памяти, команды процессора (такие как умножение и деление) исполняющиеся за недетерминированное время и другие. Характеристики производительности обычно зависят как от ключа шифрования, так и от входных данных. При этом время, затрачиваемое на выполнение определённых запросов, может стать источником утечки информации о системе. Насколько такая информация может помочь злоумышленнику, зависит от многих параметров, таких как: дизайн криптосистемы, процессор, обслуживающий систему, используемые алгоритмы, соответствующие детали реализации, контрмеры, принятые против атаки по времени, точность проводимых измерений задержек.

Атака на алгоритм быстрого возведения в степень

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

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

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

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

Использование китайской теоремы об остатках

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

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

Временной криптоанализ DSS

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

Маскировка временных характеристик

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

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

Предотвращение атак

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

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