Difference between revisions of "Тайминг-атака"

From CryptoWiki
Jump to: navigation, search
(Криптоанализ простого модульного возведения в степень)
 
Line 85: Line 85:
 
Временной анализ может в принципе использоваться против других криптосистем, включая симметричные. Например, в программной реализации DES [4] 28-битные значения С и D часто вращаются (rotate), используя условие, которое проверяет, должен ли один бит быть обернут вокруг. Дополнительное время, требуемое, чтобы переместить отличные от нуля биты, может слегка сказаться на производительности шифрования или на времени подготовки (setup) ключей. Производительность шифра таким образом может показать хаммингский вес ключа, что в среднем предоставит [[File:Eqn24.gif]] бит ключевой информации. IDEA [3] использует функцию $f()$ с умножением по модулю (216 + 1), которое будет обычно не выполняться в фиксированное время. RC5 [7] будет под угрозой на платформах, где битовое вращение выполняется в переменное время. Попадания в программный кэш могут дать злоумышленнику временные характеристики Blowfish [11], SEAL [9], DES и другие шифров, если таблицы в памяти не используются одинаково для каждой зашифровки. Дополнительные исследования необходимы для того, чтобы определить являются ли конкретные реализации уязвимы и, если это так, то степень их уязвимости. На сегодняшний день было подробно изучено только несколько определенных систем, а атаки против умножения Монтгомери/КТО в реализациях RSA и DSS пока что являются чисто теоретическими. Также могут быть возможны дальнейшие дополнения к атакам. Прямая атака на p и q в RSA с использованием КТО была бы особенно важна.
 
Временной анализ может в принципе использоваться против других криптосистем, включая симметричные. Например, в программной реализации DES [4] 28-битные значения С и D часто вращаются (rotate), используя условие, которое проверяет, должен ли один бит быть обернут вокруг. Дополнительное время, требуемое, чтобы переместить отличные от нуля биты, может слегка сказаться на производительности шифрования или на времени подготовки (setup) ключей. Производительность шифра таким образом может показать хаммингский вес ключа, что в среднем предоставит [[File:Eqn24.gif]] бит ключевой информации. IDEA [3] использует функцию $f()$ с умножением по модулю (216 + 1), которое будет обычно не выполняться в фиксированное время. RC5 [7] будет под угрозой на платформах, где битовое вращение выполняется в переменное время. Попадания в программный кэш могут дать злоумышленнику временные характеристики Blowfish [11], SEAL [9], DES и другие шифров, если таблицы в памяти не используются одинаково для каждой зашифровки. Дополнительные исследования необходимы для того, чтобы определить являются ли конкретные реализации уязвимы и, если это так, то степень их уязвимости. На сегодняшний день было подробно изучено только несколько определенных систем, а атаки против умножения Монтгомери/КТО в реализациях RSA и DSS пока что являются чисто теоретическими. Также могут быть возможны дальнейшие дополнения к атакам. Прямая атака на p и q в RSA с использованием КТО была бы особенно важна.
  
 +
 +
[[Анонимные сети#Глоссарий | На главную страницу раздела]]
  
 
'' Солдатова Е.П., Углов Н.Д. ''
 
'' Солдатова Е.П., Углов Н.Д. ''

Latest revision as of 18:17, 6 December 2013

Contents

Введение

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

Криптоанализ простого модульного возведения в степень

В алгоритмах Диффи-Хеллмана DH и RSA нужно вычислять R=yx mod 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 = (sbЋy) mod n. Если бит равен нулю, умножение будет пропущено.

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

Коррекция ошибок

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

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

Общая схема атаки

Атаку можно трактовать как проблему распознавания сигналов. "Сигнал" состоит из вариаций измерения времени для известных бит, "шум" - из погрешностей измерения времени и вариаций измерения времени для неизвестных бит. Свойства "сигнала" и "шума" определяют количество замеров времени, требуемых для атаки. Пусть получено j сообщений y0, y1, ., yj-1 и им соответствующие измерения времени T0, T1, ., Tj-1. Вероятность, что предположение xb для первых b бит правильно, пропорциональна 30.gif, где

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' - неправильным, может быть найдена как 31.gif

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

Упрощение атаки

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

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

76.gif, где

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

Экспериментальные результаты

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

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

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

Fig1.gif, Fig2.gif

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

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

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

Стандарт цифровой подписи (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) или энергопотребления все еще могут служить признаками фактического окончания операции. Также некоторые операционные системы показывают процент использования ЦПУ процессом. Более того, реализации с фиксированным временем будут медленными; большинство оптимизаций не сможет быть использовано, так как все действия должны занимать время, исполнения самой медленной операции. (Примечание: если необязательный шаг Ri = (si Ћ y) mod n выполнять всегда, то такую реализацию нельзя назвать выполняющейся в фиксированное время, т.к. атакующий может использовать временные характеристики возведения в квадрат и последующих действий цикла).

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

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

К счастью, имеется и лучшее решение. Методы, используемые для скрытия подписей [1], могут быть приспособлены, чтобы предотвратить знание атакующего входных данных к модульной функции возведения в степень. Перед вычислением модульной экспоненты, выберите случайную пару (vi,vf), такую, что vf-1 = vix mod n. Для метода Диффи-Хеллмана наиболее просто выбрать случайное vi, затем вычислить vf = (vi-1)x mod n. Для RSA лучше выбрать случайное vf, взаимно простое к n, затем вычислить vi = (vf-1)e mod n, где e - открытая экспонента. Перед модульным возведением в степень, входные данные должны быть умножены на vi (mod n), а позже результат корректируется умножением на vf (mod n). При этом система должна отклонять сообщения, равные 0 (mod n).

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

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

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

Дальнейшее направление исследований

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


На главную страницу раздела

Солдатова Е.П., Углов Н.Д.