В криптографии атака по времени — это атака по побочному каналу , при которой злоумышленник пытается скомпрометировать криптосистему , анализируя время, необходимое для выполнения криптографических алгоритмов. Каждая логическая операция в компьютере требует времени для выполнения, и время может отличаться в зависимости от ввода; с точными измерениями времени для каждой операции злоумышленник может работать в обратном направлении к вводу. Поиск секретов с помощью информации о времени может быть значительно проще, чем использование криптоанализа известных пар открытого текста и шифротекста. Иногда информация о времени объединяется с криптоанализом для увеличения скорости утечки информации. [1]
Информация может утекать из системы через измерение времени, необходимого для ответа на определенные запросы. Насколько эта информация может помочь злоумышленнику, зависит от многих переменных: конструкции криптографической системы, процессора, на котором работает система, используемых алгоритмов, различных деталей реализации, контрмер против атак по времени, точности измерений времени и т. д. Атаки по времени могут применяться к любому алгоритму, который имеет зависящие от данных вариации времени. Устранение зависимостей времени затруднено в некоторых алгоритмах, которые используют низкоуровневые операции, которые часто демонстрируют различное время выполнения.
Атаки по времени часто упускаются из виду на этапе проектирования, поскольку они сильно зависят от реализации и могут быть непреднамеренно введены с оптимизациями компилятора . Избежание атак по времени включает проектирование функций постоянного времени и тщательное тестирование конечного исполняемого кода. [1]
Многие криптографические алгоритмы могут быть реализованы (или замаскированы прокси) таким образом, чтобы уменьшить или устранить зависящую от данных информацию о времени, алгоритм с постоянным временем . Реализацию алгоритма с постоянным временем иногда называют реализацией с безопасным временем [2] . Рассмотрим реализацию, в которой каждый вызов подпрограммы всегда возвращается ровно через x секунд, где x — максимальное время, которое когда-либо требуется для выполнения этой подпрограммы для каждого возможного авторизованного ввода. В такой реализации синхронизация алгоритма с меньшей вероятностью приведет к утечке информации о данных, предоставленных для этого вызова. [3] Недостатком этого подхода является то, что время, используемое для всех выполнений, становится временем наихудшего случая производительности функции.
Зависимость времени от данных может быть обусловлена одним из следующих факторов: [1]
Время выполнения алгоритма возведения в квадрат и умножения, используемого в модульном возведении в степень, линейно зависит от количества битов «1» в ключе. Хотя количество битов «1» само по себе не является достаточной информацией для облегчения поиска ключа, повторные выполнения с тем же ключом и разными входными данными могут быть использованы для проведения статистического корреляционного анализа информации о времени для полного восстановления ключа даже пассивным злоумышленником. Наблюдаемые измерения времени часто включают шум (из таких источников, как задержка сети или различия в доступе к диску от доступа к доступу, а также методы исправления ошибок , используемые для восстановления после ошибок передачи). Тем не менее, атаки по времени практичны против ряда алгоритмов шифрования, включая RSA , ElGamal и алгоритм цифровой подписи .
В 2003 году Боне и Брамли продемонстрировали практическую сетевую атаку по времени на веб-серверы с поддержкой SSL , основанную на другой уязвимости, связанной с использованием RSA с оптимизацией китайской теоремы об остатках . Фактическое сетевое расстояние было небольшим в их экспериментах, но атака успешно восстановила закрытый ключ сервера в течение нескольких часов. Эта демонстрация привела к широкому развертыванию и использованию методов ослепления в реализациях SSL. В этом контексте ослепление предназначено для устранения корреляций между ключом и временем шифрования. [4]
Некоторые версии Unix используют относительно дорогую реализацию функции библиотеки crypt для хеширования 8-символьного пароля в 11-символьную строку. На старом оборудовании это вычисление занимало намеренно и измеримо много времени: в некоторых случаях до двух или трех секунд. [ требуется цитата ] Программа входа в систему в ранних версиях Unix выполняла функцию crypt только тогда, когда имя входа распознавалось системой. Это приводило к утечке информации о действительности имени входа через синхронизацию, даже если пароль был неверным. Злоумышленник мог воспользоваться такими утечками, сначала применив метод подбора для создания списка известных действительных имен входа, а затем попытаться получить доступ, объединив только эти имена с большим набором известных часто используемых паролей. Без какой-либо информации о действительности имен входа время, необходимое для выполнения такого подхода, увеличилось бы на порядки, фактически сделав его бесполезным. Более поздние версии Unix исправили эту утечку, всегда выполняя функцию crypt, независимо от действительности имени входа. [ требуется цитата ]
Два в противном случае надежно изолированных процесса, запущенных в одной системе с кэш-памятью или виртуальной памятью, могут взаимодействовать, намеренно вызывая сбои страниц и/или промахи кэша в одном процессе, а затем отслеживая полученные изменения времени доступа из другого. Аналогично, если приложение является доверенным, но его подкачка/кэширование затронуто логикой ветвления, второе приложение может определить значения данных по сравнению с условием ветвления, отслеживая изменения времени доступа; в крайних случаях это может позволить восстановить биты криптографического ключа. [5] [6]
Атаки Meltdown и Spectre 2017 года , вынудившие производителей процессоров (включая Intel, AMD, ARM и IBM) перепроектировать свои процессоры, обе основаны на тайминговых атаках. [7] По состоянию на начало 2018 года почти каждая компьютерная система в мире затронута Spectre. [8] [9] [10]
Атаки по времени трудно предотвратить, и их часто можно использовать для расширения других атак. Например, в 2018 году старая атака на RSA была повторно обнаружена в варианте с побочным каналом по времени, спустя два десятилетия после первоначальной ошибки. [11]
Следующий код C демонстрирует типичное небезопасное сравнение строк, которое останавливает проверку, как только символ не совпадает. Например, при сравнении "ABCDE" с "ABxDE" он вернет после 3 итераций цикла:
bool insecureStringCompare ( const void * a , const void * b , size_t длина ) { const char * ca = a , * cb = b ; for ( size_t i = 0 ; i < длина ; i ++ ) if ( ca [ i ] != cb [ i ]) return false ; return true ; } Для сравнения, следующая версия выполняется за постоянное время, проверяя все символы и используя побитовую операцию для накопления результата:
bool constantTimeStringCompare ( const void * a , const void * b , size_t длина ) { const char * ca = a , * cb = b ; bool результат = true ; for ( size_t i = 0 ; i < длина ; i ++ ) результат &= ca [ i ] == cb [ i ]; вернуть результат ; } В мире функций библиотеки C первая функция аналогична memcmp(), тогда как последняя аналогична NetBSD consttime_memequal()или [12] OpenBSD timingsafe_bcmp()и . В других системах можно использовать timingsafe_memcmpфункцию сравнения из криптографических библиотек, таких как OpenSSL и libsodium .
Атаки по времени легче организовать, если противник знает внутренние компоненты аппаратной реализации и, тем более, используемую криптографическую систему. Поскольку криптографическая безопасность никогда не должна зависеть от неизвестности того или иного (см. безопасность через неизвестность , в частности, принцип Шеннона и принцип Керкхоффса ), устойчивость к атакам по времени тоже не должна зависеть. Если нет ничего другого, можно купить образец и провести его обратную разработку. Атаки по времени и другие атаки по побочным каналам также могут быть полезны для идентификации или, возможно, обратной разработки криптографического алгоритма, используемого каким-либо устройством.