gat3way's place on the net

In the news...

03/29/12

GPU vs FPGA, маркетинг и митове :)

Posted by: gat3way in fun

Преди не повече от седмица ми попадна следното забавно четиво на някакъв сайт посветен на embedded системите за военни цели:

http://mil-embedded.com/articles/accelerating-cryptography-fpga-clusters/

Става въпрос за рекламна статия, посветена на невероятните възможности на FPGA клъстерите за трошене на пароли. Статията е писана съвместно от директора на маркетинга и директора на отдел "Security applications" в Pico Computing - компания от Сиатъл, специализирана в предоставянето на разни FPGA решения. Та в статията пише как GPU-базираните решения за трошене на пароли не са добре оптимизирани за решаването на такива проблеми и се изтъква цената им и съотношението performance/Watt. Като пример бяха дали FileVault и WEP. Сега, WEP е ирелевантен пример, защото има далеч по-ефективни криптографски атаки спрямо простата bruteforce атака на ключа, но FileVault специално е интересна работа.

Понеже ми стана много забавно и понеже бях попрочел тук-таме, реших да я видя тази работа. За който не знае, FileVault е решение за криптиране на файлови системи в MacOSX (всъщност на директории, но полученият image се монтира като файлова система при положение че се зададе коректния passphrase). За криптографията зад това бях чел преди известно време и реших че е нещо, което лесно може да се троши върху GPU-та.

Та каква е криптографията зад FileVault? В общи линии когато искаме да отключим FileVault image (DMG файл), имаме два варианта - по-стария ползва хедър версия 1, по-новия ползва версия 2. Старият не е толкова интересен, да видим какво става в по-новата разновидност:

Потребителят задава passphrase
passphrase-а минава през 1000 итерации на PBKDF2-SHA1. За IV се ползва една стойност от хедъра. Резултатът е 192-битов ключ (което е повече от 160-битовия изход на SHA1 функцията, ерго в крайна сметка това са 2*(1000*2) + 2 = 4002 SHA1 блокови операции. Това е изчислително интензивната част на FileVault, начина по който от Apple са решили да отблъскват bruteforce атаките
Полученият 192-битов ключ се използва за 3DES-EDE-CBC декриптиране на 48 (или 64) байта wrapped key. Това става ползвайки една леко извратена форма на PKCS#5 padding/wrapping (почти съвместима с OpenSSL-ската реализация, ама не точно). От резултатa от декриптирането вземаме HMAC-SHA1 ключ и AES ключ (128 или 256-битов)
Правим HMAC-SHA1 с неговия си ключ върху 4-байтова стойност, номер на пореден криптиран 4096-байтов блок (при чупенето, тази стойност е винаги 0).
Резултатът ползваме като инициализационен вектор при AES-CBC декриптирането на въпросния блок. Поради специфичният хедър на първия блок, съдържащ определена сигнатура, можем да разберем правилна ли ни е била паролата.

Реших да реализирам единствено PBKDF2 частта върху GPU. Triple DES в CBC режим върху видеокарти е пипкава история, а AES декриптиране на 4096 байта данни е безсмислено начинание. А и благодарение на AES-NI инструкциите, последното става доста бързо върху процесори (всъщност, ние не декриптираме целия блок, а само първите 32 байта, така че това не е никакъв проблем да се прави върху CPU-та).

Обаче не бях сигурен за разни дребни детайли около цялата работа. Има един проект, vilefault, чиято цел е да троши FileVault пароли върху CPU-та. Реших да си сверя часовника с него...оооо, изненада обаче. Оказа се че последният не работи въобще коректно. Оказа се че C структурата им описваща хедъра е с грешен padding, та загубих 1-2 дни в ровене върху един примерен криптиран DMG image с hex редактор, докато си обясня какво става. Също така, сигнатурата на декриптирания хедър, която ползват е некоректна. Всичко останало им е ОК, което е много странно - това са хората, които са reverse-engineer-нали FileVault и при все това дори PoC кода им не работи заради дребни на пръв поглед неща. Надушвам конспирация :)

Както и да е, след няколко дена имах работеща CPU имплементация. Скоростта беше около 700 c/s върху 6-ядрен Bulldozer на 3.3 гигахерца. Бавно :)

OpenCL kernel-а го написах за една вечер. Първоначално предвиждах скорост от около 50 хиляди c/s върху AMD Radeon HD6870, после коригирах очакванията на около 200 хиляди....и крайният резултат след известни оптимизации беше 218 хиляди опита/секунда. Това е скорост която позволява освен речниковите атаки и доста експерименти с правила или марковски вериги :)

Да се върнем на рекламната статия. Там обясняваха колко велико нещо е техния Pico SC-5 FPGA клъстер от 72 Spartan-6 модула, консумиращ общо 1400 вата енергия, на неизвестна цена. Статията е от средата на 2010 година, когато на пазара вече ги имаше от половин година AMD Radeon HD5970 чудовищата на цена от около $900 (по спомени). Понеже архитектурите на 5970 и на 6870 са сходни (VLIW5), човек може да си направи лесни сметки вземайки предвид единствено брой шейдъри и тактова честота. Две 5970-ци консумират при натоварване около 600 вата и производителността им би била малко над 1 милион опита в секунда, далеч повече от FPGA клъстера, който прави около 700 хиляди. За цената на Pico SC-5 не знам, но като гледам, цената на един Spartan 6 модул с 15 хиляди logic cells е най-малко $54. 72 такива модула биха стрували около $3900, като много вероятно там са ползвали по-мощни модули, цените са били по-високи преди 2 години и отделно интеграцията им в клъстера струва пари. Да не говорим колко пари ще излезе някой да разпише качествен код.

Толкова за маркетинговите глупости. Но пък на сайт посветен на военни embedded джаджи сигурно такива гръмко звучащи изявления хващат око ехех.

Като цяло не бих се изказвал толкова смело иначе. FPGA решенията наистина са далеч по-скалируеми, по-енергийно ефективни....само че и далеч по-скъпи и доста по-сложни за програмиране. Доста по-капризни също така. В общият случай, мисля че GPU-базираното password recovery ще си остане най-мощният и достъпен вариант за обикновени простосмъртни, както и за средно-големи организации. Трибуквените агенции иначе така или иначе имат ресурса да си дизайнват собствени специализирани ASIC чипове и да плащат за да им ги произвеждат в големи количества, така че тях няма какво да ги мислим :)

Та горд съм от себе си. hashkill ще е първият GPU password recovery tool, който подържа FileVault апропо. Opensource разбира се и само под линукс :)

Таааа..дам, редовните screenshots...това е от AMD Radeon 6870:

Това е от NVidia GT430 (ruledict правилата са леко relax-нати, не ми се чакаше минути за screenshot-а):

Та такива забавни работи.

А, да, мисля да изоставя усилията по 7Zip засега. Вместо това ще се съсредоточа върху SHA512(Unix) системните пароли. Срамота е че не ги чупя върху видеокарти...

Comments:

April 1, 2012, 10:50 am - darkmaster
Здравей пиши на хората които разработват Back Track да добавят hashkill във следващата версия на Back Track .
http://www.backtrack-linux.org/about/
April 1, 2012, 4:42 pm - gat3way
С единия от хората които се занимават с BT киснем в един и същ IRC канал. Както и да е, не виждам особен смисъл да влиза там. Иначе засега е в AUR репото на archlinux, има ebuild за gentoo в gentoo-portage, съответно в sourcemage и pentoo както и едни хора се опитваха да го портват за FreeBSD (нямам идея колко успешно е последното). За debian или fedora предвид малоумните ми билд скриптове и няколкото любопитни момента с лиценза на нещата, които ползвам (catalyst драйвера примерно), както и повишените изисквания въобще...не знам, не вярвам скоро да стане. Но може би с предстоящата версия има повече шансове знам ли :)
За BT не знам. Пълния build на hashkill в момента е около 200-250 мегабайта. Това е доста за live дистрибуция...
April 11, 2012, 7:57 pm - darkmaster
1Качи програта тук http://www.softpedia.com/
2 Нямам търпение за новата версия съжалявам ако ставам нахален .
3 Надявам се в бъдеще програмата да може да краква True Crypt пароли .Поздрави и продължавай страхотната работа по проекта .
April 12, 2012, 11:28 pm - gat3way
1) Тя не е готова, пък да я качвам :)
Иначе се замислям за бета версии, ако някой изяви желание, няма проблеми да му билдна бета.
2) Не само ти нямаш търпение, и аз нямам търпение :) Остават малко от планираните неща (7zip отпада засега, за сметка на някои други неща). Поради ред причини няма да стане много скоро - просто още не е завършена във вида в който я искам.
3) TrueCrypt е планиран, но не за тази версия. Има известна вероятност да влезе в следващата, но мисля там акцентът да е върху документните формати (msoffice, ooffice, pdf). Може да звучи странно, но truecrypt не е толкова сложно нещо за трошене, скоростта няма да е особено очарователна (демек прости/речникови пароли вероятно ще паднат, сложни - след второто пришествие със сегашния хардуер).
April 17, 2012, 5:30 pm - Радослав
Здравей. Не знам дали мога да те попитам тук, но наред с тези постове би било интересно / а и достатъчно трудно предполагам /, да напишеш един пост със съвети как да си криптираме машините, в това число и виртуални такива, без да могат да бъдат разбити.
Интересно е как есента ще има Windows 8 Pro / анонса е от днес /, като един от "плюсовете" му ще е Bitlocker, и как сега при първото търсене веднага попаднах на това:
http://www.lostpassword.com/kit-forensic.htm
Та наистина би било полезно, ако споделиш мнение за windows потребители, как да защитят информацията си в случай на кражба на лаптоп примерно информацията да си остане все така защитена.
April 19, 2012, 1:08 am - gat3way
Bitlocker не съществува ли отпреди осмицата, да речем 7 или дори във Виста или бъркам?
На Passware шапка им свалям за много неща, технически и не толкова технически, но наистина атаката срещу bitlocker е доста...как да кажа изчислително-интензивна и при това положение вероятно overkill. Bitlocker има други проблеми, това е малко не знам...хабене на време.
Ако аз ползвах windows и исках силно криптиране, вероятно щях да ползвам TrueCrypt с достатъчно дълга и сложна парола. Защо - много дълга тема, а и това си е лично мое мнение.
Да, сигурно трябва да напиша нещо по въпроса, но имам доста неща на главата в момента. Ще ми се да можех да обяснявам нещата като хората и да имах време да го правя :)
May 6, 2012, 1:41 pm - Тодор Донев
Yo mates ! =))
Та отностно hashkill, преди малко го инсталирах с леко досадни забележки отностно инсталацията, но поносими.Тествах hashkill -phashunix -b и държеше скорост 7-8К която скорост, реално за нисък клас карта е сравнително добре, макар че при натискане на
бутона Enter правопорпорционално качваше температурата с по 1 градус. Та прав си за големината, лично аз си реших проблема, като инсталирах Ultimate Packer for eXecutables. Пакетирах hashkill-a и малко по-надолу ще видите резултатите.
Обаче след като пакетирах hashkill-a освен, че ми вдигна скороста с още 1K което си е нищо (все пак говорим за nVIDIA GEFORCE 8400GS, за преносим компютър), градусите спряха да се вдигат толкова бързо.
За целта аз използвах upx със следните опции:
# ./upx -9 -k hashkill
Ultimate Packer for eXecutables
Copyright (C) 1996 - 2011
UPX 3.08 Markus Oberhumer, Laszlo Molnar & John Reiser Dec 12th 2011
File size Ratio Format Name
-------------------- ------ ----------- -----------
2313250 -> 676756 29.26% linux/elf386 hashkill
Packed 1 file.
Реших да пиша, предварително и най-вероятно ще пробвам да го пакетирам с други апликации. Надявам се тази идея да ти помогне за напред. Пробвай сигурен съм, че ще има резултат и при теб.
Поздрави на всички,
Донев (UAnet)
May 6, 2012, 7:38 pm - Тодор Донев
gat3way ти май се обърка за големината на hashkill? Я виж хубаво колко MB е. =))
May 6, 2012, 10:45 pm - gat3way
Привет Тодоре,
Това което тестваш е версия 0.2.4. Там няма GPU подръжка за hashunix, т.е скоростта която наблюдаваш е върху процесора.
Версия 0.3.0 още не е release-ната и тя наистина е далеч по-голяма (заради прекомпилираните GPU kernel-и за всички възможни архитектури на AMD и NVidia). Та там въпросният плъгин вече е разбит на две - md5unix и sha512unix, и двете реализирани върху GPU. Поради ред причини нямам желание да ползвам публична version control система, а до release-а официално има време. Но ако имаш желание, мога да ти билдна бета версия за тестване.
May 7, 2012, 8:47 am - Тодор Донев
Здравей gat3way и добро утро! =))
# time hashkill -pmd5 -b df5ea29924d39c3be8785734f13169c6
[hashkill] Version 0.2.4
[hashkill] Plugin 'md5' loaded successfully
[hashkill] Using 1:8:lalpha defaults. Use -b<params> (no whitespaces) to specify them
[hashkill] Total physical memory : 3924 MB
[hashkill] Detected 2 CPUs.
[hashkill] Threads queue size: 128 plaintexts/thread
[hashkill] Initialized thread mutexes
[hashkill] Initialized hash bitmaps
[hashkill] SSE2 accelerated routines available
[hashkill] Attack has linear complexity
[hashkill] Single hash - skipping bitmap checks
[hashkill] Spawned worker threads
[hashkill] Bruteforce charset: abcdefghijklmnopqrstuvwxyz0123456789
[hashkill] Launching bruteforce attack
Attack statistics...
Progress: 0% Speed: 22519 KPlaintexts/sec Cracked: 1 hashes
[hashkill] Bruteforce attack complete.
[hashkill] -= Cracked list =-
Username: Hash: Preimage:
-----------------------------------------------------------------------------------
N/A df5ea29924d39c3be8785734f13169c6 blabla
[hashkill] Total: 1 hashes cracked
[hashkill] Attack took 9 seconds.
[hashkill] Bye bye :)
real 0m9.312s
user 0m13.554s
sys 0m0.218s
Това е със md5 на 0.2.4 и нарочно го пуснах със time, защото мислех че има грешка във времето. И все пак всичко е точно, радвам се поне че ми каза за hashunix-a защото твърдо бях убеден, че го чупи през картата. Все пак не следя развитието на hashkill от близо. Радвам се, че дори и за CPU пак си по-бърз от Solar Designer-a и неговия John Ther Ripper. =)) Вероятно Румънците ще започнат да правят Drone Scanner-ите си с hashkill вместо с вграден john. Не се занимавай да ми билдваш пакет, целта беше да ти помогна с идея, така или иначе го направих. С полубайтово пакетиране може и да свалиш малко големината на файловете и библиотеките, които ползва hashkill. Лично аз натъпках моя пакет на hashkill, като за lib-овете ползвах gzip-a, а за самият elf binary exec, ползвах upx както видя в по-горния коментар. С нетърпение чакам, да видя какво ще извадиш от торбичката с подаръци. Дай някакви координати къде да те търся евентуално. Надявам се и да е през IRC, защото не съм много голям фен на Skype, ICQ, Facebook, Twitter и etc.. =)) Поздрави и много успехи.
May 7, 2012, 11:08 pm - gat3way
Привет,
Според изхода от програмата, GPU-то не се ползва, което е странно. Каква е картата?
Що се отнася до компресията, за момента ползвам lzma компресия на kernel-ите. От 2 гигабайта стават малко повече от 200 мегабайта, което пак е много, но трудно може да се постигне повече (особено с ELF бинарен код какъвто генерира OpenCL компилатора).
IRC ползвам иначе...на rizon.net. Мотая се предимно из #hashcat.
May 7, 2012, 11:25 pm - Тодор Донев
Ха здравейте отново!
Та да вземеш да си видиш емейла има бъгове по hashkill. Kартата е NVIDIA GEFORCE 8400М GS и как да се ползва като то GPU няма. =)) CUDA Cores: 16 VBIOS Version: 60.86.45.00.40 Memory: 256MB Memory Interface: 64b GPU: 0
May 8, 2012, 12:26 pm - gat3way
Тази карта би трябвало да подържа OpenCL, което е странното. Да не би да ползваш билд без OpenCL (това е configure-time опция)?
May 12, 2012, 10:11 am - Тодор Донев
Здравей gat3way!
Билд на hashkill? В интерес на истината не съм и поглеждал. Това със GPU беше тъпа шега. =)) Нямам възможност да се занимая повечко. Ще чакам 0.3.0(Защо такава дълга версия си избрал?) и до тогава ако ми остане някакво време, ще разгледам hashkill и вероятно може да напиша някаква документация за него кои неща примерно не ми харесват(като това с pipe), дупки и прочие.. искам да го видя на mpi дали ще сработи и какво ще направи от към грешки.
Засега толкова, ако имаш въпроси ми имаш емейла.

Add A Comment

^ Top

Next page: Web application security

Code in the picture:
Your Name(*):
Comment(*):

gat3way's place on the net

Navigation

In the news...

GPU vs FPGA, маркетинг и митове :)

Comments:

Add A Comment