Argon2

Argon2

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

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

История

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

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

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

Argon2 использует основные и дополнительные параметры для хеширования:

Основные:

• Сообщение (пароль) [math]\displaystyle{ P }[/math], длиной от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ 2^{32}-1 }[/math].
• Соль S, длиной от [math]\displaystyle{ 8 }[/math] до [math]\displaystyle{ 2^{32}-1 }[/math].

Дополнительные:

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

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

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

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

Описание

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

Argon2 работает по следующему принципу:

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

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

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

[math]\displaystyle{ B[j] = G(B[\phi_1(j)], B[\phi_2(j)], ... , B[\phi_k(j)]) }[/math], [math]\displaystyle{ j = 1...t }[/math], где

[math]\displaystyle{ \phi_k(j) }[/math] — функция индексирования, [math]\displaystyle{ B[] }[/math] — массив памяти, [math]\displaystyle{ G }[/math] — функция сжатия, [math]\displaystyle{ P }[/math] — сообщение(пароль), [math]\displaystyle{ H }[/math] — хеш-функция Blake2b.

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

• Argon2d — [math]\displaystyle{ \phi }[/math] зависит от предыдущего блока

• Argon2i — [math]\displaystyle{ \phi }[/math] значение, определяемое генератором случайных чисел.

В случае последовательного режима работы функция сжатия применяется [math]\displaystyle{ m }[/math] раз. Для версии Argon2d на [math]\displaystyle{ i }[/math]-м шаге на вход функции [math]\displaystyle{ G }[/math] подаётся блок с индексом [math]\displaystyle{ \phi (i) }[/math], определяемый предыдущим блоком [math]\displaystyle{ \phi (i) = g(B[i]) }[/math]. Для версии Argon2i берётся значение генератора случайных чисел ([math]\displaystyle{ G }[/math] в режиме счётчика).

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

[math]\displaystyle{ B^1[i][0]=H'( \ H_0 \ || \ \underset{4 bytes}{0} \ || \ \underset{4 bytes}{i} \ ), 0\leq i \lt p }[/math]

[math]\displaystyle{ B^1[i][1]=H'( \ H_0 \ || \ \underset{4 bytes}{1} \ || \ \underset{4 bytes}{i} \ ), 0\leq i \lt p }[/math]

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

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

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

[math]\displaystyle{ q={m' \over p} \ \ \ \ \ m' = \lfloor{m \over 4p} \rfloor 4p }[/math], где [math]\displaystyle{ m' }[/math] — количество блоков памяти размером 1024 байта, [math]\displaystyle{ H_0 }[/math] — хеш-функция, принимающая на вход 32-битное представление входных параметров, на выходе которой — 64-битное значение, [math]\displaystyle{ H' }[/math] — хеш-функция переменной длины от [math]\displaystyle{ H }[/math], [math]\displaystyle{ m }[/math] — объём памяти, [math]\displaystyle{ t }[/math] — количество итераций.

В итоге:

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

[math]\displaystyle{ Tag\leftarrow H'(B_{final}) }[/math]

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

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

Далее определяется индекс [math]\displaystyle{ l=J_2mod \ p }[/math] строки, откуда берётся блок. При [math]\displaystyle{ r=0,s=0 }[/math] за текущий номер линии принимается значение [math]\displaystyle{ l }[/math] . Затем определяется набор индексов [math]\displaystyle{ R }[/math] по 2 правилам:

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

В итоге, вычисляется номер блока из [math]\displaystyle{ r }[/math], который принимается за опорный:

[math]\displaystyle{ z = |R| - 1 - ( \frac{|R|*((J_1)^2/2^{32})}{2^{32}}) }[/math]

Функция H'

Argon2

Blake2b — 64 битная версия функции BLAKE, поэтому [math]\displaystyle{ H' }[/math] строится следующим образом:

[math]\displaystyle{ if \ \tau \ \leq \ 64 }[/math]

[math]\displaystyle{ H'(X) = H_\tau(\tau||X). }[/math]

При больших [math]\displaystyle{ \tau }[/math] выходное значение функции строится по первым 32 битам блоков — [math]\displaystyle{ A_i }[/math] и последнему блоку [math]\displaystyle{ V_i }[/math] :

[math]\displaystyle{ r = \lceil\tau/32\rceil-2 }[/math]

[math]\displaystyle{ V_1\longleftarrow H_{64}(\tau||X) }[/math]

[math]\displaystyle{ V_{r+1}\longleftarrow H_{\tau-32r}(V_r) }[/math]

[math]\displaystyle{ H'(X)=A_1||A_2||...A_r||V_{r+1} }[/math]

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

Основана на функции сжатия [math]\displaystyle{ P }[/math] Blake2b. На вход получает два 8192-битных блока и вырабатывает 1024-битный блок. Сначала два блока складываются ([math]\displaystyle{ A = X\oplus Y }[/math]), затем матрица [math]\displaystyle{ A_{8,8} }[/math] обрабатывается функцией [math]\displaystyle{ P }[/math] построчно ([math]\displaystyle{ A\longrightarrow Q }[/math]), затем получившаяся матрица обрабатывается по столбцам ([math]\displaystyle{ Q\longrightarrow Z }[/math]), и на выходе [math]\displaystyle{ G }[/math] выдаётся [math]\displaystyle{ Z\oplus A }[/math].

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

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

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

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

Атаки

Memory optimization attack

Дэн Боне, 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). Они показали, что атака на Argon2 при [math]\displaystyle{ t = 6 }[/math], используя 1 GB ОЗУ, снижает время вычисления в два раза. Для эффективной защиты необходимо задать больше 10 проходов. Но при рекомендуемом подходе выбора параметров алгоритма на практике часто может выбираться всего лишь 1 проход. Разработчики Argon2 утверждают, что, применяя атаку AB16 на Argon2i-B при [math]\displaystyle{ t\geq 4 }[/math], время уменьшается не более чем в 2 раза вплоть до использования 32 GB памяти и рекомендуют использовать число проходов, превышающее значение двоичного логарифма от размера^{[уточнить]} используемой памяти.

The ranking tradeoff attack

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

Garbage collector attacks

Основным условием для представленной атаки является доступ злоумышленника к внутренней памяти целевой машины либо после прекращения схемы хеширования, либо в какой-то момент, когда сам пароль ещё присутствует в памяти. Благодаря перезаписи информации с помощью функции [math]\displaystyle{ G }[/math], 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 GB оперативной памяти, с Argon2i (p=4) занимает 3 с, в то время как аутентификация на frontend-сервере, задействовав 2 ядра и 1 GB памяти с 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.
• 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 (ранняя версия функции)