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

Начало подобным атакам положили работы Пола Кохера (Paul Kocher), прежде всего, статья, в которой была представлена атака по времени выполнения (timing attack). Данная атака использует тот факт, что на некоторых аппаратных платформах для выполнения определенных операций требуется различное количество тактов процессора. Результат — различное время выполнения операций. Соответственно, криптоаналитик путем высокоточных замеров времени выполнения шифратором определенных операций может сделать какие-либо предположения о значении определенных фрагментов секретного ключа.

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

Одним из наиболее показательных алгоритмов, против которых может быть проведена атака по времени выполнения, является алгоритм RC5.

Рассмотрим раунд этого алгоритма. Как видно, в раунде RC5 присутствуют операции вращения на переменное число битов, что приводит к появлению неких, зависящих от обрабатываемых данных и значения секретного ключа, временных характеристик. Это делает атаку на RC5 теоретически возможной. Среди других алгоритмов, подверженных атаке по времени выполнения, Кохер в упоминает такие известные алгоритмы, как IDEA, Blowfish и DES.

В качестве «противоядия» от атак по времени выполнения Кохер предлагает следующее.

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

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

По материалам книги Сергея Панасенко «Алгоритмы шифрования»

Алгоритмы шифрования