Перегляд вихідного коду сторінки Argon2

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

Це сучасний простий алгоритм, спрямований на високу швидкість заповнення пам'яті та ефективне використання декількох обчислювальних блоків{{Sfn|Argon|2016}}. Алгоритм випущений під ліцензією [[Creative Commons]].

== Історія ==
У 2013 році був оголошений конкурс {{iw|Password Hashing Competition}} для створення нової функції [[Хеш-функція|хешування]] паролів. До нового алгоритму висувалися вимоги щодо обсягу використовуваної пам'яті, кількості проходів по блоках пам'яті і по стійкості до криптоаналізу.

У 2015 році Argon2 був оголошений переможцем конкурсу{{Sfn|Password Hashing Competition}}. З того часу алгоритм зазнав 4 серйозні зміни. Виправлені частина описів алгоритмів генерації деяких блоків і помилки, додані рекомендовані параметри{{Sfn|Password Hashing Competition}}{{Sfn|Argon|2016}}.

== Вхідні дані ==
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}}

== Версії алгоритму ==
Існують дві версії алгоритму:

* ''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>, обумовлений попереднім блоком м. Для версії 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>), і на виході G видається <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}}.

== Атаки ==

=== Memory optimization attack ===
[[Ден Бонех]], Генрі Корріган-Гіббс та Стюарт Шехтер у своїй роботі показали уразливість Argon2i версії 1.2. Для однопрохідної версії їх атака знижувала витрати пам'яті в 4 рази без уповільнення використання. Для багатопрохідної версії — в 2,72 рази. Пізніше, у версії 1.3 операція перезапису була замінена на [[Виключна диз'юнкція|XOR]]{{Sfn|Henry Corrigan-Gibbs|2016}}.

=== AB16 ===
Джоел Елвен та Джеремая Блокі у своїх роботах довели, що їх алгоритм атаки AB16 ефективний не тільки для Argon2i-A (з першої версії специфікації), але і для Argon2i-B (з останньої версії 1.3). Вони показали, що атака на Argon2 при <math>t =  6</math>, використовуючи 1 гігабайт оперативної пам'яті, знижує час обчислення вдвічі. 

Для ефективного захисту необхідно поставити більше 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}}.

=== Garbage Collector Attacks ===
Основною умовою для представленої атаки є доступ зловмисника до внутрішньої пам'яті цільової машини або після припинення схеми хешування, або в якийсь момент, коли сам пароль ще присутній в пам'яті. Завдяки перезапису інформації з допомогою функції <math>G</math>, Argon2i і Argon2d стійкі до даних атак{{Sfn|Overview|2015}}.

== Застосування ==
Argon2 оптимізований під [[x86]]-архітектуру і може бути реалізований на [[Linux]], [[MacOS|OS X]], [[Microsoft Windows|Windows]].

'''Argon2d''' призначений для систем, де зловмисник не отримує регулярного доступу до системної пам'яті або [[Процесор|процесора]]. Наприклад, для backend-[[Сервер|серверів]] і [[Майнінг|криптомайнерів]]. При використанні одного ядра на 2-Ghz [[Центральний процесор|CPU]] і 250 Mb [[Оперативна пам'ять|оперативної пам'яті]] з Argon2d (p=2) криптомайнінг займає 0,1 сек., а при застосуванні 4 ядер і 4 Gb пам'яті (p=8) [[автентифікація]] на [[Front end та back end|backend]] сервері проходить за 0.5 сек.

'''Argon2i''' більше підходить для frontend-серверів і [[шифрування]] [[Жорсткий диск|жорсткого диска]]. Формування ключа для шифрування на 2-Ghz [[Центральний процесор|CPU]], використовуючи 2 ядра і 6 Гб оперативної пам'яті, з Argon2i (p=4) займає 3 сек., у той час як [[Автентифікація|аутентифікація]] на frontend-сервері, задіявши 2 ядра і 1 Gb пам'яті з Argon2i (p=4), займає 0,5 сек.{{Sfn|Argon|2016}}

== Примітки ==
{{примечания|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
 |accessdate         = 16 квітня 2018
 |archive-date         = 7 квітня 2019
 |archive-url         = https://web.archive.org/web/20190407233101/https://password-hashing.net/
 }}
* {{стаття
 | автор        = 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 {{Webarchive|url=https://web.archive.org/web/20190402211036/https://github.com/P-H-C/phc-winner-argon2 |date=2 квітня 2019 }}
* https://www.cryptolux.org/index.php/Argon2 {{Webarchive|url=https://web.archive.org/web/20190331160026/https://www.cryptolux.org/index.php/Argon2 |date=31 березня 2019 }}
* https://github.com/khovratovich/Argon2 {{Webarchive|url=https://web.archive.org/web/20180611002323/https://github.com/khovratovich/Argon2 |date=11 червня 2018 }} (рання версія функції)

{{Геш-функції та коди аутентифікації повідомлення}}
[[Категорія:Криптографія]]