MQV

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. dubna 2016; kontroly vyžadují 9 úprav .

MQV ( Meneses-Q-Wanstone ) je autentizační protokol založený na algoritmu Diffie-Hellman . MQV poskytuje ochranu proti aktivním útokům kombinací statických a dočasných klíčů. Protokol lze upravit tak, aby fungoval v libovolné konečné komutativní grupě , a zejména ve skupinách eliptických křivek , kde je znám jako ECMQV .

MQV původně navrhli Alfred Menezes , Minghua Q a Scott Vanstone v roce 1995. V roce 1998 byl upraven. Existují jedno-, dvou- a třícestné verze algoritmu.

MQV je součástí projektu standardizace kryptosystému veřejného klíče - IEEE P1363 .

Patenty na některé odrůdy MQV vlastní Certicom [ 1] .

MQV má některé slabiny, které byly opraveny algoritmem HMQV v roce 2005 [2] ; viz [3] , [4] , [5] .

Algoritmy MQV i HMQV mají zranitelnosti, které byly opraveny protokolem FHMQV (viz [6] )

Popis

Alice má statický pár klíčů ( ), kde je její veřejný klíč a soukromý klíč. Bob má statický pár klíčů ( ), kde je jeho veřejný klíč a jeho soukromý klíč. Pojďme definovat . Nechť je bod na eliptické křivce. Potom , kde je pořadí použitého generátoru bodů . Existují tedy první bity souřadnice pro . Navíc zavádíme kofaktor definovaný jako , kde je pořadí skupiny a je třeba vzít v úvahu, že z technických důvodů musí být splněn požadavek: [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$

Krok	Úkon
jeden	Alice vytvoří klíčový pár ( ) náhodným vygenerováním a výpočtem = , kde je bod na eliptické křivce. Poté pošle dočasný veřejný klíč Bobovi. $R_{a},r_{a}$ ${\displaystyle r_{a))$ $R_{a}$ $r_{a}P$ $P$ $R_{a}$
2	Bob vytvoří pár klíčů ( ) náhodným generováním a výpočtem = . Po spárování odešle svůj dočasný veřejný klíč Alici. ${\displaystyle R_{b},r_{b))$ ${\displaystyle r_{b))$ ${\displaystyle R_{b))$ $r_{b}P$ ${\displaystyle R_{b))$
3	Alice zkontroluje, že dočasný veřejný klíč patří do skupiny a také, že se nejedná o nulový prvek. Poté vypočítá prvek skupiny jako , where a . Pokud , Alice odmítne data přijatá od Boba. Jinak přijme vypočítaný výsledek jako sdílený tajný klíč. ${\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$
čtyři	Bob zkontroluje, že dočasný veřejný klíč patří do skupiny a také, že se nejedná o nulový prvek. Vypočítá prvek skupiny jako , where a . Pokud , Bob odmítne data přijatá od Alice. Jinak přijme vypočítaný výsledek jako sdílený tajný klíč. $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$

Základní protokol je atraktivním řešením z několika důvodů:

Poskytuje implicitní identifikaci klíče a následné zabezpečení pro každého peer.
Je efektivní nejen z hlediska výpočtů, ale také z hlediska propustnosti, protože využívá pouze operace specifikované na poli a jednoduché zobrazení. Výpočty každého účastníka (v hrubém odhadu) se skládají pouze z 2,5 násobení – jedno pro generování dočasného páru klíčů, druhé pro skalární násobení pomocí nebo . $s_{a}$ ${\displaystyle s_{b))$

Zbytek výpočtů je násobení nebo . Za zvážení stojí i náklady na násobení kofaktorem. Tato složitost (násobení kofaktorem) však závisí na velikosti skupiny. Pro kryptosystémy založené na eliptických křivkách je tato složitost zanedbatelná, protože kofaktor je obvykle malý [2] . ${\displaystyle {\bar {R_{a))))$ ${\displaystyle {\bar {R_{b))))$

Správnost

Bobovy výpočty: . $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 }míza$

Aliceiny výpočty: . $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 }míza$

Klávesy jsou tedy skutečně ekvivalentní klávese [3] . $Kab=Kba$ $K=h\cdot s_{b}s_{a}P$

Možné útoky

Nejjednodušší možností, kterou může útočník (kryptoanalytik) použít, je získat certifikát (identifikátor), který spojuje jeho jméno s veřejným klíčem, který má Alice. Pokud v tomto protokolu nahradí Alicin identifikátor svým vlastním, existuje značná šance, že Bob daný identifikátor přijme, aniž by si záměny všiml, ve skutečnosti si myslí, že mluví s Alicí. Zde je útok založený na substituci zdroje. Tento útok naznačuje potřebu požadavků na vlastnictví klíče: žadatel musí znát tajný klíč, aby získal identifikátor odpovídající veřejnému klíči. V zásadě by centrum identity mohlo zařídit kontrolu duplicitních veřejných klíčů, ale tento krok je nepraktický, protože zahrnuje účast velkého počtu center identit. Útočník tedy musí získat identifikátor pro nový veřejný klíč , takový, že existuje shoda pro tajný klíč , a takový, aby Bob při interakci s útočníkem vypočítal stejné sdílené tajemství, jaké by při interakci vypočítali Bob a Alice. Následující implementace splňuje všechny výše uvedené cíle. Označme útočníka jako Evu [3] . ${\displaystyle W_{e))$ $w_{e}$

Krok	Úkon
jeden	Eva zachytí dočasný veřejný klíč Alice na cestě k Bobovi. $R_{a}$
2	Eva vybere celé číslo , které patří do mezery, a vypočítá dočasný veřejný klíč jako (všimněte si, že Eva nezná odpovídající tajný klíč ). Pokud , Eva zopakuje tento krok s dalším celým číslem . $U$ $[1,$ $n-1]$ $Re}$ ${\displaystyle R_{e}=R_{a}-uP+{\bar {R_{a))}W_{a))$ $re$ $R_{e}=0$ $U$
3	Eva vypočítá statický pár jako , $(W_{e},w_{e})$ $W_{e}=w_{e}P$ $w_{e}={\bar {R_{e))}^{-1}u\cdot modn$ .
čtyři	Eva obdrží identifikátor pro svůj statický veřejný klíč . Zná tedy odpovídající tajný klíč . Splňuje tedy požadavky na vlastnictví klíče. ${\displaystyle W_{e))$ $w_{e}$
5	Eva zahájí protokol s Bobem zasláním svého dočasného veřejného klíče . $Re}$
6	Eva obdrží Bobův dočasný veřejný klíč a dá ho Alici. ${\displaystyle R_{b))$

V důsledku tohoto útoku Alice zkontroluje Bobovo ID a vypočítá sdílené tajemství , zatímco Bob obdrží a ověří Evino ID a vypočítá sdílené tajemství , jak je definováno dříve a . $Kab$ $kbe$ ${\displaystyle Kbe=hs_{b}S_{e))$ ${\displaystyle s_{b))$ ${\displaystyle S_{e}=R_{e}+{\bar {R_{e))}W_{e))$

Bobův klíč bude stejný, jako kdyby Bob interagoval s Alicí.

$hs_{b}S_{e}=hs_{b}(R_{e}+{\bar {R_{e))}W_{e})=hs_{b}(R_{a}+{\ pruh {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$ .

Eva musí získat identifikátor pro svůj statický veřejný klíč v době, kdy Alice spouští protokol. Alice si tedy může všimnout zpoždění mezi okamžikem odeslání jejího dočasného veřejného klíče a okamžikem, kdy obdrží Bobovo ID.

Protiopatření útoku

V první řadě je prvním krokem zařazení do protokolu operace, která bude vyhrazena pro kontrolu existence klíče. Tento tip platí pro všechny ověřovací protokoly. Aby tedy Eva prošla Bobovým ověřením, bude muset projít další kontrolou. Dalším protiopatřením, které lze do protokolu zavést, je, aby si strany před výměnou dočasných klíčů vyměnily jednosměrné hash svých dočasných veřejných klíčů. Mechanismus výměny je v tomto případě opravdu důležitý. Každá strana si musí být jistá, že druhý člen skutečně obdržel „balíček“, než mu pošle dočasný veřejný klíč. Potvrzení této skutečnosti lze získat příslušnou sekvencí. Například Alice pošle své potvrzení, Bob je obdrží a pošle své potvrzení. Alice obdrží Bobovo potvrzení a pošle svůj klíč. Když Bob obdrží klíč Alice, pošle svůj vlastní klíč. Bez takové sekvence, například pokud Bob a Alice posílají oba současně, bude tento protokol zranitelný vůči některým typům útoků [4] .

Pojďme se podívat na další protiopatření.

Detektor zpoždění je alternativou, která nepoužívá kryptografii. Implementace tzv. delay checkeru. Strana (Bob nebo Alice) ukončí protokol, pokud doba odezvy druhé strany překročí povolenou hodnotu uvedenou v implementaci protokolu. Když tedy Eva požaduje identifikátor, může tento krok vyžadovat další čas (existují však způsoby, jak tuto složitost obejít). Navíc bude dodatečný čas srovnatelný s časem jiných operací zahrnutých v protokolu. Toto protiopatření však nepomůže v případě vícekrokového útoku.
"Identifikátor záznamu". Příjemce si může vyžádat doklad o stáří identifikátoru. Nově získaný průkaz totožnosti může být považován za důkaz útoku. Poté bude komunikační kanál s útočníkem uzavřen.
Identifikace účastníků prostřednictvím zpráv. Hlavním principem návrhu protokolů je, že zprávy by měly nést dostatek informací, aby se zabránilo chybné interpretaci. V souladu s tím musí zprávy chráněné sdíleným tajemstvím identifikovat účastníky přenosu. Taková identifikace by zabránila možnosti nesprávné interpretace.

Všechna výše uvedená vylepšení zavádějí minimální úpravy struktury protokolu. Stojí za zmínku, že neexistuje žádný formální důkaz o úplné bezpečnosti protokolu, který je upraven pomocí výše uvedených doporučení.

Viz také

Eliptická kryptografie

Poznámky

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

Literatura

Burt Kaliski. Neznámý útok sdílením klíčů na protokol shody klíčů MQV. ACM Trans. inf. Syst. Secur. 4(3) // (anglicky) . — 2001.
Laurie Law, Alfred Menezes , Minghua Qu, Jerry Solinas, Scott A. Vanstone , Efficient Protocol for Authenticated Key Agreement. Des. Codes Cryptography 28(2): pp. 119-134 (2003)
Peter J. Leadbitter, Nigel P. Smart: Analýza nejistoty ECMQV s částečně známými nonces. ISC 2003: str. 240-251
A. Menezes, M. Qu a S. Vanstone, Některé nové protokoly klíčových dohod poskytující implicitní autentizaci, Preproceedings of Workshops on Selected Areas in Cryptography (1995).
D. Hankerson, A. Menezes a SA Vanstone, Guide to Elliptic Curve Cryptography , Springer-Verlag, 2004.

Odkazy

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta