Исследуется возможность обращения криптографической функции А5/1 с применением вычислительных ресурсов графических ускорителей общего назначения (GPU). Применение «атаки Андерсона» в реализации криптоанализа А5/1 методом прямого перебора позволяет снизить мощность пространства поиска с 264 до 253 . Одним из дальнейших путей ускорения атаки является увеличение эффективности алгоритма шифрования А5/1. В настоящей работе мы сравниваем реализацию генератора A5/1, основанную на полном предвычислении значений входящих в него регистров сдвига с линейной обратной связью с реализацией, основанной на технике "bitslice". Проведенное нами сравнение CPU и GPU версий данных алгоритмов показывает существенное преимущество GPU-bitslice версии.
Обращение криптографической функции А5/1 на платформе GPU с применением альтернативных схем вычисления значений сдвиговых регистров* 1.1 Генератор А5/1
22 + 21 + 1; agora.guru.ru/pavt Рис. 1. Схема работы генератора А5/1.
РСЛОС в А5/1 сдвигаются несинхронно. В каждом такте для регистра с номером ∈ {1,2,3} проверяется равенство = ( 1, 2, 3) (*) где – значение серединного разряда регистра с номером на такте с номером (серединными называются разряды РСЛОС 1-3 с номерами 9, 11, 11), а – функция большинства (majority function), то есть булева функция, задаваемая следующей формулой: спецификацией стандарта GSM. Хорошо известно [3], что слабости протокола GSM позволяют получить несколько первых берстов (англ. «burst», 1 берст равен 114 битам) ключевого потока. Зная этот фрагмент, достаточно найти лишь состояние регистров, которое его порождает, после чего мы можем дешифровать шифртекст любого объема. Из [5] известно, что для корректного восстановления неизвестного состояния регистров достаточно проанализировать 64 бита порожденного этим состоянием ключевого потока. 1.2 Обзор литературы и предшествующих работ
Первая атака, улучшающая оценку сложности по сравнению с полным перебором, была
предложена в 1994 году в [4] (т. н. «атака
Андерсона»). Она основана на угадывании
заполнений 2-х регистров и вычислении значений 3-го. Данная атака получила развитие,
например, в [
В дальнейшем были предложены атаки, использующие линеаризацию систем уравнений,
описывающих генерацию ключевого потока [5], а также атаки, основанные на принципах
пространственно-временного компромисса [
A5/1:
то
есть
различных
секретных
ключей,
порождающих один и тот же ключевой поток произвольной длины. Результаты работ [
Осенью 2009 года появились первые rainbow-таблицы для криптоанализа построенные группой «A5/1
Cracking Project» [3]. На сегодняшний день данный криптоанализа А5/1 можно считать самым эффективным в плане временных затрат. Правда, строго говоря, этот метод не обеспечивает полностью достоверных результатов криптоанализа, А5/1, метод поскольку вероятность найти им секретный ключ, анализируя 8 берстов ключевого потока (912 бит), составляет приблизительно 88%. 1.3 «Атака Андерсона»
В данной работе мы реализовали вариант «атаки Андерсона», в применении к регистру 2. Конкретно, по известному ключевому потоку, известному заполнению регистров 1 и 3 и известному заполнению ячеек регистра 2 , лежащих правее серединного бита, можно вычислить значения оставшихся ячеек регистра 2.
Алгоритм «атаки Андерсона» можно описать следующим образом [4]: 1) угадать заполнение регистров 1 и 3 полностью, и заполнение регистра 2 справа от серединного бита (рис. 1); 2) по известному фрагменту ключевого потока, тактируя генератор, вычислить заполнение регистра 3 слева от серединного бита; 3) проверить полученное таким образом начальное состояние генератора, тактируя его и сравнивая с известным фрагментом ключевого потока.
По сути, этот алгоритм является модификацией метода прямого перебора, в котором за счет эксплуатации особенностей конструкции шифра удается значительно уменьшить пространство поиска. В данном конкретном случае пространство поиска сокращается с 264 до 253 ключей. 2. Быстрая программная реализация генератора A5/1
Эффективность метода прямого перебора напрямую зависит от 2-х факторов: масштабов пространства поиска и скорости проверки ключей-кандидатов. В случае генератора А5/1 малая длина ключа и применение «атаки Андерсона» позволяют добиться разумного масштаба пространства поиска (253). Скорость проверки можно увеличить, задействовав вместо «наивной» программной реализации генератора А5/1 альтернативные способы вычисления ключевого потока. Далее мы приводим описание двух наиболее эффективных из них: техники bitslice (наиболее близкий русскоязычный термин «разрядно-модульный подход») и метода предвычисления РСЛОС. Данные по сравнению производительности получившихся реализаций приведены в разделе 3 в таблице 1 («атака Андерсона») и таблице 2 (обыкновенный прямой перебор). 2.1 Техника «bitslice»
Современные универсальные вычислительные архитектуры далеко не оптимальны для реализации криптографических алгоритмов. Последние работают с битами, тогда как современные процессоры проектируются для работы со словами длиной 32-256 бит. В итоге «наивная» реализация криптографической функции стандартными методами программирования может не задействовать вычислительные возможности рассматриваемой платформы полностью. К примеру, на CPU при необходимости провести операцию «сложение по модулю 2» (XOR) над двумя булевыми аргументами, их значения будут записаны в младшие биты двух 32-х битных регистров общего назначения (РОН). Результат также будет записан в один из доступных 32-х битных регистров. Фактически, 31 из 32-х бит регистра будет простаивать в бездействии. Эту проблему можно решить с применением побитовых булевых операций, которые действуют над РОН поразрядно – как над булевыми векторами. Зачастую криптографический алгоритм может быть представлен в виде схемы из логических вентилей так, что появляется возможность эффективно обрабатывать сразу столько наборов данных, сколько позволяет разрядность РОН вычислительной платформы. В англоязычной литературе этот прием иногда называют «SIMD within a register», т. е. дословно «ОКМД 1 на одном регистре», что весьма точно передает его суть. Еще одно часто используемое название – 1 Вычислительная архитектура типа «одна команда, много данных». agora.guru.ru/pavt «bitslice», т.е. «разрядно-модульный подход» (по аналогии с «разрядно-модульными процессорами»). Опишем основную идею данного подхода.
Рассмотрим произвольную булеву функцию
: {0,1} → {0,1}.
Данную функцию всегда можно представить в виде суперпозиции булевых функций арности не более 2, образующих некоторый полный базис . Простейший пример такого представления нам дают КНФ или ДНФ рассматриваемой функции (в этом случае = {∧,∨, ¬}). Значение произвольной функции из базиса в вычислительном устройстве получается в результате применения соответствующей данной функции инструкции к одной или двум (в зависимости от арности функции) ячейкам памяти устройства, содержащим по одному биту входа. Современным вычислительным устройствам доступны т. н. «побитовые» инструкции, которые могут применяться к целому регистру или паре регистров (например, инструкция «побитовое сложение по модулю 2»). Результатом выполнения такой инструкции является одновременное независимое вычисление множества значений некоторой базисной функции на соответствующем наборе входов. Обычно размер регистра (число ячеек или разрядов) есть 2 (для большинства современных архитектур 5 ≤ ≤ 7). Пусть теперь рассматривается задача вычисления произвольной функции (описанного выше вида) на всех 2 возможных входах.
Предположим, что представлена в виде суперпозиции
базисных функций из , и пусть размер регистра вычислительного устройства есть 2 . Таким образом, число инструкций, необходимых для вычисления на всех входах из {0,1} , есть
⋅ 2 − . Фактически, разрядно-модульный подход может быть использован в любых мультиразрядных арифметико-логических устройствах (АЛУ), в которых доступны инструкции, реализующие побитовые операции над РОН.
Пример 1. Пусть требуется вычислить значения функции Рис. 2. Разрядно-модульный подход.
⊕: {0,1}3 → {0,1}, заданной формулой 1 ⊕ 2 ⊕ 3, на всех возможных входах (их 8). При последовательном вычислении для каждого слова вида ( 1, 2 3) используется число инструкций для данного способа вычислений равно = 2 инструкций, поэтому общее ⋅ 2 = 16. Теперь предположим, что рассматривается вычислительное устройство с регистрами, состоящими из 8 разрядов, и на этом устройстве доступна инструкция «побитовое ⊕» для пары регистров. Тогда мы можем рассмотреть массив, в котором записаны все возможные слова из {0,1}3, т.е. 8 слов (X1, … , X8), состоящих из 3 бит, как три слова W1, W2, W3, каждое из которых состоит из 8 бит (см. Рис. 2). Складывая слова W1 и W2 при помощи одной инструкции «побитовое ⊕ » для 8 битных регистров, мы получаем вектор значений суммы первых двух битов для всех слов из {0,1}3. Вычисляя аналогичным образом значение (W1 ⊕ W2) ⊕ W3, имеем значения функции ⊕ для всех слов из {0,1}3 , записанные в 8-битном результирующем регистре. При таком способе значения функции ⊕ на всех входах из {0,1}3 вычисляются за две инструкции «побитовое ⊕» для 8-битных регистров.
Приведем далее описание реализации генератора А5/1 в этой технике. Сопоставим каждому из ∈ {1, . . . ,64} разрядов РСЛОС 1, 2, 3 слово ∈ {0,1} , где – разрядность вычислительной платформы: 2.2 Предвычисление последовательностей РСЛОС
Используемая в данном пункте схема представления состояний регистров А5/1 в целом заимствована из [1]. Полиномы, описывающие РСЛОС генератора А5/1, являются примитивными и, как следствие, порождают двоичные рекуррентные последовательности с длинами 219-1, 222-1, 223-1 бит для 1, 2 и 3 регистров соответственно. Вычисленные полностью и записанные в виде циклических битовых массивов 1, 2, 3, они в сумме занимают около 1,5 Мбайт памяти вычислительного устройства. Вместо того чтобы каждый раз при тактировании вычислять новое состояние регистров достаточно увеличивать на 1 (или 0) индексы смещения , , в этих массивах (для регистров 1, 2, 3 соответственно, см. рис. 3). Пусть – бит ключевого потока с номером . Тогда вычисление +1 будет выглядеть следующим образом: = 1( ) ⊕ 2( ) ⊕ 3( ); 1 = 1( − 11); 2 = 2( − 12); 3 = 3( − 13); =
( 1, 2, 3); +1 = + 1 ⊕ ¬ ; +1 = + 2 ⊕ ¬ ; +1 = + 3 ⊕ ¬ ; +1 = 1( +1) ⊕ 2( +1) ⊕ 3( +1).
Здесь 1, 2, 3, – значения серединных бит регистров 1, 2, 3 и функции большинства от них на шаге с номером .
Рис. 3. Представление состояний РСЛОС А5/1 в виде циклических массивов.
Для того чтобы реализовать полный перебор всех возможных начальных состояний генератора А5/1 необходимо проверить все возможные сочетания троек , , : 0 ≤ ≤ (219 − 1), 0 ≤ ≤ (222 − 1), 0 ≤ ≤ (223 − 1).
Как и bitslice, такой подход устраняет условные переходы в программном коде генератора, что повышает эффективность его выполнения на современных CPU и GPU.
Применение «атаки Андерсона» с такой реализацией генератора требует введения дополнительного массива 2, который используется для того, чтобы по известному заполнению регистра 2 найти номер данного заполнения в циклическом массиве 2. 3. Результаты экспериментов
Мы реализовали «атаку Андерсона» на GPU и CPU с применением описанных выше техник bitslice и предвычисления РСЛОС. Результаты приведены в таблице 1. В таблице 2 для сравнения приведены данные по реализации обыкновенного метода прямого перебора, реализованного с использованием тех же техник.
В экспериментах на CPU использовался процессор Intel Core i7 930 2,8 ГГц. Приложение запускалось в 1 поток, для bitslice использовались 32-разрядные типы данных. Оптимизация приложения на уровне ассемблера и специальных SIMD-инструкций процессора (SSE2, AVX и т.д.) не производилась. Компилятор g++ 4.9.2 вызывался с флагом оптимизации -O5. Эксперименты с GPU проводились на NVIDIA GeForce GTX 750 Ti с компилятором nvcc 6.5. Таблица 1. Скорость «атаки Андерсона» (пространство перебора 253) в различных реализациях генератора А5/1 на GPU и CPU, в миллионах ключей в секунду. Таблица 2. Скорость прямого перебора (пространство перебора 264) в различных реализациях генератора А5/1 на GPU и CPU, в миллионах ключей в секунду.
Платформа bitslice 4. Заключение
Приведенные в таблице 1 результаты показывают, что «атака Андерсона» на одной далеко не самой производительной видеокарте имеет вполне реалистичное время (порядка 270 часов). Реализация данной атаки на современных кластерах из GPU позволит осуществлять криптоанализ А5/1 за минуты. Преимущество данной атаки перед Rainbow-методом [3] состоит в гарантированном восстановлении секретного ключа. Преимущество перед методом прямого перебора – в значительном меньшем пространстве поиска. Литература 1. Biryukov A., Shamir A., Wagner D. Real Time Cryptanalysis of A5/1 on a PC // Fast
Software Encryption. 2000. LNCS. Vol. 1978. Springer Berlin Heidelberg. pp. 1–18. 2. Biham E. A fast new DES implementation in software // Fast Software Encryption. 1997.
LNCS. Vol. 1267. Springer Berlin Heidelberg. pp. 260-272. 11. Semenov A., Zaikin O. Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem // Parallel Computing Technologies. 2015. LNCS. Vol. 9251 Springer International Publishing. pp. 222-230. Inverting A5/1 cryptographic function on a GPU with alternative A5/1 algorithm software implementations*
V.G.Bulavintsev, A.A.Semenov In this paper we study possibilities for speeding up A5/1 cryptographic function inversion procedure with the help of a GPU. By employing “the Anderson’s attack” for the A5/1 cryptographic function we reduce search space power from 264 to 253. To enhance this attack’s speed one needs an effective software implementation of the A5/1 generator. We describe two such implementations. The first one is based on a precomputation of A5/1’s shift registers output sequences. The second one uses “bitslice” technique. We compare CPU and GPU performance of these implementations. Experimental data shows that GPU version of bitslice implementation is the fastest. We conclude that a modern GPU-based computing cluster is able to invert the A5/1 cryptographic function in several minutes. 1. Biryukov A., Shamir A., Wagner D. Real Time Cryptanalysis of A5/1 on a PC // Fast
Software Encryption. 2000. LNCS. Vol. 1978. Springer Berlin Heidelberg. pp. 1–18. 2. Biham E. A fast new DES implementation in software // Fast Software Encryption. 1997.
LNCS. Vol. 1267. Springer Berlin Heidelberg. pp. 260-272. *This work was partially funded by RFBR (grants no.14-07-00403-a, 15-07-07891-а and 16-07-00155-а).