Cryptanalysis with graphical processing units (GPU ).pdf Первые идеи использования для решения трудоемких (переборных) задач специализированныхвычислительных архитектур возникали еще в 70-х годах прошлоговека. В качестве одного из наиболее ярких примеров можно привести предложенныйУ. Диффи и М. Хеллманом проект вычислительного устройства (см. [1, 2]), предназначенногодля криптоанализа шифра DES простым перебором (метод «грубой силы»).Стоимость устройства на тот момент составляла около 20 млн долларов. На сегодняшнийдень стоимость криптоанализа DES методом «грубой силы» понижена до^ 10 тыс. долларов. Соответствующие атаки используют специальные вычислителина ПЛИСах [3]. Следует отметить, что само по себе «программирование» ПЛИС требуетопределенных навыков, относящихся не столько к собственно программированию,сколько к схемотехнике.Другой перспективной в плане применимости к криптоанализу архитектурой являютсяактивно развивающиеся в последние годы графические ускорители (GPU),специализированные под потоковые вычисления. Понимание серьезных вычислительныхвозможностей GPU (пусть даже на немногочисленных пока классах задач) мотивируетих производителей постоянно совершенствовать архитектуру и программноеобеспечение.В работе сообщаются результаты применения метода «грубой силы» к криптоанализуизвестных систем шифрования: A5/1 и DES. На примере решения этих задачдемонстрируются трудности реализации даже весьма примитивных алгоритмовна современных GPU. Описывается ряд техник и приемов организации вычислений,позволяющих частично или полностью обходить ограничения GPU-архитектур прирешении переборных задач. В частности, детально описывается технология заменыусловных переходов арифметико-логическими выражениями. Ее применение к криптоанализуметодом «грубой силы» генератора A5/1 дает существенный прирост производительностипо сравнению с «обычной схемой». При решении этой задачи такжебыл использован простейший препроцессинг: независимо сгенерированные 64 сдвига,для каждого из РСЛОСов генератора A5/1 загружались в память GPU, после чегозапускался процесс перебора. В применении к криптоанализу шифра DES методом«грубой силы» предложена новая техникареализации на GPU дискретных функцийS-блоков: для построения максимально компактных представлений данных функцийформулами используются двоичные диаграммы решений (BDD).Из полученных в ходе исследований результатов можно сделать следующие выводы.Описанная атака на DES, реализованная на GPU, по стоимости превосходитподобные атаки, реализованные на ПЛИСах. Однако рост производительности GPUоставляет в этом направлении существенные перспективы. Атака на A5/1 методом«грубой силы» бесперспективна из-за большей, в сравнении с DES, длины ключа. Кромеэтого, данная атака по эффективности более чем в 200 раз проигрывает известнойSAT-атаке [3], реализация которой на GPU невозможна вследствие целого комплексаограничений современных GPU-архитектур: отсутствие поддержки рекурсии, неэффективнаяобработка условных переходов, ограниченные возможности адресации памяти.Можно надеяться, что огромный интерес в мире к GPU-вычислениям позволитв ближайшее время в значительной степени преодолеть эти ограничения.

Скачать электронную версию публикации