応用情報技術者 2022年 春期 午前2 問42

レインボーテーブル【午前2解説】

正解の理由

解法ステップ

1. 選択肢のキーワードを確認：ハッシュ、チェーン、テーブル、平文、といった語句があるかをチェックする。
2. 「チェーン」と「ハッシュ逆引き」があればレインボーテーブルを連想する（レインボー攻撃の特徴）。
3. 他の選択肢（資格情報使い回し、総当たり、ソーシャルエンジニアリング）と比較して、チェーン＋ハッシュが含まれる選択肢を正答とする。
4. レインボーテーブルの動作イメージを頭に描き、保存方式が「全対応保存」ではなく「端点のみ保存＋再生成」であることを確認する。

• 生成時：任意の平文 p0 → ハッシュ H(p0) → 還元 R(H(p0)) = p1 → H(p1) … を L 回繰り返し、チェーンの開始 p0 と終了 hL を保存する。
• 逆引き時：不正入手したハッシュ h* に対して還元とハッシュを繰り返し（最大 L 回）、得られる値が保存された任意のチェーンの終了点と一致するかを調べ、一致したチェーンを先頭から再生成して元の平文を見つける。

選択肢別の誤答解説

• ア: これは「クレデンシャルスタッフィング（資格情報の使い回しを突く攻撃）」の説明です。事前に平文のID/パスワードリストを入手してログイン試行する点が特徴で、ハッシュやチェーンの概念は含みません。
• イ: これは「総当たり攻撃（ブルートフォース攻撃）」です。パスワード候補を片っ端から試す手法で、ハッシュ逆引きのために事前計算したチェーンを用いるレインボーテーブルとは異なります。
• ウ: レインボーテーブル（正解）。チェーンと還元関数を利用してハッシュから平文を逆引きする方法を説明しています。
• エ: これは「ソーシャルエンジニアリング／推測による攻撃」で、利用者の個人情報等からパスワードを類推する手法です。物理的・心理的な手口に属し、ハッシュ処理とは直接関係しません。

よくある誤解

1. レインボーテーブルは「全てのハッシュ→平文の対応を保存する巨大な辞書である」という誤解。実際は還元関数とチェーンを使い、チェーンの端点のみを保存してスペースを節約する方式です。
2. ソルトされたハッシュに対して同じテーブルがそのまま使えると考える誤解。ソルトが使われていると、同じパスワードでもハッシュが異なるため汎用的なレインボーテーブルは無効化されます（ソルト無効化にはテーブル毎にソルトを考慮する必要があり実用的でないことが多い）。

補足コラム

import hashlib

def H(p):  # ハッシュ関数（例）
    return hashlib.md5(p.encode()).hexdigest()

def R(h, charset="abc", length=3):  # 単純な還元関数（例）
    # ハッシュの一部を整数化して擬似的な平文を生成
    n = int(h[:6], 16)
    s = []
    for _ in range(length):
        s.append(charset[n % len(charset)])
        n //= len(charset)
    return ''.join(s)

# チェーン生成（教育用）
p0 = "aaa"
h = H(p0)
for i in range(5):
    p = R(h)
    h = H(p)
# 保存するのは (p0, h) のペアのみ

FAQ