Хеш-функція

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

 

 

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

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

 

inthash(long int x){

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

return (x % 1000);

}

 

function hash(x:longint):longint;

begin

if (x mod 1000=0) then hash:=1000 else

hash:=x mod 1000;

end;

 

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

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

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

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

 

 

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

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

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

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