Ochrana dat Obsah. Výměna tajných klíčů ve veřejném kanálu. Radim Farana Podklady pro výuku. Kryptografické systémy s tajným klíčem,

2.12.2014

Ochrana dat Radim Farana Podklady pro výuku

Obsah Kryptografické systémy s tajným klíčem,  výměna tajných klíčů veřejným kanálem,  systémy s tajným klíčem.

Elektronický podpis. Certifikační autorita. Metody zabezpečení komunikace.

Výměna tajných klíčů ve veřejném kanálu Diffie-Hellman-Merkle

Whitfield Diffie

Martin E. Hellman

Ralph C. Merkle

* 5. 6. 1944

* 2. 10. 1945 New York

* 2. 2. 1952

1. Oba účastníci si zvolí dvě čísla α a q. A to zcela veřejně. 2. Každý účastník si zvolí tajné číslo Xi a odešle partnerovi Yi jako výsledek operace: Yi   X i mod q . Kde i = 1, 2 pro jednotlivé účastníky. 3. Po výměně vypočítají společný (sdílený) klíč K12: K12  Y2X1 mod q   X1 X 2 mod q , pro prvního účastníka a K12  Y1X 2 mod q   X1 X 2 mod q , pro druhého účastníka.

1

2.12.2014

Systémy s veřejným klíčem Ze šifrovacího klíče nelze učit klíč dešifrovací. Funkce k = f(k-1) je neinverzibilní. Jednocestná funkce (je možno snadno určit f(x) a „velmi nesnadno“ f-1(x)). Základní principy: zavazadlový problém, faktorizace velkých čísel.

RSA Ronald L. Rivest * 6. 5. 1947

Adi Shamir * 6.7. 1952

Leonard M. Adleman * 31. 12. 1945 San Francisco, USA

1. Převedeme alfanumerické vyjádření znaků na numerické (obvykle se používá ASCII kód). 2. Text rozdělíme na bloky stejné délky. Obsah jednoho bloku vyjádříme jako x. 3. Zvolíme číslo N, které je součinem dvou náhodně zvolených 100-místných prvočísel N = pq. Číslo N má tedy 200 míst v dekadickém vyjádření. Přitom chceme, aby platilo 1  x < N. 4. Zvolíme šifrovací exponent s, tak aby byl nesoudělný s (N), tedy aby platilo (s, (N)) = (s, (p - 1)(q - 1)) = 1. 5. Každý účastník zveřejní čísla N a s spolu se svou adresou v telefonním seznamu. 6. Dále najde číslo t, aby vyhovovalo kongruenci ts  1 mod (N), respektive ts  1 mod (p - 1)(q - 1). Protože platí (s, (N)) = 1, má tato kongruence jediné řešení. 7. K šifrování bude použita transformace y = xs mod N a k dešifrování transformace x = yt mod N. 8. Šifrovaný text se přenáší běžným přenosovým kanálem.

RSA – příklad použití volíme p = 31, q = 37, odtud N = 1147 určíme (N) = (p - 1)(q - 1) = 1080 = 23.33.5, zvolíme nesoudělný šifrovací exponent s = 7, určíme dešifrovací exponent t7  1 mod 1080, neboli t.7 – 1 = i.1080 t = 463.

2

2.12.2014

RSA - realizace Šifrujeme: 1007 mod 1147 = 803, Dešifrujeme: 803463 mod 1147 = 100, pro násobení v modulo N platí: x.x mod N = (x1N + x2)( x1N + x2) mod N = = (x12N2 + 2x1x2N + x22) mod N = x2 x2 mod N, postupné násobení: ((x.x mod N).x mod N) ...

PGP Pretty Good Privacy Phil Zimmermann 1991 první freeware verze. Tři roky vyšetřování pro narušení zákona o zákazu vývozu kryptografického software RSA a/nebo DH systém pro šifrování náhodného tajného klíče IDEA (International Data Encryption Algorithm) Řešení elektronického podpisu

* 12. 2. 1954 Camden, NJ, USA

Elektronický podpis

Zpráva

kB

kB-1

Zpráva

hash

hash kA-1 kB

Podpis

Zpráva

kA

Podpis

Podpis kB-1 ????????

Podpis

3

2.12.2014

Certifikační autorita Sdílení důvěry věří

věří

Certifikační autorita

Ověření veřejného klíče

věří věří

Certifikace autorit vzájemně

Hašovací funkce  Zpočátku byla jako hašovací funkce označována funkce, která libovolně velkému vstupu přiřazovala krátký hašovací kód o pevně určené délce.  V současné době se označení hašovací funkce používá v kryptografii pro kryptografickou hašovací funkci, která má oproti původní definici ještě navíc vlastnosti jednosměrnosti (one-way) a bezkoliznosti (collission-free).

Jednosměrnost Jednosměrnost znamená, že z M je možno snadno vypočítat h(M), ale obráceně to je pro náhodně zadaný hašovací kód H výpočetně nezvládnutelné.

4

2.12.2014

Bezkoliznost  Bezkoliznost prvního řádu vyžaduje, aby bylo výpočetně nezvládnutelné nalezení libovolných dvou různých zpráv M a M‘ tak, že h(M) = h(M‘).  Pokud se toto stane, nalezli jsme kolizi.  Tato vlastnost je důležitá u elektronických podpisů. Umožňuje nám podepisovat pouze hašovací kód (zkráceně haš) a nikoliv celou zprávu, která může být značně dlouhá (u MD5/SHA-1/SHA-256 prakticky až do délky D  2264  1 bitů).

Bezkoliznost Bezkoliznost druhého řádu nebo také odolnost proti nalezení druhého vzoru požaduje, aby pro daný náhodný vzor x bylo výpočetně nezvládnutelné nalezení druhého vzoru y  x pro které platí h( x)  h( y) .

Kolize při použití hašovací funkce Je třeba si uvědomit, že existuje velmi mnoho různých zpráv (1  21  ...  2D  2D1  1) pro maximální délku zprávy D. Naproti tomu existuje jen málo hašovacích kódů (u algoritmu MD-5 je to jen 2128). Nutně tedy existuje velké množství kolizí (v průměru je to kolem 2D-127). Jde tedy o to, aby nebyly nalezitelné v dostupném čase.

5

2.12.2014

Kolize při použití hašovací funkce Hašovací funkce

M

M‘

h(M) = h(M‘)

Množina obrazů 2128 Množina vzorů

Náhodné orákulum  Jako orákulum označujeme libovolný stroj, který na vstup odpovídá nějakým výstupem, a to na stejný vstup vždy stejným výstupem. Jako náhodné orákulum pak označujeme orákulum, které novému vstupu přiřadí náhodnou hodnotu výstupu a zapamatuje si ji pro příští použití. Jakmile je orákulu předložen stejný vstup, odpoví opět stejným výstupem. Je tedy zřejmé, že bychom byli rádi, kdyby se hašovací funkce chovala jako náhodné orákulum. V takovém případě by složitost nalezení vzoru (zprávy) ke známému obrazu (hašovacímu kódu) byla rovna 2n , kde n – počet bitů obrazu.

Pravděpodobnost nalezení kolize  Jak velká musí být množina náhodných zpráv, aby se v ní s významnou pravděpodobností vyskytovaly alespoň dvě zprávy se stejným hašovacím kódem? Pro 50% pravděpodobnost výskytu kolize očekáváme, že pro n-bitovou hašovací funkci to bude množina 1 / 2.2n vzorů. Známý narozeninový paradox však říká, že pro n-bitovou hašovací funkci nastává kolize se zhruba 50% pravděpodobností již v množině 2 n / 2 vzorů.  Pro 160bitový hašovací kód bychom očekávali 1/ 2.2160  7,31.1047 ale bude to pouze 280  1,21.1024 .  Dostupné hašovací funkce jsou náchylné na kolize prvního druhu, ale nikoliv druhého druhu.

6

2.12.2014

Konstrukce hašovacích funkcí  Zpráva zpracovávaná hašovací funkcí může být 64 velmi dlouhá (např. D  2  1), takže ji musíme zpracovávat po blocích.  Doplníme zarovnání zprávy na délku danou celistvým násobkem délky bloku.  Nejčastěji je proto zarovnání definováno jako jednička a řada nul, za kterými následuje délka původní zprávy - Damgard-Merklovo zesílení,

Ivan Bjerre Damgård * 1956 http://pure.au.dk/portal/ da/[email protected]

Iterativní hašovací funkce  Hašovací funkce používají Damgard-Merklův (DM) princip iterativní hašovací funkce s využitím kompresní funkce.  Kompresní funkce f zpracovává blok mi zprávy a produkuje výsledek, označovaný jako kontext Hi postupně pro i = 1, 2, …, N. Hodnota kontextu je pak vstupem do dalšího iteračního kroku. Na počátku musí být kontext H0 nastaven na inicializační hodnotu (IV – initial value), která je určena jako konstanta v definici hašovací funkce.

Kompresní funkce Kontextem bývá obvykle několik 16bitových nebo 32bitových slov, u MD5 jsou to čtyři slova A, B, C, D (celkem 128 bitů).

mi

f

Hi

Hi-1

kompresní funkce

7

2.12.2014

Bezkoliznost kompresní funkce Pokud je hašovací funkce bezkolizní, bude bezkolizní také kompresní funkce. Opačně je situace složitější. Pro Damgard-Merklovu konstrukci hašovací funkce bylo dokázáno, že pokud je bezkolizní kompresní funkce, je bezkolizní také hašovací funkce.

Princip doplňování, kompresní funkce a iterativní hašovací funkce blok 512 bitů bitů:

8

8

8

význam:

h

o

j

příklad:

01101000

01101111

01101010

1

423

64

doplněk

délka

0…0

1

0 … 1011

Ahoj Jirko. … N bloků … jsem …

… nebo také … hoj

m1

f IV

…

m2

…

mi

f

f

doplněk

mN

Hi

f

HN

Hi-1

Konstrukce kompresní funkce  Ta musí být velmi robustní, musí zajistit dobré promíchání bitů zprávy a jednocestnost. Můžeme je konstruovat např. na základě známých jednocestných funkcí a použít znalosti z oblasti blokových šifer: H i Emi H i1  kde je E – kvalitní bloková šifra  Davies-Meyerova konstrukce kompresní funkce pak zesiluje vlastnost jednocestnosti ještě přičtením vzoru před výstupem:

H i f H i1 , mi   Emi H i1  XOR H i1

8

2.12.2014

Kompresní a hašovací funkce MD5 A

M1

B

M2 … M15 M16 Jiná permutace Mi

C

Hi-1

D

F

A

B

C

D

F

Mi

Mi Ki

Ki

<<<s

<<<s

A

B

C

A

B

C

D

A

B

C

D

C

D

B

C

D

B

C

D

D

F Mi Ki

mi

Jiná permutace Mi

<<<s

64 rundy A

B

… Jiná permutace Mi

A

mi

F Mi Ki

f

Hi

<<<s

Hi-1 A

Zpracování jednoho bloku kompresní funkcí

Hi

Bezpečnost MD-5  Algoritmus MD5 se stal předmětem rozsáhlých útoků. Bylo nalezeno několik postupů nalezení kolizí prvního řádu. Útočník umí najít dvě různé (náhodné) zprávy se stejným hašovacím kódem. Ale není schopen stejně snadno nalézt kolizi druhého řádu, tedy najít druhý vzor (zprávu) se stejným hašovacím kódem.  Obdobně byly prezentovány útoky schopné se složitostí 2 33 hašovacích operací pokořit algoritmus SHA-0 a se složitostí 269 hašovacích operací algoritmus SHA-1 (narozeninový paradox očekává 280 operací). To je sice stále velké číslo, ale vzhledem ke stálému růstu výkonu počítačů (v souladu s Mooreovým zákonem) nelze tuto skutečnost podceňovat.  Jsou dokumentovány postupy, jak může útočník oklamat certifikační autoritu a získat certifikát na dva různé šifrovací klíče

Třída hašovacích funkcí SHA-2 od 1. února 2003 k dispozici nová trojice hašovacích funkcí (Secure Hash Algorithm) SHA-256, SHA-384 a SHA-512 (souhrnně označované jako SHA-2) a od února 2004 SHA-224 (dodatek SHA-2). Tyto funkce zvětšuji délky hašovacího kódu na 256, 384 a 512 bitů (SHA-224 má 224 bitový hašovací kód), což odpovídá složitosti 2128, 2192 a 2256 pro nalezení kolizí narozeninovým paradoxem.

9

2.12.2014

Třída hašovacích funkcí SHA-3 V roce 2012 byla po pěti letech ukončena soutěž pro nový standard SHA-3 a přitom byl ve stejné době vydán další standard, který používá již známý standard SHA512, s výhodou využívající 64bitové operace na 64bitových procesorech. Jeho výstup je pak zkrácen na potřebnou délku t. Tak vznikají algoritmy SHA-512/t, neboli SHA512/224, SHA-512/256, SHA-512/384 a SHA-512/512.

Platební karta žádost o platební kartu k účtu 56879

účet 56879

1

2 ověření stavu účtu 56879

3 vydání platební karty k účtu 56879

6 identifikace účtu 56879 a ověření stavu

žádost o vydání peněz

4 identifikace uživatele (PIN)

on-line platební terminál

5

7 vydání peněz

11 off-line platební terminál

žádost o vydání zboží

inkaso z účtu 56879

8 9 převzetí údajů karty (otisk)

10 vydání zboží

Elektronická peněženka žádost o elektronickou peněženku k účtu 56879

účet 56879

1

2 ověření stavu účtu 56879

3 vydání elektronické peněženky k účtu 56879

6 identifikace účtu 56879 a ověření stavu

žádost o načerpání peněz

4 identifikace uživatele (PIN)

on-line terminál

5

7

vzájemné zúčtování

uložení peněz do peněženky převod peněz mezi dvojicí peněženek

8

9

10

11

uložení na účet 42136

12

10

2.12.2014

Elektronické peníze účet 56879

žádost o 100 Kč z účtu 56879

1

2 ověření stavu účtu 56879, vygenerování bankovky

3 vydání bankovky: 100-3214-5090

i-C-C 6

mod N

uložení na účet

výplata

platba

4

(CE

E-1(i)

5

ověření bankovky: mod N)E(i) mod N = C

-1(i)

Základní požadavky  nepadělatelnost  možnost ověření platnosti bankovky  přenositelnost z osoby na osobu (fax, e-mail,...)

   

anonymita plateb (neidentifikovatelnost) nízké náklady na výrobu dělitelnost problém dvojí úhrady

Zabezpečení mobilní komunikace Mobile Terminal Authentication Centre Subscriber Identification Module

GSM Net

Mobile Station Žádost o login 1

Žádost o autentizaci 2

RNG

<SRES’, Kc’> Šifrovací klíč pro A5

4

Klíč A38

3

<SRES’> 5

ne SRES’=SRES

SRES = A3(RAND, Klíč) Kc = A8(RAND, Klíč)

Přístup povolen 6

ano

0

31 SRES

95 Kc

A38(RAND, Klíč)

11

2.12.2014

Vlastní komunikace Časové sdílení kanálu: Time Division Multiple Access Číslo TDMA rámce

Kc 64 b

22 b A5

Opakování čísla TDMA rámce cca po 3,5 hod. komunikace

114 b uplink

Princip A5

+ LSFR R1

114 b downlink +

R1, 10

Data burst (114 b + synchronizace) (časový slot 576,9 μs)

bit hesla

+

LSFR R2 R2, 12

0

1

…

7

LSFR R3

Časový slot TDMA rámec

R3, 12

Nelineární řízení krokování (clock-controlled) LSFR

C Posuvný registr s lineární zpětnou vazbou (LSFR - linear feedback shift register)

12