Argon2

Argon2 — функция формирования ключа, разработанная Алексом Бирюковым (), Даниэлем Дину () и Дмитрием Ховратовичем () из Университета Люксембурга в 2015 году.

Это современный простой алгоритм, направленный на высокую скорость заполнения памяти и эффективное использование нескольких вычислительных блоков. Алгоритм выпущен под лицензией Creative Commons.

История В 2013 году был объявлен конкурс о создании новой функции хеширования паролей. К новому алгоритму предъявлялись требования по объёму используемой памяти, количеству проходов по блокам памяти и по устойчивости к криптоанализу.

В 2015 году Argon2 был объявлен победителем конкурса. С того времени алгоритм претерпел 4 серьёзных изменения. Исправлены часть описаний алгоритмов генерации некоторых блоков и опечатки, добавлены рекомендуемые параметры.

Входные данные Argon2 использует основные и дополнительные параметры для хеширования:

Основные: Сообщение (пароль) , длиной от до . Соль S, длиной от до . Дополнительные: Степень параллелизма , любое целое число от до  — количество потоков, на которое можно распараллелить алгоритм. Длина тэга , длиной от до . Объём памяти , целое число килобайтов от до Количество итераций

Версии алгоритма Существуют две версии алгоритма: Argon2d — подходит для защиты цифровой валюты и информационных систем, не подверженных атакам по сторонним каналам. Argon2i — обеспечивает высокую защиту от trade-off атак, но работает медленнее версии d из-за нескольких проходов по памяти.

Описание

Argon2 работает по следующему принципу: Производится хеширование пароля с использованием хеш-функции Blake2b. Результат хеширования записывается в блоки памяти. Блоки памяти преобразуются с использованием функции сжатия В результате работы алгоритма генерируется ключ ().

Заполнение блоков памяти

, , где

 — функция индексирования,  — массив памяти,  — функция сжатия,  — сообщение(пароль),  — хеш-функция Blake2b.

Функции индексирования зависит от версии алгоритма Argon2: Argon2d — зависит от предыдущего блока

Argon2i — значение, определяемое генератором случайных чисел. В случае последовательного режима работы функция сжатия применяется раз. Для версии Argon2d на -м шаге на вход функции подаётся блок с индексом , определяемый предыдущим блоком . Для версии Argon2i берётся значение генератора случайных чисел ( в режиме счётчика).

В случае параллельного режима (алгоритм распараллеливается на тредов) данные распределятся по блокам матрицы , где первые блоки — результат хеширования входных данных, а следующие задаются функцией сжатия по предыдущим блокам и опорному блоку :

, где  — количество блоков памяти размером 1024 байта,  — хеш-функция, принимающая на вход 32-битное представление входных параметров, на выходе которой — 64-битное значение,  — хеш-функция переменной длины от ,  — объём памяти,  — количество итераций.

В итоге:

Нахождение опорного блока Argon2d: выбираются первые 32 бита для и следующие 32 бита для из блоков Argon2i: , где - номер итерации,  — номер линии,  — задаёт версию (в данном случае единица) Далее определяется индекс строки, откуда берётся блок. При за текущий номер линии принимается значение . Затем определяется набор индексов по 2 правилам: Если совпадает с номером текущей строки, то в набор индексов добавляются все не записанные ранее блоки без Если не совпадает, то берутся блоки из всех сегментов линии и последних частей. В итоге, вычисляется номер блока из , который принимается за опорный:

Функция H'

Blake2b — 64 битная версия функции BLAKE, поэтому строится следующим образом:

При больших выходное значение функции строится по первым 32 битам блоков — и последнему блоку :

Функция сжатия G Основана на функции сжатия Blake2b. На вход получает два 8192-битных блока и вырабатывает 1024-битный блок. Сначала два блока складываются (), затем матрица обрабатывается функцией построчно (), затем получившаяся матрица обрабатывается по столбцам (), и на выходе выдаётся .

Криптоанализ Защита от коллизий: сама функция Blake2b считается криптографически безопасной. Также, ссылаясь на правила индексирования, авторы алгоритма доказали отсутствие коллизий внутри блоков данных и низкую вероятность их появления при применении функции сжатия.

Атака нахождения прообраза: пусть злоумышленник подобрал такое, что , тогда для продолжения данной атаки он должен подобрать прообраз : , что невозможно. Такое же рассуждение подходит для атаки нахождения второго прообраза.

Атаки по времени: если пользователю необходимо адаптироваться к атаке по времени, то следует использовать версию Argon2i, так как она использует независимую память.

Атаки

Memory optimization attack Дэн Боне, Henry Corrigan-Gibbs и Stuart Schechter в своей работе показали уязвимость Argon2i версии 1.2. Для однопроходной версии их атака снижала расход памяти в 4 раза без замедления выполнения. Для многопроходной версии — в 2,72 раза. Позднее, в версии 1.3 операция перезаписи была заменена на XOR.

AB16 Joel Alwen и Jeremiah Blocki в своих работах доказали, что их алгоритм атаки AB16 эффективен не только для Argon2i-A (из первой версии спецификации), но и для Argon2i-B (из последней версии 1.3). Они показали, что атака на Argon2 при , используя 1 GB ОЗУ, снижает время вычисления в два раза. Для эффективной защиты необходимо задать больше 10 проходов. Но при рекомендуемом подходе выбора параметров алгоритма на практике часто может выбираться всего лишь 1 проход. Разработчики Argon2 утверждают, что, применяя атаку AB16 на Argon2i-B при , время уменьшается не более чем в 2 раза вплоть до использования 32 GB памяти и рекомендуют использовать число проходов, превышающее значение двоичного логарифма от размера используемой памяти.

The ranking tradeoff attack Данная атака является одной из самых эффективных для Argon2d. Она снижает время обработки в 1,33 раза. Для Argon2i при коэффициент равен 3.

Garbage collector attacks Основным условием для представленной атаки является доступ злоумышленника к внутренней памяти целевой машины либо после прекращения схемы хеширования, либо в какой-то момент, когда сам пароль ещё присутствует в памяти. Благодаря перезаписи информации с помощью функции , Argon2i и Argon2d устойчивы к данным атакам.

Применение 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 с.

Примечания

Литература

Ссылки https://github.com/P-H-C/phc-winner-argon2 https://www.cryptolux.org/index.php/Argon2 https://github.com/khovratovich/Argon2 (ранняя версия функции)

Категория:Криптография