Перейти к основному содержанию
ИТарктика
УДК 004.056.55
Ильчуков Александр Сергеевич
ведущий специалист отдела разработки и адаптации информационных систем государственного автономного учреждения Республики Коми «Центр информационных технологий»
К вопросу о реализации криптографических алгоритмов с защитой от атак на кэш
Аннотация:

В работе предлагается подход к реализации таких криптографических алгоритмов как AES (Rijndael) и Whirlpool на платформе ARMv7, не подверженных уязвимостям к атакам на кэш. Приводится сравнение эффективности прототипов реализаций и промышленных реализаций этих алгоритмов на потребительских устройствах.

Ключевые слова: AES, Whirlpool, атака на кэш, ARMv7, NEON.

С развитием виртуальных сетей и их массовым использованием была выявлена проблема безопасности сети и защиты передаваемой информации. Более всего эта проблема актуальна для корпоративных сетей, где предъявляются жёсткие требования к используемым протоколам и алгоритмам шифрования. Изучение аспектов и способов защиты информации не может останавливаться на криптоанализе алгоритмов: выделяют целый класс атак [1], которые используют особенности реализации и уязвимости алгоритмов, выполняющихся на современных вычислительных устройствах. Так реализации блочного шифра AES, фактически являющегося стандартным блочным шифром для большинства программных продуктов, связанных с шифрованием, уязвимы к некоторым таким атакам [2, 3] при устойчивости ко всем видам криптоанализа. Использование атак предполагает обширное изучение работы конкретной реализации алгоритма и вычислительного устройства, на котором выполняется эта реализация. Тем не менее, проблема прохождения такой атаки существует, особенно при выходе в корпоративную сеть с личных мобильных терминалов.

Существует несколько решений этой проблемы. Во-первых, в некоторых случаях возможно использование иных алгоритмов, принципиально не подверженных указанной проблеме [4]. Однако применение данного подхода затруднительно при уже настроенном и проверенном серверном программном обеспечении корпоративной сети. Во-вторых, возможно использование реализаций, не являющихся уязвимыми к таким атакам. Данная работа представляет результаты исследования, которые проводились в рамках последнего подхода. Объектом исследования были алгоритмы AES и Whirlpool, выбор которых был обусловлен обширным распространением первого и схожестью их математических аппаратов. Целевыми вычислительными устройствами для выполнения реализаций были выбраны микропроцессоры мобильных устройств, поддерживающие набор команд ARMv7 с расширениями NEON.

Особенность работы указанных алгоритмов заключается в массивных вычислениях, которые происходят в некотором поле Галуа. Потребительские вычислительные устройства не имеют достаточной поддержки подобных вычислений, что приводит к эмуляции операций в поле Галуа с помощью стандартных битовых операций и медленной работе реализации алгоритма. Для ускорения вычислений практически во всех промышленных реализациях AES используются так называемые таблицы подстановок. При этом современные вычислительные устройства, в том числе и мобильные, обладают развитой системой кэширования, позволяющей ускорить работу подсистемы памяти. Обращение к таблицам подстановок может быть более быстрым или более медленным в зависимости от того, находится ли эта таблица в кэше. Эту информацию можно получить и использовать для получения статистически значимых сведений о ключе шифрования [3]. Подобная атака была названа атакой на кэш.

Для создания реализации алгоритма, устойчивой к атаке на кэш, необходимо либо отказаться от таблиц подстановок, либо исключить влияние кэша на эти таблицы. Теоретически, оба подхода дают существенное (один-два порядка) замедление работы реализации алгоритма. При использовании специальных команд, присутствующих в новейших архитектурах (AES NI для х86, криптографические расширения для ARMv8) можно воспользоваться вторым подходом и создать эффективную реализацию, но эти наборы команд отсутствуют в более старых вычислительных устройствах, до сих пор используемых корпоративными пользователями. Тем не менее, вычислительные устройства мобильных терминалов уже более десяти лет включают команды параллельной обработки данных, что можно использовать для эффективной реализации. Так расширения NEON микроархитектуры ARMv7, поддерживаемые практически каждым современным мобильным устройством, включают обширный набор подобных команд и, кроме того, шестнадцать 128-битных регистров для хранения операндов и результатов операций. При этом для хранения матрицы состояния AES достаточно одного такого регистра, а для матрицы состояния Whirlpool – четырёх.

В ходе исследования были написаны прототипы реализаций AES и Whirlpool на ассемблере ARMv7, на которых были протестированы оба подхода, описанные выше. Для нелинейных преобразований матрицы состояния алгоритма AES использовалась загрузка таблицы подстановок в регистры NEON. Дальнейшее обращение к ней осуществлялось непосредственно из регистров. Этот подход позволил полностью избавиться от разницы во времени при доступе к элементам таблицы. В случае нелинейных преобразований матрицы состояния Whirlpool использовался подход с вычислениями, выполняющимися параллельно для каждой четверти состояния. В другом этапе преобразований, так называемом диффузном преобразовании состояния, таблицы подстановок для обоих алгоритмов были заменены вычислениями. Суть диффузного преобразования заключается в умножении на фиксированную матрицу в поле Галуа, что было сведено к небольшому количеству побитовых операций и битовых сдвигов. В результате возможность проведения атаки на кэш была полностью исключена.

Было проведено тестирование прототипов реализаций на потребительских устройствах. Для сравнения были взяты реализации из последней версии библиотеки OpenSSL, являющейся индустриальным стандартом. Можно отметить, что библиотека OpenSSL включает в себя также оптимизированные ассемблерные реализации под различные архитектуры. В качестве компилятора использовался GCC из последней версии пакета Linaro, а вычислительными устройствами послужили чипы Nvidia Tegra 3 и Qualcomm Snapdragon 801. Тестирование показало, что разработанные прототипы реализаций не только не уступают реализациям OpenSSL по скорости работы, но и превосходят их. Таким образом, продемонстрировано, что за счёт массивного распараллеливания операций можно создать реализации алгоритмов AES и Whirlpool, которые устойчивы к атакам на кэш и не уступают по скорости индустриальным аналогам.

Список литературы

  1. Kocher P. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems // Advances in Cryptology – CRYPTO’96. Lecture Notes in Computer Science. Vol. 1109. P. 104-113.
  2. Osvik D. A., Shamir A., Tromer E. Cache Attacks and Countermeasures: the Case of AES. [Electronic resource] // Tel Aviv University. URL: http://cs.tau.ac.il/~tromer/papers/cache.pdf.
  3. Bangerter E., Gullasch D., Krenn S. Cache Games – Bringing Access-Based Cache Attacks on AES to Practice. [Electronic resource] // Cryptology ePrint Archive. URL: http://eprint.iacr.org/2010/594.pdf.

Bernstein D. J. The Salsa20 family of stream ciphers. [Electronic resource] // URL: http://cr.yp.to/snuffle/salsafamily-20071225.pdf