Перебор 40-битных ключей MS Office на GPU

В одной из первых записей в блоге я уже детально касался деталей шифрования, используемого в разных версиях Microsoft Office. Естественно, что меня интересовал вопрос, а удастся ли применить технологию вычислений на видеокартах (CUDA) для ускорения процесса перебора паролей для MS Office. Самое главное препятствие, которое существовало, - это алгоритм RC4, который является основным при шифровании почти во всех версиях Office. В интернете я видел отзывы, что реализация RC4 на CUDA оказывалась чуть ли не медленнее, чем на CPU, что означало, что алгоритм RC4 не подходит для ускорения на GPU.

Действительно, ключевой особенностью RC4 является использование таблицы перестановки (permutation) из 256 элементов, которая активно перемешивается при развертке (scheduling) ключа и при самом шифровании. Поскольку операции с глобальной и локальной памятью на CUDA занимают в сотни раз больше времени, чем с регистрами, то реализация RC4 “в лоб” действительно оказалась медленнее, чем на CPU (ниже приведен псевдокод развертки ключа RC4):

byte S[256]
for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap(&S[i],&S[j])
endfor

Но идея по оптимизации алгоритма RC4 очевидна и приходила в голову многим исследователям. Как пишет в своей статье Адриан Боинг, “использование быстрой разделяемой (shared) памяти  для хранения массива S дало существенный прирост в скорости”. Действительно, shared-память является очень быстрой и ее использование рекомендуется при оптимизации программ на CUDA. Боинг получил ускорение около 8 раз, у меня получились похожие результаты:

CPU (Core 2 Duo, 1.86 GHz, одно ядро) GPU (NVIDIA GTX 260, 1.35 GHz, 216 SP)
2.000.000 15.000.000

Таблица. Скорость развертки ключа алгоритма RC4 на CPU и GPU, ключей/сек

Естественно, что CPU-код для RC4 также был сильно оптимизирован (порядка 900 тактов/ключ), потому как если взять “наивную” реализацию RC4 (около 2.500 тактов/ключ), то можно получить ускорение не 8, а в 25 раз, что не является достоверным результатом.

Таким образом, с использованием современных GPU можно вскрыть 40-битный ключ MS Office (т.е. взломать любой пароль, независимо от его длины и сложности) менее, чем за 1 день (и это продемонстрировано в новых версиях программ GuaWord и GuaExcel, подбирающих ключ для файлов MS Word и MS Excel соответственно). Для сравнения, первые версии этих программ, работающие на Pentuim II/333, тратили на 40-битный ключ около 70 дней, а последняя версия на Core 2 Duo затратит около 8 дней на одном ядре и, соответственно,  4 и 2 дня на 2-х- и 4-х-ядерной машине. На GPU мы получаем скорость, равную 8-ядерному процессору!

Итак, алгоритм RC4 вполне поддается ускорению почти в 8 раз в помощью графических карт с технологией CUDA, хотя и не дотягивает по коэффициенту ускорения до лидеров - хешей семейства MD.

2 комментариев

  • By Ivan Golubev, 19 Июнь 2009 @ 23:21

    Любопытный результат :) Мне в своё время так задурили в голову эти “RC4 на GPU сделать нормально нереально”, что даже не стал пробовать. Выходит и RAR 2.x можно оформить на GPU. Хотя интерес это уже чисто теоретический.

    И, кстати, сильно оптимизированный RC4 занимает на iCore даже меньше 900 тактов — где-то 725-750 в зависимости от данных. Иными словами, ворд документ (где MD5+RC4_INIT+1xRC4_DECRYPT) на Q6600 можно заломать всего за 27 часов, считая все 2^40 вариантов.

    …Ну или вообще за несколько секунд, если подключить rainbow tables ;)

Other Links to this Post

  1. Все о паролях и практической криптографии » Эффективна ли архитектура Fermi для перебора паролей? — 14 Август 2010 @ 23:22

RSS лента комментариев к этой записи.

Оставить комментарий

You must be logged in to post a comment.

WordPress Themes