Estensione del dominio

Progettazione di funzioni hash:

• prima progettiamo una funzione di compressione
• poi ne estendiamo il dominio per input di lunghezza arbitraria

Senza perdita di generalità, supponiamo che $(Gen, h)$ sia tale che comprima $2n$ bit $\to$ $n$ bit

$\Rightarrow$ $(Gen, H)$ usando la trasformazione di Merkle-Damgard $x \in \{0,1\}^* \to y \in \{0,1\}^n$

Trasformazione Merkle-Damgard

Il messaggio $x$ è diviso in blocchi di $n$ bit $x_1,..,x_B$

Alla fine del messaggio viene aggiunto un extra blocco $x_{B+1}$ in cui viene codificato, sempre con $n$ bit, la lunghezza del messaggio $x$

Ad ogni passo della trasformata, viene utilizzata la funzione di compressione $h^s$ che prende in input il blocco di $n$ bit e il risultato $z_l$ prodotto dalla funzione di compressione precedente, ad eccezione del primo blocco che prende come secondo input un $IV$

Alla fine della trasformata si ottiene il valore hash per la stringa $x$

Costruzione

<aside> 💡

Sia $(Gen, h)$ una funzione hash con lunghezza fissa per input di lunghezza $2n$ e output di lunghezza $n$

Costruiamo la funzione hash $(Gen, H)$ come segue:

• $Gen$: rimane invariato
• $H$: prende in input una chiave $s$ e una stringa $x \in \{0,1\}^*$ di lunghezza $L< 2^n$ e:
  1. pone $B:=\lceil \frac{L}n \rceil$ (numero di blocchi in $x$), aggiunge degli zeri ad $x$ in modo che la sua lunghezza sia multiplo di $n$, analizza il risultato con padding come sequenza di blocchi di $n$ bit $x_1,..,x_B$, setta $x_{B+1} := L$ , dove $L$ è codificato come una stringa di $n$ bit
  2. pone $z_0 := 0^n$ ($IV$)
  3. per $i = 1,..,B+1$ computa $z_i :=h^s(z_{i-1} || x_i)$
  4. dà in output $z_{B+1}$ </aside>

Teorema

Se $(Gen, h)$ è resistente rispetto a collisioni allora anche $(Gen,H)$ lo è

Dimostrazione

Mostriamo che, per qualsiasi $s$, una collisione in $H^s$ dà una collisione in $h^s$

Siano $x$ ed $x'$ due stringhe differenti di lunghezza $L$ ed $L'$ tali che $H^s(x)=H^s(x')$ → $x= x_1..x_Bx_{B+1}$ e $x'= x'1..x'{B'}x'_{B'+1}$

Ci sono due casi da considerare: