Русская Википедия:Lyra2
Шаблон:Карточка хеш-функции Lyra2 — это криптографическая хеш-функция, которая может также использоваться, как функция формирования ключа. Lyra2 была создана Маркосом Симплисио младшим, Леонардо К. Алмейда, Эвертоном Р. Андраде, Паулу К. Ф. Сантушем и Паулу С. Л. М. Баррето из Политехнической школы Университета Сан-Паулу[1]. Lyra2 является одним из широко используемых алгоритмов хеширования наряду с PBKDF2, bcrypt и scrypt. Тем не менее, до появления Lyra2 scrypt был единственным доступным решением, учитывающим затраты памяти и времени обработки. Lyra2 представил улучшения, такие как: разделение памяти и параметров обработки, что даёт дополнительную гибкость пользователям; использование одной базовой функции губки, а не двух, используемых в scrypt; более высокая устойчивость к атакам, использующим компромиссы между временем и памятью; и более высокая производительность, позволяющая увеличить использование памяти при аналогичном времени обработки[2].
Lyra2 находится в свободном доступе и имеет два расширения:[3]
- Lyra2-δ, дающее пользователю больший контроль над пропускной способностью.
- Lyra2p, использующее возможности параллелизма вычислительных систем пользователей алгоритма.
Устойчивость к атакам
Основные достоинства алгоритма:
- Затраты по памяти и по времени могут быть разделены, что позволяет использовать ресурсы более разумно.
- Быстрота за счёт использования функции губки с сокращённым количеством раундов в алгоритме.
- Предоставление выходных данных любой желаемой длины, поэтому может работать как функция формирования ключа.
Lyra2 может быть сконфигурирован как для защиты от атакующих платформ так и для оптимизации производительности на платформе пользователя:
- Поддержка параллелизма для мультипроцессорных систем.
- Возможность использовать различные основные функции губки.
- Возможность увеличить пропускную способность памяти для алгоритма.
Затраты на вычисления при атаке асимптотически лежат между <math>O(2^{nT}R^{3})</math> и <math>O(2^{nT}R^{n+2})</math> при использовании порядка <math>1/2^{n+2}</math> памяти на пользовательской платформе. Другие алгоритмы не уступают эти показателям, но на практике они имеют значение <math>O(R)</math> ниже, чем у Lyra2.[4][5][6][7][8]
Функция губки
Криптографические функции губки представляют собой хеш-функции, способные итеративно обрабатывать произвольные длины входных и выходных данных. Их конструкция включает в себя перестановку <math>f</math> фиксированной длины, которая работает с внутренним состоянием, представленным последовательностью размером <math>b + c</math> битов, состоящим из битрейта длиной <math>b</math> и ёмкостью длиной <math>c</math>, в сочетании с входными данными <math>M</math>, разрезанными на b-битные блоки. Функция губки включает в себя операцию absorb (впитывание), которая заключается в итеративном применении <math>f</math> к внутреннему состоянию после применения операции <math>XOR</math> битрейта с каждым из b-битных входных битов. Заметим, что количество итераций в этой операции задаётся параметром, числом раундов <math>\rho</math>. Операция squeeze (выжимание), в свою очередь, представляет собой применение <math>f</math> ко всему внутреннему состоянию и последующую выдачу битрейта на выход, эта операция будет выполняться, пока заданное пользователем количество битов не будет предоставлено в качестве вывода. Есть также операция duplex, которая представляет собой серию пар последовательно применённых операций absorb и squeeze.
Параметры алгоритма
Lyra2 предоставляет возможность сконфигурировать алгоритм наиболее подходящим образом для нужд пользователя. Это обеспечивается за счёт различных параметров алгоритма, таких как:[3]
- Время выполнения (затраты по времени)
- Требуемая память (количество строк и столбцов в матрице)
- Степень параллелизма (количество потоков)
- Основная функция губки
- Число блоков, используемых основной функцией губки (битрейт)
- Количество раундов для основной функции губки
- Длина выходной последовательности
Устройство алгоритма
Как и любая другая криптографическая хеш-функция Lyra2 принимает на вход соль и пароль, выдавая на выходе псевдослучайную последовательность. Внутренне её память организована как двумерный массив, чьи ячейки итеративно читаются и записываются, называемые просто матрицей памяти[2]. Также стоит заметить, что количество посещений ячейки матрицы для её пересчёта определяется пользователем, что позволяет настроить алгоритм в соответствии с возможностями вычислительных систем пользователя. Инициализация и посещение матрицы использует сочетание состояний операций absorb, squeeze и duplex основной функции губки, обеспечивая последовательный характер всего процесса. Кроме того, пользователи могут определять размер матрицы и количество повторных посещений её ячеек после инициализации, что позволяет точно настроить использование ресурсов Lyra2. Lyra2 состоит из четырёх последовательных фаз: bootstrapping, setup, wandering и wrap-up.
Bootstrapping
На этой стадии происходит инициализация внутреннего состояния основной функции губки. На вход основной функции губки поступают пароль, соль и другие параметры. Параметры обычно представлены длиной соли, пароля, параметром затрат по времени и по памяти, то есть теми которые задаются пользователем, также могут быть добавлены и другие. Происходит операция absorb с этими входными данными, и происходит инициализация внутреннего состояния функции губки.
Setup
На стадии Setup происходит инициализация матрицы памяти. Ячейки матрицы имеют длину <math>b</math> бит, то есть размер битрейта основной функции губки. Для повышения производительности при работе с потенциально большой матрицей памяти программа установки использует операцию 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 памяти при значениях параметров <math>T = 4</math> и <math>R = 2^{15}</math>[2].
Тесты были проведены на процессоре Intel Xeon E5-2430 (2,20 GHz, 12 ядер, 64-битная система) с 48 GB DRAM, на операционной системе Ubuntu 14.04 LTS 64 бит, код алгоритма был скомпилирован с помощью gcc 4.9.2[2].
Примечания
Ссылки
