Хеш-функція

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

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

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

 

 

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

A: 01 23 45 67

B: 89 ab cd ef

C: fe dc ba 98

D: 76 54 32 10

Також для підрахунку результату використовуються наступні функції:

F(X,Y,Z) = XY v not(X) Z

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

H(X,Y,Z) = X xor Y xor Z

I(X,Y,Z) = Y xor (X v not(Z))

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

 

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

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

1. Запам'ятовуємо перші 512 біт послідовності S.
2. Видаляємо перші 512 біт послідовності S (можна обійтися і без видалення, але тоді на першому кроці треба брати не перші 512, а
3. наступні 512 біт).
4. Викликаємо функцію W. Параметри A, B, C, D — це поточні значення відповідних подвійних слів. Параметр T — це після успішної реєстрації 512 біт.
5. Додаємо до A A0.
6. B = B + B0.
7. C = C + C0.
8. D = D + D0.
9. Якщо довжина послідовності 0, виходимо.
10. Переходимо до кроку 1.

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

 

 

На вхід алгоритму надходить вхідний потік даних, хеш якого необхідно знайти. Довжина повідомлення може бути будь-який (в тому числі нульовою). Запишемо довжину повідомлення в 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 біта і задаються початкові значення (шістнадцятирічне подання):

A = 67 45 23 01;

B = EF CD AB 89;

C = 98 BA DC FE;

D = 10 32 54 76.

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

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

 

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

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

 

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