Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В криптографии , А атака по времени является побочным каналом атака , в которой попытки злоумышленника криптосистемы на основе анализа времени , необходимое для выполнения криптографических алгоритмов. Каждая логическая операция в компьютере требует времени для выполнения, и время может отличаться в зависимости от ввода; с точным измерением времени для каждой операции злоумышленник может работать в обратном направлении до входа. Поиск секретов с помощью информации о времени может быть значительно проще, чем использование криптоанализа известных пар открытого текста и зашифрованного текста. Иногда информацию о времени комбинируют с криптоанализом, чтобы увеличить скорость утечки информации. [1]

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

Атаки по времени часто упускаются из виду на этапе проектирования, потому что они сильно зависят от реализации и могут быть непреднамеренно введены при оптимизации компилятора . Избежание временных атак включает в себя разработку функций с постоянным временем и тщательное тестирование окончательного исполняемого кода. [1]

Избегание [ править ]

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

Зависимость времени от данных может происходить по одной из следующих причин: [1]

  • Доступ к нелокальной памяти, так как ЦП может кэшировать данные. Программное обеспечение, работающее на ЦП с кешем данных, будет демонстрировать зависящие от данных временные изменения в результате того, что память просматривает кэш.
  • Условные прыжки . Современные процессоры пытаются спекулятивно выполнить прошлые переходы, угадывая. Неправильное предположение (не редкость для по существу случайных секретных данных) влечет за собой измеримую большую задержку, поскольку ЦП пытается выполнить возврат. Это требует написания кода без ветвей .
  • Некоторые «сложные» математические операции в зависимости от аппаратного обеспечения ЦП:
    • Целочисленное деление - это почти всегда непостоянное время. ЦП использует цикл микрокода, который использует другой путь кода, когда либо делитель, либо делимое малы.
    • ЦП без механизма переключения передач выполняет сдвиги и повороты в цикле, по одной позиции за раз. В результате сумма сдвига не должна быть секретной.
    • Старые процессоры выполняют умножение аналогично делению.

Примеры [ править ]

Время выполнения алгоритма квадратного и умножения, используемого в модульном возведении в степень, линейно зависит от количества битов «1» в ключе. Хотя одного лишь количества битов «1» недостаточно, чтобы упростить поиск ключа, можно использовать повторные выполнения с одним и тем же ключом и разными входными данными для выполнения статистического корреляционного анализа информации о времени для полного восстановления ключа, даже если пассивный злоумышленник. Наблюдаемые измерения синхронизации часто включают шум (из таких источников, как задержка в сети или различия в доступе к диску и доступ к доступу, а также методы исправления ошибок , используемые для восстановления после ошибок передачи). Тем не менее, временные атаки применимы против ряда алгоритмов шифрования, в том числеRSA , Эль-Гамаль и алгоритм цифровой подписи .

В 2003 году Бонех и Брамли продемонстрировали практическую сетевую синхронизирующую атаку на веб-серверы с поддержкой SSL , основанные на другой уязвимости, связанной с использованием RSA с оптимизацией китайской теоремы об остатках . Фактическое сетевое расстояние в их экспериментах было небольшим, но атака успешно восстановила закрытый ключ сервера за считанные часы. Эта демонстрация привела к широкому распространению и использованию методов ослепления в реализациях SSL. В этом контексте ослепление предназначено для устранения корреляции между ключом и временем шифрования. [2]

Некоторые версии Unix используют относительно дорогостоящую реализацию функции библиотеки crypt для хеширования 8-значного пароля в 11-символьную строку. На старом оборудовании это вычисление занимало преднамеренно и ощутимо долгое время: в некоторых случаях до двух или трех секунд. [ необходима цитата ] Программа входа в систему в ранних версиях Unix выполняла функцию crypt только тогда, когда имя входа было распознано системой. Эта утечка информации о сроках действия имени для входа в систему, даже если пароль был неверным. Злоумышленник может воспользоваться такими утечками, применив сначала грубую силу.чтобы создать список известных имен для входа в систему, затем попытайтесь получить доступ, объединив только эти имена с большим набором паролей, которые, как известно, часто используются. Без какой-либо информации о допустимости имен для входа время, необходимое для выполнения такого подхода, увеличилось бы на порядки, что фактически сделало бы его бесполезным. Более поздние версии Unix устранили эту утечку, всегда выполняя функцию crypt, независимо от допустимости имени входа. [ необходима цитата ]

Два в остальном надежно изолированные процесса, работающие в одной системе с кэш-памятью или виртуальной памятью, могут обмениваться данными, намеренно вызывая сбои страниц и / или промахи кеша в одном процессе, а затем отслеживая результирующие изменения времени доступа в другом. Аналогичным образом, если приложение является доверенным, но на его пейджинг / кэширование влияет логика ветвления, второе приложение может определить значения данных по сравнению с условием ветвления, отслеживая изменения времени доступа; в крайних случаях это может позволить восстановить биты криптографического ключа. [3] [4]

Атаки Meltdown и Spectre 2017 года, которые вынудили производителей процессоров (включая Intel, AMD, ARM и IBM) изменить дизайн своих процессоров, полагаются на атаки по времени. [ необходима цитата ] По состоянию на начало 2018 года почти каждая компьютерная система в мире подвергалась воздействию Spectre, что делает его самым мощным примером временной атаки в истории. [5] [6] [7]

Алгоритм [ править ]

Следующий код на C демонстрирует типичное небезопасное сравнение строк, которое прекращает тестирование, как только символ не совпадает. Например, при сравнении «ABCDE» с «ABxDE» он вернется после 3 итераций цикла:

bool  insecureStringCompare ( const  void  * a ,  const  void  * b ,  size_t  length )  {  const  char  * ca  =  a ,  * cb  =  b ;  for  ( size_t  i  =  0 ;  i  <  length ;  i ++ )  if  ( ca [ i ]  ! =  cb [ i ])  return ложь ;  вернуть  истину ; }

Для сравнения: следующая версия работает с постоянным временем, проверяя все символы и используя поразрядную операцию для накопления результата:

bool  constantTimeStringCompare ( const  void  * a ,  const  void  * b ,  size_t  length )  {  const  char  * ca  =  a ,  * cb  =  b ;  bool  result  =  true ;  for  ( size_t  i  =  0 ;  i  <  length ;  i ++ )  result  & =  ca [ i ] ==  cb [ я ];  вернуть  результат ; }

В мире библиотечных функций C первая функция аналогична memcmp(), а последняя аналогична NetBSD consttime_memequal()или [8] OpenBSD timingsafe_bcmp()и timingsafe_memcmp. В других системах можно использовать функцию сравнения из криптографических библиотек, таких как OpenSSL и libsodium .

Заметки [ править ]

Атаки по времени легче организовать, если злоумышленник знает внутреннее устройство аппаратной реализации и, тем более, используемую криптографическую систему. Поскольку криптографическая безопасность никогда не должна зависеть от неизвестности того или другого (см. Безопасность через неясность , в частности , принцип Максима Шеннона и принцип Керкхоффа ), устойчивость к атакам по времени тоже не должна. По крайней мере, образец можно купить и перепроектировать. Атаки по времени и другие атаки по побочным каналам также могут быть полезны для идентификации или, возможно, обратного проектирования криптографического алгоритма, используемого каким-либо устройством.

Ссылки [ править ]

  1. ^ a b c «Постоянное шифрование» . BearSSL . Проверено 10 января 2017 года .
  2. ^ Дэвид Брамли и Дэн Боне. Дистанционные временные атаки практичны. Симпозиум по безопасности USENIX, август 2003 г.
  3. ↑ См. Персиваль, Колин, Кэш отсутствует для развлечения и прибыли , 2005.
  4. ↑ Бернштейн, Дэниел Дж., Атаки по времени кэширования на AES , 2005.
  5. ^ "Часто задаваемые вопросы по системам Spectre" . Meltdown и Spectre .
  6. ^ «Недостатки безопасности подвергают опасности практически все телефоны и компьютеры» . Рейтер . 4 января 2018.
  7. ^ «Возможное влияние на процессоры семейства POWER» . Блог IBM PSIRT . 14 мая 2019.
  8. ^ https://www.freebsd.org/cgi/man.cgi?query=consttime_memequal&manpath=NetBSD+7.0

Дальнейшее чтение [ править ]

  • Пол К. Кохер. Атаки по времени на реализации Diffie-Hellman, RSA, DSS и других систем. КРИПТО 1996: 104–113
  • Липтон, Ричард ; Нотон, Джеффри Ф. (март 1993 г.). «Синхронизированные злоумышленники для хеширования». Алгоритмика . 9 (3): 239–252. DOI : 10.1007 / BF01190898 . S2CID  19163221 .
  • Репараз, Оскар; Балаш, Жозеп; Verbauwhede, Ингрид (март 2017). «Чувак, мой код - постоянное время?» (PDF) . Конференция-выставка «Дизайн, автоматизация в Европе» (ДАТА), 2017 : 1697–1702. DOI : 10.23919 / DATE.2017.7927267 . ISBN 978-3-9815370-8-6. S2CID  35428223 .   Описывает dudect , простую программу, которая вычисляет фрагмент кода на разных данных.