Lyra2

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

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

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

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

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

Sponge функция

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

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

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

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

Bootstrapping

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

Setup

На стадии Setup происходит инициализация матрицы памяти. Ячейки матрицы имеют длину ${\displaystyle b}$ бит, то есть размер битрейта основной sponge функции. Для повышения производительности при работе с потенциально большой матрицей памяти программа установки использует операцию duplex sponge функции над столбцами матрицы памяти с меньшим числом раундов. Этот подход ускоряет операции губки и, таким образом, позволяет охватить больше позиций памяти в заданном интервале при заданных ограничениях на затраты по времени, чем при полном цикле 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 # Sponge функция с максимальным количеством раундов p_max
Param: p # Количество раундов для фаз Setup и Wandering, p < p_max
Param: Hp # Sponge функция с уменьшенным количеством раундов 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 памяти при значениях параметров ${\displaystyle T=4}$ и ${\displaystyle 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]

• Lyra2’s website
• Lyra2 source code repository on Github