Всі методи злому MD5

Трохи про криптографії

Сучасна криптографія включає в себе три напрямки: шифрування із закритим ключем, шифрування з відкритим ключем і хешування. Сьогодні ми поговоримо про те, що таке змішування і з чим його їдять.

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

Одним з найбільш відомих і широко використовуваних алгоритмів хешування є MD5.

початок

Алгоритм MD5 є 128-бітний алгоритм хешування. Це означає, що він обчислює 128-бітний хеш для довільного набору даних, що надходять на його вхід. Цей алгоритм розробив професор Рональд Ривест з Массачусетського технологічного інституту в 1991 році для заміни менш надійного попередника - MD4. Алгоритм був вперше опублікований в квітні 1992 року в RFC 1321. Після цього MD5 став використовуватися для вирішення найрізноманітніших завдань, від хеширования паролів в CMS до створення електронно-цифрових підписів та SSL-сертифікатів.

Про те, що алгоритм MD5 можна зламати, вперше заговорили в 1993 році. Дослідники Берт ден Боєр і Антон Боссіларіс показали, що в алгоритмі можливі псевдоколлізіі. Через три роки, в 1996-му, Ганс Доббертін опублікував статтю, в якій довів наявність колізій і описав теоретичну можливість злому MD5. Це був ще не злом, але в світі почалися розмови про необхідність переходу на більш надійні алгоритми хешування, наприклад SHA1 (на момент написання цієї статті вже було доведено, що колізії є і в цьому алгоритмі, тому рекомендую використовувати SHA2) або RIPEMD-160.

перші атаки

Безпосередній злом MD5 почався 1 березня 2004 року. Компанія CertainKey Cryptosystems запустила проект MD5CRK - розподілену систему пошуку колізій. Метою проекту був пошук двох повідомлень з ідентичними хеш-кодами. Проект завершився 24 серпня 2004 року, коли чотири незалежних дослідника - Ван Сяоюн, Фен Денгуо, Лай Сюецзя і Юй Хунбо - виявили уразливість алгоритму, що дозволяє знайти колізії аналітичним методом за більш-менш прийнятний час. За допомогою цього методу можна всього лише за годину виявити колізії на кластері IBM p690 (шкода, що у мене немає такого будинку).

Першого березня 2005 року була продемонстровано перше використання зазначеної уразливості на практиці. Група дослідників представила два сертифікати X.509 з різними наборами ключів, але з ідентичними контрольними сумами. У тому ж році Властіміл Клима опублікував алгоритм, що дозволяє виявляти колізії на звичайному ноутбуці за кілька годин. У 2006 він пішов далі. Вісімнадцятого березня 2006 року дослідник оприлюднив алгоритм, що знаходить колізії за одну хвилину! Цей метод отримав назву «туннелирование». У 2008 році на конференції Chaos Communication Congress була представлена ​​стаття про метод генерації підроблених сертифікатів X.509. Фактично це був перший випадок реального використання колізій в алгоритмі MD5.

Велика робота була також проведена і для прискорення злому хешів. У 2007 році Кевін Бриз представив програму, яка використовує Sony PlayStation3 для злому MD5. Він зумів домогтися дуже непоганих результатів: 1,4 мільярда MD5-хеш-кодувань генерувалися всього лише за одну секунду! Уже через два роки, в 2009-му, на BlackHat USA вийшла стаття про використання GPU для пошуку колізій, що дозволяло підвищити його швидкість в кілька разів, особливо якщо він виконувався за допомогою декількох відеокарт одночасно.

Відеокарта ATI Radeon HD 4850 X2 дозволяє генерувати до 2,2 мільярда хешів в секунду! Використання алгоритму MD5 в ЕЦП неприйнятно внаслідок недостатньої стійкості цього алгоритму до пошуку колізій.

Це кінець?

У 2011 році IETF погодився внести зміни в RFC 1321 (MD5) і RFC 2104 (HMAC-MD5). Так з'явився документ RFC 6151. Він визнає алгоритм шифрування MD5 небезпечним і рекомендує відмовитися від його використання. На мій погляд, цей документ офіційно поклав край MD5.

Однак, незважаючи на те що алгоритм MD5 був офіційно визнаний небезпечним, існують тисячі, якщо не десятки і сотні тисяч додатків, які використовують його для зберігання паролів, в електронно-цифрових підписах і для обчислення контрольних сум файлів.

До речі, 31 жовтня 2008 року NIST оголосила конкурс серед криптографов. Мета конкурсу - розробити алгоритм хешування на заміну застарілим SHA1 і SHA2. На даний момент фіналісти вже визначені - це BLAKE, Gostl, JH, Keccak і Skein.

Ighashgpu: злом за допомогою GPU

Але вистачить теорії. Давай перейдемо до справи і поговоримо безпосередньо про злом нашого улюбленого алгоритму. Припустимо, що нам в руки потрапив хеш якогось пароля: d8578edf8458ce06fbc5bb76a58c5ca4.

Для злому цього хешу я пропоную скористатися програмою Ighashgpu, яку можна завантажити на сайтеwww.golubev.com або знайти на нашому диску. Утиліта поширюється абсолютно безкоштовно і спокійно працює під виндой. Щоб прискорити процес злому хешу, Ighashgpu використовує GPU, тому тобі необхідна як мінімум одна відеокарта nVidia або ATI c підтримкою CUDA / ATI Stream.

Сучасні графічні процесори побудовані на дещо інший архітектурі, ніж звичайні CPU, тому вони набагато ефективніше обробляють графічну інформацію. Хоча GPU призначені для обробки тривимірної графіки, в останні кілька років з'явилася тенденція до їх застосування та для звичайних обчислень. Почати працювати з програмою не просто, а дуже просто: розпакуйте архів в будь-яке місце на диску і приступай до злому за допомогою командного рядка Windows:

ighashgpu.exe -t:md5 \
-h:d8578edf8458ce06fbc5bb76a58c5ca4 -max:7

Ми використовуємо вищенаведений спосіб для злому одного певного хешу, згенерованого за допомогою алгоритму MD5. Максимальна довжина можливого пароля становить сім символів. Через якийсь час пароль буде знайдений (qwerty). Тепер давай спробуємо зламати ще один хеш, але з трохи іншими умовами. Нехай наш хеш має вигляд d11fd4559815b2c3de1b685bb78a6283, а включає в себе літери, цифри, знак підкреслення і має суфікс «_admin». В даному випадку ми можемо використовувати перебір пароля по масці, щоб спростити програму завдання:

ighashgpu.exe -h:d11fd4559815b2c3de1b685bb78a6283 -t:md5
-u:[abcdefghijklmnopqrstuwvxyz1234567890_] -m:??????_admin

Тут параметр '-u' дозволяє вказати набір символів, які використовуються при переборі, а параметр '-m' задає маску пароля. У нашому випадку маска складається з шести довільних символів, після яких йде поєднання «_admin». Підбір пароля також не складе ніяких труднощів.

Колізії - колізією в криптографії називають два різних вхідних блоку даних, які для однієї і тієї ж хеш-функції дають один і той же хеш. Кожна функція на виході дає послідовність бітів певної довжини, яка не залежить від розміру початкових даних. Звідси випливає, що колізії існують для будь-якого алгоритму хешування. Однак імовірність того, що ти зможеш знайти колізію в «хорошому» алгоритмі, практично наближається до нуля. На жаль чи на щастя, алгоритми хешування можуть містити помилки, як і будь-які програми. Багато хеш-функції або вже були зламані, або скоро будуть. В даному випадку «зламати» - значить знайти колізію за час, який багато менші, ніж заявлена ​​нескінченності.

Ighashgpu: списки

Тепер давай спробуємо зламати відразу кілька паролів одночасно. Припустимо, що до нас в руки потрапила база даних хешів паролів. При цьому відомо, що кожен пароль закінчується символами c00l:

f0b46ac8494b7761adb7203aa7776c2a
f2da202a5a215b66995de1f9327dbaa6
c7f7a34bbe8f385faa89a04a9d94dacf
cb1cb9a40708a151e6c92702342f0ac5
00a931d3facaad384169ebc31d38775c
4966d8547cce099ae6f666f09f68458e

Збережи хеші в файлі encrypted.dat і запусти Ighashgpu як зазначено нижче:

ighashgpu.exe -t:md5 -u:[abcdefghijklmnopqrstuwvxyz1234567890_]
-m:??????c00l encrypted.dat

Після завершення роботи програми в папці Ighashgpu з'явиться файл ighashgpu_results.txt зі зламаними паролями:

f0b46ac8494b7761adb7203aa7776c2a:1rootxc00l
f2da202a5a215b66995de1f9327dbaa6:pwd12xc00l
c7f7a34bbe8f385faa89a04a9d94dacf:pwd34yc00l

cb1cb9a40708a151e6c92702342f0ac5:pwd56yc00l
4966d8547cce099ae6f666f09f68458e:pwd98zc00l
00a931d3facaad384169ebc31d38775c:pwd78zc00l

Ighashgpu: сіль

Наостанок давай зробимо злом «підсоленого» хешу. Припустимо, що хеш генерується за наступним алгоритмом:

var plain = password + "s41t";
var hash = md5(plain);

В результаті ми отримали такий хеш: 42151cf2ff27c5181bb36a8bcfafea7b. Ighashgpu дозволяє вказувати «сіль» в параметрі «-asalt»:

ighashgpu.exe -h:42151cf2ff27c5181bb36a8bcfafea7b \
-t:md5 -u:[abcdefghijklmnopqrstuwvxyz1234567890_] \
-asalt:s41t

І ми знову отримали шуканий пароль легко і швидко.

Цікава математика - Для 8-символьного пароля, складеного з перших 126 символів ASCII, є 63 527 879 748 485 376 можливих комбінацій. Для 254 символів кількість можливих комбінацій зростає до 17 324 859 956 700 833 536, що аж в 2,7 мільярда разів більше, ніж людей на нашій планеті. Якщо створити текстовий файл, який містить всі ці паролі, то він займе мільйони терабайт. Звичайно, в сучасному світі це можливо, але вартість зберігання такого файлу буде просто захмарною.

Злом MD5 в режимі турбо

Злом хешів шляхом повного перебору навіть на самому кращому залозі займає досить багато часу, особливо якщо пароль більше восьми символів. Найпростіший спосіб збільшити швидкість підбору пароля - це створити базу даних всіх хешів для певного набору символів. У 80-х роках минулого століття хакери вважали, що коли у них з'явиться більше потужне залізо, 640 Кб пам'яті і жорсткий диск розміром в 10 Мб, то така база стане реальністю і підбір будь-якого пароля перетвориться в хвилинна справа. Однак залізо розвивалося, а мрія так і залишалася мрією. Ситуація змінилася лише в серпні 2003 року, після того, як Філіп Оешлін, доктор філософії в галузі комп'ютерних мереж з Швейцарського технологічного інституту в Лозанні, опублікував свою роботу про проблему вибору оптимального співвідношення місце-час. У ній описувався метод злому хеш-функцій за допомогою «райдужних» таблиць.

Суть нового методу полягає в наступному. Спочатку необхідно вибрати довільний пароль, який потім хешіруется і піддається впливу функції редукції, перетворюючої хеш в будь-якої можливий пароль (наприклад, це можуть бути перші 64 біта вихідного хешу). Далі будується ланцюжок можливих паролів, з якої вибираються перший і останній елементи. Вони записуються в таблицю. Щоб відновити пароль, застосовуємо функцію редукції до вихідного хешу і шукаємо отриманий можливий пароль в таблиці. Якщо такого пароля в таблиці немає, хешіруем його і обчислюємо наступний можливий пароль. Операція повторюється, поки в «райдужної» таблиці не буде знайдений пароль. Цей пароль є кінець однієї з ланцюжків. Щоб знайти вихідний пароль, необхідно прогнати весь ланцюжок заново. Така операція не займає багато часу, в залежності від алгоритму побудови ланцюжка це зазвичай кілька секунд або хвилин. «Веселкові» таблиці дозволяють істотно скоротити обсяг використовуваної пам'яті в порівнянні зі звичайним пошуком. Єдиний недолік описаного методу полягає в тому, що на побудову таблиць потрібно досить багато часу.

Тепер перейдемо від слів до справи і спробуємо зламати пару-трійку хешів паролів за допомогою цього методу.

Rainbow tables - «Веселкові» таблиці - це особливий тип словника, який містить ланцюжка паролів і дозволяє підібрати пароль протягом декількох секунд або хвилин з ймовірністю 85-99%.

«Райдужний» злом

Спочатку необхідно визначитися з програмою. Особисто мені нравітсяRainbowCrack, яка розповсюджується безкоштовно і працює як на Windows, так і на Linux. Вона підтримує чотири алгоритму хешування: LN / NTLM, MD5 і SHA1. Програма не вимагає установки, досить розпакувати її куди-небудь на диск. Після розпакування необхідно знайти «райдужні» таблиці для алгоритму MD5. Тут все не так просто: їх можна або завантажити безкоштовно, або купити, або згенерувати самостійно. Один з найбільших архівів безкоштовних таблиць доступний на сайті проекту Free Rainbow Tables.

До речі, ти теж можеш допомогти проекту, якщо скачаєш клієнт з сайту і приєднаєшся до розподіленої міжнародної мережі, яка генерує «райдужні» таблиці. На момент написання статті на цьому сайті вже було доступно 3 Тб таблиць для алгоритмів MD5, SHA1, LM і NTLM. Якщо у тебе немає можливості злити такий обсяг інформації, то на тому ж сайті можна замовити диски з «райдужними» таблицями. На даний момент пропонується три пакети: LN / NTLM, MD5 і SHA1 - по 200 доларів кожен. Ми ж сгенерируем таблиці самостійно. Для цього необхідно використовувати програму rtgen, що входить до складу RainbowCrack. Вона приймає такі вхідні параметри:

• hash_algorithm - алгоритм хешування (LM, NTLM, MD5 або SHA1);
• charset - один з наборів символів, що міститься у файлі charset.txt;
• plaintextlenmin і plaintextlenmax - мінімальна і максимальна довжина пароля;
• tableindex, chainlen, chainnum і partindex - «магічні числа», описані в статті Філіпа Оешліна

Розглянемо останні параметри докладніше:

1. table_index - індекс «райдужної» таблиці, який можна використовувати при розбивці таблиці на кілька файлів. Я використовував 0, так як моя таблиця складалася всього з одного файлу.
2. chain_len - кількість унікальних паролів в ланцюжку.
3. chain_num - кількість ланцюжків в таблиці.
4. part_index - це параметр, що визначає початок ланцюжка. Творці програми просять використовувати в якості цього параметра тільки число (я використовував 0). Тепер запускаємо генерацію «райдужної» таблиці для MD5:

rtgen.exe md5 loweralpha-numeric 1 7 0 2000 97505489 0

В даному випадку ми створюємо таблицю паролів, що складаються з цифр і великих літер латинського алфавіту і мають довжину від одного до семи символів. На моєму Eee PC з процесором Intel Atom N450 цей процес зайняв майже два дня . У підсумку я отримав файл md5loweralpha-numeric # 1-702000? 975054890.rt розміром в 1,5 Гб.

Далі отриману таблицю необхідно відсортувати, щоб оптимізувати пошук потрібної нам ланцюжка. Для цього запускаємо rtsort.exe:

rtsort.exe md5_loweralpha-numeric#1-7_0_2000x97505489_0.rt

Чекаємо пару хвилин і таблиця готова! Тепер можна ламати самі паролі. Для початку спробуємо підібрати пароль для одного хешу: d8578edf8458ce06fbc5bb76a58c5ca4. Запускаємо rcrack_gui.exe і вибираємо Add Hash ... в меню File. У вікні вводимо хеш і натискаємо OK. Тепер вибираємо файл з «райдужної» таблицею. Для цього використовуємо пункт Search Rainbow Tables ... в меню Rainbow Table. У вікні для вибору файлу шукаємо файл з таблицею, у мене це md5_loweralpha-numeric # 1-7_0_2000x97505489_0.rt, потім тиснемо Open. Через кілька секунд пароль у нас в руках! Аналогічну операцію можна зробити і над списком хешів з файлу.

«Веселкові» таблиці vs. CPU vs. GPU

Я думаю, ти звернув увагу на те, наскільки швидко Ighashgpu здатний зламувати MD5-хеш-кодування повним перебором, і на те, що RainbowCrack робить це ще швидше при наявності гарної «райдужної» таблиці. Я вирішив порівняти швидкість роботи цих програм. Для чистоти експерименту я використовував програму MDCrack, яка здійснює брут пароля на CPU (і є однією з кращих серед програм такого типу). Ось що вийшло в результаті для GPU (nVidia GeForce GT 220M), CPU (Intel Atom N450, два ядра) і «райдужних» таблиць:

Длина пароля | GPU | CPU | Таблицы
4 символа | 00:00:01 | 00:00:01 | 00:00:16
5 символов | 00:00:02 | 00:00:09 | 00:00:16
6 символов | 00:00:16 | 00:05:21 | 00:00:10
7 символов | 00:07:11 | 09:27:52 | 00:00:04

Як бачиш, швидкість перебору з використанням CPU набагато менше, ніж з використанням GPU або «райдужних» таблиць. Більш того, більшість спеціалізованих програм дозволяє створити кластер з відеокарт, завдяки чому швидкість перебору пароля збільшується в рази. Я думаю, ти звернув увагу на те, що швидкість підбору 4- і 5-символьного паролів нижче, ніж швидкість підбору пароля з шести або семи символів. Це пов'язано з тим, що пошук пароля починається тільки після завантаження таблиці в пам'ять. Виходить, що з шістнадцяти секунд в середньому тринадцять витрачається на завантаження і три - на злом хешу.

bit.ly/vEhdir - додавання нового алгоритму хешування в RainbowCrack за допомогою API.

bit.ly/vTSB9K - опис формату «райдужної» таблиці.

замість висновку

В кінці я б хотів трохи поговорити про захист твоїх паролів. По-перше, не використовуй вразливі алгоритми хешування, такі як MD5 або SHA1. На даний момент варто задуматися про використання однієї з криптографічних хеш-функцій SHA2 або SHA3 (як тільки опублікують відповідний стандарт). По-друге, не використовуй функції хешування безпосередньо. Завжди старайся використовувати «сіль» і комбінувати різні алгоритми. І по-третє, вибирай складні довільні паролі довжиною як мінімум вісім символів. Звичайно, це не захистить тебе від злому на 100%, але хоча б ускладнить життя зловмисникам.