MODELLO GENERALE DI FUNZIONI HASH ITERATE

1.5 FUNZIONI HASH ITERATE

La maggior parte delle funzioni hash sono progettate come programmi iterativi per i quali si ha che input di lunghezza arbitraria sono processati trasformandoli in blocchi successivi di dimensione fissata. Un input x di lunghezza finita ed arbitraria è diviso in blocchi di lunghezza fissata, r-bit. Questa preelaborazione tipicamente richiede di appendere dei bit extra (padding) poiché è necessario ottenere una lunghezza in bit complessiva che è un multiplo della lunghezza del blocco di r bit, e spesso include, per ragioni di sicurezza un blocco o blocco parziale indicante la lunghezza dell’input prima del padding. Ogni blocco quindi serve come input ad una funzione hash f di dimensione fissata, la funzione di compressione di h, che calcola un nuovo risultato intermedio di lunghezza n bit per qualche n fissato, come funzione del risultato intermedio di n bit e il prossimo blocco . Pertanto se è il risultato parziale dopo la fase i, il processo generale per una funzione hash iterata con input può essere modellato come segue:

serve come variabile di n bit di concatenamento tra la fase i-1 e la fase i, e è un valore pre-definito di partenza o valore di inizializzazione (IV). Una trasformazione opzionale g di output è usata in un passo finale per associare la variabile di concatenamento di n bit ad un risultato di m bit ; g è spesso la funzione di identità .

Idea della dimostrazione: Una collisione per h implica una collisione per f.

Supponiamo di aver calcolato

M M' tali che h(M)=h(M').

Dopo il padding e l'aggiunta della lunghezza si ottiene:

M X₁,X₂,……,X_n

M’ X’₁,X’₂,……,X’_m

Si possono verificare i due seguenti casi:

(n=m) Siccome deve risultare

M M' allora X₁,X₂,……,X_nX’₁,X’₂,……,X’_m

e quindi esisterà una fase i tale che

f(X_i,H_i-1)=f(X’_i,H’_i-1) ma con (X_i,H_i-1)=(X’_i,H’_i-1)

e cioè la collisione per f !!!

(nm) Siccome alla fine con la tecnica del padding si sono aggiunte le lunghezze dei due messaggi M ed M' allora segue f(X_n,H_n-1)=f(X’_m,H’_m-1) con (X_n,H_n-1)=(X’_m,H’_m-1)

e cioè la collisione per f è trovata !!!

1.5.1 DETTAGLI DI FORMATTAZIONE

Per metodi di hashing blocco-per-blocco, i bit extra sono solitamente aggiunti alla stringa di input hash prima dell’hashing, per riempirlo di un numero di bit tali da renderlo un multiplo della dimensione relativa di un blocco. Il padding dei bit non ha bisogno di essere trasmesso o memorizzato, stabilito dal mittente e dal destinatario sulla base di una convenzione.

Algoritmo di padding Metodo 1

INPUT: messaggio x; lunghezza in bit n della dimensione di un blocco di dati input per la fase di elaborazione.

OUTPUT: messaggio sottoposto a padding x’, la cui lunghezza è un multiplo di n.

1. Appendi a x alcuni bit 0 necessari per ottenere una stringa x’ la cui lunghezza in bit è multipla di n.

Algoritmo di padding Metodo 2

INPUT: messaggio x; lunghezza in bit n della dimensione di un blocco di dati input per la fase di elaborazione.

OUTPUT: messaggio sottoposto a padding x’, la cui lunghezza è un multiplo di n.

1. Appendi a x un singolo bit 1.

2. Quindi appendi alcuni bit 0 necessari per ottenere una stringa x’ la cui lunghezza è un multiplo di n.

Il padding del metodo 1 è ambiguo poiché i bit 0 aggiunti al messaggio originale non possono essere distinti da quelli aggiunti durante il padding. Tali metodi sono accettabili se la lunghezza del messaggio (prima del padding) è conosciuta dal ricevente per altri mezzi. Il padding del metodo 2 non è ambiguo poiché ogni stringa x’ che è stata sottoposta al padding corrisponde ad un’unica stringa x non ancora sottoposta al padding. Quando la lunghezza del messaggio originale x è già un multiplo di n, il metodo 2 di padding comunque prevede la creazione di un blocco extra.