「Cryptography-Dan」:Integrity 1

「Cryptography-Dan」:Integrity 1

这篇文章主要介绍消息验证码,即MAC (Message Auth. Code)。

文章首先介绍了secure MAC的模型和安全定义,当攻击者能伪造出新的msg/tag对时,MAC就不再安全。

文章的第二部分介绍了基于PRF的MAC构造,根据相关定理,只要PRF的输出空间足够大,且这是一个安全的PRF,则基于PRF的MAC就是安全的。

但基于PRF的MAC只能计算固定消息大小的MAC,如何利用这个工具构造出更大消息空间的MAC?

文章后半部分给出了一些主流的MAC构造:

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

此外,文章还介绍了MAC Padding技术。

Message Auth. Codes

本节的目标是保证消息的完整性,暂时不考虑消息机密性。

比如保护磁盘上的公共二进制文件不会被篡改,保护web页面上的广告消息不会被替换篡改。

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)。

MACs

消息的完整性需要发送方和接收方共享一个密钥。

如果是用CRC来保证消息的完整性,攻击者可以修改消息,并轻易的计算出新的CRC。

Integrity requires a secret key

所以CRC可以用于检测随机错误(信道噪声),而不能用于检测恶意修改。

Secure MACs: Model

在定义安全MACs的模型中:

  • 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

在定义的MAC游戏中:

MAC game

首先挑战者会随机选择密钥 $\mathrm{k\leftarrow K}$ ,作为MAC的签名算法的密钥。

攻击者向挑战者发起q个询问,每次询问都可以得到该消息对应的消息验证码。

攻击者会生成一对msg/tag pair: (m, t),如果该pair通过了挑战者的验证算法,并且是一对新的msg/tag pair,挑战者输出:1,否则输出0。

所以secure MACs定义为:攻击者生成new message/tag pair 通过挑战者验证算法的概率为neg.

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.1

两个消息具有同样tag的概率为1/2,所以Adv[A, I]=1/2.

e.g.2:

e.g.2

同理,tag的长度是5bits,所以两个不同消息有同样tag的概率为1/32.

MACs Based on PRFs

任何PRF都可以转换为MAC。

对于一个PRF: $\mathrm{F:K\times X\longrightarrow Y}$

由该PRF定义的MAC $\mathrm{I_F=(S,V)}$ 为:

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

但安全的PRFs不一定可以生成安全的MACs,比如:

a bad example

由上式子生成的MACs并不是一个安全的MACs,因为tag的长度太短,攻击者可以为任何消息猜测其tag。

Security

所以,要保证基于PRFs的MACs的安全性,还需要PRF的输出空间足够大,否则攻击者可以通过猜测攻击成功。

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}$.

对于每一个攻击MAC的攻击者A,都存在攻击对应PRF的攻击者B,满足上述式子。所以如果不等式右边都为neg.,那不等式左边一定为neg.

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}$

基于PRFs的MACs,截断后的MACs,如果tag长度足够长,也是安全的。

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.

所以引入了一个新的问题:how to convert small-MAC into a Big-MAC ?

实践中有两种主流构造方法:

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

Sequential Constructions

本节的主要目标是: given a PRF for short messages (AES) construct a PRF for long messages.

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}$ .

新的PRF的输入为:一对密钥 和 long messages (L: blocks)

CBC-MAC

绿色部分就是原生的CBC(使用密钥k),而encrypted表现在对CBC的输出再进行加密操作(使用密钥 $\mathrm{k_1}$ ,得到消息的MAC。

需要注意的是,最后对CBC输出进行加密的密钥是独立于CBC的密钥。

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}$ .

新的PRF的输入为:一对密钥 和 long messages (L: blocks)

NMAC

绿色部分是层叠(cascade)部分,把本次消息块PRF的输出作为下次消息块PRF运算的密钥,cascade部分的输出为t。

最后对t做padding操作(fixed pad),对于padding后的结果,用新的密钥 $\mathrm{k_1}$ 再做一次PRF运算,得到最终的MAC。

Last Encryption

在ECBC和NMAC中,最后都有加密的步骤。

Why the last encryption step in ECBC-MAC ?

NMAC:

假设NMAC只有cascade部分,即S(k,m)=cascade(k,m)

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

Extension Attack:

已知cascade(k, m),对于任意消息块w,可以轻易得到cascade(k, m||w)的值。

因为cascade(k, m)是作为下一个消息块运算的密钥,所以cascade(k, m||w) = PRF(cascade(k, m), w)。

所以最后的加密步骤是为了阻止extension attack。

ECBC:

同样,假设ECBC只有raw CBC部分,没有最后加密的步骤,即S(k,m)=rawCBC(k,m).

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)


为了简化讨论,考虑不等式: $\operatorname{Adv}_{\mathrm{PRF}}\left[\mathrm{A}, \mathrm{F}_{\mathrm{ECBC}}\right] \leq \mathrm{Adv}_{\mathrm{PRP}}[\mathrm{B}, \mathrm{F}]+ \mathrm{q}^{2} /|\mathrm{X}|$

q = #messages MAC-ed with k

如果我们想得到 $\operatorname{Adv}_{\mathrm{PRF}}\left[\mathrm{A}, \mathrm{F}_{\mathrm{ECBC}}\right] \leq 1 / 2^{32}$ 的结果,必须满足: $\mathrm{q^{2} /|X|<1 / 2^{32} }$

  • 对于基于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

如果构造出的PRFs(ECBC 和 NMAC)的底层PRF是一个PRP(比如AES),那么构造出的PRFs都有可扩展性:

$$ \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 }) $$

因为底层是一个PRP,所以$F(k_1,\cdot)$ 是一个one to one function,输出相同,对应的输入也是相同的,因此rawCBC或者NCBC的cascade部分的输出是相同的。

The security bounds are tight: an attack

上述定理的安全约束是紧的,所以当q不满足约束时,MAC就不安全了。

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

the MACs become insecure.

对于满足可扩展性的PRF $\mathrm{F}_{\mathrm{BIG}}: \mathrm{K} \times \mathrm{X} \longrightarrow \mathrm{Y}$ , 可以构造出一般攻击:

  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

另一种引入随机性的构造,可以具备更好的安全性。

a rand. construction

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

将rawCBC的结果和随机值,构造为2-block,再次进行运算。

最终的结果:MAC with tags in $X^2$

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) }$

在这种构造情况下,3DES can sign q = $2^{32}$ msgs with one key.

Comparison

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

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

而NMAC的构造方式一般不使用AES或3DES

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

MAC Padding

如果msg的长度不是block-size的整数倍,就需要对msg进行padding操作。

CBC MAC padding

如果只是简单对msg进行0填充,那将会得到一个不安全的MAC,因为pad(m) = pad(m||0),所以对于给定msg m 的tag,攻击者可以轻易得到m||0的tag。

因此,为了安全性的考虑,padding操作应该是可逆的,所以如果两个消息是不同的,那么进行padding操作后的消息也应该是不同的,即: $\mathrm{m}_{0} \neq \mathrm{m}_{1} \quad \Rightarrow \quad \operatorname{pad}\left(\mathrm{m}_{0}\right) \neq \operatorname{pad}\left(\mathrm{m}_{1}\right)$ ,否则攻击者就可以利用该特性进行伪造。

ISO: pad with ‘1000…00’. Add new dummy block if needed.

(The ‘1’ indicates beginning of pad)

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

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

    padding 如果不增加dummy block,padding function就不可逆了。

CMAC (NIST standard)

介绍padding后,这里介绍一种CBC-MAC的变体,也是NIST的标准。

CMAC

key $=(k,k_1,k_2)$

在这种构造方式下,没有最后一步的加密步骤,padding时也不需要增加dummy block。

  • 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

定义新的PRF:$\mathrm{F_{PMAC}:K^2\times X^{\le L}\rightarrow X}$ , key $=(k,k_1)$

PMAC

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

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

首先用P(k, i)对msg的每一块执行异或操作,这一步可以同步进行。异或的结果再作为$F(k_1,\cdot)$ 的输入,最后把所有$F(k_1,\cdot)$的输出异或在一起,作为最后一层$F(k_1,\cdot)$ 的输入,最终得到tag.

几点说明:

  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 is incremental

PMAC是可以增量计算的。

PMAC is incremental

如果m[1]变成m’[1]后,可以快速更新tag = $\mathrm{F}^{-1}\left(\mathrm{k}_{1}, \mathrm{tag}\right) \oplus \mathrm{F}\left(\mathrm{k}_{1}, \mathrm{m}[1] \oplus \mathrm{P}(\mathrm{k}, 1)\right) \oplus \mathrm{F}\left(\mathrm{k}_{1}, \mathrm{m}^{\prime}[1] \oplus \mathrm{P}(\mathrm{k}, 1)\right)$

One Time MAC

One-time MAC 也是One-time pad的类比,密钥只应用于一条消息。

定义的MAC游戏如下,攻击者只能得到一条消息对应的tag:

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}$ )

在One- time MAC中,S(key, $\mathrm{msg_1}$ )不会透露任何关于S(key, $\mathrm{msg_2}$)的信息,所以One-time key是绝对安全的,但和ont-time pad 类似,如果将相同密钥作用于不同的消息上,two-time MAC则是不安全的。

Unconditional Security

在上面的例子中:given S( key, $\mathrm{msg_1}$ ) adv. has no info about S( key, $\mathrm{msg_2}$ ),现在我们来证明one-time MAC的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. 最后使用条件概率

该定理表明,只得到一对有效的 $(m_2,t_2)$,攻击者构造出有效 $(m_1,t_1)$ 的概率 $\le \mathrm{L/q}$ .

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的结果异或。

这也是一个randomized MAC,当计算不同消息验证码时,密钥可以重复使用,但每次都选取不同的随机值。PRF计算较慢,但作用在一个较短的随机串上,one-time MAC计算更快,作用在较长的消息串上。

CW MAC

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}$ .

Further Reading

  • [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

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×