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)$, определяемый предыдущим блоком $\varphi (i)=g(B[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

Дэн Боне, Henry Corrigan-Gibbs и Stuart Schechter в своей работе показали уязвимость Argon2i версии 1.2. Для однопроходной версии их атака снижала расход памяти в 4 раза без замедления выполнения. Для многопроходной версии — в 2,72 раза. Позднее, в версии 1.3 операция перезаписи была заменена на XORШаблон:Sfn.

AB16

Joel Alwen и Jeremiah Blocki в своих работах доказали, что их алгоритм атаки AB16 эффективен не только для Argon2i-A (из первой версии спецификации), но и для Argon2i-B (из последней версии 1.3). Они показали, что атака на Argon2 при $t=6$, используя 1 GB ОЗУ, снижает время вычисления в два раза. Для эффективной защиты необходимо задать больше 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 GB оперативной памяти, с 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
• https://www.cryptolux.org/index.php/Argon2
• https://github.com/khovratovich/Argon2 (ранняя версия функции)