vá ro ko Sý ětuše Kv

© Květuše Sýkorová

• elektronický podpis • hash funkce – bezpečná komunikace – princip – nejznámější hash funkce


• MD‐x • RIPEMD‐x • SHA

• definice: – „Elektronický podpis je nejobecnější pojem pro údaje v elektronické podobě, který slouží k ověřování identity podepisované osoby a pravosti dokumentu.“


• Může být realizován v podstatě jakoukoli technologií.

• formy: – digitální podpis • nejčastěji používaný, vychází z kryptografie s veřejným klíčem

– nascanovaný podpis • neměl by se řadit mezi elektronické podpisy – není bezpečný, snadno padělatelný

– biometrické metody © Květuše Sýkorová

• geometrie ruky, tváře, duhovka a sítnice a rohovka oka, …

– fyziologické techniky • otisky, oční sítnice, DNA, pot, pach, geometrie cév, …

– behaviorální techniky • analýza řeči, dynamika ručně psaných dopisů, …

• vlastnosti: – vstup: • libovolně dlouhý e‐dokument

– výstup: • řetězec určité délky (cca 50 – 300b) – dle zvoleného algoritmu


• připojen k dokumentu • zajišťuje – nepopiratelnost » autor nemůže popřít, že dokument vytvořil – autentizaci » příjemce ví, kdo je autorem dokumentu – integritu dat » příjemce má jistotu, že obsah dokumentu nebyl pozměněn

• bezpečnost – bezpečnost použitého algoritmu • „prolomení“

– bezpečnost implementace algoritmu • v rámci konkrétní aplikace

– důvěryhodnost centrální autority


– spolehlivost osoby • utajení soukromého klíče

• digitální podpis: – asymetrické algoritmy • pomalejší, nevhodné pro podpis celé zprávy

– hash funkce • jednosměrná – opačný proces není možný

• vrací řetězec pevné délky


– HASH = zhuštěná hodnota dlouhé zprávy

• výpočet velmi rychlý – mnohonásobně rychlejší

• stejná bezpečnostní kritéria – jako podpis asymetrickým algoritmem

podepisování s využitím digitálního podpisu (odesilatel)

otevřený text

hash funkce

hash zprávy

asymetrický algoritmus

digitální podpis


soukromý klíč odesilatele otevřený text


veřejný klíč adresáta

šifrovaný text

poslat nezabezpečeným kanálem

kontrola podpisu s využitím digitálního podpisu (adresát) nezabezpečený kanál digitální podpis



veřejný klíč odesilatele šifrovaný text


soukromý klíč adresáta

otevřený text

hash funkce

hash zprávy

porovnat

hash zprávy

• podepisování s využitím digitálního podpisu – vlastnosti: • nutné alespoň 1x šifrovat celou zprávu asymetrickým algoritmem – pomalé


• nepoužívá se moc často

podepisování s využitím digitálního podpisu a symetrického šifrování (odesilatel) otevřený text

hash funkce


hash zprávy

digitální podpis

soukromý klíč odesilatele


otevřený text

symetrický algoritmus

tajný klíč

šifrovaný text asymetrický algoritmus veřejný klíč adresáta

šifrovaný tajný klíč poslat nezabezpečeným kanálem

kontrola podpisu s využitím digitálního podpisu a symetrického šifrování (adresát) nezabezpečený kanál


šifrovaný tajný klíč

digitální podpis



hash zprávy

veřejný klíč odesilatele porovnat

tajný klíč

soukromý klíč adresáta šifrovaný text

symetrický algoritmus

otevřený text

hash funkce

hash zprávy

• podepisování s využitím digitálního podpisu a symetrického šifrování – vlastnosti: • vyžaduje dohodu předem


– formát přenášených dat – použité algoritmy

• definice: – jednosměrná matematická funkce • vstup x – blok textu proměnné délky

• výstup H(x) – blok pevné délky » např. 128b, 160b, 256b, … – haš, hašé, hash, otisk © Květuše Sýkorová

– základní vlastnost • komprese vstupu – vstup nelze zrekonstruovat – redukuje se množství informací ve vstupním bloku

• jednoduchost výpočtu – rychlý výpočet

z libovolného vstupu x

• vlastnosti: – zrychlené (de)šifrování • jednosměrná komprese vstupu • hash konstantní délky

– zachování integrity • malá změna o.t. vede na změnu hash

– vyloučení kolizí © Květuše Sýkorová

• kolize bloků

znamená

– pravděpodobnost kolize p dána délkou výstupního bloku d » 128b hash funkce má » 160b hash funkce má – 100% jistota kolize = použijeme 2 hash textů – 50% jistota kolize = použijeme 2 / hash textů

– využití: • protokoly pro digitální/elektronické podpisy – jejich součást, zajištění integrity


• kryptografické protokoly, certifikáty – jejich součást, PKI – SSL/TLS kryptografické protokoly » tvorba HMAC, generování klíčů, IV – SSH komunikační protokol » tvorba HMAC, integrita dat – IPsec » integrita zpráv, generování pseudonáhodných čísel

• časové značky – zajištění integrity

• operační systémy, servery – bezpečné uložení a kontrola hesel, hash‐hodnota

• obecný princip: – vstup = n‐bitové bloky ,


•

,…,

,

,

,…,

,…,

,

,…,

1. bit

2. bit

…

n. bit

blok 1

b11

b12

…

b1n

blok 2

b21

b22

…

b2n

:

:

:

blok m

bm1

bm2

…

bmn

hash fce

H1

H2

…

Hn

:

– výstup = n‐bitový hash •

,

,…,

– nejjednodušší hash funkce

⊗

⊗ ⋯⊗

• Merkle‐Damgårdova metoda – struktura hash funkcí – IV = iniciační vektor, f = kompresní funkce

IV

1. blok zprávy

2. blok zprávy

3. blok zprávy

n‐tý blok zprávy

f

f

f

f


– n‐tý blok • doplnit na velikost bloku – jednoznačné, kolik se doplnilo » jinak riziko kolizí – Merkle‐Damgårdovo zesílení » doplnění obsahuje info o délce zprávy

hash

• Merkle‐Damgårdova metoda – autoři: Merkle, Damgård • 1989, nezávisle na sobě – Merkleova meta metoda

• vstup: funkce f odolná vůči kolizím • výstup: iterovaná CRHF odolná vůči kolizím • matematicky dokázáno: © Květuše Sýkorová

– f je bezkolizní → bezkolizní i výstup M‐D HF

• realizace f: – vhodná bloková šifra – vhodná nelineární funkce

• druhy: – MAC • Message Authentization Code – hash funkce využívá k výpočtu tajný klíč (dva nezávislé vstupy M a K)

– MDC


• Manipulation Detection Code – hash funkce bez tajného klíče (jediný vstup M) » nebo i MIC = Message Integrity Check – OWHF = One‐way hash function » obtížné najít vstup pro danou hash – CRHF = Collision resistant hash function » obtížné najít dva kolizní vstupy – UOWHF = Universal One‐way hash function

• požadavky na HF – Preimage resistance • odolnost vůči získání předlohy (one‐way) – výpočetně nemožné získat vstup, kterému odpovídá daný otisk » pro všechny výstupy – nelze pro h najít x tak, aby

– 2nd preimage resistance


• odolnost vůči získání jiné předlohy (kolize 2. řádu, slabá odolnost) – výpočetně nemožné získat k jednomu vstupu druhý se stejným otiskem – nelze pro x najít y tak, aby a zároveň

– Collision resistance • odolnost vůči nalezení kolize (kolize 1. řádu, silná odolnost) – výpočetně nemožné systematicky vytvářet dvojice vstupů se stejným otiskem (tj. aby a zároveň )

• další požadavky na HF – Near‐collision resistance • odolnost vůči získání skoro‐kolize – výpočetně obtížné najít x a y tak, aby jen o malý počet bitů

a zároveň

• lokální odolnost vůči získání předlohy


– výpočetně obtížné najít ze znalosti h i jen část x tak, aby

• nekorelovatelnost vstupu a výstupu – nemožné použít statistickou kryptoanalýzu

se liší od

• hash funkce – autor: Ron Rivest • Message Digest – implementováno v PGP

• nedostatečně bezpečná proti útoku s kolizemi

– varianty: • MD2


– 1989, určen pro 8b PC, specifikován v RFC 1319 – kompromitovaná, nepoužívá se

• MD4 – – – –

1990, určen pro 32b PC, specifikován v RFC 1320 kompromitovaná 1995, nepoužívá se, nalezeny kolize 3 kola x 16 kroků = 48 rund výstup = 128b

• hash funkce – varianty:


• MD5 – 1991, specifikován v RFC 1321 – kompromitovaná 1996, ale oblíbená, používá se » srpen 2004 – veřejně známý postup nalezení kolizí – vstup = 512b bloky (poslední doplněn náhodně) » 16 x 32b slova (bloky) » 4 kola (pro každé slovo) x 16 kroků = 64 rund » doplnění: bit 1, bity 0, posledních 64b = původní délka mod 264 – výstup = 128b hash – rozdíly s MD4: » jiné bitové posuny, jiné aditivní konstanty, jiná kompresní funkce » lavinový efekt = připočte výsledek z minulé rundy » zápis čísel dle konvence „little‐endian“

• hash funkce – varianty:


• MD6 – 2008 – výstup = proměnný, max 512b – používá Merkle stromovou strukturu » určena do budoucnosti pro „tisíce“ jader procesoru » odolný proti diferenciální kryptoanalýze – 2008‐2009 » objevena chyba (přetečení vyrovnávací paměti), vydána oprava – nepostoupil do 2.kola soutěže o SHA‐3 » autor stáhnul kandidaturu


MD4 MD5

• hash funkce – autoři: Hans Dobbertin, Antoon Bosselaers, Bart Preneel (Belgie, Leuven) – v rámci evropského projektu RIPE (Belgie)

• RACE Integrity Primitives Evaluation Message Digest – 1996, alternativa k MD4 a MD5

– varianty • RIPEMD‐128 © Květuše Sýkorová

– kompromitovaná 2004, nepoužívá se

• RIPEMD‐160 – obě popsány ve standardu ISO/IEC

• RIPEMD‐256 (bez vyšší bezpečnosti) • RIPEMD‐320 (bez vyšší bezpečnosti)

• rodina hash funkcí – autor: NIST • Secure Hash Algorithm

– varianty • SHA‐0


– 1993, 160b hash, FIPS 180, objevena chyba (jediná bitová rotace) » 16 x 32b slova (bloky), 4 kola x 20 kroků = 80 rund – v rámci projektu SHS (Secure Hash Standard) – kompromitovaná, nepoužívá se, zápis čísel dle konvence „big‐endian“

• SHA‐1 – – – –

1995, 160b hash, SHS, FIPS 180‐1 implementováno v PGP 2005 bezpečnostní nedostatky (matematická nedostatečnost) kompromitovaná, velmi oblíbená

• rodina hash funkcí – varianty • SHA‐2 – 2002, FIPS 180‐2 – základní verze (256b, 512b) + zkrácená verze (224b, 384b) » 32b a 64b slova, posuny, součty » liší se jen v počtu rund, 3x pomalejší


• SHA‐3 – 2007‐2012, FIPS 180‐5 (mělo by obsahovat) – veřejná soutěž, 5 let, návrhy mimo NSA, 64 přihlášených » autoři: Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche (původně známý jako Keccak) – vnitřní struktura odlišná od ostatních SHA » alternativa s piškotovou konstrukcí (sponge structure) » HW implementace rychlejší než ostatní účastníci

• rodina hash funkcí – varianty


• SHA‐4 ??? (nová třída funkcí) – v průběhu soutěže o SHA‐3 » přechod z 32b na 64b PC » ve finále soutěže – algoritmy pomalejší než SHA‐2 – SHA‐512 » pracuje s 64b slovy na 64b PC » dnes nejrychlejší existující standard – úprava SHA‐512/t » SHA‐512/224, SHA‐512/256, SHA‐512/384, SHA‐512/512 » zkrácení na t bitů » FIPS 180‐4

• hash funkce – WHIRLPOOL • považována za bezpečnou

– TIGER • nenalezena dosud kolize

– GRINDAHL


• 2007, jádro AES

– 5 finalistů na SHA‐3: • BLAKE, Skein, Grøstl, JH a Keccak • další zajímavé hash funkce: – CubeHash, ECHO, Fugue, Hamsi, Luffa, Shabal, SHAvite‐3, SIMD, Skein, … – BMW = Blue Midnight Wish, EDON‐R


vá ro ko Sý ětuše Kv

Recommend Documents