ハッシュとHMAC
実装:
crypto/hash// 実行:go test ./crypto/hash/
ハッシュは任意長の入力を固定長の指紋に潰す一方向関数だ。同じ入力は同じ指紋、1ビット変えれば総崩れ、指紋から入力は戻せない。だがH(secret‖msg)を認証符号に使うと、秘密を知らない攻撃者が末尾を継ぎ足した正しい指紋を偽造できる。長さ拡張攻撃だ。ハッシュを自作してこの攻撃を実際に成功させ、それを塞ぐHMACを組む。最後にパスワード保存では速いハッシュがむしろ危険で、塩と反復が要ることを見る。
この章で作るもの
暗号の道具は、大きく3つに分かれる。中身を隠して後で戻す暗号化、戻せない指紋を作るハッシュ、その指紋を鍵で裏書きする署名。この章はそのうちのハッシュを扱う(暗号化と署名は後の暗号(RSA)の章で作る)。ハッシュは任意長の入力を固定長の指紋(ダイジェスト)に潰す関数だ。求められる性質は 3 つ。同じ入力は必ず同じ指紋になる(決定性)。入力を 1 ビット変えると指紋が半分くらい総崩れになる(なだれ効果)。そして指紋から入力を復元できない(一方向性)。ファイルの改ざん検知、パスワード保存、署名の前処理と、使い道は広い。
だが「ハッシュがあれば認証できる」と早合点すると足をすくわれる。サーバがクライアントに「このデータは正しい」と示すため、秘密鍵を混ぜた指紋 tag = H(secret‖msg) を付けたとする。秘密を知らなければ正しい tag は作れない、と思える。ところが多くのハッシュが使う Merkle–Damgård 構成には、長さ拡張攻撃という穴がある。攻撃者は secret を知らないまま、msg の末尾に好きなデータを継ぎ足した、正しい tag を偽造できる。この章はその攻撃を実際に動かし、正しい対策である HMAC を組む。
サーバが作る: H( secret ‖ msg ) = tag
└────────┬───────┘
内部状態がそのまま tag として漏れる
攻撃者が作る: tag を状態として復元 → 続きを処理
H( secret ‖ msg ‖ glue ‖ "&admin=true" ) = 偽造tag
↑ secret 不要で計算できる順に見ていく。
- ハッシュの 3 性質: 決定性・なだれ効果・一方向性。この 3 つが揃って初めて指紋として使える
- 長さ拡張攻撃: 素朴な構成では指紋が内部状態そのもの。だから H(secret‖msg) は認証符号に使えない
- HMAC が塞ぐ: 内側のハッシュを外側でもう一度包む。継ぎ足しても外側の指紋は偽造できない
① ハッシュを組み立てる
まずハッシュ本体を作る。Merkle–Damgård 構成は、入力をブロックに切り、内部状態にブロックを 1 つずつ混ぜ込んでいく。初期状態から始めて、全ブロックを混ぜ終えた状態が指紋になる:
const (
// BlockSize は圧縮関数が一度に処理するバイト数。
BlockSize = 16
// Size は指紋のバイト数(32bit 語 4 つ = 128bit)。
Size = 16
)
// iv は内部状態の初期値。
var iv = [4]uint32{0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476}
// consts は各ラウンドで混ぜる定数(なだれ効果を強める)。
var consts = [8]uint32{
0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6,
0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c,
}
// compress は 16 バイトのブロック 1 つを内部状態に混ぜ込む。
// 最後に元の状態を足し戻す(Davies–Meyer 風)ので一方向になる。
func compress(s [4]uint32, block []byte) [4]uint32 {
var w [4]uint32
for i := 0; i < 4; i++ {
w[i] = binary.LittleEndian.Uint32(block[i*4:])
}
a, b, c, d := s[0], s[1], s[2], s[3]
for r := 0; r < 8; r++ {
mixed := a + (b ^ c ^ d) + w[r%4] + consts[r]
a = bits.RotateLeft32(mixed, 7)
a, b, c, d = d, a, b, c // レジスタを回す
}
return [4]uint32{s[0] + a, s[1] + b, s[2] + c, s[3] + d}
}
// Sum は data の指紋を返す。
func Sum(data []byte) [Size]byte {
s := iv
padded := append(append([]byte{}, data...), padding(len(data))...)
for i := 0; i < len(padded); i += BlockSize {
s = compress(s, padded[i:i+BlockSize])
}
return toBytes(s)
}
func toBytes(s [4]uint32) [Size]byte {
var out [Size]byte
for i, w := range s {
binary.LittleEndian.PutUint32(out[i*4:], w)
}
return out
}
func fromBytes(d [Size]byte) [4]uint32 {
var s [4]uint32
for i := range s {
s[i] = binary.LittleEndian.Uint32(d[i*4:])
}
return s
}compress が 1 ブロックを状態に混ぜる圧縮関数だ。加算・XOR・ローテートを繰り返してなだれ効果を作り、最後に元の状態を足し戻す。この足し戻しが一方向性の要で、これがないと圧縮を逆算できてしまう。テストで、hello と hellp の 1 文字違いで指紋のビットが 1/4 以上変わることを固定した。理想は半分で、実物の SHA-256 はほぼ半分変わる。
② 長さ拡張攻撃: 素朴なMACが破れる
ここで穴を突く。上の Sum は、入力に詰め物(padding)を足してブロック境界に揃え、全ブロックを混ぜた状態を指紋として返す。最後に特別な変換をしていないので、指紋は「入力を処理し終えた内部状態」そのものだ。ということは、指紋さえあれば、そこから処理を続けられる:
// padding は msgLen バイトのメッセージの後ろに付く詰め物を返す。
// 0x80 の 1 バイト + 0 の並び + 末尾 8 バイトにビット長。これで全体が
// BlockSize の倍数になる。末尾に長さを書くのが Merkle–Damgård 強化。
func padding(msgLen int) []byte {
// 0x80 と 8 バイト長を除いて、ブロック境界に揃うだけの 0 を入れる。
zeros := (BlockSize - (msgLen+1+8)%BlockSize) % BlockSize
pad := make([]byte, 1+zeros+8)
pad[0] = 0x80
binary.LittleEndian.PutUint64(pad[1+zeros:], uint64(msgLen)*8)
return pad
}
// Extend は長さ拡張攻撃を実演する。
// 攻撃者は secret を知らなくても、H(secret‖orig) の値(digest)と
// secret‖orig の長さ(origLen)さえ分かれば、末尾に ext を継ぎ足した
// H(secret‖orig‖glue‖ext) を正しく計算できる。glue は元の詰め物。
//
// 素朴な構成では digest がそのまま内部状態なので、そこから処理を続けられる。
// これが「H(secret‖msg) を認証符号にしてはいけない」理由。
func Extend(digest [Size]byte, origLen int, ext []byte) (forged [Size]byte, glue []byte) {
glue = padding(origLen)
s := fromBytes(digest) // digest = secret‖orig‖glue 処理後の内部状態
totalLen := origLen + len(glue) + len(ext)
tail := append(append([]byte{}, ext...), padding(totalLen)...)
for i := 0; i < len(tail); i += BlockSize {
s = compress(s, tail[i:i+BlockSize])
}
return toBytes(s), glue
}攻撃はこう進む。サーバが tag = H(secret‖msg) を公開している。攻撃者は secret を知らないが、tag は手に入る。secret‖msg の長さも、msg が既知なら secret の長さを総当たりで当てられる。長さが分かれば Extend で、tag を内部状態に戻し、元の詰め物(glue)の続きに &to=attacker を継ぎ足した、正しい tag を計算できる。サーバから見れば msg‖glue‖&to=attacker という改ざんされたメッセージに、正しい tag が付いている。テストで、この偽造 tag がサーバの計算する本物の tag と一致することを固定した。攻撃は成功する。教訓は 1 つ。H(secret‖msg) を認証符号にしてはいけない。
③ HMAC: 正しい鍵付きハッシュ
対策は、内側のハッシュを外側でもう一度包むことだ。HMAC は鍵を 2 通りに変形して、内と外の 2 回ハッシュする:
// HMAC は鍵付きハッシュによる認証符号。長さ拡張攻撃に強い。
//
// HMAC(k, m) = H((k⊕opad) ‖ H((k⊕ipad) ‖ m))
//
// 内側のハッシュをさらに外側で包むので、内側を拡張しても外側の指紋は偽造できない。
func HMAC(key, msg []byte) [Size]byte {
// 鍵がブロックより長ければ一度ハッシュして縮める。
if len(key) > BlockSize {
k := Sum(key)
key = k[:]
}
k := make([]byte, BlockSize)
copy(k, key) // 短い鍵は 0 詰め
ipad := make([]byte, BlockSize)
opad := make([]byte, BlockSize)
for i := range k {
ipad[i] = k[i] ^ 0x36
opad[i] = k[i] ^ 0x5c
}
inner := Sum(append(ipad, msg...))
return Sum(append(opad, inner[:]...))
}
// Equal は 2 つの指紋を比べる(定数時間。早期 return でタイミングを漏らさない)。
func Equal(a, b [Size]byte) bool {
var diff byte
for i := 0; i < Size; i++ {
diff |= a[i] ^ b[i]
}
return diff == 0
}
// HashPassword は塩と反復でパスワードをハッシュする。
// 速いハッシュ 1 回では総当たりに弱い。塩でレインボーテーブルを無効にし、
// 反復で 1 回の検証を意図的に重くして総当たりの単価を上げる。
func HashPassword(password, salt []byte, iters int) [Size]byte {
if iters < 1 {
iters = 1
}
h := Sum(append(append([]byte{}, salt...), password...))
for i := 1; i < iters; i++ {
// 毎回 塩を混ぜ直しながら反復する。
h = Sum(append(append([]byte{}, salt...), h[:]...))
}
return h
}
// VerifyPassword は保存済みハッシュと入力パスワードを定数時間で照合する。
func VerifyPassword(stored [Size]byte, password, salt []byte, iters int) bool {
return Equal(stored, HashPassword(password, salt, iters))
}HMAC(k, m) = H((k⊕opad) ‖ H((k⊕ipad) ‖ m))。内側 H((k⊕ipad)‖m) の結果を、さらに外側の H((k⊕opad)‖…) で包む。攻撃者が内側の指紋を拡張しようとしても、その指紋は外側のハッシュへの入力に過ぎず、外側の最終指紋は鍵なしには作れない。テストで、同じ拡張攻撃が HMAC には効かないことを固定した。ついでに Equal を定数時間比較にした。指紋の照合で「何バイト目で食い違ったか」が実行時間に出ると、そこから正解を 1 バイトずつ探られる(タイミング攻撃)。早期 return せず全バイト見ることでこれを防ぐ。
同じファイルにパスワードハッシュも入れた。パスワードを H(password) で保存するのは危ない。ハッシュが速いほど、攻撃者は漏れたハッシュに総当たりを高速にかけられる。よくあるパスワードの指紋を並べたレインボーテーブルも効く。塩(salt)をパスワードごとに変えて混ぜればレインボーテーブルは無効になり、反復で 1 回の計算を意図的に重くすれば総当たりの単価が跳ね上がる。テストで、塩が違えば同じパスワードでも別の指紋になることを固定した。
動かす
下のデモは 3 つを試せる。ハッシュはなだれ効果(1 文字変えると指紋が総崩れ)、長さ拡張は攻撃が成功する様子、HMAC はそれが防がれる様子を並べて見る。
1 文字違いで指紋の 72/128 ビットが変わる。入力の微差が指紋を総崩れにする(なだれ効果)。だから改ざんは指紋の一致で検知できる
Go 実装をそのまま移植して計算している。ハッシュは 1 ビットの差を指紋全体に広げる(なだれ効果)。 だが素朴な H(secret‖msg) は、指紋が内部状態そのものなので、末尾を継ぎ足した正しい指紋を秘密なしで 偽造できる(長さ拡張攻撃)。HMAC は内側を外側で包むことでこれを防ぐ。認証符号には HMAC を使う。
設計の観点
- MAC には H(k‖m) でなく HMAC: 素朴な鍵前置きは長さ拡張で破れる。鍵付き認証符号は HMAC(または SHA-3 系や、AEAD の内蔵 MAC)を使う
- パスワードには汎用ハッシュを使わない: SHA-256 は速すぎてパスワード保存に不向き。bcrypt / scrypt / argon2 のように、塩・反復・メモリ困難性を持つ専用の関数を使う
- 比較は定数時間で: 指紋・トークン・MAC の照合は必ず定数時間比較。バイト単位の早期 return はタイミング攻撃の入口
- 衝突耐性の寿命: MD5・SHA-1 は衝突が現実に作られ、署名用途では危険。新規は SHA-256 以上。ハッシュ関数には寿命がある
- SHA-3 は構成が違う: SHA-3(Keccak)はスポンジ構成で、そもそも長さ拡張に強い。Merkle–Damgård 特有の穴を避けられる
対照と実例
| 用途 | 使うもの | 使ってはいけないもの | 理由 |
|---|---|---|---|
| 改ざん検知 | SHA-256 | MD5 / SHA-1 | 衝突が作れる |
| メッセージ認証 | HMAC-SHA256 | H(secret‖msg) | 長さ拡張で偽造される |
| パスワード保存 | argon2 / bcrypt / scrypt | 素の SHA-256 | 速すぎて総当たりされる |
| 指紋の照合 | 定数時間比較 | バイト単位の == | タイミング攻撃 |
裏どり:
- Flickr API 署名事件:
H(secret‖params)を署名に使っていて、長さ拡張攻撃で偽造された実例。この章の攻撃がそのまま現実に起きた - RFC 2104 (HMAC): HMAC の定義と、なぜ内外 2 回のハッシュで拡張攻撃を防げるかの根拠
- OWASP Password Storage: パスワードは argon2id 推奨、次点で scrypt / bcrypt。塩は必須、汎用ハッシュ単体は不可
- SHA-3 (Keccak): スポンジ構成で長さ拡張耐性を持つ。Merkle–Damgård の設計上の穴への回答
簡略化したこと
- 自作の弱いハッシュ: 128bit・8 ラウンドの玩具。衝突耐性は保証しない。構成と攻撃を見るためのもので、実運用は SHA-256 以上
- パスワードの反復は素朴: 実物はメモリ困難性(argon2/scrypt)も持たせる。ここは単純反復のみ
- 総当たりの長さ探索は省略: 攻撃では secret の長さを既知とした。実際は長さを 1 から試す
- エンコーディング省略: 指紋の 16 進表現やヘッダ形式は扱わない
参考資料
- RFC 2104: HMAC — HMAC の定義と設計根拠
- 長さ拡張攻撃 (Wikipedia) — 攻撃の原理と実例
- OWASP Password Storage Cheat Sheet — パスワード保存の現代的な指針
- 実装: crypto/hash