ライラ2
Key derivative function

Lyra2は、鍵導出関数（KDF）としても機能するパスワードハッシュスキーム（PHS）です。2015年7月に開催されたパスワードハッシュコンペティション[1]でArgon2が優勝し、高い評価を得ました。Lyra2は、Lyra2REv2 [2]などのプルーフ・オブ・ワークアルゴリズムにも利用されており、Vertcoin [3]やMonaCoin [4]をはじめとする暗号通貨にも採用されています。[5]

Lyra2 は、サンパウロ大学のMarcos A. Simplicio Jr.、Leonardo C. Almeida、Ewerton R. Andrade、Paulo CF dos Santos、およびPaulo SLM Barretoによって設計されました。[6]同じチームによって作成されたLyra [7] [8]に基づいています。 Lyra2 には次のものが含まれます。

  • アルゴリズムに必要なメモリ量、処理時間、並列処理を構成する機能。
  • メモリ使用量が多く、処理時間はscryptと同様です。

さらに、それは：[9]

  • 時間とメモリのトレードオフに対してより高いセキュリティを提供します。
  • 正当なユーザーが、独自のプラットフォームの並列処理機能からよりよいメリットを得られるようになります。
  • アルゴリズムを攻撃するための専用ハードウェアを作成するコストが増加します。
  • 安価で低速なストレージ デバイスを使用して、サイド チャネルの脅威と攻撃に対する耐性をバランスさせます。

Lyra2はパブリックドメインにリリースされました。[要出典]

デザイン

他のPHSと同様に、Lyra2はソルトとパスワードを入力として受け取り、疑似乱数出力を作成します。この出力は暗号化アルゴリズムの鍵素材や認証文字列として使用できます。[10] [検証失敗] [要出典]

内部的には、この方式のメモリは行列として構成されており、パスワードハッシュ処理全体を通してメモリ内に保持されることが想定されています。セルは繰り返し読み書きされるため、メモリ節約のためにセルを破棄すると、最後に変更された時点まで、再度アクセスされるたびに再計算が必要になります。[5]

マトリックスの構築と訪問は、基礎となるスポンジの吸収、圧縮、および二重化操作の状態のある組み合わせを使用して行われます(つまり、その内部状態は決してゼロにリセットされません)。これにより、プロセス全体の順次性が保証されます。

また、初期化後にマトリックスのセルが再訪問される回数はユーザーが定義できるため、Lyra2 の実行時間をターゲット プラットフォームのリソースに応じて微調整できます。

入力

  • パスワード
  • 塩
  • t_cost - 実行時間
  • m_cost - 必要なメモリ
  • アウトレン

このアルゴリズムではさらに、以下のパラメータ化も可能となる: [11]

  • 並列度（スレッド 数） p {\displaystyle p}
  • 基礎となる順列関数（主要な暗号プリミティブと見なすことができます）
  • 基礎となる順列関数で使用されるブロック数（ビットレート）
  • 基礎となる順列関数（ ）に対して実行されたラウンド数 ρ {\displaystyle \rho }
  • 回転に使用するビット数（） ω {\displaystyle \omega }
  • 出力長( ) κ {\displaystyle \kappa }

関数/記号

||
2つの文字列を連結する
^
ビット単位のXOR
[+]
単語ごとの加算演算（つまり、単語間の繰り上がりを無視する）
%
係数
W
ターゲットマシンのワードサイズ（通常は32または64）
omega
回転に使用するビット数（推奨：マシンのワードサイズ W の倍数）
>>>
右回転
rho
圧縮または二重化操作のラウンド数
blen
スポンジのブロックサイズ（バイト）
H or H_i
ブロックサイズblen（バイト単位）と基礎となる順列fを持つスポンジ
H.absorb(input)
スポンジの入力吸収操作
H.squeeze(len)
スポンジのlenバイトのsqueeze操作
H.squeeze_{rho}(len)
スポンジのfのrhoラウンドを使用したlenバイトのsqueeze操作
H.duplexing(input,len)
入力に対するSpongeの二重化操作で、lenバイトが生成される
H.duplexing_{rho}(input,len)
スポンジの入力に対する二重化操作。fのrhoラウンドを使用してlenバイトを生成する。
pad(string)
文字列をblenバイトの倍数にパディングします（パディングルール：10*1）
lsw(input)
入力された単語の中で最も重要でない単語
len(string)
文字列の長さ（バイト単位）
syncThreads()
並列スレッドを同期する
swap(input1,input2)
2つの入力の値を交換する
C
メモリマトリックスの列数（通常は64、128、256、512、または1024）
P
並列度（P >= 1および(m_cost/2) % P == 0）

並列処理のないアルゴリズム

** ブートストラップフェーズ: スポンジの状態とローカル変数を初期化します
# 入力パラメータのバイト表現（他のパラメータも追加可能）
params = outlen || len(パスワード) || len(ソルト) || t_cost || m_cost || C

# スポンジの状態を初期化します（その後、パスワードを上書きできます）
H.absorb( pad(パスワード || ソルト || パラメータ) )

# 訪問ステップ、ウィンドウ、フィードされる最初の行を初期化します
ギャップ = 1
stp = 1
ウィンド = 2
平方根 = 2

前0 = 2
行1 = 1
前1 = 0

** セットアップフェーズ: (m_cost x C) のメモリマトリックスを初期化し、そのセルはblenバイトのセルを持つ

# M[0]、M[1]、M[2]を初期化します
col = 0 から C-1 まで
	M[0][C-1-col] = H.squeeze_{rho}(blen)
col = 0 から C-1 まで
	M[1][C-1-col] = H.duplexing_{rho}( M[0][col], blen)
col = 0 から C-1 まで
	M[2][C-1-col] = H.duplexing_{rho}( M[1][col], blen)

# ループの充填: 残りの行を初期化します
row0 = 3 から m_cost-1 まで
	# 列ループ: M[row0]が初期化され、M[row1]が更新されます
	col = 0 から C-1 まで
		rand = H.duplexing_{rho}( M[row1][col] [+] M[prev0][col] [+] M[prev1][col], blen)
		M[行0][C-1-列] = M[前0][列] ^ ランド
		M[行1][列] = M[行1][列] ^ ( ランド >>> オメガ )

	# 次のループで再度実行される行
	前0 = 行0
	前1 = 行1
	行1 = (行1 + stp) % wnd

	# ウィンドウを全面的に再検討
	（行1 = 0）の場合
		# ウィンドウを2倍にしてステップを調整します
		wnd = 2 * wnd
		stp = sqrt + ギャップ
		ギャップ = -ギャップ
		
		# 2回おきに2倍の平方根をとる
		（ギャップ = -1）の場合
			平方根 = 2 * 平方根
	
** ワンダリングフェーズ: メモリマトリックスの疑似ランダムセルを繰り返し上書きする

# 訪問ループ: (2 * m_cost * t_cost) 行を疑似ランダムに再訪問
wCount = 0 から ( (m_cost * t_cost) - 1) まで
	# 疑似ランダム行を選択する
	行0 = lsw(rand) % m_cost
	行1 = lsw( ランド >>> オメガ ) % m_cost

	# 列ループ: M[row0]とM[row1]の両方を更新します
	col = 0 から C-1 まで
		# 疑似乱数列を選択する
		Col0 = lsw( ( rand >>> オメガ ) >>> オメガ ) % C
		Col1 = lsw( ( ( rand >>> オメガ ) >>> オメガ ) >>> オメガ ) % C

		rand = H.duplexing_{rho}( M[row0][col] [+] M[row1][col] [+] M[prev0][col0] [+] M[prev1][col1], blen)
		M[行0][列] = M[行0][列] ^ ランド
		M[行1][列] = M[行1][列] ^ ( ランド >>> オメガ )

	# 次の反復では、最後に更新された行を再訪します
	前0 = 行0
	前1 = 行1

** まとめフェーズ: 出力計算

# 最終カラムをフルラウンドスポンジで吸収
H.吸収(M[行0][0])

# 丸いスポンジで余分なビットを絞り出します
出力 = H.squeeze(outlen)

# outlen長のビット文字列を出力として提供します
出力を返す

並列処理アルゴリズム

[0..P]内の各iについて
	** ブートストラップフェーズ: スポンジの状態とローカル変数を初期化します
	
	# 入力パラメータのバイト表現（他のパラメータも追加可能）
	params = outlen || len(パスワード) || len(ソルト) || t_cost || m_cost || C || P || i

	# スポンジの状態を初期化します（その後、パスワードを上書きできます）
	H_i.absorb( pad(パスワード || ソルト || パラメータ) )

	# 訪問ステップ、ウィンドウ、フィードされる最初の行を初期化します
	ギャップ = 1
	stp = 1
	ウィンド = 2
	平方根 = 2
	同期 = 4
	j = i

	前0 = 2
	行P = 1
	前P = 0

	** セットアップフェーズ: (m_cost x C) のメモリマトリックスを初期化し、そのセルはblenバイトのセルを持つ

	# M_i[0]、M_i[1]、M_i[2]を初期化します
	col = 0 から C-1 まで
		M_i[0][C-1-col] = H_i.squeeze_{rho}(blen)
	col = 0 から C-1 まで
		M_i[1][C-1-col] = H_i.duplexing_{rho}( M_i[0][col], blen)
	col = 0 から C-1 まで
		M_i[2][C-1-col] = H_i.duplexing_{rho}( M_i[1][col], blen)

	# ループの充填: 残りの行を初期化します
	row0 = 3 の場合、 ( (m_cost / P) - 1 )
		# 列ループ: M_i[row0]が初期化され、M_j[row1]が更新されます
		col = 0 から C-1 まで
			rand = H_i.duplexing_{rho}( M_j[rowP][col] [+] M_i[prev0][col] [+] M_j[prevP][col], blen)
			M_i[行0][C-1-列] = M_i[前0][列] ^ ランド
			M_j[rowP][col] = M_j[rowP][col] ^ ( ランド >>> オメガ )

		# 次のループで再度実行される行
		前0 = 行0
		前P = 行P
		rowP = (rowP + stp) % wnd

		# ウィンドウを全面的に再検討
		（行P = 0）の場合
			# ウィンドウを2倍にしてステップを調整します
			wnd = 2 * wnd
			stp = sqrt + ギャップ
			ギャップ = -ギャップ
		
			# 2回おきに2倍の平方根をとる
			（ギャップ = -1）の場合
				平方根 = 2 * 平方根
		
		# 同期ポイント
		if (row0 = 同期)
			同期 = 同期 + (平方根 / 2)
			j = (j + 1) % P
			同期スレッド()

	同期スレッド()
	
	** ワンダリングフェーズ: メモリマトリックスの疑似ランダムセルを繰り返し上書きする

	wnd = m_cost / (2 * P)
	同期 = 平方根
	オフ0 = 0
	オフP = wnd

	# 訪問ループ: (2 * m_cost * t_cost / P) 行を疑似ランダムに再訪問
	wCount = 0 から ( ( (m_cost * t_cost) / P) - 1) まで
		# 疑似ランダムな行とスライスを選択する (j)
		row0 = off0 + (lsw(rand) % wnd)
		rowP = offP + (lsw( rand >>> omega ) % wnd)
		j = lsw( ( rand >>> オメガ ) >>> オメガ ) % P

		# 列ループ: M_i[row0]を更新
		col = 0 から C-1 まで
			# 疑似乱数列を選択	
			Col0 = lsw( ( ( rand >>> オメガ ) >>> オメガ ) >>> オメガ ) % C

			rand = H_i.duplexing_{rho}( M_i[row0][col] [+] M_i[prev0][col0] [+] M_j[rowP][col], blen)
			M_i[行0][列] = M_i[行0][列] ^ ランド

		# 次の反復では、最後に更新された行を再訪します
		前0 = 行0
		
		# 同期ポイント
		if (wCount = 同期)
			同期 = 同期 + 平方根
			スワップ(オフ0、オフP)
			同期スレッド()

	同期スレッド()

	** まとめフェーズ: 出力計算

	# 最終カラムをフルラウンドスポンジで吸収
	H_i.吸収(M_i[行0][0])

	# 丸いスポンジで余分なビットを絞り出します
	output_i = H_i.squeeze(出力長)

# outlen長のビット文字列を出力として提供します
output_0 ^ ... ^ output_{P-1} を返す

セキュリティ分析

Lyra2 に対して、正当なユーザーが使用するメモリ量 を使用した攻撃の処理コストはと の間になると予想されます。後者は、メモリ量が のときに達成されるではなく のより適切な推定値です。ここで、は処理時間を定義するユーザー定義のパラメーターです。 1 / 2 n + 2 {\displaystyle 1/2^{n+2}} O ( 2 2 n T R 3 ) {\displaystyle O(2^{2nT}R^{3})} O ( 2 2 n T R n + 2 ) {\displaystyle O(2^{2nT}R^{n+2})} n ≫ 1 {\displaystyle n\gg 1} O ( R ) {\displaystyle O(R)} O ( R ) {\displaystyle O(R)} T {\displaystyle T}

これは、メモリ使用量が多いときにコストが となるScryptとよく似ています。[12]また、文献に記載されている他のソリューションでは、結果は通常 となります。[7] [13] [14] [15] O ( R 2 ) {\displaystyle O(R^{2})} O ( 1 ) {\displaystyle O(1)} O ( R T + 1 ) {\displaystyle O(R^{T+1})}

しかしながら、実際にはこれらのソリューションは、通常、同じ処理時間でLyra2で達成されるメモリ使用量よりも低い値になります。[16] [17] [18] [19] [20] R {\displaystyle R}

パフォーマンス

C = 256、ρ = 1、p = 1、およびさまざまな T および R 設定での SSE 対応 Lyra2 のパフォーマンスを、最小パラメータを持つ SSE 対応Scryptおよびメモリハード PHC ファイナリストと比較しました。

Lyra2のSSEシングルコア実装で得られた処理時間を、ここに示す図に示す。この図は[9]から抽出したもので、PHCコンテキストで実行されたサードパーティのベンチマークと非常によく似ている。[16] [17] [18] [19] [20]

示された結果は、、、ビット（つまり、内部状態は 256 ビットです）、およびさまざまなおよび設定で構成された Lyra2 の平均実行時間に対応しており、可能なパラメータの組み合わせとそれに応じたリソースの使用法の全体的な考え方を示しています。 C = 256 {\displaystyle C=256} ρ = 1 {\displaystyle \rho =1} b = 768 {\displaystyle b=768} T {\displaystyle T} R {\displaystyle R}

この図に示すように、Lyra2 は、最大 400 MB (およびを使用) または最大 1 GB のメモリ (および を使用)を使用して 1 秒未満で実行できます。また、1.6 GB (およびを使用)では 5 秒未満で実行できます。 R = 2 14 {\displaystyle R=2^{14}} T = 5 {\displaystyle T=5} R ≈ 4.2 ⋅ 10 4 {\displaystyle R\approx 4.2\cdot 10^{4}} T = 1 {\displaystyle T=1} R = 2 16 {\displaystyle R=2^{16}} T = 6 {\displaystyle T=6}

すべてのテストは、48 GBのDRAMを搭載したIntel Xeon E5-2430（2.20 GHz、12コア、64ビット）で実行され、Ubuntu 14.04 LTS 64ビットが実行され、ソースコードはGCC 4.9.2を使用してコンパイルされました。[9]

拡張機能

Lyraは主に2つの拡張機能を提供しています。[11]

  • Lyra2- δ : アルゴリズムの帯域幅使用量をより細かく制御できます。
  • Lyra2 p :ユーザーのプラットフォーム上の並列処理機能を活用します。

参照

参考文献

  1. ^ 「パスワードハッシュコンペティション」password-hashing.net . 2016年3月22日閲覧。
  2. ^ "Lyra2REv2". eprint.iacr.org . 2016年3月22日閲覧。
  3. ^ “Vertcoin”. vertcoin.org . 2019年10月8日閲覧。
  4. ^ "MonaCoin". monacoin.org . 2019年10月8日閲覧。
  5. ^ ab van Beirendonck、M.;トルドー、L.ガード、P. Balatsoukas-Stimming、A. (2019-05-29)。Lyra2REv2 ベースの暗号通貨用の Lyra2 FPGA コア。 IEEE 回路とシステムに関する国際シンポジウム (ISCAS)。札幌、日本: IEEE。ページ 1–5。arXiv : 1807.05764。​​土井：10.1109/ISCAS.2019.8702498。
  6. ^ 「Cryptology ePrint Archive: Report 2015/136」. eprint.iacr.org . 2016年3月22日閲覧。
  7. ^ ab Almeida, Leonardo C.; Andrade, Ewerton R.; Barreto, Paulo SLM; Simplicio Jr, Marcos A. (2014-01-04). 「Lyra: メモリと処理コストを調整可能なパスワードベースの鍵導出」. Journal of Cryptographic Engineering . 4 (2): 75– 89. CiteSeerX 10.1.1.642.8519 . doi :10.1007/s13389-013-0063-5. ISSN  2190-8508. S2CID  5245769. 
  8. ^ 「Cryptology ePrint Archive: Report 2014/030」. eprint.iacr.org . 2016年3月22日閲覧。
  9. ^ abc Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. (2016-01-01). 「Lyra2: 時間とメモリのトレードオフに対抗する高セキュリティな効率的なパスワードハッシュ」IEEE Transactions on Computers . PP (99): 3096– 3108. doi :10.1109/TC.2016.2516011. ISSN  0018-9340. S2CID  37232444.
  10. ^ Chen, Lily (2009). 「疑似乱数関数を用いた鍵導出に関する推奨事項（改訂版）」（PDF） .コンピュータセキュリティ. NIST. doi : 10.6028/NIST.SP.800-108 .
  11. ^ ab シンプリシオ ジュニア、マルコス A.;アルメイダ、レオナルド C.アンドラーデ、エワートン R.サントス、パウロ C. Barreto、Paulo SLM「Lyra2 リファレンス ガイド」(PDF)。PHC。パスワードハッシュコンテスト。
  12. ^ パーシバル、コリン. 「シーケンシャルメモリハード関数による強力な鍵導出」(PDF) . TARSNAP . テクニカルBSDカンファレンス.
  13. ^ 「Cryptology ePrint Archive: Report 2013/525」. eprint.iacr.org . 2016年3月22日閲覧。
  14. ^ Schmidt, Sascha. 「Catenaパスワードスクランブルフレームワークの実装」（PDF） .バウハウス大学ヴァイマール校. メディア学部.
  15. ^ "PHC/phc-winner-argon2" (PDF) . GitHub . 2016年3月22日閲覧。
  16. ^ ab 「Gmane -- Another PHC candidates mechanical tests」. article.gmane.org . 2016年3月22日閲覧。
  17. ^ ab 「Gmane - 1日1レビュー Lyra2」. article.gmane.org . 2016年3月22日閲覧。
  18. ^ ab 「Gmane -- Lyra2初期レビュー」. article.gmane.org . 2016年3月22日閲覧。
  19. ^ ab 「Gmane -- メモリパフォーマンスとASIC攻撃」。article.gmane.org 。 2016年3月22日閲覧。
  20. ^ ab 「Gmane -- アルゴンのクイック分析」. article.gmane.org . 2016年3月22日閲覧。
  • Lyra2のウェブサイト
  • Lyra2 ソースコードリポジトリ（Github 上）
Retrieved from "https://en.wikipedia.org/w/index.php?title=Lyra2&oldid=1283386171"