Seznámení s kryptoanalýzou

Tomáš Rosa, Ph.D.eBanka, a.s., trosa@ebanka.czhttp://crypto.hyperlink.cz

Osnova přednášky

Současná kryptografie a kryptoanalýza

Základní kryptoanalytické přístupy Příklad kombinovaného útoku Útoky na jednotlivá schémata

Přístup kryptoanalytika

Věříme, že bezpečné schéma existuje. Pokud lze něco prolomit, tak musel

někdo udělat chybu. Chybovat je lidské…

Současná kryptografie

Přístup typu „black-box“ Autonomní, snadno aplikovatelné

moduly. Nízké povědomí až aktivní nezájem o

vnitřní uspořádání. Zřetelný rozdíl mezi „zpravodajským“ a

komerčním pojetím kryptografie. Neznalost až vědomá ignorace

elementárních principů. Chybí použitelný standard kvality.

Současná kryptoanalýza

Překvapivé útoky v neočekávaných místech systému Obvykle velmi efektivní a těžko odhalitelné

postupy. Postranní kanály

Podcenění fyzikálních projevů zařízení. Přískoky vědy

Podcenění heuristické povahy kryptografie. Sociální techniky

Podcenění lidského faktoru.

Postranní kanál

Každý nežádoucí způsob výměny informací mezi kryptografickým modulem a jeho okolím. Časový Napěťově - proudový Elektromagnetický Chybový Kleptografický

Postranní kanál

Ilustrace úniku informací postranním kanálem

Hammingova vzdálenost datových bloků přesouvaných vybranou instrukcí analyzovaného kódu.

Jiná ilustrace – chybový kanál

ClientKeyExchangeRSA, FinishedC = [(premaster-secret)]e mod N

server

computation:P Cd mod Npremaster-secret -1(P)if (exception in -1) premaster-secret RND(48) else if(bad version of premaster-secret) “Alert-version”

Finished/Alert

clients

Chybový postranní kanál

Kryptoanalýza dříve

Analytik měl k dispozici zachycený šifrový text.

V lepším případě měl i popis použité metody.

Kryptoanalýza nyní

Analytik komunikuje přímo s napadeným systémem - dává mu povolené příkazy.

Útok připomíná herní partii – výhrou analytika je prolomení systému.

Přískoky vědy

Prokazatelná bezpečnost je zatím iluzí. Myslíme si, že systém je tak

bezpečný, jak složitý je problém, o kterém si myslíme, že je neschůdný.

Místo myslíme si zde ovšem má být umíme dokázat.

Oslabení ze dne na den…

…bychom měli očekávat u každého algoritmu.

Realita je ovšem zcela jiná: Aplikace nejsou technicky schopny

přejít rychle na jiný algoritmus. Některé to nedokážou vůbec.

Změna algoritmu není procesně podchycena (krizové scénáře, atp.).

Sociální inženýrství (SI)

Zneužíváno jako platforma pro velmi efektivní útoky.

Útoky založeny na slabinách ve vzorcích běžného lidského chování. Zmatení uživatelů podvrženými

informacemi. Predikovatelnost reakcí skupiny

uživatelů na definované vnější podněty.

Kryptoanalýza je silná zbraň

Moderní útoky kombinují:A. Elementární matematické slabiny

Původně složitý problém může mít překvapivě snadné řešení.

B. Zranitelnosti chybné implementace - zejména postranní kanály

• Napadený modul pracuje sám proti sobě.

C. Slabiny lidského faktoru Zmatený uživatel sám spolupracuje s

útočníkem.

Příklad útoku 1/4

1. Útočník zachytí šifrovanou zprávu určenou jeho oběti.

• Máme na mysli standardní e-mailovou korespondenci dle S/MIME verze 3 (RFC 2633) s využitím kryptografických struktur podle CMS (RFC 3369).

Příklad útoku 2/4

2. Útočník předstírá, že své oběti sám zasílá šifrovanou zprávu.

• Ve skutečnosti se jedná o derivát zachycené tajné zprávy, kterou chce útočník vyluštit.

• Využíváme kombinaci přístupů A (vlastnosti šifrovacího modu) a B (nedostatečná kontrola integrity v poštovním programu).

Příklad útoku 3/4

3. Oběť přijatou zprávu odšifruje, ale vidí nesmyslný text.

• Útočník svou oběť přesvědčí, aby mu nesmyslný text zaslala. Tvrdí například, že hledá chybu ve svém systému, nebo předstírá, že oběti nevěří, že text nedává smysl.

• Oběť se nechá nachytat, protože text vypadá nezávadně.

• Využíváme přístup C (oklamání lidského faktoru).

Příklad útoku 4/4

4. Útočník přijme „nesmyslný“ text od oběti, odstraní vliv maskovací transformace, kterou předtím použil, a získá otevřený text původní zprávy.

• Využíváme přístup A (vlastnosti šifrovacího modu).

Plán útoku - ilustrace

Původní odesilatel

Původní příjemce

1

2 3

4 Útočník

Praxe: Útočník modifikuje bloky šifrového textu

Praxe: Oběť se snaží zprávu odšifrovat

Praxe: Oběť vrací útočníkovi „neškodný nesmyslný“ text

Praxe: Útočník vyluštil, co chtěl

Modus CBC

mi-1 mi mi+1

ci-2 ci-1 ci ci+1

E

+

+

D

mi-1 mi mi+1

+

E

+

E

D

+

D

+

Princip maskování

ci-1 ci ci+1

+

D

miwi

D

+

ci-1wi

+

D

+

D

i

ciwi+1

mi+1wi+1i+1

CT’ = IV w1, c1, c1 w2, c2, c2 w3, …, cn-1 wn, cn

RSA – praktické útoky

Připomeňme: šifrovací transformace: (me mod N) = c, odšifrovací transformace: (cd mod N) =

m. Základní kryptoanalytické úlohy:

inverze šifrovací transformace, nalezení soukromého klíče (N, d).

RSA – inverze ŠT

Meet-in-the-middle pro krátké zprávy bez formátování.

Orákulum parciální informace o otevřeném textu m: přímé – individuální bity, potvrzovací – správnost formátu, aj.

Chyby při šifrování – narušení e, aj.

RSA – soukromý klíč

Chybové útoky, hlavně na RSA-CRT.

Připomeňme si podpis zprávy m:1. s1 = md_p mod p

2. s2 = md_q mod q

3. h = (s1 – s2)qinv mod p

4. s = s2 + hq (= md mod N)

DSA – praktické útoky

Připomeňme: podpis:

r = (gk mod p) mod q, s = (h(m) + xr)k-1 mod q, podpisem je dvojice (r, s), k je tajné číslo, tzv. NONCE, x je soukromý klíč.

DSA – praktické útoky

Základní kryptoanalytické úlohy: útok na nepopiratelnost – padělání

podpisu, kolize, nalezení soukromého klíče.

DSA - kolize

Kolize hašovací funkce. Kolize ve vzorci pro s:

ať q | h(m1) – h(m2), potom s = (h(m1) + xr)k-1 mod q =

= (h(m2) + xr)k-1 mod q.

DSA – soukromý klíč

Velmi citlivým místem je NONCE k. Závislosti mezi jednotlivými NONCE. Parciální informace o NONCE.

Chybové útoky změnou veřejných parametrů.

Závěr

Vedle aplikované kryptografie existuje aplikovaná kryptoanalýza.

Kryptografické algoritmy nejsou nedotknutelné – mohou být napadeny a prolomeny.

Návrh bezpečnostních modulů by měl tyto skutečnosti reflektovat.

Zdroje Obecně

http://crypto.hyperlink.cz/cryptoprax.htm Menezes, A. J., van Oorschot, P. C. and Vanstone, S. A.:

Handbook of Applied Cryptography, CRC Press, 1996 http://www.cacr.math.uwaterloo.ca/hac/