Пауль Кочер
e-mail: paul@cryptography.com

(с) Перевод Ольга Букшева, Павел Семьянов, 1998.
e-mail: psw@ssl.stu.neva.ru?subject=timing attack

Тезисы. Аккуратно измеряя количество времени, необходимого для операций с закрытыми ключами, злоумышленник может найти постоянный показатель степени в схеме Диффи-Хеллмана, факторизованные ключи в RSA, а также взломать и другие криптосистемы. Если атакуемая система уязвима, то атака может быть недорогой в вычислительном отношении и часто для нее будет требоваться только известный шифрованный текст. Существующие системы потенциально уязвимы, включая криптомаркеры (tokens), сетевые криптосистемы и другие приложения, где нападающий способен сделать достаточно точные замеры времени. Представлены методы для предотвращения атаки на системы RSA и Диффи-Хеллмана. Некоторые криптосистемы должны быть пересмотрены для защиты от таких атак, а новые протоколы и алгоритмы должны включать средства для предотвращения атак временным анализом (timing attacks).

Ключевые слова: временной анализ, криптоанализ, RSA, Диффи-Хеллман, DSS.

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

В алгоритмах Диффи-Хеллмана DH [2] и RSA [8] нужно вычислять R=y^x mod n, где n - известен, а y может быть найден перехватом. Цель нападающего - найти секретный ключ x. Для осуществления атаки необходимо, чтобы жертва вычисляла y^x mod n для нескольких значений y, где y, n и время вычислений известны атакующему. (Если секретная экспонента x будет меняться для каждой операции, атака не сработает). Необходимая информация и время вычислений могут быть получены пассивным подслушиванием, так как нападающий может записывать сообщения, посылаемые цели атаки и измерять время получения ответа для каждого y.

Атака может быть осуществлена при любой реализации алгоритма модульного возведения в степень, где время вычисления не является фиксированным, но сначала лучше рассмотреть обычный алгоритм вычисления R= y^x 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 итераций цикла и найти значение s_b. Следующая итерация потребует первого неизвестного бита. Если этот бит установлен в 1, то будет вычислен R_b = (s_bЋy) mod n. Если бит равен нулю, умножение будет пропущено.

Рассмотрим сначала атаку в следующем гипотетическом случае. Пусть атакуемая система использует очень быструю функцию модульного умножения, но которая иногда потребляет гораздо большее время, чем вся функция модульного возведения в степень. Тогда для некоторых значений s_b и y вычисления R_b = (s_bЋy) mod n будут чрезвычайно медленны, и, используя знания о реализации атакуемой системы, нападающий может определить, каковы эти значения. Если время вычисления всей функции модульного возведения в степень мало, но при этом R_b = (s_b* y) mod n должно было бы вычисляться медленно, то бит b, очевидно, равен 0. Наоборот, если долгие по времени вычисления R_b = ( s_bЋy) mod n всегда приводят к медленному модульному возведению в степень, это бит, вероятно, установлен в 1. Как только бит b станет известен, атакующий может проверить, что полное время операций медленно всякий раз, когда s_b+1 = R²_b mod n ожидается быть медленным. Эти же самые предположения могут использоваться и дальше, чтобы найти следующие биты.

Если бит b угадан неправильно, значения, вычисляемые для R_{k >= b} будут также неверны, и далее результат будет, в общем, случайный. Время, требуемое для умножения после ошибки не будет отражаться на полном время возведения в степень. Атака таким образом имеет свойство "обнаружения ошибки"; после неправильного предположения о значении бита не будет наблюдаться никакой значимой корреляции.

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

Атаку можно трактовать как проблему распознавания сигналов. "Сигнал" состоит из вариаций измерения времени для известных бит, "шум" - из погрешностей измерения времени и вариаций измерения времени для неизвестных бит. Свойства "сигнала" и "шума" определяют количество замеров времени, требуемых для атаки. Пусть получено j сообщений y₀, y₁, ., y_j-1 и им соответствующие измерения времени T₀, T₁, ., T_j-1. Вероятность, что предположение x_b для первых b бит правильно, пропорциональна, где

t(y_i,x_b) - время, требуемое для первых b итераций цикла вычсиления y_i^x mod n с использованием бит x_b,

F - ожидаемая фунция распределения вероятности T-t(y,x_b) по всем значениям y и правильному x_b. Т.к. F определена как распределение вероятностиT_i-t(y_i,x_b), если x_b правильно, то это - лучшая функция для предсказания T_i-t(y_i,x_b). Обратите внимание, что измерения времени и промежуточные значения s могут использоваться для улучшения оценки F.

При правильном предположении для x_b-1 имеются два возможных значения для x_b. Вероятность того, что x_b - является правильным, а x_b' - неправильным, может быть найдена как

На практике эта формула не очень полезна, т.к. поиск F потребует слишком больших усилий.

К счастью, нет необходимости вычислять F. Каждое наблюдение времени состоит из, где t_i - время, требуемое для умножения и возведения в степень для бита i, а e включает ошибку измерения, время на инкремент цикла и т.п. Имея предположение x_b, нападающий может вычислить для каждого значения y¹. Если x_b правильно,то вычитая это время из T, получим . Т.к. времена модульного умножения не зависят от друг друга и от ошибки измерения, дисперсия по всем наблюдаемым значениям, ожидается, будет равна Var(e)+(w-b)Var(t). Однако, если только первые c < b бит угаданы правильно, ожидаемая дисперсия будет Var(e)+(w-b+2c)Var(t). Итерации с правильными предположениями уменьшают ожидаемую дисперсию на Var(t), каждая итерация после неправильного предположения увеличивает дисперсию на Var(t). Вычислять дисперсии легко, и это обеспечивает хороший способ идентификации правильного бита.

Теперь возможно оценить число значений, требуемых для атаки. Предположим, что нападавший имеет j точных времен измерения и два предположения относительно первых b битов w-битного значения, одно правильное и другое - неправильное с первой ошибкой в бите c. Для каждого предположения время измерения может быть сверено с . Если такая сверка имеет меньшую дисперсию, то это - правильное предположение. Возможно аппроксимировать t_i с использованием независимых стандартных нормальных переменных. Если Var(e) незначительно, ожидаемая вероятность правильности предположения

X и Y - нормальные случайные переменные с законом (0, 1). Т.к. j относительно большое, и приблизительно нормальны с законом (0,). Отсюда , где Z - стандартная нормальная случайной переменная. Интегрирование для нахождения вероятности правильного предположения дает , где - область под стандартной нормальной кривой от до x. Требуемое число значений j таким образом пропорционально длине экспоненты w. Число измерений может быть уменьшено, если нападающий может выбирать такие входные данные, чтобы иметь экстремумы времени в тех битах экспоненты, которые его интересуют.

На рис. 1 показано распределение выполнения модульного умножения 10⁶ раз. Для этого использовался пакет RSAREF [10] на 120-MHz компьютере Pentium с ОС MS-DOS. Распределение было построено, замеряя время одного миллиона вычислений (aЋb mod n), где a и b получались как результат фактических операций модульного возведения в степень со случайными входными данными. В качестве n использовалось первое 512-битное простое число из демонстрационной программы метода Диффи-Хеллмана пакета RSAREF. Все наиболее отклонившиеся значения измерений (которые заняли более 1300 мкс) были отвергнуты. Распределение на рис. 1 имеет мат. ожидание Њ = 1167.8 мкс и стандартное отклонение = 12.01 мкс. Ошибка измерения мала; испытания проводились дважды и средняя разница между измерениями составила менее 1 мкс. RSAREF использует одну и ту же функцию для возведения в квадрат и умножения; таким образом времена возведения в квадрат и умножения имеют идентичные распределения.

RSAREF вычисляет заранее y² mod n и y³ mod n и обрабатывает сразу два бита. Всего, 512-битное модульное возведение в степень со случайным показателем степени из 256 бит требует 128 итераций цикла модульного умножения и общее количество действий модульного умножения и возведения в квадрат приблизительно 352, т.к. каждая итерация выполняет два действия возведения в квадрат и, если любой из двух бит не 0, одно умножение. Атака может быть скорректирована для этого случая, чтобы прибавлять пару бит и оценивать четыре значения кандидата в каждой позиции экспоненты вместо двух.

Так как модульные умножения потребляют наибольшее количество общего времени, ожидается, что распределение времени будет приблизительно нормально с законом (Њ, ), где Њ >= 1167.8Ћ352 = 411065.6 мкс и = 225 мкс. Рисунок 2 показывает измерения из 5000 фактических действий, использующих тот же самый компьютер и модуль n, где получилось распределение с Њ = 419,901 мкс и = 235 мкс.

При 250 измерениях времени вероятность того, что вычитание времени правильной итерации из каждого значения будет сокращать общую дисперсию на большую величину, чем вычитание неправильной итерации, оценивается формулой , где j=250, b=1, c=0 и w=127. (Имеются 128 итераций цикла в RSAREF для экспоненты в 256 бит, но первая итерация игнорируется). Правильные предположения таким образом ожидаются с вероятностью . 5000 значений из рисунка 2 были разделены на 20 групп по 250 в каждой, и сравнивались дисперсии, получаемые при вычитании времени для неправильных и правильных итераций цикла, для каждой из 127 пар бит. Из 2450 испытаний, в 2168 дисперсия после вычитания времени неправильного цикла была больше, чем после вычитания времени правильного, составив вероятность 0.885. Первые биты наиболее трудны для анализа, но по мере увеличения b вероятность должна улучшаться. (Испытания не использовали этого свойства). Важно отметить, что использовались точные измерения времени; погрешности измерений с относительно большим отклонением по сравнению с временем вычисления модульного возведения в степень, будут увеличивать размер выборки.

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

Большинство вариаций времени в модульном умножении обычно вызывает сокращение модульных операций. Умножение Монтгомери [6] устраняет необходимость сокращения mod n и, в результате, имеет тенденцию уменьшать значимость временных характеристик. Однако, некоторые вариации все же остаются. Если оставшийся "сигнал" не затмевается ошибками измерения, дисперсия в t_b и дисперсия были бы сокращены пропорционально и атака еще бы сработала. Однако, если ошибка измерения e большая, то требуемое число значений будет увеличиваться пропорционально .

Китайская теорема об остатках (КТО) также часто используется, чтобы оптимизировать операции в RSA. При ее использовании сначала вычисляются y mod p и y mod q, где y - сообщение. Эти первоначальные шаги могут быть уязвимыми для временных атак. Простейшая из них состоит в том, что нужно выбрать значения y, которые являются близкими к p или q, и, используя измерения времени, выяснить, является ли предполагаемое значение меньше, чем фактическое значение p (или q). Если y - меньше, чем p, то вычисление y mod p не нужно, в то время как если y больше, чем p, то для вычисления y mod p необходимо вычитание p по крайней мере один раз. Также, если сообщение чуть-чуть больше, чем p, y mod p будет иметь первые нулевые биты, что может сократить время, требуемое для первого шага умножения. Особенности временных характеристик зависят от реализации. Модульная функция сокращения RSAREF с 512-битным модулем на компьютере Pentium с y, выбранным случайно между 0 и 2p, занимает в среднем 42.1 мкс, если y < p, и 73.9 мкс, если y > p. Время измерения для многих y может использоваться для последовательной аппроксимации p.

В некоторых случаях возможно улучшить атаку на RSA с КТО, если использовать известный (не выбранный) шифрованный текст, сокращая число требуемых сообщений и делая возможными атаки на цифровые подписи RSA. Сокращение модульных операций выполняется вычитанием нескольких модулей сразу, и вариации времени, которые можно использовать, возникают за счет разного количества шагов "сравнения-вычитания". Например, цикл деления RSAREF выполняет целочисленное деление старших двух цифр y на старшую цифру p, умножает p на частное, сдвигает влево на соответствующее число цифр, а затем вычитает результат из y. Если результат больше, чем p (сдвинутый влево), то выполняется дополнительное вычитание. Решение, делать ли дополнительное вычитание в первом цикле алгоритма деления, обычно зависит только от y (который известен) и старших двух цифр p. Временной анализ может быть использован для определения старших цифр p. Например, полный перебор по всем возможным значениям для старших двух цифр p (или более эффективные методы) может установить значение, для которого наблюдаемое время коррелирует наиболее близко с ожидаемым количеством действий вычитания. Как и в случае атаки для метода Диффи-Хеллмана, как только одна цифра p будет найдена, измерения времени могут многократно использоваться, чтобы найти последующие цифры.

Еще не известно, может ли быть приспособлен временной анализ, чтобы непосредственно нападать на возведение в степень по модулю p и q, выполняемых с помощью КТО.

Стандарт цифровой подписи (Digital Signature Standart, DSS) вычисляет s=(k^-1(H(m)+x Ћ r)) mod q, где r and q известны атакующему, k^-1 обычно вычислено заранее, H(m) - хэш сообщения, а x - секретный ключ. На практике сначала вычисляется (H(m) + x Ћ r) mod q, а затем умножается на k^-1 (mod q).

Если функция модульного сокращения не выполняется в фиксированное время, время полной подписи должно коррелировать со временем вычисления (x Ћ r mod q). Атакующий может вычислить и скомпенсировать время, требуемое для вычисления H(m). Так как H(m) имеет приблизительно тот же размер, что и q, его сложение оказывает несущественное влияние на время модульного сокращения. Наиболее значимые биты x Ћ r обычно используются первыми в модульном сокращении. Они зависят от r, который известен, и от наиболее значимых бит секретного значения x. Таким образом, должна существовать корреляция между значениями старших битов x и общим временем модульного сокращения. Используя самые большие вероятности по значениям, нападавший может попытаться идентифицировать старшие биты x. Чем больше бит x становится известно, тем больше и бит x Ћ r становится известно, позволяя нападавшему моделировать все больше итераций цикла модульного сокращения, атакуя все новые биты x. Если k^-1 - вычислено заранее, подписи DSS требуют всего 2 операции модульного умножения, потенциально производящие временной шум, который должен быть отфильтрован.

Наиболее очевидный путь предотвращения атак временным анализом состоит в том, чтобы все действия занимали точно одно и то же временя. К сожалению, это часто бывает трудно. Создание программного обеспечения, особенно платформо-независимого, таким образом, чтобы оно выполнялось в фиксированное время, весьма трудно, потому что оптимизация компилятора, попадания в программный кэш, время выполнения инструкций и другие факторы могут внести неожиданные колебания во время исполнения. Если для задержки возвращаемых результатов до определенного времени используется таймер, то факторы типа "отклика системы" (responsiveness) или энергопотребления все еще могут служить признаками фактического окончания операции. Также некоторые операционные системы показывают процент использования ЦПУ процессом. Более того, реализации с фиксированным временем будут медленными; большинство оптимизаций не сможет быть использовано, так как все действия должны занимать время, исполнения самой медленной операции. (Примечание: если необязательный шаг R_i = (s_i Ћ y) mod n выполнять всегда, то такую реализацию нельзя назвать выполняющейся в фиксированное время, т.к. атакующий может использовать временные характеристики возведения в квадрат и последующих действий цикла).

Другой подход состоит в том, чтобы сделать измерения времени настолько неточными, чтобы атака стала невыполнимой. Случайные задержки, добавленные к процессу, увеличат необходимое количество шифрованного текста для нападающего, но он сможет преодолеть это увеличением числа измерений. Требуемое число значений грубо оценивается как квадрат шума. Например, если модульное возведение в степень, временные характеристики которой имеют стандартное отклонение 10 мс, может быть взломано за 1000 измерений времени, добавление случайной нормально распределенной задержки со стандартным отклонением в 1 сек. потребует приблизительно = 10⁷ значений. (Примечание: задержка должна быть несколько секунд, чтобы ее стандартное отклонение было бы в 1 секунду). Хотя 10⁷ значений - больше, чем наибольшее возможное количество значений, которое можно собрать, фактор безопасности в 10⁷ обычно не считается достаточно адекватным.

К счастью, имеется и лучшее решение. Методы, используемые для скрытия подписей [1], могут быть приспособлены, чтобы предотвратить знание атакующего входных данных к модульной функции возведения в степень. Перед вычислением модульной экспоненты, выберите случайную пару (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).

Вычисление инверсий mod n медленно, поэтому не практично выбирать новую случайную (v_i,v_f) пару для каждой новой экспоненты. Более того, само вычисление v_f = (v_i^-1)^x mod n может быть подвергнуто временному анализу. Однако (v_i,v_f) пары не должны быть использоваться повторно, так как они могут быть раскрыты временным анализом, что делает секретную экспоненту уязвимой. Эффективное решение этой проблемы - модернизация v_i and v_f перед каждым шагом модульного возведения в степень, вычисляя v_i' = v_i² and v_f' = v_f². Общие затраты на это будут малы (2 модульных возведений в квадрат, которые может быть вычислены заранее, плюс 2 модульных умножения). Возможно использовать и более сложную модернизацию пары, используя порядки выше 2, умножение на другую пару (v_i,v_f) и т.п., но это не привнесет новых преимуществ.

Если (v_i,v_f) хранится в секрете, то нападающий не имеет никакой полезной информации относительно входных данных для функции модульного возведения с степень. Следовательно, максимум того, что атакующий может узнать, - это общее распределение времени для действий возведения в степень. Практически, эти распределения близки к нормальным и 2^w экспонент нельзя различить. Однако, специально разработанная злоумышленником функция модульного возведения в степень могла бы теоретически иметь распределение с острой пиками, соответствующими битам экспоненты, и в этом случае скрытие, вероятно, не предотвратит временной анализ.

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

Временной анализ может в принципе использоваться против других криптосистем, включая симметричные. Например, в программной реализации DES [4] 28-битные значения С и D часто вращаются (rotate), используя условие, которое проверяет, должен ли один бит быть обернут вокруг. Дополнительное время, требуемое, чтобы переместить отличные от нуля биты, может слегка сказаться на производительности шифрования или на времени подготовки (setup) ключей. Производительность шифра таким образом может показать хаммингский вес ключа, что в среднем предоставит бит ключевой информации. IDEA [3] использует функцию $f()$ с умножением по модулю (2¹⁶ + 1), которое будет обычно не выполняться в фиксированное время. RC5 [7] будет под угрозой на платформах, где битовое вращение выполняется в переменное время. Попадания в программный кэш могут дать злоумышленнику временные характеристики Blowfish [11], SEAL [9], DES и другие шифров, если таблицы в памяти не используются одинаково для каждой зашифровки. Дополнительные исследования необходимы для того, чтобы определить являются ли конкретные реализации уязвимы и, если это так, то степень их уязвимости. На сегодняшний день было подробно изучено только несколько определенных систем, а атаки против умножения Монтгомери/КТО в реализациях RSA и DSS пока что являются чисто теоретическими. Также могут быть возможны дальнейшие дополнения к атакам. Прямая атака на p и q в RSA с использованием КТО была бы особенно важна.

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

Я благодарен Matt Blaze, Joan Feigenbaum, Martin Hellman, Phil Karn, Ron Rivest и Bruce Schneier за их поддержку, полезные комментарии и предложения по улучшению рукописи.

1. D. Chaum, "Blind Signatures for Untraceable Payments," Advances in Cryptology: Proceedings of Crypto 82, Plenum Press, 1983, pp. 199-203.
2. W. Diffie and M.E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, IT-22, n. 6, Nov 1976, pp. 644-654. :
3. X. Lai, On the Design and Security of Block Ciphers, ETH Series in Information Processing, v. 1, Konstanz: Hartung-Gorre Verlag, 1992. :
4. National Bureau of Standards, "Data Encryption Standard," Federal Information Processing Standards Publication 46, January 1977. :
5. National Institute of Standards and Technology, "Digital Signature Standard," Federal Information Processing Standards Publication 186, May 1994. :
6. P.L. Montgomery, "Modular Multiplication without Trial Division," Mathematics of Computation, v. 44, n. 170, 1985, pp. 519-521. :
7. R.L. Rivest, "The RC5 Encryption Algorithm," Fast Software Encryption: Second International Workshop, Leuven, Belgium, December 1994, Proceedings, Springer-Verlag, 1994, pp. 86-96. :
8. R.L. Rivest, A. Shamir, and L.M. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, 21, 1978, pp. 120-126. :
9. P.R. Rogaway and D. Coppersmith, "A Software-Optimized Encryption Algorithm," Fast Software Encryption: Cambridge Security Workshop, Cambridge, U.K., December 1993, Proceedings, Springer-Verlag, 1993, pp. 56-63. :
10. RSA Laboratories, "RSAREF: A Cryptographic Toolkit," Version 2.0, 1994, available via FTP from rsa.com. :
11. B. Schneier, "Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish)," Fast Software Encryption: Second International Workshop, Leuven, Belgium, December 1994, Proceedings, Springer-Verlag, 1994, pp. 191-204.

:

¹. В статье нигде не говорится о требованиях, предъявляемых к производительности компьютера атакующего. Из этой фразы можно сделать вывод, что она должна быть такой же, как у атакуемого компьютера. - Прим. пер.