パスワードハッシュの内部（bcrypt/scrypt/Argon2 とメモリ困難性）

出発点：なぜ汎用ハッシュは「設計からして」不適なのか

パスワードの安全な保存 では「SHA-256 をそのまま使うな、bcrypt/Argon2 を使え」という結論を扱いました。本稿はその一段下、なぜそれらが効くのかを内部動作から詰めます。

汎用ハッシュ（SHA-256, BLAKE2 など）の設計目標は「衝突耐性」と「高速性」です。1回の計算が軽く、状態がレジスタに収まる小ささであることは、ファイル検証やHMACでは美徳です。しかしパスワード保存では、この性質がそのまま攻撃者への贈り物になります。

• オフライン攻撃には速度制限がない：DBが漏れた後の総当たりは攻撃者の手元で走るため、レートリミットもアカウントロックも効きません。守りは「1回の計算をどれだけ重くできるか」だけになります。
• 攻撃側ハードウェアが圧倒的に有利：SHA-256 は分岐もメモリ参照もほぼ無い純粋な算術演算の連なりなので、GPUの数千コアやASICで完全に並列化できます。汎用CPUで毎秒数百万回でも、専用ハードでは数百億〜数兆回に達します。

つまり問題は「ハッシュかどうか」ではなく、防御側CPUと攻撃側ハードの“計算効率の差”をいかに潰すかです。専用パスワードハッシュは、この非対称性を埋めるために生まれました。

ストレッチング：時間困難性で計算効率の差を埋める

最初の武器がストレッチング（key stretching）――同じ計算を何千〜何十万回も反復し、1回の検証コストを意図的に引き上げる手法です。PBKDF2 はこれを最も素朴に実装し、HMAC を iterations 回チェーンするだけです。

PBKDF2 の骨子（1ブロック分）:
  U1 = HMAC(password, salt || INT(i))
  U2 = HMAC(password, U1)
  ...
  Uc = HMAC(password, U(c-1))
  T  = U1 XOR U2 XOR ... XOR Uc        # c = iterations

反復回数を上げれば防御側の検証時間は線形に伸び、攻撃者の総当たりコストも線形に増えます。正規ログインは1ユーザー1回なので 0.2〜0.5 秒は許容できますが、攻撃者は何十億通りも試すため、1回の重さがそのまま壁になります。

ただしPBKDF2の中身は HMAC-SHA256 などの汎用ハッシュです。前節のとおりこれはGPU/ASICで超並列化できるため、PBKDF2は「攻撃者も同じ命令を高速に回せる」弱点を引きずります。時間だけを縛っても、攻撃側の単位時間あたり処理能力が桁違いなら効きが薄い。ここが次のメモリ困難性への動機になります。

bcrypt の内部：Blowfish 鍵スケジュールの反復

bcrypt は Blowfish 暗号の鍵セットアップを流用します。Blowfish は18個のサブキー（Pボックス）と4枚のSボックス（各256エントリ、計約4KB）を、鍵から派生させてから暗号化に入ります。bcrypt の核は EksBlowfishSetup（拡張鍵スケジュール）にあります。

EksBlowfishSetup(cost, salt, password):
  state = InitState()                  # P/S を πの定数で初期化
  state = ExpandKey(state, salt, password)   # ソルトとパスワードを混ぜる
  repeat 2^cost times:                 # ← ここで時間を稼ぐ
    state = ExpandKey(state, 0, password)
    state = ExpandKey(state, 0, salt)
  return state
# 最後に固定文字列 "OrpheanBeholderScryDoubt" を 64 回暗号化 → ハッシュ

ポイントは2つです。第一に、コスト係数 cost に対し反復回数が 2^cost で指数的に増えること。cost=10 なら 1024 回、cost=12 なら 4096 回の鍵スケジュールを回します。第二に、Blowfishの暗号化は**Sボックスへの大量のテーブル参照（データ依存のメモリアクセス）**を伴うため、PBKDF2のような純算術より攻撃側の最適化が効きにくいことです。

しかしbcryptの内部状態は約4KBに固定されています。これはGPUの各コアが持つわずかなローカルメモリやASICの小さなSRAMに余裕で収まるサイズです。結果として、攻撃者は数千の試行を並列にメモリ内で走らせられ、メモリ面では防御側を縛れません。bcryptが縛れるのは「CPU時間」だけで、「メモリ」は縛れない――これが次世代アルゴリズムが乗り越えた限界です。

メモリ困難性：scrypt が変えた攻撃の経済学

bcrypt の限界を突いたのが scrypt の**メモリ困難性（memory-hardness）**です。発想を変え、「大量のメモリを使わないと計算できない」関数を作れば、メモリが乏しい攻撃ハードを直接不利にできます。

scrypt の心臓部 ROMix は、まず擬似乱数で大きな配列 V を埋め（N 個のブロック）、その後 V を入力依存の順序でランダムアクセスします。

ROMix(B, N):
  # フェーズ1：N ブロック分のメモリを順に埋める
  V[0] = B
  for i in 1..N-1:
    V[i] = BlockMix(V[i-1])
  # フェーズ2：V を“データ依存”でランダム参照しながら混ぜる
  X = V[N-1]
  for i in 0..N-1:
    j = Integerify(X) mod N      # 次に読む位置が X に依存して決まる
    X = BlockMix(X XOR V[j])     # ← V 全体を保持していないと計算できない
  return X

ここで効くのが時間とメモリのトレードオフです。攻撃者がメモリを節約しようと V を保持せず必要時に再計算すると、フェーズ2のランダム参照のたびに大量の再計算が発生し、計算量が爆発します（TMTO ペナルティ）。つまり「メモリを使うか、時間を爆発させるか」の二択を強いる。GPUはコアあたりのオンチップメモリが小さく、外部メモリへのランダムアクセス帯域がボトルネックになるため、scrypt のランダム参照はGPUの強み（演算スループット）を活かせなくします。

Argon2：メモリ困難性の決定版と data-dependent の選択

2015年の Password Hashing Competition で選ばれたのが Argon2（RFC 9106）です。メモリ困難性を洗練させ、3つのパラメータで明示的に制御します。

• メモリコスト m：使用するメモリ量（KiB）。困難性の主軸。
• 時間コスト t：メモリ全体を上書きで舐める反復回数（パス数）。
• 並列度 p：内部レーン数。マルチコアでの正規検証を速めつつ、攻撃者にも同じメモリ総量を要求する。

Argon2 は大きなメモリブロック配列を確保し、各ブロックを直前ブロックと参照ブロックの圧縮関数 G で更新しながら、配列全体を t 回上書きします。肝はその参照ブロックの選び方で、3つの版に分かれます。

data-dependent（Argon2d）は参照先アドレスをメモリ内容そのものから決めるため、攻撃者は前節の TMTO ペナルティを最大限に食らいます。一方でアクセスパターンが秘密（パスワード）に依存するため、キャッシュタイミング等のサイドチャネルで情報が漏れる懸念が生じます。Argon2id は最初のパスの前半を data-independent で回してこの懸念を抑え、以降を data-dependent にして TMTO 耐性を確保する――両者の良いとこ取りです。だから汎用のパスワード保存では Argon2id が第一候補になります。

# OWASP の代表的な推奨設定（同等の防御強度／環境に応じて調整）
Argon2id, m = 19456 KiB (≈19 MiB), t = 2, p = 1     # メモリ制約が厳しい場合
Argon2id, m = 47104 KiB (≈46 MiB), t = 1, p = 1     # 高メモリ側の代替
# 参考：RFC 9106 自体は m=2 GiB, t=1, p=4 を第一推奨、制約環境では m=64 MiB, t=3, p=4 を挙げる
# 方針：まず m を許せる限り大きく取り、検証時間が 0.5 秒前後に収まるよう t を調整

パラメータ設定とペッパー、運用の実務

最後に内部理解を運用へ落とします。原則は**「検証1回が許容できる上限ぎりぎりまで重く」**――目安は対話ログインで 0.2〜0.5 秒です。Argon2 ではまず m を環境が許す限り大きく取り（メモリ困難性は m に強く依存）、その上で t を調整して目標時間に合わせます。p はサーバーの空きコア数を超えない範囲にします。

ペッパー（pepper）は全ユーザー共通の秘密値で、DBとは別の場所（環境変数や シークレット管理 のKMS/HSM）に保管します。ソルトと違い秘匿が本質で、DBだけ漏れてもハッシュ単独からは総当たりできなくする上乗せ策です。HMAC でパスワードに先がけて適用するのが安全で、ハッシュ関数へ単純連結する実装は前述の長さ切り詰めと干渉しうるため避けます。

まとめると、汎用ハッシュ→ストレッチング（時間困難）→メモリ困難という流れは、すべて攻撃者ハードウェアの優位を消すという一本の動機で貫かれています。bcrypt は時間を、scrypt/Argon2 は時間に加えてメモリを人質に取る。GPUの帯域とASICの面積という「演算では下がらないコスト」を突くからこそ、メモリ困難性は現代のパスワード保存の決定打になっています。新規設計では迷わず Argon2id を、十分大きな m とともに選んでください。