Хеш-функція

 

1. ЩО ТАКЕ MD5

1.1. ІСТОРІЯ АЛГОРИТМУ

1.2. ДЛЯ ЧОГО ПОТРІБЕН MD5

1.3. ПРИКЛАДИ ВИКОРИСТАННЯ MD5

2. ЯК ПРАЦЮЄ MD5

2.1.АЛГОРИТМMD5

2.2. ПРИКЛАДИ MD5-ХЕШЕЙ

2.3. ОСНОВИ БЕЗПЕКИ ПРИ ВИКОРИСТАННІ MD5

3. НАДІЙНІСТЬ

3.1. ВЗЛОМ MD5

3.2. КОЛІЗІЇ MD5

 

 

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

Хешування (англ. Hashing) - перетворення вхідного масиву даних довільної довжини у вихідний рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, вхідний масив - прообразом, а результати перетворення - хешем, хеш-кодом, хеш-образом, цифровим відбитком або дайджестом повідомлення (англ. Messagedigest).

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

На практиці хеш-функції використовують для таких цілей:

• для прискорення пошуку даних в БД;
• для перевірки цілісності та автентичності повідомлень;
• для створення стисненого образу, що застосовується в процедурах ЕЦП;
• для захисту пароля в процедурах аутентифікації.

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

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

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

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

 

 

Після цього MD5 став використовуватися для вирішення самих різних завдань, від хеширования паролів в CMS до створення електронно-цифрових підписів та SSL-сертифікатів.

MD5 (англ. MessageDigest 5) - 128-бітний алгоритм хешування, розроблений професором Рональдом Л. Ривестом з Массачусетського Технологічного Інституту (MIT, MassachusettsInstituteofTechnlogy) в 1991 році, а опублікований в квітні 1992 року в RFC 1321. Потім він здобув велику популярність і став використовуватися всюди.

Призначений для створення «відбитків» або «дайджестів» повідомлень довільної довжини. Прийшов на зміну MD4, який був недосконалий. Працює на 32-бітних машинах.Після цього MD5 став використовуватися для вирішення самих різних завдань, від хешування паролів в CMS до створення електронно-цифрових підписів та SSL-сертифікатів, а також використовується для перевірки автентичності опублікованих повідомлень шляхом порівняння дайджесту повідомлення з опублікованими. 

Знаючи MD5, неможливо відновити вхідний повідомлення, так як одному MD5 можуть відповідати різні повідомлення.

Починаючи з 1993 року, регулярно з’являються дослідження, які знаходять все нові уразливості в алгоритмі MD5. На даний момент алгоритм MD5 вважається вразливим і поступово замінюється алгоритмом SHA.

 

 

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

1992 рік – вперше описаний в RFC 1321, де і здобуває велику популярність.

Квітень 1993 року – році Берт ден Бур (BertdenBoer) і Антон Босселарс (AntoonBosselaers) показали, що в алгоритмі можливі псевдоколлізії, коли різним ініціалізованим векторам відповідають однакові дайджести для вхідного повідомлення.

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

Через невеликого розміру хешу в 128 біт можна розглядати birthday-атаки. У березні 2004 року був запущений проект MD5CRK з метою виявлення вразливостей алгоритму, використовуючи birthday-атаки. Проект MD5CRK закінчився 17 серпня 2004 року, коли Ван Сяоюн (WangXiaoyun), Фен Денг (FengDengguo), Лай Сюецзя (LaiXuejia) і ЮйХунбо (YuHongbo) виявили вразливості в алгоритмі.

1 березня 2005 рік –АрьєнЛенстра, Ван Сяоюн і Бенне де Вегер продемонстрували побудову двох документів X.509 з різними відкритими ключами і однаковим хешем MD5.

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

Кінець 2008 року – US-CERT закликав розробників програмного забезпечення, власників веб-сайтів і користувачів припинити використовувати MD5 в будь-яких цілях, так як дослідження продемонстрували ненадійність цього алгоритму.

24 грудня 2010 рік – Тао Се (TaoXie) і Фен Денг (FengDengguo) вперше представили колізію повідомлень довжиною в один блок