Argon2

Argon2 — функция формирования ключа, разработанная Алексом Бирюковым (англ. Alex Biryukov), Даниэлем Дину (англ. Daniel Dinu) и Дмитрием Ховратовичем (англ. Dmitry Khovratovich) из Университета Люксембурга в 2015 году^[1].

Это современный простой алгоритм, направленный на высокую скорость заполнения памяти и эффективное использование нескольких вычислительных блоков^[2]. Алгоритм выпущен под лицензией Creative Commons.

История

В 2013 году был объявлен конкурс Password Hashing Competition^[en] о создании новой функции хеширования паролей. К новому алгоритму предъявлялись требования по объёму используемой памяти, количеству проходов по блокам памяти и по устойчивости к криптоанализу.

В 2015 году Argon2 был объявлен победителем конкурса^[1]. С того времени алгоритм претерпел 4 серьёзных изменения. Исправлены часть описаний алгоритмов генерации некоторых блоков и опечатки, добавлены рекомендуемые параметры^[1][3].

Входные данные

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}$^[4]

Версии алгоритма

Существуют две версии алгоритма:

• Argon2d — подходит для защиты цифровой валюты и информационных систем, не подверженных атакам по сторонним каналам.
• Argon2i — обеспечивает высокую защиту от trade-off атак, но работает медленнее версии d из-за нескольких проходов по памяти^[1].

Описание

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

Нахождение опорного блока

• 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}}})}$ ^[6]

Функция H'

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}$), и на выходе ${\displaystyle G}$ выдаётся ${\displaystyle Z\oplus A}$^[6].

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

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

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

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

Атаки

Memory optimization attack

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

AB16

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

The ranking tradeoff attack

Данная атака является одной из самых эффективных для Argon2d. Она снижает время обработки в 1,33 раза. Для Argon2i при ${\displaystyle t>2}$ коэффициент равен 3^[10].

Garbage collector attacks

Основным условием для представленной атаки является доступ злоумышленника к внутренней памяти целевой машины либо после прекращения схемы хеширования, либо в какой-то момент, когда сам пароль ещё присутствует в памяти. Благодаря перезаписи информации с помощью функции ${\displaystyle G}$, Argon2i и Argon2d устойчивы к данным атакам^[11].

Применение

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

Argon2d предназначен для систем, где злоумышленник не получает регулярного доступа к системной памяти или процессору. Например, для backend-серверов и криптомайнеров^{[источник не указан 467 дней]}. При использовании одного ядра на 2-GHz CPU и 250 MB оперативной памяти с Argon2d (p=2) криптомайнинг занимает 0,1 с, а при применении 4 ядер и 4 GB памяти (p=8) аутентификация на backend сервере проходит за 0,5 с^{[источник не указан 467 дней]}.

Argon2i больше подходит для frontend-серверов и шифрования жёсткого диска^{[источник не указан 467 дней]}. Формирование ключа для шифрования на 2-GHz CPU, используя 2 ядра и 6 GB оперативной памяти, с Argon2i (p=4) занимает 3 с, в то время как аутентификация на frontend-сервере, задействовав 2 ядра и 1 GB памяти с Argon2i (p=4), занимает 0,5 с^[12].

Примечания

Литература

• 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.
• 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: 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. — P. 3—18. — ISBN 978-3-319-24192-0.

Ссылки

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

Эта страница в последний раз была отредактирована 27 июля 2022 в 20:23.