Тезисы. Аккуратно измеряя количество времени, необходимого для операций с закрытыми ключами, злоумышленник может найти постоянный показатель
степени в схеме Диффи-Хеллмана, факторизованные ключи в RSA, а также взломать и другие криптосистемы. Если атакуемая система уязвима, то атака может быть недорогой в вычислительном отношении и часто для нее будет требоваться только известный шифрованный текст. Существующие системы потенциально уязвимы, включая криптомаркеры (tokens), сетевые криптосистемы и другие приложения, где нападающий способен сделать достаточно точные замеры времени. Представлены методы для предотвращения атаки на системы RSA и Диффи-Хеллмана. Некоторые криптосистемы должны быть пересмотрены для защиты от таких атак, а новые протоколы и алгоритмы должны включать средства для предотвращения атак временным анализом (timing attacks).
Введение
Криптосистемы часто используют различное количество времени для обработки различных входных данных. Причины этого включают оптимизацию по времени, попадания в кэш, инструкции процессора (типа умножения и деления), которые не имеют фиксированного числа тактов, а также многое другое. Скорость обычно зависит от ключа шифрования и входных данных (открытого или зашифрованного текста). В то время как известно, что, вообще говоря, временные каналы могут пропускать данные или ключи через защищенный периметр обработки, интуиция подсказывает, что временные характеристики могут раскрыть только незначительную информацию о криптосистеме (типа хэммингского веса ключа). Однако атака, представленная здесь, способна использовать измерения времени в уязвимых системах для нахождения всего секретного ключа.
Криптоанализ простого модульного возведения в степень
В алгоритмах Диффи-Хеллмана DH [2] и RSA [8] нужно вычислять R=yxmod n, где n - известен, а y может быть найден перехватом. Цель нападающего - найти секретный ключ x. Для осуществления атаки необходимо, чтобы жертва вычисляла yx mod n для нескольких значений y, где y, n и время вычислений известны атакующему. (Если секретная экспонента x будет меняться для каждой операции, атака не сработает). Необходимая информация и время вычислений могут быть получены пассивным подслушиванием, так как нападающий может записывать сообщения, посылаемые цели атаки и измерять время получения ответа для каждого y.
Атака может быть осуществлена при любой реализации алгоритма модульного возведения в степень, где время вычисления не является фиксированным, но сначала лучше рассмотреть обычный алгоритм вычисления R= yx mod n, где x - длиной w бит:
Let s0 = 1.
For k = 0 upto w-1:
If (bit k of x) is 1 then
Let Rk = (sk  y) mod n.
Else
Let Rk = sk.
Let sk+1 = Rk2 mod n.
EndFor.
Return (Rw-1).
:
Атака позволит тому, кто знает биты 0..(b-1), найти бит b. Чтобы получить экспоненту целиком, надо начать с b равным 0 и повторять атаку до тех пор, пока вся экспонента не станет известна.
Т.к. первые b бит известны, нападавший может вычислить первые b итераций цикла и найти значение sb. Следующая итерация потребует первого неизвестного бита. Если этот бит установлен в 1, то будет вычислен Rb = (sby) mod n. Если бит равен нулю, умножение будет пропущено.
Рассмотрим сначала атаку в следующем гипотетическом случае. Пусть атакуемая система использует очень быструю функцию модульного умножения, но которая иногда потребляет гораздо большее время, чем вся функция модульного возведения в степень. Тогда для некоторых значений sb и y вычисления Rb = (sby) mod n будут чрезвычайно медленны, и, используя знания о реализации атакуемой системы, нападающий может определить, каковы эти значения. Если время вычисления всей функции модульного возведения в степень мало, но при этом Rb = (sb* y) mod n должно было бы вычисляться медленно, то бит b, очевидно, равен 0. Наоборот, если долгие по времени вычисления Rb = ( sby) mod n всегда приводят к медленному модульному возведению в степень, это бит, вероятно, установлен в 1. Как только бит b станет известен, атакующий может проверить, что полное время операций медленно всякий раз, когда sb+1 = R2b mod n ожидается быть медленным. Эти же самые предположения могут использоваться и дальше, чтобы найти следующие биты.
Коррекция ошибок
Если бит b угадан неправильно, значения, вычисляемые для Rk >= b будут также неверны, и далее результат будет, в общем, случайный. Время, требуемое для умножения после ошибки не будет отражаться на полном время возведения в степень. Атака таким образом имеет свойство "обнаружения ошибки"; после неправильного предположения о значении бита не будет наблюдаться никакой значимой корреляции.
Свойство "обнаружения ошибки" может использоваться для ее коррекции. Например, нападавший может поддерживать список наиболее вероятных промежуточных экспонент наряду со значением, соответствующей правильной вероятности. Атака продолжается для единственного наиболее вероятного кандидата. Если текущее значение неправильно, оно будет иметь тенденцию опускаться в списке наиболее вероятных значений, тогда как правильное должно было бы повышаться. Методы исправления ошибок увеличивают необходимую память и процессорное время, но при этом значительно уменьшают число необходимых значений.
Общая схема атаки
Атаку можно трактовать как проблему распознавания сигналов. "Сигнал" состоит из вариаций измерения времени для известных бит, "шум" - из погрешностей измерения времени и вариаций измерения времени для неизвестных бит. Свойства "сигнала" и "шума" определяют количество замеров времени, требуемых для атаки. Пусть получено j сообщений y0, y1, ., yj-1 и им соответствующие измерения времени T0, T1, ., Tj-1. Вероятность, что предположение xb для первых b бит правильно, пропорциональна , где
t(yi,xb) - время, требуемое для первых b итераций цикла вычсиления yix mod n с использованием бит xb,
F - ожидаемая фунция распределения вероятности T-t(y,xb) по всем значениям y и правильному xb. Т.к. F определена как распределение вероятностиTi-t(yi,xb), если xb правильно, то это - лучшая функция для предсказания Ti-t(yi,xb). Обратите внимание, что измерения времени и промежуточные значения s могут использоваться для улучшения оценки F.
При правильном предположении для xb-1 имеются два возможных значения для xb. Вероятность того, что xb - является правильным, а xb' - неправильным, может быть найдена как
На практике эта формула не очень полезна, т.к. поиск F потребует слишком больших усилий.
Упрощение атаки
К счастью, нет необходимости вычислять F. Каждое наблюдение времени состоит из  , где ti - время, требуемое для умножения и возведения в степень для бита i, а e включает ошибку измерения, время на инкремент цикла и т.п. Имея предположение xb, нападающий может вычислить  для каждого значения y. Если xb правильно,то вычитая это время из T, получим   . Т.к. времена модульного умножения не зависят от друг друга и от ошибки измерения, дисперсия по всем наблюдаемым значениям, ожидается, будет равна Var(e)+(w-b)Var(t).
Однако, если только первые c < b бит угаданы правильно, ожидаемая дисперсия будет Var(e)+(w-b+2c)Var(t). Итерации с правильными предположениями уменьшают ожидаемую дисперсию на Var(t), каждая итерация после неправильного предположения увеличивает дисперсию на Var(t). Вычислять дисперсии легко, и это обеспечивает хороший способ идентификации правильного бита.
Теперь возможно оценить число значений, требуемых для атаки. Предположим, что нападавший имеет j точных времен измерения и два предположения относительно первых b битов w-битного значения, одно правильное и другое - неправильное с первой ошибкой в бите c. Для каждого предположения время измерения может быть сверено с . Если такая сверка имеет меньшую дисперсию, то это - правильное предположение. Возможно аппроксимировать ti с использованием независимых стандартных нормальных переменных. Если Var(e) незначительно, ожидаемая вероятность правильности предположения
 ,
где
X и Y - нормальные случайные переменные с законом (0, 1). Т.к. j относительно большое,  и  приблизительно нормальны с законом (0, ). Отсюда   , где Z - стандартная нормальная случайной переменная. Интегрирование для нахождения вероятности правильного предположения дает  ,
где  - область под стандартной нормальной кривой от  до x. Требуемое число значений j таким образом пропорционально длине экспоненты w. Число измерений может быть уменьшено, если нападающий может выбирать такие входные данные, чтобы иметь экстремумы времени в тех битах экспоненты, которые его интересуют.
1 2 3
8 8 8
| |
*
Обратная связь