Lyra2 - Lyra2

Lyra2 это схема хеширования паролей (PHS), который также может работать как ключевая деривационная функция (KDF). Особое признание получил во время Конкурс по хешированию паролей в июле 2015 года.^[1], который выиграл Аргон2. Помимо того, что он использовался для своих первоначальных целей, он также лежит в основе алгоритмов доказательства работы, таких как Lyra2REv2,^[2] принят Vertcoin,^[3] MonaCoin,^[4] среди других криптовалют^[5]Lyra2 был разработан Маркосом А. Симпличио-младшим, Леонардо К. Алмейда, Эвертоном Р. Андраде, Пауло К. Ф. душ Сантушем и Пауло С. Л. М. Баррето из Escola Politécnica da Universidade de São Paulo.^[6] Это улучшение по сравнению с Lyra,^[7][8] ранее предложенные теми же авторами. Lyra2 сохраняет безопасность, эффективность и гибкость своего предшественника, включая: (1) возможность конфигурировать желаемый объем памяти, время обработки и параллелизм, которые будут использоваться алгоритмом; и (2) способность обеспечивать высокое использование памяти со временем обработки, аналогичным полученному с зашифровать. Кроме того, по сравнению со своим предшественником он имеет следующие улучшения:^[9]

• это обеспечивает более высокий уровень защиты от атак с участием компромиссы времени и памяти
• это позволяет законным пользователям более эффективно извлекать выгоду из параллелизм возможности собственных платформ
• он включает настройки для увеличения затрат на строительство специализированное оборудование атаковать алгоритм
• это уравновешивает сопротивление против побочные угрозы и атаки, полагающиеся на более дешевые (а значит, и более медленные) устройства хранения данных
• Lyra2 выпущен под всеобщее достояние, и предоставляет два основных расширения:^[10]
• Lyra2-δ, дает пользователю лучший контроль над использованием полосы пропускания алгоритма
• Lyra2п, использует возможности параллелизма на платформе легального пользователя

Этот алгоритм позволяет параметризацию с точки зрения:^[10]

• время исполнения (временная стоимость ${\displaystyle T}$)
• требуется память (количество строк ${\displaystyle R}$, и количество столбцов ${\displaystyle C}$)
• степень параллелизма (количество потоки ${\displaystyle p}$)
• базовая функция перестановки (может рассматриваться как основной криптографический примитив)
• количество блоков, используемых базовой функцией перестановки (битрейт)
• количество раундов, выполненных для базовой функции перестановки (${\displaystyle \rho }$)
• количество бит, используемых при ротации (${\displaystyle \omega }$)
• длина вывода (${\displaystyle \kappa }$)

Сильные стороны

Основные сильные стороны алгоритма:^[5][10]

• Высокая устойчивость к компромиссам между обработкой и памятью: оценочные затраты на обработку атаки с низким использованием памяти включают фактор, который экспоненциально растет со временем из-за перерасчетов
• Можно разделить затраты на память и время, что позволяет точно настроить использование ресурсов.
• Быстро благодаря использованию в ядре алгоритма функции губки с уменьшенным округлением
• Может обеспечивать выходы любой желаемой длины, ведя себя как ключевая деривационная функция (KDF)
• Дизайн сочетает в себе устойчивость к атаки по побочным каналам (в течение всего этапа настройки) и атакам с дешевыми (а значит, и низкоскоростными) запоминающие устройства, стремясь сбалансировать такие противоречивые требования
• Рассматривает широкий спектр конфигураций для защиты от атакующих платформ при оптимизации работы на легитимной платформе, таких как:
  • Поддержка параллелизма для многоядерные платформы, не давая особого преимущества GPU -основанные атаки
  • Возможность использования различных базовых функций губки в зависимости от целевой платформы (например, BLAKE2b для программных реализаций; Кечак для аппаратных реализаций; BlaMka для дополнительной защиты от аппаратных платформ; так далее.)
  • Возможность увеличить использование полосы пропускания памяти алгоритма (примечание: исходная спецификация должна максимально увеличить пропускную способность на текущих машинах, но функция может быть полезна для будущего оборудования)

Дизайн

Как и любой PHS, Lyra2 принимает на вход соль и пароль, создавая псевдослучайный вывод, который затем может быть использован в качестве ключевого материала для криптографических алгоритмов или как аутентификация нить.^{[11][неудачная проверка ][нужна цитата ]}

Внутренне память схемы организована как матрица, которая, как ожидается, будет оставаться в памяти в течение всего процесса хеширования пароля: поскольку ее ячейки итеративно считываются и записываются, сброс ячейки для сохранения памяти приводит к необходимости пересчитывать ее всякий раз, когда к ней обращаются еще раз, до момента последнего изменения.^[5]

Построение и посещение матрицы выполняется с использованием комбинации операций поглощения, сжатия и дуплексирования нижележащего слоя. губка (т.е. его внутреннее состояние никогда не сбрасывается до нуля), что обеспечивает последовательный характер всего процесса.

Кроме того, количество повторных посещений ячеек матрицы после инициализации определяется пользователем, что позволяет точно настроить время выполнения Lyra2 в соответствии с ресурсами целевой платформы.

# *** Функции / символы ***# || Соединить две строки# ^ Побитовое XOR# [+] Пословное сложение (т.е. игнорирование переносов между словами)#% Модуль# W Размер слова целевой машины (обычно 32 или 64)# omega Количество битов, используемых при ротации (рекомендуется: кратное размеру машинного слова, W)# >>> Правое вращение# rho Количество раундов для сокращенного сжатия или дуплексных операцийРазмер блока # blen Sponge в байтах # H или H_i Sponge с размером блока blen (в байтах) и базовой перестановкой f# H.absorb (ввод) Операция поглощения губкой при вводе# H.squeeze (len) Операция сжатия губкой len байтов# H.squeeze_ {rho} (len) Операция сжатия губкой len байтов с использованием rho раундов f# H.duplexing (input, len) Дуплексная операция Sponge на входе, производящая len байтов# H.duplexing_ {rho} (input, len) Операция дуплексирования Sponge на входе с использованием rho раундов f, в результате получается len байтов# pad (строка) Дополняет строку до числа, кратного blen байтам (правило заполнения: 10 * 1)# lsw (input) Наименьшее значащее слово ввода# len (строка) Длина строки в байтах# syncThreads () Синхронизировать параллельные потоки# swap (input1, input2) Поменять местами значения двух входов# C Количество столбцов в матрице памяти (обычно 64, 128, 256, 512 или 1024)# P Степень параллелизма (P> = 1 и (m_cost / 2)% P = 0)# *** Входы ***# пароль# соль# t_cost# m_cost# outlen# *** Алгоритм без параллелизма ***# ** Фаза начальной загрузки: инициализирует состояние губки и локальные переменные# Байтовое представление входных параметров (могут быть добавлены другие)параметры =  Outlen || len(пароль) || len(соль) || t_cost || m_cost || C# Инициализирует состояние губки (после этого пароль можно перезаписать)ЧАС.впитывать( подушечка(пароль || соль || параметры) )# Инициализирует шаг посещения, окно и первые строки, которые будут кормить зазор = 1stp = 1wnd = 2sqrt = 2предыдущая0 = 2row1 = 1пред1 = 0# ** Этап настройки: инициализирует матрицу памяти (m_cost x C), ее ячейки имеют двухбайтовые ячейки# Инициализирует M [0], M [1] и M [2]за Col = 0 к C-1	M[0][C-1-Col] = ЧАС.сжимать_{ро}(блен)за Col = 0 к C-1	M[1][C-1-Col] = ЧАС.дуплексный_{ро}( M[0][Col], блен)за Col = 0 к C-1	M[2][C-1-Col] = ЧАС.дуплексный_{ро}( M[1][Col], блен)# Filling Loop: инициализирует оставшиеся строкиза row0 = 3 к m_cost-1	# Цикл столбцов: M [row0] инициализируется, а M [row1] обновляется	за Col = 0 к C-1		ранд = ЧАС.дуплексный_{ро}( M[row1][Col] [+] M[предыдущая0][Col] [+] M[пред1][Col], блен)		M[row0][C-1-Col] = M[предыдущая0][Col] ^ ранд		M[row1][Col] = M[row1][Col] ^ ( ранд >>> омега )	# Строки, которые будут пересмотрены в следующем цикле	предыдущая0 = row0	пред1 = row1	row1 = (row1 + stp) % wnd	# Окно полностью пересмотрено	если (row1 = 0)		# Двойное окно и регулирует шаг		wnd = 2 * wnd		stp = sqrt + зазор		зазор = -зазор				# Удваивает sqrt каждую вторую итерацию		если (зазор = -1)			sqrt = 2 * sqrt	# ** Фаза блуждания: итеративно перезаписывает псевдослучайные ячейки матрицы памяти.# Цикл посещения: (2 * m_cost * t_cost) строки пересмотрены псевдослучайным образомза wCount = 0 к ( (m_cost * t_cost) - 1)	# Выбирает псевдослучайные строки	row0 = lsw(ранд) % m_cost	row1 = lsw( ранд >>> омега ) % m_cost	# Columns Loop: обновляет M [row0] и M [row1]	за Col = 0 к C-1		# Выбирает псевдослучайные столбцы		col0 = lsw( ( ранд >>> омега ) >>> омега ) % C		col1 = lsw( ( ( ранд >>> омега ) >>> омега ) >>> омега ) % C		ранд = ЧАС.дуплексный_{ро}( M[row0][Col] [+] M[row1][Col] [+] M[предыдущая0][col0] [+] M[пред1][col1], блен)		M[row0][Col] = M[row0][Col] ^ ранд		M[row1][Col] = M[row1][Col] ^ ( ранд >>> омега )	# Следующая итерация повторяет последние обновленные строки	предыдущая0 = row0	пред1 = row1# ** Фаза подведения итогов: вычисление вывода# Поглощает последний столбик с помощью губки полного круглого сеченияЧАС.впитывать( M[row0][0] )# Выдавливает выступающие части губкой по периметру.выход = ЧАС.сжимать(Outlen)# Предоставляет на выходе длинную битовую строкувозвращаться выход# *** Алгоритм с параллелизмом ***за каждый я в [0,п[	# ** Фаза начальной загрузки: инициализирует состояние губки и локальные переменные		# Байтовое представление входных параметров (могут быть добавлены другие)	параметры =  Outlen || len(пароль) || len(соль) || t_cost || m_cost || C || п || я	# Инициализирует состояние губки (после этого пароль можно перезаписать)	Здравствуй.впитывать( подушечка(пароль || соль || параметры) )	# Инициализирует шаг посещения, окно и первые строки, которые будут кормить 	зазор = 1	stp = 1	wnd = 2	sqrt = 2	синхронизировать = 4	j = я	предыдущая0 = 2	rowP = 1	предП = 0	# ** Этап настройки: инициализирует матрицу памяти (m_cost x C), ее ячейки имеют двухбайтовые ячейки	# Инициализирует M_i [0], M_i [1] и M_i [2]	за Col = 0 к C-1		М_и[0][C-1-Col] = Здравствуй.сжимать_{ро}(блен)	за Col = 0 к C-1		М_и[1][C-1-Col] = Здравствуй.дуплексный_{ро}( М_и[0][Col], блен)	за Col = 0 к C-1		М_и[2][C-1-Col] = Здравствуй.дуплексный_{ро}( М_и[1][Col], блен)	# Filling Loop: инициализирует оставшиеся строки	за row0 = 3 к ( (m_cost / п) - 1 )		# Цикл столбцов: M_i [row0] инициализируется, а M_j [row1] обновляется		за Col = 0 к C-1			ранд = Здравствуй.дуплексный_{ро}( M_j[rowP][Col] [+] М_и[предыдущая0][Col] [+] M_j[предП][Col], блен)			М_и[row0][C-1-Col] = М_и[предыдущая0][Col] ^ ранд			M_j[rowP][Col] = M_j[rowP][Col] ^ ( ранд >>> омега )		# Строки, которые будут пересмотрены в следующем цикле		предыдущая0 = row0		предП = rowP		rowP = (rowP + stp) % wnd		# Окно полностью пересмотрено		если (rowP = 0)			# Двойное окно и регулирует шаг			wnd = 2 * wnd			stp = sqrt + зазор			зазор = -зазор					# Удваивает sqrt каждую вторую итерацию			если (зазор = -1)				sqrt = 2 * sqrt				# Синхронизировать точку		если (row0 = синхронизировать)			синхронизировать = синхронизировать + (sqrt / 2)			j = (j + 1) % п			syncThreads()	syncThreads()		# ** Фаза блуждания: итеративно перезаписывает псевдослучайные ячейки матрицы памяти.	wnd = m_cost / (2 * п)	синхронизировать = sqrt	выкл0 = 0	offP = wnd	# Цикл посещения: (2 * m_cost * t_cost / P) строки пересмотрены псевдослучайным образом	за wCount = 0 к ( ( (m_cost * t_cost) / п) - 1)		# Выбирает псевдослучайные строки и фрагменты (j)		row0 = выкл0 + (lsw(ранд) % wnd)		rowP = offP + (lsw( ранд >>> омега ) % wnd)		j = lsw( ( ранд >>> омега ) >>> омега ) % п		# Цикл столбцов: обновить M_i [row0]		за Col = 0 к C-1			# Выбирает псевдослучайный столбец			col0 = lsw( ( ( ранд >>> омега ) >>> омега ) >>> омега ) % C			ранд = Здравствуй.дуплексный_{ро}( М_и[row0][Col] [+] М_и[предыдущая0][col0] [+] M_j[rowP][Col], блен)			М_и[row0][Col] = М_и[row0][Col] ^ ранд		# Следующая итерация повторяет последние обновленные строки		предыдущая0 = row0				# Синхронизировать точку		если (wCount = синхронизировать)			синхронизировать = синхронизировать + sqrt			замена(выкл0,offP)			syncThreads()	syncThreads()	# ** Фаза подведения итогов: вычисление вывода	# Поглощает последний столбик с помощью губки полного круглого сечения	Здравствуй.впитывать( М_и[row0][0] )	# Выдавливает выступающие части губкой по периметру.	output_i = Здравствуй.сжимать(Outlen)# Предоставляет на выходе длинную строку битоввозвращаться output_0 ^ ... ^ выход_{п-1}

Анализ безопасности

В сравнении с Lyra2 стоимость обработки атак с использованием ${\displaystyle 1/2^{n+2}}$ от объема памяти, используемой законным пользователем, как ожидается, будет между ${\displaystyle O(2^{2nT}R^{3})}$ и ${\displaystyle O(2^{2nT}R^{n+2})}$, последнее является лучшей оценкой для ${\displaystyle n\gg 1}$, вместо ${\displaystyle O(R)}$ достигается, когда объем памяти ${\displaystyle O(R)}$, куда ${\displaystyle T}$ - это определяемый пользователем параметр для определения времени обработки.

Это хорошо сравнивается с зашифровать, который отображает стоимость ${\displaystyle O(R^{2})}$ когда использование памяти ${\displaystyle O(1)}$,^[12] и с другими решениями в литературе, для которых результаты обычно ${\displaystyle O(R^{T+1})}$.^{[7][13][14][15]}

Тем не менее, на практике эти решения обычно включают стоимость ${\displaystyle R}$ (использование памяти) ниже, чем у Lyra2 за то же время обработки.^{[16][17][18][19][20]}

Спектакль

Производительность Lyra2 с поддержкой SSE для C = 256, ρ = 1, p = 1 и различных настроек T и R по сравнению с финалистами Scrypt с поддержкой SSE и требовательным к памяти PHC с минимальными параметрами.

Время обработки, полученное с помощью одноядерной реализации Lyra2 SSE, показано на приведенном ниже рисунке. Эта цифра была извлечена из,^[21] и очень похож на тесты сторонних производителей, выполняемые в контексте PHC.^{[16][17][18][19][20]}

Изображенные результаты соответствуют среднему времени выполнения Lyra2, настроенного с ${\displaystyle C=256}$, ${\displaystyle \rho =1}$, ${\displaystyle b=768}$ бит (т.е. внутреннее состояние имеет 256 бит), и разные ${\displaystyle T}$ и ${\displaystyle R}$ настройки, дающие общее представление о возможных комбинациях параметров и соответствующем использовании ресурсов.

Как показано на этом рисунке, Lyra2 может выполняться за: менее 1 секунды при использовании до 400 МБ (с ${\displaystyle R=2^{14}}$ и ${\displaystyle T=5}$) или до 1 ГБ памяти (с ${\displaystyle R\approx 4.2\cdot 10^{4}}$ и ${\displaystyle T=1}$); или менее чем за 5 с с 1,6 ГБ (с ${\displaystyle R=2^{16}}$ и ${\displaystyle T=6}$).

Все тесты проводились на Intel Xeon E5-2430 (2,20 ГГц с 12 ядрами, 64 бит) с 48 ГБ DRAM, Бег Ubuntu 14.04 LTS 64 бита, а исходный код был скомпилирован с использованием gcc 4.9.2.^[21]

Рекомендации

1. «Конкурс по хешированию паролей». password-hashing.net. Получено 2016-03-22.
2. «Лира2РЕв2». eprint.iacr.org. Получено 2016-03-22.
3. «Верткойн». vertcoin.org. Получено 2019-10-08.
4. "MonaCoin". monacoin.org. Получено 2019-10-08.
5. van Beirendonck, M .; Trudeau, L .; Giard, P .; Балацукас-Стимминг, А. (29.05.2019). Ядро Lyra2 FPGA для криптовалют на основе Lyra2REv2. Международный симпозиум IEEE по схемам и системам (ISCAS). Саппоро, Япония: IEEE. С. 1–5. arXiv:1807.05764. Дои:10.1109 / ISCAS.2019.8702498.
6. «Архив Cryptology ePrint: отчет 2015/136». eprint.iacr.org. Получено 2016-03-22.
7. Алмейда, Леонардо Ц .; Andrade, Ewerton R .; Баррето, Пауло С. Л. М .; Симпличио-младший, Маркос А. (4 января 2014 г.). «Lyra: получение ключей на основе пароля с настраиваемой памятью и затратами на обработку». Журнал криптографической инженерии. 4 (2): 75–89. CiteSeerX  10.1.1.642.8519. Дои:10.1007 / s13389-013-0063-5. ISSN  2190-8508.
8. «Архив Cryptology ePrint: отчет 2014/030». eprint.iacr.org. Получено 2016-03-22.
9. Andrade, E .; Simplicio Jr, M .; Barreto, P .; Сантос, П. (01.01.2016). «Lyra2: эффективное хеширование паролей с высокой степенью защиты от компромиссов времени и памяти». Транзакции IEEE на компьютерах. PP (99): 3096–3108. Дои:10.1109 / TC.2016.2516011. ISSN  0018-9340.
10. Simplicio Jr, Marcos A .; Алмейда, Леонардо Ц .; Andrade, Ewerton R .; Santos, Paulo C .; Баррето, Пауло С. Л. М. "Справочное руководство по Lyra2" (PDF). ПМСП. Конкурс по хешированию паролей.
11. Чен, Лили (2009). «Рекомендации по получению ключей с использованием псевдослучайных функций (пересмотренная)» (PDF). Компьютерная безопасность. NIST. Дои:10.6028 / NIST.SP.800-108.
12. Персиваль, Колин. «Более надежный вывод ключей с помощью последовательных функций с жесткой памятью» (PDF). ТАРСНАП. Техническая конференция BSD.
13. «Архив Cryptology ePrint: отчет 2013/525». eprint.iacr.org. Получено 2016-03-22.
14. Шмидт, Саша. «Реализация фреймворка шифрования паролей Catena» (PDF). Bauhaus-Universität Weimar. Факультет СМИ.
15. "P-H-C / phc-Winner-argon2" (PDF). GitHub. Получено 2016-03-22.
16. «Гмане - Другой кандидат ПМСП на механические испытания». article.gmane.org. Получено 2016-03-22.
17. «Гмане - Обзор на день Lyra2». article.gmane.org. Получено 2016-03-22.
18. "Gmane - предварительная проверка Lyra2". article.gmane.org. Получено 2016-03-22.
19. «Gmane - Производительность памяти и атаки ASIC». article.gmane.org. Получено 2016-03-22.
20. «Гмане - Быстрый анализ аргона». article.gmane.org. Получено 2016-03-22.
21. Andrade, E .; Simplicio Jr, M .; Barreto, P .; Сантос, П. (01.01.2016). «Lyra2: эффективное хеширование паролей с высокой степенью защиты от компромиссов времени и памяти». Транзакции IEEE на компьютерах. PP (99): 3096–3108. Дои:10.1109 / TC.2016.2516011. ISSN  0018-9340.

внешняя ссылка

• Сайт Lyra2
• Репозиторий исходного кода Lyra2 на Github