e h(x)=h(x’)Da un’attenta analisi degli attacchi che possono essere portati alle strategie di firma digitale si possono individuare quelle proprietà che h deve soddisfare per evitare possibili contraffazioni.
Definizione 1.2.1 (Sicurezza debole) Una funzione hash h è debolmente priva di collisioni se dato un messaggio x è computazionalmente inammissibile trovare un messaggio x’ tale che
e h(x)=h(x’)
Definizione 1.2.2 (Sicurezza forte) Una funzione hash h è fortemente libera da collisioni se è computazionalmente inammissibile trovare due messaggi x ed x’ tali che
e
h(x)=h(x’)
Definizione 1.2.3 (One-way) h() è una funzione hash one way se, dato un message digest z, è computazionalmente inammissibile trovare un messaggio x tale che h(x)=z.
Si
può fornire una motivazione per ognuna delle tre proprietà delle funzioni
hash. A tal proposito si consideri uno schema di firma digitale in cui la firma è apposta al
valore hash h(x) piuttosto che al messaggio x. In tal caso h
dovrebbe essere una funzione hash con la proprietà di sicurezza debole
altrimenti, un nemico C potrebbe osservare la firma di A su h(x), e
quindi cercare un messaggio x' tale che h(x)=h(x'), e quindi
dimostrare che A ha firmato x'. Se C inoltre può scegliere il messaggio
che A deve firmare, allora C ha solamente bisogno di cercare una coppia (x,x')
che è una collisione, lavoro piuttosto arduo se la funzione hash gode della
proprietà di sicurezza forte. Meno ovvia è la richiesta della proprietà di
one-way per una funzione hash in uno schema di firma digitale a chiave pubblica;
si consideri l'RSA, dove l'utente A possiede una chiave pubblica (e,n),
allora C può scegliere un valore casuale y, calcolare
, e
dimostrare che y è una firma di A su x. Questa contraffazione
può essere sostanziale se C può cercare una preimmagine x tale che h(x)=z.
|
|
|
|
La proprietà di sicurezza forte implica la proprietà di sicurezza debole. Infatti se h è fortemente sicura allora, per definizione, è computazionalmente inammissibile trovare, tra tutte le coppie di messaggi, una che collide. A maggior ragione è computazionalmente inammissibile trovare una tale coppia con uno dei messaggi fissato. Viceversa, se h fosse fortemente sicura ma non debolmente sicura, dovrebbe essere computazionalmente possibile, dato un messaggio x, trovare un x’ per cui c’è collisione. Ma ciò significherebbe che è computazionalmente ammissibile trovare una coppia che collide contrariamente a quanto stabilito dalla proprietà di sicurezza forte.
|
|
|
La proprietà
di sicurezza forte implica la proprietà one-way per una funzione hash.
Otterremo il risultato facendo vedere che qualora h fosse fortemente sicura
allora non potrebbe non essere one-way. Un’ipotesi diversa, e cioè
l’invertibilità di h in tempo ammissibile tramite un algoritmo A porta alla
possibilità di costruire un algoritmo probabilistico di tipo Las Vegas che,
servendosi di A come oracolo, trova collisioni con alta probabilità in tempo
ammissibile, contrariamente a quanto stabilito dalla proprietà di sicurezza
forte di h. Questo risultato può essere ottenuto con un’assunzione molto
debole sulle dimensioni relative del dominio e del codominio della funzione
hash. Supponiamo che
sia la funzione hash dove X e Z sono insiemi finiti e tali che
Quest’ipotesi è ragionevole in
quanto se pensiamo ad un elemento di X come ad una stringa di bit di lunghezza
e a quello di Z come ad una stringa
di lunghezza
allora stiamo supponendo che la
lunghezza di z=h(x) sia più piccola di almeno un bit rispetto a quella di
x
(infatti
). E’ ovvio che diminuendo il numero di bit il numero di collisioni non può
che aumentare.
Teorema 1.2.1
Sia
una funzione hash, dove
e
sono finiti e
Sia A un algoritmo di inversione
per h. Allora esiste un algoritmo probabilistico di tipo Las Vegas che trova una
collisione per h con probabilità almeno
.
DIMOSTRAZIONE
Consideriamo il seguente algoritmo
1. Scegli un
a caso.
2. Calcola z=h(x).
3. Calcola x’=A(z).
4. Se
allora (x’,x) genera una collisione (successo)
altrimenti ESCI (fallimento).
L’algoritmo è di tipo Las Vegas in quanto o dà una risposta esatta o non risponde. Per calcolare la probabilità di successo dell’algoritmo nella ricerca di collisioni operiamo come segue:
definiamo una relazione di equivalenza ~ su
X
ponendo 
e denotiamo con
la classe di equivalenza dell’elemento
. Indichiamo con C l’insieme delle classi di equivalenza. Risulta che
in quanto ogni classe [x] è
costituita dall’immagine inversa di al più un elemento di Z. Sia
l’elemento scelto nel passo 1 dell’algoritmo e sia Prob(x)
la probabilità che x sia scelto. Per questo x ci sono |[x]|
possibili valori che A può
restituire come preimmagini di z ad passo 3 dell’algoritmo. Di questi solo
|[x]|-1 sono differenti da x e portano ad un successo nel passo 4. Risulta dunque che
e quindi
Pertanto la sicurezza forte implica necessariamente la proprietà di one-way.
|
|
|
|
