Biztonságos kulcscsere-protokollok

Biztonságos kulcscsere-protokollok

Biztonságos kulcscsere-protokollok Összefoglalás (Victor Shoup:”On Formal Methods for Secure Key Exchange” alapján) II. rész Tóth Gergely

1

Bevezetés

A következőkben a Shoup által publikált cikk fő vonulatának (statikus és adaptív feltörés esetére vonatkozó kulcscsere-protokollok) összefoglalása olvasható. A cikkben a következő feltörési módok definíciója található: •

statikus feltörés: a támadó különböző álnevekkel is megjelenhet a rendszerben, de becsületes felhasználókat nem tud feltörni (korrumpálni);

•

adaptív feltörés: a támadó feltörhet (korrumpálhat) becsületes felhasználókat, és így hozzájuthat ezen felhasználók hosszú távú titkaihoz (long-term secret, LTS);

•

erősen adaptív feltörés: a támadó feltörhet (korrumpálhat) becsületes felhasználókat, és így azok minden belső információjához (amit azok előzőleg kifejezetten nem töröltek) hozzájuthat.

Az összefoglalóban csak a protokollok rövid ismertetése és az üzenetek specifikációja kerül bemutatásra. Az egyes protokollok biztonságának formális bizonyítása a teljes cikkben olvasható. Az specifikált protokollok csoportosítása az alábbi táblázatban látható: Fajta

Statikus Statikus Adaptív Adaptív feltörés esetére feltörés esetére feltörés esetére feltörés esetére (anonim) (anonim)

Diffie-Hellman alapú

DHKE

Titkosítás alapú

2

EKE

A-DHKE

A-EKE-1 A-EKE-2

DHKE-1 DHKE-2 DHKE-3

A-DHKE-1 A-DHKE-3

EKE-1

Statikus feltörés

Először a statikus feltörés esetére vizsgálunk meg protokollokat. Ebben az esetben a támadó a hálózati forgalomtól függetlenül tör fel (korrumpál) felhasználókat. Mivel a támadóról feltesszük, hogy tetszőlegesen befolyásolhatja a hálózatot, a továbbiakban magát a hálózatot beleolvasztjuk a támadóba, így maga a támadó kézbesíti az üzeneteket. Létezik a valós világ a korábban ismertetett módon. Ennek modellezésére definiáltuk az ideális világot. A két világ eseményeinek leírására mindkét esetben készül egy napló

Tóth Gergely, 2004. május 5.

1

Biztonságos kulcscsere-protokollok (transcript). A két naplónak megkülönböztethetetlennek kell lennie. Amennyiben ez teljesül, úgy egy az ideális világban modellezhető protokoll a valós világban biztonságos. Példa: tegyük fel, létezik egy A valós világbeli támadó, aki az egyeztetett viszonykulcsot az egyeztetés után, de még a használat előtt kideríti és beleírja a naplóba. A valós világban tehát a kulcs kitalált és a tényleges értéke tehát megegyezne, amennyiben A meg tudja törni a protokollt. Az ideális világban ez a két érték azonban csak nagyon kis valószínűséggel lenne ugyanaz. Ez azonban statisztikai tesztelésre adna lehetőséget, amivel a valós és az ideális világ naplóját meg lehetne különböztetni. Tehát vagy nincs ilyen A, vagy a kulcscsere protokoll nem biztonságos. Ismétlés: Ideális világ start session operátora: •

create: start session i, j, create: a porondmester Kij kulcsot véletlen kulcsra állítja

•

connect: start session i, j, connect i’, j’: a porondmester Kij és Ki’j’ kulcsot egyenlővé teszi

•

compromize: start session i, j, compromize, W: a porondmester Kij kulcsot a támadó által adott W kulcsra állítja.

Feltételek:

3

•

C1: create mindig lehetséges: utána Iij izolált.

•

C2: connect akkor lehetséges, ha Ii’j’ izolált és kompatibilis Iij-vel. Ezek után Ii’j’ már nem izolált.

•

C3: compromize akkor lehetséges, ha PIDij nem felhasználóhoz rendelt.

Diffie-Hellman alapú protokoll (DHKE)

Minden felhasználó kiválaszt magának egy q-ad rendű G csoportot és ennek egy g generátorát. Ezek után minden felhasználó generál magának egy nyilvános/titkos aláíró kulcspárt. A felhasználó teljes nyilvános kulcsa ezek után G, g és az aláíró nyilvános kulcs, míg a teljes titkos kulcs az aláíró titkos kulcs. sigi(msg) jelenti msg digitális aláírását, melyet az Ui felhasználó készített, míg certi az a tanúsítvány, mely Ui felhasználó nyilvános kulcsát és személyazonosságát összekapcsolja. A protokoll szerint Ui és Ui’ cserél kulcsot. G, g, q az Ui felhasználó tanúsítványában leírt csoportra vonatkozik. A protokollt Ui indítja. Hk páronként független hash-függvények családja, ahol k egy előre meghatározott hosszúságú véletlenül választott bitsorozat. Ui Ö Ui’ : gx, sigi(gx, IDi’), certi // ahol x ∈ Zq véletlenszerűen választott Ui’ Ö Ui : gy, k, sigi’(gx, gy, k, IDi), certi’ // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index A viszonykulcs ezek után Hk(gxy). Ezen felül minkét fél ellenőrzi a tanúsítványokat és digitális aláírásokat. Amennyiben ezek hibát eredményeznek, úgy nem számolják ki viszonykulcsot és visszautasítják a kapcsolatot. DDH feltételezés: nincs hatékony algoritmus DHP kiszámítására. g1, g2, u1, u2 ∈ G, DHP(g1, g2, u1, u2) 1 ha létezik x∈Zq, hogy u1=g1x és u2=g2x, máskülönben 0.

Tóth Gergely, 2004. május 5.

2

Biztonságos kulcscsere-protokollok F1 feltételezés: A (g, gx, gy, k, Hk(gxy)) és a (g, gx, gy, k, K) eloszlás megkülönböztethetetlen (K Hk(gxy) hosszú véletlen szám). T1 tétel: DHKE biztonságos kulcscsere protokoll a DDH feltételezés (F1 feltételezés) mellet, feltéve hogy az alkalmazott aláírási rendszer biztonságos. első üzenet PIDi’j’ nem megérkezett felhasználóhoz Ii’j’-höz rendelt PIDi’j’ Ui felhasználóhoz rendelt

második üzenet megérkezett Iij-hez

PIDij nem felhasználóhoz rendelt PIDij Ui’ felhasználóhoz rendelt

1. Az ideális világban compromize Ii’j’, a valós világból nyerjük a kulcsot. 1. Azt állítjuk, hogy egy egyértelmű Iij van, úgy hogy PIDij = IDi’ és Iij küldte gx-et. Ez a protokoll lefolyásából és az aláírások biztonságosságából következik. 2. Emiatt create Ii’j’ lehetséges csak és a porondmester kicseréli az aktuális viszonykulcsot egy véletlen viszonykulcsra. Bizonyítandó, hogy ez megkülönböztethetetlen. Ez következik a F1 feltételezésből, feltéve ha Iij nem volt és soha nem is kompromittálódik. Ez azonban fenn áll, hiszen PIDij = IDi’ és ilyen Iij-re nem megengedett a compromize operátor: Iij vagy soha nem jut elfogadó állapotba vagy Ii’j’-vel connect kapcsolatba lép vagy Ui’ másik példányával kerül kapcsolatba. 1. Az ideális világban compromize Iij, a kulcsot magából Iij-ből nyerjük. 1. Azt állítjuk, hogy egy egyértelmű Ii’j’ van úgy, hogy PIDi’j’ = IDi és gx, gy, k megegyeznek. Ez a protokoll lefolyásából és az aláírások biztonságosságából következik. Ebben az esetben connect Iij és Ii’j’ következik, és a porondmester Iij kulcsát Ii’j’ kulcsára állítja be (amit előzőleg szintén a porondmester generált). Ez a csere megkülönböztethetetlen.

Ezzel a szimulálhatóság bizonyított. Az életképesség és a befejeződés triviális. „

4

Titkosítás alapú protokoll (EKE)

Minden felhasználó generál magának egy aláíró és egy titkosító nyilvános/titkos kulcspárt. Hasonlóan az előzőekhez sigi(msg) Ui felhasználó msg digitális aláírása, míg Ei(msg) Ui felhasználó titkosító nyilvános kulcsával való kódolása. Ui Ö Ui’ : r, certi // r egy megfelelően hosszú véletlen bitsorozat Ui’ Ö Ui : α = Ei(K, IDi’), sigi’(α, r, IDi), certi’ // K egy véletlen bitsorozat Ezek után a viszonykulcs K. Ezen felül minkét fél ellenőrzi a tanúsítványokat és digitális aláírásokat. Továbbá Ui ellenőrzi, hogy α visszakódolása helyes formájú eredményt ad és a megfelelő személyazonosságot tartalmazza. T2 tétel: EKE biztonságos kulcscsere protokoll, feltéve hogy az alkalmazott aláírási rendszer biztonságos és a titkosítási rendszer rejtjeles szöveg módosíthatatlan biztonságos (nonmalleable). Tóth Gergely, 2004. május 5.

3

Biztonságos kulcscsere-protokollok első üzenet PIDi’j’ nem 1. Az ideális világban compromize Ii’j’, a valós világból megérkezett felhasználóhoz nyerjük a kulcsot. Ii’j’-höz rendelt 1. create Ii’j’ és a porondmester kicseréli az aktuális PIDi’j’ Ui felhasználóhoz viszonykulcsot egy véletlen viszonykulcsra. Mivel a rendelt titkosítás módosíthatatlan ez a csere megkülönböztethetetlen, feltéve (T2a), hogy a titkosított α-t soha nem kódolják vissza. Ezt a későbbiekben bizonyítjuk. második PIDij nem 1. Amennyiben α-t egy olyan Ii’j’ generálta, ahol üzenet felhasználóhoz PIDi’j’ = IDi, akkor Iij elutasít, mivel az α-ban levő IDi’ megérkezett rendelt identitás nem az, amit Iij vár (PIDij). Ezt α dekódolása Iij-hez nélkül megtehető. 2. Amennyiben nem az előbbi eset áll fenn, akkor Iij befejezi a protokollt. Ha elfogadó állapotba kerül, akkor compromize Iij, a kulcsot magából Iij-ből nyerjük. Ez persze implicit módon használja Ui dekódoló függvényét, de az előbbiekben biztosítottuk, hogy nem dekódolunk semmit, amit olyan Ii’j’ titkosított, ahol PIDi’j’ = IDi. Mivel csak itt dekódolunk bármit is ebben a játékban, a fenti kitételt (T2a) – miszerint nem dekódolunk olyan titkosított szöveget, amit create operátoros felhasználó generált – bizonyítottuk. PIDij Ui’ 1. Amennyiben az aláírás ellenőrzése sikerült, úgy α-t olyan felhasználóhoz Ii’j’ készítette, ahol PIDi’j’ = IDi és az α-ban levő identitás rendelt IDi’. Továbbá connect Iij és Ii’j’ érvényes, mivel az r érték egyértelmű (legalábbis óriási valószínűséggel). Tehát connect Iij és Ii’j’, és a porondmester Iij kulcsát Ii’j’ kulcsára állítja be (amit előzőleg szintén a porondmester generált). Ez a csere megkülönböztethetetlen. Ezzel a szimulálhatóság bizonyított. Az életképesség és a befejeződés triviális. „

5

Anonim alanyok

Anonim alany (U0) alatt olyan felhasználót értünk, akinek nincs tanúsítványa. Ennek megfelelően szinonimaként talán a „nem hitelesített” felhasználót is használhatnánk. Mivel az anonim felhasználó a támadó is lehet, a nem anonim felhasználó számára ezek a protokollok nem tudnak sokat garantálni. Azonban amennyiben felsőbb protokollban (pl. az egyeztetett kulccsal titkosított csatornán keresztül) az anonim alany azonosítja magát (pl. jelszó segítségével), úgy a kommunikáció során mindkét fél személyazonosságának hitelessége garantálható. Ebben az esetben az ideális világ szabályrendszerét módosítani kell: •

C3*: compromize akkor lehetséges, ha PIDij nem felhasználóhoz rendelt vagy PIDij=anonymous.

Tóth Gergely, 2004. május 5.

4

Biztonságos kulcscsere-protokollok 5.1 Anonim Diffie-Hellman alapú protokoll (A-DHKE) A-DHKE a DHKE protokoll módosítása anonim alanyok kezelése érdekében. U0 Ö Ui’ : gx // ahol x ∈ Zq véletlenszerűen választott Ui’ Ö U0 : gy, k, sigi’(gx, gy, k, anonymous), certi’ // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index A kulcs ezek után Hk(gxy). Természetesen az anonim alany ellenőrzi a digitális aláírásokat. 5.2 Anonim titkosítás alapú protokollok (A-EKE-1 és A-EKE-2) EKE módosítása A-EKE-1 anonim alanyok kezelése érdekében. Ui Ö U0 : r, certi // r egy megfelelően hosszú véletlen bitsorozat U0 Ö Ui : α = Ei(K, anonymous, r) // K egy véletlen bitsorozat Mint általában, a viszonykulcs K és Ui ellenőrzi, hogy a titkosított üzenetben levő értékek megfelelőek-e. Alternatívaként A-EKE-2 protokoll is használható. Legyen f egy K kulccsal indexelt véletlenfüggvény család. Ui Ö U0 : certi U0 Ö Ui : Ei(K, anonymous) // K egy véletlen bitsorozat Ui Ö U0 : r // r egy véletlen bitsorozat Az egyeztetett viszonykulcs fK(r) Mivel általában a gyakorlatban az anonim alany kezdi a kommunikációt, A-EKE-1 és A-EKE-2 implementációja esetén az anonim alany pl. egy üres üzenettel jelezheti kommunikációs szándékát.

6

Adaptív feltörés

Adaptív feltörés esetén a támadó hozzájut a felhasználó hosszú távú titkaihoz (LTS), de máshoz nem (így ideiglenes adatokhoz csak a későbbiekben ismertetett erősen adaptív feltörés esetén jut). Ezen kívül megengedjük, hogy a megbízható harmadik félnél is történjen hiba (pl. a támadó beszerezhet olyan tanúsítványt, mely őt mint egy felhasználót jelöli meg). Az elemzéseink során egy feltört felhasználó normálisan vesz továbbra is részt a protokollok lefolyásában, azaz minden üzenetet megfelelően generál és küld. Természetesen mivel a támadó megszerezte a feltört felhasználó hosszú távú titkait, az ő nevében tud más felhasználókkal kapcsolatba lépni.

Tóth Gergely, 2004. május 5.

5

Biztonságos kulcscsere-protokollok Az ideális világ szabályrendszerét módosítani kell: •

C3*: compromize akkor lehetséges, ha o PIDij nem felhasználóhoz rendelt vagy o PIDij korrumpált felhasználóhoz rendelt vagy o Ui korrumpált.

A következőkben az adaptív feltörésnek két alfaját különböztetjük meg:

7

•

általános adaptív kompromittálás: ha Ui feltört (korrumpált), akkor minden Iij példánya kompromittálható (compromize érvényes).

•

szigorú adaptív kompromittálás: csak akkor kompromittálható Iij, ha PIDij nincs hozzárendelve semelyik még nem korrumpált felhasználóhoz. Különbség: Alice a következőképpen gondolkodhat: egy biztonságosan egyeztetett viszonykulccsal titkosított csatornán érkezett üzenet vagy Bob-tól érkezett, vagy Bob korrumpált. Alice ebben biztos lehet, függetlenül attól, hogy az ő kulcsa kiderült-e, azaz függetlenül attól, hogy ő korrumpált-e.

Adaptív feltörésnek ellenálló Diffie-Hellman alapú protokollok (DHKE-1, DHKE-2 és DHKE-3)

7.1 DHKE-1 DKHE-1 a DHKE protokoll módosításával kapható és ellenáll adaptív feltörések ellen is. Alapvetően a DHKE protokoll kiegészítése egy „kulcs-visszaigazolás” üzenettel. Ui Ö Ui’ : gx, sigi(gx, IDi’), certi // ahol x ∈ Zq véletlenszerűen választott Ui’ Ö Ui : gy, k, sigi’(gx, gy, k, IDi), certi’ // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index Ui Ö Ui’ : k1 // ahol (k1, k2) = BitGen(Hk(gxy)) Az egyeztetett viszonykulcs k2. Az általános aláírás ellenőrzéseken kívül Ui’ ellenőrzi, hogy a megkapott k1 üzenet megegyezik a várt értékkel. Feltételezzük, hogy k1 egy elegendően hosszú bitsorozat. A következőkben jelölje Gi a certi-ben leírt csoportot. Hasonlóan az előzőekben ismertetett módszerhez, DHKE-1-et is lehet úgy módosítani, hogy támogasson anonim felhasználókat. Az így kapott protokoll A-DHKE-1. U0 Ö Ui : gx // ahol x ∈ Zq véletlenszerűen választott Ui Ö U0 : gy, k, sigi (gx, gy, k, anonymous), certi // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index U0 Ö Ui : k1 // ahol (k1, k2) = BitGen(Hk(gxy))

Tóth Gergely, 2004. május 5.

6

Biztonságos kulcscsere-protokollok 7.2 DHKE-2 DHKE-1 DHKE minimális módosítása volt. Most ismertetjük DHKE-2-t, ami egy másik megközelítés. Ui Ö Ui’ : gx, certi // ahol x ∈ Zq véletlenszerűen választott Ui’ Ö Ui : gy, k, sigi’(gx, gy, k, IDi), certi’ // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index Ui Ö Ui’ : sigi(gx, gy, k, IDi’) A feltételek azonosak DHKE-vel, azaz a viszonykulcs Hk(gxy). 7.3 DHKE-3 Bár DHKE-1 és DHKE-2 biztonságos általános adaptív kompromittálás esetén, érdemes megjegyezni, hogy a szigorú adaptív kompromittálás esetén nem biztonságosak. DHKE-1 esetén nincs egyszerű mód eme hiányosság kijavítására, azonban DHKE-2 könnyen módosítható úgy, hogy a szigorú szabálynak is megfeleljen. Az így létrejött protokoll DHKE-3. Ui Ö Ui’ : Gi, gx, certi // ahol x ∈ Zq véletlenszerűen választott Ui’ Ö Ui : gy, k, sigi’(Gi, gx, gy, k, IDi), certi’ // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index Ui Ö Ui’ : sigi(Gi, gx, gy, k, IDi’) Természetesen DHKE-3 is módosítható úgy, hogy támogassa az anonim felhasználókat. Az így kapott protokoll A-DHKE-3. Ui Ö U0’ : Gi, gx, certi // ahol x ∈ Zq véletlenszerűen választott U0 Ö Ui : gy, k // ahol y ∈ Zq véletlenszerűen választott és k egy véletlen hash-index Ui Ö U0 : sigi(Gi, gx, gy, k, anonymous)

8

Adaptív feltörésnek ellenálló titkosítás alapú protokoll (EKE-1)

Legvégül ismertetésre kerül az EKE-1 protokoll, ami az EKE protokoll kicsit módosított változata. A módosítás lényege, hogy nem csak hosszú-távú aszimmetrikus kulcsokat használ, hanem ideiglenes (csak egy viszony alatt élő) kulcsokat is. Minden felhasználó egyrészt generál magának egy aláíró kulcspárt, melynek nyilvános része kerül a felhasználó tanúsítványába. Ezen felül minden felhasználó rendelkezik egy kulcsgeneráló algoritmussal KeyGen(), ami egy nyilvános/titkos kulcspárt (E, D) generál. Ui Ö Ui’ : E, sigi(E, IDi’), certi // ahol (E, D) = KeyGen() Ui’ Ö Ui : α = E(K), sigi’(α, E, IDi), certi’ // K egy véletlen bitsorozat

Tóth Gergely, 2004. május 5.

7

Biztonságos kulcscsere-protokollok Az egyeztetett viszonykulcs K, amit Ui D(α) kiszámolásával kap meg. Mint mindig, mindkét fél ellenőrzi a digitális aláírásokat. Megjegyzés: EKE-vel ellentétben Ui’ nem rakja bele személyazonosságát (IDi’) a titkosított üzenetbe.

9

Összefoglaló

A biztonságos kulcscsere protokollok legelterjedtebb alkalmazási területe az ún. rejtjel protokollok (pl. SSL, TLS, SSH, WTLS) első lépése, melynek során a két kommunikáló fél megegyezik a közös titokban (master secret), amelyből aztán mindketten legenerálják a titkosítási és üzenet-hitelesítési kulcsokat. Az összefoglaló ismertetett Diffie-Hellman és titkosítás alapú protokollokat, melyek különböző feltételek (pl. statikus feltörés, anonim alanyok, adaptív feltörés) mellett biztosítják a kulcsok biztonságos (titkos és hiteles) egyeztetését.

Tóth Gergely, 2004. május 5.

8