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!!"  # 攻撃者は知らない（長さ32バイトのみ既知と仮定）
known_message = b"user=alice&admin=false"
original_mac = sha256_scratch(secret + known_message)

extension = b"&admin=true"
secret_len = 32  # 攻撃者が既知/推測した長さ（len(secret) == 32。1バイトでもずれると偽造は失敗する）
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で悪用された既知の脆弱性クラスです。

注意：secret_len は1バイトでもずれると攻撃は失敗します。 上のコードで secret_len を33（実際の32から1ずらした値）に変えて実行すると、glue_padding のパディング長がずれ、forged_mac と real_mac は一致しなくなります（Attack succeeds: False）。つまりこの攻撃は「secret の値」を知る必要はありませんが、「secret の正確な長さ」だけは知っている（または総当たりで正しく言い当てる）必要があります。多くの実装では鍵長が固定（16/32バイト等）または限られた候補しかないため、この前提は現実的に満たされてしまうことが多い、という点が本質的な弱点です。

Merkle-Damgård構成の逐次連鎖(上段)と長さ拡張攻撃(下段左、original_macを新しい初期状態として再利用しforged_macを計算)、およびHMACの入れ子構成(下段右、外側ハッシュの再開にはK’⊕opad＝鍵そのものが必要なため同じ手法が通用しない)を示す模式図

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の出力に対しても試みました。攻撃者は「HMACのブロック長は64バイトである」というRFC 2104公開の事実だけを手がかりに、original_hmac をあたかも SHA256(64バイトに埋めた鍵 ‖ known_message) の中間状態であるかのように再利用しようとします。

known_message = b"user=alice&admin=false"
extension = b"&admin=true"
hmac_key = b"hmac-secret-key-of-any-length"
original_hmac = hmac_sha256_scratch(hmac_key, known_message)

# 攻撃者は「ブロック長64バイト」しか知らないので、鍵ぐるみで64バイトに
# パディングされた状態から known_message を続けたものだと仮定して継続を試みる
assumed_prefix_len = 64 + len(known_message)
glue_padding = sha256_pad(b"\x00" * assumed_prefix_len)[assumed_prefix_len:]

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

実行結果：

original_hmac        : 41761b3768c7c93c847725233afcadfc57cd8d66fab9ca3d3daddc5422f743b6
naive_forged          : d271cb903261507c9b97d1bdc306dd94cac0e6ee36134fc5f0ded05dd83a9425
real_hmac_of_extended: c3d71f89be480af38ea463b8494bc345b8fb6ce4f5539ef7019fd873bc1b9037
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のような検証済み構成を使うべき理由です。

エッジケースと設計上の注意点

SHA-3（Keccak）はMerkle-Damgård構成ではないため、この攻撃自体が成立しない

長さ拡張攻撃は「ハッシュ関数の最終出力がそのまま次の計算の初期状態として再利用できる」というMerkle-Damgård構成特有の性質に起因します。これに対し、SHA-3（Keccak）はスポンジ構成を採用しており、内部状態（1600ビット）のうち出力にそのまま現れるのは一部（レート部）のみで、残り（キャパシティ部）は最終出力から復元できません。そのため、SHA3-256(secret ‖ message) は本記事と同じ手法では偽造できません。

とはいえ、これは「生のSHA3-256を直接MACとして使ってよい」という意味ではありません。SHA-3自体は正式な鍵付きAPIを提供しておらず、secret ‖ message という連結方式には長さ拡張以外の攻撃面（実装によるタイミング差など）が残り得ます。NIST SP 800-185はSHA-3ファミリー向けの鍵付き構成として KMAC（Keccak-based MAC）を規定しており、鍵をハッシュ入力に混ぜるのではなく、Keccakの汎用化された cSHAKE 経由でドメイン分離を行う設計を採用しています。「使っているハッシュ関数の内部構成が長さ拡張に強いかどうか」を都度確認するより、HMACやKMACのような検証済みの鍵付き構成を常に使う方が安全側に倒せます。

HMACの出力を切り詰めても長さ拡張耐性は変わらない

RFC 4231はHMAC-SHA-256の出力を96ビットや128ビットに切り詰める運用（トランケーション）を認めています。切り詰めは出力の全数探索コストを下げる（攻撃者が試す組み合わせが減る）ため衝突耐性の議論には影響しますが、長さ拡張攻撃への耐性には無関係です。攻撃の成立条件は「最終状態を次の計算の初期状態として使えること」であり、HMACでは外側ハッシュの入力を再構成できない時点で攻撃が成立しないため、出力の長さは無関係です。

2025年に実際に見つかった長さ拡張攻撃の実例

長さ拡張攻撃は「2009年のFlickr事件のような過去の話」ではありません。セキュリティ研究者のFrank Denisは2025年10月、CDNサービスBunnyCDNのトークン認証方式（SHA256(secret ‖ query_string) という設計）に対する長さ拡張攻撃の概念実証を公開しました。攻撃者は秘密鍵を知らないまま、既存の署名付きURLに role=admin のようなパラメータを追記した、正規のものと同じ署名を持つ偽造URLを生成できることを実証しています。この事例は、「秘密鍵とメッセージを連結してハッシュ化する」という素朴なMAC設計が、17年近く経った今でも実運用システムに紛れ込み続けていることを示しています。

なお、SHA-256などのハッシュ値はブラウザで動くハッシュ計算ツール(CalcBox) で手軽に確認できる。

暗号系ロードマップ：古典暗号・対称鍵・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（長さ拡張攻撃の実例）.
Kelsey, J., Chang, S., & Perlner, R. (2016). SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash. NIST SP 800-185.
Denis, F. (2025). Length-Extension Attacks Are Still a Thing. 00f.net（BunnyCDNのトークン認証に対する2025年時点の実例）.