暗号

暗号
一般的な
デザイナーコリン・パーシバル
初版2009
暗号の詳細
ダイジェストサイズ変数
ブロックサイズ変数
ラウンド変数

暗号学において、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 入力:このアルゴリズムには、次のパラメータが含まれます: Passphrase: ハッシュする文字列 (バイト) Salt : レインボー テーブル攻撃から保護するためにハッシュを変更するランダム文字列 ( バイト) 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（パスフレーズ、ソルト、1、ブロックサイズ*並列化ファクター） 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 ← ブロックミックス(X xor V j ) X を返す

RFC 7914 では、 X の最後の 64 バイトをリトルエンディアン整数 A 1Integerify(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月リリース）に初めて実装され、 LitecoinとDogecoinの基盤となり、これらにもScryptアルゴリズムが採用されました。[ 7 ] [ 8 ] Scryptを使用する暗号通貨のマイニングは、多くの場合、グラフィックス・プロセッシング・ユニット（ GPU ）で行われます。これは、GPUがCPUと比較して（一部のアルゴリズムでは）はるかに高い処理能力を持つ傾向があるためです。[ 9 ]この結果、2013年11月と12月にこれらの通貨の価格が上昇し、ハイエンドGPUが不足しました。[ 10 ]

ユーティリティ

scrypt暗号化ユーティリティ
開発者コリン・パーシバル
安定版リリース
1.3.3 [ 11 ] ウィキデータで編集する / 2025年2月14日 （2025年2月14日）
リポジトリgithub .com /Tarsnap /scrypt
Webサイトwww .tarsnap .com /scrypt .html

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

参照

参考文献

  1. ^ “Colin Percival” . Twitter . 2019年2月17日時点のオリジナルよりアーカイブ。
  2. ^ a b「scrypt鍵導出関数」 Tarsnap . 2019年5月28日時点のオリジナルよりアーカイブ。2014年1月21日閲覧。
  3. ^ a b「SCRYPT(1) 一般コマンドマニュアル」Debian Manpages . 2022年3月2日時点のオリジナルよりアーカイブ。2022年3月2日閲覧。
  4. ^ Percival, Colin; Josefsson, Simon (2016年8月). 「scryptパスワードベースの鍵導出関数」 . RFC Editor. 2021年12月13日時点のオリジナルよりアーカイブ。 2021年12月13日閲覧。
  5. ^ Alec Liu (2013年11月29日). 「ビットコインを超えて：最も有望な暗号通貨ガイド」 . 2018年6月13日時点のオリジナルよりアーカイブ。2017年7月8日閲覧。
  6. ^パーシバル、コリン。「シーケンシャルメモリハード関数によるより強力な鍵導出」（PDF）。2019年4月14日時点のオリジナルよりアーカイブ（PDF） 。 2022年11月11日閲覧。
  7. ^ Andreas M. Antonopoulos (2014年12月3日). Mastering Bitcoin: Unlocking Digital Cryptocurrencies . O'Reilly Media. pp. 221, 223. ISBN 9781491902646。
  8. ^ 「暗号通貨の歴史」 litecoin.info wiki 2014年2月7日。 2016年6月11日時点のオリジナルよりアーカイブ。 2014年6月27日閲覧。
  9. ^ Roman Guelfi-Gibbs. Radeon 7950向けLitecoin Scryptマイニング設定. Amazon Digital Services. 2016年10月24日時点のオリジナルよりアーカイブ。 2017年9月11日閲覧。
  10. ^ Joel Hruska (2013年12月10日). 「Litecoinマイニングの急増がグラフィックカード不足につながる」 ExtremeTech. 2017年12月12日時点のオリジナルよりアーカイブ。 2014年1月1日閲覧。
  11. ^ 「リリース 1.3.3」 2025年2月14日. 2025年2月28日閲覧。
  12. ^ Shelley, Johnny; Stolarczyk, Philip. 「Bcrypt – Blowfish File Encryption (ホームページ)」 . Sourceforge . 2015年8月29日時点のオリジナルよりアーカイブ。 2024年4月8日閲覧。
  13. ^ 「bcrypt APK for Android – Droid Informerで無料ダウンロード」droidinformer.org . 2020年2月15日時点のオリジナルよりアーカイブ。2022年3月2日閲覧。
  14. ^ 「T2パッケージ – trunk – bcrypt – ファイルを暗号化するためのユーティリティ」 . t2sde.org . 2017年10月28日時点のオリジナルよりアーカイブ。2022年3月2日閲覧。
  15. ^ 「Oracle® GoldenGateライセンス情報」 . Oracleヘルプセンター. 2024年3月6日時点のオリジナルよりアーカイブ。 2024年4月8日閲覧。
「 https://en.wikipedia.org/w/index.php?title=Scrypt&oldid=1332071125」から取得