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