Просмотр кода страницы Argon2

{{Карточка хеш-функции}}
'''Argon2''' — [[функция формирования ключа]], разработанная [[Бирюков, Алекс|Алексом Бирюковым]] ({{lang-en|Alex Biryukov}}), Даниэлем Дину ({{lang-en|Daniel Dinu}}) и Дмитрием Ховратовичем ({{lang-en|Dmitry Khovratovich}}) из [[Университет Люксембурга|Университета Люксембурга]] в 2015 году{{sfn|Password Hashing Competition}}.

Это современный простой алгоритм, направленный на высокую скорость заполнения памяти и эффективное использование нескольких вычислительных блоков{{sfn|Argon|2016|страницы = 293}}. Алгоритм выпущен под лицензией [[Creative Commons]].

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

В 2015 году Argon2 был объявлен победителем конкурса{{sfn|Password Hashing Competition}}. С того времени алгоритм претерпел 4 серьёзных изменения. Исправлены часть описаний алгоритмов генерации некоторых блоков и опечатки, добавлены рекомендуемые параметры{{sfn|Password Hashing Competition}}{{sfn|Argon|2016|страницы = 292}}.

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

Основные:
* Сообщение (пароль) <math>P</math>, длиной от <math>0</math> до <math>2^{32}-1</math>.
* [[Соль (криптография)|Соль]] S, длиной от <math>8</math> до <math>2^{32}-1</math>.
Дополнительные:
* Степень параллелизма <math>p</math>, любое целое число от <math>1</math> до <math>2^{24}-1</math> — количество потоков, на которое можно распараллелить алгоритм.
* Длина тэга <math>\tau</math>, длиной от <math>4</math> до <math>2^{32}-1</math>.
* Объём памяти <math>m  </math>, целое число килобайтов от <math>8p</math> до <math>2^{32}-1</math>
* Количество итераций <math>t  </math>{{sfn|Argon|2016|страницы = 294}}

== Версии алгоритма ==
Существуют две версии алгоритма:
* ''Argon2d'' — подходит для защиты [[Цифровая валюта|цифровой валюты]] и [[Информационная система|информационных систем]], не подверженных [[Атака по сторонним каналам|атакам по сторонним каналам]].
* ''Argon2i'' — обеспечивает высокую защиту от [[Компромисс времени и памяти|trade-off атак]], но работает медленнее версии d из-за нескольких проходов по памяти{{sfn|Password Hashing Competition}}.

== Описание ==
[[Файл:Схема Argon2.png|мини|504x504пкс|Схема работы '''Argon2''']]
Argon2 работает по следующему принципу:
# Производится хеширование пароля с использованием хеш-функции [[BLAKE (хеш-функция)|Blake2b]].
# Результат хеширования записывается в блоки памяти.
# Блоки памяти преобразуются с использованием функции сжатия <math>G</math>
# В результате работы алгоритма генерируется ключ ({{lang-en|Tag}}).

=== Заполнение блоков памяти ===
<math>B[0] = H(P,S)  </math>

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

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

Функции индексирования зависит от версии алгоритма Argon2:
* Argon2d — <math>\phi</math> зависит от предыдущего блока

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

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

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

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

<math>B^1[i][j]=G(B^1[i][j-1],B^1[i'][j']), 0\leq i < p  </math>

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

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

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

В итоге:

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

<math>Tag\leftarrow H'(B_{final}) </math> {{sfn|Argon|2016|страницы = 294—295}}

=== Нахождение опорного блока ===
* Argon2d: выбираются первые 32 бита для <math>J_1  </math> и следующие 32 бита для <math>J_2  </math> из блоков <math>B[i][j-1]  </math>
* Argon2i: <math>(J_1||J_2) = G^2(null_{1024},{ r||l||s||m'||t||y||i||null_{968} })  </math>, где <math>r  </math>- номер итерации, <math>l  </math> — номер линии, <math>y  </math> — задаёт версию (в данном случае единица)
Далее определяется индекс <math>l=J_2mod \ p  </math> строки, откуда берётся блок. При <math>r=0,s=0</math> за текущий номер линии принимается значение <math>l</math> . Затем определяется набор индексов <math>R</math> по 2 правилам:
# Если <math>l</math> совпадает с номером текущей строки, то в набор индексов добавляются все не записанные ранее блоки без <math>B[i][j-1]  </math>
# Если <math>l</math> не совпадает, то берутся блоки из всех сегментов линии и последних <math>S-1=3</math> частей.
В итоге, вычисляется номер блока из <math>r  </math>, который принимается за опорный:

<math>z = |R| - 1 - ( \frac{|R|*((J_1)^2/2^{32})}{2^{32}})   </math> {{sfn|Argon|2016|страницы =295}}

=== Функция H' ===
[[Файл:Argon2.png|мини|431x431пкс|Argon2]]
Blake2b — 64 битная версия функции [[BLAKE (хеш-функция)|BLAKE]], поэтому <math>H'</math> строится следующим образом:

<math>if \ \tau \ \leq \ 64</math>

<math>H'(X) = H_\tau(\tau||X).</math>

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

<math>r = \lceil\tau/32\rceil-2</math>

<math>V_1\longleftarrow H_{64}(\tau||X)</math>

<math>V_{r+1}\longleftarrow H_{\tau-32r}(V_r)</math>

<math>H'(X)=A_1||A_2||...A_r||V_{r+1}</math>

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

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

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

'''Атаки по времени:''' если пользователю необходимо адаптироваться к [[Атака по времени|атаке по времени]], то следует использовать версию Argon2i, так как она использует независимую память{{sfn|Argon|2016|страницы = 296—297}}.

== Атаки ==

=== Memory optimization attack ===
[[Дэн Боне]], Henry Corrigan-Gibbs и Stuart Schechter в своей работе показали уязвимость Argon2i версии 1.2. Для однопроходной версии их атака снижала расход памяти в 4 раза без замедления выполнения. Для многопроходной версии — в 2,72 раза. Позднее, в версии 1.3 операция перезаписи была заменена на [[Сложение по модулю 2|XOR]]{{sfn|Henry Corrigan-Gibbs|2016}}.

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

=== The ranking tradeoff attack ===
Данная атака является одной из самых эффективных для Argon2d. Она снижает время обработки в 1,33 раза. Для Argon2i при <math>t>2</math> коэффициент равен 3{{sfn|Argon|2016|страницы = 297}}.

=== Garbage collector attacks ===
Основным условием для представленной атаки является доступ злоумышленника к внутренней памяти целевой машины либо после прекращения схемы хеширования, либо в какой-то момент, когда сам пароль ещё присутствует в памяти. Благодаря перезаписи информации с помощью функции <math>G</math>, Argon2i и Argon2d устойчивы к данным атакам{{sfn|Overview|2015}}.

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

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

'''Argon2i''' больше подходит для frontend-серверов и [[Шифрование|шифрования]] жёсткого диска{{нет АИ|27|07|2022}}. Формирование ключа для шифрования на 2-GHz [[Центральный процессор|CPU]], используя 2 ядра и 6 GB оперативной памяти, с Argon2i (p=4) занимает 3 с, в то время как аутентификация на frontend-сервере, задействовав 2 ядра и 1 GB памяти с Argon2i (p=4), занимает 0,5 с{{sfn|Argon|2016|страницы = 300}}.

== Примечания ==
{{примечания|2}}

== Литература ==
* {{статья
 | автор        = Joel Alwen, Jeremiah Blocki
 | заглавие     = Efficiently Computing Data-Independent Memory-Hard Functions
 | издательство = Advances in Cryptology – CRYPTO 2016
 | год          = 2016
 | pages        = 241—271
 | isbn         = 978-3-662-53008-5
 | ref          = Alwen, Blocki
}}
* {{статья
 | автор        = 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
 | pages        = 220—248
 | isbn         = 978-3-662-53887-6
 | ref          = Henry Corrigan-Gibbs
}}
* {{cite web
 |url         = https://password-hashing.net/
 |title       = Password Hashing Competition
 |ref         = 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
 | ref          = Argon
}}
* {{статья
 | автор        = 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
 | pages        = 3—18
 | isbn         = 978-3-319-24192-0
 | ref          = Overview
}}

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

{{Хеш-алгоритмы}}
[[Категория:Криптография]]