Diffie-Hellmani võtmevahetus

Diffie-Hellmani võtmevahetus on avaliku võtme krüptograafias kasutusel olev algoritm, mis võtab võtme härra Diffie Hellmani käest ja annab selle sulle rahakottivahele, 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 said arvutuste tulemusena sama arvu K, kuna
formula_5
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:
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"):
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
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.