由淺入深的白話 HMAC 問答

Q： HMAC (Hash-based Message Authentication Code) 的功能是什麼？
A： 甲跟乙在網路上通訊， 甲寄訊息 m 給乙， 乙想確認 m 真的是甲寄的， 不是別人偽造的。
Q： 那就叫甲寄出 m 的時候採用 (非對稱密碼學的) 數位簽章就好了， 不是嗎？
A： HMAC 的演算法比數位簽章簡單很多， 也快很多。 特別是當甲跟乙頻繁來回簡短對話的場合， HMAC 合適多了。
Q： 那為什麼不用 HMAC 取代所有的數位簽章？
A： 數位簽章具有 不可否認性， 是 HMAC 無法取代的。 因為 HMAC 採用對稱式密碼學， 甲跟乙都需要知道一把共同的金鑰 K， 而任何知道 K 的人， 也都可以用 K 跟 m 產出讓乙滿意的訊息。 例如乙收到的 m 是一筆很大的訂單， 於是開心地備餐交貨， 結果甲說那不是我下的單， 可能是我們共用的 K 外洩了!@#$ 這時乙也無法判斷甲到底有沒有說謊...
Q： HMAC 的數學式長怎樣？
A： HMAC(K, m) = H( (K' ⊕ opad) || H( (K' ⊕ ipad) || m) ) 甲算完送出之後， 乙握有相同的資訊， 可以驗證； 其他人沒有 K， 所以無法產生相同的 HMAC 值來欺騙乙。
Q： 太複雜了 orz
A： 其實原本的想法很簡單： HMAC_0(K, m) = H(K || m)， 其中 H 是某個 單向雜湊函數 ， 而 || 就只是表示把兩個字串接起來 (string concatenation) 而已。 根據單向雜湊函數的特性， 就算路人甲看到原始訊息 m 跟運算結果， 也無法倒回去算出 K， 當然也就不可能在沒有 K 的情況下，用一個假訊息 m_attack 瞎掰出一個乙可以接受的運算結果。
Q： OK， 這好懂。 但是？
A： 但是這個簡單的版本有可能受到 長度擴充攻擊： 丙知道甲送給乙的訊息是 m="二十顆水餃"， 也側錄到 HMAC_0(K, m) 的值 h0， 即使丙不知道 K， 他也能夠從 h0 跟 m 變造出 m1="二十顆水餃________喔，不，改成兩千顆好了。" 以及 HMAC_0(K, m1)=h1 然後寄這組偽造的 (m1,h1) 給乙， 而乙也會驗證成功、欣然接受。
Q： 蛤？ 這麼厲害？
A： 因為有很多單向雜湊函數 H 採用 Merkle–Damgård construction 類型的演算法。 這類演算法會把輸入資料 m 切成一段一段， 逐段疊加到前面所有段落的運算結果。 最後輸出的結果， 其實也可以視為 「更長的輸入字串尚未算完的中途半成果」， 所以攻擊者可以把這個中途半成果 (h0) 撿起來， 搭配 「原字串 m 後面用空格/底線補齊目前段落 (其實是補零)， 再增添任意的文字」 再套用原來的 H 演算法繼續把這個 H 函數算完。
Q： 所以解決之道是？
A： HMAC_1(K,m) = H(K || H(K || m)) 也就是 (有可能被拿來變造的) "中途半成果" 前面補 key 再 hash， 它就變成不是任何其他訊息的半成果。 有點像是蓋上瓶蓋。
Q： 那其他的修飾是...？
A： 剛剛說輸入字串會切成一段一段。 如果 K 的長度不是正好一段，那就要小手術一下得到長度正好的 K'， 詳見文章開始的維基百科連結。 至於為什麼要跟 ipad 跟 opad 做 xor？ 請參考 這個問答 跟 這個問答， 不過那已超出我的閱讀範圍了。

* * * * *

先前寫程式時遇到 HMAC 這個名詞， 有稍微讀一下。 這次認真爬文， 發現中英文文章的解釋都很難懂。 身為推廣科普的通識老師， 決定採用由淺到深的方式降低理解門檻， 讓更多人 - 包含非程式設計師 - 知道它的用途與設計理念。