Аргон2 - Argon2

Аргон2 это ключевая деривационная функция который был выбран победителем Конкурс по хешированию паролей в июле 2015 года.[1][2] Он был разработан Алексей Бирюков, Даниэль Дину и Дмитрий Ховратович от Люксембургский университет.[3] Эталонная реализация Argon2 выпущена под лицензией Creative Commons. CC0 лицензия (т.е. всеобщее достояние ) или Лицензия Apache 2.0, и предоставляет три связанных версии:

  • Argon2d максимизирует устойчивость к атакам взлома GPU. Он обращается к массиву памяти в зависимости от пароля, что снижает вероятность компромисс между временем и памятью (TMTO) атак, но вводит возможные атаки по побочным каналам.
  • Argon2i оптимизирован для защиты от атак по побочным каналам. Он обращается к массиву памяти в независимом от пароля порядке.
  • Argon2id - гибридная версия. Он следует подходу Argon2i для первого полупрохода по памяти и подходу Argon2d для последующих проходов. Интернет-проект[4] рекомендует использовать Argon2id, кроме случаев, когда есть причины предпочесть один из двух других режимов.

Все три режима позволяют задавать параметры по трем параметрам, которые контролируют:

  • время исполнения
  • требуется память
  • степень параллелизма

Криптоанализ

Хотя публичного криптоанализа, применимого к Argon2d, не существует, есть две опубликованные атаки на функцию Argon2i. Первая атака применима только к старой версии Argon2i, а вторая была расширена до последней версии (1.3).[5]

Первая атака показывает, что можно вычислить однопроходную функцию Argon2i, используя от четверти до пятой части желаемого пространства, без потери времени, и вычислить многопроходную функцию Argon2i, используя только N/е < N/2.71 пробел без штрафа по времени.[6] По словам авторов Argon2, этот вектор атаки был исправлен в версии 1.3.[7]

Вторая атака показывает, что Argon2i можно вычислить с помощью алгоритма со сложностью O (п7/4 бревно(п)) для всех вариантов выбора параметров σ (стоимость помещения), τ (временные затраты) и количество потоков, такое что п=σ∗τ.[8] Авторы Argon2 утверждают, что эта атака неэффективна, если Argon2i используется с тремя или более проходами.[7] Однако Джоэль Алвен и Иеремия Блоки улучшили атаку и показали, что для того, чтобы атака не удалась, Argon2i 1.3 требует более 10 проходов по памяти.[5]

Алгоритм

Функция Аргон2 Входы:      пароль (п): Байты (0..232-1)    Пароль (или сообщение) для хеширования      соль (S): Байты (8..232-1)    Salt (рекомендуется 16 байт для хеширования паролей)      параллелизм (п): Число (1..224-1)   Степень параллелизма (т.е. количество потоков)      tagLength (Т): Число (4..232-1)   Желаемое количество возвращаемых байтов      memorySizeKB (м): Число (8p..232-1)  Объем памяти (в кибибайты ) использовать      итерации (т): Число (1..232-1)   Количество итераций для выполнения      версия (v): Число (0x13)     Текущая версия - 0x13 (19 в десятичной системе)      ключ (K): Байты (0..232-1)    Необязательный ключ (Опечатка: в PDF указано 0..32 байта, в RFC указано 0..232 байты)      connectedData (Икс): Байты (0..232-1)    Необязательные произвольные дополнительные данные      hashType (у): Число (0 = Argon2d, 1 = Argon2i, 2 = Argon2id) Выход:      тег: Байт (tagLength) Результирующие сгенерированные байты, tagLength bytes long   Сгенерировать начальный 64-байтовый блок H0.    Все входные параметры объединяются и вводятся как источник дополнительной энтропии. Исправление: RFC говорит H0 64-битный; PDF говорит H0 составляет 64 байта. Исправление: RFC говорит, что хеш - это H ^, в PDF указано, что это (но не документирует, что такое). На самом деле это Blake2b. К элементам переменной длины добавляется их длина в виде 32-битных целых чисел с прямым порядком байтов.   буфер ← параллелизм ∥ tagLength ∥ memorySizeKB ∥ итерации ∥ версия ∥ hashType ∥ Длина (пароль) ∥ Пароль ∥ Длина (соль) ∥ соль ∥ Длина (ключ) ∥ ключ ∥ Длина (associatedData) ∥ associatedData H0 ← Blake2b (буфер, 64) // размер хэша Blake2b по умолчанию составляет 64 байта   Вычислить количество блоков размером 1 КБ, округлив memorySizeKB до ближайшего значения, кратного 4 * параллелизму. кибибайты   blockCount ← Floor (memorySizeKB, 4 * параллелизм) Выделить двумерный массив из блоков размером 1 КиБ (строки параллелизма x столбцы columnCount)   columnCount ← blockCount / parallelism; // В RFC columnCount упоминается как q   Вычислить первый и второй блок (то есть нулевой и один столбцы) каждой полосы (то есть строки)   за я ← 0 к параллелизм-1 делать для каждой строки      Bя[0] ← Хеш (H0 ∥ 0 ∥ i, 1024) // Создаем 1024-байтовый дайджест      Bя[1] ← Хеш (H0 ∥ 1 ∥ я, 1024) // Создаем 1024-байтовый дайджест   Вычислить оставшиеся столбцы каждой полосы   за я ← 0 к параллелизм-1 делать // для каждой строки      за j ← 2 к columnCount-1 делать // для каждого последующего столбца         // индексы i 'и j' зависят от того, является ли это Argon2i, Argon2d или Argon2id (см. раздел 3.4)         i ′, j ′ ← GetBlockIndexes (i, j) // функция GetBlockIndexes не определена         Bя[j] = G (Bя[j-1], Bя'[j ′]) // хэш-функция G не определена   Далее проходит, когда итераций> 1   за Итерация ← 2 к итерации делать      за я ← 0 к параллелизм-1 делать для каждой строки        за j ← 0 к columnCount-1 делать // для каждого последующего столбца           // индексы i 'и j' зависят от того, является ли это Argon2i, Argon2d или Argon2id (см. раздел 3.4)           i ′, j ′ ← GetBlockIndexes (i, j) если j == 0 тогда              Bя[0] = Bя[0] xor G (Bя[columnCount-1], Bя'[j ′]) еще             Bя[j] = Bя[j] xor G (Bя[j-1], Bя'[j ′]) Вычислить последний блок C как XOR последнего столбца каждой строки   C ← B0[columnCount-1] за я ← 1 к параллелизм-1 делать      C ← C xor Bя[columnCount-1] Вычислить выходной тег   возвращаться Хэш (C, tagLength)

Хеш-функция переменной длины

Argon2 использует хеш-функцию, способную производить дайджесты до 232 длина в байтах. Эта хеш-функция внутренне построена на Blake2.

Функция Хеш (сообщение, размер дайджеста) Входы:      сообщение: байты (0..232-1)     Сообщение для хеширования      digestSize: Целое число (1..232)     Желаемое количество возвращаемых байтов   Выход:      дайджест: байты (digestSize) Полученные в результате сгенерированные байты, digestSize bytes long   Хеш - хэш-функция переменной длины, построенная с использованием Blake2b, способная генерировать дайджесты до 232 байты.   Если запрошенный размер дайджеста составляет 64 байта или меньше, мы используем Blake2b напрямую.   если (digestSize <= 64) тогда      возвращаться Blake2b (digestSize ∥ сообщение, digestSize) // объединение 32-битного little endian digestSize с байтами сообщения   Для желаемых хэшей размером более 64 байтов (например, 1024 байта для блоков Argon2) мы используем Blake2b для генерации в два раза большего количества необходимых 64-байтовых блоков, а затем используем только 32 байта из каждого блока.   Подсчитайте количество целых блоков (зная, что мы будем использовать только 32 байта из каждого)   r ← Ceil (digestSize / 32) -1; Сгенерируйте r целых блоков.   Первоначальный блок генерируется из сообщения   V1 ← Blake2b (digestSize ∥ сообщение, 64); Последующие блоки создаются из предыдущих блоков.   за я ← 2 к р делать      Vя ← Blake2b (Vя-1, 64)   Сгенерируйте последний (возможно, частичный) блок   partialBytesNeeded ← digestSize - 32 * r; Vг + 1 ← Blake2b (Vр, partialBytesNeeded) Объедините первые 32 байта каждого блока Vя   (кроме, возможно, частичного последнего блока, который мы берем целиком)   Пусть Aя представляют младшие 32 байта блока Vя   возвращаться А1 ∥ А2 ∥ ... ∥ Ар ∥ Vг + 1

Рекомендации

  1. ^ «Конкурс по хешированию паролей»
  2. ^ Йос Ветцельс (8 февраля 2016 г.). "Open Sesame: соревнование по хешированию паролей и Argon2" (PDF). arXiv:1602.03097.CS1 maint: использует параметр авторов (связь)
  3. ^ Argon2: функция жесткой памяти для хеширования паролей и других приложений, Алексей Бирюков и др., 1 октября 2015 г.
  4. ^ https://datatracker.ietf.org/doc/draft-irtf-cfrg-argon2/ Хеширование паролей Argon2 с жесткой памятью и функция доказательства работы, draft-irtf-cfrg-argon2-03, по состоянию на 16 августа 2017 г.
  5. ^ а б Джоэль Алвен, Иеремия Блоки (5 августа 2016 г.). «На пути к практическим атакам на Argon2i и хэширование шаров» (PDF). Цитировать журнал требует | журнал = (помощь)CS1 maint: использует параметр авторов (связь)
  6. ^ Генри Корриган-Гиббс, Дэн Боне, Стюарт Шехтер (14 января 2016 г.). «Воздушное хеширование: функции хеширования с ограниченным пространством и шаблонами доступа, не зависящими от данных» (PDF). Цитировать журнал требует | журнал = (помощь)CS1 maint: использует параметр авторов (связь)
  7. ^ а б "[Cfrg] Argon2 v.1.3". www.ietf.org. Получено 2016-10-30.
  8. ^ Джоэл Алвен, Иеремия Блоки (19 февраля 2016 г.). «Эффективное вычисление не зависящих от данных функций с жесткой памятью» (PDF). Цитировать журнал требует | журнал = (помощь)CS1 maint: использует параметр авторов (связь)

внешняя ссылка