Idea

Costruire uno schema Mac sicuro per messaggi di lunghezza arbitraria basandosi direttamente su una funzione hash → due livelli di hash → $H^s(k_1,H^s(k_2,m))$

• un primo livello per creare il digest
• un secondo livello per autenticare

Costruzione

Sia $(Gen_H, H)$ una funzione hash costruita applicando la trasformata di Merkle-Damgard ad una funzione di compressione $(Gen_H,h)$ che prende input di lunghezza $n+n'$, siano $opad$ e $ipad$ delle costanti fisse di lunghezza $n'$

• $Gen$: $Gen_H(1^n) \to s$, sceglie uniformemente $k \in \{0,1\}^{n'}$ e dà in output $<s,k>$
• $Mac$: con input $<s,k>$ ed $m \in \{0,1\}^*$, dà in output $t:= H^s((k \oplus opad) || H^s((k \oplus ipad)||m))$
• $Vrfy$: con input $<s,k>$, $m \in \{0,1\}^*$ e $t$, dà in output $1$ se e solo se $t = H^s((k \oplus opad)||H^s((k \oplus ipad)||m))$

Sicurezza

Può essere vista come una specifica istanza del paradigma Hash-and-Mac:

• associa una stringa corta ad un messaggio di lunghezza arbitraria $y:= H^s((k \oplus ipad) ||m)$
• calcola con una funzione a chiave segreta $t:=H^s((k \oplus opad)|| \tilde y)$

Più precisamente, sia $\tilde H^s(m) := H^s((k \oplus ipad) ||m)$ $\Rightarrow$ $\tilde H^s$ è collision-resistant se $h$ lo è, per qualsiasi valore di $k \oplus ipad$

Inoltre il primo passo nel calcolo di $t$ consiste nel calcolare il valore $k_{out} := h^s(IV|| k \oplus opad)$ per poi calcolare $t:= h^s(k_{out}|| \tilde y)$, pertanto se trattiamo $k_{out}$ come una stringa uniforme e assumiamo che $\tilde Mac_k (y) := h^s(k||y)$ sia un Mac sicuro a lunghezza fissa, allora HMAC è un’istanziazione di Hash-and-Mac → $HMAC_{s,k} = \tilde Mac_{k_{out}}(\tilde H^s(m))$

Le costanti $ipad$ ed $opad$ servono a derivare efficientemente due chiavi da una sola

La sicurezza di HMAC si basa sul concetto di weak collision-resistance, che è più semplice da soddisfare

Se assumiamo che $G^s(k) = h^s ( IV|| (k \oplus opad))||h^s(IV||(k \oplus ipad)) = k_{out} ||k_{in}$ sia un PRG per qualsiasi valore di $s$, allora $k_{out}$ e $k_{in}$ possono essere considerate chiavi indipendenti ed uniformemente distribuite

Teorema