Funzioni hash crittografiche

In questa lezione esamineremo le funzioni hash crittografiche, ampiamente utilizzate per la validazione rapida e l'autenticazione.

Al termine della lezione avremo trattato:

• Cosa sono le funzioni hash crittografiche
• Esempi di codice Python che illustrano l'uso delle funzioni hash
• Le applicazioni dell'hashing crittografico
• La sicurezza dell'hashing crittografico
• Le minacce a questi algoritmi da parte sia dei computer classici che di quelli quantistici

Introduzione all'hashing crittografico

Le funzioni hash rappresentano uno strumento prezioso in crittografia poiché consentono la validazione con riservatezza. In quanto tali, le funzioni hash costituiscono una componente importante dei meccanismi per l'autenticazione e l'integrità dei dati, come i codici di autenticazione dei messaggi basati su hash (HMAC) e le firme digitali. Questo articolo discuterà le idee fondamentali e le considerazioni di sicurezza alla base delle funzioni hash crittografiche, e delineerà le potenziali vulnerabilità derivanti dall'avvento del calcolo quantistico.

Razionale di base e progettazione delle funzioni hash

Esistono molte situazioni in cui l'autenticazione e la verifica dell'integrità devono essere eseguite in modo efficiente e senza rivelare informazioni private alla parte che esegue la validazione.

Ad esempio, quando si scarica un software da un server remoto, è necessario un meccanismo efficiente per verificare che il software scaricato non sia stato modificato da quando è stato creato dall'autore originale. Allo stesso modo, durante l'autenticazione degli utenti di applicazioni web, sarebbe auspicabile utilizzare un meccanismo che non preveda l'archiviazione fisica o la trasmissione delle password effettive, il che potrebbe compromettere la loro riservatezza.

Le funzioni hash crittografiche (CHF) soddisfano tali esigenze in modo efficiente e sicuro.

Fondamentalmente, una funzione hash crittografica prende un input (o messaggio) di lunghezza arbitraria e restituisce una stringa di n bit di dimensione fissa come output. L'output di una CHF è anche chiamato digest. Una CHF utile deve soddisfare diverse proprietà fondamentali:

1. Uniformità: I digest prodotti da una CHF devono essere distribuiti uniformemente e devono sembrare casuali. L'obiettivo è garantire che l'output non riveli alcuna informazione sull'input.
2. Determinismo: Per un dato input, una CHF deve sempre produrre lo stesso digest, ovvero deve essere deterministica.
3. Irreversibilità: Una CHF è una funzione unidirezionale nel senso che, dato un digest, dovrebbe essere computazionalmente impossibile invertire l'hashing e ottenere l'input.
4. Inettività approssimata: Sebbene le CHF siano funzioni molti-a-uno, devono sembrare funzioni uno-a-uno. Questo si ottiene combinando un'enorme dimensione dello spazio di output con l'effetto valanga, per cui piccole variazioni nell'input portano a digest molto divergenti. Questa caratteristica è nota come iniettività approssimata.

Dato ciò, è possibile validare un dato rispetto all'istanza originale confrontando il digest del dato con il digest dell'originale.

• Se i due digest corrispondono, possiamo essere ragionevolmente certi che il dato sia identico all'originale.
• Se i digest differiscono, possiamo essere certi che il dato sia stato manomesso o sia comunque non autentico.

Poiché i digest della CHF non rivelano il contenuto effettivo dei dati né dell'originale, consentono la validazione preservando la privacy.

Mathematical description

Una funzione hash $H$ può essere definita come:

$H : Σ^* \rightarrow \{0,1\}^n$

dove $Σ^*$ è l'insieme di tutte le possibili stringhe, che possiamo considerare come stringhe binarie di qualsiasi lunghezza.

Il fatto che la dimensione del dominio di input $Σ^*$ di $H$ sia illimitata, mentre quella del codominio $\{0,1\}^n$ sia limitata, significa che $H$ è necessariamente una mappatura molti-a-uno, che associa infiniti input a una qualsiasi stringa di n bit.

Le proprietà di uniformità e determinismo sono ben incapsulate nel modello dell'oracolo casuale dell'hashing crittografico.

Esempio di hashing crittografico in Python con SHA-256

Questo semplice esempio illustra l'hashing crittografico usando il popolare algoritmo SHA-256, fornito dalla libreria Python cryptography. Prima mostriamo come una piccola differenza nei testi in chiaro produca una grande differenza nei digest hash.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

I due messaggi differiscono esattamente in un carattere.

Successivamente, istanziamo oggetti hash per abilitare il processo di hashing, che prevede chiamate a due metodi: update e finalize.

Vediamo che, grazie all'effetto valanga nella CHF SHA-256, una differenza di un solo carattere nei messaggi di input produce due digest molto diversi.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Applicazioni dell'hashing crittografico

Le proprietà uniche delle CHF le rendono adatte a un'ampia gamma di applicazioni:

• Verifica dell'integrità dei dati: Le funzioni hash possono essere utilizzate per creare un checksum per un insieme di dati. Qualsiasi modifica ai dati, intenzionale o meno, produrrà un checksum diverso, avvisando i sistemi o gli utenti della variazione. Il checksum è anche tipicamente molto più compatto dei dati originali, il che rende i confronti tra checksum molto rapidi.

Figura 1. Hashing sicuro per la verifica dell'integrità dei dati

• Firme digitali: Gli hash crittografici sono essenziali per il funzionamento delle firme digitali, poiché implicano il confronto di messaggi con hash crittografico per stabilire l'autenticità e l'integrità preservando la privacy.

Figura 2. Firme digitali

• Blockchain e criptovalute: Le criptovalute come Bitcoin si affidano ampiamente alle CHF, in particolare per creare l'integrità delle transazioni e abilitare meccanismi di consenso come la proof of work.

Sicurezza dell'hashing crittografico

La sicurezza di una CHF viene tipicamente valutata in base alla resistenza a due tipi di attacchi: pre-immagine e collisione.

Resistenza alla pre-immagine

La resistenza alla pre-immagine significa che, dato un digest, dovrebbe essere computazionalmente impossibile risalire all'input.

Questa proprietà è collegata alla natura unidirezionale delle CHF.

Una buona CHF è progettata in modo tale che una parte che desideri condurre un attacco di pre-immagine non abbia altra scelta che ricorrere a un approccio di forza bruta, con complessità temporale $2^n$.

mathematical details

Data una CHF $H$ e un digest $g$, dovrebbe essere computazionalmente impossibile trovare un qualsiasi input $m$ dalla pre-immagine di $g$ tale che $H(m) = g$.

Resistenza alle collisioni

La resistenza alle collisioni significa che è difficile trovare due input diversi che producano lo stesso digest.

Una collisione hash crittografica si verifica quando due input producono lo stesso digest. Sebbene le collisioni esistano inevitabilmente data la natura molti-a-uno delle CHF, una buona CHF rende tuttavia impossibile individuarne una a piacere.

La resistenza alle collisioni è fondamentale per applicazioni come le firme digitali e i certificati, dove potrebbe essere catastrofico se una parte malintenzionata fosse in grado di creare una contraffazione che produce lo stesso valore hash.

mathematical details of hash collisions

$m_1, m_2$ possono essere trovati tali che $H(m_1) = H(m_2)$.

Lunghezza dell'hash

La resistenza alle collisioni è un requisito più stringente della resistenza alla pre-immagine e richiede lunghezze di output doppie rispetto a quelle necessarie per la resistenza alla pre-immagine. Questo perché un attacco di forza bruta noto come attacco del compleanno, che può essere utilizzato per identificare le collisioni hash, ha complessità temporale $2^{n/2}$.

In assenza di debolezze crittanalitiche, la sicurezza di una funzione hash è quindi principalmente influenzata dalla sua lunghezza. Più lungo è l'hash, più è sicuro, poiché diventa più difficile condurre attacchi di forza bruta.

Funzioni hash crittografiche comunemente utilizzate

La tabella seguente elenca alcune funzioni hash crittografiche comunemente utilizzate, insieme alle loro lunghezze di output e ai principali ambiti di applicazione:

Hash Function	Output Length (bits)	Common Applications
MD5	128	File integrity checking, older systems, non-crypto uses
SHA-1	160	Legacy systems, Git for version control
SHA-256	256	Cryptocurrency (Bitcoin), digital signatures, certificates
SHA-3	Variable (up to 512)	Various cryptographic applications, successor to SHA-2
Blake2	Variable (up to 512)	Cryptography, replacing MD5/SHA-1 in some systems
Blake3	Variable (up to 256)	Cryptography, file hashing, data integrity

• MD5 e SHA-1, pur essendo ancora presenti in applicazioni meno sensibili, sono considerati obsoleti in termini di resistenza alle collisioni e non sono raccomandati per i nuovi sistemi. SHA-256, parte della famiglia SHA-2, è ampiamente utilizzato ed è attualmente sicuro per la maggior parte delle applicazioni.
• SHA-3 è uno standard più recente, selezionato dal NIST nel 2015 come vincitore della competizione NIST per le funzioni hash. È progettato per essere una sostituzione diretta di SHA-2, ma presenta anche alcune caratteristiche interne diverse ed è resistente a certi tipi di attacchi che potrebbero risultare efficaci contro SHA-2.
• Blake2 e Blake3 sono funzioni hash crittografiche più veloci di MD5, SHA-1, SHA-2 e SHA-3, ma almeno altrettanto sicure dell'ultimo standard, SHA-3. Vengono sempre più utilizzate nei nuovi sistemi, in particolare dove la velocità è importante.

Rischi quantistici per l'hashing crittografico tradizionale

La principale minaccia quantistica all'hashing crittografico è rappresentata dagli attacchi di forza bruta.

Dato un particolare digest, un attaccante proverà input casuali finché non ne trova uno che produca lo stesso digest.

Con $n$ bit nell'input, ci sono $2^n$ valori possibili. Pertanto, l'attaccante deve provare circa $2^{n-1}$ input per avere una probabilità superiore al 50% di successo.

L'algoritmo di Grover

Per un contesto di ricerca non strutturata di questo tipo, l'algoritmo di Grover può fornire un'accelerazione quadratica tramite una tecnica nota come amplificazione dell'ampiezza quantistica, riducendo la complessità temporale di un attacco di pre-immagine a $2^{n/2}$.

In termini pratici, questo significa che una CHF a 256 bit, attualmente considerata sicura contro gli attacchi di pre-immagine dai computer classici, offrirebbe lo stesso livello di sicurezza di una CHF a 128 bit di fronte a un attaccante quantistico che utilizza l'algoritmo di Grover.

L'algoritmo di Grover da solo non è noto per fornire ulteriori accelerazioni quantistiche rispetto agli attacchi di collisione oltre il limite stabilito dall'attacco del compleanno, che può essere eseguito su computer classici. Poiché l'attacco del compleanno classico richiede già che le CHF adottino lunghezze di hash doppie rispetto a quelle necessarie per la resistenza alla pre-immagine, il fatto che la ricerca di Grover dimezzi effettivamente la lunghezza dell'hash rispetto agli attacchi di pre-immagine non rappresenta una minaccia pratica.

Ad esempio, nel caso di SHA-256, eseguire dell'ordine di $2^{128}$ operazioni per condurre un attacco di pre-immagine assistito da Grover sarebbe comunque impossibile nel prevedibile futuro.

L'algoritmo BHT

Un algoritmo quantistico che combina aspetti dell'attacco del compleanno con la ricerca di Grover è stato proposto nel 1997 da Brassard, Høyer e Tapp (BHT) e offre una scalabilità teorica di $O(2^{n/3})$ per trovare collisioni hash. Tuttavia, questa scalabilità migliorata è subordinata all'esistenza della tecnologia di memoria ad accesso casuale quantistico QRAM, che attualmente non esiste.

Senza QRAM, la scalabilità realizzabile è $\tilde{O}(2^{2n/5})$ e, per le lunghezze di hash attualmente in uso, questo marginale miglioramento nella capacità di trovare collisioni rispetto all'attacco del compleanno non rappresenta una minaccia critica.

Riepilogo

Le funzioni hash crittografiche sono una componente essenziale per garantire l'integrità e la privacy dei dati nei sistemi di informazione digitale e trovano ampia applicazione in molti contesti.

I requisiti di sicurezza delle CHF sono principalmente compresi in termini di resistenza agli attacchi di pre-immagine e collisione. Per le CHF ben progettate, la lunghezza dell'hash è un buon indicatore del livello di sicurezza.

Sebbene l'avvento dei computer quantistici che eseguono gli algoritmi di Grover e BHT influenzi in teoria la resistenza alla pre-immagine e alle collisioni delle CHF tradizionali, le lunghe lunghezze di hash già in uso oggi significa che i moderni algoritmi di hashing crittografico, come SHA-3, rimarranno probabilmente sicuri, salvo la scoperta di attacchi crittanalitici ancora sconosciuti.

La rilevanza delle CHF risiede nel loro ruolo come elemento fondamentale per gli schemi crittografici resistenti ai computer quantistici, garantendo che le informazioni digitali rimangano sicure anche di fronte ai potenziali futuri progressi negli algoritmi e nelle tecnologie di calcolo quantistico.