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

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

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

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

Ссылки


Wikimedia Foundation. 2010.

Нужно решить контрольную?

Полезное


Смотреть что такое "Атака по времени" в других словарях:

  • Атака по сторонним каналам — Атака по энергопотреблению на алгоритм RSA. Левый пик соответствует операции быстрого возведения в степень без умножения, правый  с умножением, что позволяет восстановить значение обрабатываемых битов. Атака по сто …   Википедия

  • Атака на ГПСЧ — Атака на генератор псевдослучайных чисел атака, направленная на раскрытие параметров генератора псевдослучайных чисел (ГПСЧ) с целью дальнейшего предсказания псевдослучайных чисел. Содержание 1 Актуальность 2 Типы атак на ГПСЧ …   Википедия

  • Атака фортов-застав — АТАКА ФОРТОВЪ ЗАСТАВЪ представляетъ самостоятельный эпизодъ боевыхъ дѣйствій въ условіяхъ крѣпостной борьбы. Въ своихъ пріемахъ она будетъ отличаться отъ А. большой современной крѣпости въ зависимости отъ устройства самихъ ф. з. и отъ… …   Военная энциклопедия

  • Атака кавалерийская — АТАКА КАВАЛЕРІЙСКАЯ. Подъ этимъ терминомъ тактика разумѣетъ рѣшительное, безостановочное движеніе впередъ къ противнику, съ цѣлью нанести ему ударъ напоромъ коней и холоднымъ оружіемъ, а также нравственно потрясти его; нравств. потрясеніе м. б.… …   Военная энциклопедия

  • Атака на основе подобранного открытого текста — (англ. Chosen plaintext attack, CPA)  один из 4 основных способов криптоаналитического вскрытия[1]. Криптоаналитик обладает определённым числом открытых текстов и соответствующих шифротекстов, кроме того, он имеет возможность… …   Википедия

  • АтакА — Студийный альбом Линды Дата выпуска 5 ноября 2004 Записан Студии «Криста …   Википедия

  • Атака минная, морская — АТАКА МИННАЯ, МОРСКАЯ, такъ называется нападеніе миннаго судна на какое либо непріятельское съ цѣлью нанести ему ударъ миной; трудность мин. А. заключается въ томъ, что надо приблизиться къ непріятелю на дистанцію, доступную для мины и… …   Военная энциклопедия

  • Атака укрепленной позиции — АТАКА УКРѢПЛЕННОЙ ПОЗИЦІИ представляетъ собой одну изъ труднѣйшихъ полевыхъ операцій, почему современное военное искусство требуетъ отъ обороняющагося укрѣпленія всякой позиціи, на которой онъ задается цѣлью упорнаго боя. Опыть послѣдней войны… …   Военная энциклопедия

  • Атака артиллерийская в полевом бою — АТАКА АРТИЛЛЕРІЙСКАЯ въ полевомъ бою, терминъ условный, оспариваемый большинствомъ авторитетовъ, отрицающихъ самую возможность А. артил., приводящей къ рѣшенію боя однимъ огнемъ. Впервые встрѣчается, какъ терминъ, въ Высочайшемъ предуказаніи для… …   Военная энциклопедия

  • Атака крепости — АТАКА КРѢПОСТИ является совокупностью боевыхъ дѣйствій войскъ наступающей арміи въ борьбѣ за обладаніе крѣпостью. Маневренное значеніе, какое пріобрѣтаютъ крѣпости въ современныхъ войнахъ, показываетъ, что дѣйствія подъ крѣпостями, при всѣхъ… …   Военная энциклопедия

Книги

Другие книги по запросу «Атака по времени» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»