Хеш-функція MD5

Хеш-функція MD5

Приватний вищий навчальний заклад

«Міжнародний науково-технічний університет імені академіка Юрія Бугая»

Полтавський інститут бізнесу

Кафедра інформаційнихтехнологій, економіки та менеджменту

КУРСОВА РОБОТА

з Криптографічні системи захисту інформації

на тему: _Хеш-функція MD5

ВСТУП

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

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

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

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

для прискорення пошуку даних в БД;

для перевірки цілісності та автентичності повідомлень;

для створення стисненого образу, що застосовується в процедурах ЕЦП;

для захисту пароля в процедурах аутентифікації.

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

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

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

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

1.ЩО ТАКЕ MD5

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

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

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

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

.1 Історія алгоритму

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

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

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

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

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

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

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

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

грудня 2010 рік - Тао Се (TaoXie) і Фен Денг (FengDengguo) вперше представили колізію повідомлень довжиною в один блок (512 біт). Раніше колізії були знайдені для повідомлень довжиною в два блоки і більш. Пізніше Марк Стівенс (MarcStevens) повторив успіх, опублікувавши блоки з однаковим хешем MD5, а також алгоритм для отримання таких колізій.

рік - був опублікований інформаційний документ RFC 6151. Він визнає алгоритм хешування MD5 небезпечним для деяких цілей і рекомендує відмовитися від його використання.

.2 Для чого потрібен MD5

Щоб зрозуміти навіщо потрібен алгоритмMD5 спочатку розглянемо принцип дії звичайної хеш-функції.

Припустимо, у нас є певний набір даних. Для простоти будемо розглядати натуральні числа від 1 до106. І нехай є деяка функція, в якій один параметр - натуральне число від 1 до 106, а повертається значення у вигляді натурального числа від 1 до 1000. Нам не важливо, що саме робить ця функція, нам важливо те, що вона кожному натуральному числу від 1 до 106ставить у відповідність інше натуральне число від 1 до 1000. Для прикладу розглянемо одну з найпростіших функцій, які виконують цю дію:(long int x){

if (x%1000==0) return 1000;(x % 1000);

}hash(x:longint):longint;(x mod 1000=0) then hash:=1000 else:=x mod 1000;;

Це і є проста хеш-функція. Якщо ми знаємо параметр функції, то однозначно можемо сказати, якою буде результат. А якщо нам відомий результат, то чи можемо ми дізнатися однозначно параметр? Звичайно, ні. Для числа 234 параметр може бути 234,1234, 2234,3234 ... Тому однозначно відновити параметр не вийде.

Тепер повернімося до алгоритму MD5. Для функції з прикладу, якщо відомий результат, можна легко знайти параметр, для якого буде такий же результат. А ось для функції MD5 це зробити не так-то просто. Тобто якщо у нас є тільки результат функції MD5, то ми не зможемо знайти параметр, для якого функція видає цей же результат (мова навіть не йде про однозначне відновлення параметра). MD5 використовують для зберігання паролів. Наведу приклад, коли зберігання паролів у відкритому вигляді небезпечно. Візьмемо сайт "Дистанційне навчання". На цьому сайті проходять міські олімпіади школярів з інформатики, щодня навчаються сотні школярів і студентів. У багатьох школах доступу в Інтернет немає, і школярам необхідно користуватися послугами сайту або вдома, або не в своїй школі. Тому сайт почали встановлювати в самих школах. Тобто навчання відбувається не на самому сайті, а на його копії, встановленій в школі. Проблема в тому, що разом з сайтом школа отримувала паролі всіх користувачів (в тому числі і адміністраторів), і цими паролями будь-хто міг скористатися для "адміністрування" самого сайту. Було два способи вирішити цю проблему:

. Перед створенням копії сайту, яка буде перенесена в школу, видаляти всі паролі.

. Зашифрувати всі паролі так, щоб ніхто не зміг розшифрувати їх назад.

Був обраний другий спосіб. Зараз паролі зберігаються в зашифрованому вигляді (за допомогою MD5). Після того, як користувач введе свій пароль, від пароля обчислюється хеш-функція MD5. Результат порівнюється зі значенням, що зберігається в базі. Якщо значення рівні, то пароль вірний. Ще MD5 можна використовувати в якості контрольної суми. Припустимо, необхідно кудись скопіювати файл. Причому немає ніяких гарантій, що файл буде доставлений без пошкоджень. Перед відправкою можна порахувати MD5 від вмісту файлу і передати результат разом з файлом. Потім порахувати MD5 від прийнятого файлу і порівняти два результату. Якщо результати різні, то це означає, що файл або результат був зіпсований при передачі. Останнім часом MD5 стали використовувати інтернет-казино. Перед тим, як зробити ставку, гравець отримує хеш від результату гри. Коли ставка зроблена, гравець отримує результат гри (наприклад, випало число 26). Порахувавши від результату хеш-функцію, можна переконатися, що казино згенерувало це число до того, як гравець зробив ставку. Але не варто думати, що виграти в цьому казино дуже просто. Весь секрет у тому що, ймовірність виграшу підібрана таким чином, що гравець майже завжди буде в програші[1].

.3 Приклади використання MD5

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

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

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

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

Паролі зберігаються як є. При зломі такої бази всі паролі стануть відомі.

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

До кожного паролю додається кілька випадкових символів (їх називають «сіль») і результат хешується. Отриманий хеш разом з «сіллю» зберігаються у відкритому вигляді. Знайти пароль за допомогою таблиць таким методом не вийде[2].

2. ЯК ПРАЦЮЄ MD5

Тепер подивимося, як саме працює MD5. Для обробки MD5 отримує деякий рядок. Цей рядок перетвориться в послідовність з нулів і одиниць. Такі дій виконуються за допомогою системи, яка видає кожному символу свій номер. Ці номери можна записати в двійковій системі числення. Виходить, кожен символ можна записати як послідовність нулів і одиниць. Якщо цим скористатися, отримаємо з рядка послідовність з нулів і одиниць. Нехай q буде довжиною отриманої послідовності (рівно 64 біта, можливо, з незначними нулями). До отриманої послідовності приписується 1. В результаті довжина послідовності збільшується на 1. Потім до послідовності приписуються нулі, поки довжина не стане по модулю 512 дорівн 448 (lengthmod 512 = 448). Далі до послідовності дописують молодші 32 біта числа q, а потім - старші. Довжина послідовності стає кратною 512. Отриману послідовність назвемо S. Для підрахунку результату використовуються чотири подвійні слова (32 біта). Ці подвійні слова не започатковано наступними шістнадцятирічними значеннями, де першим слід наймолодший байт:: 01 23 45 67

B: 89 ab cd ef: fe dc ba 98

D: 76 54 32 10

Також для підрахунку результату використовуються наступні функції:(X,Y,Z) = XY v not(X) Z

G(X,Y,Z) = XZ v Y not(Z)(X,Y,Z) = X xor Y xor Z(X,Y,Z) = Y xor (X v not(Z))

X, Y, Z - це подвійні слова. Результати функцій, також подвійні слова. Для підрахунку використовується ще одна функція (назвемо її W). Вона хитро обробляє дані і повертає результат. Обробка даних відбувається з використанням функцій F, G, H, I[3].

Рис.2.1.Схематично зображена функція. Зліва - вхідні дані, праворуч - вихідні.

Всі необхідні функції і позначення розглянуті. Тепер розглянемо, як відбувається прорахунок результату:

. Запам'ятовуємо перші 512 біт послідовності S.

. Видаляємо перші 512 біт послідовності S (можна обійтися і без видалення, але тоді на першому кроці треба брати не перші 512, а наступні 512 біт).

. Викликаємо функцію W. Параметри A, B, C, D - це поточні значення відповідних подвійних слів. Параметр T - це після успішної реєстрації 512 біт.

. Додаємо до A A0.

. B = B + B0.

. C = C + C0.

. Якщо довжина послідовності 0, виходимо.

. Переходимо до кроку 1.

Після виконання цього алгоритму A, B, C, D - це результат (його довжина буде 128 біт). Часто можна бачити результат MD5 як послідовність з 32 символів 0..f. Це те ж саме, тільки результат записаний не в двійковій системі числення, а в шістнадцятирічній[4].

.1 Алгоритм MD5

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

Далі представлений алгоритм вираховування хеша.

Нижче наведено алгоритм обчислення хешу.

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

Кінець вихідного повідомлення, довжиною L, дописують одиничний біт, потім необхідне число нульових біт так, щоб новий розмір L 'був порівнянний з 448 по модулю 512 (L' mod 512 = 448). Додавання нульових біт виконується, навіть якщо нова довжина, включаючи одиничний біт, вже можна порівняти з 448[6].

. Додавання довжини повідомлення.

До модифікованого повідомленням дописують 64-бітове представлення довжини даних (кількість біт в повідомленні). Тобто довжина повідомлення T стає кратною 512 (T mod 512 = 0). Якщо довжина вихідного повідомлення перевищує 264 - 1, то дописують тільки молодші 64 біта. Крім цього, для зазначеного 64-бітного представлення довжини спочатку записуються молодші 32 біта, а потім старші 32 біта[7].

. Ініціалізація буфера.

Для обчислень ініціалізуются 4 змінних розміром по 32 біта і задаються початкові значення (шістнадцятирічне подання):= 67 45 23 01;= EF CD AB 89;= 98 BA DC FE;= 10 32 54 76.

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

. Обчислення хешу в циклі.

Оригінал тексту розбивається на блоки T, довжиною 512 біт. Для кожного блоку в циклі виконується процедура, наведена на рис.2. Результат обробки всіх блоків вихідного повідомлення в вигляді об'єднання 32-бітних значень змінних ABCD і буде хешем.

Рис.2.1.1 Шаг основного розрахункового циклу

У кожному раунді над змінними ABCD і блоком вихідного тексту Т в циклі (16 ітерацій) виконуються однотипні перетворення за такою схемою.

Рис.2.1.2. Одна ітерація циклу раунду

Умовні позначення.- раундова функція, яка визначається за наступною таблицею.

Таблиця 2.1.1.

Раундові функції RF

) tj - j-а 32-бітова частина блоку вихідного повідомлення Т зі зворотним порядком проходження байт;

) ki - ціла частина константи, яка визначається за формулою= 232 * | sin(i + 16 * (r - 1)) |,

де i - номер ітерації циклу (i = 1..16);- номер раунду (r = 1..4).

Аргумент функції sin вимірюється в радіанах.

) ⊞ - додавання за модулем 232.

) <<< si - циклічний зсув вліво на si розрядів.

Використовувана 32-бітова частина блоку вихідного повідомлення tjі величина циклічного сдвигу вліво siзалежать ві номеру ітерації та приведені в таблиці 2.1.2.

Після 4 раундів нове (модифіковане) значення кожної з змінних ABCD складається (⊞) з вихідним (значенням змінної до 1-го раунду)[9].

. Перестановка байт в змінних ABCD. Після обробки всіх блоків вихідного повідомлення для кожної змінної виконується зворотна перестановка байт, і в результаті ми отримаємо наш MD5 хеш[10].

Таблиця 2.1.2.

Величини, що використовуються на етапі циклу раунду

.2 Приклади MD5-хешей

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

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

Навіть невелика зміна вхідного повідомлення (в нашому випадку на один біт: ASCII символ «5» з кодом3516 = 0001101012замінюється на символ «4» з кодом 3416 = 0001101002) призводить до повної зміни хешу. Така властивість алгоритму називається лавинним ефектом[12].("md4") = C93D3BF7A7C4AFE94B64E30C2CE39F4F

Приклад MD5-хеша для «нульового» рядка:("") = D41D8CD98F00B204E9800998ECF8427E

Цей стандарт кодування є одним з найпоширеніших методів захисту даних не тільки в прикладному, але і в веб-програмуванні. Тому не буде зайвим убезпечити свій md5 hash від навмисного злому.

Основним способом, що гарантує безпеку хешу вашого пароля, є використання «солі». Він заснований на додаванні до паролю кількох випадкових символів і подальшому хешуванні результату[13].

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

Створити хеш-код MD5 в php можна за допомогою декількох функцій:() - в якості одного з параметрів приймає значення «солі»;() - на відміну від попередньої ця функція повністю автоматизує весь процес, в тому числі і генерування значення солі.

Її синтаксис:crypt ( string$str [, string $salt ] )

Приклад використання:= crypt('password')

При використанні функції md5 () в PHP для завдання значення солі використовують методи генерації випадкових чисел. Наприклад, rand ():

<? Php

$ Pass = 'admin';salt () {

$ S = '';

$ Length = rand (7,12); // довжинасолі($ i = 0; $ i<$ length; $ i ++) {

$ S. = Chr (rand (33,126)); // випадковийсимвол з таблиці ASCII

}$ s;

}md5 (md5 ($ pass) .salt ());

?>

Крім застосування «солі» було розроблено ще кілька методів захисту хешу MD5:(Unix) - задане первинне значення проходить цикл хеширования близько 1000 разів;(HMAC) - даний метод заснований на використанні в хешуванні спеціального ключа;(Base64) - отриманий хеш ще раз кодуються за допомогою алгоритму Base64.

У цьому розділі наведено лише початкові відомості про забезпечення безпеки хешу, отриманого за допомогою цього алгоритму. Найпростішим і ефективним з них є використання унікального значення «солі», яка дозволяє істотно «насолити» зловмисникові і «підсолодити» життя власникузламуваного паролю[14].

. НАДІЙНІСТЬ

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

Під колізією розуміють можливість отримання однакового результату обчислень хеш-функції при різних вхідних значеннях[15].

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

Тобто велика ймовірність розшифровки паролів MD5 є основною причиною відмови від використання цього алгоритму. Більшість криптологів (фахівці з шифрування даних) пов'язують низьку надійність MD5 з малою довжиною одержуваного хеш-коду.У 1996 році Ганс Доббертін знайшов псевдоколлізії в MD5, використовуючи певний започатковано буффер (ABCD). Також в 2004 році китайські дослідники Ван Сяоюн, Фен Денгуо, Лай Сюецзя і ЮйХунбо оголосили про виявлену ними уразливості в алгоритмі, що дозволяє за невеликий час (1 година на кластері IBM p690) знаходити колізії. Однак в 2006 році чеський дослідник Властіміл Клима опублікував алгоритм, що дозволяє знаходити колізії на звичайному комп'ютері з будь-яким початковим вектором (A, B, C, D) за допомогою методу, названого їм «туннелювання»[16].

3.1 ВзломMD5

В Інтернеті можна знайти багато програм, які обіцяють знайти рядок, для якої алгоритм MD5 видає заданий результат. Ці програми дійсно працюють. Раніше зазначалося, що відновити параметр неможливо. Як же працюють ці програми? Вони перебирають всі можливі рядки, застосовують до них алгоритм MD5, а потім порівнюють зі зразком. Якщо значення співпали, це означає, що програма знайшла необхідний рядок. Але у цих програм є маленький недолік. Припустимо, відомо, що програму доведеться перебрати усі слова довжиною в 8 символів, що складаються з маленьких і великих латинських букв. Скільки часу це займе? Скільки всього таких слів? На першому місці може стояти будь-який з 26 * 2 = 52 символів. На 2, 3, 4, 5, 6, 7 і 8 - теж 52. Значить, всього таких слів буде: 52 * 52 * 52 * 52 * 52 * 52 * 52 * 52 = 528 = 53 * 1012. А якщо використовуються не тільки латинські букви? То це ще більше. Перебір всіх варіантів на звичайному персональному комп'ютері займе дуже багато часу. В Інтернеті можна знайти сайти, які по введеному хешу видають рядок, для якої буде точно такий же хеш. Ці сайти використовують базу даних з заздалегідь прорахованим хешом. Але в базах зберігаються не всіхеши, а тільки самі використовувані. Так що рекомендується використовувати в якості пароля абсолютно випадкову послідовність символів[17].

На даний момент існують кілька видів «злому» хешів MD5 - підбору повідомлення із заданим хешем:

Перебір по словникомforce

Колізія хеш-функції

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

Коротко розглянемо ці види «злому»:

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

Повний перебір (або метод «грубої сили», англ. Bruteforce) - метод вирішення математичних задач. Відноситься до класу методів пошуку рішення вичерпання всіляких варіантів. Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже велике, то повний перебір може не дати результатів протягом декількох років або навіть століть.

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

У криптографії на обчислювальної складності повного перебору ґрунтується оцінка крипостійкості шифрів. Зокрема, шифр вважається крипостійким, якщо не існує методу «злому» істотно більш швидкого ніж повний перебір всіх ключів. Криптографічні атаки, засновані на методі повного перебору, є найбільш універсальними, але і найдовшими[20].- комп'ютерна програма для швидкого злому хешей. Є реалізацією техніки Філіпа Окслінаfastertime-memorytrade-off. Вона дозволяє створити базу предсгенерованихLanManagerхешів, за допомогою якої можна майже миттєво зламати практично будь-який алфавітно-цифровий пароль.Хоча створення райдужних таблиць займає багато часу і пам'яті, наступний злом проводиться дуже швидко. Основна ідея даного методу - досягнення компромісу між часом пошуку по таблиці і займаної пам'яттю[21].

Колізією хеш-функції H називається два різних вхідних блока даних x і y таких, що H (x) = H (y).

Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. У деяких окремих випадках, коли безліч різних вхідних даних звичайно, можна задати ін'єкційних хеш-функцію, за визначенням не має колізій. Однак для хеш-функцій, що приймають вхід змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії зобов'язані існувати, оскільки хоча б для одного значення хеш-функції відповідне йому безліч вхідних даних (повний прообраз) буде нескінченне - і будь-які два набори даних з цієї безлічі утворюють колізію[22].

.2 Колізії MD5

Колізія хеш-функції - це отримання однакового значення функції для різних повідомлень і ідентичного початкового буфера. На відміну від колізій, псевдоколлізії визначаються як рівні значення хешу для різних значень початкового буфера, причому самі повідомлення можуть збігатися або відрізнятися. У MD5 питання колізій не вирішується[23].

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

В = 0x3B341042= 0x5F62B97C= 0x4BA763E

і задати вхідний повідомлення

то, додаючи число 29 до певного 32-розрядного слова в блоковому буфері, можна отримати друге повідомлення з таким же хешем[24].

Тоді MD5 (IV, L1) = MD5 (IV, L2) = BF90E670752AF92B9CE4E3E1B12CF8DE.

У 2004 році китайські дослідники Ван Сяоюн (WangXiaoyun), Фен Денг (FengDengguo), Лай Сюецзя (LaiXuejia) і ЮйХунбо (YuHongbo) оголосили про виявлену ними уразливості в алгоритмі, що дозволяє за невеликий час (1 година на кластері IBM p690) знаходити колізії.

У 2005 році Ван Сяоюн і ЮйХунбо з університету Шаньдун в Китаї опублікували алгоритм, який може знайти дві різні послідовності в 128 байт, які дають однаковий MD5-хеш[25].

Кожен з цих блоків дає MD5-хеш, рівний 79054025255fb1a26e4bc422aef54eb4.

У 2006 році чеський дослідник Властіміл Клима опублікував алгоритм, що дозволяє знаходити колізії на звичайному комп'ютері з будь-яким початковим вектором (A, B, C, D) за допомогою методу, названого їм «туннелирование».

Алгоритм MD5 використовує ітераційний метод Меркле-Дамгарда, тому стає можливим побудова колізій з однаковим, заздалегідь обраним префіксом. Аналогічно, колізії виходять при додаванні однакового суфікса до двох різних префіксам, які мають однаковий хеш. У 2009 році було показано, що для будь-яких двох заздалегідь обраних префіксів можна знайти спеціальні суфікси, з якими повідомлення будуть мати однакове значення хешу. Складність такої атаки становить всього 239 операцій підрахунку хешу[26].

Метод Ван Сяоюн і ЮйХунбо

Метод Ван Сяоюн і ЮйХунбо використовує той факт, що MD5 побудований на ітераційному методі Меркле-Дамгарда. Поданий на вхід файл спочатку доповнюється, так щоб його довжина була кратна 64 байтам, після цього він ділиться на блоки по 64 байта кожен M0,M1,…,Mn-1.Далі обчислюється послідовність 16-байтних станів s0,…,snза правилом sf+1 = ƒ(sj,Mi), де ƒ- деяка фіксована функція. Початковий стан s0називається ініціалізовним вектором[27].

Метод дозволяє для заданого ініціалізованоговектора знайти дві пари М,М’ и N,N’, такі що ƒ(ƒ(s,M),M’)= ƒ(ƒ(s,N),N’). Важливо відзначити, що цей метод працює для будь-якого ініціалізованоговектора, а не тільки для вектора використовуваного за стандартом.

Ця атака є різновидом диференціальної атаки, яка, на відміну від інших атак цього типу, використовує цілочисельне віднімання, а не XOR в якості запобіжної різниці. При пошуку колізій використовується метод модифікації повідомлень: спочатку вибирається довільне повідомлення M0, далі воно модифікується за деякими правилами, сформульованим у розділі, після чого обчислюється диференціал хеш-функції, причому =М0+dM0з ймовірністю 2-37. До М0і  застосовується функція стиснення для перевірки умов колізії; далі вибирається довільне M1,модифікується, обчислюється новий диференціал, рівний нулю з ймовірністю 2-30, а рівність нулю диференціала хеш-функції як раз означає наявність колізії. Виявилося, що знайшовши одну пару М0і , можна змінювати лише два останніх слова в М0,тоді для знаходження нової пари М1і  потрібно всього близько 239 операцій хеширования.

Застосування цієї атаки до MD4 дозволяє знайти колізію менше ніж за секунду. Вона також може бути застосована до інших хеш-функцій, таких як RIPEMD і HAVAL[28].

ВИСНОВКИ

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

Алгоритм шифрования MD5// Компьтерная газета - Режим доступу:http://www.nestor.minsk.by/kg/index.html

Що таке MD5, як отримати MD5-хеш// Гаджет експерт- Режим доступу:http://gadget-explorer.com/articles/shho-take-md5-yak-otrimati-md5-hesh/// Криптография- Режим доступу:http://kriptografea.narod.ru/MD5.html

Криптографические методы защиты// Информационные технологии и системы - Режим доступу:https://sites.google.com/site/anisimovkhv/learning/kripto/lecture/tema9// Википедия - Режим доступу:https://ru.wikipedia.org/wiki/MD5

Колисниченко Д.Н. PHP и MySQL. Разработка веб-приложений. - 5-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2015. - 592с.

Хэш-функцияMD5// Хабрахабр- Режим доступу:https://habrahabr.ru/sandbox/26876/

Хеширование и расшифровкаMD5// Сайтостроение от А до Я- Режим доступу:http://www.internet-technologies.ru/articles/article_2346.html

ХэшфункцияMD5// Инфостарт- Режим доступу:https://infostart.ru/public/96713/

Все методывзломаMD5// Хакер.ру- Режим доступу:https://xakep.ru/2013/10/13/md5-hack/

Шнайер Б. Прикладнаякриптография. Протоколы, алгоритмы, исходныетексты на языкеСи - М.: «Триумф», 2002.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы крипто-графии. Учебноепособие. - М.: «Гелиос АРВ», 2001.

Чмора А.Л. Современная прикладная криптография. - М.: «Гелиос АРВ», 2002.

Введение в криптографию / Подобщ. ред. В.В. Ященко. - 3-е изд., доп. - М.: МЦНМО, «ЧеРо», 2000.

Саломаа А. Криптография с открытым ключом / Пер. с англ. - М.: Мир, 1996.

Столингс В. Криптография и защитасетей. Принципы и практика. 2-е изд. - М.: Издательскийдом «Вильямс», 2001.

Лидл Р., Нидеррайтер Г. Конечные поля, т. 1,2. - М.: Мир, 1998.A.J., van Oorcshot P.C., Vanstone S.A. Handbook of Applied Cryptography. - CRC Press, 1997. (http://www.cacr.math.uwaterloo.ca/hac/).

Диффи У., Хеллман М.Э. Защищенность и имитостойкость. Введение в криптографию. - ТИИЭР, т.67, №3, 1979.

Молдовян Н. А. Криптография: от примитивов к синтезу алгоритмов. - СПб: BHV-Петербург, 2004.

Шеннон К. Работы по теории информации и кибернетике. - М.: ИЛ, 1963.

История криптографии. А.В. Бабаш, Г.П. Шанкин. - М.: "ГелиосАРВ", 2001 г.

Агибалов Г.П. Избранные теоремы начального курса криптографии: Учебноепособие. - Томск: Изд-во НТЛ, 2005. - 116 с.

Асосков А.В и др. Поточные шифры. - М.: Кудиц-образ, 2003. - 336 с.

Брассар Ж. Современнаякриптология. - М.: ПОЛИМЕД, 1999.