暗号

暗号学において、scrypt（発音は「エス・クリプト」^[1]）は、2009年3月にコリン・パーシバルによって作成されたパスワードベースの鍵導出関数であり、もともとはTarsnapオンラインバックアップサービスのために作成された。^{[2] [3]}このアルゴリズムは、大量のメモリを必要とすることで、大規模なカスタムハードウェア攻撃の実行コストが高くなるように特別に設計された。2016年に、scryptアルゴリズムはIETFによってRFC 7914として公開された^。[4] scryptの簡易バージョンは、多くの暗号通貨でプルーフオブワークスキームとして使用されており、最初にArtForzと呼ばれる匿名のプログラマーによってTenebrixに実装され、その後すぐにFairbrixとLitecoinがそれに続いた。^[5]

パスワードベースのキー導出関数(パスワードベースの KDF) は、一般的に計算集約型に設計されているため、計算には比較的長い時間がかかります (数百ミリ秒程度)。正当なユーザーは、操作 (認証など) ごとに関数を 1 回実行するだけでよいため、必要な時間はごくわずかです。ただし、ブルート フォース攻撃では、操作を数十億回実行する必要がある可能性が高く、その時点で時間要件が大きくなり、理想的には法外なものになります。

以前のパスワードベースの KDF ( RSA Laboratoriesの人気のPBKDF2など) はリソース要求が比較的低く、実行に複雑なハードウェアや大量のメモリを必要としません。そのため、ハードウェア ( ASICやFPGAなど) に簡単かつ安価に実装できます。これにより、十分なリソースを持つ攻撃者は、ハードウェアにアルゴリズムの実装を数百または数千構築し、それぞれにキー空間の異なるサブセットを検索させることで、大規模な並列攻撃を開始できます。これにより、ブルートフォース攻撃を完了するために必要な時間が利用可能な実装の数で分割され、妥当な時間枠に短縮される可能性が高くなります。

scrypt関数は、アルゴリズムのリソース要求を高めることで、このような攻撃を阻止するように設計されています。具体的には、このアルゴリズムは他のパスワードベースのKDFと比較して大量のメモリを使用するように設計されており、^[6]ハードウェア実装のサイズとコストが大幅に高くなり、したがって、攻撃者が特定の量の資金リソースに対して使用できる並列処理の量が制限されます。

scrypt の大きなメモリ要件は、アルゴリズムの一部として生成される疑似ランダムビット文字列の大きなベクトルに起因します。ベクトルが生成されると、その要素は疑似ランダムな順序でアクセスされ、結合されて派生キーが生成されます。単純な実装では、必要に応じてアクセスできるように、ベクトル全体を RAM に保持する必要があります。

ベクトルの要素はアルゴリズム的に生成されるため、各要素は必要に応じてオンザフライで生成され、一度に 1 つの要素のみをメモリに格納できるため、メモリ要件が大幅に削減されます。ただし、各要素の生成は計算コストが高くなることが想定されており、関数の実行中に要素に何度もアクセスすることが予想されます。したがって、大量のメモリ要件をなくすには、速度とのトレードオフが大きくなります。

この種の時間とメモリのトレードオフは、コンピュータ アルゴリズムによく存在します。つまり、速度を上げるにはメモリ使用量を増やす必要があり、メモリ要件を下げるには操作数を増やして時間がかかることになります。scrypt の背後にある考え方は、このトレードオフをどちらの方向でも意図的にコストがかかるようにすることです。つまり、攻撃者は、多くのリソースを必要としない (したがって、限られた費用で大規模に並列化できる) が非常に低速で実行される実装を使用したり、より高速で実行されるがメモリ要件が非常に大きいため並列化にコストがかかる実装を使用したりすることができます。

関数scrypt
   入力: このアルゴリズムには、次のパラメータが含まれます:
      パスフレーズ:    ハッシュされるバイト文字列
      ソルト:    レインボー テーブル攻撃から保護するためにハッシュを変更するランダムな文字のバイト文字列
      CostFactor (N): 整数  CPU/メモリ コスト パラメータ - 2 の累乗にする必要があります (例: 1024) 
      BlockSizeFactor (r): 整数  ブロック サイズ パラメータ。順次メモリの読み取りサイズとパフォーマンスを微調整します。(通常は 8 が使用されます) 
      ParallelizationFactor (p): 整数  並列化パラメータ。 (1 .. 2 32 -1 * hLen/MFlen) 
      DesiredKeyLen (dkLen): 整数  バイト単位の希望するキーの長さ (派生キーのオクテット単位の想定出力長。dkLen ≤ (2 32 − 1) * hLen を満たす正の整数。) 
      hLen: 整数  ハッシュ関数のオクテット単位の長さ (SHA256 の場合は 32)。 
      MFlen: 整数  ミキシング関数 (以下のSMix )の出力のオクテット単位の長さ。RFC7914 では r * 128 と定義されています。
   出力: 
      DerivedKey:    バイト配列のバイト、DesiredKeyLen は long

   ステップ 1. 高価なソルトを生成します
   。blockSize ← 128*BlockSizeFactor   // SMix ミキシング関数出力の長さ (バイト単位) (例: 128*8 = 1024 バイト)

   PBKDF2 を使用して、最初の 128*BlockSizeFactor*p バイトのデータを生成します (例: 128*8*3 = 3072 バイト)。結果を
   p要素の配列として扱います。各エントリはブロックサイズバイトです (例: 3 要素、各 1024 バイト)。 
   [B 0 ...B p−1 ] ← PBKDF2 HMAC-SHA256 ( Passphrase、Salt、 1、 blockSize*ParallelizationFactor)

   ROMix関数を使用して、 B内の各ブロックをCostFactor回ミックスします（各ブロックは並列にミックスできます）
   。i ← 0からp-1まで、 
      B i ← ROMix(B i , CostFactor)を実行します。

   B のすべての要素は、新しい「高価な」ソルト
   expensiveSalt ← B 0 ‖B 1 ‖B 2 ‖ ... ‖B p-1   // ここで ‖ は連結です
 
   ステップ 2. PBKDF2 を使用して必要なバイト数を生成しますが、先ほど生成した高価なソルトを使用して、
    PBKDF2 HMAC-SHA256 (Passphrase, expensiveSalt, 1, DesiredKeyLen);
を返します。

ここで、PBKDF2(P, S, c, dkLen)表記は RFC 2898 で定義されており、c は反復回数です。

この表記法は、c = 1 の PBKDF2 の使用法を指定するために RFC 7914 で使用されます。

関数ROMix(ブロック、反復)

   Xの反復コピーを作成する
   X ← ブロック
   i ← 0からIterations−1まで
      V i ← X を実行する
      X ← ブロックミックス(X)

   i ← 0からIterations−1まで
      j ← Integerify(X) mod 反復
      X ← BlockMix(X xor V j )

   Xを
返す

RFC 7914 では、 X の最後の 64 バイトをリトルエンディアン整数 A ₁Integerify(X)として解釈した結果として定義されています。

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

機能ブロックミックス(B):

    ブロックBはr個の128バイトのチャンク（2r個の64バイトのチャンクに相当）です。
    r ← 長さ(B) / 128;

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

    X ← B 2r−1 
    for i ← 0 to 2r−1 do 
        X ← Salsa20/8(X xor B i )   // Salsa20/8は64バイトから64バイトにハッシュします
        Y i ← X

    戻る← Y 0 ∈Y 2 ∈...∈Y 2r−2 ∈Y 1 ∈Y 3 ∈...∈Y 2r− 1

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

scryptは、多くの暗号通貨でプルーフ・オブ・ワークアルゴリズムとして使用されています（より正確には、Hashcashプルーフ・オブ・ワークアルゴリズムのハッシュ関数として使用されています）。これは、Tenebrix（2011年9月リリース）に最初に実装され、同じくscryptアルゴリズムを採用したLitecoinとDogecoinの基礎となりました。 ^{[7] [8] scryptを使用する}暗号通貨のマイニングは、多くの場合、グラフィックス処理装置（ GPU ）で実行されます。これは、GPUがCPUと比較して（一部のアルゴリズムでは）はるかに高い処理能力を持つ傾向があるためです。^[9]これにより、2013年11月と12月にこれらの通貨の価格が上昇したため、ハイエンドGPUが不足しました。^[10]

scryptユーティリティは、scryptキー導出関数のデモンストレーションとして、2009年5月にColin Percivalによって作成されました。^{[2] [3]ほとんどの}LinuxおよびBSDディストリビューションで利用可能です。

• Argon2 – 2015年のパスワードハッシュコンテストの優勝者
• bcrypt – blowfish ベースのパスワードハッシュ関数
• bcrypt – 2002年に開発されたblowfishベースのクロスプラットフォームファイル暗号化ユーティリティ^{[12] [13] [14] [15]}
• crypt – Unix C ライブラリ関数
• crypt – Unix ユーティリティ
• ccrypt – ユーティリティ
• キー導出関数
• キーストレッチ
• mcrypt – ユーティリティ
• PBKDF2 – 広く使用されている標準のパスワードベースのキー導出関数 2
• PufferFish – 改良された bcrypt 設計に基づくキャッシュハード パスワード ハッシュ関数
• 空間と時間のトレードオフ

• Tarsnap Web サイトの暗号化ページ。
• オリジナルのscrypt紙。
• GitHubの scrypt