Временная атака

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

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

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

Избегание

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

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

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

Примеры

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

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

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

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

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

Временные атаки трудно предотвратить, и их часто можно использовать для расширения других атак. Например, в 2018 году старая атака на RSA была вновь обнаружена в варианте временного побочного канала, спустя два десятилетия после первоначальной ошибки. ^{[ 10 ]}

Алгоритм

Следующий код 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() или ^{[ 11 ]} OpenBSD timingsafe_bcmp() и timingsafe_memcmp. функцию сравнения из криптографических библиотек, таких как OpenSSL и libsodium В других системах можно использовать .

Примечания

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

Ссылки

^ Перейти обратно: ^а ^б ^с «Криптопостоянное время» . МедведьSSL . Проверено 10 января 2017 г.
^ «Руководство для начинающих по криптографии постоянного времени» . Проверено 9 мая 2021 г.
^ Дэвид Брамли и Дэн Боне. Удаленные атаки по времени практичны. Симпозиум по безопасности USENIX, август 2003 г.
^ См. Персиваль, Колин, Тайник пропал ради развлечения и прибыли , 2005.
^ Бернштейн, Дэниел Дж., Атаки по времени кэша на AES , 2005.
^ Хорн, Янн (3 января 2018 г.). «Чтение привилегированной памяти по побочному каналу» . googleprojectzero.blogspot.com.
^ «Часто задаваемые вопросы по системам Spectre» . Мелтдаун и Призрак .
^ «Недостатки безопасности подвергают риску практически все телефоны и компьютеры» . Рейтер . 4 января 2018 г.
^ «Потенциальное влияние на процессоры семейства POWER» . Блог IBM PSIRT . 14 мая 2019 г.
^ Карио, Юбер. «Атака Марвина» . People.redhat.com . Проверено 19 декабря 2023 г.
^ «Consttime_memequal» .

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

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

[BearSSL-1] Перейти обратно: ^а ^б ^с «Криптопостоянное время» . МедведьSSL . Проверено 10 января 2017 г.

[2] «Руководство для начинающих по криптографии постоянного времени» . Проверено 9 мая 2021 г.

[3] Дэвид Брамли и Дэн Боне. Удаленные атаки по времени практичны. Симпозиум по безопасности USENIX, август 2003 г.

[4] См. Персиваль, Колин, Тайник пропал ради развлечения и прибыли , 2005.

[5] Бернштейн, Дэниел Дж., Атаки по времени кэша на AES , 2005.

[6] Хорн, Янн (3 января 2018 г.). «Чтение привилегированной памяти по побочному каналу» . googleprojectzero.blogspot.com.

[7] «Часто задаваемые вопросы по системам Spectre» . Мелтдаун и Призрак .

[8] «Недостатки безопасности подвергают риску практически все телефоны и компьютеры» . Рейтер . 4 января 2018 г.

[9] «Потенциальное влияние на процессоры семейства POWER» . Блог IBM PSIRT . 14 мая 2019 г.

[10] Карио, Юбер. «Атака Марвина» . People.redhat.com . Проверено 19 декабря 2023 г.

[11] «Consttime_memequal» .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]