Як зламати функцію md5

MD5 є дуже поширеною функцією для обчислення хешів.

Початківці часто використовують його для хешування паролів, що не є гарною ідеєю, оскільки існує багато способів відновити оригінальний пароль.

Ця стаття описує конкретні методи, як це зробити.

Часова складність

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

Якщо ми зламуємо пароль, перебираючи комбінації по черзі, то це атака грубої сили.

Методи крекінгу

Є кілька стратегій:

• Послідовний метод спроб і помилок (атака грубою силою)
• Тестування словникових паролів
• Райдужні таблиці (попередньо розрахована хеш-база даних)
• Пошукові запити в Google
• Попадання колізій в алгоритм

Існує набагато більше методів, в цій статті описані лише найпоширеніші з них.

Стратегії злому грубою силою

Всі комбінації букв, цифр та інших символів випробовуються по черзі.

Згенеровані спроби хешуються одна за одною і порівнюються з оригінальним хешем.

Так, наприклад:

aaaaaaabaaacaaadaaaeaaaf...

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

Тому важливо обирати довгі паролі, бажано випадкові, зі спеціальними символами.

Стратегія словникової атаки

Зазвичай люди обирають слабкі паролі, які існують у словнику.

Якщо скористатися цим фактом, то можна швидко відкинути малоймовірні варіанти на кшталт 6w1SCq5cs і натомість вгадувати вже існуючі слова.

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

Веселкові таблиці - попередньо розрахована база даних

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

Насправді, пошук завжди на порядки швидше, ніж перебір хешів знову і знову.

Крім того, для більших витоків даних, паролі можуть бути паралельно хешовані таким чином і, наприклад, 10% всіх паролів користувачів можуть бути швидко відновлені.

Хорошою базою паролів є, наприклад, Crack Station.

Пошук в Google

Багато простих паролів відомі безпосередньо Google, оскільки він індексує сторінки, які містять хеші.

Я завжди використовую Google як перший варіант. :)

Пошук колізій в алгоритмі

Принцип Діріхле описує, що якщо ми маємо набір хешів, які завжди мають довжину 32 символи, то існує як мінімум 2 різних пароля по 33 символи (один довший), які генерують один і той же хеш.

На практиці шукати колізії не має сенсу, але іноді автор заявки сам полегшує собі завдання, перераховуючи колізії.

Наприклад:

$password = 'пароль';

for ($i = 0; $i <= 1000; $i++) {
    $password = md5($password);
}

echo $password; // 1000x хешування через md5()

У цьому випадку має сенс вгадувати колізію, а не вихідний хеш.

Вип'ємо за розлив!

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt