###### tags: `memo` `security`
# メッセージ認証コード(MAC)勉強メモ

## 効果
A が B にメッセージを送信することを考えた場合、MACは以下を保証

1. メッセージが改ざんされていない（改ざん防止）
2. メッセージは A が送ったものである（なりすまし防止）

ただし、2. は再送攻撃がない前提

## 前提条件
A, B 間で秘密鍵を共有する必要がある

## ざっくりとした動作
1. A, B 間で秘密鍵を共有
2. A はメッセージ M と秘密鍵 K からタグ T を生成する
3. A は M, T を B に送信する
4. B は M と自身が持つ秘密鍵 K からタグ T' を生成する
5. B と T と T' を比べ、一致していたら改ざんはない

## 再送攻撃
通信路上の M, T を攻撃者がキャッチして、再度 B に投げたとき、B は M, T が A から送られたのか、攻撃者の再送攻撃によって送られたのか確かめるすべはない

## 例. HMAC (Hash function-based MAC)
### 基本的な発想

ハッシュ関数に K とメッセージをぶち込んだったら、いい感じにタグ作れるだろというモチベ

$$
MAC_K(M) = h(K, M)
$$

h はハッシュ関数をつかって K, M をごにょごにょする関数

### ナイーブな発想
秘密鍵 K とメッセージ M を連結して、ハッシュ関数に入れる

$$
h(K, M) = H(K || M)\ or\ H(M || K)
$$

H はハッシュ関数、|| は連結

#### K が頭に来る場合 --- secret prefix
伸長攻撃ができる

攻撃者 Oscar は通信路上から M と T = H(K || M) を盗める。なので、テキトーなメッセージ M' を使って、H(K || M || M') を作れる。これで攻撃者は、MAC の検証をパスできるメッセージとタグのペア(M || M', K)を生成できたことになる

これは padding を考慮していないので、padding を考慮するともうすこしややこしくなる

#### M が頭に来る場合 --- secret suffix
ハッシュ関数 H の衝突困難性が破れたとする。つまり、M != M', H(M) == H(M') なる衝突ペア (M, M') が見つかったとする

H(M) == H(M') なので、反復型ハッシュ関数の性質上 H(M || K) == H(M' || K) になる。

このとき、攻撃者は異なるメッセージ（M, M'）に対して同一のタグを生成できたことになる

**secret suffix の場合 MAC の強さはハッシュ関数の衝突困難性に依存する**

### HMAC の定義
FIPS PUB 198-1 によると

MAC(text) = HMAC(K, text) = H((K0 ⊕ opad) || H((K0 ⊕ ipad) || text))

------------

プログラムっぽく書くと

HMAC(K, text) {
    K0 = pre_process(K)
    H1 = H((K0 ⊕ ipad) || text) // inner hash
    H2 = H((K0 ⊕ opad) || H1)   // outer hash
    return H2
}

ipad, opad は固定値

簡単にいうと

secret prefix を 2 回繰り返す

HMAC で伸長攻撃をするためには H1 を知る必要があるが、H1 は内部ハッシュ値で攻撃者にはわからないので、攻撃は難しくなるということなのかなー…

#### 実装

import hmac
from secrets import token_bytes
from hashlib import sha256
from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import long_to_bytes as l2b

def _hmac(key: bytes, m: bytes, H) -> bytes:
    B = H().block_size
    L = H().digest_size

    # key を長さ B バイトに揃える
    if len(key) > B:
        key = H(key.ljust(B, b"\x00")).digest()
    elif len(key) < B:
        key = key.ljust(B, b"\x00")

    # 1 回目のハッシュ化
    ipad = b2l(b"\x36" * B)
    h1 = H(l2b(b2l(key) ^ ipad) + m).digest()

    # 2 回目のハッシュ化
    opad = b2l(b"\x5c" * B)
    h2 = H(l2b(b2l(key) ^ opad) + h1).digest()

    # h2 が tag になる（場合によっては、先頭数バイトだけ使うことも）
    return h2

m = "ニイタカヤマノボレ".encode("utf-8")
H = sha256
key = token_bytes(H().digest_size // 2)

print(_hmac(key, m, H))
print(hmac.new(key, m, H).digest())

出力

$ python m_hmac.py
b'\xad8\xbc\x94\xa9r\xa9\xf4\x89\x9bv \xb93\xeeK\xc7\x07.\xd8\xce\x1a\x0fT(*\xba_\xd2\x16\xa7\xd0'
b'\xad8\xbc\x94\xa9r\xa9\xf4\x89\x9bv \xb93\xeeK\xc7\x07.\xd8\xce\x1a\x0fT(*\xba_\xd2\x16\xa7\xd0'

## MAC にできないこと
### メッセージの暗号化
MAC では、タグを使ったメッセージの検証が主な目的なので、メッセージの暗号化については考慮されていない。このあたりは別の要素技術で補う必要がある

### 否認防止
秘密鍵を使う性質上、メッセージからタグを作ることは送信側も受信側もできる。なので、受信側が勝手に作ったタグだと、送信側が言い張れば、それを否認することはできない

### 第三者に対する完全性を保証できない
秘密鍵を使うのでもちろん、秘密鍵を共有していない第三者に対してMACは使えない

## 参考
- CIPHER and CODE 暗号技術のすべて
- https://www.cryptrec.go.jp/report/cryptrec-gl-2001-2013r1.pdf
- https://tools.ietf.org/html/rfc2104
- https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.198-1.pdf
- https://www.youtube.com/watch?v=DiLPn_ldAAQ