チャレンジレスポンス認証方式

チャレンジレスポンス認証方式の仕組みを解説。パスワードをネットワーク上に送信せずに認証を行い、盗聴やリプレイ攻撃を防ぐ方法を紹介します。

概要

チャレンジレスポンス認証方式(Challenge-Response Authentication)は、セキュリティを強化するために使用される認証方式の一つです。この方式では、ユーザーのパスワードそのものをネットワーク上で送信することなく、認証を行います。これにより、盗聴によるパスワード漏洩のリスクを大幅に低減できます。

本記事では、単に手順を紹介するだけでなく、

  1. なぜハッシュ関数の一方向性がこの方式の安全性を支えているのか(定式化と論理的な導出)
  2. なぜチャレンジが毎回ランダムであることがリプレイ攻撃を防ぐのか(証明とエントロピーの議論)
  3. CHAP・HOTP・TOTPという実在の標準規格が、この方式のどんな変種なのか
  4. 逆に、この方式が中間者攻撃(MITM)には単純な形では耐性を持たないのはなぜか

を、実際にHMAC-SHA256で実装したPythonコードの実行結果とあわせて掘り下げます。なお、同じディレクトリの シングルサインオン(SSO)とID連携 は本記事とは別の認証トピック(複数システム間での認証情報の連携)を扱っており、本記事では単一のクライアント・サーバー間の認証プロトコルそのものに焦点を絞ります。

チャレンジレスポンス認証方式の流れ

  1. [クライアント] ユーザー認証情報の送信: 利用者がIDとパスワードを入力すると、クライアントはIDのみを認証サーバーに送信します。パスワードは送信しません。

  2. [認証サーバー] チャレンジコードの生成と送信: 認証サーバーは、受け取ったIDに対応するユーザーを特定し、使い捨ての乱数(チャレンジコード) \(c\) を生成します。このチャレンジコードをクライアントに送信します。

  3. [クライアント] レスポンスの生成と送信: クライアントは、受け取ったチャレンジコード \(c\) と、クライアント・サーバー間で共有された鍵(パスワードやそのハッシュ値)\(k\) を組み合わせて、ハッシュ関数でレスポンス \(r\) を生成します。

    \[ r = H(c, k) \]

    この生成されたレスポンス \(r\) を認証サーバーに送信します。

  4. [認証サーバー] レスポンスの検証: 認証サーバーは、自身が生成したチャレンジ \(c\) と、サーバー側で管理している鍵 \(k\) を同じ手順で処理し、\(r' = H(c, k)\) を計算します。\(r' = r\) であれば、ユーザーは正当な鍵 \(k\) (=パスワード)を知っていると判断し、認証成功となります。

以降の節では、この \(r = H(c,k)\) という一見単純な式が、なぜ安全な認証を実現できるのかを、ハッシュ関数の性質から丁寧に導出します。

なぜ安全なのか:ハッシュ関数の一方向性による導出

攻撃者の視点を定式化する

ネットワークを盗聴する攻撃者が観測できる情報を整理すると、ID・チャレンジ \(c\) ・レスポンス \(r=H(c,k)\) の組だけです。鍵 \(k\) (パスワード相当の秘密情報)そのものは一度もネットワーク上に現れません。攻撃者の目的は、次のいずれかです。

  • (A) 鍵 \(k\) 自体を復元する(一度復元できれば、以後どんなチャレンジにも正しく応答できてしまう)
  • (B) 鍵 \(k\) を知らないまま、特定のチャレンジ \(c\) に対する正しいレスポンス \(r\) を偽造する

この2つがどちらも困難であることを保証するのが、ハッシュ関数(や、鍵付きハッシュであるHMAC)に要求される暗号学的性質です。

(A) を防ぐ性質:一方向性(原像計算困難性)

ハッシュ関数 \(H\) が一方向性(one-wayness)、より正確には**原像計算困難性(preimage resistance)**を持つとは、出力 \(y=H(x)\) が与えられたとき、\(H(x')=y\) を満たす \(x'\) を効率的に見つけるアルゴリズムが(現実的な計算資源では)存在しないことを言います。

チャレンジレスポンス方式では、攻撃者は \(c\) (既知)と \(r=H(c,k)\) (観測可能)を手にしていますが、これは「\(k\) を含む入力に対する出力」という一種の原像探索問題になっています。\(H\) が原像計算困難であれば、攻撃者はこの \((c, r)\) の組から \(k\) を復元できません。これが「パスワード \(k\) そのものを一度もネットワークに流さずに認証できる」という、この方式の核となる安全性の根拠です。

(B) を防ぐ性質:擬似ランダム関数(PRF)としてのHMAC

一方向性だけでは実は不十分です。なぜなら (B) は「\(k\) を復元せずに、特定の \(c\) に対する \(r\) だけを偽造する」という、より弱い(攻撃者にとってはより易しい)目標だからです。この (B) を防ぐために必要な性質は、暗号理論では**MACの存在的偽造不可能性(EUF-CMA: Existential Unforgeability under Chosen-Message Attack)**と呼ばれます。

  • 攻撃者はクライアントになりすましたサーバーとして振る舞い、任意に選んだチャレンジ \(c_1, c_2, \dots\) をクライアントに送りつけて、対応するレスポンス \(r_1=H(c_1,k), r_2=H(c_2,k),\dots\) を収集できる(これを選択平文攻撃に相当するオラクルアクセスと見なせます)。
  • それでもなお、これまで問い合わせていない新しいチャレンジ \(c^\*\) に対する正しいレスポンス \(r^\*=H(c^\*,k)\) を、無視できない確率で計算できてはいけません。

単純な \(H(c \Vert k)\) (ハッシュ関数への鍵付き連結)は、Merkle-Damgård構成のハッシュ関数に対して長さ拡張攻撃という弱点があり、この性質を満たさない場合があることが知られています(https://yuhi-sa.github.io/posts/20260715_sha256_hmac/1/で、この攻撃を実際に成功させています)。そのため実務では、この記事の数値実験も含め、入れ子構成によって長さ拡張攻撃を防ぐHMAC(RFC 2104)を用いるのが標準です。

\[ r = \mathrm{HMAC}(k, c) = H\bigl((k' \oplus \text{opad}) \Vert H((k' \oplus \text{ipad}) \Vert c)\bigr) \]

HMACは擬似ランダム関数(PRF)として振る舞うことが標準的な仮定のもとで示されており、上記のEUF-CMA性を満たします。したがって、攻撃者がいくら過去のチャレンジ・レスポンスの組を観測しても、鍵 \(k\) を知らない限り、新しいチャレンジに対する正しいレスポンスを計算することはできません。

リプレイ攻撃耐性の証明

なぜ過去の \((c,r)\) の再送は失敗するのか

チャレンジ \(c\) が、認証のたびに独立に一様ランダムな \(n\) ビットの値として選ばれるとします(\(|C|=2^n\) )。攻撃者が過去に盗聴した組 \((c_{old}, r_{old})\) (\(r_{old}=\mathrm{HMAC}(k,c_{old})\) )を、新しいセッションでそのまま再送したとします。新しいセッションのチャレンジ \(c_{new}\) は独立に選ばれるため、

\[ \Pr[c_{new} = c_{old}] = \frac{1}{2^n} \]

であり、\(c_{new} \neq c_{old}\) が(\(n\) が十分大きければ)圧倒的な確率で成り立ちます。このとき、サーバーが計算する正しい値は \(\mathrm{HMAC}(k, c_{new})\) であり、攻撃者が送った \(r_{old}=\mathrm{HMAC}(k,c_{old})\) とは異なるチャレンジに対する値です。前節のEUF-CMA性(HMACがPRFとして振る舞うこと)から、\(c_{old}\neq c_{new}\) である限り

\[ \Pr\bigl[\mathrm{HMAC}(k,c_{old}) = \mathrm{HMAC}(k,c_{new})\bigr] \approx 2^{-\ell} \]

程度に無視できる確率でしか一致しません(\(\ell\) はHMAC出力のビット長。SHA-256ベースなら \(\ell=256\) )。つまりリプレイは、\(c_{new}\neq c_{old}\) となった時点でほぼ確実に失敗します。

エッジケース:チャレンジの予測可能性・再利用がある場合

上記の証明は「チャレンジが十分なエントロピーを持ち、かつ再利用されない」という前提に強く依存しています。この前提が崩れると、リプレイ攻撃は現実的な脅威になります。

  • チャレンジ空間が小さすぎる場合: \(n\) ビットのチャレンジを使う場合、\(q\) 回のセッションを観測すれば、誕生日のパラドックスにより、あるチャレンジ値が2回出現する確率はおよそ \(q^2/2^{n+1}\) になります。\(n\) が小さい(例えば16ビット程度)と、比較的少ない観測回数でチャレンジの再利用が発生し、過去のレスポンスがそのまま通用してしまいます。
  • チャレンジが予測可能・決定的な場合: 例えば単純なインクリメンタルカウンタや、シードが弱い擬似乱数生成器(PRNG)を使っていると、攻撃者は次に送られてくるチャレンジを事前に予測できます。予測できたとしても \(k\) を知らなければ正しい \(r\) は計算できませんが(前節のEUF-CMA性)、もしサーバー側の実装不備でカウンタがリセットされたり、同じチャレンジが2回発行されたりすれば、以前に記録した \((c,r)\) をそのまま再送でき、認証を突破できます。
  • サーバーがチャレンジの使用済みチェックをしない場合: サーバーが「同じチャレンジ値を2度受け付けない」ことを保証していないと、攻撃者は同一セッション内で観測した正規のレスポンスを、サーバーがまだ古いチャレンジを覚えている間に再送できる可能性があります。

これらはいずれも「チャレンジのランダム性・新規性(freshness)」という前提が崩れたケースであり、チャレンジレスポンス方式を実装する際は、暗号学的に安全な乱数生成器を使い、十分なビット長(一般に128ビット以上)のチャレンジを採用し、使用済みチャレンジを検証することが必須になります。

CHAP・HOTP・TOTPとの比較:チャレンジの性質の違い

チャレンジレスポンス認証は抽象的な設計原則であり、実在する複数の標準規格がその具体的な変種として実装されています。違いは主に「チャレンジとして何を使うか」にあります。

方式チャレンジの実体新規性の根拠実装上の特徴
汎用チャレンジレスポンス認証のたびに送られる乱数 \(c\)高エントロピーな乱数を毎回生成サーバーが能動的にチャレンジを送信する必要がある
CHAP(RFC 1994、PPP向け)接続確立時、および接続中に任意のタイミングでサーバーが送るランダムな値乱数 + 接続中の再チャレンジレスポンスは \(H(\text{ID} \Vert \text{secret} \Vert \text{challenge})\) 。サーバーは平文相当の秘密を保持する必要がある
HOTP(RFC 4226)クライアント・サーバー双方が保持するカウンタ \(C\)カウンタが単調増加し、使用済みの値を再利用しないチャレンジをネットワーク越しに送らず、暗黙に同期された状態として扱う。\(\mathrm{HOTP}(K,C)=\mathrm{Truncate}(\mathrm{HMAC\text{-}SHA1}(K,C))\)
TOTP(RFC 6238)現在時刻から導出されるタイムステップ \(T=\lfloor (t-T_0)/X \rfloor\) (既定 \(X=30\) 秒)時刻の経過が新規性を保証HOTPの \(C\) を \(T\) に置き換えたもの。クライアント・サーバー間の時刻同期が前提

この表からわかるように、CHAPは「サーバーが乱数を送る」という古典的な意味でのチャレンジを使うのに対し、HOTP/TOTPは明示的にチャレンジを送信しない変種です。カウンタや時刻という、双方が独立に計算できる値を「暗黙のチャレンジ」として使うことで、往復通信を1回減らせるのが利点ですが、その分次のようなトレードオフがあります。

  • HOTP: 同じカウンタ値に対するOTPは、サーバーがそのカウンタを「使用済み」として記録し拒否するまでの間は有効です。カウンタの同期がずれた場合の再同期処理(許容ウィンドウ内でカウンタを進めて再照合する)が、攻撃者に多少の猶予を与える可能性があります。
  • TOTP: 1つのタイムステップ(既定30秒)内であれば、そのステップに対するOTPは有効なままです。つまり、乱数チャレンジ方式が理論上ほぼゼロのリプレイ猶予しか持たないのに対し、TOTPは時間窓の分だけリプレイの猶予が存在します(多くの実装では、時計のずれを許容するため前後1ステップ程度を有効とし、猶予がさらに広がります)。
  • CHAP: RFC 1994が既定とするMD5は、衝突耐性の観点では現在推奨されない古いハッシュ関数ですが、CHAPが実際に依拠しているのは主に一方向性(原像計算困難性)であり、MD5の原像計算困難性自体は本記事執筆時点で実務上深刻に破られてはいません。とはいえ、CHAPはサーバー側が平文相当の秘密を保持する必要がある(ハッシュ化されたパスワードだけでは検証できない)という設計上の弱点があり、また \(H(\text{ID}\Vert\text{secret}\Vert\text{challenge})\) という生のハッシュ関数の鍵付き連結は、HMACのような検証済みの構成と比べて安全性の議論が難しく、現在ではCHAP自体が非推奨とされ、より強力なEAP系認証方式への移行が進んでいます。

中間者攻撃(MITM)への耐性の限界

チャレンジレスポンス方式は、盗聴とナイーブなリプレイには強い一方、**能動的に通信を中継・改ざんする中間者攻撃(MITM)**には、単純な形式のままでは耐性を持ちません。これは見落とされがちな重要な限界です。

具体的な攻撃シナリオ:中継(リレー)攻撃

攻撃者 \(M\) が、正規のクライアント \(A\) と正規のサーバー \(S\) の通信経路上に割り込んでいるとします。

  1. \(A\) が \(M\) (\(A\) からは \(S\) に見えている)に ID を送る。
  2. \(M\) はこの ID をそのまま本物の \(S\) に転送する。
  3. \(S\) は正規の乱数チャレンジ \(c\) を生成し、\(M\) に送る。
  4. \(M\) はこの \(c\) をそのまま \(A\) に転送する。
  5. \(A\) は正しく \(r=\mathrm{HMAC}(k,c)\) を計算し、\(M\) に送る。
  6. \(M\) はこの \(r\) をそのまま \(S\) に転送する。
  7. \(S\) は \(r\) を検証し、認証成功と判断する。

この手順を通じて、\(M\) は \(k\) を一切知ることなく、\(A\) と \(S\) の間の認証を成立させることに成功します。問題は、認証が成立した後の通信経路に \(M\) がまだ介在し続けている点です。\(M\) はこの後、\(A\) と \(S\) の間でやり取りされる(本来は認証済みのはずの)データを盗聴・改ざんできる立場に居続けます。チャレンジレスポンスは「その時点で \(k\) を知っている」ことしか証明しておらず、「その後の通信路が信頼できる」ことは何も保証していないのです。

対策:相互認証とチャネルバインディング

この限界に対処するには、以下のような追加の仕組みが必要です。

  • 相互認証: クライアントだけでなくサーバー側も自身を証明することで、少なくとも「なりすましサーバーに接続してしまう」タイプの被害の一部を防げます。ただし、\(M\) が両方向を単純に中継するだけの「純粋なリレー攻撃」には、相互認証だけでは対処できません(\(M\) は双方の正規のやり取りをそのまま右から左に流すだけで、双方の認証をどちらも通過させてしまうため)。
  • チャネルバインディング: 認証のやり取り(チャレンジやレスポンス)を、根底の通信チャネル(例えばTLSセッション)固有の値と結びつける技術です。これにより、たとえ \(M\) がチャレンジ・レスポンスを中継できたとしても、\(A\) -\(M\) 間のTLSチャネルと \(M\) -\(S\) 間のTLSチャネルは別物であるため、サーバー \(S\) 側で「認証時に使われたチャネル」と「実際に通信しているチャネル」の不一致を検出でき、中継を無効化できます。

つまり、チャレンジレスポンス方式単体は「平文パスワードを流さない」「単純な再送を防ぐ」という限定的な保証しか提供しておらず、能動的なMITMを防ぐには、相互認証やチャネルバインディング、あるいは後述するWebAuthn/FIDO2のように通信のオリジン(送信先ドメイン)そのものを署名対象に含める設計が必要になります。

数値実験:HMAC-SHA256によるチャレンジレスポンス認証の検証

以上の議論を、実際にPythonで動かして確認します。共有鍵 \(k\) を持つクライアントとサーバーを模擬し、(1) 正規認証、(2) 新しいチャレンジに対するリプレイ攻撃、(3) 誤った鍵での認証、(4) チャレンジが再利用された場合のリプレイ、の4パターンを検証しました。

import hmac
import hashlib
import secrets


def generate_challenge(nbytes: int = 16) -> bytes:
    """暗号学的に安全な乱数チャレンジを生成する"""
    return secrets.token_bytes(nbytes)


def client_response(key: bytes, challenge: bytes) -> bytes:
    """クライアント側: r = HMAC(k, c) を計算する"""
    return hmac.new(key, challenge, hashlib.sha256).digest()


def server_verify(key: bytes, challenge: bytes, response: bytes) -> bool:
    """サーバー側: 自分でHMAC(k, c)を再計算し、定数時間比較で照合する"""
    expected = hmac.new(key, challenge, hashlib.sha256).digest()
    return hmac.compare_digest(expected, response)


shared_key = secrets.token_bytes(32)  # クライアント・サーバー間で事前共有された256ビット鍵

# シナリオ1: 正規の認証
c1 = generate_challenge()
r1 = client_response(shared_key, c1)
ok1 = server_verify(shared_key, c1, r1)

# シナリオ2: リプレイ攻撃(新しい、独立に生成されたチャレンジに対して古い応答を再送)
c2 = generate_challenge()
ok2_replay_fresh = server_verify(shared_key, c2, r1)

# シナリオ3: 誤った共有鍵での認証
wrong_key = secrets.token_bytes(32)
r3 = client_response(wrong_key, c1)
ok3_wrong_key = server_verify(shared_key, c1, r3)

# シナリオ4: チャレンジの再利用(弱いRNG・カウンタリセット等を模擬)が起きた場合のリプレイ
ok4_replay_reused_challenge = server_verify(shared_key, c1, r1)

print(f"c1 = {c1.hex()}")
print(f"r1 = {r1.hex()}")
print(f"c2 = {c2.hex()}  (c1 と異なる: {c1 != c2})")
print(f"シナリオ1 正規認証: {ok1}")
print(f"シナリオ2 リプレイ(新チャレンジ): {ok2_replay_fresh}")
print(f"シナリオ3 誤った鍵: {ok3_wrong_key}")
print(f"シナリオ4 リプレイ(チャレンジ再利用): {ok4_replay_reused_challenge}")

実行結果:

c1 = 24de785a3ff43a32a8a9524a1b84db22
r1 = 1e482276c3da679d0d69a8fcc98be3b12bf569ecbe624aa7403c904d5113ef7e
c2 = d700d389cdc9d76c3f661a8ab964617b  (c1 と異なる: True)
シナリオ1 正規認証: True
シナリオ2 リプレイ(新チャレンジ): False
シナリオ3 誤った鍵: False
シナリオ4 リプレイ(チャレンジ再利用): True

結果は理論的な議論と完全に一致しました。(1) 正規のクライアントは常に認証に成功し、(2) 過去のレスポンス \(r_1\) を新しく生成された独立なチャレンジ \(c_2\) に対して再送しても認証は失敗します(\(c_1 \neq c_2\) のため、HMACの出力が一致しない)。(3) 誤った鍵で計算したレスポンスも当然拒否されます。一方で、(4) もし何らかの理由で同じチャレンジ \(c_1\) が再度使われてしまうと、過去に記録したレスポンス \(r_1\) がそのまま通用し、認証が成立してしまいます。これは前節で述べた「チャレンジの新規性が崩れるとリプレイ耐性も崩れる」というエッジケースを、実際のコードで再現したものです。

なお、server_verify の照合に hmac.compare_digest という定数時間比較関数を使っている点にも注意してください。単純な == 比較や、バイト列の先頭から順に不一致を検出した時点で早期リターンする実装は、タイミング攻撃(応答時間の微小な差から、正解にどれだけ近いかを推測する攻撃)に対して脆弱になり得ます。ハッシュ値やMACの照合には必ず定数時間比較関数を使うべきである、というのは実装上の重要な注意点です。

下図は、シナリオ1(正規の認証フロー)とシナリオ2(新しいチャレンジに対するリプレイ攻撃の失敗)を図解したものです。

Challenge-response authentication: legitimate flow vs. replay attack. Left panel shows the client sending an ID, receiving a random challenge c, and returning r = HMAC(k, c), with the server recomputing the same HMAC and accepting on a match. Right panel shows an attacker replaying an old response r_old against a freshly generated challenge c_new; since r_old = HMAC(k, c_old) and the server expects HMAC(k, c_new), the mismatch causes the server to reject the replayed response.

近年の動向:パスキー / WebAuthn / FIDO2への発展

近年、パスワードに依存しない認証(パスワードレス認証)の文脈でよく登場するパスキー(passkey)や、その基盤となるWebAuthn(W3Cが標準化するWeb向けAPI)・FIDO2は、本記事で扱ったチャレンジレスポンス方式の発展形として位置づけられます。

基本的なやり取りの骨格は同じです。サーバー(Relying Party)がランダムなチャレンジを送り、クライアント側の認証器(デバイス内の生体認証やセキュリティキーなど)がそれに応答する、という構造は変わりません。大きく異なるのは、応答の作り方です。

  • 本記事で扱った方式: クライアント・サーバーが共有の秘密鍵 \(k\) を持ち、\(r=H(c,k)\) や \(\mathrm{HMAC}(k,c)\) という対称鍵ベースの計算でレスポンスを作る。サーバー側も \(k\) を(ハッシュ化された形であれ)保持・再現できる必要がある。
  • WebAuthn/FIDO2: 登録時に生成された公開鍵ペアのうち、秘密鍵はクライアント側のデバイスから外に出ません。認証時には、サーバーが送ったチャレンジ(に加え、接続先のオリジン情報なども含めたデータ構造)に対して、クライアントがデジタル署名を行い、サーバーは事前に登録された公開鍵で検証します。

この違いには構造的な利点があります。対称鍵ベースの方式では、サーバー側のデータベースが漏洩すると、(保存形式によっては)攻撃者が正規のレスポンスを偽造できてしまう可能性がありますが、公開鍵ベースの方式では、サーバーが保持するのは公開鍵のみであり、それが漏洩してもレスポンス(署名)の偽造にはつながりません。また、署名対象にオリジン情報を含めることで、本記事で述べたMITM・フィッシングによる中継攻撃に対しても、単純な共有鍵ベースのチャレンジレスポンスより強い耐性を持つ設計になっています。

ここで挙げた内容は、パスキーやWebAuthn/FIDO2に関する一般に広く知られている基本設計についての説明であり、細部の仕様や最新の普及状況については、実装・利用する際にW3C・FIDO Allianceの一次情報を確認することをお勧めします。

利点

  • パスワードの盗聴リスクの低減: ネットワーク上をパスワードそのものが流れることがないため、盗聴されてもパスワードが漏洩するリスクが低いです。
  • リプレイ攻撃への耐性: チャレンジコードが毎回異なる、十分なエントロピーを持つ乱数であるため、過去の通信内容を盗聴されても、それをそのまま再利用して認証を突破するリプレイ攻撃を(本記事で証明した確率的な意味で)防ぐことができます。
  • 限界を正しく理解した上での利用が重要: 一方で、能動的な中間者攻撃には単純な形式のままでは耐性がないため、通信経路自体をTLS等で保護し、必要に応じて相互認証やチャネルバインディングを組み合わせる必要があります。

関連記事

参考


関連ツール