1. Количество ядер CUDA увеличено (самый слабый на сегодня GPU семейства Fermi GTX 460 имеет 336 ядер, тогда как самая мощная карта прошлого поколения имела 240).
2. Количество регистров на мультипроцессор увеличено вдвое (с 16384 до 32768), объем разделяемой памяти - втрое (с 16К до 48К). Именно эти два параметра оказывают  ключевое вляние на загрузку мультироцессора.
3. Введена возможность настоящих вызовов функций (до Fermi все функции интерпретировались как встроенные (inline)) - соответственно, появились указатели на функции, полная поддержка наследования методов в C++ и разрешена рекурсия.
4. Появился кэш L1/L2 - обращения к локальной и глобальной памяти теперь кэшируется.
5. Появились новые целочисленные команды в “ассемблере” Fermi PTX и улучшена поддержка стандарта IEEE 754 для плавающей арифметики.

По всем пунктам, как видно, архитектура Fermi превосходит предыдущую. Давайте попытаемся потвердить это на реальных задачах и программах. Я буду сравнивать GTX 460 c 336 ядрами CUDA и GTX 260 со 216 ядрами - судя по маркировке, эти карты занимают примерно один уровень в своих поколениях. Посморим, будет ли реальный прирост скорости близок в полуторакратному.

1. Сначала протестируем карту на задаче, традиционно считающейся идеальной для GPU - перебор паролей хэшей семейства MD (MD5, SHA). Проверим как программы, считающие эти хэши однократно, так и криптосистемы, использущие многократное циклическое вычисление хэшей (RAR 3.x, MS Office 2007)
   

   Алгоритм	Программа	NVIDIA GeForce GTX 260	NVIDIA GTX 460	Ускорение, раз
   MD5	ighashgpu	690.000.000	768.000.000	1.11
   MD5	BarsWF v. 0.B	690.000.000	680.000.000	0.98
   SHA-1 (77841 раз)	cRARK 3.3	2600	3840	1.47
   SHA-1 (50000 раз)	Accent Office Password Recovery 4.1	4600	6340	1.37

   Таблица 1. Скорость перебора в криптосистемах, основанных на хэшах семейства MD5, паролей/сек

Хотя одному приложению не удалось продемострировать рост на GTX 460, остальные результаты вполне можно назвать ожидаемыми - новый видеопроцессор оказывается быстрее, достигая почти 1.5-кратного превосходства. Очень жаль, с другой стороны, что NVIDIA не добавила в список инструкций Fermi побитовый циклический сдвиг (rol/ror), который очень часто используется в криптоалгоритмах. Его аналог, недавно появившийся в архитектуре ATI - bitalign - дает, по результататам Ивана Голубева, 40% ускорение.

2. Теперь рассмотрим криптоалгоритмы, реализация которых на GPU традиционно считается неудобной. Самая частая причина этого, что они слишком активно и/или слишком много используют память. Из наиболее часто использующихся в современных криптосистемах к ним относятся RC4, Blowfish.
   

   Алгоритм	Программа	NVIDIA GTX 260	NVIDIA GTX 460	Ускорение, раз
   RC4	GuaPDF	13.600.000	7.200.000	0.5
   BlowFish	NMSS	23.700 (*)	19.000 (**)	0.8

^(*) - быстрее, чем на CPU Core 2 1.86 ГГц
^(**) - медленнее, чем на CPU Core 2 1.86 ГГц

Таблица 2. Скорость перебора в криптосистемах, неудобных для реализации на GPU, ключей/сек

Здесь ситуация резко меняется - карта на архитектуре Fermi оказывается гораздо хуже, чем ее предшественница. Особенно странна ситуация с RC4 - все изменения кода ( в т.ч. увеличение используемой разделяемой памями, которая очень помогала при оптимизации этого алгоритма на GTX 260) - давали только большее ухудшение скорости.

На мой взгляд, данные результаты показывают, что, несмотря на увеличение в 2 раза регистров и в 3 раза разделяемой памяти на один мультипроцессор,  увеличение в 4-6 раз количества ядер CUDA на этот же мультипроцессор приводит к тому, что в некоторых задачах он загружается хуже, чем в предыдущем поколении. Я также не заметил особого влияения нового кэша L2 в криптографических алгоритмах с интенсивным использование памяти.

В любом случае, эффективность архитектуры Fermi для перебора паролей является неоднозначной и она требует, как минимум, дополнительной оптимизации и настройки алгоритмов. Но в некоторых случаях все равно она может оказаться хуже, чем архитектура предыдущего поколения.

Меньше она стала потому, что я перевел ее на Driver API (как известно, CUDA поддерживает два вида API - Runtime и Driver, у каждого есть некоторые перимущества, но Driver API является более низкоуровневым и позволяет использовать некоторые низкоуровневые оптимизации). Именно из-за них программа стала быстрее - немного, где-то до 5%, но тем не менее эти 5% должны вернуть cRARk славу самой быстрой программы

Наконец, в новой версии появился ключ -d, которые задает соотношение между скоростью и плавностью вывода на экран. Ключ -d0 обеспечивает максимальную скорость, а -d5 - максимальный комфорт работы.

Также  предыдущей версии программы, 3.25, был немного оптимизирован CPU-код, особенно для семейства Intel Core i5/i7. Теперь на нем один пароль проверяется за 13.000.000 тактов, что означает, что функция SHA вычисляется за 168 тактов! На всех остальных процессорах Intel в 32-битном режиме эта цифра не падала меньше, чем до 177 тактов.

Прошу о всех проблемах с новой версией писать сюда в комментарии или по e-mail. Также я планирую в следующей записи в блоге коснуться возможностей языка описания паролей, используемого в cRARk.

1. Accent Office Password Recovery v. 3.50, поддерживающий как карты NVIDIA, так и ATI;
2. Parallel Password Recovery (Office module) v. 1.5.1 (поддерживает только NVIDIA GPU);
3. Elcomsoft Distributed Password Recovery v. 2.90 с поддержкой карт NVIDIA (компания Elcomsoft имеет специальный продукт для восстановления паролей MS Office - AOPR, но он пока не имеет поддержки GPU)

и три версии Office, наиболее распространенные сегодня: MS Office XP, 2007 и 2010.

Для тестирования каждой версии были взяты по два файла - один со стандартной длиной ключа (128 бит для всех версий Office) и один с нестандартной (алгоритм RC4 с ключом 120 бит для Office XP и AES с ключом 256 бит для Office 2007 и 2010).

Тестирование проводилось на типичных современных компьютерах, два из которых были десктопами и один ноутбук:

1. Intel Core i5-750 (2.66 GHz, 4 ядра), NVIDIA GeForce GTX 260 (216 потоковых процессоров), 4 GB RAM, 64-битная Windows 7
2. Intel Core 2 E6300 (1.8 GHz, 2 ядра), NVIDIA GeForce 9800GT (112 потоковых процессоров),2 GB RAM, 32-битная Windows XP
3. AMD Athlon II M300 (2.00 GHz, 2 ядра), ATI Mobility Radeon HD 4300 (80 потоковых процессоров), 2 GB RAM, 64-битная Windows 7

Результаты тестирования приведены в следующей таблице (разным цветом выделены разные компьютеры; в том случае, если тестирование проводилось до конца, указано время и скорость, иначе - только скорость). Тестировался только режим полного перебора паролей начиная с длины 1, только маленькие латинские буквы.

Таблица. Скорость перебора паролей MS Office на разных CPU и GPU.

По данным результатам можно сделать несколько выводов:

1. Утилиты по восстановлению паролей MS Office плохо справляются с нестандартным шифрованием (нестандартной длиной ключа) - были отмечены как случаи нераспознавания такого файла, так даже и зависания программы. Даже Parallel Password Recovery - явный лидер, справившийся со всеми примерами, в одном случае не использовал GPU при нестандартной длине ключа в 120 бит.
2. При переборе паролей файлов MS Office XP/2003 лидером по скорости является программа Parallel Password Recovery, т.к. она единственная использует GPU
   в данном случае, а скорости на CPU у нее также впечатляющие.
3. В случае стандартных файлов MS Office 2007 и 2010 скорости всех программ стали практически одинаковыми (отставание EDPR связано с тем, что она не использовала CPU, а скорость перебора на GPU у нее такая же, как и у остальных). Такое равенство связано с тем, что эти версии Office используют специально замедленную процедуру получения ключа из пароля (а именно, 50.000 и 100.000 вызовов функции хэширования SHA-1), и все разработчики давно оптимизировали эту функцию до максимума.
4. Скорость перебора файлов Office 2010 во всех программах и любых процессорах (CPU и GPU) ровно в два раза меньше, чем файлов Office 2007. Это напрямую связано с двухкратным увеличением количества вызовов SHA-1. Можно сказать, что файлы Office 2010 ставят новый рекорд в скорости перебора паролей и обеспечивают самое стойкое шифрование, свергая с пьедестала прошлого лидера - зашифрованные архивы RAR 3.x.
5. Программа Accent Office Password Recovery, хотя и плохо справляется с нестандартными файлами, тем не менее выделяется тем, что очень грамотно использует графический процессор: это единственная программа, позволяющая более-менее комфортно работать на компьютере при переборе паролей на GPU (остальные программы зависают на несколько секунд перед каждой отрисовкой экрана), а также единственная поддерживает карты ATI, даже такую маломощную как ATI Mobility Radeon HD 4300. Благодаря этому эта программа показывает в 3 раза большую суммарную скорость при переборе паролей MS Office 2007 и 2010 на третьем тестовом компьютере.

Спасибо всем компаниям, предоставившим мне регистрационные ключи для тестирования их продуктов - без них полноценное тестирование скорости было бы невозможным. В дальнейшем я планирую продолжить тестирование взломщиков паролей - заинтересованных производителей прошу связываться со мной по е-mail.

Рассмотрим обобщенный процесс верификации пароля в MS Office,  который был придуман еще в ранних версиях Office и принципиально не поменялся до сих пор.

Схема проверки пароля в MS Office

• Шаг 1. Из пароля и случайной привязки (salt) через одно- или многократное хэширование получается строка бит.
• Шаг 2. Из этой строки берется ровно столько бит, сколько нужно для генерации ключа (в разных версиях от 40 до 256).
• Шаг 3. Еще одна случайная строка (Verifier) длиной 128 бит зашифровывается на полученном ключе и результат EncryptedVerifier сохраняется в файле Office.
• Шаг 4. Тот же самый Verifier однократно хэшируется.
• Шаг 5. Результат хеширования зашифровается на полученном на шаге 2 ключе и сохраняется в файле как EncryptedVerifierHash.

Тогда, по замыслу разработчиков, для проверки пароля надо было сгенерировать ключ, расшифровать EncryptedVerifier, найдя исходный Verifier, получить его хэш, зашифровать по шагу 5 и сравнить полученный результат с EncryptedVerifierHash. Когда алгоритмом хэширования в Office XP был MD5, а шифрования - RC4, все работало именно так. Но в Office 2007 разработчики заменили MD5 на SHA1, а RC4 на AES.

Казалось бы, все стало только лучше - SHA1 явно более стойкий, чем MD5, а AES - современный стандарт шифрования. Но,

1. MD5 генерировал хэш длиной 128 бит, а SHA1 - 160. AES же работает блоками по 128 бит.
2. RC4 был потоковый шифр, а AES - блочный.

Первое привело к тому, что VerifierHash на шаге 5 перестал быть кратен длине блока AES, поэтому для его зашифрования пришлось использовать два 128-битных блока. Лишние 96 бит, недолго думая, заполнили нулями. А это уже разрушило всю преполагаемую схему аутентификации. Действительно, теперь шаг 5 можно пройти в обратном порядке, расшифровав EncryptedVerifierHash, и если мы получим в результате последние 96 бит нулей, то пароль верный! Больше нет необходимости делать шаги 3 и 4!

Если бы алгоритм шифрования остался RC4, то этот трюк не удался бы, потому как в нем состояние ключа меняется при каждой операции шифрования, и поэтому нам необходимо было бы все равно сделать шифрование на третьем шаге. Но замена RC4 на AES решила эту проблему.

Да, это нельзя назвать серьезной уязвимостью, и на скорость подбора пароля Office это тоже не влияет, так как основной по трудоемкости является шаг 2, где выполняется 50.000 (Office 2007) или 100.000 (Office 2010) преобразований SHA1. Интересно то, что в модификации Office 2010 разработчики предложили несколько новых улучшений, но описанную проблему проигнорировали. Забавно также, что похожая проблема была в старой версии MS Office 97, когда процесс верификации пароля в MS Word удалось убыстрить примерно с помощью такого же трюка (не нужно было выполнять несколько шагов, предложенных Microsoft). Именно поэтому восстановление паролей Word 97 происходит быстрее, чем Excel 97.

Миф 1.  Пароль хранится где-то внутри архива и можно так взломать RAR, чтобы он пароль не проверял.

К счастью, на сегодняшний день практически всем уже стало понятно, что это не так. Действительно, RAR зашифровывает поток данных после компрессии при помощи алгоритма AES, получая зашифрованный текст. При разархивации RAR пытается расшифровать его с введенным паролем, независимо от того, является этот пароль правильным или нет. Иными словами, понять, что пароль является верным, можно только после расшифрования.

Миф 2.  Существует некий универсальный пароль, которым можно расшифровать любой архив.

Нет, поскольку RAR использует симметричный алгоритм шифрования, то ключ шифрования (он же и ключ расшифрования) только один. Никакого другого ключа (и пароля, соответственно) не существуют.

Миф 3.  RAR при создании архива с паролем может вставить куда-то внутрь потока данных отдельные биты ключа, что позволит практически мгновенно расшифровать любой архив.

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

Тем не менее, это не доказывает на 100%, что скрытого канала в RAR нет. Скрытые каналы по своей природе могут быть очень хитрыми, и только открытый исходный код позволит полностью опровергнуть этот миф.

Миф 4.   Если у меня есть один файл из архива в незашифрованном виде, пароль  можно сломать быстрее.

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

Миф 5.    Для того, чтобы понять, что пароль верный, надо расшифровать, затем полностью разархивировать файл, а потом проверить CRC.

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

Миф 6.    Если ввести любой пароль и прервать RAR, когда он дошел до 99% разархивации файла, то можно получить разархивированный файл без всякого пароля.

RAR прерывать не нужно - есть опция “-kb”, которая и так сохранит файл, даже если контрольная сумма не совпала. Очевидно, что с настоящим файлом он не будет иметь ничего общего, более того, как было сказано выше, скорее всего процесс разархивации даже не дойдет до конца, и файл не будет иметь ни правильного содержимого, ни правильного размера.

Действительно, ключевой особенностью 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 раз, у меня получились похожие результаты:

Таблица. Скорость развертки ключа алгоритма 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.

Как пишет сам автор, это больше демонстрация возможностей современных видеокарт, чем реальная программа для перебора паролей. Действительно, поддерживаются только RAR-архивы 3.x с зашифрованными заголовками и только атака по словарю, но, самое главное то, что эта программа показывает невиданные на сегодняшний день скорости взлома паролей RAR - тысячи паролей в секунду. До сих пор у самых совершенных программ, использующих многоядерный перебор, эта скорость только приближалась к 1.000 паролей в секунду (а можно еще вспомнить, что несколько лет назад, при появлении новой, 3-ей версии RAR, предположения о скорости перебора были “несколько паролей в секунду”).

Таблица. Скорость перебора 4-х символьных паролей RAR на CPU и GPU, паролей/сек

Итак, по этой таблице можно сделать несколько важных выводов:

1) Перебор паролей RAR тоже убыстряется на GPU, но речь уже не идет о сотнях раз, как в случае хешей, а о 5-20-кратном ускорении

2) Потенциально пароли RAR 3.x могут вскрываться на современном аппаратном обеспечении с скоростью несколько тысяч паролей в секунду

3) Карты ATI гораздо лучше приспособлены для задач по перебору паролей. Так, карта HD4850 стоимостью $130 показывает в 1.5 раза лучшие результаты, чем карта GTX 260 стоимостью $200. Таким образом, карты ATI оказываются эффективнее почти в 3 раза по соотношению скорость перебора/стоимость. (Аналогичный вывод можно сделать, сравнив скорости взлома MD5 с помощью программы BarsWF, которая есть в версиях CUDA и Brook). С другой стороны, количество потоковых процессоров (SP) у карт ATI примерно во столько же раз больше. Также можно отметить, что написание программ под технологию ATI, конкурирующую с CUDA - ATI Stream - несколько более трудоемко, чем под CUDA.

UPD от 27.05.2009.
В связи с выходом новой версии cRARk, которая стала быстрее до 2 раз и возможностью протестировать на видеокарте NVIDIA GTX 260 216 SP я публикую новую таблицу сравнения скоростей:

Таблица. Скорость перебора 4-х символьных паролей RAR на CPU и GPU, паролей/сек

Первое, и самое главное: в таких задачах, как перебор паролей, которые по своей сути допускают легкое распараллеливание, использование CUDA оказывается чрезвычайно простым. Написание исходного текста программы на CUDA оказалось очень легким: я взял код функции SetCryptKeys() из исходных текстов UnRAR, добавил к ней свободно распространяемые реализации криптографических функций SHA-1 и AES, после чего вставил у всех используемых функций спецификатор __device__, который означает, что эти функции будут выполнятся на устройстве (GPU). По сути, никаких переделок кода с языка C/C++ на CUDA не потребовалось и первая же версия программы, которая смогла скомпилироваться, выдавала осмысленные результаты!

Далее, сложность отладки под GPU оказалась преувеличенной. В опциях компилятору можно указать “-deviceemu”, после чего отлаживать становится возможным в режиме эмуляции, под любимым отладчиком, например, прямо в Visual Studio. Да, в этом режиме эмуляция GPU невозможна на 100%, и некоторые тонкие моменты (например, синхронизацию потоков) там не отладить, но тем не менее режим эмуляции позволяет отладить большинство возникающих проблем.  Также я столкнулся с тем, что запись по невыровненному адресу в режиме эмуляции работает, а на реальном устройстве - нет:

long A[N], i;

* (long *) ((char *)A + 3) = i;  // запись по адресу,
                                 // не кратному 4

Компилятор nvcc, несмотря на версию 2.1, все еще является сыроватым. Так, я несколько раз в разных ситуациях получал сообщение о внутренней ошибке компилятора, и совершенно было непонятно, где искать проблему, так номер строки в этом случае не выводится. Опытным путем было выяснено, что он не любит использования функции memcpy(), которая часто встречается в реализации криптопримитивов.  По логике, должно быть сообщение об ошибке вызова функции хоста (__host__) на устройстве, вместо этого выдавалось сообщение: “Signal: caught in PU_adjust_addr_flags phase”.

Следующая проблема, которая не описана как следует в документации, заключалась в том, что каждый вызов ядра (kernel) должен выполняться на GPU не более 5 секунд. Поскольку для проверки одного пароля RAR необходимо сделать около 70.000 преобразований SHA-1, то, задавая довольно большие размеры сетки (grid), можно очень скоро упереться в этот барьер, получая сообщение типа “the launch timed out and was terminated”.

Наконец, оптимизация программ на CUDA оказалась довольно трудоемкой и малоэффективной. Так, первая рабочая версия cRARk под CUDA выдавала около 200 паролей в секунду, нынешняя версия показывает 240 (на GeForce 8600GTS). При этом мне кажется, что скорость можно поднять еще как минимум в 2 раза (мое предположение основывается на скорости вычислений MD5 на CUDA, рассмотренной в прошлый раз). На сайте crark.net я выложил исходники реализации перебора паролей RAR на CUDA. Если есть желающие помочь в оптимизации этой бесплатной утилиты, буду рад.

Таким образом, технология CUDA, бесспорно, является очень эффективной и легкой в применении в задачах перебора паролей, но при практической реализации возникает ряд подводных камней, затрудняющих получение наилучших результатов. В частности, для рассмотренной задачи перебора паролей RAR пока скорость на топовых моделях видеокарт и процессоров оказывается примерно одинаковой - около 1000 паролей в секунду.

Действительно, семейство хэшей MD (куда относятся алгоритмы MD4, MD5, SHA) отличает простота и компактность. Они не используют никакую дополнительную память, кроме непосредственно сообщения и выходного значения, а все операции представляют собой простые арифметические и логические действия над 32-битными данными, а именно: AND, OR, XOR, NOT, сложение и циклический сдвиг, для которых в ассемблере обычно есть соответствующие команды.

Оптимизация перебора хэшей MD5 и аналогичных состоит в следующем:

1. Использование параллельных вычислений, т.к алгоритм перебора паролей прекрасно распараллеливается - для процессоров на 2, 4 и более потоков (по количеству ядер), для GPU - на 64/128/256 и более.
2. Вычисление нескольких хэшей одновременно в одном потоке. Для этого подходят MMX- и SSE-инструкции, позволяющие одновременно вычислять 2 и 4 хэша соответственно. Перевести ассемблерный код на использование MMX или SSE довольно просто - надо заменить обычные ассемблерные инструкции и регистры на соотвествующие MMX/SSE. Код ниже показывает соответствие обычного и SSE-кода одного из шагов на первом раунде MD5:
   

   xor edi, edx	pxor xmm4, xmm3
   and edi, ebx	pand xmm4, xmm1
   xor edi, edx	pxor xmm4, xmm3
   lea eax, DWORD PTR 3614090360[edi+eax]	paddd xmm0, XMMWORD PTR _DATA_R0[0] paddd xmm0, xmm4
   mov edi, ebx	movdqa xmm4, xmm1
   add eax, DWORD PTR [esi]	paddd xmm0, XMMWORD PTR [esi]
   rol eax, 7	movdqa xmm5, xmm0 pslld xmm0, 7 psrld xmm5, 25 por xmm0, xmm5
   add eax, ebx	paddd xmm0, xmm1

   Как видно, коды очень похожи, за исключением реализации циклического сдвига - вместо одной операции на SSE приходится делать 4: два обычных сдвига в разные стороны и потом объединение результатов. (Странно, что даже в самой последней версии SSE 4.2 команд для циклических сдвигов так и не появилось).

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

Для тестирования скорости подбора MD5-хэшей использовались следующие программы:

1. Тестовый, неоптимизированный код под CUDA MD5-PoC от Андрея Беленко (в исходниках под Visual C)
2. Бесплатная утилита от Elcomsoft Lighting Hash Cracker (LHC) v. 0.52
3. Бесплатная утилита BarsWF v. 0.8 от Сваричевского Михаила
4. Коммерческая программа Extreme GPU Bruteforcer (EGP) v. 1.4.2 от InsidePro.
5. Коммерческий профессиональный продукт Elcomsoft Distributed Password Recovery (EDPR) v. 2.71
6. Бесплатная утилита UDC v. 3.2.1.0, бывшая чемпионом по скорости до внедрения технологии CUDA

Тесты проводились на Intel Core 2 Duo 6300, 1.86 GHz + NVIDIA GeForce 8600 GTS, 675 MHz. Результаты представлены в таблице:

Таблица. Скорость перебора MD5-хэшей на CPU и GPU, миллионов хэшей/сек

Примечание *. В одном случае утилита LHC искомый пароль не нашла.

Выводы:

1. Технология CUDA кардинально меняет представления о скорости перебора хэшей и стойкости паролей. Даже самая первая, неоптимизированная версия переборщика показывает скорость выше, чем самая быстрая, оптимизированная под SSE версия для CPU. При этом тактовая частота GPU была в 3 раза меньше. Современные графические карты способны вычислять более полумиллиарда хэшей в секунду, что означает, что они способны перебрать все буквенно-цифровые пароли до 8 символов включительно за пару дней!
2. Программа BarsWF оправдывает звание самого быстрого взломщика MD5, показывая фантастические результаты как на CPU, так и на GPU. По утверждению автора, она тратит 58 тактов CPU на один хэш, что, бесспорно, является впечатляющим. (У меня есть код MD5, который требует 130 тактов для полного MD5, т.е. с исключенным последним раундом он бы исполнялся около 100 тактов. Куда деваются еще 40, непонятно). В любом случае, поздравляем автора с наградой в категории MD5-хэши.
3. Использование технологий обычных вычислений на графических видеокартах (GPGPU) пока еще может вызвать затруднения как у разработчиков, так и у пользователей. Для разработчиков отмечу непривычную архитектуру высокопараллельных вычислений и трудность отладки (что приводит к ошибкам, как в утилите LHC). Для пользователей - это сложность в запуске таких программ, требующих совместимых видеокарт, последних версий драйверов и некоторых дополнительных dll-библиотек, плюс, для достижения масчимальной скорости,  желательны дополнительные настройки под конкретную видеокарту.

Дополнительные ссылки:

1. NVIDIA CUDA — неграфические вычисления на графических процессорах
2. Тестирование скорости работы MD5-взломщиков от автора BarsWF

]]> http://www.password-crackers.ru/blog/?feed=rss2&p=27 http://www.password-crackers.ru/blog/?p=15 http://www.password-crackers.ru/blog/?p=15#comments Tue, 17 Feb 2009 21:12:53 +0000 Pavel Semjanov http://www.password-crackers.ru/blog/?p=15 В заключении своей статьи “Почему криптосистемы ненадежны”, написанной в 1998 году, я указывал, что положение с применением сильной криптографии в приложениях начинает меняться в лучшую сторону. Рассмотрим эволюцию использования криптографических средств на примере одного из самых популярных приложений для персональных компьютеров  - офисного пакета MS Office, тем более, что недавно Microsoft официально открыла спецификации этого пакета, включая используемые алгоритмы шифрования. Ниже я буду говорить только о паролях на открытие файла, т.к. при установке остальных паролей (на доступ по чтению и т.д.) сам текст документа не зашифровывается и они поэтому могут быть легко обойдены.

Первым шифрованием, применяемым в MS Office до версии 6.0 включительно, было ни что иное, как обычный XOR. Понятно, что такой простейший алгоритм шифрования не обеспечивает никакой защиты (и теперь стыдливо называется в спецификации словом “запутывание” (“obfuscation”)), и любые пароли восстанавливались мгновенно. Такое запутывание не запутало специалистов по криптографии, и соответствующие программы по взлому MS Word и Excel появились очень быстро. Как отмечал один из их авторов Marc Thibault, “ложное чувство безопасности гораздо хуже, чем ее отсутствие” и просил фирму Microsoft улучшить защиту в Office.

Что и было сделано в следующих версиях MS Office - 97 и 2000. Там уже использовались проверенные и сильные криптографические алгоритмы MD5 и RC4, поэтому о мгновенном взломе любых паролей пришлось забыть (временно, как оказалось позже). Но тут в дело вступил иной фактор - так называемые “ограничения по экспорту сильной криптографии”, действовавшие в то время в США. Вообще говоря,  разумное зерно в ограничении доступа к современным криптографическим алгоритмам нежелательным лицам, бесспорно, есть. Иное дело, что таким способом этот доступ террористам и иже с ними не ограничить - например, исходные тексты программы PGP, которые нельзя было вывозить из США в электронном виде, были вывезены в виде бумажной распечатки в соответствии с первой поправкой к конституции, затем отсканированы и переведены обратно в электронную форму.

Так вот, экспортные ограничение предписывали не иметь в программах, использующихся за пределами США, криптоалгоритмы с ключом более 40 бит. Это привело к тому, что ключи в алгоритме RC4, которые в MS Office 97/2000 потенциально могли быть до 128 бит, искусственно сокращались до 40. Т.е. из 16 байт, полученных на выходе Md5, 11 байт просто затирались нулями, и из 5 значащих байт и 11 нулей формировался уже сам ключ RC4.

Это привело к возможности атаки полным перебором на все возможные ключи. Для того, чтобы расшифровать файл Word/Excel 97/2000, необходимо перебрать максимум 2⁴⁰ ключей, после чего мы с гарантией найдем нужный ключ, независимо от длины и сложности используемого пароля. (Если вам непонятно отличие ключа от пароля - почитайте FAQ). Я  тоже занимался написанием такой программы в 2000 году, и после всех оптимизаций (причем одной из самых существенных была замена инструкции mov eax, 0 на xor eax, eax - я этого еще коснусь в этом блоге) на тогдашнем Pentium II/333 Мгц она должна была считаться около 70 дней. Сегодня перебор 2⁴⁰ ключей из Microsoft Office занимает 3 дня на двуядерном Core 2 Duo/2 ГГц.

Создатели программ для восстановления паролей Office 97/2000 на этом не остановились. Дело в том, что если создать огромную базу данных предвычисленных значений и применить т.н. Rainbow-атаку, то нужный ключ можно найти за секунды. По сути, мы заменяем сложные и долгие вычисления поиском в заранее вычисленной таблице (в оптимизации это называется “замена время-память”). Чем больше таблица, тем с большей вероятностью мы найдем там ключ. Обычно эта вероятность составляет более 99%. Первым, насколько я помню, появился онлайн-сервис Decryptum, предлагавший мгновенную расшифровку файлов Office 97/2000. Затем появились другие сервисы и программы, которые можно найти здесь.

В Office XP/2003 эволюция шифрования продолжилась. К тому времени экспортные ограничения была отменены, а Microsoft разработала свой CryptoAPI, который и не преминула использовать в новой версии Office. Но, по не очень понятной причине, в качестве шифрования по умолчанию был оставлен все тот же алгоритм с 40-битными ключами, рассмотренный выше. Это означает, что для многих файлов, созданных в Office XP/2003, также возможна гарантированная расшифровка. Что касается нового шифрования через CryptoAPI, то были сделаны следующие изменения:

• вместо алгоритма хэширования MD5 используется SHA1;
• ключи в алгоритме RC4 теперь могут быть до 128 бит;
• длина пароля увеличена с 16 до 255 символов.

В остальном же схема шифрования достаточно стандартна - из пароля с помощью хеширования получается ключ, на этом ключе шифруется документ. Таким образом, говорить о гарантированной расшифровке файлов Office XP/2003 уже не приходится - это невозможно для ключей более 64 бит для пользователя или небольшой организации, имеющей несколько сотен компьютеров. К десятой версии MS Office шифрование наконец стало достаточно адекватным.

Иное дело, что используемая схема шифрования и проверки пароля допускает достаточно высокую скорость перебора - до 1.000.000 паролей в секунду на одном ядре (столько показывает самая быстрая известная мне программа по восстановлению паролей MS Office XP/2003 - Parallel Password Recovery (Office module)), что означает, что на современном четырехъядерном компьютере можно перебрать все пароли из латинских букв и цифр вплоть до 8 символов за неделю!

Именно с большой скоростью перебора была призвана бороться новая схема шифрования, используемая в последней версии Office - 2007.  В ней было сделано три принципиальных отличия от предыдущей версии:

• вместо хорошего, но неоднократно неправильно примененного (в том числе в самом Office) потокового алгоритма RC4 используется стандарт шифрования AES
• вместо однократного хэширования пароля, результат хешируется циклически еще 50.000 раз
• возможно применение сторонних алгоритмов шифрования.

В результате скорость перебора паролей в Office 2007 упала с одного миллиона до 200 паролей в секунду (в 50.000 раз, что логично, потому что именно этот цикл хэширования и является самым “тактопожирающим”), и за разумное время теперь можно подобрать пароли не длинее 5-6 симоволов.

Таким образом, применяемая схема шифрования в последней версии Microsoft Office 2007 не имеет известных уязвимостей, не допускает никаких атак, кроме перебора паролей, а скорость этого перебора значительно ограничена…

… была до недавнего времени, пока не появились возможности перебора паролей на современных графических картах (GPU), в особенности технология CUDA от NVidia. Но об этом в следующий раз.

Дополнительные ссылки:

• FAQ по парольной защите MS Office
• Информация из первых рук о шифровании в Microsoft Office (англ.)