Protocollo Menezes Qu Vanstone

MQV

Il protocollo di scambio chiave MQV prende il nome dai suoi ideatori (Menezes Qu Vanstone) ed è stato pubblicato nel 1998 [1]

Generazione delle chiavi

La generazione delle chiavi avviene esattamente come per l'algoritmo di ElGamal: dato un gruppo G di ordine q, un generatore g, Alice genera un numero casuale a (chiave privata) e calcola A=g^a (chiave pubblica). Analogamente Bob genera b (chiave privata) e calcola B=g^b (chiave pubblica).

Generazione del valore condiviso

Alice genera una coppia di chiavi effimere x e X=g^x, e analogamente Bob genera una coppia y e Y=g^y. Alice e Bob si scambiano le chiavi pubbliche, sia quelle personali che quelle effimere.

Sia Alice che Bob calcolano:

(1)

\begin{align} l = \frac{q}{2} \end{align}

(2)

\begin{eqnarray} d = 2^l + (g^x mod 2^l) \\ e = 2^l + (g^y mod 2^l) \end{eqnarray}

Alice calcola:

(3)

\begin{equation} S_A = (Y B^e)^{(x+da)} \end{equation}

Bob calcola:

(4)

\begin{equation} S_B = (X A^d)^{(y+eb)} \end{equation}

I valori di S_A e S_B sono uguali:

Unsupported math environment "eqnaray"

Alice e Bob calcolano il valore generato da una funzione detta KDF (Key Derivation Function) che riceve in input il valore di S_A e S_B. Tale valore costituisce la chiave condivisa. KDF può ad esempio essere implementata attraverso una funzione di hash.

(6)

\begin{equation} K = KDF(S_A) = KDF(S_B) \end{equation}

HMQV

Nel 2005, Krawczyk propose una modifica al protocollo MQV in modo da aumentarne la sicurezza [2]. Secondo Krawczyk infatti, MQV era vulnerabile a diversi attacchi e non soddisfaceva completamente i requisiti formali di Canetti-Krawczyk, richiesti per i protocolli di scambio chiave. Menezes, che ha ideato assieme a Qu e Vanstone il protocollo MQV e Krawczyk hanno criticato aspramente le rispettive proposte [2] [3].

Nel protocollo HMQV si introduce uno scambio di tipo challenge-response, dove un destinatario invia al mittente un messaggio detto challenge. Il mittente genera una sorta di firma digitale sulla base del challenge chiamata response e la invia al destinatario, il quale la verifica. Krawczyk ha proposto uno scambio challenge-response chiamato XCR (eXponential Challenge Response), e due varianti chiamate HCR (Hashed Exponential Challenge Response) DCR (Dual Exponential Challenge Response).

XCR

Sia H' una funzione di hash che genera un codice lungo l = q/2 bit. Bob è colui che genera la firma ed Alice la verifica. Alice possiede una coppia di chiavi di tipo ElGamal (a, A = g^a) e Bob una coppia (b, B = g^b). Le due parti si sono scambiate le rispettive chiavi pubbliche.

Alice genera una coppia di chiavi effimera (x, X = g^x) ed invia una challege costituita da un messaggio m e X. Bob genera una propria coppia di chiavi effimera (y, Y = g^y) e risponde con la seguente coppia di valori

(7)

\begin{align} \left(Y,\:X^{y+H'(g^y,m)b} \right) = \left( g^y,\:({g^x})^{y+H'(g^y,m)b} \right) \end{align}

in pratica, Bob calcola un codice di hash ottenuto dalla funzione di hash H' a cui viene fornito in input il valore di Y = g^y e del messaggio m. Bob, dunque, Invia la propria chiave pubblica effimera Y ad Alice, assieme al valore seguente

(8)

\begin{align} {X}^{y+H'(g^y,m)b} = g^{xy}\:g^{xH'(g^y,m)b} \end{align}

dove b è la chiave privata di Bob e y è la chiave privata effimera di Bob. Quando Alice ottiene la chiave pubblica effimera di Bob Y = g^y e il valore (8), calcola a sua volta

(9)

\begin{align} (Y\:g^{bH'(g^y,m)})^x \end{align}

si può facilmente verificare che (8) e (9) sono uguali:

(10)

\begin{align} {g^x}^{y+H'(g^y,m)b} = g^{xy}\:g^{xH'(g^y,m)b} = (g^y\:g^{bH'(g^y,m)})^x = g^{xy}\:g^{bH'(g^y,m)x} \end{align}

HCR

Lo scambio challenge-response chiamato HCR (Hashed Exponential Challenge Response) è esattamente identico a quello XCR, tranne per l'applicazione di una funzione di Hash nella risposta di Bob e nella verifica di Alice. Al posto del valore (8) viene inviato

(11)

\begin{align} HASH\left(X^{y+H'(g^y,m)b}\right) \end{align}

e, analogamente, Alice calcola il codice Hash di (9) e lo confronta con quello di Bob.

Poiché, in base alla (10), i due valori calcolati sono uguali, allora saranno uguali anche i valori di hash.

DCR

Il meccanismo di doppia firma prevede l'invio da Alice a Bob della coppia (m₁, X) e da parte di Bob ad Alice della coppia (m₂, Y).
Alice procede a calcolare

(12)

\begin{align} \left( YB^e \right)^{(x+da)} \end{align}

mentre Bob calcola

(13)

\begin{align} \left( XA^d \left)^{(y+be)} \end{align}

dove $d = H'(X, m_1)$, $e = H'(Y, m_2)$. I due valori calcolati sono uguali:

(14)

\begin{eqnarray} (YB^e)^{(x+da)} = (g^y g^{be})^{(x+da)} = g^{(y+be)(x+da)} \\ (XA^d)^{(y+be)} = (g^x g^{ad})^{(y+be)} = g^{(x+ad)(y+be)} \end{eqnarray}

Questo valore costituisce la chiave condivisa.

FHMQV

Nel 2009 Sarr, Elbaz–Vincent e Bajard hanno proposto una evoluzione del protocollo HMQV, introducendo gli scambi challenge-response chiamati FXCR (Full Exponential Challenge Response) e FDCR (Full Dual Exponential Challenge Response) [4].

Bibliography

1. L.Law, A.Menezes, M.Qu, J.Solinas, S.Vanstone, "An Efficient Protocol for Authenticated Key Agreement", 1998, University of Waterloo, Sito web: http://www.cacr.math.uwaterloo.ca/techreports/1998/corr98-05.pdf

2. H. Krawczyk, "HMQV: A High-Performance Secure Diffie-Hellman Protocol", 2005, Cryptology ePrint Archive, Report 2005/176, Sito web: http://eprint.iacr.org/2005/176

3. A.Menezes, "Another look at HMQV", 2005, University of Waterloo, Sito web: http://eprint.iacr.org/2005/205

4. A.P. Sarr, P. Elbaz–Vincent, J.–C. Bajard, "A Secure and Efficient Authenticated Diffie-Hellman Protocol", 2009, Cryptology ePrint Archive: Report 2009/408, Sito web: http://eprint.iacr.org/2009/408