Argon2

Argon2 — функція формування ключа, розроблена (англ. Alex Biryukov), Даніелем Діну (англ. Daniel Dinu) і Дмитром Ховратовичем (англ. Dmitry Khovratovich) з в 2015 році.

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

Історія

У 2013 році був оголошений конкурс ^[en] для створення нової функції хешування паролів. До нового алгоритму висувалися вимоги щодо обсягу використовуваної пам'яті, кількості проходів по блоках пам'яті і по стійкості до криптоаналізу.

У 2015 році Argon2 був оголошений переможцем конкурсу. З того часу алгоритм зазнав 4 серйозні зміни. Виправлені частина описів алгоритмів генерації деяких блоків і помилки, додані рекомендовані параметри.

Вхідні дані

Argon2 використовує основні та додаткові параметри для хешування:

Основні:

• Повідомлення (пароль) ${\displaystyle P}$, довжиною від ${\displaystyle 0}$ до ${\displaystyle 2^{32}-1}$.
• Сіль S, довжиною від ${\displaystyle 8}$ до ${\displaystyle 2^{32}-1}$.

Додаткові:

• Ступінь паралелізму ${\displaystyle p}$ будь-яке ціле число від ${\displaystyle 1}$ до ${\displaystyle 2^{24}-1}$ — кількість потоків, на яку можна розпаралелити алгоритм.
• Довжина тегу ${\displaystyle \tau }$, довжиною від ${\displaystyle 4}$ до ${\displaystyle 2^{32}-1}$.
• Об'єм пам'яті ${\displaystyle m}$, ціле число кілобайтів від  ${\displaystyle 8p}$ до ${\displaystyle 2^{32}-1}$.
• Кількість ітерацій ${\displaystyle t}$

Версії алгоритму

Існують дві версії алгоритму:

• Argon2d — підходить для захисту цифрової валюти та інформаційних систем, що не піддаються атакам по стороннім каналам.
• Argon2i — забезпечує високий захист від trade-off атак, але працює повільніше версії d через кілька проходів по пам'яті.

Опис

Схема роботи Argon2

Argon2 працює за наступним принципом:

1. Проводиться хешування пароля з використанням хеш-функції Blake2b.
2. Результат хешування записується в блоки пам'яті.
3. Блоки пам'яті перетворюються з використанням функції стиснення ${\displaystyle G}$.
4. В результаті роботи алгоритму генерується ключ (англ. Tag).

Заповнення блоків пам'яті

${\displaystyle B[0]=H(P,S)}$

${\displaystyle B[j]=G(B[\phi _{1}(j)],B[\phi _{2}(j)],...,B[\phi _{k}(j)])}$, ${\displaystyle j=1...t}$,де

${\displaystyle \phi _{k}(j)}$ — функція індексування, ${\displaystyle B[]}$ — масив пам'яті, ${\displaystyle G}$ — функція стиснення, ${\displaystyle P}$ — повідомлення(пароль), ${\displaystyle H}$ — хеш-функція Blake2b.

Функції індексування залежить від версії алгоритму Argon2:

• Argon2d — ${\displaystyle \phi }$ залежить від попереднього блоку

• Argon2i — ${\displaystyle \phi }$ значення, яке визначається генератором випадкових чисел.

У разі послідовного режиму роботи функція стиснення застосовується ${\displaystyle m}$ раз. Для версії Argon2d на ${\displaystyle i}$-му кроці на вхід функції ${\displaystyle G}$ подається блок з індексом ${\displaystyle \phi (i)}$, обумовлений попереднім блоком м. Для версії Argon2i береться значення генератора випадкових чисел (${\displaystyle G}$ у режимі лічильника).

У разі паралельного режиму (алгоритм розпаралелюється на ${\displaystyle p}$ тредів) дані розподіляться по блокам матриці ${\displaystyle B[i][j]}$, де перші блоки — результат хешування вхідних даних, а наступні задаються функцією стиснення ${\displaystyle G}$ за попередніми блоками і опорного блоку ${\displaystyle B^{1}[i'][j']}$:

${\displaystyle B^{1}[i][0]=H'(\ H_{0}\ ||\ {\underset {4bytes}{0}}\ ||\ {\underset {4bytes}{i}}\ ),0\leq i<p}$

${\displaystyle B^{1}[i][1]=H'(\ H_{0}\ ||\ {\underset {4bytes}{1}}\ ||\ {\underset {4bytes}{i}}\ ),0\leq i<p}$

${\displaystyle B^{1}[i][j]=G(B^{1}[i][j-1],B^{1}[i'][j']),0\leq i<p}$

${\displaystyle B^{t}[i][0]=G(B^{t-1}[i][q-1],B^{1}[i'][j'])\oplus B^{t-1}[i][0]}$

${\displaystyle B^{t}[i][j]=G(B^{t}[i][j-1],B^{1}[i'][j'])\oplus B^{t-1}[i][j]}$

${\displaystyle q={m' \over p}\ \ \ \ \ m'=\lfloor {m \over 4p}\rfloor 4p}$, де ${\displaystyle m'}$ — кількість блоків пам'яті розміром 1024 байта, ${\displaystyle H_{0}}$ — хеш-функція, що приймає на вхід 32-бітове представлення вхідних параметрів на виході якої — 64-бітове значення, ${\displaystyle H'}$ — хеш-функція змінної довжини від ${\displaystyle H}$, ${\displaystyle m}$ — обсяг пам'яті, ${\displaystyle t}$ — кількість ітерацій.

В результаті:

${\displaystyle B_{final}=B^{T}[0][q-1]\oplus B^{T}[1][q-1]\oplus ...\oplus B^{T}[p-1][q-1]}$

${\displaystyle Tag\leftarrow H'(B_{final})}$

Знаходження опорного блоку

• Argon2d: вибираються перші 32 біта ${\displaystyle J_{1}}$ і наступні 32 біта ${\displaystyle J_{2}}$з блоків ${\displaystyle B[i][j-1]}$
• Argon2i: ${\displaystyle (J_{1}||J_{2})=G^{2}(null_{1024},{r||l||s||m'||t||y||i||null_{968}})}$, где ${\displaystyle r}$- номер ітерації, ${\displaystyle l}$ — номер линії, ${\displaystyle y}$ — визначає версію (в даному випадку одиниця)

Далі визначається індекс ${\displaystyle l=J_{2}mod\ p}$ рядки, звідки береться блок. При ${\displaystyle r=0,s=0}$ за поточний номер лінії приймається значення ${\displaystyle l}$ . Потім визначається набір індексів ${\displaystyle R}$ по 2 правилами:

1. Якщо ${\displaystyle l}$ збігається з номером поточного рядка, то в набір індексів додаються не всі записані раніше блоки без ${\displaystyle B[i][j-1]}$
2. Якщо ${\displaystyle l}$ не збігається, то беруться блоки з усіх сегментів лінії і останніх ${\displaystyle S-1=3}$ частин.

У підсумку, обчислюється номер блоку з ${\displaystyle r}$, який приймається за опорний:

${\displaystyle z=|R|-1-({\frac {|R|*((J_{1})^{2}/2^{32})}{2^{32}}})}$

Функція H'

Argon2

Blake2b — 64 бітна версія функції BLAKE, тому ${\displaystyle H'}$ будується наступним чином:

${\displaystyle if\ \tau \ \leq \ 64}$

${\displaystyle H'(X)=H_{\tau }(\tau ||X).}$

При великих ${\displaystyle \tau }$ вихідне значення функції будується за першим 32 бітам блоків — ${\displaystyle A_{i}}$ і останнього блоку ${\displaystyle V_{i}}$ :

${\displaystyle r=\lceil \tau /32\rceil -2}$

${\displaystyle V_{1}\longleftarrow H_{64}(\tau ||X)}$

${\displaystyle V_{r+1}\longleftarrow H_{\tau -32r}(V_{r})}$

${\displaystyle H'(X)=A_{1}||A_{2}||...A_{r}||V_{r+1}}$

Функція стиснення G

Заснована на функції стиснення ${\displaystyle P}$ Blake2b. На вхід отримує два 8192-бітних блоки і виробляє 1024-бітний блок. Спочатку два блоки складаються (${\displaystyle A=X\oplus Y}$), потім матриця ${\displaystyle A_{8,8}}$ обробляється функцією ${\displaystyle P}$ порядково (${\displaystyle A\longrightarrow Q}$), потім отримана матриця обробляється за стовпцями (${\displaystyle Q\longrightarrow Z}$), і на виході G видається ${\displaystyle Z\oplus A}$.

Криптоаналіз

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

Атака знаходження прообразу: нехай зловмисник підібрав ${\displaystyle m}$ таке, що ${\displaystyle G(m)=h}$, тоді для продовження даної атаки він повинен підібрати прообраз ${\displaystyle n}$: ${\displaystyle H(n)=m}$, що неможливо. Таке ж міркування підходить для атаки знаходження другого прообразу.

Атаки по часу: якщо користувачеві необхідно адаптуватися до атаки по часу, то слід використовувати версію Argon2i, так як вона використовує незалежну пам'ять.

Атаки

Memory optimization attack

Ден Бонех, Генрі Корріган-Гіббс та Стюарт Шехтер у своїй роботі показали уразливість Argon2i версії 1.2. Для однопрохідної версії їх атака знижувала витрати пам'яті в 4 рази без уповільнення використання. Для багатопрохідної версії — в 2,72 рази. Пізніше, у версії 1.3 операція перезапису була замінена на XOR.

AB16

Джоел Елвен та Джеремая Блокі у своїх роботах довели, що їх алгоритм атаки AB16 ефективний не тільки для Argon2i-A (з першої версії специфікації), але і для Argon2i-B (з останньої версії 1.3). Вони показали, що атака на Argon2 при ${\displaystyle t=6}$, використовуючи 1 гігабайт оперативної пам'яті, знижує час обчислення вдвічі.

Для ефективного захисту необхідно поставити більше 10 проходів. Але при рекомендованому підході вибору параметрів алгоритму на практиці часто може вибиратися всього лише 1 прохід. Розробники Argon2 стверджують, що, застосовуючи атаку AB16 на Argon2i-B при ${\displaystyle t\geq 4}$, час зменшується не більше ніж в 2 рази аж до використання 32 GB пам'яті і рекомендують використовувати число проходів, що перевищує значення двійкового логарифма від використовуваної пам'яті.

The ranking tradeoff attack

Ця атака є однією з найбільш ефективних для Argon2d. Вона знижує час обробки в 1,33 рази. Для Argon2i при ${\displaystyle t>2}$ коефіцієнт дорівнює 3 .

Garbage Collector Attacks

Основною умовою для представленої атаки є доступ зловмисника до внутрішньої пам'яті цільової машини або після припинення схеми хешування, або в якийсь момент, коли сам пароль ще присутній в пам'яті. Завдяки перезапису інформації з допомогою функції ${\displaystyle G}$, Argon2i і Argon2d стійкі до даних атак.

Застосування

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 сек.

Примітки

1. Password Hashing Competition.
2. Argon, 2016.
3. Argon, 2016, с. 294—295.
4. Argon, 2016, с. 295.
5. Henry Corrigan-Gibbs, 2016.
6. Alwen, Blocki, 2016.
7. Overview, 2015.

Література

• Joel Alwen, Jeremiah Blocki. Efficiently Computing Data-Independent Memory-Hard Functions. — Advances in Cryptology – CRYPTO 2016, 2016. — С. 241—271. — .
• 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. — .
• . Архів оригіналу за 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. — .

Посилання

• 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.] (рання версія функції)