Sicurezza
Mappa buffer overflow
Mappa cifratura asimmetrica
Mappa cifratura simmetrica
Mappa firewall
Mappa funzioni di hash e firma elettronica
Mappa IPsec
Mappa XSS, CSRF, SQLi
Funzioni di hash
Funzione di hash

Una funzione di hash trasforma un messaggio m di un certa lunghezza (variabile) in un codice di hash di dimensione fissa. Abbiamo che se è la nostra funzione di hash, .

Grazie alla funzione di hash possiamo garantire l'integrità dei dati. Anche un file, passato ad un funzione di hash, ha un suo codice di hash. Molti siti mostrano il codice di hash di un certo file, prima del download, in modo tale che, una volta che il file è disponibile sul proprio computer, è passabile alla medesima funzione di hash, che deve restituire, per dimostrare che il file non è stato compromesso durante la fase di download, lo stesso codice di partenza (in questo caso quello indica sulla pagina di chi ha reso disponibile il file). Questo è uno dei tanti usi che si può fare di questo strumento.

Può succedere che due messaggi (file, testo, ...) abbiano lo stesso codice di hash.
Questo può succedere, poiché il numero di messaggi è maggiore rispetto al numero di codici hash: quindi succede che e . I messaggi e collidono.

La collisione di diversi messaggi, nel medesimo codice hash presenta un altro problema: la falsificazione dei messaggi, infatti se due messaggi collidono, un attaccante potrebbe sostituire un messaggio originale con un altro contenente dati dannosi, ma con lo stesso valore di hash.

Cosa vogliamo da una funzione di hash?
  • Che non sia invertibile (one-way, a una via): dato , deve essere difficile trovare un input tale che . Esempio: i database, quelli sicuri, mantengono la coppia user:password nella forma user:hash(password). Il database potrebbe subire un attacco e finire nella mani di un attaccante che potrebbe voler decifrare l'hash per essere a conoscenza della password, allora effettua un attacco di forza bruta per trovare un messaggio il cui hash corrisponda con quello trovato nel database.
  • Fortemente non invertibile: dato deve essere difficile trovare in modo che . Esempio: supponiamo che un utente mantenga l'hash dei suoi file. Se un attaccante riesce a modificare i file ottenendo lo stesso hash (per uno di essi), allora l'attaccante può modificare il file, facendo credere al proprietario che i messaggi non sono stati modificati.
  • Resistente alle collisioni: deve essere difficile trovare tali che . Esempio: un attaccante sviluppa due versioni di un driver per un sistema operativo, una versione di questo è legittimo, l'altra versione contiene un malware, l'hash di entrambe le versioni collidono per una certa funzione di hash. L'attaccante chiede l'autenticazione del driver legittimo. Una volta autenticato, l'attaccante usa la firma usata per autenticare quel driver, per autenticare la versione malevola di esso. Quando un utente richiede il download di quel driver, esso risulterà autenticato e sicuro, ma in realtà non è stato modificato. (Attacco di tipo chosen message: l'attaccante sceglie quale messaggio far autenticare).

Le ultime due proprietà sembrano uguali, ma non lo sono. Nella seconda è dato un valore , quindi si tratta di trovare una specifica collisione per un dato messaggio. Nella terza proprietà ci si riferisce al fatto che si possano trovare collisioni tra elementi non fissati.

Un attaccante come potrebbe generare collisioni?

La risposta è con un attacco di forza bruta. L'attaccante studia la funzione di hash e tenta brutalmente di trovare delle collisioni.

Paradosso del compleanno
...

Gli attacchi di forza bruta possono essere facilitati molto sfruttando il paradosso del compleanno.
Il problema può essere formulato in questo modo: quante persone devono essere presenti in una stanza affinché la probabilità sia del 50% affinché almeno due persone nel gruppo siano nate lo stesso giorno?
La risposta breve è , bastano persone. Il che può sembrare all'inizio controintuitivo.
Chiamiamo la probabilità che tra le nessuno abbia il compleanno in comune, mentre chiamiamo , la probabilità che almeno una coppia abbiano il compleanno in comune:
Il ragionamento è il seguente: definiamo come la probabilità che ci sia almeno una ripetizione in un insieme di elementi, scelti tra .

Affinché la probabilità sia maggiore al 50% quanto deve essere ?
Porto l'1 del secondo membro al primo membro e faccio la differenza: . Quindi ottengo: Per grande, possiamo sostituire con ottenendo:
Se , otteniamo: .

Perché questo risultato è utile?

Immaginiamo di avere valori di hash su 128 bit. Intuitivamente, un generico attaccante se volesse generare una collisione, avrebbe bisogno di testare almeno messaggi. Invece ne bastano, per il paradosso del compleanno, solamente .

Il concetto del paradosso del compleanno può essere generalizzato come segue: se
Nel contesto della sicurezza informatica e in particolare delle comunicazioni:

  • è il numero totale di messaggi (, se un messaggio è di bit ci sono messaggi)
  • è il numero totale di valori hash di bit (valori di hash, per lo stesso ragionamento sopra)

se


Come abbiamo detto, se sono possibili le collisioni, è possibile trovare messaggi che abbiano lo stesso valore hash di altri messaggi, questo è noto come birthday attack (letteralmente attacco del compleanno). Supponiamo di avere una funzione di hash , con possibili output (valori di hash). Se è applicata a input casuali, quale deve essere il valore di affinché la probabilità di avere almeno un duplicato (ad esempio per quale input )? Utilizzando l'approssimazione ottenuta sopra abbiamo: Il problema è leggermente diverso. Il paradosso del compleanno spiega come trovare una collisione casuale in un gruppo casuale di persone, di fatti un attaccante non vuole generare semplicemente una collisione casuale, ma vuole generare una collisione specifica. Ovvero dato un messaggio l'attaccante vuole generare un messaggio arbitrario che abbia lo stesso hash di .

Intersezione tra due insiemi
...

Il problema è il seguente: dato un intero casuale, che può assumere un valore tra e con la stessa probabilità per ciascun numero, e due insiemi con elementi (), qual è la probabilità tale che i due insiemi sono disgiunti? O, in altre parole, che abbiano almeno un elemento in comune?

Diciamo che esistono due insiemi, e :
Dato il valore di , la probabilità che è , dunque la probabilità che è
Questo è vero perché abbiamo supposto che il valore di lo abbiamo già. Infatti avendo un numero compreso tra e , qual è la probabilità che tale numero sia uguale ad un altro scelto tra e (con probabilità uniforme)? Basta azzeccare un numero sugli possibili, disponibili nell'altro insieme .

Se generiamo elementi di , la probabilità che nessuno di questi sia uguale a è .
Dunque, la probabilità che ci sia almeno una corrispondenza è .

Assumiamo adesso che, tutti gli elementi di sono diversi. Se è abbastanza grande e pure, allora potrebbero esserci poche duplicazioni di valori, ma la maggior parte dei valori sarebbero distinti tra di loro. Fatte queste assunzioni possiamo fare la seguente derivazione: calcoliamo la probabilità di non trovare una corrispondenza in per , adesso calcoliamo la probabilità di non trovare nessuna corrispondenza fra i due insiemi:
da qui calcoliamo la probabilità di trovare almeno una corrispondenza tra i due insiemi:
svolgendo i calcoli: Adesso chiediamoci: quale valore di k è richiesto affinché la probabilità sopra sia superiore a ?

Un attaccante, potrebbe utilizzare una certa funzione di hash su un certo numero di elementi per generare un insieme di codici. Dopo utilizza la medesima funzione di hash su un altro numero di elementi per generare un insieme di codici. Se il numero di elementi è grande circa quanto , la probabilità che venga trovata una collisione tra i due insiemi è superiore al 50%.
Trovata la collisione, l'attaccante conosce i due messaggi che generano la collisione e può falsificare messaggi nella funzioni di hash: per esempio l'attaccante invia uno dei due messaggi (considerati legittimi), e dopo che la funzione hash è stata applicata, può sostituire il messaggio con l'altro (illegittimo) che genera la collisione.
Il birthday attack è un esempio di chosen message attack, in cui l'attaccante sceglie il messaggio da cifrare.
Diciamo che sono i messaggi legittimi per il mittente (ovvero che il mittente autenticherebbe, firmandoli). Invece sono i messaggi illegittimi per il mittente.
Un attaccante (Eva) trova un messaggio in e una variante di tali che essi collidono per una funzione di hash . Eva potrebbe indurre il mittente (Alice) a riautenticare il messaggio . Eva usa l'autenticazione di per .

Scenario

Alice è una dirigente di una grande azienda e comunica con i suoi dipendenti attraverso un sistema di messaggistica sicuro. Utilizzando un meccanismo di autenticazione basato su firme digitali, dove i messaggi legittimi sono firmati e autenticati dal mittente attraverso una funzione di hash crittografica H.

Eva, ha un'idea di quali messaggi sono considerati legittimi () e quali messaggi non lo sono (, i suoi). Trova un messaggio in e in tale che .

Eva decide di sfruttare questa collisione per indurre Alice a riautenticare il messaggio legittimo . Per farlo, Eva invia a Alice, facendo apparire che sia un messaggio legittimo che richiede un'autenticazione da parte sua.

Alice, fidandosi del sistema di autenticazione, firma digitalmente il messaggio , riautenticandolo. Tuttavia, Eva prende la firma digitale di e la applica al suo equivalente illegittimo .
Ora, Eva ha un messaggio illegittimo firmato digitalmente che sembra essere stato autenticato da Alice.

Successivamente, Eva invia il messaggio ai destinatari desiderati, che potrebbero essere altri dipendenti dell'azienda o addirittura partner commerciali. Poiché il messaggio è stato firmato digitalmente con la chiave di Alice, sembra autentico e legittimo.

L'attacco è di tipo chosen message attack perché Eva sceglie un messaggio e lo fa riautenticare ad Alice (cosa che non è detto che riesca).

I valori di hash, risultati da una funzione di hash, devono essere molto grandi, per ridurre la probabilità di riuscita di un attacco di questo tipo.

Struttura funzioni di hash
...

Schema generale
...

Pasted image 20230903103802.png
Il messaggio viene diviso in parti, ciascuna di esse costituisce uno dei due input della sotto-funzione. L'altro parametro può essere o il valore hash calcolato per il blocco precedente, oppure un valore hash iniziale, noto come vettore di inizializzazione.

è la funzione di hash, le funzioni di hash più note sono:

  • MD5
  • SHA-1

Non approfondiremo il funzionamento di questi due algoritmi, ne daremo solo un infarinatura molto generale.
Nello schema MD5/SHA-1, il messaggio viene diviso in blocchi di bit.
Nel caso in cui (spesso l'ultimo blocco del messaggio), non abbia un dimensione di bit, si effettuano delle operazioni di riempimento (padding).

Come viene effettuato il padding?

Cosa è necessario consocere:

  • dimensione del blocco
  • dimensione del messaggio
  • dimensione da riempire

Ogni byte di padding che viene aggiunto ha il valore corrispondente alla dimensione da riempire, ad esempio se il è necessario riempire byte, allora ogni byte di padding, avrà il valore . Una volta applicato il padding, il messaggio ha una lunghezza che è un multiplo intero della dimensione del blocco, il che lo rende pronto per essere elaborato dall'algoritmo in questione.

Alla fine di tutto si ottiene il digest (letteralmente riassunto), ovvero il valore hash per il messaggio che gli è stato passato in input.

Interactive Graph
Table Of Contents

Funzioni di hash

Paradosso del compleanno

Intersezione tra due insiemi

Struttura funzioni di hash

Schema generale