Введення в KDF на прикладі вирішення криптографічного ребуса

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

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

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

Повідомлення було закодовано в base64:

KDF function uses only this sentence as input for a generic hash algorithm which has a 32 bytes output.

Encryption algorithm is AES CBC with the concatenated key and init vector as KDF output.

Here is the encrypted question: далі йшов текст закодованого повідомлення як шістнадцятковий рядок.

KDF

Перше, що кинулося в очі, це невідоме мені KDF function.

Key Derivation Function - це така функція, яка служить для отримання секретних ключів з якогось іншого секретного значення для завдань захисту інформації.

Найпоширеніше завдання для KDF - це хешування паролів. Де потрібно ускладнити злом скомпрометованих хешів.

update (дякую frol):

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

А хіба звичайний sha-2 з сіллю не підходить для задах хешування, збереження і захисту паролів?

Ось KDF забезпечує кращий захист секретних ключів (такі як паролі), ніж звичайні криптографічні хеш-функції. Виходить це за рахунок розтягнення ключа (key stretching) і можливість використовувати різні псевдопромінювальні хеш-функції (pseudo-random hash-function).

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

Вся справа в тому, що застосовуючи розтягнення ключа, а саме багаторазове повторення хешування, дозволяє керувати складністю підбору хешу, використаної пам'яті і процесорним часом. Що в підсумку дає багаторазове ускладнення злому.

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

Види KDF

І ось розібралися з KDF, тепер повернемося до першої підказки.

KDF function uses only this sentence as input for a generic hash algorithm which has a 32 bytes output.

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

Які ж є в природі різновиди KDF?

Ось приблизний список:

KDF1, KDF2, KDF3, KDF4, MGF1, PBKDF-Schneier, PBKDF1, PBKDF2, bcrypt, scrypt, HKDF.

Забагато, треба б виключити свідомо невірні.

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

Залишилися найбільш сучасні та актуальні: PBKDF2, bcrypt, scrypt, HKDF.

Здавалося, найбільш перспективний претендент - це PBKDF2. Але на вхід отримує, крім хеш-функції, ще й сіль, кількість ітерацій і кількість вихідних байт.

Далі з'ясувалося, що bcrypt обов'язково на вхід вимагає сіль, та ще від реалізації залежить кількість ітерацій. Оскільки про сіль з повідомлення нам нічого не відомо, bcrypt вибуває з претендентів.

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

Залишається так само і HMAC-based Extract-and-Expand Key Derivation Function або HKDF.

Пошук ключа

Другий етап розшифровки, це зрозуміти як розшифровувати.

У підказці йдеться: Encryption algorithm is AES CBC with the concatenated key and init vector as KDF output.

З алгоритмом шифрування все ясно - це AES в режимі шифрування CBC.

Для розшифрування потрібно знати крім ключа і вектор ініціалізації, так ще який варіант AES використовується, з розміром блоку 128, 192 або 256 біт.

Нам дали підказку, що ключ і вектор ініціалізації (швидше за все) це вихід KDF.

Ви вже відчули кількість невідомих параметрів?

Тут починаються танці, тому що такі функції як PBKDF2 або scrypt можуть повертати рахуй майже будь-яку кількість байт, а HKDF повертає залежно від псевдопромінювальної функції.

А ще невідомі параметри складності обчислення для PBKDF2 і scrypt, також невідома сіль. І неясно який розмір ключа AES і який розмір вектора ініціалізації.

Благо з'ясувалося, що розмір цього вектора повинен збігатися з розміром блоку. Наприклад, для rijndael-128 (rijndael - це інша назва AES) - розмір блоку 128 біт або 16 байт. Тому в цьому варіанті розмір вектора ініціалізації повинен бути рівно 16 байт.

Також виявилося, що ключ не може бути більше, ніж 32 байти.

Розшифрування

Тепер можна приступати до самої розшифровки.

І зараз зрозуміло, що треба взяти результат роботи KDF, з них від 0 до 32 байти - це ключ, а далі, залежно від варіанту AES, вектор ініціалізації: 16, 24 або 32 байти.

Отже, розмір результату роботи KDF повинен бути не більше 64 байтів, щоб вмістити 32 байти ключа і 32 байти вектора ініціалізації.

Після перевірки на базових параметрах: порожня сіль, прості коефіцієнти (одинички), не вдалося отримати результат.

Тому довелося почати панікувати.

Паніка

Для PBKDF2 перебирався тільки один параметр - ітерації шифрування, але з порожньою сіллю (оскільки не ясно було звідки брати цю сіль).

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

Незважаючи на те, що ключ і вектор ініціалізації також підбиралися, ніяких результатів не з'явилося.

Почав коситися на просто hash-based message authentication code (HMAC) варіанти хешів, але скрізь говорилося, що це використовується в якості псевдопромінювальної функції, а не як KDF.

Але, перепробувавши всі варіанти з HMAC, так і не отримав результату.

Світло в кінці

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

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

І виявилося, що при використанні rijndael-128 (16 байт розмір вектора і блоку), хеш-функції sha256, результат якої 32 байти ділився на ключ 16 байт, і інші 16 байт на вектор ініціалізації, вийшло розшифрувати вихідне повідомлення. У якому просто пропонувалося послати лист на певну адресу.

Однією рукою друкую, іншою сльози витираю. Все виявилося набагато простіше, ніж бачилося спочатку.