Scrypt

暗号理論において、scrypt"ess crypt"と発音する。このアルゴリズムは特に大規模なカスタムハードウェア攻撃の実行時に大量のメモリが必要になるようにし、そのコストが高くなるように設計されている。2016年にscryptアルゴリズムはIETFによって7914}

1. 導入
-----

パスワードベースの鍵導出関数は一般的に多くの計算資源が必要になるように設計されているので、計算に比較的長い時間がかかる数百ミリ秒程度。}}。正しいユーザーは認証などの操作ごとにこれを1回だけ実行するので、必要な時間は僅かである。しかし、総当たり攻撃では操作を何十億回も実行する必要がある可能性が高く、その時点で必要な時間が無視できないほどになり、理想的には途方もない時間が必要となる。

RSAセキュリティによるPBKDF2などの以前のパスワードベースの鍵導出関数は、要求される計算資源が比較的低く、実行に綿密なハードウェアや大量のメモリを必要としない。そのため、ASICやFPGAなどのハードウェアに簡単かつ安価に実装することができる。これによって、十分な計算資源を持つ攻撃者は、数百から数千のハードウェアにアルゴリズムの実装を構築し、それぞれが鍵空間の異なるサブセットを検索することで、大規模な並列攻撃を始めることができる。これは総当たり攻撃を完了するのに必要な時間を利用可能な実装で割ることにより、必要な時間を妥当なものに引き下げる可能性が非常に高い。

scrypt関数はアルゴリズムの計算資源要求を引き上げることによって、このような試みを阻止するように設計されている。具体的には、このアルゴリズムは他のパスワードベースの鍵導出関数と比較して大量のメモリを使用するように設計されており、ハードウェア実装のサイズとコストが遥かに高くなるので、攻撃者が実行可能な並列処理の量が制限される。

2. 概要
-----

scryptが多くのメモリを必要とすることはアルゴリズムの一部として生成される擬似ランダムビット文字列の大きなベクターに由来する。ベクターが一度生成されると、派生鍵を生成するためにその要素に対して擬似ランダムな順序でアクセスと結合が行われる。単純な実装では、必要に応じてアクセスできるように、ベクター全体をRAMに保持する必要がある。

ベクターの要素はアルゴリズムで生成されるので、必要に応じて各要素をオンザフライで生成でき、一度に1つの要素だけをメモリに格納できるので、メモリ使用量が大幅に削減される。しかし、各要素の生成には多くの計算資源を必要とすることを意図しており、要素は関数の実行中に何度もアクセスされることが予想される。したがって、メモリの使用量を減らすには速度に大きなトレードオフがある。

この種の時間とメモリのトレードオフは、多くのコンピューターアルゴリズムに存在する。速度はより多くのメモリを使用することで上げることができ、メモリ使用量はより多くの操作を実行して長い時間を必要とすることで減らすことができる。scryptの背後にある考え方は、このトレードオフを意図的にどちらも高価なものにすることである。したがって、攻撃者は限られた費用で大規模な並列化が可能な多くの計算資源を必要としない実装を使用する可能性があるが、これの実行速度は非常に遅くなる。または、高速に実行できる実装を使用する場合は、大量のメモリが必要となることから並列化のコストが高価になる。

3. アルゴリズム
---------

Function scryptInputs: //このアルゴリズムには次のパラメーターが含まれている:// Passphrase: Bytes ハッシュ化する文字列Salt: Bytes レインボーテーブル攻撃から保護するためにハッシュを変更するランダムな文字列 CostFactor : Integer CPU/メモリコストパラメーター - 2の累乗でなければならない BlockSizeFactor : Integer ブロックサイズパラメーター、シーケンシャルメモリ読み取りサイズと性能を微調整する ParallelizationFactor : Integer //並列化パラメーター//。 DesiredKeyLen : Integer 必要な鍵の長さ hLen: Integer ハッシュ関数のオクテット単位の長さ。 MFlen: Integer 混合関数のオクテット単位の出力長。RFC7914でr * 128と定義されている。Output: DerivedKey: Bytes バイト配列、長さはDesiredKeyLen

//ステップ1. 高価なソルトを生成する// blockSize ← 128*BlockSizeFactor //// バイト単位のSMix混合関数の出力長//

PBKDF2を使用して最初の128*BlockSizeFactor*pバイトのデータを生成する結果を//p//個の要素を持つ配列として扱う。各エントリーは//blocksize//バイトである [B0...Bp−1] ← PBKDF2HMAC-SHA256

ROMix関数を使用して各ブロックをB Costfactor回混合するfor i ← 0 to p-1 do Bi ← ROMix

Bの全要素が新しい「高価な」ソルトである expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1 //// ∥は連結を意味する//

//ステップ2. PBKDF2を使用して目的のバイト数を生成するが、生成した高価なソルトを使用する//return PBKDF2HMAC-SHA256;

//PBKDF2//表記は2898}}で定義されており、cは反復回数である。

この表記はc = 1でPBKDF2の使用法を指定するために7914}}で使用されている。Function ROMix

//X//の//Iterations//コピーを作成する X ← Blockfor i ← 0 to Iterations−1 do Vi ← X X ← BlockMix

for i ← 0 to Iterations−1 do j ← Integerify mod Iterations X ← BlockMix

return X

7914}}ではIntegerify}}をXの最後の64バイトを//リトルエンディアン//整数A1として解釈した結果として定義している。

Iterationsは2のN乗と等しいので、Xの//最後//の64バイトのうち//最初//のCeilingバイトだけが//リトルエンディアン//整数A2として解釈され、Integerify mod Iterations = A1 mod Iterations = A2 mod Iterationsを計算するために実際に必要となる。

Function BlockMix:

//ブロックBはrの128バイトのチャンクである// r ← Length / 128;

//Bを2rの64バイトチャンクの配列として扱う// [B0...B2r-1] ← B

X ← B2r−1for i ← 0 to 2r−1 do X ← Salsa20/8 // 64バイトから64バイトのSalsa20/8ハッシュ Yi ← X

return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

//Salsa20/8//はSalsa20の8ラウンドバージョンである。

4. 暗号通貨での使用
-----------

Scryptはプルーフ・オブ・ワークアルゴリズムとして多くの暗号通貨で使用されている。最初は2011年9月にTenebrixに実装され、scryptアルゴリズムを採用したライトコインとドージコインの基礎となった。scryptを使用する暗号通貨の採掘は、Graphics Processing UnitがCPUと比べて処理能力が大幅に高い傾向があることから、GPUで実行されることが多い。これは2013年の11月と12月にこれらの暗号通貨の価格が上昇した際に、ハイエンドGPUが不足したことにつながった。

2014年5月時点で特別なASIC採掘ハードウェアがscryptベースの暗号通貨で利用することができるdate=May 2019}}。

5. ユーティリティ
----------

scryptユーティリティは2009年5月にコリン・パーシバルによってscrypt鍵導出関数のデモンストレーションとして作成された。これは殆どのLinuxディストリビューションとBSDディストリビューションで利用することができる。

6. 関連項目
-------

Argon2 – 2015年のパスワードハッシュ競技会の勝者
bcrypt – blowfishベースの鍵導出関数
鍵導出関数
PBKDF2 – 広く利用されている標準の鍵導出関数
[1] – 改善されたbcryptの設計に基づくキャッシュ耐性のある鍵導出関数
時間と空間のトレードオフ

7. 脚注
-----

7.1. 注釈
-------

7.2. 出典
-------

8. 外部リンク
--------