О документе
Internet Research Task Force (IRTF) A. Biryukov
Request for Comments: 9106 D. Dinu
Category: Informational University of Luxembourg
ISSN: 2070-1721 D. Khovratovich
ABDK Consulting
S. Josefsson
SJD AB
September 2021
Функция Argon2 с требованием к памяти для хеширования паролей и
приложений доказательства выполнения работы
1. Введение
Этот документ описывает функцию Argon2 [ARGON2ESP] с требованием к
памяти для хеширования паролей и приложений доказательства выполнения
работы. Мы предоставляем ориентированное на реализатора описание с
тестовыми векторами. Цель состоит в упрощении внедрения Argon2 в
интернет-протоколах. Этот документ соответствует версии 1.3
хеш-функции Argon2.
Argon2 — функция с требованием к памяти [HARD]. Она имеет упрощённую
конструкцию. Она нацелена на максимальную скорость заполнения памяти
и эффективное использование нескольких вычислительных блоков, при
этом обеспечивая защиту от атак компромисса. Argon2 оптимизирована для
архитектуры x86 и использует организацию кэша и памяти современных
процессоров Intel и AMD. Argon2 имеет один основной вариант, Argon2id,
и два дополнительные варианта, Argon2d и Argon2i. Argon2d использует
зависимый от данных доступ к памяти, что делает его пригодным для
криптовалют и приложений доказательства выполнения работы без угроз
атак по времени через побочные каналы. Argon2i использует независимый
от данных доступ к памяти, который предпочтителен для хеширования
паролей и выведения ключей на основе паролей. Argon2id работает как
Argon2i в течение первой половины первого прохода по памяти и как
Argon2d в оставшейся части, обеспечивая тем самым как защиту от атак
по побочным каналам, так и снижение стоимости перебора благодаря
компромиссам времени и памяти. Argon2i выполняет больше проходов по
памяти для защиты от атак компромисса [AB15].
Argon2id ДОЛЖЕН (MUST) поддерживаться любой реализацией этого
документа, тогда как Argon2d и Argon2i МОГУТ (MAY) поддерживаться.
Argon2 также является режимом работы над функцией сжатия G с
фиксированной длиной входных данных и хеш-функцией H с переменной
длиной входных данных. Хотя Argon2 потенциально может использоваться
с произвольной функцией H, если она выдаёт результаты длиной до 64
байтов, в этом документе используется функция BLAKE2b [BLAKE2].
Дополнительные сведения и обсуждение приведены в статье об Argon2
[ARGON2].
Этот документ представляет консенсус Crypto Forum Research Group
(CFRG).
1.1. Язык требований
Ключевые слова "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY" и
"OPTIONAL" в этом документе должны интерпретироваться согласно BCP 14
[RFC2119] [RFC8174] тогда и только тогда, когда они написаны полностью
прописными буквами, как показано здесь.
2. Обозначения и соглашения
x^y целое число x, умноженное само на себя целое число y раз
a*b умножение целого числа a на целое число b
c-d вычитание целого числа d из целого числа c
E_f переменная E с нижним индексом f
g / h целое число g, делённое на целое число h. Результатом
является рациональное число.
I(j) функция I, вычисленная при j
K || L строка K, конкатенированная со строкой L
a XOR b побитовое исключающее ИЛИ между битовыми строками a и b
a mod b остаток от деления целого числа a по модулю целого
числа b, всегда в диапазоне [0, b-1]
a >>> n циклический сдвиг 64-битной строки a вправо на n битов
trunc(a) 64-битное значение, усечённое до 32 младших значащих
битов
floor(a) наибольшее целое число, не большее a
ceil(a) наименьшее целое число, не меньшее a
extract(a, i) i-й набор из 32 битов из битовой строки a, начиная с
набора с номером 0
|A| число элементов в множестве A
LE32(a) 32-битное целое число a, преобразованное в байтовую
строку с порядком байтов little endian (например,
123456 (десятичное) равно 40 E2 01 00)
LE64(a) 64-битное целое число a, преобразованное в байтовую
строку с порядком байтов little endian (например,
123456 (десятичное) равно 40 E2 01 00
00 00 00 00)
int32(s) 32-битная строка s интерпретируется как неотрицательное
целое число в порядке little endian
int64(s) 64-битная строка s интерпретируется как неотрицательное
целое число в порядке little endian
length(P) байтовая длина строки P, выраженная как 32-битное
целое число
ZERO(P) нулевая строка длиной P байтов
3.1. Входные и выходные данные Argon2
Argon2 имеет следующие входные параметры:
* Строка сообщения P, которая является паролем для приложений
хеширования паролей. Её длина ДОЛЖНА (MUST) быть не больше
2^(32)-1 байтов.
* Nonce S, который является солью для приложений хеширования
паролей. Его длина ДОЛЖНА (MUST) быть не больше 2^(32)-1 байтов.
Для хеширования паролей СЛЕДУЕТ (RECOMMENDED) использовать 16 байтов.
Соль СЛЕДУЕТ (SHOULD) делать уникальной для каждого пароля.
* Степень параллелизма p определяет, сколько независимых (но
синхронизирующихся) вычислительных цепочек (полос) может быть
запущено. Она ДОЛЖНА (MUST) быть целым числом от 1 до 2^(24)-1.
* Длина тега T ДОЛЖНА (MUST) быть целым числом байтов от 4 до 2^(32)-
1.
* Размер памяти m ДОЛЖЕН (MUST) быть целым числом кибибайтов от 8*p
до 2^(32)-1. Фактическое число блоков — m', то есть m, округлённое
вниз до ближайшего кратного 4*p.
* Число проходов t (используемое для настройки времени выполнения
независимо от размера памяти) ДОЛЖНО (MUST) быть целым числом от 1
до 2^(32)-1.
* Номер версии v ДОЛЖЕН (MUST) быть одним байтом 0x13.
* Секретное значение K НЕОБЯЗАТЕЛЬНО (OPTIONAL). Если оно
используется, его длина ДОЛЖНА (MUST) быть не больше 2^(32)-1
байтов.
* Связанные данные X НЕОБЯЗАТЕЛЬНЫ (OPTIONAL). Если они используются,
их длина ДОЛЖНА (MUST) быть не больше 2^(32)-1 байтов.
* Тип y ДОЛЖЕН (MUST) быть равен 0 для Argon2d, 1 для Argon2i или 2
для Argon2id.
Выход Argon2, или «тег», представляет собой строку длиной T байтов.
3.2. Работа Argon2
Argon2 использует внутреннюю функцию сжатия G с двумя входами по
1024 байта, выходом размером 1024 байта и внутреннюю хеш-функцию
H^x(), где x — длина её выхода в байтах. Здесь H^x(), применённая к
строке A, является функцией BLAKE2b ([BLAKE2], раздел 3.3), которая
принимает в качестве параметров (d,ll,kk=0,nn=x), где d — A,
дополненная до кратной 128 байтам длины, а ll — длина d в байтах.
Функция сжатия G основана на её внутренней перестановке. Также
используется хеш-функция переменной длины H', построенная на основе H.
G описана в разделе 3.5, а H' — в разделе 3.3.
Работа Argon2 выполняется следующим образом.
1. Установить H_0 как 64-байтовое значение, показанное ниже. Если K,
X или S имеют нулевую длину, они просто отсутствуют, но их поле
длины сохраняется.
H_0 = H^(64)(LE32(p) || LE32(T) || LE32(m) || LE32(t) ||
LE32(v) || LE32(y) || LE32(length(P)) || P ||
LE32(length(S)) || S || LE32(length(K)) || K ||
LE32(length(X)) || X)
Рисунок 1: Формирование H_0
2. Выделить память как m' блоков по 1024 байта, где m' выводится
следующим образом:
m' = 4 * p * floor (m / 4p)
Рисунок 2: Выделение памяти
Для p полос память организована в матрицу блоков B[i][j] с p
строками (полосами) и q = m' / p столбцами.
3. Вычислить B[i][0] для всех i в диапазоне от (включительно) 0 до
(не включая) p.
B[i][0] = H'^(1024)(H_0 || LE32(0) || LE32(i))
Рисунок 3: Начальные блоки полос
4. Вычислить B[i][1] для всех i в диапазоне от (включительно) 0 до
(не включая) p.
B[i][1] = H'^(1024)(H_0 || LE32(1) || LE32(i))
Рисунок 4: Вторые блоки полос
5. Вычислить B[i][j] для всех i в диапазоне от (включительно) 0 до
(не включая) p и для всех j в диапазоне от (включительно) 2 до
(не включая) q. Вычисление ДОЛЖНО (MUST) выполняться посрезово
(раздел 3.4): сначала вычисляются блоки среза 0 для всех полос
(в произвольном порядке полос), затем вычисляются блоки среза 1 и
т. д. Индексы блоков l и z определяются для каждого i, j по-разному
для Argon2d, Argon2i и Argon2id.
B[i][j] = G(B[i][j-1], B[l][z])
Рисунок 5: Дальнейшее формирование блоков
6. Если число проходов t больше 1, повторить шаг 5. Вычислить
B[i][0] и B[i][j] для всех i, «raging» от (включительно) 0 до
(не включая) p и для всех j в диапазоне от (включительно) 1 до
(не включая) q. Однако блоки вычисляются иначе, поскольку старое
значение подвергается XOR с новым:
B[i][0] = G(B[i][q-1], B[l][z]) XOR B[i][0];
B[i][j] = G(B[i][j-1], B[l][z]) XOR B[i][j].
Рисунок 6: Дальнейшие проходы
7. После выполнения t шагов итоговый блок C вычисляется как XOR
последнего столбца:
C = B[0][q-1] XOR B[1][q-1] XOR ... XOR B[p-1][q-1]
Рисунок 7: Итоговый блок
8. Выходной тег вычисляется как H'^T(C).
3.3. Хеш-функция переменной длины H'
Пусть V_i — 64-байтовый блок, а W_i — его первые 32 байта. Тогда
функцию H' определяем следующим образом:
if T <= 64
H'^T(A) = H^T(LE32(T)||A)
else
r = ceil(T/32)-2
V_1 = H^(64)(LE32(T)||A)
V_2 = H^(64)(V_1)
...
V_r = H^(64)(V_{r-1})
V_{r+1} = H^(T-32*r)(V_{r})
H'^T(X) = W_1 || W_2 || ... || W_r || V_{r+1}
Рисунок 8: Функция H' для вычислений тега и начального блока
3.4. Индексирование
Чтобы обеспечить параллельное вычисление блоков, далее разделим
матрицу памяти на SL = 4 вертикальных среза. Пересечение среза и
полосы называется сегментом, длина которого равна q/SL. Сегменты
одного среза могут вычисляться параллельно и не ссылаются на блоки
друг друга. На все прочие блоки можно ссылаться.
slice 0 slice 1 slice 2 slice 3
___/\___ ___/\___ ___/\___ ___/\___
/ \ / \ / \ / \
+----------+----------+----------+----------+
| | | | | > lane 0
+----------+----------+----------+----------+
| | | | | > lane 1
+----------+----------+----------+----------+
| | | | | > lane 2
+----------+----------+----------+----------+
| ... ... ... | ...
+----------+----------+----------+----------+
| | | | | > lane p - 1
+----------+----------+----------+----------+
Рисунок 9: Однопроходный Argon2 с p полосами и 4 срезами
3.4.1. Вычисление 32-битных значений J_1 и J_2
3.4.1.1. Argon2d
J_1 задаётся первыми 32 битами блока B[i][j-1], тогда как J_2 задаётся
следующими 32 битами блока B[i][j-1]:
J_1 = int32(extract(B[i][j-1], 0))
J_2 = int32(extract(B[i][j-1], 1))
Рисунок 10: Получение J1,J2 в Argon2d
3.4.1.2. Argon2i
Для каждого сегмента выполняется следующее. Сначала вычисляется значение Z
как:
Z= ( LE64(r) || LE64(l) || LE64(sl) || LE64(m') ||
LE64(t) || LE64(y) )
Рисунок 11: Входные данные для вычисления J1,J2 в Argon2i
где
r: номер прохода
l: номер полосы
sl: номер среза
m': общее число блоков памяти
t: общее число проходов
y: тип Argon2 (0 для Argon2d, 1 для Argon2i, 2 для Argon2id)
Затем вычисляются:
q/(128*SL) 1024-байтовых значений
G(ZERO(1024),G(ZERO(1024),
Z || LE64(1) || ZERO(968) )),
G(ZERO(1024),G(ZERO(1024),
Z || LE64(2) || ZERO(968) )),... ,
G(ZERO(1024),G(ZERO(1024),
Z || LE64(q/(128*SL)) || ZERO(968) )),
которые разделяются на q/(SL) 8-байтовых значений X, рассматриваемых
как X1||X2 и преобразуемых в J_1=int32(X1) и J_2=int32(X2).
Значения r, l, sl, m', t, y и i представляются 8 байтами в
порядке little endian.
3.4.1.3. Argon2id
Если номер прохода равен 0, а номер среза равен 0 или 1, то J_1 и J_2
вычисляются как для Argon2i, иначе J_1 и J_2 вычисляются как для Argon2d.
3.4.2. Отображение J_1 и J_2 на индекс опорного блока [l][z]
Значение l = J_2 mod p задаёт индекс полосы, из которой будет взят
блок. Для первого прохода (r=0) и первого среза (sl=0) блок берётся
из текущей полосы.
Множество W содержит индексы, на которые ссылаются согласно следующим
правилам:
1. Если l является текущей полосой, то W включает индексы всех
блоков в последних SL - 1 = 3 вычисленных и завершённых сегментах,
а также блоков, вычисленных в текущем сегменте в текущем проходе,
за исключением B[i][j-1].
2. Если l не является текущей полосой, то W включает индексы всех
блоков в последних SL - 1 = 3 вычисленных и завершённых сегментах
полосы l. Если B[i][j] является первым блоком сегмента, то самый
последний индекс из W исключается.
Затем блок из W выбирается с неравномерным распределением по [0, |W|)
с использованием следующего отображения:
J_1 -> |W|(1 - J_1^2 / 2^(64))
Рисунок 12: Вычисление J1
Чтобы избежать вычислений с плавающей точкой, используется следующее
приближение:
x = J_1^2 / 2^(32)
y = (|W| * x) / 2^(32)
zz = |W| - 1 - y
Рисунок 13: Вычисление J1, часть 2
Затем из W берётся zz-й индекс; он будет значением z для индекса
опорного блока [l][z].
3.5. Функция сжатия G
Функция сжатия G построена на основе преобразования P на базе BLAKE2b.
P работает со 128-байтовыми входными данными, которые можно
рассматривать как восемь 16-байтовых регистров:
P(A_0, A_1, ... ,A_7) = (B_0, B_1, ... ,B_7)
Рисунок 14: Функция раунда Blake P
Функция сжатия G(X, Y) работает с двумя 1024-байтовыми блоками X
и Y. Сначала она вычисляет R = X XOR Y. Затем R рассматривается как
матрица 8x8 16-байтовых регистров R_0, R_1, ... , R_63. Затем P сначала
применяется к каждой строке, а затем к каждому столбцу, чтобы получить Z:
( Q_0, Q_1, Q_2, ... , Q_7) <- P( R_0, R_1, R_2, ... , R_7)
( Q_8, Q_9, Q_10, ... , Q_15) <- P( R_8, R_9, R_10, ... , R_15)
...
(Q_56, Q_57, Q_58, ... , Q_63) <- P(R_56, R_57, R_58, ... , R_63)
( Z_0, Z_8, Z_16, ... , Z_56) <- P( Q_0, Q_8, Q_16, ... , Q_56)
( Z_1, Z_9, Z_17, ... , Z_57) <- P( Q_1, Q_9, Q_17, ... , Q_57)
...
( Z_7, Z_15, Z 23, ... , Z_63) <- P( Q_7, Q_15, Q_23, ... , Q_63)
Рисунок 15: Ядро функции сжатия G
Наконец, G выдаёт Z XOR R:
G: (X, Y) -> R -> Q -> Z -> Z XOR R
+---+ +---+
| X | | Y |
+---+ +---+
| |
---->XOR<----
--------|
| \ /
| +---+
| | R |
| +---+
| |
| \ /
| P rowwise
| |
| \ /
| +---+
| | Q |
| +---+
| |
| \ /
| P columnwise
| |
| \ /
| +---+
| | Z |
| +---+
| |
| \ /
------>XOR
|
\ /
Рисунок 16: Функция сжатия Argon2 G
3.6. Перестановка P
Перестановка P основана на функции раунда BLAKE2b. Восемь
16-байтовых входных значений S_0, S_1, ... , S_7 рассматриваются как
матрица 4x4 64-битовых слов, где S_i = (v_{2*i+1} || v_{2*i}):
v_0 v_1 v_2 v_3
v_4 v_5 v_6 v_7
v_8 v_9 v_10 v_11
v_12 v_13 v_14 v_15
Рисунок 17: Обозначение элементов матрицы
Она работает следующим образом:
GB(v_0, v_4, v_8, v_12)
GB(v_1, v_5, v_9, v_13)
GB(v_2, v_6, v_10, v_14)
GB(v_3, v_7, v_11, v_15)
GB(v_0, v_5, v_10, v_15)
GB(v_1, v_6, v_11, v_12)
GB(v_2, v_7, v_8, v_13)
GB(v_3, v_4, v_9, v_14)
Рисунок 18: Передача элементов матрицы в GB
GB(a, b, c, d) определяется следующим образом:
a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64)
d = (d XOR a) >>> 32
c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64)
b = (b XOR c) >>> 24
a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64)
d = (d XOR a) >>> 16
c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64)
b = (b XOR c) >>> 63
Рисунок 19: Подробности GB
Модульные сложения в GB объединены с 64-битовыми умножениями.
Умножения являются единственным отличием от исходной конструкции BLAKE2b.
Этот выбор сделан для увеличения глубины схемы и, следовательно, времени
работы реализаций ASIC при примерно том же времени работы на CPU благодаря
параллелизму и конвейеризации.
4. Выбор параметров
Argon2d оптимизирован для условий, в которых противник не получает
регулярного доступа к памяти системы или CPU, то есть не может проводить
атаки по сторонним каналам на основе информации о времени, а также не может
восстановить пароль значительно быстрее с помощью сборки мусора. Такие
условия более типичны для бэкенд-серверов и майнинга криптовалют.
Для практического применения мы предлагаем следующие настройки:
* Майнинг криптовалют, занимающий 0,1 секунды на CPU 2 ГГц
с использованием 1 ядра -- Argon2d с 2 полосами и 250 МБ RAM.
Argon2id оптимизирован для более реалистичных условий, в которых
противник может получить доступ к той же машине, использовать её CPU или
осуществить атаки cold boot. Мы предлагаем следующие настройки:
* Аутентификация на бэкенд-сервере, занимающая 0,5 секунды на CPU 2 ГГц
с использованием 4 ядер -- Argon2id с 8 полосами и 4 ГиБ RAM.
* Выработка ключа для шифрования жёсткого диска, занимающая 3 секунды на
CPU 2 ГГц с использованием 2 ядер -- Argon2id с 4 полосами и 6 ГиБ
RAM.
* Аутентификация фронтенд-сервера, занимающая 0,5 секунды на CPU 2 ГГц
с использованием 2 ядер -- Argon2id с 4 полосами и 1 ГиБ RAM.
Мы рекомендуем следующую процедуру для выбора типа и параметров
Argon2 для практического применения.
1. Если приемлем единообразно безопасный вариант, не адаптированный к
вашему приложению или оборудованию, выберите Argon2id с t=1
итерацией, p=4 полосами, m=2^(21) (2 ГиБ RAM), 128-битовой солью и
размером тега 256 бит. Это ПЕРВЫЙ РЕКОМЕНДУЕМЫЙ (RECOMMENDED) вариант.
2. Если доступно значительно меньше памяти, единообразно безопасным
вариантом является Argon2id с t=3 итерациями, p=4 полосами,
m=2^(16) (64 МиБ RAM), 128-битовой солью и размером тега 256 бит.
Это ВТОРОЙ РЕКОМЕНДУЕМЫЙ (RECOMMENDED) вариант.
3. В противном случае начните с выбора типа y. Если вы не знаете
различия между типами или считаете атаки по сторонним каналам
реальной угрозой, выберите Argon2id.
4. Выберите p=4 полосы.
5. Определите максимальный объём памяти, который может позволить себе
каждый вызов, и преобразуйте его в параметр m.
6. Определите максимальное количество времени (в секундах), которое
может позволить себе каждый вызов.
7. Выберите длину соли. Длины 128 бит достаточно для всех приложений,
но при ограничениях пространства её можно уменьшить до 64 бит.
8. Выберите длину тега. Длины 128 бит достаточно для большинства
приложений, включая выработку ключей. Если нужны более длинные ключи,
выберите более длинные теги.
9. Если атаки по сторонним каналам являются реальной угрозой или вы
не уверены, включите параметр стирания памяти при вызове библиотеки.
10. Запустите схему типа y, с памятью m и p полосами, используя разное
число проходов t. Определите максимальное t, при котором время работы
не превышает допустимое время. Если оно превышается даже при t = 1,
соответственно уменьшите m.
11. Используйте Argon2 с определёнными значениями m, p и t.
5. Тестовые векторы
Этот раздел содержит тестовые векторы для Argon2.
5.1. Тестовые векторы Argon2d
Мы предоставляем тестовые векторы с полными выходными данными (тегами).
Для удобства разработчиков мы также предоставляем некоторые промежуточные
переменные -- а именно первый и последний блоки памяти каждого прохода.
=======================================
Argon2d version number 19
=======================================
Memory: 32 KiB
Passes: 3
Parallelism: 4 lanes
Tag length: 32 bytes
Password[32]: 01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01
Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02
Secret[8]: 03 03 03 03 03 03 03 03
Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04
Pre-hashing digest: b8 81 97 91 a0 35 96 60
bb 77 09 c8 5f a4 8f 04
d5 d8 2c 05 c5 f2 15 cc
db 88 54 91 71 7c f7 57
08 2c 28 b9 51 be 38 14
10 b5 fc 2e b7 27 40 33
b9 fd c7 ae 67 2b ca ac
5d 17 90 97 a4 af 31 09
After pass 0:
Block 0000 [ 0]: db2fea6b2c6f5c8a
Block 0000 [ 1]: 719413be00f82634
Block 0000 [ 2]: a1e3f6dd42aa25cc
Block 0000 [ 3]: 3ea8efd4d55ac0d1
...
Block 0031 [124]: 28d17914aea9734c
Block 0031 [125]: 6a4622176522e398
Block 0031 [126]: 951aa08aeecb2c05
Block 0031 [127]: 6a6c49d2cb75d5b6
After pass 1:
Block 0000 [ 0]: d3801200410f8c0d
Block 0000 [ 1]: 0bf9e8a6e442ba6d
Block 0000 [ 2]: e2ca92fe9c541fcc
Block 0000 [ 3]: 6269fe6db177a388
...
Block 0031 [124]: 9eacfcfbdb3ce0fc
Block 0031 [125]: 07dedaeb0aee71ac
Block 0031 [126]: 074435fad91548f4
Block 0031 [127]: 2dbfff23f31b5883
After pass 2:
Block 0000 [ 0]: 5f047b575c5ff4d2
Block 0000 [ 1]: f06985dbf11c91a8
Block 0000 [ 2]: 89efb2759f9a8964
Block 0000 [ 3]: 7486a73f62f9b142
...
Block 0031 [124]: 57cfb9d20479da49
Block 0031 [125]: 4099654bc6607f69
Block 0031 [126]: f142a1126075a5c8
Block 0031 [127]: c341b3ca45c10da5
Tag: 51 2b 39 1b 6f 11 62 97
53 71 d3 09 19 73 42 94
f8 68 e3 be 39 84 f3 c1
a1 3a 4d b9 fa be 4a cb
5.2. Тестовые векторы Argon2i
=======================================
Argon2i version number 19
=======================================
Memory: 32 KiB
Passes: 3
Parallelism: 4 lanes
Tag length: 32 bytes
Password[32]: 01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01
Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02
Secret[8]: 03 03 03 03 03 03 03 03
Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04
Pre-hashing digest: c4 60 65 81 52 76 a0 b3
e7 31 73 1c 90 2f 1f d8
0c f7 76 90 7f bb 7b 6a
5c a7 2e 7b 56 01 1f ee
ca 44 6c 86 dd 75 b9 46
9a 5e 68 79 de c4 b7 2d
08 63 fb 93 9b 98 2e 5f
39 7c c7 d1 64 fd da a9
After pass 0:
Block 0000 [ 0]: f8f9e84545db08f6
Block 0000 [ 1]: 9b073a5c87aa2d97
Block 0000 [ 2]: d1e868d75ca8d8e4
Block 0000 [ 3]: 349634174e1aebcc
...
Block 0031 [124]: 975f596583745e30
Block 0031 [125]: e349bdd7edeb3092
Block 0031 [126]: b751a689b7a83659
Block 0031 [127]: c570f2ab2a86cf00
After pass 1:
Block 0000 [ 0]: b2e4ddfcf76dc85a
Block 0000 [ 1]: 4ffd0626c89a2327
Block 0000 [ 2]: 4af1440fff212980
Block 0000 [ 3]: 1e77299c7408505b
...
Block 0031 [124]: e4274fd675d1e1d6
Block 0031 [125]: 903fffb7c4a14c98
Block 0031 [126]: 7e5db55def471966
Block 0031 [127]: 421b3c6e9555b79d
After pass 2:
Block 0000 [ 0]: af2a8bd8482c2f11
Block 0000 [ 1]: 785442294fa55e6d
Block 0000 [ 2]: 9256a768529a7f96
Block 0000 [ 3]: 25a1c1f5bb953766
...
Block 0031 [124]: 68cf72fccc7112b9
Block 0031 [125]: 91e8c6f8bb0ad70d
Block 0031 [126]: 4f59c8bd65cbb765
Block 0031 [127]: 71e436f035f30ed0
Tag: c8 14 d9 d1 dc 7f 37 aa
13 f0 d7 7f 24 94 bd a1
c8 de 6b 01 6d d3 88 d2
99 52 a4 c4 67 2b 6c e8
5.3. Тестовые векторы Argon2id
=======================================
Argon2id version number 19
=======================================
Memory: 32 KiB, Passes: 3,
Parallelism: 4 lanes, Tag length: 32 bytes
Password[32]: 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02
Secret[8]: 03 03 03 03 03 03 03 03
Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04
Pre-hashing digest: 28 89 de 48 7e b4 2a e5 00 c0 00 7e d9 25 2f
10 69 ea de c4 0d 57 65 b4 85 de 6d c2 43 7a 67 b8 54 6a 2f 0a
cc 1a 08 82 db 8f cf 74 71 4b 47 2e 94 df 42 1a 5d a1 11 2f fa
11 43 43 70 a1 e9 97
After pass 0:
Block 0000 [ 0]: 6b2e09f10671bd43
Block 0000 [ 1]: f69f5c27918a21be
Block 0000 [ 2]: dea7810ea41290e1
Block 0000 [ 3]: 6787f7171870f893
...
Block 0031 [124]: 377fa81666dc7f2b
Block 0031 [125]: 50e586398a9c39c8
Block 0031 [126]: 6f732732a550924a
Block 0031 [127]: 81f88b28683ea8e5
After pass 1:
Block 0000 [ 0]: 3653ec9d01583df9
Block 0000 [ 1]: 69ef53a72d1e1fd3
Block 0000 [ 2]: 35635631744ab54f
Block 0000 [ 3]: 599512e96a37ab6e
...
Block 0031 [124]: 4d4b435cea35caa6
Block 0031 [125]: c582210d99ad1359
Block 0031 [126]: d087971b36fd6d77
Block 0031 [127]: a55222a93754c692
After pass 2:
Block 0000 [ 0]: 942363968ce597a4
Block 0000 [ 1]: a22448c0bdad5760
Block 0000 [ 2]: a5f80662b6fa8748
Block 0000 [ 3]: a0f9b9ce392f719f
...
Block 0031 [124]: d723359b485f509b
Block 0031 [125]: cb78824f42375111
Block 0031 [126]: 35bc8cc6e83b1875
Block 0031 [127]: 0b012846a40f346a
Tag: 0d 64 0d f5 8d 78 76 6c 08 c0 37 a3 4a 8b 53 c9 d0
1e f0 45 2d 75 b6 5e b5 25 20 e9 6b 01 e6 59
6. Соображения IANA
В этом документе нет действий IANA.
7. Соображения безопасности
7.1. Безопасность в качестве хеш-функции и KDF
Уровни устойчивости Argon2 к коллизиям и нахождению прообраза эквивалентны
уровням лежащей в его основе хеш-функции BLAKE2b. Для получения
коллизии требуется 2^(256) входных данных. Для нахождения прообраза
необходимо опробовать 2^(512) входных данных.
Безопасность KDF определяется длиной ключа и размером внутреннего
состояния хеш-функции H'. Чтобы отличить выход ключевого Argon2 от
случайного, требуется как минимум (2^(128),2^length(K)) вызовов
BLAKE2b.
7.2. Безопасность против атак компромисса «время—память»
Компромиссы «время—память» позволяют вычислять функцию, требующую большого
объёма памяти, храня меньше блоков памяти ценой большего числа вызовов
внутренней функции сжатия. Преимущество атак компромисса измеряется
коэффициентом уменьшения произведения «время—площадь», где память и
дополнительные ядра функции сжатия вносят вклад в площадь, а время
увеличивается для учёта повторного вычисления пропущенных блоков. Высокий
коэффициент уменьшения потенциально может ускорить поиск прообраза.
Наилучшей известной атакой на Argon2i с 1 и 2 проходами является атака с
малым хранилищем, описанная в [CBS16], которая уменьшает произведение
«время—площадь» (с использованием пикового значения памяти) в 5 раз.
Наилучшая атака на Argon2i с 3 или более проходами описана в [AB16], при
этом коэффициент уменьшения является функцией размера памяти и числа
проходов (например, для 1 гибибайта памяти коэффициент уменьшения равен 3
для 3 проходов, 2,5 для 4 проходов, 2 для 6 проходов). Коэффициент
уменьшения возрастает примерно на 0,5 при каждом удвоении размера памяти.
Чтобы полностью предотвратить компромиссы «время—память» из [AB16], число
проходов ДОЛЖНО (MUST) превышать двоичный логарифм объёма памяти минус 26.
Асимптотически наилучшая атака на Argon2i с 1 проходом приведена в [BZ17],
при этом максимальное преимущество противника сверху ограничено
O(m^(0.233)), где m — число блоков. Эта атака также асимптотически
оптимальна, поскольку [BZ17] также доказывает, что верхняя граница для
любой атаки равна O(m^(0.25)).
Наилучшей атакой компромисса на Argon2d с t проходами является ранговая
атака компромисса, которая уменьшает произведение «время—площадь» в 1,33
раза.
Наилучшую атаку на Argon2id можно получить, дополнив наилучшую атаку на
Argon2i с 1 проходом наилучшей атакой на Argon2d с несколькими проходами.
Таким образом, наилучшей атакой компромисса на Argon2id с 1 проходом
является объединённая атака с малым хранилищем (для первой половины
памяти) и ранговая атака (для второй половины), которые дают коэффициент
около 2,1. Наилучшей атакой компромисса на Argon2id с t проходами является
ранговая атака компромисса, которая уменьшает произведение
«время—площадь» в 1,33 раза.
7.3. Безопасность для защитников, ограниченных по времени
Узким местом в системе, использующей функцию хеширования паролей, часто
является задержка функции, а не затраты памяти. Поэтому рациональный
защитник максимизировал бы затраты на полный перебор для атакующего,
располагающего списком хешей, солей и информацией о времени, при
фиксированном времени вычислений на машине защитника. Оценки стоимости
атаки из [AB16] подразумевают, что для Argon2i 3 прохода почти
оптимальны для большинства разумных размеров памяти; для Argon2d и
Argon2id 1 проход максимизирует стоимость атаки при постоянном времени
защитника.
7.4. Рекомендации
ПЕРВЫМ вариантом, который СЛЕДУЕТ (RECOMMENDED) использовать, является
вариант Argon2id с t=1 и 2 GiB памяти; он предлагается в качестве настройки
по умолчанию для всех сред. Эта настройка защищена от атак по побочным
каналам и максимизирует затраты противника на специализированном
оборудовании для полного перебора. ВТОРЫМ вариантом, который СЛЕДУЕТ
(RECOMMENDED) использовать, является вариант Argon2id с t=3 и 64 MiB
памяти; он предлагается в качестве настройки по умолчанию для сред с
ограниченным объёмом памяти.
8.1. Нормативные ссылки
[BLAKE2] Saarinen, M-J., Ed. and J-P. Aumasson, "The BLAKE2
Cryptographic Hash and Message Authentication Code (MAC)",
RFC 7693, DOI 10.17487/RFC7693, November 2015,
<https://www.rfc-editor.org/info/rfc7693>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
8.2. Информативные ссылки
[AB15] Biryukov, A. and D. Khovratovich, "Tradeoff Cryptanalysis
of Memory-Hard Functions", ASIACRYPT 2015,
DOI 10.1007/978-3-662-48800-3_26, December 2015,
<https://eprint.iacr.org/2015/227.pdf>.
[AB16] Alwen, J. and J. Blocki, "Efficiently Computing Data-
Independent Memory-Hard Functions", CRYPTO 2016,
DOI 10.1007/978-3-662-53008-5_9, March 2016,
<https://eprint.iacr.org/2016/115.pdf>.
[ARGON2] Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: the
memory-hard function for password hashing and other
applications", March 2017,
<https://www.cryptolux.org/images/0/0d/Argon2.pdf>.
[ARGON2ESP]
Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: New
Generation of Memory-Hard Functions for Password Hashing
and Other Applications", Euro SnP 2016,
DOI 10.1109/EuroSP.2016.31, March 2016,
<https://www.cryptolux.org/images/d/d0/Argon2ESP.pdf>.
[BZ17] Blocki, J. and S. Zhou, "On the Depth-Robustness and
Cumulative Pebbling Cost of Argon2i", TCC 2017,
DOI 10.1007/978-3-319-70500-2_15, May 2017,
<https://eprint.iacr.org/2017/442.pdf>.
[CBS16] Boneh, D., Corrigan-Gibbs, H., and S. Schechter, "Balloon
Hashing: A Memory-Hard Function Providing Provable
Protection Against Sequential Attacks", ASIACRYPT 2016,
DOI 10.1007/978-3-662-53887-6_8, May 2017,
<https://eprint.iacr.org/2016/027.pdf>.
[HARD] Alwen, J. and V. Serbinenko, "High Parallel Complexity
Graphs and Memory-Hard Functions", STOC '15,
DOI 10.1145/2746539.2746622, June 2015,
<https://eprint.iacr.org/2014/238.pdf>.