Nyilvános kulcsú kriptográfia

Informatikai biztonság 2002. október 15.

Nyilvános kulcsú kriptográfia – elmélete, algoritmusok, gyakorlati problémák –

Endrődi Csilla BME MIT Ph.D. hallgató, S E A R C H Laboratórium [email protected]

! Ismétlés

Előadásvázlat

! Nyilvános kulcsú kriptográfiai elméleti háttere ! Nyilvános kulcsú kriptográfiai algoritmus konstruálása ! Az algoritmusok biztonsága ! Egy rendszer biztonságossága

! Nyilvános kulcsú algoritmusok ! RSA, ECC, XTR, NTRU

! Nyilvános kulcsú rendszerek, gyakorlati problémák ! ! ! ! ! ! !

Titkosítás Digitális aláírás Autentikáció Nyilvános kulcs nyilvánossága Titkos kulcs titkossága Időkezelés problémája További érdekes problémák

! Összefoglalás

Ismétlés ! Kriptográfia

Összefoglaló Előadásomban az eredeti jo elektronikus aláírásról szóló magyate

F F

-1

szöveg elrejtése

! Kulccsal paraméterezhető függvény Szimmetrikus kulcsú: Aszimmetrikus kulcsú:



FK GK FK1 GK2

! Nyilvános kulcsú kriptográfia: K1: nyilvános kulcs K2: titkos kulcs

Speciális kapcsolat a kulcsok között: • Egymás kiegészítő párjai • Egy kulcsnak csak egy párja van • Egymásból gyakorlatilag kiszámíthatatlanok

(FK)

-1

(FK1)

= GK

-1

= GK2

Nyilvános kulcsú kriptográfia elmélete ! Nyilvános kulcsú kriptográfiai algoritmus konstruálása ! Nehéz probléma ! Egyirányú „rejtekajtós” függvény ! Az algoritmusok biztonsága ! Egy rendszer biztonságossága

Algoritmus konstruálás Hogyan lehet nyilvános kulcsú kriptográfiai algoritmust készíteni?

Algoritmus konstruálás Hogyan lehet nyilvános kulcsú kriptográfiai algoritmust készíteni? Minden nyilvános kulcsú kriptográfiai algoritmus alapja egy nehéz probléma, amely segítségével speciális, egyirányú „rejtekajtós” függvény készíthető.

Algoritmus konstruálás Hogyan lehet nyilvános kulcsú kriptográfiai algoritmust készíteni? Minden nyilvános kulcsú kriptográfiai algoritmus alapja egy nehéz probléma, amely segítségével speciális, egyirányú „rejtekajtós” függvény készíthető. ! „Nehéz probléma”:

Algoritmus konstruálás Hogyan lehet nyilvános kulcsú kriptográfiai algoritmust készíteni? Minden nyilvános kulcsú kriptográfiai algoritmus alapja egy nehéz probléma, amely segítségével speciális, egyirányú „rejtekajtós” függvény készíthető. ! „Nehéz probléma”: a megoldására létező legjobb algoritmus költsége nagy.

Fogalmak Nehéz probléma ! „Legjobb algoritmus” ! a legjobb, amit eddig találtak ! a legjobb, ami általános esetben működik ! „Költsége” ! az algoritmus lépésszáma ! az input függvényében ! nagy számoknál a szorzás nem egység költségű A költség az input függvényében: ! ! ! !

exponenciális szubexponenciális polinomiális lineáris

NP P

Az input növelésével tetszőleges nehézségűre növelhető a probléma.

Fogalmak Nehéz probléma

Nevezetes matematikai nehéz problémák: ! ! ! ! ! ! ! !

Egészek Faktorizációs Problémája (IFP) Diszkrét Logaritmus Probléma (DLP) Utazó Ügynök Probléma (Traveling Salesman Problem) Gráf Színezési Probléma (Graph Coloring Problem) Hamilton Út Probléma (Hamiltonian Path Problem) Hátizsák Probléma (Knapsack Problem) Legrövidebb Vektor Probléma (Closest Vector Problem) stb.

! „Nagy költség”: Belátható időn belül nem oldható meg. ! Változó fogalom ! Virtuális gép: MIPS (million instructiuons per second) ! Jelenleg: 1012 MIPS-year-es probléma

Fogalmak Nehéz probléma

A kriptográfiában használt problémák: ! Egész Faktorizációs Probléma (IFP) ! RSA ! Rabin rejtjelezés

! Diszkrét Logaritmus Probléma (DLP) ! ! ! !

Diffie-Hellmann kulcsegyeztető protokoll (DH, DH2) ElGamal rejtjelezés DSA XTR

! Elliptikus Görbéken Alapuló Diszkrét Logaritmus Probléma (ECDLP) ! ! ! !

ECDH ECDSA ECElGamal Menezes-Qu-Vanstone (MQV)

! Legrövidebb Vektor Problémája (CVP) ! NTRU

Fogalmak Egyirányú "rejtekajtós" függvény Minden nyilvános kulcsú kriptográfiai algoritmus alapja egy nehéz probléma, amely segítségével speciális, egyirányú „rejtekajtós” függvény készíthető. F: könnyen Összefoglaló Előadásomban az eredeti jo elektronikus aláírásról szóló magyate

F -1: nem számítható, „titok” ismeretében könnyen számítható

Nyilvános kulcs: a problémacsalád melyik példánya Mindenki ismeri Titkos kulcs: „rejtekajtó” információ Csak a kulcspár gazdája ismeri

Az algoritmusok biztonsága Mitől függ egy nyilvános kulcsú kriptográfiai algoritmus biztonságossága? ! RSA ≡ IFP nem bizonyított ! DH ≡ DLP bizonyított ! Nehéz probléma megoldása ! Általános megoldó algoritmusok ! Speciális megoldó algoritmusok

! Más módszerek ! Rendszer biztonsága ≠ algoritmus biztonsága

Nehéz probléma megoldása Egészek Faktorizációs Problémája (IFP) ! Általános célú megoldó algoritmusok ! Number Field Sieve (NFS); General Number Sieve Field (GNFS) ! Multiple Polynomial Quadratic Sieve (MPQS)

! Speciális célú megoldó algoritmusok ! ! ! !

Pollard rho algoritmus Pollard p-1 algoritmus Pollard p+1 algoritmus Elliptic Curve Method (ECM)

RSA Factoring Challange ! 1999: RSA-155 faktorizálása (512 bites modulus) NFS módszer; 7 hónap, 300 PC (jelenleg pár nap…) ! 2002. január 18.: RSA-158 faktorizálása (525 bites modulus) GNFS módszer új implementációjával (Lánczos algoritmus) 2-3 hónap, PC-k és Cray 90 supercomputer Becslések: 512 bites RSA törhető kevesebb mint 3000 EU-ból 2010-re a 768-bites RSA is törhető lesz hasonló költségen Ajánlott kulcsméret: 1024 bites modulus

Nehéz probléma megoldása Diszkrét Logaritmus Probléma (DLP) ! Általános célú megoldó algoritmusok: Ütközés-kereső módszerek ! Pollard rho algoritmus (legnagyobb megoldott probléma: 297 rendű véges test)

! Speciális célú megoldó algoritmusok: Index-kalkulus módszerek ! Két módszer, az NFS-hoz és az MPQS-hez hasonlóak (legnagyobb megoldott probléma: 2503 rendű véges test)

Ajánlott: legalább 760 bites modulus használata.

Nehéz probléma megoldása Elliptikus Görbéken Alapuló Diszkrét Logaritmus Probléma (ECDLP) !

Index-kalkulus módszerek nem működnek ECDLP-re

!

Általános algoritmusok: ! !

!

Baby-step-Gians-step Pollard rho algoritmus, Párhuzamos Pollard rho algoritmus

Speciális esetben hatékony algoritmusok: ! ! ! ! ! !

Pollard lambda algoritmus Pollard-Hellmann algoritmus Menezes-Okamoto-Vanstone algoritmus Semaev-Smart-Satoh-Araki algoritmus Galbraith-Smart algoritmus Silverman-Stapleton algoritmus

Nehéz probléma megoldása ECDLP

ECC Challange Kategóra

Probléma

Számításigény 1 gép esetén

Excercises

79-97 bit

néhány év

Level I. Challange

108-131 bit

103 - 107 év

Level II. Challange

163-358 bit

1012-1041 év

EREDMÉNYEK:

Excercises: Mindegyik megoldásra került. Level I. Challanges: Mindössze 1-et sikerült megoldani. 2000 április: 108 bites probléma 4 hónap, 9500 PC („Az 512 bites RSA 50-szerese.”) Level II. Challanges: Egyet sem sikerült megoldani.

Certicom ajánlata: 150 bites ECC használata.

Rendszerek biztonsága Rendszer biztonsága ≠ algoritmus biztonsága ! Implementációs hibák ! Programozási hibák Le nem kezelt esetek, hibás függvények stb.

! Szándékos hiba Trójai falovak stb.

! Gyenge paraméterek használata, ki nem küszöbölése pl. RSA-nál kis exponens stb.

! Helytelen alkalmazás ! Rossz konfiguráció pl. kis kulcsméret

! Koncepcionális hibák pl. RSA-nál közös exponens választás mindenkinek

! Protokollhibák pl. undue signing

Egy rendszer támadási lehetőségei ! Brute Force • Kimerítő keresés (Executing search) • A nehéz probléma megoldása ! Kriptográfia • Gyenge paraméterek pl. RSA-nál kis exponens választás

• Speciális paraméterek pl. RSA-nál közeli prímek problémája

• Speciális paraméter együttállások pl. RSA-nál közös modulus

! Kulcstér csökkentése • Ál-véletlenszám generátor megtörése • Egyéb információk felhasználása

Egy rendszer támadási lehetőségei ! Protokoll • Közbeékelődő támadó (Men-in-the-Middle Attack) • Megszemélyesítés (Impersonation) • Üzenet visszajátszás (Message-replay) ! Implementáció függő • „Side-channel attack”: Többlet információ szerzése • • • •

Időtartam mérése Áramfelvétel mérése Sugárzás mérése Hőmérséklet mérése

• „Failure analysis” • Hiba esetén hogyan reagál a rendszer pl. memory dump elemzése

• Nem várt paraméterekkel való indítás

! Humán faktor, Fizikai támadás

Nyilvános kulcsú algoritmusok ! RSA ! ECC ! XTR ! NTRU

Nyilvános kulcsú algoritmusok Nehéz problémák: ! Egészek Faktorizációs Problémája (IFP) ! Diszkrét Logaritmus Probléma (DLP) ! Elliptikus Görbén Alapuló Diszkrét Logaritmus Probléma (ECDLP) ! Legrövidebb Vektor Probléma (CVP)

Alkalmazási területek: ! Kulcsegyeztetés (Key Agreement) ! ! ! !

Rejtjelezés (Encryption) Digitális aláírás (Sign) Anonimitási protokoll (Anonimity Protocols) stb.

Nyilvános kulcsú algoritmusok DLP-n alapuló: ! Diffie-Hellmann Key Agreement (DH) ! ! ! ! ! ! ! ! !

El-Gamal Encryption Scheme Menezes-Qu-Vanstone Key Agreement Protocol (MQV) Efficient Compact Subgroup Trace Representation (XTR) Digital Signature Algorithm (DSA) BlumGoldwasser Encryption Scheme Zheng-Seberry Ecryption Scheme Ballare-Rogaway Encryption Scheme Nyberg-Rueppel Signature Scheme Schnorr Signature Scheme

IFP-n alapuló: ! RSA Encryption and Signature Scheme ! Rabin-Williams Encryption and Signature Scheme

ECDLP-n alapuló: ! ! ! ! !

Elliptic Curve Diffie-Hellmann Key Agreement (ECDH) Elliptic Curve Menezes-Qu-Vanstone Key Agreement Protocol (ECMQV) Elliptic Curve Integrated Encryption Scheme (ECIES) Elliptic Curve Digital Signature Algorithm (ECDSA) Elliptic Curve Nyberg-Rueppel Signature Scheme (ECNR)

Egyéb: ! ! ! !

LUCDIF Key Agreement Protocol LUCELG Encryption Scheme LUCRSA Encryption Scheme Merkle-Hellmann

! ! ! !

Chor-Rivest McEliece NTRUSign NTRUEncrypt

Nyilvános kulcsú algoritmusok Algoritmusok összehasonlítása: ! Milyen a „jó” algoritmus? ! Minimum követelmény: BIZTONSÁG Biztonság ~ kulcsméret (nehéz probléma támadása) ! Egyéb támadások (pl. side-channel attack): most nem foglalkozunk. ! Hatékonyság - kicsi kulcs méret - kicsi kódolt adat méret - kicsi aláírás méret - az algoritmus kódja legyen kicsi - gyors kódolás - gyors dekódolás - gyors aláírás - gyors aláírás ellenőrzés - kis számítási kapacitás

Függenek a kulcsmérettől!

Nyilvános kulcsú algoritmusok RSA algoritmus (1978) Kulcs előállítás:

! ! ! ! ! !

Nyilvános kulcs:

p, q prímek; m = p*q Φ(m) = (p-1) * (q-1) e tetszőleges: 1 ≤ e ≤ Φ(m); (e, Φ(m)) = 1 (e, m)

Titkos kulcs:

(d, m)

Kódoló függvény:

E(x) = xe mod m;

Dekódoló függvény:

D(y) = yd mod m

x < m;

IFP-n alapszik, ami egy évszázadok óta ismert probléma Mai napig nincs érdemi törés IFP = RSA nem bizonyított Egyszerű, szép matematikai háttér: moduláris aritmetika Az RSA Security szabadalma alatt állt 2000. szeptember 20-ig A világon a legelterjedtebb nyilvános kulcsú algoritmus

! Tipikus paraméterek: 512-4096-bites modulus; ajánlott: 1024 bit ! Gyorsítási lehetőség: ‘e’-nek kicsi érték választása (e = 65537 = 10001h) ! Az egy lépésben kódolható adat maximális mérete függ a modulus értékétől

Nyilvános kulcsú algoritmusok ECC algoritmus (1985-) Közös paraméterek: E(K) elliptikus görbe, B bázispont Titkos kulcs: k; véletlen egész; k < csoport rendje Nyilvános kulcs: P (= B⊗B⊗ … ⊗B = k"B) Kódoló függvény: E(M) = (Y1, Y2); Y1 = r"B; Y2 = M ⊗ r"(k"B); r véletlen egész Dekódoló függvény: D(Y1, Y2) = Y2 ⊗ (-) k" Y1 ! Viszonylag fiatal ! Bonyolult matematikai háttér: elliptikus görbe pontjain értelmezett csoportban végzett műveletek ! A törő algoritmusok lassabban működnek (mint pl. az RSA-nál) Azonos biztonsági szint eléréséhez sokkal kisebb kulcsra van szükség az ECC-nél, mint az RSA-nál. azaz az „egy bitre jutó biztonság” értéke nagyobb. Paraméterek: ! Kulcsméret: 110 - 570-bit; ajánlott: 160-bites ! Közös paraméterek: „szabvány görbék” (ANSI, Certicom) ! Gyorsítási lehetőség: A B és P-vel végzett „csoportszorzás” eredményeit előre kiszámítani és eltárolni.

Elliptikus görbék Az elliptikus görbét definiáló egyenlet általános alakja: x, y, y2 + axy + by = x3 + cx2 + dx + e

a, b, c, d, e ∈ F

Ha az F = valós számtest

y2 = x3 + ax + b

x, y, a, b ∈ R

A fenti egyenletet kielégítő (x,y) pontpárok alkotják az E(F) elliptikus görbe pontjait. Az elliptikus görbe pontjai egy alkalmasan megválasztott művelettel csoportot alkotnak. A 0 is eleme a csoportnak. A 0 a csoport neutrális eleme. A kriptográfiában a véges test feletti elliptikus görbéknek van jelentősége.


a, b, c, d, e ∈ F


y2 = x3 + ax + b

x, y, a, b ∈ R



a, b, c, d, e ∈ F


y2 = x3 + ax + b

x, y, a, b ∈ R



a, b, c, d, e ∈ F


y2 = x3 + ax + b

x, y, a, b ∈ R



a, b, c, d, e ∈ F


y2 = x3 + ax + b

x, y, a, b ∈ R



a, b, c, d, e ∈ F


y2 = x3 + ax + b

x, y, a, b ∈ R



a, b, c, d, e ∈ F


y2 = x3 + ax + b

x, y, a, b ∈ R


Elliptikus görbék Véges test feletti elliptikus görbék:

y2 + axy + by = x3 + cx2 + dx + e

x, y, a, b, c, d, e ∈ GF(q)

Ezek közül a GF(2n) illetve a GF(p) feletti elliptikus görbéknek van gyakorlati jelentőgége. Példa véges test feletti elliptikus görbére:

y2 = x3 - 2x2 (mod 5)

A modulo 5 síknak 5*5 = 25 pointja van. Az elliptikus görbének 10 pontja van: (0,0), (1,2), (1,3), (2,2), (2,3), (3,1), (3,4), (4,1), (4,4), 0

ECC és RSA összehasonlítása (1) Kulcsméretek: Kulcsméret ~ Biztonsági szint Azonos Biztonságot Nyújtó Kulcsméretek RSA (bit) 512 768 1024 2048 4096

ECC (bit) 113 136 160 282 409

(2) Algoritmus típusok: RSA: 3 releváns eset a nyilvános exponens értékétől függően: e = 3; e = 65537; e = nagy, véletlen. ECC: 3 releváns eset a használt csoport típusától függően: GF(p); GF(2n) trinomiális; GF(2n) pentanomiális (ECP, EC2NT, EC2NP) Nincs megfeleltetés, altípusaiként kezelve

az

egyes

esetek

az

algoritmusok

további

Mérések Implementáció:

Crypto++

! Nyílt forrású ! Mind az ECC, mind az RSA algoritmusait tartalmazza !1995 óta fejlesztik ! Sokan használják ! A nemzetközi szabványoknak megfelelő implementációt tartalmaz (IEEE P1363, X.509, SEC1, SEC2 stb.).

Mérési környezet:

PC: Intel Celeron 450 MHz processzor, 128 KB cache, 192 MB memory, 75 MHz memory bus speed, 75 MHz FSB OS: Windows 98 (version 4.10.1998) operációs rendszer Keretrendszer: Microsoft Visual C++ 6.0; Crypto++ version 4.1 ! A mérési eredmények text file-ban keletkeztek, Microsoft Excel-lel lettek elemezve ECC-nél kb. 4000, RSA-nál több mint 2000 teszteset.

Végrehajtási idő Közös param.

RSA

ECC

—

Bonyolult ! ajánlott paraméterek.

Kulcsgen.

! Nemdeterminisztikus K 0,054 s - 1,4 min 0,2 s - 14 min ECP, P+, 161-bit key: 0,09 s 1024-bit key: 2,8 s

K T P

Kódolás

K 0,05 s - 2,8 min 0,02 s - 6,7 s 1024-bit key, e=65537: E ECP, 163-bit key, 2048 byte data: 0,12 min 0,025 s

K T A El K T A

K 0,03 s - 1,55 min

Dekódolás

0,03 s - 4,45 s 1024-bit key: 0,13 s

Aláírás

∼ Dekódolás

K ∼ Dekódolás

∼ Kódolás

K E ∼ Kódolás

Aláírás ellenőrzés

ECP, 163-bit key, 22 byte data: 0,05 s

KT A KT A El.


RSA

ECC

—


Kulcsgen.

! Nemdeterminisztikus K 0,054 s - 1,4 min 0,2! s - 14 min ECP, P+, 161-bit key: Nemdeterminisztikus ECC 3 0,09 × s 1024-bit key: 2,8 s

K T El P

Kódolás

K 0,05 s - 2,8 min 0,02 s - 6,7 s 1024-bit key, e=65537: E ECP, 163-bit key, 2048 byte data: 0,12 min 0,025 s

K T A El K T A

K 0,03 s - 1,55 min

Dekódolás

0,03 s - 4,45 s 1024-bit key: 0,13 s

Aláírás

∼ Dekódolás

K ∼ Dekódolás

∼ Kódolás

K E ∼ Kódolás



KT A KT A El.


RSA

ECC

—


Kulcsgen.


K T El P

Kódolás

K K 0,05 s - 2,8 min RSA 0,02 s - 6,7 s E ECP, 163-bit key, 2048 byte data: 1024-bit key,‘e’-vel e=65537: E kicsi 0,12 min 0,025 s 4 - 5 ×

K T A El K T A

K 0,03 s - 1,55 min

Dekódolás

0,03 s - 4,45 s 1024-bit key: 0,13 s

Aláírás

∼ Dekódolás

K ∼ Dekódolás

∼ Kódolás

K E ∼ Kódolás



KT A KT A El.


RSA

ECC

—


Kulcsgen.


K T El P

Kódolás


K T A El K T P A

K 0,03 s - 1,55 min ECP

Dekódolás

0,03 s - 4,45 s 1024-bit key: 0,13 s

Aláírás

∼ Dekódolás

K ∼ Dekódolás

∼ Kódolás

K E ∼ Kódolás


ECP, 163-bit key, 22 byte data: előszám. táblával 0,05 s 2×

KT A KT A El.


RSA

ECC

—


Kulcsgen.


K T El P

Kódolás


K T A El K T P A

K 0,03 s - 1,55 min ECP

Dekódolás

0,03 s - 4,45 s 1024-bit key: 0,13 s

Aláírás

∼ Dekódolás

K ∼ Dekódolás

∼ Kódolás

K E ∼ Kódolás



ECP

előszám. táblával.

K KK T T A T A P KT A El.


RSA

ECC

—


Kulcsgen.


K T El P

Kódolás


K T A El K T P A

K 0,03 s - 1,55 min ECP

Dekódolás

0,03 s - 4,45 s 1024-bit key: 0,13 s

Aláírás

∼ Dekódolás

K ∼ Dekódolás


∼ Kódolás RSA

K E ∼ Kódolás

kicsi ‘e’-vel


ECP

előszám. táblával.

K KK T T A T A P KT A El.

Adat ffile-ok ile-ok mérete RSA

ECC

Közös Par. és Kulcs file

872 byte - 6870 byte K 1452 byte - 11328 byte 1024-bit key, e=65537: 1584 E 160-bit key, P-: 1890 byte byte 160-bit key, P+: 4684 byte

Kódolt Adat file

64 byte - 512 byte 1024-bit key, 22 byte: 128 byte

K 73 byte - 595 byte

! Syigorú korlát 22 byte - 470 byte 1024-bit key: 86 byte

K 3971 byte - 4045 byte

64 byte - 512 byte 1024-bit key: 128 byte


Kódoható adat file max. mérete Aláírás file

K El.

K 160-bit key, 22 byte: 83 byte A K

160-bit key: 4035 byte


K El.


ECC


K 1452 byte - 11328 byte 872 byte - 6870 byte K 1024-bit key, e=65537: RSA 3 × 1584 EE 160-bit key, P-: 1890 byte byte 160-bit key, P+: 4684 byte

Kódolt Adat file




K 3971 byte - 4045 byte




K El.

K 160-bit key, 22 byte: 83 byte A K



K El.


ECC



Kódolt Adat file




K 3971 byte - 4045 byte




K El.

K K A 160-bit key, ∼22ECC byte: 83 byte A K



K El.


ECC



Kódolt Adat file



! Syigorú korlát 22! byte - 470 byte Komoly korlátozás (*) 1024-bit key: 86 byte

K 3971 byte - 4045 byte




K El.

K K A 160-bit key, ∼22ECC byte: 83 byte A


ECC 50 ×


K K T P

K El.


ECC



Kódolt Adat file




K 3971 byte - 4045 byte




K El.



ECC 50 ×

ECC 3× 160-bit key: 42 byte

K K T P

K K El.T El.


ECC



Kódolt Adat file




K 3971 byte - 4045 byte




K El.



ECC 50 ×

ECC 3× 160-bit key: 42 byte

(*) Nagy adatok kódolása (pl.100 byte-os adat, kulcsmérettől függően): RSA-nál csak több lépésben hajtható végre ECC-nél akár egy lépésben Ilyenkor a kódolás az ECC-nél akár 10-szer gyorsabb, mint az RSA-nál! (Annak ellenére, hogy az RSA egy lépésnél gyorsabb.)

K K T P

K K El.T El.

Összefoglalás Gyenge pontok: RSA: ! Kulcsgenerálás ! Egy lépésben kódolható adatméret

ECC: ! Új közös paraméterek generálása ! Előszámított táblák használata szükséges

Erősség: RSA: ! Gyors kódolás ! Gyors aláírás ellenőrzés ! Paraméter file-ok mérete

Σ:

ECC: ! Gyors dekódolás ! Gyors aláírás ! Kódolt adat file-ok mérete ! Aláírás file-ok mérete




Σ:


Melyik a jobb algoritmus…?




Σ:


Melyik a jobb algoritmus…? Általánosságban nem eldönthető.




Σ:


Általánosságban nem eldönthető DE




Σ:


Általánosságban nem eldönthető DE adott alkalmazás igényei ismeretében eldönthető .

Új riváliosok XTR (Efficient Compact Subgroup Trace Representation) http://www.ecstr.com/

! Kidolgozók: Arjen Lenstra, Eric Verheul ! Crypto2000 konferencián publikálták először ! Az XTR biztonság a véges testek feletti DLP-n alapszik ! „Az XTR legalább olyan biztonságos, mint az RSA.” ! „Az XTR pareméter- és kulcsgenerálása 80-szor gyorsabb, mint az RSA.” ! „Az XTR olyan kulcsbit-hatékony, mint az ECC.” ! „Az XTR gyorsabb, mint az ECC.” ! „Az XTR egyesíti az RSA és az ECC előnyeit, jó alternatívája ezeknek az SSL-ben, WAP-ban stb.”

Érdekesség: Új riválisok NTRU http://www.ntru.com/

! ! ! ! !

Kidolg.: Jeffrey Hoffstein, Joseph Silverman, Jill Pipher, Daniel Lieman 1996: NTRU Cryptosystems Inc. 2000. július: USA szabadalom Az NTRU biztonság a rács redukción alapszik NTRU Challange (eddigieket senki sem oldotta meg)

! „Az NTRU akár 2000-szer gyorsabb, mint az alternatívái.” ! „A szükséges programkód akár 1/50 méretű.” (Kódolás 20 soros, dekódolás 52 soros C program.) ! „Az NTRU legalább 100-szor gyorsabb, mint az ECC.” !„Az NTRU struktúrája egyszerűbb az RSA-énál.” ! „Az NTRU kulcsméretek hasonlóak a jelenleg használtakhoz.” - Titkos kulcs: max. 80 bit - Összesen: max. 2000 bit ! „A kódolás és dekódolás az NTRU-val 1-2 nagyságrenddel gyorsabb.” ! NTRU 167 ≈ RSA 512; NTRU 263 ≈ RSA 1024; NTRU 503 ≈ RSA 2048; ! Törés: NTRU 167: 550 év; NTRU 503: 5,4 103 év

Nyilvános kulcsú rendszerek a gyakorlatban ! Titkosítás ! Digitális aláírás ! Autentikáció ! Nyilvános kulcs nyilvánossága ! Titkos kulcs titkossága ! Időkezelés problémája ! További érdekes problémák

Ismétlés Nyilvános kulcsú kriptográfia Összefoglaló Előadásomban az elektronikus aláírásról szóló magyar törvényterveze tet szándékozom elemzés alá vetni. Vizsgálódásom során nem jogi

FK1 GK2

F-1K1 = GK2 K1: nyilvános kulcs K2: titkos kulcs

Speciális kapcsolat a kulcsok között: • Egymás kiegészítő párjai • Egy kulcsnak csak egy párja van • Egymásból gyakorlatilag kiszámíthatatlanok

Kulcsgeneráló eljárás garantálja

Alapfeltételezés: • Mindenki rendelkezik kulcspárral • A nyilvános kulcsát mindenki nyilvánosságra hozza • Titkos kulcsát szigorúan titokban tartja

Titkosítás

Titkosítás

Anna

Titkosítás Barbara

Anna

Titkosítás Barbara

Anna

Barbara titkos kulcsa

Titkosítás Barbara Barbara nyilvános kulcsa

Anna



Anna



Anna Összefoglaló Előadásomban az elektronikus aláírásról szóló magyar törvénytervezetet szándékozom elemzés alá vetni. Vizsgálódásom során nem jogi




Kódolás Barbara nyilvános kulcsával











Anna


Összefoglaló Előadásomban az elektronikus aláírásról szóló magyar törvénytervezetet szándékozom elemzés alá vetni. Vizsgálódásom során nem jogi


Dekódolás Barbara titkos kulcsával













HIBALEHETŐSÉG: Nyilvános kulcsú titkosítást értelmes szöveg titkosítása használni nem szabad!

Titkosítás Értelmes szöveg titkosítása:

x1 x2 x3 Lehetséges válaszok

kódolás az ismert nyilvános kulccsal

y1 y2

?

y

y3 Lehetséges kódolt válaszok

Kódolt válasz

Helyes alkalmazás: Nagy entrópiájú adat kódolására (pl. Session-key, Dokumentum lenyomat: lásd későbbi példákban!) A nyilvános kulcsú kriptográfiában a rejtjelezés alapfunkció, azonban a felhasználási terület nem a szöveg titkosítása, hanem az összetettebb funkciókban van jelentősége!

Digitális aláírás Aláíró fél

Ellenőrző fél

Digitális aláírás Aláíró fél Összefoglaló Előadásomban az elektronikus aláírásról szóló magyar törvénytervezetet szándékozom elemzés alá vetni. Vizsgálódásom során nem jogi szempontból kívánom feltárni az „érzékeny pontokat”, hanem a jogi szabályozás és a mögöttes technikai háttér kapcsolatára, a technikai problémákra próbálok rávilágítani. A vizsgálat eredményeként megállapítható, hogy a törvénytervezet az EU irá

Ellenőrző fél


Ellenőrző fél Összefoglaló Előadásomban az elektronikus aláírásról szóló magyar törvénytervezetet szándékozom elemzés alá vetni. Vizsgálódásom során nem jogi szempontból kívánom feltárni az „érzékeny pontokat”, hanem a jogi szabályozás és a mögöttes technikai háttér kapcsolatára, a technikai problémákra próbálok rávilágítani. A vizsgálat eredményeként megállapítható, hogy a törvénytervezet az EU irá


Ellenőrző fél Megbízhatatlan hálózat

Összefoglaló Előadásomban az elektronikus aláírásról szóló magyar törvénytervezetet szándékozom elemzés alá vetni. Vizsgálódásom során nem jogi szempontból kívánom feltárni az „érzékeny pontokat”, hanem a jogi szabályozás és a mögöttes technikai háttér kapcsolatára, a technikai problémákra próbálok rávilágítani. A vizsgálat eredményeként megállapítható, hogy a törvénytervezet az EU irá


Lenyomatkészítés




Lenyomatkészítés

Kódolás a titkos kulccsal

DIGITÁLIS ALÁÍRÁS




Lenyomatkészítés








Lenyomatkészítés





Lenyomatkészítés



Lenyomatkészítés





Lenyomatkészítés



Lenyomatkészítés

Kódolás a titkos kulccsal Dekódolás a nyilvános kulccsal




Lenyomatkészítés




Lenyomatkészítés

=? Dekódolás a nyilvános kulccsal



Autentikáció „Amit az én nyilvános kulcsommal lehet dekódolni, az biztosan az én titkos kulcsommal készült.” ! „dekódolni” Fontos az adat formátuma! - Specifikációk ! „én titkos kulcsommal” Titkos kulcs titokban tartása! -Adatsor tárolási helye (file, chipkártya) -Hozzáférés védelem; felhasználó azonosítás ! „én nyilvános kulcsommal” A személy és a nyilvános kulcs megbízható összerendelése! - Fingerprint, Bizalmi lánc, elektronikus tanúsítvány, Ellenőrzési lánc (erről később még lesz szó)

Autentikáció „Amit az én nyilvános kulcsommal lehet dekódolni, az biztosan az én titkos kulcsommal készült.” ! „dekódolni” Fontos az adat formátuma! - Specifikációk ! „én titkos kulcsommal” Titkos kulcs titokban tartása! -Adatsor tárolási helye (file, chipkártya) -Hozzáférés védelem; felhasználó azonosítás ! „én nyilvános kulcsommal” A személy és a nyilvános kulcs megbízható összerendelése! - Fingerprint, Bizalmi lánc, elektronikus tanúsítvány, Ellenőrzési lánc (erről később még lesz szó)

Autentikáció Alapja: „Amit az én nyilvános kulcsommal lehet dekódolni, az biztosan az én titkos kulcsommal készült.” pl. Challenge & Response módszer:

A

adat

?

FKB,t [adat]

B

FKB,ny [ FKB,t [adat] ] = adat

HIBA: Undue signing Ha az „adat” jelentéssel bír. Helyes alkalmazás: ! Az „adat” kialakításában vegyen részt B is. VAGY

! Különböző kulcsok használata autentikációra és aláírásra.

Nyilvános kulcs nyilvánossága Kritikus pont: A szereplők nyilvános kulcsának közzététele hiteles módon. ! ! ! !

Személyes találkozás Nehézkes, bonyolult Támadás veszélye! Elektronikus formában elküldeni Nyilvános kulcs lenyomata (fingerprint) megbízható közzététele Megbízható harmadik fél által kiadott tanúsítvány

Megbízható harmadik fél (Trusted Third Party) ! Az életben ismert személy ! Hatóság ! Szolgáltató „Elektronikus igazolvány”: Certificate (Tanúsítvány) Nyilvános kulcs és a személy összekapcsolása hitelt érdemlő módon.

Nyilvános kulcs nyilvánossága „Elektronikus igazolvány”: Certificate (Tanúsítvány) SZEMÉLYI IGAZOLVÁNY Állandó adatok: - név, - anyja neve, - szig. szám.

Biometriai adatok: - fénykép, aláírás Használat: - biometriai adat ellenőrzése - fizikai birtoklás: csak egyetlen darab létezik

Hitelesség bizonyítása: - hatóság pecsétje,

Érvényesség: -tól, -ig

DIGITÁLIS IGAZOLVÁNY Állandó adatok: - név (Common Name), - értelmezést segítő adatok, - serial number

Kriptográfiai adat: - nyilvános kulcs Használat: - titkos kulcs birtoklása (kriptográfiai ellenőrzés) - akármennyi létezhet

Hitelesség bizonyítása: - hatóság digitális aláírása

Érvényesség: -tól, -ig

Certificate (X.509) issuer :/C=HU/L=Budapest/O=NetLock Halozatbiztonsagi Kft./OU=Tanusitvanykiadok/CN=NetLock Teszt Tanusitvanykiado subject:/C=HU/ST=/L=Budapest/O=/OU=/CN=Endrodi Csilla/[email protected] serial :0100Certificate: Data: Version: 3 (0x2) Serial Number: 256 (0x100) Signature Algorithm: md5WithRSAEncryption Issuer: C=HU, L=Budapest, O=NetLock Halozatbiztonsagi Kft., OU=Tanusitvanykiadok, CN=NetLock Teszt Tanusitvanykiado Validity Not Before: Apr 20 14:48:40 2000 GMT Not After : May 20 14:48:40 2000 GMT Subject: C=HU, ST=, L=Budapest, O=, OU=, CN=Endrodi Csilla/[email protected] Subject Public Key Info: Public Key Algorithm: rsaEncryption RSA Public Key: (512 bit) Modulus (512 bit): 00:91:ac:d8:b7:49:2e:85:a8:f5:cb:01:00:6e:4c: 2b:cf:3d:73:f8:24:d2:61:3b:cd:4a:09:e4:c5:e6: 5c:df:f8:36:4c:58:76:e0:6a:ef:6f:37:32:1b:56: f7:2a:0a:0e:bf:11:25:cf:51:72:3b:55:c0:60:75: 05:46:c5:0c:47 Exponent: 65537 (0x10001)

X509v3 extensions: Netscape Comment: FIGYELEM! Ezen tanusitvany a NetLock Kft. Altalanos Szolgaltatasi Felteteleiben leirt eljarasok alapjan keszult. A hitelesites folyamatat a NetLock Kft. termekfelelosseg-biztositasa vedi. A digitalis alairas elfogadasanak feltetele az eloirt ellenorzesi eljaras megtetele. Az eljaras leirasa megtalalhato a NetLock Kft. Internet honlapjan a https://www.netlock.net/docs cimen vagy kerheto az [email protected] e-mail cimen. IMPORTANT! The issuance and the use of this certificate is subject to the NetLock CPS available at https://www.netlock.net/docs or by e-mail at [email protected]. Netscape Cert Type: 0xA0 X509v3 Basic Constraints: critical 0.... X509v3 Key Usage: critical .... Signature Algorithm: md5WithRSAEncryption 63:4c:ff:12:aa:64:19:1a:0e:b2:ae:5e:5e:2f:fe:48:d2:8e: f7:28:ff:ce:34:b5:0d:af:17:ed:aa:55:db:62:af:67:66:30: 93:08:44:b9:21:7a:60:a2:47:d6:5d:6a:11:47:30:fe:22:82: f5:b0:b1:2b:a7:aa:ed:0c:73:7a:e7:d5:99:82:08:73:a2:0d: 13:e5:5e:21:7f:a0:23:9b:1e:ed:1c:bf:75:1b:5b:60:27:60: f2:3d:9c:d7:1c:39:43:b1:f8:af:af:74:17:bd:77:ec:cc:21: e1:89:eb:e7:ca:f2:bd:92:e5:42:a8:cf:4b:c3:f7:7f:76:6e: f7:be

-----BEGIN CERTIFICATE----MIIE3DCCBEWgAwIBAgICAQAwDQYJKoZIhvcNAQEEBQAwgY4xCzAJBgNVBAYTAkhV MREwDwYDVQQHEwhCdWRhcGVzdDEnMCUGA1UEChMeTmV0TG9jayBIYWxvemF0Yml6 dG9uc2FnaSBLZnQuMRowGAYDVQQLExFUYW51c2l0dmFueWtpYWRvazEnMCUGA1UE AxMeTmV0TG9jayBUZXN6dCBUYW51c2l0dmFueWtpYWRvMB4XDTAwMDQyMDE0NDg0 MFoXDTAwMDUyMDE0NDg0MFowfDELMAkGA1UEBhMCSFUxCTAHBgNVBAgTADERMA8G A1UEBxMIQnVkYXBlc3QxCTAHBgNVBAoTADEJMAcGA1UECxMAMRcwFQYDVQQDEw5F bmRyb2RpIENzaWxsYTEgMB4GCSqGSIb3DQEJARYRY3NpbGxhQHNjaC5ibWUuaHUw XDANBgkqhkiG9w0BAQEFAANLADBIAkEAkazYt0kuhaj1ywEAbkwrzz1z+CTSYTvN SgnkxeZc3/g2TFh24GrvbzcyG1b3KgoOvxElz1FyO1XAYHUFRsUMRwIDAQABo4IC nDCCApgwggJgBglghkgBhvhCAQ0EggJRFoICTUZJR1lFTEVNISBFemVuIHRhbnVz aXR2YW55IGEgTmV0TG9jayBLZnQuIEFsdGFsYW5vcyBTem9sZ2FsdGF0YXNpIEZl bHRldGVsZWliZW4gbGVpcnQgZWxqYXJhc29rIGFsYXBqYW4ga2VzenVsdC4gQSBo aXRlbGVzaXRlcyBmb2x5YW1hdGF0IGEgTmV0TG9jayBLZnQuIHRlcm1la2ZlbGVs b3NzZWctYml6dG9zaXRhc2EgdmVkaS4gQSBkaWdpdGFsaXMgYWxhaXJhcyBlbGZv Z2FkYXNhbmFrIGZlbHRldGVsZSBheiBlbG9pcnQgZWxsZW5vcnplc2kgZWxqYXJh cyBtZWd0ZXRlbGUuIEF6IGVsamFyYXMgbGVpcmFzYSBtZWd0YWxhbGhhdG8gYSBO ZXRMb2NrIEtmdC4gSW50ZXJuZXQgaG9ubGFwamFuIGEgaHR0cHM6Ly93d3cubmV0 bG9jay5uZXQvZG9jcyBjaW1lbiB2YWd5IGtlcmhldG8gYXogZWxsZW5vcnplc0Bu ZXRsb2NrLm5ldCBlLW1haWwgY2ltZW4uIElNUE9SVEFOVCEgVGhlIGlzc3VhbmNl IGFuZCB0aGUgdXNlIG9mIHRoaXMgY2VydGlmaWNhdGUgaXMgc3ViamVjdCB0byB0 aGUgTmV0TG9jayBDUFMgYXZhaWxhYmxlIGF0IGh0dHBzOi8vd3d3Lm5ldGxvY2su bmV0L2RvY3Mgb3IgYnkgZS1tYWlsIGF0IGNwc0BuZXRsb2NrLm5ldC4wEQYJYIZI AYb4QgEBBAQDAgCgMA8GA1UdEwEB/wQFMAMBAQAwDgYDVR0PAQH/BAQDAgCgMA0G CSqGSIb3DQEBBAUAA4GBAGNM/xKqZBkaDrKuXl4v/kjSjvco/840tQ2vF+2qVdti r2dmMJMIRLkhemCiR9ZdahFHMP4igvWwsSunqu0Mc3rn1ZmCCHOiDRPlXiF/oCOb Hu0cv3UbW2AnYPI9nNccOUOx+K+vdBe9d+zMIeGJ6+fK8r2S5UKoz0vD9392bve+ -----END CERTIFICATE-----

Titkos kulcs titkossága Csak a tulajdonos használhassa! (# azonosítás) Jelszóval védett file, Smart card, Biometria Kritikus pont: Titkos kulcs elvesztése/kompromittálódása Veszély: A kulcsot birtokló hitelesnek tűnően aláírhat az igazi tulajdonos nevében. A hamisíthatatlanság, egyediség, letagadhatatlanság megszűnik. Teendő: A kulcspár használatának azonnali letiltása.

Tanúsítvány visszavonási lista Certificate Revocation List (CRL)

A visszavonást megelőzően készített aláírásoknak érvényesnek kell maradniuk! Fontos: Minden aláírás és a visszavonás időpontjának rögzítése.

Időkezelés problémája Ki rögzíti az időpontot? Aláírást végző személy • Tévedés • Visszaélés lehetősége Megbízható harmadik fél: Time Stamping Authority (TSA)

Időbélyegző (Time Stamp, TS)

$

Elosztott rendszerekben az időkezelés: „Később történt”

„Előbb történt”

200104-19 17:10

Az elosztott rendszerekben, ahol az elemek egymástól fizikailag is távol vannak, a kommunikáció különböző megbízhatóságú rendszerelemeken keresztül és különböző ideig tarthat, az idő kezelése nehézkes.

A

t

200104-19 17:10

Az elosztott rendszerekben, ahol az elemek egymástól fizikailag is távol vannak, a kommunikáció különböző megbízhatóságú rendszerelemeken keresztül és különböző ideig tarthat, az idő kezelése nehézkes.

A

t Az elosztott rendszerekben, ahol az elemek egymástól fizikailag is távol vannak, a kommunikáció különböző megbízhatóságú rendszerelemeken keresztül és különböző ideig tarthat, az idő kezelése nehézkes.

200104-19 17:10

A

További érdekes problémák

1. CA-k hibázása Kritikus pont a felhasználó adatainak ellenőrzése! 2. CRL vizsgálata Sok esetben nem használják, ha igen, mikori, honnan származik…? 3. Időkezelés Kettős időbélyeg Szűkülő időintervallumok CA subject

4. Tanúsítvány típusa Magánszemély / beosztás Nem csak embereknek lehet rá szüksége

További érdekes problémák 5. Certificate ellenőrzése Ellenőrzási lánc nem egyértelmű Kapott / tárolt certificate-ek

„Root CA” CA 1

6. Kulcsgenerálás Ki generálja a kulcsot? User / központ

cert1

CA 2

cert2

7. Algoritmus típusának ellenőrzése RSA/ECC: más biztonságos kulcsméret 8. Certificate-ek kompatíbilitása Országspecifikus attributumok 9. Mit írtunk alá…? „Csak szöveg”: Mit jelent pontosan? (Word document, Rich Text Format, makrók?)

„Rejtett” mezők

Összefoglalás ! Nyilvános kulcsú algoritmusok matematikai alapjai - A nyilvános kulcsú kriptográfiai algoritmusok széles választéka áll rendelkezésre. - Ezek megfelelően használva elegendő biztonságot tudnak nyújtani. Egy rendszer leggyengébb pontjai általában nem a kriptográfiai algoritmusok. - Egy rendszer biztonságossága nagyon sok körülménytől függ. Nem elég a „legmodernebbnek”, „legjobbnak” kikiáltott algoritmusokat használni. - Ismerjük és kövessük a világ fejlődését, és legyünk körültekintőek.

Összefoglalás ! Nyilvános kulcsú algoritmusok - A kulcsméret mellett számos egyéb tényezőt is figyelembe kell venni az algoritmus megválasztásánál. - Egyértelműen legjobb algoritmus nincsen. Ismerjük meg az algoritmusok sajátosságait, és a létrehozandó alkalmazás számára legcélszerűbbet válasszuk.

! Nyilvános kulcsú rendszerek a gyakorlatban - A nyilvános kulcsú infrastruktúra gyakorlati használata még rengeteg „gyermekbetegséggel” küzd. - A nehézségeken való túljutáshoz fontos a nemzetközi szakértői együttműködés (szabványosítás). - A szabályozások, ajánlások gyakorlatba való átültetéséhez nem elég azokat papírra vetni! (marketing, termékek kötelező bevezetése stb.)

Irodalmak ! RSA RFC 2437, PKCS #1: RSA Cryptography Specifications http://www.rsa.com, http://www.ietf.org ! ECC Sandards for Efficient Cryptography Group (SECG) SEC1: Elliptic Curve Cryptography SEC2: Recommended Elliptic Curve Cryptography Domain Parameters ! Crypto++ „a C++ Class Library of Cryptographic Primitives” http://www.cryptopp.com ! XTR (Efficient Compact Subgroup Trace Representation) http://www.ecstr.com/

! NTRU http://www.ntru.com/

í Köszönöm a figyelmet!

Endrődi Csilla

Nyilvános kulcsú kriptográfia

Recommend Documents