Лира2

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

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

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

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

Сильные стороны [ править ]

Основные сильные стороны алгоритма заключаются в следующем: ^[5]^[10]

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

Дизайн [ править ]

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

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

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

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

Функции/символы [ изменить ]

||				Concatenate two strings
^				Bitwise XOR
[+]				Wordwise add operation (i.e., ignoring carries between words)
%				Modulus
W				The target machine's word size (usually, 32 or 64)
omega				Number of bits to be used in rotations (recommended: a multiple of the machine's word size, W)
>>>				Right rotation
rho				Number of rounds for reduced squeeze or duplexing operations
blen				Sponge's block size in bytes 
H or H_i			Sponge with block size blen (in bytes) and underlying permutation f
H.absorb(input)			Sponge's absorb operation on input
H.squeeze(len)			Sponge's squeeze operation of len bytes
H.squeeze_{rho}(len)		Sponge's squeeze operation of len bytes using rho rounds of f
H.duplexing(input,len)		Sponge's duplexing operation on input, producing len bytes
H.duplexing_{rho}(input,len)	Sponge's duplexing operation on input, using rho rounds of f, producing len bytes
pad(string)			Pads a string to a multiple of blen bytes (padding rule: 10*1)
lsw(input)			The least significant word of input
len(string)			Length of a string, in bytes
syncThreads()			Synchronize parallel threads
swap(input1,input2)		Swap the value of two inputs
C				Number of columns on the memory matrix (usually, 64, 128, 256, 512 or 1024)
P				Degree of parallelism (P >= 1 and (m_cost/2) % P = 0)

Входы [ править ]

пароль
соль
t_cost
m_cost
вне

Алгоритм без параллелизма [ править ]

** Bootstrapping phase: Initializes the sponge's state and local variables
# Byte representation of input parameters (others can be added)
params =  outlen || len(password) || len(salt) || t_cost || m_cost || C

# Initializes the sponge's state (after that, password can be overwritten)
H.absorb( pad(password || salt || params) )

# Initializes visitation step, window and first rows that will feed 
gap = 1
stp = 1
wnd = 2
sqrt = 2

prev0 = 2
row1 = 1
prev1 = 0

** Setup phase: Initializes a (m_cost x C) memory matrix, its cells having blen-byte cells

# Initializes M[0], M[1] and M[2]
for col = 0 to C-1
	M[0][C-1-col] = H.squeeze_{rho}(blen)
for col = 0 to C-1
	M[1][C-1-col] = H.duplexing_{rho}( M[0][col], blen)
for col = 0 to C-1
	M[2][C-1-col] = H.duplexing_{rho}( M[1][col], blen)

# Filling Loop: initializes remainder rows
for row0 = 3 to m_cost-1
	# Columns Loop: M[row0] is initialized and M[row1] is updated
	for col = 0 to C-1
		rand = H.duplexing_{rho}( M[row1][col] [+] M[prev0][col] [+] M[prev1][col], blen)
		M[row0][C-1-col] = M[prev0][col] ^ rand
		M[row1][col] = M[row1][col] ^ ( rand >>> omega )

	# Rows to be revisited in next loop
	prev0 = row0
	prev1 = row1
	row1 = (row1 + stp) % wnd

	# Window fully revisited
	if (row1 = 0)
		# Doubles window and adjusts step
		wnd = 2 * wnd
		stp = sqrt + gap
		gap = -gap
		
		# Doubles sqrt every other iteration
		if (gap = -1)
			sqrt = 2 * sqrt
	
** Wandering phase: Iteratively overwrites pseudorandom cells of the memory matrix

# Visitation Loop: (2 * m_cost * t_cost) rows revisited in pseudorandom fashion
for wCount = 0 to ( (m_cost * t_cost) - 1)
	# Picks pseudorandom rows
	row0 = lsw(rand) % m_cost
	row1 = lsw( rand >>> omega ) % m_cost

	# Columns Loop: updates both M[row0] and M[row1]
	for col = 0 to C-1
		# Picks pseudorandom columns
		col0 = lsw( ( rand >>> omega ) >>> omega ) % C
		col1 = lsw( ( ( rand >>> omega ) >>> omega ) >>> omega ) % C

		rand = H.duplexing_{rho}( M[row0][col] [+] M[row1][col] [+] M[prev0][col0] [+] M[prev1][col1], blen)
		M[row0][col] = M[row0][col] ^ rand
		M[row1][col] = M[row1][col] ^ ( rand >>> omega )

	# Next iteration revisits most recently updated rows
	prev0 = row0
	prev1 = row1

** Wrap-up phase: output computation

# Absorbs a final column with a full-round sponge
H.absorb( M[row0][0] )

# Squeezes outlen bits with a full-round sponge
output = H.squeeze(outlen)

# Provides outlen-long bitstring as output
return output

Алгоритм с параллелизмом [ править ]

for each i in [0..P]
	** Bootstrapping phase: Initializes the sponge's state and local variables
	
	# Byte representation of input parameters (others can be added)
	params =  outlen || len(password) || len(salt) || t_cost || m_cost || C || P || i

	# Initializes the sponge's state (after that, password can be overwritten)
	H_i.absorb( pad(password || salt || params) )

	# Initializes visitation step, window and first rows that will feed 
	gap = 1
	stp = 1
	wnd = 2
	sqrt = 2
	sync = 4
	j = i

	prev0 = 2
	rowP = 1
	prevP = 0

	** Setup phase: Initializes a (m_cost x C) memory matrix, its cells having blen-byte cells

	# Initializes M_i[0], M_i[1] and M_i[2]
	for col = 0 to C-1
		M_i[0][C-1-col] = H_i.squeeze_{rho}(blen)
	for col = 0 to C-1
		M_i[1][C-1-col] = H_i.duplexing_{rho}( M_i[0][col], blen)
	for col = 0 to C-1
		M_i[2][C-1-col] = H_i.duplexing_{rho}( M_i[1][col], blen)

	# Filling Loop: initializes remainder rows
	for row0 = 3 to ( (m_cost / P) - 1 )
		# Columns Loop: M_i[row0] is initialized and M_j[row1] is updated
		for col = 0 to C-1
			rand = H_i.duplexing_{rho}( M_j[rowP][col] [+] M_i[prev0][col] [+] M_j[prevP][col], blen)
			M_i[row0][C-1-col] = M_i[prev0][col] ^ rand
			M_j[rowP][col] = M_j[rowP][col] ^ ( rand >>> omega )

		# Rows to be revisited in next loop
		prev0 = row0
		prevP = rowP
		rowP = (rowP + stp) % wnd

		# Window fully revisited
		if (rowP = 0)
			# Doubles window and adjusts step
			wnd = 2 * wnd
			stp = sqrt + gap
			gap = -gap
		
			# Doubles sqrt every other iteration
			if (gap = -1)
				sqrt = 2 * sqrt
		
		# Synchronize point
		if (row0 = sync)
			sync = sync + (sqrt / 2)
			j = (j + 1) % P
			syncThreads()

	syncThreads()
	
	** Wandering phase: Iteratively overwrites pseudorandom cells of the memory matrix

	wnd = m_cost / (2 * P)
	sync = sqrt
	off0 = 0
	offP = wnd

	# Visitation Loop: (2 * m_cost * t_cost / P) rows revisited in pseudorandom fashion
	for wCount = 0 to ( ( (m_cost * t_cost) / P) - 1)
		# Picks pseudorandom rows and slices (j)
		row0 = off0 + (lsw(rand) % wnd)
		rowP = offP + (lsw( rand >>> omega ) % wnd)
		j = lsw( ( rand >>> omega ) >>> omega ) % P

		# Columns Loop: update M_i[row0]
		for col = 0 to C-1
			# Picks pseudorandom column	
			col0 = lsw( ( ( rand >>> omega ) >>> omega ) >>> omega ) % C

			rand = H_i.duplexing_{rho}( M_i[row0][col] [+] M_i[prev0][col0] [+] M_j[rowP][col], blen)
			M_i[row0][col] = M_i[row0][col] ^ rand

		# Next iteration revisits most recently updated rows
		prev0 = row0
		
		# Synchronize point
		if (wCount = sync)
			sync = sync + sqrt
			swap(off0,offP)
			syncThreads()

	syncThreads()

	** Wrap-up phase: output computation

	# Absorbs a final column with a full-round sponge
	H_i.absorb( M_i[row0][0] )

	# Squeezes outlen bits with a full-round sponge
	output_i = H_i.squeeze(outlen)

# Provides outlen-long bitstring as output
return output_0 ^ ... ^ output_{P-1}

Анализ безопасности [ править ]

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

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

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

Производительность [ править ]

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

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

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

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

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

Ссылки [ править ]

^ «Конкурс хеширования паролей» . пароль-хеширование.net . Проверено 22 марта 2016 г.
^ «Лира2РЕв2» . eprint.iacr.org . Проверено 22 марта 2016 г.
^ «Верткоин» . vertcoin.org . Проверено 8 октября 2019 г.
^ «МонаКоин» . Монакоин.орг . Проверено 8 октября 2019 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ван Бейрендонк, М.; Трюдо, Л.; Джард, П.; Балацукас-Стимминг, А. (29 мая 2019 г.). Ядро Lyra2 FPGA для криптовалют на основе Lyra2REv2 . Международный симпозиум IEEE по схемам и системам (ISCAS). Саппоро, Япония: IEEE. стр. 1–5. arXiv : 1807.05764 . дои : 10.1109/ISCAS.2019.8702498 .
^ «Архив криптологии ePrint: отчет 2015/136» . eprint.iacr.org . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б Алмейда, Леонардо К.; Андраде, Эвертон Р.; Баррето, Пауло СЛМ; Симплисио-младший, Маркос А. (04 января 2014 г.). «Лира: получение ключа на основе пароля с настраиваемой памятью и затратами на обработку». Журнал криптографической инженерии . 4 (2): 75–89. CiteSeerX 10.1.1.642.8519 . дои : 10.1007/s13389-013-0063-5 . ISSN 2190-8508 . S2CID 5245769 .
^ «Архив криптологии ePrint: отчет 2014/030» . eprint.iacr.org . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б ^с Андраде, Э.; Симпличио-младший, М.; Баррето, П.; Сантос, П. (01 января 2016 г.). «Lyra2: эффективное хеширование паролей с высокой степенью защиты от компромисса между временем и памятью». Транзакции IEEE на компьютерах . ПП (99): 3096–3108. дои : 10.1109/TC.2016.2516011 . ISSN 0018-9340 . S2CID 37232444 .
^ Jump up to: Перейти обратно: ^а ^б ^с Симпличио-младший, Маркос А.; АЛМЕЙДА, Леонардо К.; АНДРАДЕ, Эвертон Р.; САНТОС, Пауло К.; Баррето, Пауло СЛМ «Справочное руководство по Lyra2» (PDF) . ПМЦ . Соревнования по хешированию паролей.
^ Чен, Лили (2009). «Рекомендации по получению ключей с использованием псевдослучайных функций (пересмотренные)» (PDF) . Компьютерная безопасность . НИСТ. дои : 10.6028/NIST.SP.800-108 .
^ Персиваль, Колин. «Более надежный вывод ключей с помощью последовательных функций с жесткой памятью» (PDF) . ТАРСНАП . Техническая конференция BSD.
^ «Архив криптологии ePrint: отчет 2013/525» . eprint.iacr.org . Проверено 22 марта 2016 г.
^ Шмидт, Саша. «Реализация системы шифрования паролей Catena» (PDF) . Университет Баухаус в Веймаре . Факультет СМИ.
^ «PHC/phc-winner-argon2» (PDF) . Гитхаб . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б «Гмане — еще одни механические испытания кандидатов на ПМСП» . Article.gmane.org . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б "Гмане -- Обзор за день Лира2" . Article.gmane.org . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б «Гмане — первоначальный обзор Lyra2» . Article.gmane.org . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б «Гмане — Производительность памяти и атаки ASIC» . Article.gmane.org . Проверено 22 марта 2016 г.
^ Jump up to: Перейти обратно: ^а ^б «Гмане — Быстрый анализ аргона» . Article.gmane.org . Проверено 22 марта 2016 г.

Внешние ссылки [ править ]

[1] «Конкурс хеширования паролей» . пароль-хеширование.net . Проверено 22 марта 2016 г.

[Lyra2REv2-2] «Лира2РЕв2» . eprint.iacr.org . Проверено 22 марта 2016 г.

[vertcoin-3] «Верткоин» . vertcoin.org . Проверено 8 октября 2019 г.

[MonaCoin-4] «МонаКоин» . Монакоин.орг . Проверено 8 октября 2019 г.

[lyra2ToC-5] Jump up to: Перейти обратно: ^а ^б ^с ван Бейрендонк, М.; Трюдо, Л.; Джард, П.; Балацукас-Стимминг, А. (29 мая 2019 г.). Ядро Lyra2 FPGA для криптовалют на основе Lyra2REv2 . Международный симпозиум IEEE по схемам и системам (ISCAS). Саппоро, Япония: IEEE. стр. 1–5. arXiv : 1807.05764 . дои : 10.1109/ISCAS.2019.8702498 .

[:0-6] «Архив криптологии ePrint: отчет 2015/136» . eprint.iacr.org . Проверено 22 марта 2016 г.

[:1-7] Jump up to: Перейти обратно: ^а ^б Алмейда, Леонардо К.; Андраде, Эвертон Р.; Баррето, Пауло СЛМ; Симплисио-младший, Маркос А. (04 января 2014 г.). «Лира: получение ключа на основе пароля с настраиваемой памятью и затратами на обработку». Журнал криптографической инженерии . 4 (2): 75–89. CiteSeerX 10.1.1.642.8519 . дои : 10.1007/s13389-013-0063-5 . ISSN 2190-8508 . S2CID 5245769 .

[:8-8] «Архив криптологии ePrint: отчет 2014/030» . eprint.iacr.org . Проверено 22 марта 2016 г.

[lyra2ToC2-9] Jump up to: Перейти обратно: ^а ^б ^с Андраде, Э.; Симпличио-младший, М.; Баррето, П.; Сантос, П. (01 января 2016 г.). «Lyra2: эффективное хеширование паролей с высокой степенью защиты от компромисса между временем и памятью». Транзакции IEEE на компьютерах . ПП (99): 3096–3108. дои : 10.1109/TC.2016.2516011 . ISSN 0018-9340 . S2CID 37232444 .

[lyra2RefGuide-10] Jump up to: Перейти обратно: ^а ^б ^с Симпличио-младший, Маркос А.; АЛМЕЙДА, Леонардо К.; АНДРАДЕ, Эвертон Р.; САНТОС, Пауло К.; Баррето, Пауло СЛМ «Справочное руководство по Lyra2» (PDF) . ПМЦ . Соревнования по хешированию паролей.

[11] Чен, Лили (2009). «Рекомендации по получению ключей с использованием псевдослучайных функций (пересмотренные)» (PDF) . Компьютерная безопасность . НИСТ. дои : 10.6028/NIST.SP.800-108 .

[12] Персиваль, Колин. «Более надежный вывод ключей с помощью последовательных функций с жесткой памятью» (PDF) . ТАРСНАП . Техническая конференция BSD.

[13] «Архив криптологии ePrint: отчет 2013/525» . eprint.iacr.org . Проверено 22 марта 2016 г.

[14] Шмидт, Саша. «Реализация системы шифрования паролей Catena» (PDF) . Университет Баухаус в Веймаре . Факультет СМИ.

[15] «PHC/phc-winner-argon2» (PDF) . Гитхаб . Проверено 22 марта 2016 г.

[:3-16] Jump up to: Перейти обратно: ^а ^б «Гмане — еще одни механические испытания кандидатов на ПМСП» . Article.gmane.org . Проверено 22 марта 2016 г.

[:4-17] Jump up to: Перейти обратно: ^а ^б "Гмане -- Обзор за день Лира2" . Article.gmane.org . Проверено 22 марта 2016 г.

[:5-18] Jump up to: Перейти обратно: ^а ^б «Гмане — первоначальный обзор Lyra2» . Article.gmane.org . Проверено 22 марта 2016 г.

[:6-19] Jump up to: Перейти обратно: ^а ^б «Гмане — Производительность памяти и атаки ASIC» . Article.gmane.org . Проверено 22 марта 2016 г.

[:7-20] Jump up to: Перейти обратно: ^а ^б «Гмане — Быстрый анализ аргона» . Article.gmane.org . Проверено 22 марта 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]