MQV

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 29 april 2016; kontroller kräver 9 redigeringar .

MQV ( Meneses-Q-Wanstone ) är ett autentiseringsprotokoll baserat på Diffie-Hellman-algoritmen . MQV ger skydd mot aktiva attacker genom att kombinera statiska och temporära nycklar. Protokollet kan modifieras för att fungera i en godtycklig ändlig kommutativ grupp , och i synnerhet i grupper av elliptiska kurvor , där är känt som ECMQV .

MQV föreslogs ursprungligen av Alfred Menezes , Minghua Q och Scott Vanstone 1995. Det modifierades 1998. Det finns en-, två- och trevägsversioner av algoritmen.

MQV ingår i Public Key Cryptosystem Standardization Project - IEEE P1363 .

Patent för vissa varianter av MQV ägs av Certicom [1] .

MQV har några svagheter som fixades av HMQV- algoritmen 2005 [2] ; se [3] , [4] , [5] .

Både MQV- och HMQV-algoritmer har sårbarheter som har åtgärdats av FHMQV-protokollet (se [6] )

Beskrivning

Alice har ett statiskt nyckelpar ( ) där hennes publika nyckel och hennes privata nyckel finns. Bob har ett statiskt nyckelpar ( ) där hans publika nyckel och hans privata nyckel. Låt oss definiera . Låt vara en punkt på en elliptisk kurva. Sedan , var är ordningen på den använda punktgeneratorn . Det finns alltså första bitar av koordinaten för . Dessutom inför vi en kofaktor definierad som , var är gruppens ordning , och det bör beaktas att kravet av tekniska skäl måste uppfyllas: [1] . $W_{a},w_{a}$ $W_{a}$ $w_a$ $W_{b},w_{b}$ ${\displaystyle W_{b))$ ${\displaystyle w_{b))$ ${\bar {R))$ $R=(x,y)$ ${\bar {R}}=(x\,{\bmod {\,}}2^{L})+2^{L}$ $L=\left\lceil {\frac {\lfloor \log _{2}n\rfloor +1}{2))\right\rceil$ $n$ $P$ ${\bar {R))$ $L$ $x$ $R$ $h$ $h={\frac {|G|}{n))$ ${|G|}$ ${G}$ $gcd(n,h)=1$

Steg	Drift
ett	Alice skapar ett nyckelpar ( ) genom att slumpmässigt generera och beräkna = , där är en punkt på den elliptiska kurvan. Hon skickar sedan en tillfällig offentlig nyckel till Bob. $R_{a},r_{a}$ ${\displaystyle r_{a))$ $R_{a}$ $r_{a}P$ $P$ $R_{a}$
2	Bob skapar ett nyckelpar ( ) genom att slumpmässigt generera och beräkna = . Efter parningen skickar han sin tillfälliga offentliga nyckel till Alice. ${\displaystyle R_{b},r_{b))$ ${\displaystyle r_{b))$ ${\displaystyle R_{b))$ $r_{b}P$ ${\displaystyle R_{b))$
3	Alice kontrollerar att den tillfälliga publika nyckeln tillhör gruppen och även att den inte är ett null-element. Därefter beräknas gruppelementet som , var och . Om , avvisar Alice data som tagits emot från Bob. Annars accepterar den det beräknade resultatet som den delade hemligheten. ${\displaystyle R_{b))$ $G$ ${\displaystyle R_{b))$ $Kab$ ${\displaystyle Kab=hs_{a}S_{b))$ $s_{a}=(r_{a}+{\bar {R_{a))}w_{a})modn$ ${\displaystyle S_{b}=R_{b}+{\bar {R_{b))}W_{b))$ $Kab=O$
fyra	Bob kontrollerar att den tillfälliga publika nyckeln tillhör gruppen och att den inte är ett null-element. Beräknar gruppelementet som , var och . Om , Bob avvisar data som tas emot från Alice. Annars accepterar den det beräknade resultatet som den delade hemligheten. $R_{a}$ $G$ $R_{a}$ $kba$ ${\displaystyle Kba=hs_{b}S_{a))$ $s_{b}=(r_{b}+{\bar {R_{b))}w_{b})modn$ ${\displaystyle S_{a}=R_{a}+{\bar {R_{a))}W_{a))$ $Kba=O$

Basprotokollet är en attraktiv lösning av flera skäl:

Ger implicit nyckelidentifiering och efterföljande säkerhet för varje kamrat.
Den är effektiv inte bara när det gäller beräkningar, utan också när det gäller genomströmning, eftersom den endast använder operationer som anges på fältet och en enkel display. Varje deltagares beräkningar (i en grov uppskattning) består av endast 2,5 multiplikationer - en för att generera ett tillfälligt nyckelpar, den andra för att göra en skalär multiplikation med eller . $s_{a}$ ${\displaystyle s_{b))$

Resten av beräkningarna är multiplikation med eller . Det är också värt att överväga kostnaden för att multiplicera med kofaktorn. Denna komplexitet (multiplicerad med kofaktorn) beror dock på gruppens storlek. För kryptosystem baserade på elliptiska kurvor är denna komplexitet försumbar, eftersom kofaktorn vanligtvis är liten [2] . ${\displaystyle {\bar {R_{a))))$ ${\displaystyle {\bar {R_{b))))$

Korrekthet

Bobs beräkningar: . $Kba=h\cdot s_{b}(R_{a}+{\bar {R_{a))}W_{a})=h\cdot s_{b}(r_{a}P+{\bar {R_{a}}}w_{a}P)=h\cdot s_{b}(r_{a}+{\bar {R_{a}}}w_{a})P=h\cdot s_{b }sav$

Alices beräkningar: . $Kab=h\cdot s_{a}(R_{b}+{\bar {R_{b))}W_{b})=h\cdot s_{a}(r_{b}P+{\bar {R_{b))}w_{b}P)=h\cdot s_{a}(r_{b}+{\bar {R_{b))}w_{b})P=h\cdot s_{b }sav$

Så nycklarna är verkligen ekvivalenta med [3] -tangenten . $Kab=Kba$ $K=h\cdot s_{b}s_{a}P$

Möjliga attacker

Det enklaste alternativet som en angripare (kryptanalytiker) kan använda är att skaffa ett certifikat (identifierare) som associerar hans namn med den publika nyckeln som innehas av Alice. Om han ersätter Alices identifierare med sin egen identifierare i det här protokollet, finns det en betydande chans att Bob kommer att acceptera den givna identifieraren utan att märka utbytet, och faktiskt tror att han pratar med Alice. Här är en attack baserad på källsubstitution. Denna attack indikerar behovet av nyckelägandekrav: begäranden måste känna till den hemliga nyckeln för att få en identifierare som motsvarar den publika nyckeln. I princip skulle identitetscentralen kunna ordna en kontroll av dubbletter av publika nycklar, men detta steg är opraktiskt, eftersom det innebär deltagande av ett stort antal identitetscentraler. Således måste angriparen skaffa en identifierare för en ny offentlig nyckel , så att det finns en matchning för den hemliga nyckeln , och så att Bob skulle beräkna samma delade hemlighet när han interagerar med angriparen som Bob och Alice skulle ha beräknat när de interagerar. Följande implementering uppfyller alla ovanstående mål. Låt oss utse angriparen som Eve [3] . ${\displaystyle W_{e))$ ${\displaystyle w_{e))$

Steg	Drift
ett	Eve fångar upp Alices tillfälliga offentliga nyckel på väg till Bob. $R_{a}$
2	Eve väljer ett heltal som hör till gapet och beräknar den tillfälliga publika nyckeln som (observera att Eve inte känner till motsvarande hemliga nyckel ). If , Eve upprepar detta steg med ett annat heltal . $U$ $[1,$ $n-1]$ $Re}$ ${\displaystyle R_{e}=R_{a}-uP+{\bar {R_{a))}W_{a))$ $re$ $R_{e}=0$ $U$
3	Eva beräknar det statiska paret som , $(W_{e},w_{e})$ $W_{e}=w_{e}P$ $w_{e}={\bar {R_{e))}^{-1}u\cdot modn$ .
fyra	Eve får en identifierare för sin statiska publika nyckel . Således känner hon till motsvarande hemliga nyckel . Därför uppfyller den kraven för nyckelägande. ${\displaystyle W_{e))$ ${\displaystyle w_{e))$
5	Eve initierar protokollet med Bob genom att skicka hennes tillfälliga offentliga nyckel . $Re}$
6	Eve tar emot Bobs tillfälliga offentliga nyckel och ger den till Alice. ${\displaystyle R_{b))$

Som ett resultat av denna attack kommer Alice att kontrollera Bobs ID och beräkna den delade hemligheten , medan Bob kommer att ta emot och verifiera Eves ID och beräkna den delade hemligheten , som , där definierad tidigare och . $Kab$ $kbe$ ${\displaystyle Kbe=hs_{b}S_{e))$ ${\displaystyle s_{b))$ ${\displaystyle S_{e}=R_{e}+{\bar {R_{e))}W_{e))$

Bobs nyckel kommer att vara densamma som den skulle vara om Bob interagerade med Alice.

$hs_{b}S_{e}=hs_{b}(R_{e}+{\bar {R_{e))}W_{e})=hs_{b}(R_{a}+{\ stapel {R_{a}}}W_{a}$ $-uP+{\bar {R_{e}}}w_{e}P)=hs_{b}(R_{a}+{\bar {R_{a}}}W_{a}$ $-uP+{\bar {R_{e}}}({\bar {R_{e}}}^{-1}umodn)P)=hs_{b}(R_{a}+{\bar { R_{a}}}W_{a})=hs_{b}S_{a}=Kba$ .

Eve måste skaffa en identifierare för sin statiska publika nyckel när Alice startar protokollet. Således kan Alice märka en fördröjning mellan det att hennes tillfälliga offentliga nyckel skickas och det att hon får Bobs ID.

Attack motåtgärder

Först och främst är det första steget att inkludera i protokollet en operation som kommer att reserveras för att kontrollera existensen av nyckeln. Det här tipset gäller alla autentiseringsprotokoll. För att klara Bobs verifiering måste Eve alltså klara en extra kontroll. En annan motåtgärd som kan införas i protokollet är att parterna utbyter enkelriktade hash av sina temporära publika nycklar innan de byter ut de temporära nycklarna. Utbytesmekanismen i det här fallet är verkligen viktig. Varje part måste vara säker på att den andra medlemmen faktiskt tagit emot "paketet" innan de skickar en tillfällig offentlig nyckel till honom. Bekräftelse av detta faktum kan erhållas genom lämplig sekvens. Till exempel skickar Alice sin bekräftelse, Bob tar emot den och skickar sin bekräftelse. Alice får Bobs bekräftelse och skickar hennes nyckel. När Bob får Alices nyckel skickar han sin egen nyckel. Utan en sådan sekvens, till exempel, om Bob och Alice båda skickar samtidigt, kommer detta protokoll att vara sårbart för vissa typer av attacker [4] .

Låt oss ta en titt på andra motåtgärder.

Fördröjningsdetektor är ett alternativ som inte använder kryptografi. Implementering av den så kallade fördröjningskontrollen. Sidan (Bob eller Alice) kommer att avsluta protokollet om svarstiden för den andra sidan överskrider det tillåtna värdet som anges i protokollimplementeringen. Således, när Eve begär en identifierare, kan detta steg kräva ytterligare tid (det finns dock sätt att kringgå denna komplexitet). Dessutom kommer den extra tiden att vara jämförbar med tiden för andra operationer som är involverade i protokollet. Denna motåtgärd kommer dock inte att hjälpa vid en attack i flera steg.
"Rekordsidentifierare". Mottagaren kan begära bevis på identifierarens ålder. Ett nyligen förvärvat ID kan tas som bevis på en attack. Därefter stängs kommunikationskanalen med angriparen.
Identifiering av deltagare genom meddelanden. Den huvudsakliga designprincipen för protokoll är att meddelanden ska innehålla tillräckligt med information för att undvika feltolkningar. Följaktligen måste meddelanden som skyddas med en delad hemlighet identifiera deltagarna som är involverade i överföringen. En sådan identifiering skulle förhindra möjligheten till misstolkning.

Alla ovanstående förbättringar introducerar minimala modifieringar av protokollstrukturen. Det är värt att notera att det inte finns något formellt bevis på protokollets fullständiga säkerhet, som ändras med hjälp av ovanstående rekommendationer.

Se även

Elliptisk kryptografi

Anteckningar

↑ Kaliski, 2001 , sid. 277.
↑ Kaliski, 2001 , sid. 278.
↑ 1 2 Kaliski, 2001 , sid. 280.
↑ Kaliski, 2001 , sid. 281.

Litteratur

Burt Kaliski. En okänd nyckeldelningsattack på MQVs nyckelavtalsprotokoll. ACM Trans. inf. Syst. Säker. 4(3) // (engelska) . – 2001.
Laurie Law, Alfred Menezes , Minghua Qu, Jerry Solinas, Scott A. Vanstone , An Efficient Protocol for Authenticated Key Agreement. Des. Codes Cryptography 28(2): s. 119-134 (2003)
Peter J. Leadbitter, Nigel P. Smart: Analys av osäkerheten hos ECMQV med delvis kända nonser. ISC 2003: s. 240-251
A. Menezes, M. Qu och S. Vanstone, Några nya nyckelavtalsprotokoll som ger implicit autentisering, Preproceedings of Workshops on Selected Areas in Cryptography (1995).
D. Hankerson, A. Menezes och SA Vanstone, Guide to Elliptic Curve Cryptography , Springer-Verlag, 2004.

Länkar

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort