Argon2

Argon2 — функція формування ключа, розроблена Алексом Бірюковим (Шаблон:Lang-en), Даніелем Діну (Шаблон:Lang-en) і Дмитром Ховратовичем (Шаблон:Lang-en) з Університету Люксембургу в 2015 роціШаблон:Sfn.

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

Історія

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

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

Вхідні дані

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

Основні:

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

Додаткові:

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

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

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

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

Опис

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

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

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

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

$B[0]=H(P,S)$

$B[j]=G(B[{\varphi }_1(j)],B[{\varphi }_2(j)],...,B[{\varphi }_k(j)])$, $j=1...t$,де

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

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

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

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

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

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

$B^1[i][0]=H^{\prime }(H_0||\underset{4bytes}{0}||\underset{4bytes}{i}),0\le i<p$

$B^1[i][1]=H^{\prime }(H_0||\underset{4bytes}{1}||\underset{4bytes}{i}),0\le i<p$

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

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

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

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

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

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

$Tag\leftarrow H^{\prime }(B_{final})$ Шаблон:Sfn

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

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

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

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

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

$z=|R|-1-(\frac{|R|*((J_1{)}^2/2^{32})}{2^{32}})$ Шаблон:Sfn

Функція H'

Argon2

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

$if\tau \le 64$

$H^{\prime }(X)=H_{\tau }(\tau ||X).$

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

$r=\lceil \tau /32\rceil -2$

$V_1⟵H_{64}(\tau ||X)$

$V_{r+1}⟵H_{\tau -32r}(V_r)$

$H^{\prime }(X)=A_1||A_2||...A_r||V_{r+1}$

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

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

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

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

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

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

Атаки

Memory optimization attack

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

AB16

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

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

The ranking tradeoff attack

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

Garbage Collector Attacks

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

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

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 сек.Шаблон:Sfn

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Cite web
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• https://github.com/P-H-C/phc-winner-argon2 Шаблон:Webarchive
• https://www.cryptolux.org/index.php/Argon2 Шаблон:Webarchive
• https://github.com/khovratovich/Argon2 Шаблон:Webarchive (рання версія функції)