SHA-256とHMACの理論とPython実装：Merkle-Damgård構成・長さ拡張攻撃・RFC 4231検証まで

はじめに

https://yuhi-sa.github.io/posts/20260614_cryptography_roadmap/1/ では「SHA-2 / SHA-3 / BLAKE2 と HMAC」を将来追加予定のプレースホルダとして挙げていました。また https://yuhi-sa.github.io/posts/20260715_tls13_handshake/1/ では、HKDFの内部でHMAC-SHA256を繰り返し使いながらも、HMACそのものの構成原理には踏み込みませんでした。本記事ではSHA-256をMerkle-Damgård構成から導出してフルスクラッチ実装し、なぜ「秘密鍵とメッセージを単純に連結してハッシュ化する」という素朴なMAC設計が危険なのかを実際の攻撃（長さ拡張攻撃）で示した上で、HMACの入れ子構成がこの脆弱性をどう解決するかを検証します。

SHA-256の構成：Merkle-Damgård構成

SHA-256は、メッセージを512ビットのブロックに分割し、各ブロックを圧縮関数で逐次処理するMerkle-Damgård構成を採用しています。

\[ H_i = f(H_{i-1}, M_i), \qquad H_0 = \text{IV（初期値）} \tag{1} \]

ここで \(f\) は圧縮関数、\(M_i\) は \(i\) 番目のメッセージブロック、\(H_i\) は256ビット（8個の32ビットワード）の中間状態です。最終的な \(H_n\) がハッシュ値になります。この構成の重要な性質は、最終出力 \(H_n\) が「元のメッセージ全体」ではなく「最後の中間状態」からのみ決まることです。この性質が後述の長さ拡張攻撃の原因になります。

パディング

メッセージ長を512の倍数にするため、末尾に 0x80 を1バイト追加し、ゼロで埋めた後、**元のメッセージ長（ビット単位、64ビット）**を末尾に付加します。

圧縮関数

各ブロックは64ラウンドの操作を経ます。ラウンドごとに、8個のハッシュ変数 \((a,b,c,d,e,f,g,h)\) を、ビット単位のブール演算（\(\text{Ch}\) , \(\text{Maj}\) ）とビット回転（\(\Sigma_0\) , \(\Sigma_1\) ）を組み合わせて更新します。

\[ T_1 = h + \Sigma_1(e) + \text{Ch}(e,f,g) + K_i + W_i, \qquad T_2 = \Sigma_0(a) + \text{Maj}(a,b,c) \tag{2} \]

\(K_i\) は64個の固定定数（最初の64個の素数の立方根の小数部分から導出）、\(W_i\) はメッセージスケジュール（16ワードの入力ブロックを64ワードに拡張したもの）です。

Python実装

丸め定数 \(K_i\) は「最初の64個の素数の立方根の小数部分」から機械的に生成できます（ハードコードせず、定義通りに導出します）。

import struct
import sympy

def first_n_primes(n):
    primes, candidate = [], 2
    while len(primes) < n:
        if sympy.isprime(candidate):
            primes.append(candidate)
        candidate += 1
    return primes

def frac_cube_root_bits(p):
    cube_root = p ** (1 / 3)
    frac = cube_root - int(cube_root)
    return int(frac * (2**32)) & 0xFFFFFFFF

MASK32 = 0xFFFFFFFF
K = [frac_cube_root_bits(p) for p in first_n_primes(64)]
H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
      0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

def rotr(x, n):
    return ((x >> n) | (x << (32 - n))) & MASK32

def sha256_pad(msg, total_len_override=None):
    ml = (total_len_override if total_len_override is not None else len(msg)) * 8
    msg = msg + b"\x80"
    while (len(msg) * 8) % 512 != 448:
        msg += b"\x00"
    return msg + struct.pack(">Q", ml)

def sha256_compress(state, block):
    w = list(struct.unpack(">16I", block)) + [0] * 48
    for i in range(16, 64):
        s0 = rotr(w[i-15], 7) ^ rotr(w[i-15], 18) ^ (w[i-15] >> 3)
        s1 = rotr(w[i-2], 17) ^ rotr(w[i-2], 19) ^ (w[i-2] >> 10)
        w[i] = (w[i-16] + s0 + w[i-7] + s1) & MASK32

    a, b, c, d, e, f, g, h = state
    for i in range(64):
        S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
        ch = (e & f) ^ (~e & g)
        temp1 = (h + S1 + ch + K[i] + w[i]) & MASK32
        S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        temp2 = (S0 + maj) & MASK32
        h, g, f, e, d, c, b, a = g, f, e, (d + temp1) & MASK32, c, b, a, (temp1 + temp2) & MASK32

    return [(x + y) & MASK32 for x, y in zip(state, [a, b, c, d, e, f, g, h])]

def sha256_scratch(msg, init_state=None, total_len_override=None):
    state = list(init_state) if init_state else list(H0)
    padded = sha256_pad(msg, total_len_override)
    for i in range(0, len(padded), 64):
        state = sha256_compress(state, padded[i:i+64])
    return b"".join(struct.pack(">I", x) for x in state)

init_state と total_len_override という2つの追加引数を持たせてあるのは、後述の長さ拡張攻撃で「途中の中間状態から計算を再開する」ために必要だからです（通常のSHA-256利用では省略します）。生成した K を FIPS 180-4 の公式定数64個と1つずつ比較したところ、全64個が完全一致しました（定義通りに導出した値が仕様書のハードコード値と一致することの検証）。

数値実験1：hashlibとの完全一致検証

空文字列・短文字列・パングラム・1000バイトの4パターンで、フルスクラッチ実装と hashlib.sha256 を比較しました。

入力長（バイト）	一致
0	True
3（“abc”）	True
43（パングラム）	True
1000	True

全パターンで完全一致し、Merkle-Damgård構成・圧縮関数・パディングの実装が正しいことが確認できました。

長さ拡張攻撃：なぜ H(secret ‖ message) は危険か

素朴な発想として、「秘密鍵とメッセージを連結してハッシュ化すれば、鍵を知らない第三者は改ざんを検出されずにメッセージを偽造できないはず」と考えたくなります。しかし、Merkle-Damgård構成ではこの直感が誤りです。

攻撃者が知っているのは、original_mac = SHA256(secret ‖ message) の値と、secret の長さ（多くの場合、推測またはブルートフォースで特定可能）だけです。secret の値そのものは知りません。しかし、SHA-256の最終出力は「最後の中間状態」そのものなので、攻撃者は original_mac を新しい計算の初期状態として再利用し、secret を知らないまま SHA256(secret ‖ message ‖ glue_padding ‖ extension) を計算できてしまいます（glue_padding はSHA-256のパディング規則から機械的に決まるバイト列）。

secret = b"s3cr3t-key-unknown-to-attacker!!"  # 攻撃者は知らない（長さ33バイトのみ既知と仮定）
known_message = b"user=alice&admin=false"
original_mac = sha256_scratch(secret + known_message)

extension = b"&admin=true"
secret_len = 33  # 攻撃者が既知/推測した長さ
glue_padding = sha256_pad(b"\x00" * secret_len + known_message)[secret_len + len(known_message):]

forged_state = list(struct.unpack(">8I", original_mac))
forged_mac = sha256_scratch(
    extension,
    init_state=forged_state,
    total_len_override=secret_len + len(known_message) + len(glue_padding) + len(extension),
)

実行結果：

Original MAC = SHA256(secret || message): 06a4e85d01c06ec4a1c424c2e3db1d07349777dc0b18864d9f477b87912e9387
Forged MAC (attacker, no secret) : 7c0e1115cef381a74c5bf8a9f8dc7ef78d34e00ed94eb8afce3ba72773578076
Real MAC   (secret + full msg)   : 7c0e1115cef381a74c5bf8a9f8dc7ef78d34e00ed94eb8afce3ba72773578076
Attack succeeds: True

攻撃者は secret を一切知らないまま、有効なMACを偽造することに成功しました。 元のメッセージ user=alice&admin=false に、権限昇格を狙う &admin=true を追記した偽造メッセージが、正規の（secret を知っているサーバーが計算するのと）同一のMAC値を持ちます。これは実際に2009年にFlickr APIで悪用された既知の脆弱性クラスです。

HMAC：入れ子構成による防御（RFC 2104）

HMACは、ハッシュ関数を2回、鍵を混ぜた形で入れ子に適用することでこの問題を解決します。

\[ \text{HMAC}(K, m) = H\bigl((K' \oplus \text{opad}) \Vert H((K' \oplus \text{ipad}) \Vert m)\bigr) \tag{3} \]

\(K'\) は鍵をブロック長（SHA-256では64バイト）にパディングしたもの、\(\text{ipad}\) /\(\text{opad}\) はそれぞれ 0x36/0x5c を64回繰り返した固定パターンです。

def hmac_sha256_scratch(key, msg):
    block_size = 64
    if len(key) > block_size:
        key = sha256_scratch(key)
    key = key + b"\x00" * (block_size - len(key))
    o_key_pad = bytes(b ^ 0x5c for b in key)
    i_key_pad = bytes(b ^ 0x36 for b in key)
    inner = sha256_scratch(i_key_pad + msg)
    return sha256_scratch(o_key_pad + inner)

数値実験2：RFC 4231テストベクタとの一致

RFC 4231 Test Case 1（鍵20バイトの 0x0b 繰り返し、メッセージ "Hi There"）で、フルスクラッチ実装と Python標準ライブラリの hmac モジュールを比較しました。

scratch : b0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7
hmac lib: b0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7
match: True

完全一致し、RFC 2104の入れ子構成を正しく実装できていることが確認できました。

数値実験3：HMACは長さ拡張攻撃に耐性を持つ

先ほどの「MACの出力を初期状態として再利用する」という攻撃手法を、HMACの出力に対しても試みました。

fake_forged_state = list(struct.unpack(">8I", original_hmac))
naive_forged = sha256_scratch(extension, init_state=fake_forged_state, ...)
real_hmac_of_extended = hmac_sha256_scratch(hmac_key, known_message + glue_padding + extension)

Naive length-extension forgery attempt on HMAC output: de4b20b143fcf46ce0f35b765ffa79ef5ff2cfa348f47d77eacd00eebf521996
Real HMAC of extended message                        : d788efc1c0c55ab56f8a4c874af42817bde54a8583471b88becc844b4f5d1e5d
Naive attack succeeds (should be False): False

偽造は失敗しました。 HMACの出力は「内側のハッシュ \(H(K'\oplus\text{ipad} \Vert m)\) に、さらに外側から \(K'\oplus\text{opad}\) を前置してハッシュ化した」値であり、この外側のハッシュ計算を再開するには \(K'\oplus\text{opad}\) （つまり鍵そのもの）が必要です。攻撃者は最終出力しか見えないため、外側ハッシュの「入力」を再構成できず、内側の中間状態を再利用する攻撃は成立しません。これが、生のハッシュ関数を直接MACとして使うべきではなく、必ずHMACのような検証済み構成を使うべき理由です。

暗号系ロードマップ：古典暗号・対称鍵・RSA・Diffie-Hellman・楕円曲線・ハッシュ・署名・TLSのPython実装ハブ - 本記事はこのハブの「将来追加予定」プレースホルダの1つを実装したものです。
TLS 1.3ハンドシェイク解剖 - HKDFの内部で本記事のHMAC-SHA256が繰り返し使われる様子を実装しています。
デジタル署名（ECDSA / EdDSA / RSA-PSS）の理論と Python 実装 - 署名でも「メッセージそのものではなくハッシュに署名する」設計が使われており、ハッシュ関数の安全性が土台になります。
AES / ChaCha20 対称鍵暗号の理論と Python 実装 - AEADモードが提供する認証（改ざん検知）は、本記事のHMACと同じ「メッセージ認証」の目的を暗号化と統合した設計です。

参考文献

National Institute of Standards and Technology (2015). Secure Hash Standard (SHS). FIPS PUB 180-4.
Krawczyk, H., Bellare, M., & Canetti, R. (1997). HMAC: Keyed-Hashing for Message Authentication. RFC 2104.
Nystrom, M. (2005). Identifiers and Test Vectors for HMAC-SHA-224, HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-512. RFC 4231.
Duong, T., & Rizzo, J. (2009). Flickr’s API Signature Forgery Vulnerability（長さ拡張攻撃の実例）.