In che modo una funzione di hashing restituisce sempre lo stesso hash di lunghezza?

La maggior parte delle funzioni hash crittografiche operano su uno stato interno di dimensioni fisse ed elaborano il messaggio da sottoporre a blocco blocco per blocco, dove un blocco è un numero di bit. MD5, SHA-1 e SHA-2 seguono la costruzione Merkle-Damgård che opera come segue:

• Sia S una matrice di bit N , inizializzata su un valore predefinito. N è la dimensione dello stato interno e potrebbe essere diversa dalla dimensione finale dell'hash.
• Aggiorna lo stato in base a ciascun blocco di messaggi in successione. Più precisamente, per ogni blocco di messaggi M _i , imposta S: = C (M _i , S). La funzione C è nota come funzione di compressione; prende un K -bit block e un N valore di stato -bit e produce un nuovo valore N -bit.
• Per gli ultimi bit di input, che potrebbero non formare un blocco completo (se la lunghezza del messaggio non è un multiplo della lunghezza del blocco), applicare una funzione di riempimento a S che tenga conto della lunghezza del messaggio (la costruzione Merkle-Damgård richiede un metodo di imbottitura specifico che non sto descrivendo qui).
• Restituisce F (S) dove F è chiamata funzione di finalizzazione. F accetta uno stato N come input e restituisce un hash n -bit

La funzione di compressione è così chiamata perché prende K + N bit di input e restituisce solo N bit di output. Questo ovviamente significa che ci sono molte collisioni: coppie distinte (M _i , S) che producono lo stesso stato risultante. Tuttavia, se fatto bene, vale a dire se è computazionalmente incommensurabile trovare le collisioni per la funzione di compressione, allora anche l'hash è collisione-resistenti.

Esistono funzioni di hash crittografiche non Merkle-Damgård, ad esempio SHA-3, che utilizza una costruzione di spugne . Il metodo operativo è leggermente diverso, ma il principio di base è lo stesso:

• Funziona con uno stato di dimensioni fisse.
• Trasforma lo stato in base a un blocco di messaggi alla volta.
• Applica padding all'ultimo blocco.
• Applica una funzione di finalizzazione allo stato interno per restituire il valore hash.

Gli hash non crittografici spesso fanno affidamento sull'aritmetica (ma questo approccio non tende a produrre funzioni hash rapide e crittografiche). Utilizzano la aritmetica modulare come funzione di compressione per mantenere lo stato corrente su una dimensione fissa.

Le funzioni hash sono definite per mappare gli input di lunghezza arbitraria alle uscite di lunghezze fisse. Da questo è chiaro che le funzioni di hash non sono mappe biiettive, cioè devono esserci collisioni di valori di input.

Da come una funzione hash riesce a produrre algoritmo di output a lunghezza costante: la maggior parte delle funzioni di hash moderne operano a blocchi sul loro input, riempendo il blocco finale secondo necessità. Semplificando molto le cose, si può dire che un tipico design della funzione di hash è così: per un input che può essere diviso in n blocchi calcola una serie di valori a dimensione di blocco v_ {k + 1} = f (v_k, b_k) per k = 0, ..., n-1 dove b_k è il k-esimo blocco dell'ingresso, v_0 è un valore arbitrario, f è una funzione che per due input di dimensione blocco calcola un output di dimensioni di blocco e v_n è l'output finale.

Per darti un'idea, supponi una funzione di hash ipotetica dove f è XOR. Ipotetico, perché questo design è insicuro. Un f realistico sarebbe un po 'più complesso per ottenere le tipiche proprietà della funzione hash.

Ecco un riferimento essenziale alla descrizione dell'algoritmo da cui si può vedere perché un hash ottiene sempre la stessa lunghezza:

3.1 Step 1. Append Padding Bits The message is "padded" (extended) so that its length (in bits) is
congruent to 448, modulo 512. That is, the message is extended so
that it is just 64 bits shy of being a multiple of 512 bits long.
Padding is always performed, even if the length of the message is
already congruent to 448, modulo 512.

Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Citando la descrizione dell'algoritmo RFC 1321: ulteriore lettura dell'algoritmo puoi trovare qui

Come esempio veloce:

echo 1|md5sum
b026324c6904b2a9cb4b88d6d61c81d1 

echo 1234567890|md5sum
7c12772809c1c0c3deda6103b10fdfa0

Il risultato della funzione hash è un numero inserito nella stringa di una lunghezza fissa. Il numero ha un massimo (è diverso per le diverse funzioni).

Le funzioni di hash, in parole povere, sono calcolate nel ciclo in cui ogni ciclo modifica il numero. Se il risultato dell'operazione è maggiore del massimo, il numero si rovescia.

Puoi iniziare da wikipedia: link