Diffie-Hellmani võtmevahetus

Diffie-Hellmani võtmevahetus on avaliku võtme krüptograafias kasutusel olev algoritm, mille abil saab moodustada krüptograafilisi võtmeid ja neid mitteturvaliste arvutivõrkude kaudu jagada. See oli üks esimesi avalikustatud rakenduslikke meetodeid, mille abil avalikke võtmeid vahetada sai. Varem pidid sõnumi krüpteerimiseks ning dekrüpteerimiseks nii sõnumi saatja kui vastuvõtja omama ühte ja sama võtit. See omakorda tähendas, et saatja pidi kuidagi selle võtme vastuvõtjani toimetama, mida aga on väga keeruline turvaliselt teha. Diffie-Hellmani algoritm võimaldab kahel osapoolel, kellel pole omavahel eelnevalt mingit kokkupuudet olnud, kokku leppida ühise salajase võtme. Nad saavad kasutada suhtluseks avalikku arvutivõrku, kuna osapoolte saadetud sõnumite sisu teadmisest ei piisa, et ära arvata kokku lepitud salajast võtit. Pärast salajase võtme kokku leppimist saavad osapooled kasutada seda võtit edasise suhtluse krüpteerimiseks sümmeetrilise algoritmiga.

Whitfield Diffie ja Martin Hellman avalikustasid algoritmi 1976. aastal. 1970. aastate algul tegeles Suurbritannia signaalluureasutus samuti aktiivselt krüptograafiliste võtmete jagamise probleemiga. Nende tegevust juhtis James H. Ellis, kes mõtles välja avaliku võtmevahetuse skeemi, kuid ei suutnud leida matemaatilist funktsiooni, mis rahuldaks vajalikke nõudeid. Tema alluvuses töötasid C.C. Cocks ja M.J. Williamson, kellel oli rohkem edu matemaatiliste funktsioonide tuletamisel. Cocks mõtles 1973. aastal välja algoritmi, mis on analoogiline RSA algoritmiga. Williamson avastas 1975. aastal Diffie-Hellmani algoritmi. Kumbki neist avastustest laiemat tuntust ei saavutanud, kuna tulemused olid salastatud kuni 1999. aastani.

Diffie-Hellmani protokoll oma algsel kujul ei võimalda kasutajate autentimist (st me ei saa kindlad olla, kas teine osapool on see, kelle ta väidab end olevat). Seetõttu tuleb reaalses kasutuses alati kasutada sertifitseeritud avalikke võtmeid. Kombineerides sertifikaate ning igal sessioonil uue avaliku võtme genereerimist, on võimalik saavutada perfect forward secrecy. Sellist algoritmi varianti nimetatakse efemeerseks Diffie-Hellmani võtmevahetuseks.

Diffie-Hellmani algoritmile järgnes 1976. aastal teine populaarne avaliku võtme protokoll RSA, mis võimaldab lisaks krüpteerimisele ka turvalist allkirjastamist.

Algoritmi kirjeldus 
Diffie-Hellmani võtmevahetuse tulemusena teavad kaks osapoolt ühist salajast numbrit nii, et nende osapoolte infovahetust pealt kuulates ei ole kolmandal osapoolel võimalik seda numbrit tuvastada.

Graafiliselt võib algoritmi kirjeldada, kasutades mustrite liitmist. Eeldame, et kokku liidetud mustrist esialgsete mustrite tuvastamine on väga keeruline probleem.

Esmalt lepivad Alice (A) ja Bob (B) kokku ühises mustris. Seejärel valib kumbki endale salajase mustri, mida ainult tema teab, ning liidab selle ühisele mustrile. Saadud tulemused vahetatakse omavahel. Nüüd liidab kumbki osapool teise käest saadud mustrile enda salajase mustri. Tulemusena on mõlemal identne muster, mis ongi ühiseks saladuseks.

Matemaatiline kirjeldus 

Algoritmis kasutatakse kahte avalikku ning eelnevalt kokku lepitud muutujat p ning g, kus p on algarv ning g on tema primitiivne juur.

 Alice ja Bob lepivad kokku p ja g
 Alice valib enda salajase võtme a. Seejärel arvutab ta enda avaliku võtme ja saadab selle Bobile 
 Bob valib enda salajase võtme b. Seejärel arvutab ta enda avaliku võtme ja saadab selle Alice'ile 
 Alice arvutab 
 Bob arvutab 
 Alice ja Bob teavad ühist salajast arvu K

Alice ja Bob said arvutuste tulemusena sama arvu K, kuna

Leitud arvu K saavad Alice ja Bob kasutada võtmena edasise suhtluse krüpteerimiseks mõne sümmeetrilise algoritmi abil. Eeldusel, et algarv p on piisavalt suur (2015. aasta seisuga võib öelda, et mõistlik piir on 1024 bitti, turvaline piir 2048 bitti ), ei ole kolmandal osapoolel võimalik mõistliku aja jooksul leida arvu K, teades ainult arve p, g, A, B.
Ülesannet, kuidas leida K, kui on teada p, g, A, B, nimetatakse Diffie-Hellmani probleemiks.

Üldistus üle tsükliliste rühmade 
Diffie-Hellmani algoritmi saab laiendada üle kõikide sobivate tsükliliste rühmade, eeldusel et Diffie-Hellmani probleemi on selles rühmas raske lahendada ning rühma tehted on võimalik efektiivselt implementeerida. Algoritmi kirjeldus:
 Alice ja Bob lepivad kokku n-järku lõpliku tsüklilise rühma G ja selle moodustaja g.
 Alice valib juhusliku naturaalarvu a nii, et 1 ≤ a < n, ja saadab Bobile ga.
 Bob valib juhusliku naturaalarvu b nii, et 1 ≤ b < n, ja saadab Alice'ile gb.
 Alice arvutab ühise saladuse K = (gb)a.
 Bob arvutab ühise saladuse K = (ga)b.

Rohkem kui kaks osapoolt 
Diffie-Hellmani algoritmi on võimalik kasutada ühise salajase numbri kokku leppimiseks ka kolme või enama osapoole korral. Näiteks kolme osaleja (Alice, Bob ja Carol) korral (kõik tehted modulo p):
 Kõik osalejad lepivad kokku arvudes p ja g.
 Kõik osalejad valivad enda salajase võtme, vastavalt a, b ja c.
 Alice'ist algav jada
 Alice arvutab ga ja saadab tulemuse Bobile.
 Bob arvutab (ga)b = gab ja saadab tulemuse Carolile.
 Carol arvutab K = (gab)c = gabc, mis ongi ühiseks saladuseks.
 Bobist algav jada
 Bob arvutab gb ja saadab tulemuse Carolile.
 Carol arvutab (gb)c = gbc ja saadab tulemuse Alice'ile.
 Alice arvutab K = (gbc)a = gbca = gabc.
 Carolist algav jada
 Carol arvutab gc ja saadab tulemuse Alice'ile.
 Alice arvutab (gc)a = gca ja saadab tulemuse Bobile.
 Bob arvutab K = (gca)b = gcab = gabc.

Osalejad on jõudnud kõik ühise saladuseni K nii, et kolmandal osapoolel, kes küll teab ga, gb, gc, gab, gac, gbc, ei ole võimalik leida K = gabc.

Üldjuhul tuleb silmas pidada kahte põhimõtet
 Iga jada algab arvuga g ning peab ühekordselt läbi käima kõik osalejad, kes astendavad saadud vahetulemust oma salajase võtmega. 
 Iga jada jõuab ühise saladuseni siis, kui viimane osaleja rakendab enda salajast võtit. Oluline on, et pärast seda arvutust ei saadetaks tulemust enam edasi. Vahepealsed tulemused võivad olla kõik avalikud.

Arvutuste järjekorda optimeerides on iga osaleja teostatavate astendamiste arvu võimalik vähendada log2(N) + 1 astendamiseni.

Kasutusvaldkonnad võrguprotokollides 
Diffie-Hellmani võtmevahetust toetavad mitmed interneti protokollid. Kõige populaarsemad neist on TLS/SSL, SSH ning IPsec. Kõik protokollid kasutavad Diffie-Hellmani võtmevahetust esialgses faasis, et kokku leppida salajast võtit, mida edasipidi suhtluse krüpteerimisel kasutada.

Turvalisus 

Õigete tingimuste täitmisel on Diffie-Hellmani protokoll väga turvaline, aga kahjuks on praktilistes rakendustes esinenud mitmeid puudujääke. Need on võimaldanud mitmesuguseid rünnakuid algoritmi implementatsioonide vastu..

Vahendajarünne 

Kuna Diffie-Hellmani protokoll ei võimalda teise osapoole autentimist, siis on selle vastu võimalik kasutada vahendajarünnet (ingl man-in-the-middle-attack). Alice ja Bob soovivad omavahel kokku leppida ühist saladust, aga kolmas osapool (Mallory) sekkub nendevahelisse avalike võtmete vahetusse. Mallory loob kaks sideseanssi, ühe Alice'iga ning teise Bobiga. Alice'ile ütleb ta, et on Bob, ning Bobile, et on Alice. Kuna nii Alice kui Bob usaldavad seda informatsiooni (neil pole võimalik teist osapoolt autentida), siis lepivad mõlemad Malloryga kokku saladuse, mida kasutavad oma sõnumite krüpteerimiseks. See võimaldab Malloryl dekrüpteerida Alice'i ja Bobi sõnumeid ilma, et nood seda tuvastada suudaksid. Kui Mallory enam ei vahenda Alice'i ja Bobi sõnumeid, siis saavad nad teada, et keegi kuulas nende omavahelist sidet pealt, kuna Alice ja Bobi saladused ei kattu ning nad ei saa enam üksteise sõnumeid dekrüpteerida.

Lahendamaks vahendajaründe probleemi, tuleb teise osapoole autentimiseks kasutada mingisugust meetodit. Üheks võimaluseks on STS protokoll, mis ühendab endas Diffie-Hellmani võtmevahetuse ning osapoolte autentimise.

Logjam 
2015. aastal avaldatud uurimuses kirjeldatakse, kuidas sooritada rünnet TLS protokolli vastu, mis kasutab Diffie-Hellmani algoritmi. Rünne kasutab ära asjaolu, et Diffie-Hellmani probleemi lahendamise võib jagada kaheks eraldi osaks, millest üks sõltub ainult algarvust p ning mis on võimalik sooritada enne reaalset võtmevahetuse toimumist. See on osa, mis nõuab suurema enamuse vajalikust arvutusvõimsusest. Kui see eelnev arvutus (kasutatava p jaoks) on tehtud, siis võtmevahetuse ajal avalikest võtmetest salajaste arvutamine on suhteliselt vähest arvutusvõimsust nõudev.

Esimese osa arvutamine vajab siiski väga suurt ressurssi, 512-bitise p juures kulub suurel arvutikobaral selle arvutamiseks umbes nädal, 768-bitise juures mõnikümmend aastat ning 1024-bitise juures veel 1000 korda rohkem aega. Siiski on piisava arvutusvõimsuse korral ka tänapäeva superarvutitega võimalik see arvutus sooritada 1024-bitise p korral. Alates 2048-bitiste arvude korral pole see arvutus enam reaalne.

Olulise turvaprobleemi tekitab see, et väga paljud serverid kasutavad samu algarve kõikide seansside jaoks. Seega mõne p jaoks arvutuste sooritamine annab ligipääsu suurele osale seni turvaliseks arvatud infovahetusele. Lisaks võimendab probleemi see, et paljud serverid toetavad iganenud standardit export DHE, mis kasutab 512-bitist algarvu. Kuigi see ei ole enamasti vaikimisi pakutud standard, on pahatahtlikul ründajal tihtipeale siiski võimalik mõjutada serveri ja kasutaja vahelist kokkulepet nii, et nad hakkavad kasutama seda nõrka standardit. Kui ründaja lisaks teab algaarvu p, siis on tal juba üpris lihtne ära arvata kasutatavad salajased võtmed ning edasine suhtlus dekrüpteerida.

Viited

Välislingid 
 Public Key Cryptography: Diffie-Hellman Key Exchange Video, mis selgitab Diffie-Hellman algoritmi
 Is there any particular reason to use Diffie-Hellman over RSA for key exchange? Põhjalik Diffie-Hellmani ja RSA algoritmide võrdlus
 weakdh.org Veebileht Logjami rünnaku kohta

Krüptograafia
Algoritmid