# 「Cryptography-Boneh」:Integrity

• 串行构造：CBC-MAC、NMAC、CMAC
• 并行构造：PMAC、HMAC（下一篇文章）
• 基于one-time MAC: CW MAC

# Message Auth. Codes

Def: MAC I = (S, V) defined over (K, M, T) is a pair of algs:

• S(k, m) outputs t in T
• V(k, m, t) outputs ‘yes’ or ‘no’

MAC是一组定义在(K, M, T)上的算法(S, V)，生成tag的算法S(k, m)和验证tag的算法V(k, m, tag)。

## Secure MACs: Model

• Attacker’s power: chosen message attack
选择明文攻击: 对于任意的消息 $\mathrm{m_1,m_2,…,m_q}$ ，攻击者能得到其对应的消息验证码 $\mathrm{t}_{\mathrm{i}} \leftarrow \mathrm{S}\left(\mathrm{k}, \mathrm{m}_{\mathrm{i}}\right)$
• Attacker’s goal: existential forgery
伪造: 希望能伪造 新的 message/tag (m,t)。
新的，意味着 $(\mathrm{m}, \mathrm{t}) \notin\left\{\left(\mathrm{m}_{1}, \mathrm{t}_{1}\right), \ldots,\left(\mathrm{m}_{\mathrm{q}}, \mathrm{t}_{\mathrm{q}}\right)\right\}$

new valid message/tag pair:

• attacker cannot produce a valid tag for a new message.
意味着不能为新的消息生成有效的tag
• given (m,t) attacker cannot even produce (m,t’) for $\mathrm{t’\ne t}$
也不能为原消息生成新的tag

## Secure MACs: Def

Def：I=(S, V) is a secure MAC if for all “efficient” A:
$$\mathrm{Adv_{MAC}[A,I]=Pr[Chal. output 1]\quad is “negligible”}$$

e.g.1:

e.g.2:

# MACs Based on PRFs

• S(k, m) := F(k, m)
• V(k, m, t): output ‘yes’ if t = F(k,m) and ‘no’ otherwise.

## Security

Thm:

If $\mathrm{F:K\times X\rightarrow Y}$ is a secure PRF and 1/|Y| is negligible(i.e. |Y| is large) then $\mathrm{I_F}$ is a secure MAC.

In particular, for every eff. MAC adversary A attacking $\mathrm{I_F}$ there exists an eff. PRF adversary B attacking F s.t.:
$$\mathrm{Adv_{MAC}[A,I_F]\le Adv_{PRF}[B, F]+1/|Y|}$$
$\mathrm{I_F}$ is secure as long as |Y| is large, say |Y| = $2^{80}$.

## Truncating MACs based on PRFs

Truncating MACs的定义如下：

Easy lemma: suppose $\mathrm{F:K\times X\rightarrow {0,1}}$ is a secure PRF.

Then so is $\mathrm{F_t(k,m)=F(k,m)[1\dots t]}$ for all $\mathrm{1\le t\le n}$

if (S,V) is a MAC is based on a secure PRF outputing n‐bit tags the truncated MAC outputing w bits is secure as long as $\mathrm{1/2^w}$ is still negligible (say w≥64)

## Examples

AES可以看作为：a MAC for 16-byte messages.

• CBC-MAC (banking – ANSI X9.9, X9.19, FIPS 186‐3)
• HMAC (Internet protocols: SSL, IPsec, SSH, …)

# Sequential Constructions

From here on let $\mathrm{X={0,1}^n}$ (e.g. n=128)

## 1. CBC-MAC

CBC-MAC 也叫 encrypted CBC-MAC (ECBC)

PRP: $\mathrm{F:K\times X\rightarrow X}$ .

ECBC定义新的PRF $\mathrm{F_{ECBC}:K^2\times X^{\le L}\rightarrow X}$ .

## 2. NMAC

NMAC即 nested MAC。

PRF: $\mathrm{F:K\times X\rightarrow K}$

NMAC定义新的PRF $\mathrm{F_{NMAC}:K^2\times X^{\le L}\rightarrow K}$ .

## Last Encryption

Why the last encryption step in ECBC-MAC ?

NMAC:

Then this MAC can be forged with one chosen msg query.

Extension Attack:

ECBC：

Then $\mathrm{I_{RAW}=(S,V)}$ is easily broken using a 1-chosen msg attack.

1-chosen msg attack:

1. 攻击者随机选择one-block message m.

2. 请求得到m对应的tag t = F(k,m)

3. 攻击者可以伪造2-block message $\mathrm{(m,t\oplus m)}$ 的MAC，其实也就是 t。

$\operatorname{rawCBC}(\mathrm{k},(\mathrm{m}, \mathrm{t} \oplus \mathrm{m}))=\mathrm{F}(\mathrm{k}, \mathrm{F}(\mathrm{k}, \mathrm{m}) \oplus(\mathrm{t} \oplus \mathrm{m}))=\mathrm{F}(\mathrm{k}, \mathrm{t} \oplus(\mathrm{t} \oplus \mathrm{m}))=\mathrm{t}$

## Security Analysis

Theorem: For any L > 0,

For every eff. q-query PRF adv. A attacking $\mathrm{F_{ECBC}}$ or $\mathrm{F_{NMAC}}$ , there exists an eff. adversary B s.t.:

$$\begin{array}{l}\operatorname{Adv}_{\mathrm{PRF}}\left[\mathrm{A}, \mathrm{F}_{\mathrm{ECBC}}\right] \leq \mathrm{Adv}_{\mathrm{PRP}}[\mathrm{B}, \mathrm{F}]+2 \mathrm{q}^{2} /|\mathrm{X}| \\ \operatorname{Adv}_{\mathrm{PRF}}\left[\mathrm{A}, \mathrm{F}_{\mathrm{NMAC}}\right] \leq \mathrm{q} \cdot \mathrm{L} \cdot \mathrm{Adv}_{\mathrm{PRF}}[\mathrm{B}, \mathrm{F}]+\mathrm{q}^{2} / 2|\mathrm{~K}|\end{array}$$

CBC‐MAC is secure as long as q << $|X|^{1/2}$

NMAC is secure as long as q << $|K|^{1/2}$

(q << $2^{64}$ for AES-­128)

q = #messages MAC-ed with k

• 对于基于AES的$\mathrm{F_{ECBC}}$：|X|=$2^{128}$ ，q必须满足 q < $2^{48}$ 。所以在对 $2^{48}$ 个messages进行MAC运算后，必须更换密钥。
• 对于基于3DES的$\mathrm{F_{ECBC}}$: |X|= $2^{64}$ ，q必须满足 q < $2^{16}$ .

### Extension Property

$$\forall \mathrm{x}, \mathrm{y}, \mathrm{w}: \mathrm{F}_{\mathrm{BIG}}(\mathrm{k}, \mathrm{x})=\mathrm{F}_{\mathrm{BIG}}(\mathrm{k}, \mathrm{y}) \quad \Rightarrow \quad \mathrm{F}_{\mathrm{BIG}}(\mathrm{k}, \mathbf{x||w} )=\mathrm{F}_{\mathrm{BIG}}(\mathrm{k}, \mathbf { y||w })$$

### The security bounds are tight: an attack

After signing $|X|^{1/2}$ messages with ECBC-MAC or $|K|^{1/2}$ messages with NMAC,

the MACs become insecure.

1. 随机选取 $|Y|^{1/2}$ 个不同的消息，请求询问得到对应的tag: $(m_i,t_i)$
2. 根据生日悖论，可以找到碰撞：$t_u=t_v$
3. 选择w，攻击者构造消息 $m_u||w$，请求询问其tag： $\mathrm{t}:=\mathrm{F}_{\mathrm{BIG}}\left(\mathrm{k}, \mathrm{m}_{\mathrm{u}} \| \mathrm{w}\right)$
4. 此时，攻击者可以成功伪造pair： $\mathrm{(m_{v} || w, t})$
根据可扩展性， $\mathrm{t}=\mathrm{F}_{\mathrm{BIG}}\left(\mathrm{k}, \mathrm{m}_{\mathrm{v}} \| \mathrm{w}\right)$

## Rand. Construction

Let $\mathrm{F:K\times X\rightarrow X}$ be a PRF.

Security: $\mathrm{A d v_{M A C}\left[A, I_{R C B C}\right] \leq A d v_{P R P}[B, F] \cdot\left(1+2 q^{2} /|X|\right) }$

## Comparison

ECBC‐MAC 的构造方式常常用来构造基于AES的MAC

• 比如CCM encryption mode (used in 802.11i)
• NIST standard called CMAC

• 主要的原因是：在NMAC中，对每个block的计算都需要更换AES密钥，也就需要重复进行AES密钥扩展。
• 但NMAC是HMAC的基础。

(The ‘1’ indicates beginning of pad)

• 对于msg长度不是block-size整数倍的情况，用’100..0’字符串进行填充：

• 对于msg长度是block-size整数倍的情况，需要增加一个dummy block:

## CMAC (NIST standard)

key $=(k,k_1,k_2)$

• No final encryption step (extension attack thwarted by last keyed xor)
因为最后一步使用密钥$k_2$异或，所以不知道函数F(k, ·)的输入，也就不能进行extension attack。
• No dummy block (ambiguity resolved by use of $k_1$ or $k_2$)
最后一步通过两个不同密钥的使用来解决歧议情况。

# Parallel Constructions

ECBC和NMAC都是时序性(sequential)，本节将通过a small PRF构造a parallel MAC.

## 3. PMAC: parallel MAC

Let $\mathrm{F:K\times X\rightarrow X}$ be a PRF

P(k, i): an easy to compute function

padding: similar to CMAC, but no need for dummy block

1. m[i] 与 P(k, i)异或的必要性：如果不进行这一步，交换消息中的不同块，也可以得到相同的MAC，即block swapping attack，PMAC变得不再安全。所以P(k, i)的作用是保存消息的顺序。
2. 最后一块不需要再通过$F(k_1,\cdot)$，是技术原因。
3. 因为P(k, i)增加了block的块数/顺序信息，所以不需要增加dummy block。

### PMAC: Analysis

PMAC Theorem: For any L > 0,

If F is a secure PRF over (K,X,X) then $F_{PMAC}$ is a secure PRF over $\mathrm{(K,X^{\le L}, X)}$ .

For every eff. q-query PRF adv. A attacking $F_{PMAC}$, there exists an eff. PRF adversary B s.t.:
$$\mathrm{Adv_{PRF}[A,F_{PMAC}]\le Adv_{PRF}[B,F]+2q^2L^2/|X|}$$
PMAC is secure as long as qL << $|X|^{1/2}$ .

PMAC是可以增量计算的。

## One Time MAC

Def: I=(S,V) is a secure MAC if for all “efficient” A:
$$\operatorname{Adv}_{1 \mathrm{MAC}}[\mathrm{A}, \mathrm{l}]=\operatorname{Pr}[\text { Chal. outputs 1] } \quad \text { is “negligible.” }$$

### Example

One-time MAC可以抵抗所有的攻击者，具有unconditional security（perfect security）。此外，One-time MAC相对于基于PRF的MAC，具有更快的运算速度。

One-time MAC can be secure against all adversaries and faster than PRF-based MACs.

$\mathrm{q}$: 一个大素数（比如q = $2^{128}$ +51)

$\mathrm{\text {key}=(a, b) \in{1, \ldots, q}^{2}}$ : 两个随机数

$\mathrm{\mathrm{msg}=(\mathrm{m}[1], \ldots, \mathrm{m}[\mathrm{L}])}$ ：每一块都看作是是128 bit的整数

MAC ：计算以msg作为系数的多项式
$$\begin{array}{c}S(\text { key, msg} )=\mathrm{P_{m s g}(a)+b \quad(\bmod q)} \ \text { where } \mathrm{P_{m s g}(x)=x^{L+1}+m[L] \cdot x^{L}+\ldots+m[1] \cdot x \quad \text { is a poly. of } \operatorname{deg} L+1 }\end{array}$$
We show: given S( key, $\mathrm{msg_1}$ ) adv. has no info about S( key, $\mathrm{msg_2}$ )

### Unconditional Security

Thm: the ont-time MAC in the example satisfies: (L = msg-len, q is the prime)
$$\mathrm{\forall m_{1} \neq m_{2}, t_{1}, t_{2}: \quad P r_{a, b}\left[s\left((a, b), m_{1}\right)=t_{1} \mid s\left((a, b), m_{2}\right)=t_{2}\right] \leq L / q}$$
Proof: $\forall \mathrm{m_1\ne m_2,t_1,t_2}:$

1. $\mathrm{\operatorname{Pr}_{a, b}\left[s\left((a, b), m_{2}\right)=t_{2}\right]=\operatorname{Pr}_{a, b}\left[P_{m_{2}}(a)+b=t_{2}\right]=1 / q}$ 对于任意的$m_2$，多项式计算出的结果等于$t_2$ 的概率为1/q。
2. $\mathrm{\operatorname{Pr}_{\mathrm{a}, \mathrm{b}}\left[s\left((\mathrm{a}, \mathrm{b}), \mathrm{m}_{1}\right)=\mathrm{t}_{1} \text { and } s\left((\mathrm{a}, \mathrm{b}), \mathrm{m}_{2}\right)=\mathrm{t}_{2}\right]}$ $=\operatorname{Pr}_{\mathrm{a}, \mathrm{b}}\left[\mathrm{P}_{\mathrm{m}_{1}}(\mathrm{a})-\mathrm{P}_{\mathrm{m}_{2}}(\mathrm{a})=\mathrm{t}_{1}-\mathrm{t}_{2} \text { and } \mathrm{P}_{\mathrm{m}_{2}}(\mathrm{a})+\mathrm{b}=\mathrm{t}_{2}\right] \leq \mathrm{L} / \mathrm{q}^{2}$
• 概率第二个条件，任意的$m_2$，多项式计算出的结果等于$t_2$ 的概率为1/q。
• 概率第一个条件，两式相减后，得到一个deg L的多项式，该多项式值为 $\mathrm{t_1-t_2}$ 的概率为1/q。但这是一个度为L的多项式，所以最多可能有L个根。所以第一个条件的概率是<=L/q
3. 最后使用条件概率

### Many-time MAC: Cater-Wegman MAC

(S,V): 是一个安全的one-time MAC over $(K_I,M,{0,1} ^n)$.

$F:K_F\times {0,1}^n \rightarrow {0,1}^n$ 是 安全的PRF.

Cater-Wegman MAC:
$$\mathrm{C W\left(\left(k_{1}, k_{2}\right), m\right)=\left(r, F\left(k_{1}, r\right) \oplus S\left(k_{2}, m\right)\right)} \quad \text{ for random r }\leftarrow {0,1}^n$$
CW MAC首先选取了一个随机值 r，然后用PRF对随机值加密,，得到 $\mathrm{F(k_1,r)}$ 。再用one-time MAC作用于消息，得到的结果与PRF的结果异或。

Thm : If (S,V) is a secure one-time MAC and F is a secure PRF, then CW is a secure MAC outputting tags in ${0,1}^{2n}$ .

• [basis of CBC MACs] J. Black, P. Rogaway: CBC MACs for Arbitrary-­Length Messages: The Three­Key Constructions. J. Cryptology 18(2): 111‐131 (2005)
• K. Pietrzak: A Tight Bound for EMAC. ICALP (2) 2006: 168-179
• [PMAC] J. Black, P. Rogaway: A Block-­‐Cipher Mode of Operation for Parallelizable Message Authentication. EUROCRYPT 2002: 384-­‐397
• [security of NMAC] M. Bellare: New Proofs for NMAC and HMAC: Security Without Collision­Resistance. CRYPTO 2006: 602-­‐619
• Y. Dodis, K. Pietrzak, P. Puniya: A New Mode of Operation for Block Ciphers and Length-Preserving MACs. EUROCRYPT 2008: 198‐219

「Cryptography-Boneh」:Integrity

https://f7ed.com/2021/11/22/stanford-integrity1/

f7ed

2021-11-22

2021-12-28