[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

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

Argon2

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

История

править

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

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

Входные данные

править

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

Основные:

  • Сообщение (пароль)  , длиной от   до  .
  • Соль S, длиной от   до  .

Дополнительные:

  • Степень параллелизма  , любое целое число от   до   — количество потоков, на которое можно распараллелить алгоритм.
  • Длина тэга  , длиной от   до  .
  • Объём памяти  , целое число килобайтов от   до  
  • Количество итераций  [4]

Версии алгоритма

править

Существуют две версии алгоритма:

Описание

править
 
Схема работы Argon2

Argon2 работает по следующему принципу:

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

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

править

 

 ,  , где

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

Функции индексирования зависит от версии алгоритма Argon2:

  • Argon2d —   зависит от предыдущего блока
  • Argon2i —   значение, определяемое генератором случайных чисел.

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

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

 

 

 

 

 

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

В итоге:

 

  [5]

Нахождение опорного блока

править
  • Argon2d: выбираются первые 32 бита для   и следующие 32 бита для   из блоков  
  • Argon2i:  , где  - номер итерации,   — номер линии,   — задаёт версию (в данном случае единица)

Далее определяется индекс   строки, откуда берётся блок. При   за текущий номер линии принимается значение   . Затем определяется набор индексов   по 2 правилам:

  1. Если   совпадает с номером текущей строки, то в набор индексов добавляются все не записанные ранее блоки без  
  2. Если   не совпадает, то берутся блоки из всех сегментов линии и последних   частей.

В итоге, вычисляется номер блока из  , который принимается за опорный:

  [6]

Функция H'

править
 
Argon2

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

 

 

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

 

 

 

 

Функция сжатия G

править

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

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

править

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

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

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

Memory optimization attack

править

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

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

The ranking tradeoff attack

править

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

Garbage collector attacks

править

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

Применение

править

Argon2 оптимизирован под x86-архитектуру и может быть реализован на Linux, OS X, Windows.

Argon2d предназначен для систем, где злоумышленник не получает регулярного доступа к системной памяти или процессору. Например, для backend-серверов и криптомайнеров[источник не указан 859 дней]. При использовании одного ядра на 2-GHz CPU и 250 MB оперативной памяти с Argon2d (p=2) криптомайнинг занимает 0,1 с, а при применении 4 ядер и 4 GB памяти (p=8) аутентификация на backend сервере проходит за 0,5 с[источник не указан 859 дней].

Argon2i больше подходит для frontend-серверов и шифрования жёсткого диска[источник не указан 859 дней]. Формирование ключа для шифрования на 2-GHz CPU, используя 2 ядра и 6 GB оперативной памяти, с Argon2i (p=4) занимает 3 с, в то время как аутентификация на frontend-сервере, задействовав 2 ядра и 1 GB памяти с Argon2i (p=4), занимает 0,5 с[12].

Примечания

править
  1. 1 2 3 4 Password Hashing Competition.
  2. Argon, 2016, с. 293.
  3. Argon, 2016, с. 292.
  4. Argon, 2016, с. 294.
  5. Argon, 2016, с. 294—295.
  6. 1 2 Argon, 2016, с. 295.
  7. Argon, 2016, с. 296—297.
  8. Henry Corrigan-Gibbs, 2016.
  9. Alwen, Blocki, 2016.
  10. Argon, 2016, с. 297.
  11. Overview, 2015.
  12. Argon, 2016, с. 300.

Литература

править
  • Joel Alwen, Jeremiah Blocki. Efficiently Computing Data-Independent Memory-Hard Functions. — Advances in Cryptology – CRYPTO 2016, 2016. — P. 241—271. — ISBN 978-3-662-53008-5.
  • Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. — Advances in Cryptology – ASIACRYPT 2016, 2016. — P. 220—248. — ISBN 978-3-662-53887-6.
  • Password Hashing Competition.
  • Alex Biryukov, Daniel Dinu, Dmitry Khovratovich. Argon2: new generation of memory-hard functions for password hashing and other applications. — European Symposium on Security and Privacy, 2016.
  • Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Overview of the Candidates for the Password Hashing Competition and their resistance against Garbage-Collector Attacks. — Technology and Practice of Passwords, 2015. — P. 3—18. — ISBN 978-3-319-24192-0.

Ссылки

править