Сроки атаки - Timing attack

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

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

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

Избегание

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

Зависимость времени от данных может быть связана с одним из следующих факторов:

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

Примеры

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

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

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

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

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

Алгоритм

Следующий код на 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 false;
  return true;
}

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

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[i];
  return result;
}

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

Заметки

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

Рекомендации

дальнейшее чтение