Введение
Argon2 – это ключевая функция деривации, которая была выбрана победителем конкурса хеширования паролей в июле 2015 года. Она была разработана Алексом Бирюковым, Даниэлем Дину и Дмитрием Ховратовичем из Люксембургского университета. Обычно Argon2 реализуется под лицензией Creative Commons CC0 ( общественное достояние) или Apache License 2.0, и предоставляет три связанные версии: Argon2d, Argon2i и Argon2id.
В этой статье мы обсудим принцип и использование Argon2.
ключевая функция вывода
В криптографии функция получения ключа (KDF) — это криптографическая хэш-функция, которая извлекает один или несколько ключей из секретного значения (например, главного ключа, пароля или фразы-пароля) с использованием псевдослучайной функции. KDF можно использовать для преобразования ключей в более длинные ключи или для получения ключей в нужном формате, например, для преобразования результата обмена ключами Диффи-Хеллмана в симметричный ключ для AES.
Password Hashing Competition
Хотя криптография — это изучение паролей, чем более публичным является алгоритм шифрования, тем лучше. Только сделав его общедоступным, мы можем проверить качество алгоритма. Только после тщательного исследования каждого алгоритм может использоваться и распространяться в отрасли.
Самым известным конкурсом криптографических алгоритмов, безусловно, является конкурс, проведенный NIST в 2001 г. для определения стандартного алгоритма AES.Цель конкурса — найти новейший алгоритм шифрования для замены старого алгоритма DES. В этом конкурсе появилось много превосходных алгоритмов, в том числе CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish и т. д. В конечном итоге алгоритм Rijndael был выбран в качестве окончательной реализации алгоритма AES.
Тот же PHC также является одним из таких конкурсов алгоритмов.В отличие от конкурса алгоритмов, проводимого NIST, это неофициальное соревнование, организованное криптографами. Он был запущен осенью 2012 года Жаном-Филиппом Омассоном.
В первом квартале 2013 г. было выпущено уведомление о запросе мнений, и к крайнему сроку 31 марта 2014 г. было получено в общей сложности 24 представления. В декабре 2014 года было определено 9 шорт-листов. В июле 2015 года победителем был объявлен Argon2.
Алгоритм Аргон2
Структура Argon2 проста и направлена на достижение максимальной скорости заполнения памяти и эффективного использования нескольких вычислительных блоков, а также на обеспечение защиты от компромиссных атак (путем использования кеша и памяти процессора).
Argon2 имеет три варианта. Argon2i, Argon2d и Argon2id. Argon2d быстрее и использует метод доступа к памяти, зависящий от данных, что делает его очень устойчивым к атакам взлома графического процессора и подходящим для приложений (таких как криптовалюты), которым не угрожают атаки по времени по сторонним каналам.
Argon2i использует независимый от данных доступ к памяти, который предпочтительнее для алгоритмов хэширования паролей и создания ключей на основе паролей, и характеризуется более медленной работой, поскольку выполняет больше логики обработки в памяти для предотвращения атак компромиссов.
Argon2id представляет собой гибрид Argon2i и Argon2d, который использует комбинацию доступа к памяти, зависящего от данных, и независимого от данных, что может противостоять атакам синхронизации по сторонним каналам и атакам взлома графического процессора.
Входные параметры Аргона2
Argon2 имеет два типа входных параметров: первичные входы и вторичные входы.
Первичные входные данные включают сообщения для шифрования P и одноразовый номер S, которые представляют пароль и соль соответственно.
Длина P от 0 до 232-1 байт, длина S от 8 до 232-1 байт (рекомендуется 16 байт для хеширования пароля).
Причина, по которой он называется первичным вводом, заключается в том, что необходимо ввести эти два параметра.
Остальные параметры называются вторичными входами и включают в себя:
- Степень параллелизма p, показывающая, сколько независимых вычислительных цепочек может работать одновременно, значение от 1 до 2.24-1.
- Длина тега τ, длина от 4 до 232-1 байт. ‘
- Размер памяти m, единица измерения мегабайт, значение варьируется от 8p до 232-1.
- Количество итераторов t повышает скорость работы. значение от 1 до 232-1.
- Номер версии v, один байт, значение 0x13.
- Безопасное значение K , длина от 0 до 232-1 байт.
- Дополнительные данные X, длина от 0 до 232-1 байт.
- Тип Argon2, 0 для Argon2d, 1 для Argon2i и 2 для Argon2id.
Эти входы могут быть представлены следующим кодом:
Inputs:
password (P): Bytes (0..232-1) Password (or message) to be hashed
salt (S): Bytes (8..232-1) Salt (16 bytes recommended for password hashing)
parallelism (p): Number (1..224-1) Degree of parallelism (i.e. number of threads)
tagLength (T): Number (4..232-1) Desired number of returned bytes
memorySizeKB (m): Number (8p..232-1) Amount of memory (in kibibytes) to use
iterations (t): Number (1..232-1) Number of iterations to perform
version (v): Number (0x13) The current version is 0x13 (19 decimal)
key (K): Bytes (0..232-1) Optional key (Errata: PDF says 0..32 bytes, RFC says 0..232 bytes)
associatedData (X): Bytes (0..232-1) Optional arbitrary extra data
hashType (y): Number (0=Argon2d, 1=Argon2i, 2=Argon2id)
Output:
tag: Bytes (tagLength) The resulting generated bytes, tagLength bytes long
Технологический поток
Давайте сначала посмотрим на поток алгоритма непараллельного Argon2:
Непараллельный Argon2 самый простой.
G на приведенном выше рисунке представляет функцию сжатия, которая получает два входа по 1024 байта и выводит один 1024 байт.
i представляет количество выполненных шагов, а φ(i) выше — это ввод, который берется из пространства памяти.
Для алгоритма, требовательного к памяти, очень важной задачей является создание исходной памяти. Далее, давайте посмотрим, как устроено начальное пространство памяти.
Во-первых, нам нужно построить H0, который представляет собой значение блока размером 64. С помощью H0 мы можем построить больше блоков. Формула для расчета H0 выглядит следующим образом:
H0 = H(p,τ,m,t,v,y,⟨P⟩,P,⟨S⟩,S,⟨K⟩,K,⟨X⟩,X)
Это функция H входных параметров, о которых мы упоминали ранее. Размер H0 составляет 64 байта.
Посмотрите на генерацию кода H0:
Generate initial 64-byte block H0.
All the input parameters are concatenated and input as a source of additional entropy.
Errata: RFC says H0 is 64-bits; PDF says H0 is 64-bytes.
Errata: RFC says the Hash is H^, the PDF says it's ℋ (but doesn't document what ℋ is). It's actually Blake2b.
Variable length items are prepended with their length as 32-bit little-endian integers.
buffer ← parallelism ∥ tagLength ∥ memorySizeKB ∥ iterations ∥ version ∥ hashType
∥ Length(password) ∥ Password
∥ Length(salt) ∥ salt
∥ Length(key) ∥ key
∥ Length(associatedData) ∥ associatedData
H0 ← Blake2b(buffer, 64) //default hash size of Blake2b is 64-bytes
Для степени параллелизма p входных параметров память необходимо разбить на матрицу памятиB[i][j], которая представляет собой матрицу из p строк.
Вычислить значение матрицы B:
где H' — алгоритм хеширования переменной длины, основанный на H.
Приведем реализацию этого алгоритма:
Function Hash(message, digestSize)
Inputs:
message: Bytes (0..232-1) Message to be hashed
digestSize: Integer (1..232) Desired number of bytes to be returned
Output:
digest: Bytes (digestSize) The resulting generated bytes, digestSize bytes long
Hash is a variable-length hash function, built using Blake2b, capable of generating
digests up to 232 bytes.
If the requested digestSize is 64-bytes or lower, then we use Blake2b directly
if (digestSize <= 64) then
return Blake2b(digestSize ∥ message, digestSize) //concatenate 32-bit little endian digestSize with the message bytes
For desired hashes over 64-bytes (e.g. 1024 bytes for Argon2 blocks),
we use Blake2b to generate twice the number of needed 64-byte blocks,
and then only use 32-bytes from each block
Calculate the number of whole blocks (knowing we're only going to use 32-bytes from each)
r ← Ceil(digestSize/32)-1;
Generate r whole blocks.
Initial block is generated from message
V1 ← Blake2b(digestSize ∥ message, 64);
Subsequent blocks are generated from previous blocks
for i ← 2 to r do
Vi ← Blake2b(Vi-1, 64)
Generate the final (possibly partial) block
partialBytesNeeded ← digestSize – 32*r;
Vr+1 ← Blake2b(Vr, partialBytesNeeded)
Concatenate the first 32-bytes of each block Vi
(except the possibly partial last block, which we take the whole thing)
Let Ai represent the lower 32-bytes of block Vi
return A1 ∥ A2 ∥ ... ∥ Ar ∥ Vr+1
Если у нас более одной итерации, то есть t > 1, мы вычисляем B для следующей итерации следующим образом:
После окончательного обхода T раз мы получаем окончательный B:
Наконец получил вывод:
Эта логика также может быть выражена в коде:
Calculate number of 1 KB blocks by rounding down memorySizeKB to the nearest multiple of 4*parallelism kibibytes
blockCount ← Floor(memorySizeKB, 4*parallelism)
Allocate two-dimensional array of 1 KiB blocks (parallelism rows x columnCount columns)
columnCount ← blockCount / parallelism; //In the RFC, columnCount is referred to as q
Compute the first and second block (i.e. column zero and one ) of each lane (i.e. row)
for i ← 0 to parallelism-1 do for each row
Bi[0] ← Hash(H0 ∥ 0 ∥ i, 1024) //Generate a 1024-byte digest
Bi[1] ← Hash(H0 ∥ 1 ∥ i, 1024) //Generate a 1024-byte digest
Compute remaining columns of each lane
for i ← 0 to parallelism-1 do //for each row
for j ← 2 to columnCount-1 do //for each subsequent column
//i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)
i′, j′ ← GetBlockIndexes(i, j) //the GetBlockIndexes function is not defined
Bi[j] = G(Bi[j-1], Bi′[j′]) //the G hash function is not defined
Further passes when iterations > 1
for nIteration ← 2 to iterations do
for i ← 0 to parallelism-1 do for each row
for j ← 0 to columnCount-1 do //for each subsequent column
//i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)
i′, j′ ← GetBlockIndexes(i, j)
if j == 0 then
Bi[0] = Bi[0] xor G(Bi[columnCount-1], Bi′[j′])
else
Bi[j] = Bi[j] xor G(Bi[j-1], Bi′[j′])
Compute final block C as the XOR of the last column of each row
C ← B0[columnCount-1]
for i ← 1 to parallelism-1 do
C ← C xor Bi[columnCount-1]
Compute output tag
return Hash(C, tagLength)
Эта статья была включена вwww.flydean.com/40-argon2/
Самая популярная интерпретация, самая глубокая галантерея, самые краткие уроки и множество трюков, о которых вы не знаете, ждут вас!
Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: «Программируйте эти вещи», разбирайтесь в технологиях, лучше поймите себя!