Argon2

Argon2 - функция формирования ключа, в разработке которой принимали участие Алекс Бирюков (Alex Biryukov), Даниэль Дину (Daniel Dinu) и Дмитрий Ховратович (Dmitry Khovratovich) из университета Люксембурга в 2015 году. Это рациональный и простой алгоритм, направленный на самую высокую скорость заполнения памяти и эффективное использование нескольких вычислительных блоков. Существуют две версии: Argon2i и Argon2d. Argon2d подходит для защиты цифровой валюты и информационных систем, не подверженных атакам по сторонним каналам. Argon2i обеспечивает высокую защиту от trade-off атак, но работает медленнее версии d из-за нескольких проходов по памяти.

История

Алгоритм функции выпущен под лицензией Creative Commons. Argon2 является победителем конкурса Password Hashing Competition в 2015 году. С того времени алгоритм претерпел 4 серьезных изменения. Исправлены часть описаний алгоритмов генерации некоторых блоков и опечатки, добавлены рекомендуемые параметры. Наиболее удачными атаками на Argon2 являются the low-storage attack и the ranking tradeoff attack.

Описание

Используется следующий режим работы:

Заполнение массива памяти

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

$for\ j\ from\ 1\ to\ t$

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

$\phi _{k}(j)$ - функция индексирования

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

$B[]$ - массив памяти

$G$ - функция сжатия

$P$ - сообщение(пароль)

$H$ - хэш-функция Blake2b

Функции индексирования различают по версии Argon2:

• Argon2d - $\phi$ зависит от предыдущего блока

• Argon2i - $\phi$ фиксированное значение

При непараллельном режиме функция $G$ повторяется $m$ раз . На шаге $i$ берется блок с индексом $\phi (i)$ определяемый предыдущим блоком при Argon2d: $\phi (i)=g(B[i])$ или берется значение генератора случайных чисел($G$ в режиме счетчика) при Argon2i.

$g$ - функция берет часть значений блока ,принимая результат деления по модулю $i-1$

Если распараллелить алгоритм на $p$ тредов, то данные распределятся по блокам матрицы $B[i][j]$, где

первые блоки - результат хэширования входных данных, а следующие задаются функцией сжатия по предыдущим блокам и опорному блоку:

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

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

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

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

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

$q={m' \over p}\ \ \ \ \ m'=\lfloor {m \over 4p}\rfloor 4p$

$m'$ - количество блоков памяти размером 1024 байта

$H_{0}$ - хэш-функция принимающая на вход 32 битное представление входных параметров, на выходе которой 64 битное значение

$H'$ - хэш-функция переменной длины от $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'(B_{final})$

Нахождение опорного блока $B^{1}[i'][j']$

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

Считаем $l=J_{2}modp$ строки , откуда берется блок. При $r=0,s=0$, за текущий номер полосы принимается значение $l$ . Затем определяем набор индексов $R$ по 2 правилам:

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

Вычисляем номер блока из $R$ который примем за опорный:

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

Blake2b - 64 битная версия функции BLAKE, поэтому $H'$ строится так:

$if\ \tau \ \leq \ 64$

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

при больших $\tau$ выходное значение функции строится по первым 32 битам блоков - $A_{i}$ и последнему блоку $V_{i}$ :

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

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

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

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

Функция сжатия G

Основана на функции сжатия $P$ Blake2b. На вход получает два 8192 битных блока и вырабатывает 1024 битный блок. Сначала два блока складываются ($R=X\oplus Y$),

затем матрица R 8*8 обрабатывается функцией $P$ построчно ($R\longrightarrow Q$), затем получившаяся матрица по столбцам($Q\longrightarrow Z$), и на выходе G выдается $Z\oplus R$.

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

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

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

Защита от таблиц поиска: благодаря использованию соли в данном алгоритме, для атаки TMTO требуется предварительное вычисление всевозможных вычислений Nonce. При размере соли в 16 байт придется вычислять 2128 матриц значений, каждая из которых занимает гигабайты памяти. Также, изменяя входные параметры алгоритма можно уменьшить вероятность успеха злоумышленников, ограничив внутреннее распараллеливание.

CPU атаки: Argon2 устойчив к атакам злоумышленников с ASIC, так как оптимизирован под x86 архитектуру. Эффективность атак злоумышленников с CPU ограничена RAM доступной для устройства и количеством ядер возможных для x86 архитектуры.

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

Использование хэш-функции Blake2b также исключает уязвимости для других атак.

Рекомендуемые параметры

Исходя из области применения необходимо выбрать подходящую версию алгоритма(d или i). Далее задать максимальное число потоков, памяти и времени ,возможное для каждого вызова функции. Длины в 128 бит для соли и тэга хватает для любых применений. Затем подобрать максимальное число проходов $t$, при котором не превышается заданное время инициализации.

Атаки

Memory optimization attack

Dan Boneh, Henry Corrigan-Gibbs, и Stuart Schechter в своей работе показали уязвимость Argon2i версии 1.2. Для однопроходной версии их атака выиграла в 4 раза по памяти без штрафного времени. Для многопроходной версии выигрыш составлял 2.72. Позднее в версии 1.3 операцию перезаписи заменили на XOR.

AB16

Joel Alwen и Jeremiah Blocki в своих работах доказали, что их алгоритм атаки AB16 эффективен не только для Argon2i-A(из первой версии спецификации), но и для Argon2i-B(из последней версии 1.3). Они показали , что для $t=6$ над 1GB памяти атака снижает затраты в два раза. Для эффективной защиты необходимо задать больше 10 проходов. Но при рекомендуемом подходе выбора параметров алгоритма на практике часто может выбираться все лишь 1 проход. Разработчики Argon2 утверждают, что коэффициент уменьшения атаки AB16 на Argon2i-B при $t\geq 4$ не превышает 2 вплоть до использования 32GB памяти и рекомендуют использовать число проходов превышающее значение двоичного логарифма от используемой памяти.

The ranking tradeoff attack

Данная атака лучшая для Argon2d. Ее коэффициент уменьшения времени равен 1.33. Для Argon2i при $t>2$ коэффициент по времени равен 3.

Применение

Argon2 оптимизирован под x86 архитектуру и может быть реализована на Linux,OS X,Windows.

Argon2d предназначен для систем, где злоумышленник не получает регулярный доступ к системной памяти или процессору. Например, для backend серверов и криптомайнеров. При использовании одного ядра на 2Ghz CPU и 250Mb оперативной памяти с Argon2d (p=2) криптомайнинг занимает 0.1 сек. А при применении 4 ядер и 4 Gb памяти (p=8) аутентификация на backend сервере проходит за 0.5 сек.

Argon2i больше подходит для frontend серверов и шифрования жесткого диска. Формирование ключа для шифрования на 2Ghz CPU, используя 2 ядра и 6Gb оперативной памяти с Argon2i (p=4) занимает 3 сек. В то время как аутентификация на frontend сервере, задействовав 2 ядра и 1Gb памяти с Argon2i (p=4), занимает 0.5 сек.

Литература

• Joel Alwen, Jeremiah Blocki. Efficiently Computing Data-Independent Memory-Hard Functions. — Advances in Cryptology – CRYPTO 2016, 2016. — P. 241-271. — ISBN 978-3-662-53008-5.
• Jos Wetzels. Open Sesame The Password Hashing Competition and Argon2. — 2016.
• 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. — P. 220-248. — ISBN 978-3-662-53887-6.
• Password Hashing Competition  (неопр.).
• Alex Biryukov, Daniel Dinu, Dmitry Khovratovich. Argon2: the memory-hard function for password hashing and other applications. — 2016.