Русская Википедия:Argon2
Шаблон:Карточка хеш-функции Argon2 — функция формирования ключа, разработанная Алексом Бирюковым (Шаблон:Lang-en), Даниэлем Дину (Шаблон:Lang-en) и Дмитрием Ховратовичем (Шаблон:Lang-en) из Университета Люксембурга в 2015 годуШаблон:Sfn.
Это современный простой алгоритм, направленный на высокую скорость заполнения памяти и эффективное использование нескольких вычислительных блоковШаблон:Sfn. Алгоритм выпущен под лицензией Creative Commons.
История
В 2013 году был объявлен конкурс Шаблон:Iw о создании новой функции хеширования паролей. К новому алгоритму предъявлялись требования по объёму используемой памяти, количеству проходов по блокам памяти и по устойчивости к криптоанализу.
В 2015 году Argon2 был объявлен победителем конкурсаШаблон:Sfn. С того времени алгоритм претерпел 4 серьёзных изменения. Исправлены часть описаний алгоритмов генерации некоторых блоков и опечатки, добавлены рекомендуемые параметрыШаблон:SfnШаблон:Sfn.
Входные данные
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
Версии алгоритма
Существуют две версии алгоритма:
- Argon2d — подходит для защиты цифровой валюты и информационных систем, не подверженных атакам по сторонним каналам.
- Argon2i — обеспечивает высокую защиту от trade-off атак, но работает медленнее версии d из-за нескольких проходов по памятиШаблон:Sfn.
Описание
Argon2 работает по следующему принципу:
- Производится хеширование пароля с использованием хеш-функции Blake2b.
- Результат хеширования записывается в блоки памяти.
- Блоки памяти преобразуются с использованием функции сжатия <math>G</math>
- В результате работы алгоритма генерируется ключ (Шаблон:Lang-en).
Заполнение блоков памяти
<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> — хеш-функция 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
Нахождение опорного блока
- 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
Функция H'
Blake2b — 64 битная версия функции 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.
Криптоанализ
Защита от коллизий: сама функция Blake2b считается криптографически безопасной. Также, ссылаясь на правила индексирования, авторы алгоритма доказали отсутствие коллизий внутри блоков данных и низкую вероятность их появления при применении функции сжатия.
Атака нахождения прообраза: пусть злоумышленник подобрал <math>m</math> такое, что <math>G(m) = h</math>, тогда для продолжения данной атаки он должен подобрать прообраз <math>n</math>: <math>H(n)=m</math>, что невозможно. Такое же рассуждение подходит для атаки нахождения второго прообраза.
Атаки по времени: если пользователю необходимо адаптироваться к атаке по времени, то следует использовать версию Argon2i, так как она использует независимую памятьШаблон:Sfn.
Атаки
Memory optimization attack
Дэн Боне, Henry Corrigan-Gibbs и Stuart Schechter в своей работе показали уязвимость Argon2i версии 1.2. Для однопроходной версии их атака снижала расход памяти в 4 раза без замедления выполнения. Для многопроходной версии — в 2,72 раза. Позднее, в версии 1.3 операция перезаписи была заменена на XORШаблон:Sfn.
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.
The ranking tradeoff attack
Данная атака является одной из самых эффективных для Argon2d. Она снижает время обработки в 1,33 раза. Для Argon2i при <math>t>2</math> коэффициент равен 3Шаблон:Sfn.
Garbage collector attacks
Основным условием для представленной атаки является доступ злоумышленника к внутренней памяти целевой машины либо после прекращения схемы хеширования, либо в какой-то момент, когда сам пароль ещё присутствует в памяти. Благодаря перезаписи информации с помощью функции <math>G</math>, Argon2i и Argon2d устойчивы к данным атакамШаблон:Sfn.
Применение
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 сШаблон:Sfn.
Примечания
Литература
Ссылки
- https://github.com/P-H-C/phc-winner-argon2
- https://www.cryptolux.org/index.php/Argon2
- https://github.com/khovratovich/Argon2 (ранняя версия функции)
