In un precedente articolo, abbiamo visto un algoritmo asimmetrico per lo scambio di chiavi la cui sicurezza è basata sulla difficoltà del problema del logaritmo discreto. In questo articolo vediamo un altro caso in cui la difficoltà dello stesso problema permette la costruzione di un algoritmo per l’identificazione.
In un sistema di crittografia asimmetrica, Arduino mette a disposizione pubblica una chiave pubblica che chiunque può utilizzare per crittare un messaggio; una volta ricevuto il messaggio, Arduino può poi decrittarlo con la sua chiave privata. Chiaramente perché il protocollo funzioni, deve essere difficile dedurre la chiave privata da quella pubblica: ciò è vero ad esempio per l’algoritmo RSA, e anche per l’algoritmo di Diffie-Hellman che abbiamo visto in un precedente articolo. L’algoritmo di Schnorr è molto simile a quest’ultimo caso.
Supponiamo infatti che Arduino abbia una chiave pubblica $A$ e una chiave privata $a$ nel sistema Diffie-Hellman. Ciò vuol dire che abbiamo scelto un numero primo $p$ e un generatore $g \in \Z_p$. Allora la chiave pubblica e la chiave privata (che in pratica sono semplicemente dei numeri naturali) sono legate dalla relazione $g^a = A$ in $\Z_p$, che in pratica vuol dire $g^a = A \,\,(\mathrm{mod}\,p)$.
Ora Beatrice vuole assicurarsi che Arduino abbia veramente accesso alla chiave privata $a$ e non soltanto a quella pubblica. Chiaramente ciò deve avvenire senza che Arduino debba rivelare la chiave pubblica. L’idea è che Beatrice “sfida” Arduino a rispondere ad un problema la cui risposta è conoscibile solo da chi ha accesso alla chiave privata. Un’idea di base sarebbe di cifrare un messaggio (utilizzando la chiave comune prodotta da Diffie-Hellman) e chiedere ad Arduino di decrittarlo. Tuttavia il problema in questo caso è che magari qualcuno (che sostiene essere Beatrice ma chissà) potrebbe in realtà starti chiedendo di decifrare un messaggio che ti sei scambiato con Beatrice, quindi potenzialmente compromettendo la sicurezza della chiave. Inoltre chiedendo di decifrare una serie di messaggi un attaccante potrebbe ricavare informazioni utili alla crittanalisi.
L’algoritmo di identificazione di Schnorr parte da un’idea simile, in cui Beatrice sfida Arduino, ma in maniera che nessuna informazione sulla chiave privata o quella comune è ricavata dallo scambio. L’algoritmo funziona nella maniera seguente:
- Beatrice dichiara ad Arduino la sua intenzione di voler verificare la sua conoscenza della chiave privata corrispondente alla chiave pubblica $A$.
- Arduino allora prepara una chiave privata temporanea $t$ (generata anche casualmente, diversa ad ogni iterazione dell’algoritmo) e calcola la corrispondente chiave pubblica temporanea $T = g^t \,\,(\mathrm{mod}\,p)$. Poi manda $T$ a Beatrice. Ricavare $t$ da $T$ è supposto essere un problema difficile, come abbiamo visto nel precedente articolo.
- Beatrice allora calcola una sfida $s$, cioè un numero (generato anch’esso casualmente o come preferisce Beatrice) e la manda ad Arduino.
- Arduino allora calcola la sua risposta $r = a s + t$ (il che richiede la chiave privata $a$ e la chiave temporanea $t$ che solo Arduino conosce) e lo manda a Beatrice.
- A questo punto a Beatrice basta verificare che $g^r \equiv A^s T \,\,(\mathrm{mod}\,p)$.
La verifica funziona perché infatti abbiamo
$$g^r \equiv (g^a)^s g^t \equiv A^s T \,\,(\mathrm{mod}\,p)$$
Per falsificare il protocollo, Arduino dovrebbe conoscere un numero $a$ tale che $(g^a)^s \equiv A^s \,\,(\mathrm{mod}\,p)$ per $s$ arbitrario, il che immagino sia altrettanto difficile che risolvere il problema del logaritmo discreto (ricavare $a$ da $A$).
Il protocollo inoltre non rivela nulla sulla chiave privata $a$. Poiché dimostra l’identità di Arduino senza fornire nessuna informazione ulteriore, è detto “protocollo a informazione nulla” (zero knowledge proof). Supponiamo di conoscere in anticipo la sfida $s$. Allora è banale per Arduino produrre tutti i dati che deve mandare a Beatrice senza conoscere la chiave privata $a$. In particolare, Beatrice vuole conoscere un $T$ e un $r$ tali che $g^r \equiv A^s T$. Conoscendo $s$ in anticipo, basta scegliere $r$ a caso ($g$ ed $A$ sono noti), e quindi $T$ è banalmente la soluzione dell’equazione $g^r \equiv A^s T$ modulo $p$, che esiste sempre (dato che $p$ è primo) e inoltre può essere calcolata in maniera efficiente utilizzando l’algoritmo euclideo. Ciò dimostra che le informazioni pubbliche non ci danno nessuna informazione sulla chiave privata, e che inoltre è solo l’interattività del protocollo che garantisce la sua autenticità. In particolare è importante il fatto che $T$ sia dichiarata prima di sapere $s$.
Un punto debole dell’algoritmo è il seguente. Poiché non conosciamo il numero (in linea di massima casuale) $t$, anche conoscendo $s$ ed $r = a s + t$, non abbiamo informazioni sufficienti per ricavare $a$. Tuttavia supponiamo di avere, anche per caso, utilizzato due volte la stessa chiave temporanea privata $t$. È probabile che ciò sia successo se Beatrice riceve due volte la stessa chiave temporanea pubblica $T$. Allora date due sfide diverse $s$ e $s’$, avremo $r’ = a s’ + t’$, ma poiché $t’=t$ allora
$$r’-r = a (s’-s)$$
e quindi poiché Beatrice (o qualcuno che stia ascoltando la conversazione) conosce tanto le risposte $r, r’$, quanto le sfide $s, s’$, è un semplice problema di divisione quello di ricavare $a$. Questa vulnerabilità è abbastanza grave. Può essere mitigata ad esempio utilizzando una funzione di hash per produrre $r$, in maniera che le collisioni siano improbabili.