GPU изчисления напоследък стана много популярен във всички региони, където е възможно, за да ги използвате. Една такава област е криптография, по-тясно - подбор / сортиране на пароли. За съжаление, реалните резултати от работата (както става обикновено) украсявам маркетингови цели, така че да не е много ясно кой всъщност се възползват от използването на графичния процесор в областта.
Дълги кратки крайни обяснение терминали (което вероятно си струва и да четат, когато четете първата от статията).
По това време, прекарано с груба сила.
Ако преди десет години, всеки разработчик се опитва да излезе с някакъв, оригиналният алгоритъм за криптиране (но, тъй като почти никой не е експерт в областта на криптографията, по-голямата част от тези "оригинални" алгоритми бяха разделени в момента), но сега това е станал много по-лесно , Почти всички тествани използвайки стандартна схема.
За криптиране, първо трябва да се превърне в ключов паролата определен тип и размер (стъпка хеширане), а след това с помощта на този ключ за криптиране на действителните данни (с помощта на който и да е надежден алгоритъм като AES).
За да хеш MD5 доскоро се използва в големи количества, но (след откриването на уязвимост в алгоритъма) то доста бързо заменя SHA1. С SHA1 в момента не е съвсем става плавно (сложността на намирането на сблъсък е около 2 ^ 63, а в последно време все повече и обяви намаляване на броя до 2 ^ 52), но когато той се използва в някои "рамка" като PBKDF2 сложност (или по-скоро, лекота) място на сблъсък не е толкова важно.
В PDF9 Adobe много пропуснати с нов алгоритъм, като едно повторение на SHA256 вместо 50 MD5 + 20x RC4, което ускорява скоростта на груба сила, в сравнение с предишната версия е почти два порядъка. Но след хеширане валидирането на паролата не изисква криптиране, така че има само важно скорост SHA256.
Правилното алгоритъм за криптиране прави невъзможно груба сила намаляването на мястото за ключове. Това е да се намери, например, 128-битов ключ е необходимо да се мине през 2 ^ 128 == 3.4 * 10 ^ 38 опции. Ако приемем, че един компютър минава през един милиард възможности в секунда, ние имаме един милиард компютри, а ние имаме един милиард години, като през това време ние ще бъдем в състояние да провери само 10 * 9 * 10 * 9 * 10 * 9 * 60 * 60 m * 24 часа * 365.25 г
= 3,16 * 10 ^ 34 изпълнения желания обхват по-малко от 1/10000.
Например неуспешен опит криптиращи алгоритми: с помощта на 96-битови ключове са класически цип. Въпреки миналото повече от 20 години от създаването на алгоритъма, тези ключове все още е невъзможно да се оправи "на челото." Въпреки това, като част от нешифрован файл, можете да извърши т.нар прав текст атаката, докато сложността на груба сила ще падне до 2 ^ 96 само 2 ^ 38, което е само на няколко часа за съвременния компютър.
Всички "силни" алгоритми за криптиране (AES, Blowfish, и т.н.) не позволяват прав текст атака и не позволяват да се намали търсенето пространство. Така че единственият начин да получат достъп до криптирани файлове - да се знае правилната парола.
Заключение: алгоритъм за шифроване, използван от почти никакъв ефект върху скоростта на груба сила. Добър алгоритъм просто прави невъзможно клавиш за избор "на челото." И сега най-важното е да превъртите чрез превръщането на пароли е парола в ключов, и тя е отговорна за хеширане алгоритми (MD5, SHA1), а не алгоритми за криптиране (AES, Blowfish).
Стойността на "брой повторения", казва малко.
MD5, SHA1 (и неговите потомци като SHA256, 384, 512) са много сходни. На входа има състояние хеш (128 бита за MD5, 160 бита в SHA1) и размера на блока данни на 512 бита (64 байта). На изхода, след хеширане операции, ще получим едно ново състояние на хеша. Това е сърцето на алгоритъм, функцията обикновено се нарича MD5_Transform, SHA1_Transform и т.н.
Важно е да се отбележи, че размера на блока е константа, винаги хешираното точно 64 байта. Ако се подава към входа на един байт, ще бъдат допълнени до 64 чрез прибавяне на нули терминатор символ и 8-байтов стойност на дължина на блок. Това означава, че от тях поотделно вход хеш функция 64 × 1 байт или веднъж на всеки 64 байта - абсолютно идентични с равнината на скоростта на обработка (без да броим факта, че при прилагането на 64 байта ще символ терминатор и процес на стойност дължина вече през следващата блок) ,
За някои алгоритми, написани на броя на повторенията, тъй като броят на функция призовава за актуализиране на хеш. Но не всяка актуализация води до наричаме трансформация функция. Събраните данни в буфера и се прехвърлят на трансформация блокове от 64 байта. Например за RAR 3.x брой повторения, равни на 262 144, но броят на обработените блокове, се равнява на повече ((dlina_parolya * 2 + 8 + 3) * 262 144) / 64. С, например пароли в 4 дължина характер ще бъдат 77 824 (+ 17 допълнителни блокове за създаване на IV за AES).
Какво означава достигане на броя повторения на броя на блоковете да се превърне? Тъй като времето за хеш изчисление е независима от данните в блока е постоянен, като знаете времето на хеширане един блок и на броя на дяловете може лесно да се изчисли общото време хеширане. Също така е лесно да се прецени колко по-бързо или по-бавно различни алгоритми поколение парола една спрямо друга.
Например, въз основа на изчисления по-горе става ясно, че скоростта WinZip / AES груба сила в
Заключение: Броят на "виртуални" повторения в алгоритъма не означава много. За да изчислите скоростта трябва да знае броя на 64-байтови блокове, използвани в хеширане. Знаейки тази стойност, като цяло скоростта на обработка се получават лесно, просто, като се умножи тази стойност от обработката на информационния блок.
Колко бързо мога да хеширате?
Сега ние се интересуваме от въпроса за това, колко бързо може да обработва 64-байт блок от данни. Операции ispolzueschiesya трансформация функция в най-прост - логично OR, XOR, не, както и, аритметични добавяне на смени. Всички действия се извършват на 32-битово цяло число. Един блок от данни лесно се побира в нито една от L1 кеша на съвременните процесори, така че скоростта на паметта, неговия размер, размера на L2 или RPM твърд диск не играе никаква роля. С други думи, скоростта на търсене е пряка функция на число ALU скорост и практически не зависи от останалите. В някои от съвременните процесори с най-добрите?
Процесори.
От хеширане различни пароли не могат да зависят един от друг, е много изгодно да се използват някои SIMD набор инструкции за паралелна обработка на информацията. Най-добър SSE2 (въпреки че "старата» MMX все още има употреба) ви позволява да извършвате операция веднага с четири 32-битови операнди. В първия вариант, Pentium 4 със скоростта на SSE2 инструкция не става плавно (например пратка registr-> цена регистър 6 цикъла, както и изпълнението на всички или 2), но дори и тогава печалбата на тяхното приложение е доста забележително. В същото време изпълнението SSE2 в архитектурата Intel Core е просто красива: тя е възможно да се извърши на 3 операции на часовника, като в резултат ще бъде готов за следващия цикъл (латентност == 1 бар). Това означава, че пиковата производителност на ядро от 12 операции, с 32-битово цяло число в рамките на цикъла. Въпреки че не всички операции могат да се извършват на този връх процент.
Въпреки появата на нова основна ревизия, на прехода от 65nm до 45nm, и най-накрая се освободи Core i7, никакви съществени промени в цяло число ALU случили. Затова Core i7 работи почти както и неговото предшественик 65nm ядро 2. Капацитетът зависи само от честотата, така например, Q6600 с тактова честота до 3 GHz (което е доста често срещана практика) е точно 3 / 2.66 = 12.7% по-бързо от Core i7 920 на номиналната честота (с изключение на турбо разрушаване). Цената на Core i7, включително дънната платка и DDR3 памет е значително по-висока, отколкото в "старите" Core 2 системи 65 / 45nm.
Ситуацията е малко по-лоши с AMD. Дори и сега, все още има доста системи с Athlon XP процесор. По това време той е много добре да се конкурира с P4, но тя не трябва SSE2. Архитектурата на K8 реализирал е подкрепа за SSE2, но в най-примитивната форма: 128-битови инструкции са разделени на две половини и се провежда на 64-битов ALU. Какво доведе до факта, че разликата между MMX и SSE2 код почти не беше.
С появата на K10 (или Phenom) AMD най-накрая направи SSE2 подкрепят по достоен начин, но Core 2 е значително по-ниско. K10 може да извършва до 2 операции с 4 х 32-битови цели числа на цикъл и експлоатация резултат ще бъде готов само след цикъл (латентност == 2 цикъла). Това е, изпълнението на връх е 8 операции с 32-битово цяло число в рамките на цикъла. Какво означава това от гледна точка на сравнения K10 срещу Core 2: Процесорът AMD е средно 1,5 пъти по-бавно, ако ние можем да изградим инструкции, така че забавянето не е ограничаващ фактор. В някои алгоритми, като се има предвид ограничения брой XMM регистри, което го прави много трудно, ако не и невъзможно.
От друга страна, не всички операции Core 2 могат да изпълняват на ниво "три на такт. Допълнения могат да се правят само две, и промените в общата такава. K10 е в състояние да се движат два XMM регистри на часовник, но с латентност на 3 цикъла. Поради това, действителното съотношение на производителност Core 2 срещу K10 плава някъде в 1.25-2x област. K10 винаги е по-бавен от задачи, които зависят само от скоростта на SSE2 ALU, но може да бъде по-бързо на алгоритми с различни от показанията на паметта, както и липсата на логически операции.
Phenom II, който не се появи толкова отдавна, просто различен от Phenom # 'и далеч по-малко в сравнение с Core i7 от Core 2 45nm. Но това е необходимо, разбира се, по-скъпи.
Важно е да се отбележи, че по това време на използването на SSE2 е задължително за паралелна обработка на информацията. Логическата операция на регистър на 32-битова или над 128-битово XMM регистър, който съдържа четири 32-битови стойности, се извършва в продължение на точно по същото време. Изчислено на Core 2 без SSE2 е искал да вземе на графичния процесор и изключване на него ¾ от всички поточни процесора.
Също така, задачата за възстановяване на паролата перфектно паралелизирано, тъй като няма връзка между данните. Поради това, производителността расте линейно с честотата и броя на ядрата. Няма никакъв смисъл да се използва "бързо" dvuhyadernik, ако това е възможно да се използва "бавен" chetyrohyadernik. С други думи, Q6600 на 2.4GHz честота ще работи като 4 * 2.4 = 9.6Ggts и E8600 3.33 GHz само 3,33 * 2 = 6.66Ggts. Разликата в скоростта е 1.5 пъти, а разликата в цената е почти същото, но в обратна посока.
Заключение: Най-добрият процесор за груба сила в момента е Intel Core Quad. От гледна точка на цена / производителност по-изгодно Core 2 65 / 45nm. системи на разходите за Core i7-горе, както и честотата не е по-добре от "старите» 2. ядрени процесори от AMD Значително по-назад по изчисления SSE2 число и по този начин разликата в цената между Core 2 и Phenom не компенсира това изоставане. SSE2 необходимо за консумация, или на възможностите на съвременните процесори просто не разкриват.
Така че в крайна сметка колко бързо можете да хеширате?
Много грубо, скоростта за броя на използваните функции може да се изчисли, както следва:
Разбира се такава оценка не се вземат предвид много различни фактори, но подходящ за бързо разбират колко бързо това е теоретично възможно да се извърши 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, които, от своя страна, помага за решаване на проблемите с латентност. Това е особено въздействие върху MD5, когато сделките са много малки, така че винаги трябва да се изчакат резултатите от предишни изчисления, ако процесът едва 4 блок данни в даден момент.
Теоретични и практически резултати.
И накрая, обобщена таблица в името на който всичко е започнало. Сравнение на цените за различните видове пароли. Те са били използвани:
Скорост се измерва при едно ядро Intel Core 2 Q6600 @ 2,4 GHz, ATI HD4850 на номиналната честота 625Mgts, NVIDIA GTX 260 / w 192SP също на номиналната честота 1.242Ggts.
Резултатът е списък с отправна точка на производителността до 4 ядра Q6600 на 2.4GHz честота:
Честота, брой ядра
Цената на процесора или GPU
Общата цена на системата
2x ATI HD4870X2
0.75 х 800 х 2 х 2
4x NVIDIA GTX295
1242 х 240 х 2 х 4
За системи с по-бавен GPU (като GT 8600) има смисъл да се помисли за изпълнение като CPU + GPU (което не е било направено от тук). За бърза същото GPU процесора ще бъдат натоварени с допълнителни изчисления и задачи синхронизация, така че да вземе по-нататък той просто няма смисъл. В някои случаи, четири-ядрени процесори, не може да бъде достатъчно, за системи с 8 GPU.
Както се вижда, най-интересното решение от гледна точка на цена / производителност е комбинация от 4-HD4770. За пореден път, обаче, тя изисква дънната платка, които могат да се настанят четирима такива карти - въпреки факта, че един чип карта за охлаждане на HD4770 заема допълнителен слот.
Имаше един "малък" проблем - почти пълната липса на софтуер за ATI карти. Картички от NVIDIA, подкрепени от Разпределени Recovery ElcomSoft # е парола, но с ATI, докато нещата наистина лоши.
Заключение: Увеличаването на ефективността от използването на един GPU приблизително 4-5 пъти в сравнение с модерна система четириядрен. ATI карти много по-бързо на същата цена, но да имат малък или никакъв софтуер. С нарастването на броя на GPU в нелинейни проблеми растат система - има нужда от висока мощност захранване, заградено, ефективна система за охлаждане и т.н.
И защо една толкова малка печалба?!
Заключение: то винаги е полезно да се мисли за себе си.
Кои пароли може да се счита, устойчиви?
Свързани статии