Argon2
Argon2 — функція формування ключа, розроблена Алексом Бірюковим (англ. Alex Biryukov), Даніелем Діну (англ. Daniel Dinu) і Дмитром Ховратовичем (англ. Dmitry Khovratovich) з Університету Люксембургу в 2015 році[1].
Це сучасний простий алгоритм, спрямований на високу швидкість заповнення пам'яті та ефективне використання декількох обчислювальних блоків[2]. Алгоритм випущений під ліцензією Creative Commons.
Історія
У 2013 році був оголошений конкурс Password Hashing Competition[en] для створення нової функції хешування паролів. До нового алгоритму висувалися вимоги щодо обсягу використовуваної пам'яті, кількості проходів по блоках пам'яті і по стійкості до криптоаналізу.
У 2015 році Argon2 був оголошений переможцем конкурсу[1]. З того часу алгоритм зазнав 4 серйозні зміни. Виправлені частина описів алгоритмів генерації деяких блоків і помилки, додані рекомендовані параметри[1][2].
Вхідні дані
Argon2 використовує основні та додаткові параметри для хешування:
Основні:
- Повідомлення (пароль) , довжиною від до .
- Сіль S, довжиною від до .
Додаткові:
- Ступінь паралелізму будь-яке ціле число від до — кількість потоків, на яку можна розпаралелити алгоритм.
- Довжина тегу , довжиною від до .
- Об'єм пам'яті , ціле число кілобайтів від до .
- Кількість ітерацій [2]
Версії алгоритму
Існують дві версії алгоритму:
- Argon2d — підходить для захисту цифрової валюти та інформаційних систем, що не піддаються атакам по стороннім каналам.
- Argon2i — забезпечує високий захист від trade-off атак, але працює повільніше версії d через кілька проходів по пам'яті[1].
Опис
![](http://upload.wikimedia.org/wikipedia/commons/4/49/%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_Argon2.png)
Argon2 працює за наступним принципом:
- Проводиться хешування пароля з використанням хеш-функції Blake2b.
- Результат хешування записується в блоки пам'яті.
- Блоки пам'яті перетворюються з використанням функції стиснення .
- В результаті роботи алгоритму генерується ключ (англ. Tag).
Заповнення блоків пам'яті
, ,де
— функція індексування, — масив пам'яті, — функція стиснення, — повідомлення(пароль), — хеш-функція Blake2b.
Функції індексування залежить від версії алгоритму Argon2:
- Argon2d — залежить від попереднього блоку
- Argon2i — значення, яке визначається генератором випадкових чисел.
У разі послідовного режиму роботи функція стиснення застосовується раз. Для версії Argon2d на -му кроці на вхід функції подається блок з індексом , обумовлений попереднім блоком м. Для версії Argon2i береться значення генератора випадкових чисел ( у режимі лічильника).
У разі паралельного режиму (алгоритм розпаралелюється на тредів) дані розподіляться по блокам матриці , де перші блоки — результат хешування вхідних даних, а наступні задаються функцією стиснення за попередніми блоками і опорного блоку :
, де — кількість блоків пам'яті розміром 1024 байта, — хеш-функція, що приймає на вхід 32-бітове представлення вхідних параметрів на виході якої — 64-бітове значення, — хеш-функція змінної довжини від , — обсяг пам'яті, — кількість ітерацій.
В результаті:
[3]
Знаходження опорного блоку
- Argon2d: вибираються перші 32 біта і наступні 32 біта з блоків
- Argon2i: , где - номер ітерації, — номер линії, — визначає версію (в даному випадку одиниця)
Далі визначається індекс рядки, звідки береться блок. При за поточний номер лінії приймається значення . Потім визначається набір індексів по 2 правилами:
- Якщо збігається з номером поточного рядка, то в набір індексів додаються не всі записані раніше блоки без
- Якщо не збігається, то беруться блоки з усіх сегментів лінії і останніх частин.
У підсумку, обчислюється номер блоку з , який приймається за опорний:
[4]
Функція H'
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/76/Argon2.png/431px-Argon2.png)
Blake2b — 64 бітна версія функції BLAKE, тому будується наступним чином:
При великих вихідне значення функції будується за першим 32 бітам блоків — і останнього блоку :
Функція стиснення G
Заснована на функції стиснення Blake2b. На вхід отримує два 8192-бітних блоки і виробляє 1024-бітний блок. Спочатку два блоки складаються (), потім матриця обробляється функцією порядково (), потім отримана матриця обробляється за стовпцями (), і на виході G видається [4].
Криптоаналіз
Захист від колізій: Сама функція Blake2b вважається криптографічно безпечною. Також, посилаючись на правила індексування, автори алгоритму довели відсутність колізій всередині блоків даних і низьку ймовірність їхньої появи при застосуванні функції стиснення.
Атака знаходження прообразу: нехай зловмисник підібрав таке, що , тоді для продовження даної атаки він повинен підібрати прообраз : , що неможливо. Таке ж міркування підходить для атаки знаходження другого прообразу.
Атаки по часу: якщо користувачеві необхідно адаптуватися до атаки по часу, то слід використовувати версію Argon2i, так як вона використовує незалежну пам'ять[2].
Атаки
Memory optimization attack
Ден Бонех, Генрі Корріган-Гіббс та Стюарт Шехтер у своїй роботі показали уразливість Argon2i версії 1.2. Для однопрохідної версії їх атака знижувала витрати пам'яті в 4 рази без уповільнення використання. Для багатопрохідної версії — в 2,72 рази. Пізніше, у версії 1.3 операція перезапису була замінена на XOR[5].
AB16
Джоел Елвен та Джеремая Блокі у своїх роботах довели, що їх алгоритм атаки AB16 ефективний не тільки для Argon2i-A (з першої версії специфікації), але і для Argon2i-B (з останньої версії 1.3). Вони показали, що атака на Argon2 при , використовуючи 1 гігабайт оперативної пам'яті, знижує час обчислення вдвічі.
Для ефективного захисту необхідно поставити більше 10 проходів. Але при рекомендованому підході вибору параметрів алгоритму на практиці часто може вибиратися всього лише 1 прохід. Розробники Argon2 стверджують, що, застосовуючи атаку AB16 на Argon2i-B при , час зменшується не більше ніж в 2 рази аж до використання 32 GB пам'яті і рекомендують використовувати число проходів, що перевищує значення двійкового логарифма від використовуваної пам'яті[6].
The ranking tradeoff attack
Ця атака є однією з найбільш ефективних для Argon2d. Вона знижує час обробки в 1,33 рази. Для Argon2i при коефіцієнт дорівнює 3 [2].
Garbage Collector Attacks
Основною умовою для представленої атаки є доступ зловмисника до внутрішньої пам'яті цільової машини або після припинення схеми хешування, або в якийсь момент, коли сам пароль ще присутній в пам'яті. Завдяки перезапису інформації з допомогою функції , Argon2i і Argon2d стійкі до даних атак[7].
Застосування
Argon2 оптимізований під x86-архітектуру і може бути реалізований на Linux, OS X, Windows.
Argon2d призначений для систем, де зловмисник не отримує регулярного доступу до системної пам'яті або процесора. Наприклад, для backend-серверів і криптомайнерів. При використанні одного ядра на 2-Ghz CPU і 250 Mb оперативної пам'яті з Argon2d (p=2) криптомайнінг займає 0,1 сек., а при застосуванні 4 ядер і 4 Gb пам'яті (p=8) автентифікація на backend сервері проходить за 0.5 сек.
Argon2i більше підходить для frontend-серверів і шифрування жорсткого диска. Формування ключа для шифрування на 2-Ghz CPU, використовуючи 2 ядра і 6 Гб оперативної пам'яті, з Argon2i (p=4) займає 3 сек., у той час як аутентифікація на frontend-сервері, задіявши 2 ядра і 1 Gb пам'яті з Argon2i (p=4), займає 0,5 сек.[2]
Примітки
- ↑ а б в г Password Hashing Competition.
- ↑ а б в г д е Argon, 2016.
- ↑ Argon, 2016, с. 294—295.
- ↑ а б Argon, 2016, с. 295.
- ↑ Henry Corrigan-Gibbs, 2016.
- ↑ Alwen, Blocki, 2016.
- ↑ Overview, 2015.
Література
- Joel Alwen, Jeremiah Blocki. Efficiently Computing Data-Independent Memory-Hard Functions. — Advances in Cryptology – CRYPTO 2016, 2016. — С. 241—271. — ISBN 978-3-662-53008-5.
- Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. — Advances in Cryptology – ASIACRYPT 2016, 2016. — С. 220—248. — ISBN 978-3-662-53887-6.
- Password Hashing Competition. Архів оригіналу за 7 квітня 2019. Процитовано 16 квітня 2018.
- Alex Biryukov, Daniel Dinu, Dmitry Khovratovich. Argon2: new generation of memory-hard functions for password hashing and other applications. — European Symposium on Security and Privacy, 2016.
- Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Overview of the Candidates for the Password Hashing Competition and their resistance against Garbage-Collector Attacks. — Technology and Practice of Passwords, 2015. — С. 3—18. — ISBN 978-3-319-24192-0.
Посилання
- https://github.com/P-H-C/phc-winner-argon2 [Архівовано 2 квітня 2019 у Wayback Machine.]
- https://www.cryptolux.org/index.php/Argon2 [Архівовано 31 березня 2019 у Wayback Machine.]
- https://github.com/khovratovich/Argon2 [Архівовано 11 червня 2018 у Wayback Machine.] (рання версія функції)
|