HMAC正しく理解していますか？

プログラマーであれば一度は目にしたことがありそうなHMACですが、どうやって算出されているかを知ってる人は少ないかと思います。少なくとも私は頻繁に使うものの知りませんでした。

BIP32等ブロックチェーンの世界でも度々登場している他、API認証としても利用しています。メッセージに加えて、パスワードとなる暗号キーを用いてハッシュ値を生成するものという認識で、自分のサービスで使用する際はもっぱらユーザ認証目的で使用しています。

ブラックボックスとしている実際の算出方法は気にしたことがありませんでしたが、正しく理解するために調べた備考録としてこれを記します。

検索した所、HMACは1997年のRFC2104で定義されていましたが、これでは古すぎて今の利用のされ方と相違した定義になっていることも考えられます。そのためWikipediaで概要を確認した後RFC2104を読んでみます。

Wikipediaでの説明

Wikipediaは日本語と英語で情報量が違うことが多い為、今回も例に漏れず英語ページからの引用です。

In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. It may be used to simultaneously verify both the data integrity and the authentication of a message, as with any MAC. Any cryptographic hash function, such as SHA-256 or SHA-3, may be used in the calculation of an HMAC; the resulting MAC algorithm is termed HMAC-X, where X is the hash function used (e.g. HMAC-SHA256 or HMAC-SHA3). The cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function, the size of its hash output, and the size and quality of the key.
HMAC

HMACはHash-based Message Authentication Code、ハッシュを用いたメッセージ認証コードです。

ハッシュ関数と暗号鍵を使いデータの整合性と認証を確認する為のもので、強度は合わせて使用されるハッシュ関数の出力データ長に依存する・・・。

どうやら、やんわりとした理解で使ってきたHMACそのものの説明で、認識の誤りはないようです。

RFC2104

MAC(Message Authentication Codes)として

・様々なハッシュ関数で利用出来る
・利用するハッシュ関数のパフォーマンスを極力下げずに処理出来る

といったことを主目的としていて、算出ロジックはすごく短く明瞭です。

任意のハッシュ関数`H`
メッセージ`M`
暗号鍵`K`
`H`のブロック長を`B`とした時

ipad = 0x36の`B` bytes埋め(`0x363636...`)
opad = 0x5Cの`B` bytes埋め(`0x5C5C5C...`)

H(K XOR opad, H(K XOR ipad, M))

H(x,y)はxにyを付け加えてHのハッシュ計算です。
これをHMACとする。非常にシンプルです。

なぜ`ipad`と`opad`で0x36と0x5Cなのかは気になるところですが、ipad = opadとしてしまっては同一値をpaddingしながらのストレッチングに他なりません。ipad != opadが意図する所であり、異なりさえすれば何でも良いということでしょう。

また、`B`bytesの`ipad`、`opad`でXORを行うことから自明ですが、上記を実行する時`K`のデータ長は`B`bytesはなければいけません。

HMACでは`K`が`B`bytes未満の場合、`B`bytesになるまで末尾に`0x00`をpaddingし、`B`bytesを超える場合は評価前に`H(K)`を計算し、そのハッシュ値でKを置き換えます。

Scalaでのナイーブな実装は以下のようになります。

 type Bytes = Array[Byte]
 val (ipad,opad) = (0x36, 0x5C)

 def genHmacCalculator(h: Bytes => Bytes, b: Int): Bytes => Bytes => Bytes = {
   val xor = (k: Bytes, pad: Int) => k.map(_ ^ pad).map(_.toByte)
   k: Bytes => m: Bytes => {
     val actualK = k.length match {
       case x if x == b => k
       case x if x < b => k.padTo(b, 0.toByte)
       case x if x > b => h(k)
     }
     h(xor(actualK,opad) ++ h(xor(actualK,ipad) ++ m))
   }
 }

任意のハッシュ関数をHMAC利用出来るようにし、代表的なHMAC-SHA-256、HMAC-SHA-512でRFC4231のテストケースを満たすことを確認します。

Key = 4a656665 ("Jefe")
Data = 7768617420646f2079612077616e7420 ("what do ya want ")
666f72206e6f7468696e673f ("for nothing?")

HMAC-SHA-224 = a30e01098bc6dbbf45690f3a7e9e6d0f
8bbea2a39e6148008fd05e44
HMAC-SHA-256 = 5bdcc146bf60754e6a042426089575c7
5a003f089d2739839dec58b964ec3843
HMAC-SHA-384 = af45d2e376484031617f78d2b58a6b1b
9c7ef464f5a01b47e42ec3736322445e
8e2240ca5e69e2c78b3239ecfab21649
HMAC-SHA-512 = 164b7a7bfcf819e2e395fbe73b56e0a3
87bd64222e831fd610270cd7ea250554
9758bf75c05a994a6d034f65f8f0e6fd
caeab1a34d4a6b4b636e070a38bce737

RFC4231

import java.security.MessageDigest

val hmacSha256 = genHmacCalculator(MessageDigest.getInstance("SHA-256").digest, 64)
val hmacSha512 = genHmacCalculator(MessageDigest.getInstance("SHA-512").digest, 128)

hmacSha256("Jefe".getBytes)("what do ya want for nothing?".getBytes).map("%02X" format _).mkString
//5bdcc146bf60754e6a042426089575c75a003f089d2739839dec58b964ec3843

hmacSha512("Jefe".getBytes)("what do ya want for nothing?".getBytes).map("%02X" format _).mkString
//164b7a7bfcf819e2e395fbe73b56e0a387bd64222e831fd610270cd7ea2505549758bf75c05a994a6d034f65f8f0e6fdcaeab1a34d4a6b4b636e070a38bce737

一致していますね

まとめ

HMACは高速に処理可能なXORと、2回(Kの長さ > Bの場合は3回)で計算出来るシンプルな実装でした。
リクエスト電文に含めたメッセージの認証としてHMACをヘッダに含めるといった用途の場合は注意が必要です。

メッセージを盗み見られるとMと出力されたハッシュ値から第三者が総当たりでKを探すことになりますが、総当たりに必要な試行回数は2のKbit乗 × 2のハッシュ計算と非常に少なく済んでしまい、数TH/s程度のASICで英数字5,6桁ぐらいのパスワードであれば1秒以下で計算出来てしまいます。電文自体がセキュアに送られていない場合はKの長さに注意して使用する必要がありそうです。