Lyra2
Войти  |  Регистрация
Авторизация
» » Lyra2

Lyra2



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

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

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

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

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

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

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

    Затраты на вычисления при атаке асимптотически лежат между 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 предоставляет возможность сконфигурировать алгоритм наиболее подходящим образом для нужд пользователя. Это обеспечивается за счёт различных параметров алгоритма, таких как:

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

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

    Как и любая другая криптографическая хеш-функция 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.


    Добавлено Admin 15-02-2022, 09:00 Просмотров: 38
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent