Скорость перебора паролей на CPU и GPU

(с) Иван Голубев, http://www.golubev.com
29 мая 2009 г.
«косметическая» правка 14 августа 2009 г.

Вычисления на GPU в последнее время стали очень популярными во всех областях, где есть возможность их использовать. Одним из таких направлений является криптография, более узко – подбор / перебор паролей. К сожалению, реальные результаты работы (как обычно это и бывает) приукрашаются в маркетинговых целях, так что становится не очень ясно, какой на самом деле выигрыш от использования GPU в этой области.

Длинные объяснения заканчиваются краткими выводами (которые, вероятно, и стОит прочитать при первом ознакомлении с этой статьёй).

На что тратится время при переборе паролей.

Если с десять лет назад каждый разработчик пытался придумать какой-то свой, оригинальный алгоритм шифрования (но, так как почти никто не был экспертом в области криптографии, подавляющее большинство таких «оригинальных» алгоритмов ломались в момент), то теперь с этим стало гораздо проще. Практически везде используются проверенные и стандартные схемы.

Для шифрования сначала необходимо преобразовать пароль в ключ заданного вида и размера (этап хэширования), а потом уже с помощью этого ключа собственно зашифровать данные (с помощью любого надёжного алгоритма вроде AES).

Для хэширования ещё совсем недавно массово использовался MD5, но (после обнаружения уязвимостей в алгоритме) его довольно быстро заменил SHA1. С SHA1 в данный момент уже тоже не совсем всё гладко (сложность нахождения коллизии составляет примерно 2^63, а недавно ещё и заявили о снижении этого числа до 2^52), но при использовании его в каком-нибудь «обрамлении» вроде PBKDF2 сложность (а, точнее, легкость) нахождения коллизии уже не так важна.

Один очень важный момент: при проверке паролей определяющей чаще всего является именно скорость хэширования, а не скорость шифрования. Практически везде сейчас используется так называемое «key strengthening», то есть усиление ключа путём добавления сложности на этапе генерации пароль -> ключ. Вместо одного преобразования SHA1 можно выполнить 10000, подавая результат первой итерации как вход на вторую и т.д. Для валидных паролей, которые собственно проверяются один раз, разница незаметна – генерится ключ 0.01 мс или 10 мс совсем не важно. А вот для задачи перебора паролей, когда проверяются миллиарды комбинаций, это уже очень ощутимо. Если, например, какой-то пароль можно подобрать за месяц, то он явно не стойкий. Однако, если использовать схему «усиления ключа» с дополнительными 10000 итераций, то на подбор того же самого пароля уйдёт уже не месяц, а 830 лет, что переводит пароль в разряд довольно устойчивых.

Алгоритм PBKDF2, описанный в RFC 2898, сейчас является одним из самых популярных для «key strengthening» и используется во многих приложениях. Рекомендуемый минимум итераций в нём составляет 1000 (а одна итерация требует выполнения двух SHA1_Transform действий, о которых ниже).

В некоторых случаях для проверки валидности пароля вообще не надо расшифровывать файл. Например, появившееся в WinZip 9 сильное шифрование на основе AES 128 & 256 bit на самом деле до AES доходит только в случае абсолютной правильности проверяемого пароля. Во всех остальных случаях выполняется только PBKDF2, который в свою очередь использует только SHA1. В RAR 3.x до AES доходим после 262144 итераций SHA1. Так что на фоне такого количества SHA1 инициализация и расшифровка нескольких байт с помощью AES занимает мизерные доли процентов от общих вычислений. В MS Office 2007 используется 50 000 итераций SHA1, в WPA, как и в WinZip, PBKDF2, но уже с количеством итераций 4096.

В PDF9 Adobe сильно промахнулся с новым алгоритмом, взяв одну итерацию SHA256 вместо 50-ти MD5 + 20x RC4, что ускорило скорость перебора паролей по сравнению с предыдущей версией практически на два порядка. Но валидация пароля после хэширования не требует никакого шифрования, так что и тут важна только скорость SHA256.

Правильный алгоритм шифрования делает невозможным сокращение пространства перебора для ключей. То есть, чтобы найти, например, 128-ми битный ключ надо перебрать 2^128 == 3.4 * 10^38 вариантов. Если допустить, что один компьютер перебирает один миллиард вариантов в секунду, у нас есть миллиард компьютеров и мы располагаем миллиардом лет, то за это время мы сможем проверить всего лишь 10^9 * 10^9 * 10^9 * 60 с * 60 м * 24 ч * 365.25 д ~= 3.16 * 10^34 вариантов, меньше 1/10000 требуемого диапазона.

Пример неудачного алгоритма шифрования: в классическом zip используются 96-ти битные ключи. Несмотря на прошедшие уже 20 лет с момента создания алгоритма, эти ключи до сих пор невозможно перебрать «в лоб». Однако, имея часть незашифрованного файла, можно провести так называемую plaintext attack, при этом сложность перебора упадёт с 2^96 всего до 2^38, что составляет всего пару часов работы для современного компьютера.

Все «сильные» алгоритмы шифрования (AES, Blowfish, etc) не позволяют провести plaintext атаку и не позволяют сократить пространство перебора. Так что единственная возможность получить доступ к зашифрованным файлам – знать правильный пароль.

Вывод: используемый алгоритм шифрования практически никак не влияет на скорость перебора паролей. Хороший алгоритм просто обеспечивает невозможность подбора ключа «в лоб». А вот уже для перебора паролей главным является именно преобразование пароля в ключ, а за это отвечают алгоритмы хэширования (MD5, SHA1), а не алгоритмы шифрования (AES, Blowfish).

Значение «количество итераций» мало что говорит.

MD5, SHA1 (и его потомки в виде SHA256, 384, 512) очень похожи. На входе есть состояние хэша (128 бит для MD5, 160 бит на SHA1) и блок данных размером в 512 бит (64 байт). На выходе, после операции хэширования, получаем новое состояние хэша. Это сердце алгоритма, функция обычно называется MD5_Transform, SHA1_Transform, etc.

Важно заметить, что размер блока является константой, всегда хэшируются именно 64 байта. Если подать на вход 1 байт, то он будет дополнен до 64 путём добавления нулей, символа-терминатора и 8-ми байтового значения длины блока. То есть, подать отдельно на вход хэш-функции 64 раза по 1 байту или один раз 64 байта – абсолютно одинаково в плане скорости обработки (не считая того, что при подаче 64 байт придётся символ-терминатор и значение длины обрабатывать уже в следущем блоке).

Для некоторых алгоритмов пишется количество итераций как количество вызовов функции по обновлению хэша. Но не всякое обновление ведёт к вызову Transform функции. Данные накапливаются в буфере и отдаются на Transform блоками по 64 байта. Например для RAR 3.x количество итераций равно 262144, но количество обрабатываемых блоков будет равно ((длина_пароля * 2 + 8 + 3) * 262144) / 64. Что, например, для паролей длиной в 4 символа составит 77824 (+ещё 17 дополнительных блоков для создания IV для AES).

Для алгоритма PBKDF2 требуется на каждую итерацию обработать 2 блока плюс ещё 2 для инициализации. Иными словами, для проверки одного пароля WinZip/AES (где количество итераций равно 1000) надо выполнить 2002 операции SHA1_Transform.

В Office 2007 используется 50 000 итераций и обрабатывается блок в 20 байт. Но подаются эти байты каждый раз отдельно, поэтому выходит именно 50 000 вызовов SHA1_Transform, а не 50000*20/64 = 15 625.

Что даёт приведение количества итераций к количеству блоков для Transform? Так как время вычисления хэша не зависит от данных в блоке и является константой, зная время хэширования одного блока и количество блоков, можно легко посчитать общее время хэширования. Также легко оценить, насколько быстрее или медленнее разные алгоритмы генерации паролей относительно друг друга.

Например, на основе рассчётов выше выходит, что скорость перебора паролей WinZip/AES в ~39 раз быстрее, чем 4-х символьных паролей в RAR 3.x. А скорость перебора паролей для Office 2007 в 25 раз ниже, чем для WinZip/AES. Точность этих вычислений, конечно, приблизительная. Для сложных алгоритмов инициализации блока данных (как в RAR 3.x) такая оценка может давать заметную ошибку. Но в большинстве случаев достаточно знать только порядок величины, а не абсолютное значение.

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

Насколько быстро можно хэшировать?

Теперь нас интересует вопрос, насколько же быстро можно обработать один 64-х байтный блок данных. Операции, используещиеся в Transform функции, самые простейшие – логические OR, XOR, NOT, AND, арифметическое сложение, сдвиги. Все действия производятся над 32-х битными целыми. Один блок данных легко помещается в кэш L1 любого из современных процессоров, так что скорость работы с памятью, её размер, размер L2 или RPM дискового накопителя не играет никакой роли. Иными словами, скорость перебора находится в прямой зависимости от скорости целочисленного ALU и практически никак не зависит от всего остального. У какого же из современных процессоров с этим лучше всего?

Процессоры.

Так как хэширование разных паролей никак не зависит друг от друга, то очень выгодно использовать какой-нибудь SIMD набор инструкций для их параллельной обработки. Лучше всего подходит SSE2 (хотя и от «старого» MMX до сих пор есть польза), позволяющий выполнять какую-либо операцию сразу с четырьмя 32-х битными операндами. В своем первом воплощении в Pentium 4 со скоростью работы SSE2 инструкций было не всё гладко (например, пересылки регистр->регистр стоили 6 тактов, а выполнение OR всего 2), но уже тогда выигрыш от их применения был вполне ощутимым. В данный же момент реализация SSE2 в Intel Core архитектуре просто великолепна: можно выполнить 3 операции за такт, причём результат будет готов уже на следующем такте (latency == 1 такт). То есть, пиковая производительность у Core составляет 12 операций с 32-х битными целыми за такт. Хотя не все операции можно выполнять на этой пиковой скорости.

Несмотря на появление новых ревизий ядра, перехода с 65nm на 45nm и, наконец, выхода Core i7, никаких заметных изменений в целочисленном ALU не произошло. Поэтому Core i7 работает практически также, как и его 65nm предок Core 2. Производительность зависит только от частоты, поэтому, например, Q6600 разогнанный до 3-х Ггц (что является вполне обычной практикой) будет ровно на 3/2.66 = 12.7% быстрее, чем Core i7 920 на штатной частоте (не считая turbo burst). Стоимость же Core i7, включая материнскую плату и память DDR3 заметно выше, чем у «старых» систем на Core 2 65/45nm.

Ситуация с AMD несколько хуже. Даже сейчас существует ещё довольно много систем с процессором Athlon XP. В своё время он очень хорошо конкурировал с P4, но вот SSE2 в нём нет. В архитектуре K8 AMD сделала поддержку SSE2, но в самом примитивном виде: 128-ми битные инструкции разбивались на две половинки и запускались на 64-х битном ALU. Что приводило к тому, что разницы между MMX кодом и SSE2 практически не было.

С появлением K10 (или Phenom) AMD наконец сделала поддержку SSE2 более достойным образом, однако Core 2 она заметно уступает. K10 может выполнить до 2-х операций с 4-мя 32-х битными целыми за такт, а результат операции будет готов только через такт (latency == 2 такта). То есть, пиковая производительность составляет 8 операций с 32-х битными целыми за такт. Что это означает в плане сравнения K10 vs Core 2: процессор от AMD будет в среднем в 1.5 раза медленнее, если мы сможем выстроить инструкции таким образом, чтобы latency не была лимитирующим фактором. В некоторых алгоритмах, учитывая ограниченное количество XMM регистров, сделать это очень непросто, а то и невозможно.

С другой стороны, не все операции Core 2 может выполнять на уровне «три за такт». Сложений можно выполнить только два, а сдвигов вообще один. K10 же умеет сдвигать два XMM регистра за такт, но уже с latency в 3 такта. Поэтому реальное соотношение производительности Core 2 vs K10 плавает где-то в районе 1.25-2x. K10 всегда медленней на задачах, которые зависят только от скорости SSE2 ALU, но может быть быстрее на алгоритмах со множеством чтений из памяти и отсутствием логических операций.

Phenom II, появившийся не так давно, отличается от просто Phenom'а гораздо меньше, чем Core i7 от Core 2 45nm. Но стоит, конечно, дороже.

Важно заметить, что в данный момент использование SSE2 является обязательным при параллельной обработке данных. Логическая операция над 32-х битным регистром или над 128-ми битным xmm регистром, содержащим четыре 32-х битных значения, выполняется за абсолютно одинаковое время. Считать на Core 2 без SSE2 это всё равно что взять GPU и отключить на нём ¾ всех потоковых процессоров.

Также, задача перебора паролей идеально распараллеливается, так как нет никакой зависимости между данными. Поэтому производительность растёт линейно в зависимости от частоты и количества ядер. Нет никакого смысла использовать «быстрый» двухядерник, если есть возможность задействовать «медленный» четырёхядерник. Иными словами, Q6600 на частоте 2.4Ггц будет работать как 4*2.4 = 9.6Ггц, а E8600 3.33 Ггц только как 3.33 * 2 = 6.66Ггц. Разница в скорости в 1.5 раза, а разница в цене примерное такая же, но в другую сторону.

Вывод: Лучшим процессором для перебора паролей в данный момент является Intel Core Quad. По соотношению цена / производительность выгоднее модели Core 2 65/45nm. Стоимость систем на Core i7 выше, а частота ничуть не лучше, чем у «старых» Core 2. Процессоры от AMD заметно отстают на SSE2 целочисленных вычислениях и при этом разница в цене между Core 2 и Phenom ничуть не компенсирует этого отставания. SSE2 обязательно к употреблению, иначе возможности современных процессоров просто не раскрыть.

Так всё-таки насколько быстро можно хэшировать?

Подробные рассчёты затрагивают слишком много деталей и требуют отдельной статьи, поэтому рассмотрим кратко только MD5. MD5_Transform состоит из 64 итераций. В каждой итерации используются похожие операции. Подробное описание можно найти, например тут – http://en.wikipedia.org/wiki/MD5.

Очень грубо скорость по количеству используемых операций можно оценить так:

Intel Core	F	G	H	I
Логические (L)	4	4	3	4
Сложение (A)	4	4	4	4 + CMP
Сдвиги (S)	2	2	2	2
Пересылки (M)	2	2	2	1
Возможное группирование инструкций	SAL SAL AML AML	SAL SAL AML AML	SAL SAL AML AM.	SAL SAL AML ACL
256 / 4 = 64 тактов на один блок	4 * 16	4 * 16	4 * 16	4 * 16

Ради сравнения – то же самое для AMD K10:

AMD K10	F	G	H	I
Логические (L)	4	4	3	4
Сложение (A)	4	4	4	4 + CMP
Сдвиги (S)	2	2	2	2
Пересылки (M)	2	2	2	1
Возможное группирование инструкций	SA SA AM AM LL LL	SA SA AM AM LL LL	SA SA AM AM LL L.	SA SA AM AL CL LL
376 / 4 = 94 тактов на один блок	6 * 16	6 * 16	5.5 * 16	6 * 16

Конечно такая оценка не учитывает много разных факторов, однако подходит чтобы быстро понять, насколько быстро теоретически можно выполнять MD5_Transform. Опытные же результаты, как обычно, выглядят похуже. Но не так уж сильно:

MD5_Transform 72 такта в 64-х битном режиме.

MD5_Transform 90 тактов в 32-х битном режиме.

MD5_Transform в простейшей реализации на SSE2 при обработке всего 4-х блоков за раз 128 тактов.

SHA1_Transform 175 тактов в 32-х битном режиме, 162 такта в 64-х битном.

С SHA256 точного значения нет (так как используется SHA256 значительно реже), но SHA256_Transform займёт как минимум 425 тактов. Присутствие значительного бОльшего количества сдвигов и сложений скорее всего увеличит это значение.

Использование 64-х битного режима позволяет задействовать в два раза больше XMM регистров, что, в свою очередь, помогает решить проблемы с latency. Особенно сильно это влияет на MD5, где операций очень мало, так что постоянно приходится ждать результаты предыдущих вычислений, если обрабатывать всего 4 блока данных за раз.

Теоретические и практические результаты.

Ну и наконец сводная таблица, ради которой всё и затевалось. Сравнение скоростей для различных видов паролей. Были использованы:

crark http://www.crark.net
Advanced Archive Password Recovery http://www.elcomsoft.com/archpr.html
Elcomsoft Wireless Security Auditor http://www.elcomsoft.com/ewsa.html
Advanced PDF Password Recovery http://www.elcomsoft.com/apdfpr.html
BarsWF http://3.14.by/en/md5
Мои эксперименты с GPU, в том числе http://www.golubev.com/rargpu.htm (Хотя ARCHPR на самом деле тоже является «моим экспериментом»).

Скорость замерялась на одном ядре Intel Core 2 Q6600 @ 2.4Ггц, ATI HD4850 на штатной частоте 625Мгц, nVidia GTX 260 /w 192SP тоже на штатной частоте 1.242Ггц.

Алгоритм	Количество блоков	Требуется тактов	Теоретическая скорость	Практическая скорость	ATI HD4850	x	GTX 260	x
RAR 3.x passlen = 4	(4 * 2 + 11) * 4096 + 17 = 77841 x SHA1	13 622 175	176	160(ARCHPR) 168 (crark)	3120	19.5	2080	12.4
RAR 3.x passlen = 6	(6 * 2 + 11) * 4096 + 17 = 94225 x SHA1	16 489 375	145	134 (ARCHPR)	2625	19.5	1695	12.6
WinZip AES	(1000 + 1) * 2 = 2002 x SHA1	350350	6850	6700	135K	20.1	-	-
WPA	(4096 + 1) * 2 * 2 = 16388 x SHA1	2867900	836	820	14К	17	9800	12
MS Office 2007	50005 x SHA1	8750875	274	94	-	-	3300	37.5
PDF9	1 x SHA256	-	-	5.09M	-	-	74.4M	14.6
MD5 single hash	1 x MD5 * (45/64)	51	47M	44.5M	891M	20	563M	12.7

Как видно, соотношение скоростей на GPU к скорости на CPU довольно однообразное. ATI HD4850 примерно в 20 раз быстрее одного ядра Q6600 на частоте 2.4Ггц, GTX 260 примерно в 12 раз. Значение 37.5 для Office 2007 появилось только из-за неоптимизированного CPU кода (забавно что для Office 2007 используется SSE2, но настолько неудачно, что лучше бы вообще не использовался). Скорость перебора на GPU зависит только от частоты работы ALU (всё как с CPU), скорость памяти и объём ничего не значат. Зная разницу в частоте и количество SP можно довольно точно оценить производительность разных GPU одного семейства.

Сравнивать напрямую по цене CPU и GPU довольно глупо – видеокарта не может работать самостоятельно, да и CPU тоже. Системы с двумя и более процессорами сразу уводят нас на другой уровень цен, в то время как нет никакого экономического смысла рассматривать эти (серверные) процессоры с большим L2 кэшем для задач перебора паролей. С GPU же ограничивающим фактором является количество PCI-E разъёмов на материнской плате. На самых простейших платах он всего один, на большинстве – два. Материнские платы с 4-мя разъёмами уже довольно редки. Причём нужно не только 4 разъёма, но ещё и место под сами карты – занимают-то они обычно 2 слота. 4 раза по 2 слота встречается, судя по всему, только у MSI K9A2 Platinum. Есть 6-ти слотовый P6T6 WS Revolution, но там могут поместиться только «одинарные» карты.

Похоже, собрать систему с 4-мя ATI HD4870x2 невозможно в принципе (неплохое описание всех возникающих проблем тут: http://forums.guru3d.com/showthread.php?p=2862271). Системы с 4-мя двойными nVidia картами существуют (например http://fastra.ua.ac.be/en/specs.html), но проблем и там хватает. Начиная с мощного блока питания и корпуса, куда можно всё нормально поместить и заканчивая установкой драйверов.

В итоге получается такой список с точкой отсчёта производительности на 4-х ядрах Q6600 на частоте 2.4Ггц:

Название	Частота, кол-во ядер	Соотношение	Цена CPU или GPU	Общая цена системы
E2160	1.8 x 2	0.38x	?	<$300
Q6600	2.4 x 4	1x	$220	~$600
nVidia 8600 GT	1.188 x 32	0.5x	?	~$650
nVidia 9800 GT	1.242 x 112	1.75x	$120	~$720
ATI HD4770	0.75 x 640	5x	$100	~$700
ATI HD4850	0.625 x 800	5x	$120	~$720
nVidia GTX295	1.242 x 240 x 2	7.5x	$500	~$1200
ATI HD4870x2	0.75 x 800 x 2	12x	$400	~$1100
4x ATI HD4770	0.75 x 640 x 4	20x	$400	~$1200
2x ATI HD4870x2	0.75 x 800 x 2 x 2	24x	$800	~$1600
4x nVidia GTX295	1.242 x 240 x 2 x 4	30x	$2000	>$3000
TACC1441 FPGA	?	2.4x	$4000	~$4500

Для систем с медленными GPU (вроде 8600 GT) имеет смысл считать производительность как CPU+GPU (что тут сделано не было). Для быстрых же GPU процессор будет загружен дополнительными рассчётами и синхронизацией задач, так что считать дополнительно на нём просто не имеет смысла. В некоторых случаях четырёхядерного процессора может и не хватить для систем с 8-ю GPU.

Как видно, самым интересным решением в плане цена/производительность является связка из 4-х HD4770. Однако, опять же, требуется материнская плата, где можно разместить 4 такие карты – несмотря на то, что HD4770 одночиповая карта, система охлаждения занимает дополнительный слот.

TACC1441 приведён для примера в качестве «железного» решения. Это плата на основе FPGA, поддерживается ПО от AccessData (http://www.forensic-computers.com/TACC1441.php). Как видно, никакой конкуренции современным GPU он составить не может.

Осталась одна «маленькая» проблема – практическое полное отсутствие ПО для карт ATI. Карты от nVidia поддерживаются в ElcomSoft's Distributed Password Recovery, а вот с ATI пока всё совсем плохо.

Вывод: прирост в производительности от использования одного GPU примерно 4х-5ти кратный по сравнению с современной четырёхядерной системой. Карты от ATI заметно быстрее при той же цене, однако для них практически нет ПО. При росте количества GPU в системе нелинейно растут проблемы – появляется потребность в мощном блоке питания, специальном корпусе, эффективной системе охлаждения и т.д.

А почему такой маленький прирост?!

TACC1441 обещает 60-ти кратный прирост. EDPR декларирует 100x и 200x. Почему же тут получилось «только» 30? Ответ прост: маркетологи и пиарщики тоже работают. Сравнивая неоптимизированный CPU код на системе начального уровня с top решением на 4xGTX295 можно получить совершенно потрясающий результат. Например такой: E2160 1.8Ггц vs 4xGTX295 для документа MS Office 2007 в EDPR == прирост в 229 раз!

Вывод: всегда полезно думать самому.

Какие пароли можно считать стойкими?

Алгоритм	Длина	Набор символов	Количество вариантов	Время перебора на «обычной системе» Q6600 + HD4770	Время перебора на системе 4xGTX295	Время перебора на суперкластере 100x 4xGTX295
RAR 3.x	4	Латинские маленькие + большие + цифры + спецсимволы	96^4 = 84934656	7.6 часов	1.5 часа	45 сек
RAR 3.x	6	Латинские маленькие + большие + цифры + спецсимволы	96^6 = 782757789696	8 лет	1.33 лет	5 дней
WPA	8	Латинские маленькие + большие + цифры	62^8 = 218340105584896	495 лет	82 лет	300 дней
WinZip 9+	8	Латинские маленькие + большие + цифры	62^8 = 218340105584896	51 год	8.5 лет	31 год

Вывод: неутешительный для brute-force атаки. При правильно выбранном пароле из 8-ми символов подобрать его в осмысленное время просто невозможно.

Авторизуйтесь для добавления комментариев!