Lyra2
| Lyra2 | |
|---|---|
| Создан | 2014 |
| Опубликован | 2014 |
| Тип | хеш-функция |
Lyra2 — криптографическая хеш-функция, которая может также использоваться, как функция формирования ключа. Lyra2 была создана Маркосом Симплисио младшим, Леонардо К. Алмейда, Эвертоном Р. Андраде, Паулу К. Ф. Сантушем и Паулу С. Л. М. Баррето из Политехнической школы Университета Сан-Паулу[1]. Lyra2 является одним из широко используемых алгоритмов хеширования наряду с PBKDF2, bcrypt и scrypt. Тем не менее, до появления Lyra2 scrypt был единственным доступным решением, учитывающим затраты памяти и времени обработки. Lyra2 представил улучшения, такие как: разделение памяти и параметров обработки, что даёт дополнительную гибкость пользователям; использование одной базовой функции губки, а не двух, используемых в scrypt; более высокая устойчивость к атакам, использующим компромиссы между временем и памятью; и более высокая производительность, позволяющая увеличить использование памяти при аналогичном времени обработки[2].
Lyra2 находится в свободном доступе и имеет два расширения:[3]
- Lyra2-δ, дающее пользователю больший контроль над пропускной способностью.
- Lyra2p, использующее возможности параллелизма вычислительных систем пользователей алгоритма.
Устойчивость к атакам
[править | править код]Основные достоинства алгоритма:
- Затраты по памяти и по времени могут быть разделены, что позволяет использовать ресурсы более разумно.
- Быстрота за счёт использования функции губки с сокращённым количеством раундов в алгоритме.
- Предоставление выходных данных любой желаемой длины, поэтому может работать как функция формирования ключа.
Lyra2 может быть сконфигурирован как для защиты от атакующих платформ так и для оптимизации производительности на платформе пользователя:
- Поддержка параллелизма для мультипроцессорных систем.
- Возможность использовать различные основные функции губки.
- Возможность увеличить пропускную способность памяти для алгоритма.
Затраты на вычисления при атаке асимптотически лежат между и при использовании порядка памяти на пользовательской платформе. Другие алгоритмы не уступают эти показателям, но на практике они имеют значение ниже, чем у Lyra2.[4][5][6][7][8]
Функция губки
[править | править код]
Криптографические функции губки представляют собой хеш-функции, способные итеративно обрабатывать произвольные длины входных и выходных данных. Их конструкция включает в себя перестановку фиксированной длины, которая работает с внутренним состоянием, представленным последовательностью размером битов, состоящим из битрейта длиной и ёмкостью длиной , в сочетании с входными данными , разрезанными на b-битные блоки. Функция губки включает в себя операцию absorb (впитывание), которая заключается в итеративном применении к внутреннему состоянию после применения операции битрейта с каждым из b-битных входных битов. Заметим, что количество итераций в этой операции задаётся параметром, числом раундов . Операция squeeze (выжимание), в свою очередь, представляет собой применение ко всему внутреннему состоянию и последующую выдачу битрейта на выход, эта операция будет выполняться, пока заданное пользователем количество битов не будет предоставлено в качестве вывода. Есть также операция duplex, которая представляет собой серию пар последовательно применённых операций absorb и squeeze.
Параметры алгоритма
[править | править код]Lyra2 предоставляет возможность сконфигурировать алгоритм наиболее подходящим образом для нужд пользователя. Это обеспечивается за счёт различных параметров алгоритма, таких как:[3]
- Время выполнения (затраты по времени)
- Требуемая память (количество строк и столбцов в матрице)
- Степень параллелизма (количество потоков)
- Основная функция губки
- Число блоков, используемых основной функцией губки (битрейт)
- Количество раундов для основной функции губки
- Длина выходной последовательности
Устройство алгоритма
[править | править код]Как и любая другая криптографическая хеш-функция Lyra2 принимает на вход соль и пароль, выдавая на выходе псевдослучайную последовательность. Внутренне её память организована как двумерный массив, чьи ячейки итеративно читаются и записываются, называемые просто матрицей памяти[2]. Также стоит заметить, что количество посещений ячейки матрицы для её пересчёта определяется пользователем, что позволяет настроить алгоритм в соответствии с возможностями вычислительных систем пользователя. Инициализация и посещение матрицы использует сочетание состояний операций absorb, squeeze и duplex основной функции губки, обеспечивая последовательный характер всего процесса. Кроме того, пользователи могут определять размер матрицы и количество повторных посещений её ячеек после инициализации, что позволяет точно настроить использование ресурсов Lyra2. Lyra2 состоит из четырёх последовательных фаз: bootstrapping, setup, wandering и wrap-up.
Bootstrapping
На этой стадии происходит инициализация внутреннего состояния основной функции губки. На вход основной функции губки поступают пароль, соль и другие параметры. Параметры обычно представлены длиной соли, пароля, параметром затрат по времени и по памяти, то есть теми которые задаются пользователем, также могут быть добавлены и другие. Происходит операция absorb с этими входными данными, и происходит инициализация внутреннего состояния функции губки.
Setup
На стадии Setup происходит инициализация матрицы памяти. Ячейки матрицы имеют длину бит, то есть размер битрейта основной функции губки. Для повышения производительности при работе с потенциально большой матрицей памяти программа установки использует операцию 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 памяти при значениях параметров и [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 года.
- ↑ 1 2 3 4 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.
- ↑ 1 2 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. (недоступная ссылка)
Ссылки
[править | править код]| Общего назначения | |
|---|---|
| Криптографические | |
| Функции формирования ключа | |
| Контрольное число (сравнение) | |
| Применение хешей | |
