Що таке MD5?

MD5 (Англ. Message Digest 5) - 128-бітний алгоритм хешування, розроблений професором Рональдом Л. Рівестом з Массачусетського технологічного інституту (Massachusetts Institute of Technology, MIT) в 1991 році. Призначений для створення «відбитків» або «дайджестів» повідомлень довільної довжини.

Є покращеною в плані безпеки версією MD4. Знаючи MD5-образ (званий також MD5-хеш або MD5-дайджест), неможливо відновити вхідний повідомлення, так як одному MD5-образу можуть відповідати різні повідомлення. Використовується для перевірки автентичності опублікованих повідомлень шляхом порівняння дайджесту повідомлення з опублікованим. Цю операцію називають «перевірка хешу» (hashcheck). Описаний в RFC 1321.

MD5 дозволяє отримувати відносно надійний ідентифікатор для блоку даних. Така властивість алгоритму широко застосовується в різних областях. Воно дозволяє шукати дублюються файли на комп'ютері, порівнюючи MD5 файлів, а не їх вміст. Як приклад, dupliFinder - графічна програма під Windows і Linux. Такий же пошук може працювати і в інтернеті.

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

MD5 використовується для хеширования паролів. В системі UNIX кожен користувач має свій пароль і його знає тільки користувач. Для захисту паролів використовується хешування. Отримати справжній пароль можна тільки повним перебором. При появі UNIX єдиним способом хеширования був DES (Data Encryption Standard), але ним могли користуватися тільки жителі США, тому що вихідні коди DES не можна було вивозити з країни. Під FreeBSD вирішили цю проблему. Користувачі США могли використовувати бібліотеку DES, а решта користувачі мають метод, дозволений для експорту. Тому в FreeBSD стали використовувати MD5 за замовчуванням.

У Linux для перевірки md5 існує команда md5sum, яка обчислює і перевіряє контрольну суму файлу, використовуючи алгоритм MD5. Для ОС сімейства Windows існує безліч програм, що дозволяють перевірити суму md5.

Багато систем використовують базу даних для зберігання паролів і існують кілька способів для їх зберігання:

• Паролі зберігаються як є. При зломі такої бази всі паролі стануть відомі.
• Зберігаються тільки хеші паролів (за допомогою MD5, SHA). Знайти паролі можна тільки повним перебором. Але зараз така задача вирішується за частки секунди. Пароль з таблиці був знайдений всього за 0,036059 сек.
• Зберігаються хеши паролів і кілька випадкових символів. До кожного паролю додається кілька випадкових символів (їх ще називають «salt» або «сіль») І результат ще раз хешіруется. Наприклад, md5 (md5 (pass) + word). Знайти пароль за допомогою таблиць таким методом не вийде.

Історія

MD5 - один із серії алгоритмів з побудови дайджесту повідомлення, розроблений професором Рональдом Л. Рівестом з Массачусетського технологічного інституту. Розроблено в 1991 році, як більш надійний варіант попереднього алгоритму MD4. Пізніше Гансом Доббертіном були знайдені недоліки алгоритму MD4.

У 1993 році Берт ден Боєр (Bert den Boer) і Антон Босселаріс (Antoon Bosselaers) показали, що в алгоритмі можливі псевдоколлізіі, коли різним ініціалізувалися векторах відповідають однакові дайджести для вхідного повідомлення.

У 1996 році Ганс Доббертін (Hans Dobbertin) оголосив про колізії в алгоритмі і вже в той час було запропоновано використовувати інші алгоритми хешування, такі як Whirlpool, SHA-1 або RIPEMD-160.

Через невеликого розміру хешу в 128 біт, можна розглядати birthday атаки. У березні 2004 року був запущений проект MD5CRK з метою виявлення вразливостей алгоритму, використовуючи birthday атаки.

Проект MD5CRK закінчився після 17 серпня 2004, коли Ван Сяоюн (Wang Xiaoyun), Фен Денгуо (Feng Dengguo), Лай Сюецзя (Lai Xuejia) і Юй Хунбо (Yu Hongbo) виявили вразливості в алгоритмі.

1 березня 2005, Arjen Lenstra, Xiaoyun Wang, і Benne de Weger продемонстрували побудова двох X.509 документів з різними відкритими ключами і однаковим хешем MD5.

18 березня 2006 дослідник Властіміл Клима (Vlastimil Klima) опублікував алгоритм, який може знайти колізії за одну хвилину на звичайному комп'ютері, метод отримав назву «туннелирование».

Алгоритм MD5

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

Нижче наведено 5 кроків алгоритму:

Крок 1. Вирівнювання потоку

Вхідні дані вирівнюються так, щоб їх новий розмір L 'був порівнянний з 448 по модулю 512 (L' = 512 - N + 448). Спочатку дописують одиничний біт в кінець потоку, потім необхідне число нульових біт (вирівнювання відбувається, навіть якщо довжина вже порівнянна з 448).

Крок 2. Додавання довжини повідомлення

В залишилися 64 біта дописують 64-бітове представлення довжини даних (кількість біт в повідомленні) до вирівнювання. Якщо довжина перевершує 2⁶⁴ - 1, то дописують тільки молодші біти. Після цього довжина потоку стане кратної 512. Обчислення будуть грунтуватися на уявленні цього потоку даних у вигляді масиву слів по 512 біт.

Крок 3. Ініціалізація буфера

Для обчислень инициализируются 4 змінних розміром по 32 біта і задаються початкові значення шестнадцатерічнимі числами:

А = 23 січня 45 67;

В = 89 AB CD EF;

С = FE DC BA 98;

D = 76 54 32 10.

У цих змінних будуть зберігатися результати проміжних обчислень. Початковий стан ABCD називається ініціалізувалися вектором.

Крок 4. Обчислення в циклі

Заносимо в блок даних елемент n з масиву. Зберігаються значення A, B, C і D, що залишилися після операцій над попередніми блоками (або їх початкові значення, якщо блок перший).

AA = A

BB = B

CC = C

DD = D

Підсумовуємо з результатом попереднього циклу:

A = AA + A

B = BB + B

C = CC + C

D = DD + D

Після закінчення циклу необхідно перевірити, чи є ще блоки для обчислень. Якщо так, то змінюємо номер елемента масиву (n ++) і переходимо в початок циклу.

Крок 5. Результат обчислень

Результат обчислень знаходиться в буфері ABCD, це і є хеш. Якщо вивести слова в зворотному порядку DCBA, то ми отримаємо наш MD5 хеш.

MD5-хеш-кодування

Хеш містить 128 біт (16 байт) і зазвичай представляється як послідовність з 32 шістнадцяткових цифр.

Кілька прикладів хешу:

"MD5 (" md5 ") = 1bc29b36f623ba82aaf6724fd3b16718"

"MD5 (" md4 ") = c93d3bf7a7c4afe94b64e30c2ce39f4f"

Навіть невелика зміна вхідного повідомлення (у нашому випадку на один біт: ASCII символ «5» з кодом 0x35₁₆ = 000110101₂ замінюється на символ «4» з кодом 0x34₁₆ = 000110100₂) Призводить до повної зміни хешу. Така властивість алгоритму називається лавинним ефектом.

Приклад MD5-хешу для «нульовий» рядки:

"MD5 (" ") = d41d8cd98f00b204e9800998ecf8427e"

Атаки переборного типу

Для повного перебору або перебору по словнику можна використовувати програми PasswordsPro, MD5BFCPF, John the Ripper. Для перебору за словником існують готові словники.

RainbowCrack - ще один метод злому хешу. Він заснований на генеруванні великої кількості хешів з набору символів, щоб по вийшла базі вести пошук заданого хешу. Хоча генерація хешів займає багато часу, зате наступний злом проводиться дуже швидко.

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

Колізії MD5

Колізія хеш-функції - це отримання однакового значення функції для різних повідомлень і ідентичного початкового буфера. На відміну від колізій, псевдоколлізіі визначаються як рівні значення хешу для різних значень початкового буфера, причому самі повідомлення можуть збігатися або відрізнятися. У 1996 році Ганс Доббертін знайшов псевдоколлізіі в MD5, використовуючи певні ініціалізували вектори, відмінні від стандартних. Виявилося, що можна для відомого повідомлення побудувати другий, таке, що воно буде мати такий же хеш, як і вихідне. C точки зору математики це означає: MD5 (IV, L1) = MD5 (IV, L2), де IV - початкове значення буфера, а L1 і L2 - різні повідомлення.

Джерела:

• ru.wikipedia.org - MD5, матеріал з Вікіпедії - вільної енциклопедії;
• double-dot.info - перевірка файлів. Використання MD5summer;
• linuxiso.com.ua - контрольна сума MD5.

Додаткова інформація:

• md5x.ru - онлайн-MD5 і base64 кодер / декодер;
• md5x.ru - хеши найбільш часто використовуваних паролів.