Funzioni di hash collision free e schemi di firma digitale a chiave pubblica

Sommario

Presenteremo la costruzione di funzioni di hash. Tali funzioni sono collision free nel senso che, sotto determinate assunzioni crittografiche, è difficile per un esterno poter rilevare delle collisioni. Assunzioni sufficienti sono la difficoltà del problema della fattorizzazione, del logaritmo discreto o possibili assunzioni ancor più generali riguardo l'esistenza di insiemi di permutazioni claw free.

La capacità delle funzioni hash di migliorare la sicurezza e la velocità di uno schema di firma digitale è discussa: per esempio, potremmo combinare il sistema RSA con una funzione di hash collision free basata sul problema della fattorizzazione per ottenere uno schema più efficiente e più robusto.

Inoltre presenteremo l'effetto dovuto alla combinazione dello schema di firma di Goldwasser, Micali e Rivest con una tale funzione. Nell'implementazione basata sulla fattorizzazione dello schema che utilizza un modulo di k bit, il processo di firma può essere velocizzato di un fattore circa pari a k*O(log₂(k)), mentre il processo di verifica della firma può migliorare di un fattore O(log₂(k)).

Introduzione

Una degli argomenti più interessanti della crittografia a chiave pubblica è il concetto di firma digitale. Comunque, per molti degli schemi finora proposti non è ancora stata data una prova di robustezza, o è stato dimostrato che possono essere violati mediante attacchi sufficientemente violenti. Inoltre un'implementazione pratica degli schemi di firma è spesso resa molto difficile dalla complessità degli algoritmi necessari al sistema. Questi problemi suggeriscono l'uso di funzioni di hash, una qualche trasformazione adatta è applicata al messaggio prima i firmalo. In particolare:

Con un algoritmo di firma block oriented quando il messaggio è più lungo del blocco non è sicuro cifrare il messaggio blocco per blocco: un nemico potrebbe rimuovere dei blocchi dal messaggio cifrato o inserire dei blocchi a sua scelta in un messaggio prima che esso venga firmato. Quindi è necessaria una qualche trasformazione affinché una firma dipenda da tutte le parti del messaggio.

Se lo spazio dei messaggi ha una qualche struttura algebrica e l'algoritmo di firma rispetta una tale struttura il sistema può essere vulnerabile rispetto ad un attacco di tipo chosen message. Una funzione di hash può essere utilizzata per distruggere una tale struttura algebrica.

Normalmente l'output di una funzione di hash è molto più corto dell'input quindi se l'algoritmo di firma è più lento della funzione di hash si riscontra un notevole risparmio di tempo nell'implementazione dello schema.

La necessità di funzioni di hash è nota da molto tempo e molti tentativi sono stati fatti per realizzarle utilizzando ad esempio DES e RSA come blocchi costruttivi. Ad ogni modo per nessuna delle idee proposte è ancora stata data una dimostrazione di sicurezza e molti tentativi fatti con DES sono risultati insicuri. Altre varianti delle funzioni di hash sono state proposte, ad esempio funzioni pseudocasuali, ma per tali funzioni sorge la necessità per mittente e destinatario di condividere una chiave segreta. Sono dunque metodi adatti per meccanismi di autenticazione ma non si adattano a schemi a chiave pubblica. Si vorrebbero ottenere funzioni di hash pubbliche e facili da calcolare per tutti gli utenti.

Costruzione di funzioni di hash collision free

Invece di considerare delle singole funzioni di hash considereremo delle famiglie di funzioni, in modo da rendere possibile una trattazione teorica della complessità. Ogni membro di una tale famiglia avrà associato un parametro indicante la sua sicurezza. Da esso dipenderanno varie caratteristiche del sistema che usa una funzione di hash, come ad esempio la sicurezza globale del sistema stesso. Per ogni valore del parametro di sicurezza k, scegliamo un alfabeto finito S_k con ½S_k½ = r_{k .} Una funzione di hash con parametro di sicurezza pari a k sarà una funzione di mappatura h : M_k A_k, dove M _k è l'insieme di tutte le parole finite su  S_k , e A _k è un qualche insieme finito. Ometteremo a volte il pedice k, qualora non vi siano possibilità di confusione.

La caratteristica peculiare di una buona funzione di hash dovrebbe essere la sua inattaccabilità da parte di un nemico alla ricerca di collisioni, cioè differenti messaggi mappati sullo stesso valore. Dovrebbe dunque essere computationally infeasible. Ci sono vari medi per descrivere questa inattaccabilità, non tutti equivalenti. Diremo che un problema è computationally infeasible se la seguente proprietà è soddisfatta:

Sia una famiglia di circuiti booleani di dimensione polinomialmente limitata. Sia e_k la frazione di istanze del problema di dimensione k risolte da C_k. Allora e_k tende a zero più velocemente di qualsiasi frazione polinomiale.

In parole povere un problema è difficile da risolvere nel senso precedente se nessun circuito di dimensione polinomiale rispetto a k può risolvere una frazione rilevante di istanze del problema.

[SNIP?]

Lemma

Data una famiglia collision free, e un membro h : M A. Per ogni W M con |W| - |A| frazione "nonnegligible" di |A|, è computazionalmente impossibile dato h(w), dove wIW, trovare una qualsiasi w'IW con h(w') = h(w), per una frazione non irrilevante delle w in W.

Dimostrazione per assurdo: Scegliamo a caso w IW e calcoliamo h(w). Per ipotesi possiamo trovare rapidamente w' tale che h(w') = h(w) . Per ipotesi su |W|, la probabilità che w ¹ w' è non irrilevante, quindi questa procedura crea una collisione per h con probabilità nono irrilevante.

E' importante notare che dato che A potrebbe essere molto piccolo rispetto a W, il lemma precedente non implica che sia difficile invertire h su quasi tutti gli elementi in A : anche se l'insieme di elementi di w I W per cui è semplice invertire h su h(w) è molto piccolo se paragonato a W, le loro immagini potrebbero costituire una larga parte di A! Ne consegue che quest'ultimo tipo di proprietà one way è importante in relazione agli attacchi di tipo chosen message agli schemi di firma. Ogni funzione di hash deve quindi essere controllata in merito a questa proprietà.

Definizione

Una famiglia di permutazioni claw free è una famiglia di insiemi di permutazioni con le seguenti proprietà:

Ogni insieme S nella famiglia ha un parametro di sicurezza connesso, e esiste una funzione g: N N tale che se S ha parametro di sicurezza pari a k, allora |S|=g(k).

Tutti gli elementi di un insieme S nella famiglia hanno lo stesso dominio.

Esiste un algoritmo probabilistico polinomiale che, dato in input un parametro di sicurezza k, estrae a caso con probabilità uniforme un membro della famiglia avente parametro di sicurezza k.

Per ogni insieme S = , e ogni x IDominio(f ), è semplice calcolare f_i(x) per ogni i = 0 , , r-lma è computazionalmente impossibile creare un claw, cioè trovare x e y tali che per i ¹ j esistano f_i(x) = f_i(y).

Assumendo l'esistenza di famiglie di permutazioni claw free possiamo costruire funzioni di hash collision free. Introduciamo prima una notazione:

Sia S un alfabeto con cardinalità r e sia data una parola finita m su S. Denotiamo con [m] una codifica prefix free di m su S.La scelta di una codifica particolare non è importante per i risultati esposti in questa sede, tranne per il fatto che è possibile codificare in modo efficiente in modo che la lunghezza f di [m] sia una funzione lineare nella lunghezza di m. In binario, ad esempio, 1 potrebbe essere codificato come 11, 0 come 00 e tutte le codifiche potrebbero terminare con 01.Questo è importante perché una codifica corta renderà i meccanismi esposti più efficienti. In effetti, i risultati teorici mostrano che la codifica può essere scelta in modo tale che la lunghezza di m sia circa uguale alla lunghezza di [m]. In questo caso, comunque il processo di codifica stesso potrebbe diventare inefficiente.

Se è un insieme di permutazioni, tutte con dominio D, definiamo f_[m](I)=f_m1(f_m2(f_m(i))), dove IID, [m] = m m m_s, e le lettere in S sono denotate dai numeri 0,,r-l.

Teorema

La famiglia F costruita come segue è una famiglia collision free di funzioni di hash.

Sia P una famiglia di permutazioni claw free. Per ogni valore del parametro di sicurezza k sia S_k l'alfabeto di cardinalità r _k=g(k) dato da S_k = . Per ogni insieme S = IP e ogni I Idominio(f ), definiamo un elemento h di F con parametro di sicurezza k con h(m)=f_[m](I), per ogni mIM_k

Dimostrazione: Supponiamo per assurdo che F non sia collision free. Ciò significa che per ogni h IF possiamo trovare efficientemente m ¹ m' tale che f_[m](I)=f_[m'](I), dove [m] e [m'] hanno rispettivamente lunghezza s e s'. Dato che assumiamo che m e m' siano prodotti da un circuito di dimensione polinomiale, sia s che s' saranno al più polinomiali in k. Se m₁ ¹ m₁' abbiamo un claw per l'insieme S. Se m₁ = m₁' il fatto che le f siano iniettive implica che f_m2(f_ms(i)) = f_m2'(f_ms'(i)).Possiamo applicare ancora lo stesso ragionamento e, poiché la codifica applicata è prefix free, questo procedimento dovrà terminare con la creazione di un claw.

Se denotiamo con T il tempo necessario per valutare una delle permutazioni  usate nella costruzione è evidente che il tempo necessario per calcolare h su un messaggio di lunghezza L è O(TL).

La motivazione per lavorare con insiemi di permutazioni claw free piuttosto che con delle semplici coppie è dunque evidente: qualunque messaggio binario può essere trasmesso come una parola su un alfabeto più ampio trattando dei frammenti di s bit di esso come simboli di un alfabeto di  2^S elementi. Quindi se abbiamo insiemi claw free di 2^S elementi, il messaggio può essere "hashed" elaborando s bit anziché uno solo alla volta.

Esempi di permutazioni claw free

Vediamo innanzitutto la costruzione di una famiglia claw free di permutazioni assumendo che il problema della fattorizzazione sia sufficientemente difficile.

Scelta una qualsiasi funzione g: N N. Per ogni valore del parametro di sicurezza k poniamo la dimensione dell'insieme di permutazioni pari a g(k), per brevità r_k. Sia n=p₁p₂ . p_t , dove tutte le p sono numeri primi di k bit equivalenti a 3 nell'aritmetica modulo 4 e dove t è il più piccolo intero tale che 2^t-l ³ r_k . Chiamiamo l'insieme di tali interi H_k .Per ogni n I H_k costruiremo un insieme di permutazioni claw free con parametro di sicurezza k.

Per ogni numero a primo rispetto a n definiamo J(a)=((a/p₁),(a/p₂), . ,(a/p_t)). QR(n) sarà l'insieme di residui quadratici modulo n. Quindi QR(n)=.

L'insieme di tutte le 1 t-tuple forma un gruppo rispetto alla moltiplicazione pointwise. Denotiamo con G_t questo gruppo modulo il sottogruppo generato da (-l,-l, . ,-l). Chiaramente J induce un omomorfismo suriettivo F_n:Z^*_n G_t. Scegliamo un insieme di r_k elementi in Z^*_n , A = tali che |F_n(A)|=|A|. Questo è sicuramente possibile per come abbiamo scelto t. A è un insieme iniettivo di numeri quando soddisfa tale condizione. Possiamo adesso definire il nostro insieme di permutazioni come l'insieme di permutazioni dato da f_i⁽ⁿ⁾ (x) = (a_ix)2 mod n , per xI QR(n) e i = 0, . , r-l.

Per dimostrare che trovare dei claws è difficile quanto la fattorizzazione risulta essenziale che gli a_i (e non solo i loro quadrati) siano resi pubblici. Si potrebbe pensare che questo potrebbe essere rischioso per la fattorizzazione di n, dato che controllare se un insieme è iniettivo richiede la conoscenza dei fattori e dato che la dimensione di un insieme cresce esponenzialmente con il numero dei fattori. Per dimostrare che una tale realizzazione di un insieme iniettivo non è pericolosa ci serviremo dei seguenti lemmi, tecnici ma elementari.

Lemma

Sia G un gruppo abeliano finito di esponente 2. Sia S = G. Allora <S>, il sottogruppo generato da S, ha ordine al più 2^s e l'uguaglianza occorre esattamente quando nessun g_i può essere espresso come prodotto degli altri.

Dimostrazione: banale per il fatto che tutti gli g_i hanno ordine 1 o 2.

Lemma

Sia G un gruppo abeliano finito di esponente 2, |G| = 2^s . La probabilità che un sottoinsieme S di G, scelto casualmente, di cardinalità s generi G è ps = [SNIP]

Lemma

Si consideri una famiglia di circuiti probabilistici di dimensione polinomiale che, dati in input un intero n I H_k e un insieme iniettivo per n, fattorizzi n con probabilità p_k. Per ogni famiglia di circuiti di questo tipo e ogni e > 0 esiste un'altra famiglia di circuiti probabilistici di dimensione polinomiale che fattorizza n con probabilità q_k , tale che | p_k - q_k | < e

[SNIP dimostrazione]

Teorema

La famiglia composta da tutti gli insiemi di permutazioni costruite come in precedenza è una famiglia di permutazioni claw free, supposto che fattorizzare gli interi in sia computazionalmente impossibile.

Dimostrazione: Usando algoritmi ben noti e il teorema cinese del resto le p e le a per ogni n possono essere scelti facilmente. Inoltre ogni permutazione può essere valutata mediante due moltiplicazioni modulari. Questo è sufficiente a provare che trovare dei claws è difficile quanto fattorizzare. Supponiamo di aver trovato un claw per l'insieme . Quindi per qualche i ¹ j abbiamo f_i⁽ⁿ⁾(x) = f_j⁽ⁿ⁾(x) ovvero (a_ix - a_jy)*(a_ix + a_jy) º 0 mod n. Per la scelta delle a e le proprietà fondamentali del simbolo di Jacobi ciò significa che MCD(a_ix + a_jy, n) produrrà una fattorizzazione non banale di n. Per il lemma precedente possiamo fattorizzare efficientemente n se possiamo trovare efficientemente dei claws.

Con questa costruzione di insiemi claw free sarà spesso possibile migliorare le prestazioni delle funzioni di hash usando insiemi più ampi che semplici coppie di funzioni. Tuttavia è necessario notare che questa costruzione con insiemi più ampi richiede un maggior numero di fattori primi e quindi un modulo più lungo. Si noti che un modulo con molti fattori primi corti non sarebbe sicuro a causa di algoritmi di fattorizzazione come il metodo delle curve ellittiche di Lentra il cui tempo di esecuzione dipende essenzialmente dalla dimensione del più piccolo fattore primo.

Esiste comunque una piccola variante della costruzione precedente che non presenta questa controindicazione. Si ispira alla costruzione delle "blobs". In questo caso, sia n un modulo con esattamente due fattori primi  di k bit equivalenti a 3 mod 4. Si scelga poi un insieme A = QR(n). Si definisca un insieme di permutazioni come f_i⁽ⁿ⁾(x)=a_ix² per xIQR(n). E' dunque banale dimostrare il:

Lemma

Si supponga che un avversario possa calcolare un claw per f_i⁽ⁿ⁾ e f_j⁽ⁿ⁾ definite come sopra. Può dunque calcolare una radice quadrata di a_i*a_j^-l .

Il vantaggio pratico è che l'insieme A può essere allargato senza cambiare il modulo in modo da poter usare una quantità arbitraria di a. Asintoticamente, dato che possiamo usare un A di dimensione polinomiale, questo significa che questa variazione è più veloce rispetto alla precedente di un fattore O(log₂(k)). Tuttavia esiste una controindicazione che ha un'importanza teorica: con la costruzione precedente potevamo dimostrare che per ogni scelta di un insieme iniettivo la conoscenza di un claw implicava la conoscenza di un fattore di n. Nella nuova costruzione è ammissibile che un avversario possa conoscere qualche radice quadrata degli elementi in A solo per caso e non come conseguenza di un algoritmo per calcolare le radici quadrate di elementi casuali in QR(n). Potremmo comunque assumere che la probabilità che ciò accada sia praticamente irrilevante: se gli elementi di A sono scelti casualmente allora la probabilità che qualche circuito di dimensione polinomiale possa trovare la loro radice quadrata è irrilevante dato che le radici quadrate non possono essere calcolate in tempo polinomiale.

L'ultimo esempio è basato sulla difficoltà del problema del logaritmo discreto e mostra che non è necessario che le permutazioni claw free siano delle trapdoor. Per questo motivo ha una rilevanza teorica ma è di scarsa utilità pratica in quanto la valutazione di una permutazione richiede un'esponenziazione modulare completa. Scelti un grosso intero primo p, un generatore g di Z*_p e un insieme A = Z*_p definiamo f_i(x) = a_ig^x, per x I Z*_p e 0 £ i £ r-l.

Allo stesso modo di prima è semplice dimostrare che per trovare dei claws è necessario essere in grado di trovare il logaritmo discreto in base g dei quozienti degli elementi in A.

Combinare uno schema di firma e una funzione di hash

Useremo il seguente modello per lo schema di firma digitale

Spazio dei messaggi A

Spazio delle firme B

Algoritmo di firma D

Che per ogni messaggio aIA produce come output una firma D(S, a)IB usando la chiave segreta S.

D potrebbe essere probabilistico e il suo output potrebbe dipendere dal numero di messaggi firmati in precedenza o dal modo in cui erano stati firmati, in questo caso lo schema è chiamato non-memoryless. Dato che la mancanza di memoria non è rilevante per i risultati esposti più avanti, la dipendenza da input casuali o messaggi passati è stata omessa dalla trattazione.

Un predicato di verifica G

Che per ogni messaggio a e firma s produce come output un valore booleano G(P, a, s) usando la chiave pubblica P. G(P, a, s)=TRUE se e solo se s è una firma valida per a usando la chiave segreta corrispondente a P.

Questo schema è noto come schema originale. Un modello completo per la firma digitale dovrebbe anche includere un algoritmo per generare le coppie di chiavi (pubblica e privata), ma ciò è irrilevante in questo contesto.

Come al solito un gran numero di aspetti, come la lunghezza delle chiavi, il tempo di esecuzione di D e G, la sicurezza globale del sistema, dipendono dal valore di un parametro di sicurezza k.

Possiamo ora combinare questo schema con una funzione di hash h : M A. Un messaggio viene firmato calcolando D(S, h(m)) e la firma è controllata calcolando G(P, h(m), D(S, h(m))). Questo schema è detto schema combinato.

Combinando uno schema con una funzione di hash collision free assumiamo sempre per semplicità che lo schema e la funzione abbiano lo stesso parametro di sicurezza.

Uno schema di firma è detto existentially forgeable se, sotto un qualsiasi tipo di attacco, un nemico può ricavare la firma di almeno un messaggio (non necessariamente scelto dal nemico).

Un attacco di tipo chosen message è un attacco in cui il nemico può scegliere un messaggio da far firmare all'utente legittimo prima di provare a forzare la firma. Se egli è in grado di scegliere un messaggio ance durante il processo di forzatura allora si parla di attacco di tipo chosen message adattivo.

Ovviamente è necessario poter confrontare la sicurezza dei due tipi di schemi. Presentiamo innanzitutto il seguente

Teorema

Supponiamo che lo schema combinato sia almeno existentially forgeable sotto un attacco di tipo chosen message e che la funzione di hash usata sia collision free. Allora lo schema originale può essere existentially forged da un attacco di tipo chosen message.

Dimostrazione: Assumiamo per assurdo di avere un algoritmo F che forza almeno una firma dello schema combinato dopo aver ricevuto le firme di messaggi a sua scelta. Assumiamo anche di poter avere un attacco di tipo chosen message allo schema originale. Mentre eseguiamo F ci verranno richieste le firme per dei messaggi nel sottoinsieme N di M. Esse sono facilmente trovate calcolando l'insieme h(N) e usando l'attacco chosen message per ottenere D(S, h(N)). Con probabilità non irrilevante F produrrà in output un messaggio m Ï N e una firma valida per m. Se h(m) I h(N) abbiamo trovato una collisione per h ma, per ipotesi su h, questo può accadere soltanto con probabilità irrilevante. Possiamo dunque assumere che h(m) Ï h(N), il che significa che abbiamo creato una nuova firma nello schema originale.

Si noti che la dimostrazione è analoga nel caso l'attacco sia di tipo adattivo.

Questo risultato ha due conseguenze utili:

Se lo schema originale non è existentially forgeable allora non lo è neanche lo schema combinato.

Se lo schema combinato ha una qualche debolezza allora lo schema originale era già existentially forgeable.

L'ultima proposizione dice che l'uso delle funzioni di hash non introduce alcuna debolezza completamente nuova nello schema. Questo potrebbe semplificare l'anaisi dela sicureza dello schema ma sfortunatamente non contempla la possibilità che lo schema combinato sia più debole dello schema originale. Ne daremo un esempio in seguito.

L'ultimo risultato, comunque, mostra che almeno una larga classe di attacchi contro lo schema originale possono essere prevenuti usando un'adeguata funzione di hash:

Proposizione

Supponiamo che la funzione di hash usata sia one way nel senso che è difficile da invertire su un elemento scelto a caso di A. Si consideri un algoritmo per creare firme usato contro lo schema originale, cioè la funzione di hash usata non è parte dell'input dell'algoritmo. Un algoritmo che non soddisfi almeno una delle seguenti due proprietà potrà essere utile in un attacco allo schema combinato:

i)   L'algoritmo funziona solo durante un attacco di tipo chosen message e durante l'attacco richiede firme di messaggi distribuiti uniformemente su A.

ii)       L'algoritmo può creare firmo solo per un piccolo numero (cioè polinomiale) di messaggi non scelti e uniformemente distribuiti sullo spazio dei messaggi (dove la distribuzione è presa su tutte le scelte di messaggi da firmare dall'utente legittimo e tutte le scelte sono fatte dal nemico).

Dimostrazione

i): per la proprietà one way, anche un attacco di tipo chosen message allo schema combinato non consente un attacco di tipo chosen message allo schema originale: Dato che h non è parte dell'input dell'algoritmo di forge, qualsiasi procedura in grado di implementare un attacco di tipo chosen message allo schema originale basandosi su uno allo schema combinato sarebbe in effetti un algoritmo di inversione di h.

ii): Chiamiamo X l'insieme dei messaggi per cui l'algoritmo ha forzato la firma. Dato che X è in effetti una variabile casuale, per usare quelle firme il nemico deve avere un algoritmo che ricevendo in input un qualsiasi insieme di messaggi Y con |Y| = |X| produce in modo efficiente un elemento m I M con h(m) I Y. Ma questo gli consentirebbe di invertire h con probabilità non irrilevante su elementi scelti a caso.