Lyra2

Lyra2
Lyra2
Создан	2014
Опубликован	2014
Тип	хеш-функция

Lyra2 — криптографическая хеш-функция, которая может также использоваться, как функция формирования ключа. Lyra2 была создана Маркосом Симплисио младшим, Леонардо К. Алмейда, Эвертоном Р. Андраде, Паулу К. Ф. Сантушем и Паулу С. Л. М. Баррето из Политехнической школы Университета Сан-Паулу^[1]. Lyra2 является одним из широко используемых алгоритмов хеширования наряду с PBKDF2, bcrypt и scrypt. Тем не менее, до появления Lyra2 scrypt был единственным доступным решением, учитывающим затраты памяти и времени обработки. Lyra2 представил улучшения, такие как: разделение памяти и параметров обработки, что даёт дополнительную гибкость пользователям; использование одной базовой функции губки, а не двух, используемых в scrypt; более высокая устойчивость к атакам, использующим компромиссы между временем и памятью; и более высокая производительность, позволяющая увеличить использование памяти при аналогичном времени обработки^[2].

Lyra2 находится в свободном доступе и имеет два расширения:^[3]

Lyra2-δ, дающее пользователю больший контроль над пропускной способностью.
Lyra2p, использующее возможности параллелизма вычислительных систем пользователей алгоритма.

Устойчивость к атакам

Основные достоинства алгоритма:

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

Lyra2 может быть сконфигурирован как для защиты от атакующих платформ так и для оптимизации производительности на платформе пользователя:

Поддержка параллелизма для мультипроцессорных систем.
Возможность использовать различные основные функции губки.
Возможность увеличить пропускную способность памяти для алгоритма.

Затраты на вычисления при атаке асимптотически лежат между $O(2^{nT}R^{3})$ и $O(2^{nT}R^{n+2})$ при использовании порядка $1/2^{n+2}$ памяти на пользовательской платформе. Другие алгоритмы не уступают эти показателям, но на практике они имеют значение $O(R)$ ниже, чем у Lyra2.^[4]^[5]^[6]^[7]^[8]

Функция губки

Криптографические функции губки представляют собой хеш-функции, способные итеративно обрабатывать произвольные длины входных и выходных данных. Их конструкция включает в себя перестановку $f$ фиксированной длины, которая работает с внутренним состоянием, представленным последовательностью размером $b+c$ битов, состоящим из битрейта длиной $b$ и ёмкостью длиной $c$ , в сочетании с входными данными $M$ , разрезанными на b-битные блоки. Функция губки включает в себя операцию absorb (впитывание), которая заключается в итеративном применении $f$ к внутреннему состоянию после применения операции $XOR$ битрейта с каждым из b-битных входных битов. Заметим, что количество итераций в этой операции задаётся параметром, числом раундов $\rho$ . Операция squeeze (выжимание), в свою очередь, представляет собой применение $f$ ко всему внутреннему состоянию и последующую выдачу битрейта на выход, эта операция будет выполняться, пока заданное пользователем количество битов не будет предоставлено в качестве вывода. Есть также операция duplex, которая представляет собой серию пар последовательно применённых операций absorb и squeeze.

Параметры алгоритма

Lyra2 предоставляет возможность сконфигурировать алгоритм наиболее подходящим образом для нужд пользователя. Это обеспечивается за счёт различных параметров алгоритма, таких как:^[3]

Время выполнения (затраты по времени)
Требуемая память (количество строк и столбцов в матрице)
Степень параллелизма (количество потоков)
Основная функция губки
Число блоков, используемых основной функцией губки (битрейт)
Количество раундов для основной функции губки
Длина выходной последовательности

Устройство алгоритма

Как и любая другая криптографическая хеш-функция Lyra2 принимает на вход соль и пароль, выдавая на выходе псевдослучайную последовательность. Внутренне её память организована как двумерный массив, чьи ячейки итеративно читаются и записываются, называемые просто матрицей памяти^[2]. Также стоит заметить, что количество посещений ячейки матрицы для её пересчёта определяется пользователем, что позволяет настроить алгоритм в соответствии с возможностями вычислительных систем пользователя. Инициализация и посещение матрицы использует сочетание состояний операций absorb, squeeze и duplex основной функции губки, обеспечивая последовательный характер всего процесса. Кроме того, пользователи могут определять размер матрицы и количество повторных посещений её ячеек после инициализации, что позволяет точно настроить использование ресурсов Lyra2. Lyra2 состоит из четырёх последовательных фаз: bootstrapping, setup, wandering и wrap-up.

Bootstrapping

На этой стадии происходит инициализация внутреннего состояния основной функции губки. На вход основной функции губки поступают пароль, соль и другие параметры. Параметры обычно представлены длиной соли, пароля, параметром затрат по времени и по памяти, то есть теми которые задаются пользователем, также могут быть добавлены и другие. Происходит операция absorb с этими входными данными, и происходит инициализация внутреннего состояния функции губки.

Setup

На стадии Setup происходит инициализация матрицы памяти. Ячейки матрицы имеют длину $b$ бит, то есть размер битрейта основной функции губки. Для повышения производительности при работе с потенциально большой матрицей памяти программа установки использует операцию duplex функции губки над столбцами матрицы памяти с меньшим числом раундов. Этот подход ускоряет операции губки и, таким образом, позволяет охватить больше позиций памяти в заданном интервале при заданных ограничениях на затраты по времени, чем при полном цикле f. Эта фаза заканчивается, когда все столбцы матрицы памяти были посещены.

Wandering

Фаза блуждания заключается в псевдослучайной перезаписи ячеек матрицы памяти с использованием операции duplex над столбцами так же, как и в фазе Setup. Количество итераций на этом этапе ограничено параметром затрат по времени.

Wrap-up

На этом этапе происходит применение операции absorb с максимальным количество раундов, а затем операции squeeze, и получение на выходе псевдослучайной последовательности заданного размера.

Обозначения
Символы ⊕ обозначают побитовое исключающее или (XOR), в то время как ⊞ 
обозначает сложение машинных слов. Конкатенация между массивами байтов a и b
записывается a || b. Для массива байтов x, обозначения |x| и len(x) означают, соответственно, 
длину x в битах и байтах (т. е. минимальное количество битов/байтов, необходимых для 
представления x). Подразумевается, что вычислительная машина имеет little-endian 
порядок байтов, в данном описании алгоритма lsw(x) возвращает наименее
значимое словом x, а rot^y (x) — w-битный циклический сдвиг x влево, повторенный y раз.

Param: H # Функция губки с максимальным количеством раундов p_max
Param: p # Количество раундов для фаз Setup и Wandering, p < p_max
Param: Hp # Функция губки с уменьшенным количеством раундов p
Param: w # Количество бит, используемых для циклического сдвига
Input: pwd # Пароль
Input: salt # Соль
Input: T # Параметр, определяющий затраты по времени
Input: R, C # Параметры, определяющие затраты по памяти 
Input: k # Длина выходной последовательности в битах
Output: K # Зависящий от пароля хеш длиной k бит

Bootstrapping
Params <- len(k) || len(pwd) || len(salt) || T || R || C # Представляем параметры в виде последовательности байт
H.absorb(pad(pwd || salt || params)) # Разделяем последовательность на подпоследовательности длиной b бит
Prev0 <- 2 ; row1 <- 1 ; prev1 <- 0

Setup
For (col <- 0 to C-1) do {M[0][C-1-col] <- Hp.squeeze(b)} end for # Инициализируем M[0]
For (col <- 0 to C-1) do {M[1][C-1-col] <- M[0][col] ⊕ Hp.duplex(M[0][col], b)} end for # Инициализируем M[1]
For (col <- 0 to C-1) do {M[2][C-1-col] <- M[1][col] ⊕ Hp.duplex(M[1][col], b)} end for # Инициализируем M[2]

For (row0 <- 3 to R-1) do # Инициализируем оставшиеся строки
	For (col <- 0 to C-1) do # Итерация по столбцам, здесь инициализируется M[row0] и перезаписывается M[row1]
		rand <- Hp.duplex(M[row1][col] ⊞ M[prev0][col] ⊞ M[prev1][col], b)
		M[row0][C-1-col] <- M[prev0][col] ⊕ rand
		M[row1][C-1-col] <- M[row1][col] ⊕ rot(rand) # rot(): вращение на w бит
	end for
	prev0 <- row0 ; prev1 <- row1 # Определяются строки, которые будут использоваться на следующей итерации
	getNext(row1) # Обновление row1 для следующей итерации
End for

Wandering
For (wCount <- 0 to R*T - 1) do # 2*R*T строк будут перезаписаны псевдослучайным образом
	row0 <- lsw(rand) mod R ; row1 <- lsw(rot(rand)) mod R # Псевдослучайно выбираются строчки
	for (col <- 0 to C-1) do
		col0 <- lsw(rot^2(rand)) mod C ; col1 <- lsw(rot^3(rand)) mod C # Псевдослучайно выбираются столбцы
		rand <- Hp.duplex(M[row0][col] ⊞ M[row1][col] ⊞ M[prev0][col] ⊞ M[prev1][col], b)
		M[row0][col] <- M[row0][col] ⊕ rand # Перезапись псевдослучайной ячейки
		M[row1][col] <- M[row1][col] ⊕ rot(rand) # rot(): вращение на w бит
	end for
	prev0 <- row0 ; prev1 <- row1 # Определяются строки, которые будут использоваться на следующей итерации
End for

Wrap-up
H.absorb(M[row0][0])
K <- H.squeeze(k)

Return K

Производительность

Lyra2 позволяет произвести вычисления мене чем за 1 секунду при использовании 400 MB памяти при значениях параметров $T=4$ и $R=2^{15}$ ^[2].

Тесты были проведены на процессоре Intel Xeon E5-2430 (2,20 GHz, 12 ядер, 64-битная система) с 48 GB DRAM, на операционной системе Ubuntu 14.04 LTS 64 бит, код алгоритма был скомпилирован с помощью gcc 4.9.2^[2].

Примечания

↑ Cryptology ePrint Archive: Report 2015/136 (неопр.). eprint.iacr.org. Дата обращения: 22 марта 2016. Архивировано 9 марта 2016 года.
↑ ¹ ² ³ ⁴ Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. Lyra2: efficient password hashing with high security against time-memory trade-offs (англ.) // IEEE Transactions on Computers^[англ.] : journal. — 2016. — 1 January (vol. PP, no. 99). — P. 3096—3108. — ISSN 0018-9340. — doi:10.1109/TC.2016.2516011.
↑ ¹ ² Simplicio Jr, Marcos A.; Almeida, Leonardo C.; Andrade, Ewerton R.; Santos, Paulo C.; Barreto, Paulo S. L. M. The Lyra2 reference guide (неопр.). PHC. The Password Hashing Competition. Дата обращения: 6 декабря 2019. Архивировано 30 ноября 2020 года.
↑ Gmane -- Another PHC candidates mechanical tests (неопр.). article.gmane.org. Дата обращения: 22 марта 2016. (недоступная ссылка)
↑ Gmane -- A review per day Lyra2 (неопр.). article.gmane.org. Дата обращения: 22 марта 2016. (недоступная ссылка)
↑ Gmane -- Lyra2 initial review (неопр.). article.gmane.org. Дата обращения: 22 марта 2016. (недоступная ссылка)
↑ Gmane -- Memory performance and ASIC attacks (неопр.). article.gmane.org. Дата обращения: 22 марта 2016. (недоступная ссылка)
↑ Gmane -- Quick analysis of Argon (неопр.). article.gmane.org. Дата обращения: 22 марта 2016. (недоступная ссылка)