Strokovne razpravf
Napadi na kriptografske sisteme
Matej Salamo». Tomaž Oogša Fakulleta za elektrotehniko, računalništvo in informatiko Univerza v Mariboru, Smetanova 17, 2000 Maribor ma tej.sala mon®uni-rribisj
Izvleček
V prispevku smo predstavili najpogostejše vrste kriptografskih napadov na simetrične in asimetrične kriptografske sisteme. Mor vrste napada je odvisen od napadalcu razpoložljivih sestavnih delov kriptografskega sistema ter drugih informacij.
Primerjati smo odpornost simetričnih in asimetričnih kriptografskih sistemov, glede na dolžino uporabljenega ključa, obširneje pa smo predstavili napad z grobo silo. Navedli smo povprečni čas, ki ga posamezni napadalec ati skupine potrebujejo za preiskavo polovice vseh možnih ključev. V najslabšem primeru je lahko povprečni čas dvakrat daljši. Opisali smo tudi napad na kriptografski sistem DES, v katerega je bilo leta 1999 z distribuiranim iskanjem tainega ključa vlomljeno v rekordno hitrem času,
Abstract
Attacks against Cryptographic Systems
In this article we describe most frequently used crypto attacks against conventional or symmetric and public-key or asymmetric cryptographic systems. Type of attack selection depends on availability of cryptographic system components and other information to attacker.
Resistance of symmetric and asymmetric cryptographic systems is compared due to used key length. Brute force attack is circumstantially presented and average time needed to search half of the symmetric key-space is stated. Worst-case scenario could be twice as long.
tVe also describe a year 1999 attack against DES. in which cipher was broken in record time using distributed key search.
1. Uvod
Zagotavljanje tajnosti podatkov je zopet postalo aktualno. ko so se po Internetu začela pošiljati zaupna sporočila. Vsako poslovanje prek Interneta zahteva tajnost, celovitost in avtentičnost sporočil. Internet omogoča zelo hiter prenos velikega števila sporočil, vendar tudi zelo enostavno prestrezanje sporočil. Kot odgovor na ta problem so nastali razni širfirni in deši-frirni sistemi, ki jim pravimo tudi kriptografski sistemi. Njihova osnovna naloga je zagotavljanje tajnosti pre-našanega sporočila. Z določenimi dodatnimi postopki lahko zagotovimo tudi celovitost in avtentičnost sporočil ter preprečitev utaje avtorstva in sprejema sporočila. Nepooblaščeno osebo, ki se želi dokopati do vsebine sporočila ali ga spremeniti, bomo poimenovali napadalec. Prva naloga napadalca je, da se dokoplje do sporočila. Če je le-to šifrirano, potem ima na razpolago dve možnosti. Prva je, da z analizo šifri-ranega sporočila razvozla vsebino. Temu postopku pravimo kriptoanaliza. Drug pristop je kraja ključa, s katerim lahko sporočilo dešifrira.
Pri kriptoanalizi nastopata dve konfliktni zahtevi; Prva je ta, da naj bodo kriptografski sistemi čini bolj vami, čim cenejši in vsakomur1 d os l o piti. Mnogo ljudi si želi popolno tajnost poslanih sporočil. Organizacije, ki se borijo proti kriminalu in protiobveščevalne
organizacije pa tega vedno ne želijo, saj dobri kriptografski sistemi otežujejo njihovo delo. Te dileme ne bomo obravnavali v tem prispevku, ampak se bomo posvetili predvsem opisu raznih vrst napadov na kriptografske sisteme. Najprej bodo na kratko opisane liste lastnosti kriptografskih sistemov, ki jih bomo v nadaljevanju potrebovali (podrobnejši opis glej v (PaveŠič 1997). Obravnavane bodo splošne značilnosti napadov in primerjava med kriptografskimi sistemi glede njihove varnosti. Nato bo sledil kratek opis najpogostejših napadov.
2. Kriptografski sistemi
Kadar želimo zagotoviti zasebnost nekega sporočila, ga moramo pretvoriti v nerazumljivo obliko kar pomeni, da ga moramo šifrirali. Sporočilo mora biti šifri rano tako, da ga zna dešitrirati samo listi, ki mu je sporočilo namenjeno, vsem ostalim pa mora bili njegova vsebina nerazumljiva. Sisteme, ki omogočajo šifriranje in dešifriranje sporočil, imenujemo kriptografski sistemi.
Pri šifriranju gre za transformacijo odprtega spnrnaln v nerazumljivo šifrirana sporočilo ali lajnopis. Tovrstna transformacija, ki se običajno izvaja kar z računalnikom,
fif*>«i/ip «INFORMATIKA
2001 številka 3 - letnik IX
Matey ¿s/amo/i, Tomaž Dogša: Napuili na kriptografske sisteme
poteka v skladu s tmtisfornmctjskbiu tabelami ali šifrirnih mi algoritmi. Šifrirni postopek mora biti reverzibilen, siij je le v tem primeru tajnopis mogoče dešifrirati, to je pretvoriti nazaj v originalno odprto sporočilo.
Šifriranje in dešifriranje vhodnega sporočila poteka rta osnovi ključa, ki mora biti tajen kar pomeni, da ga sme poznali samo pošiljatelj sporočila in tisti, ki mu je sporočilo namenjeno. Ključ, ki mora biti povsem neodvisen od odprtega sporočila, tvorijo izbrane vrednosti parametrov šifrirnega in dešifrirnega algoritma. Če za šifriranje in deŠifriranje uporabljamo enak ključ, potem takemu sistemu pravimo simetričen kriptografski sistemi Pri asimetričnih sistemih2 imamo poseben ključža šifriranje, ki je javen, ke s privatnim ključem lahko tajnopis de šifri ramo. Glede na dolžino podatkov, ki jih v algoritmu obdelujemo, ločimo tokovne in blokovne šifrirne sisteme. Pri tokovnih se odprta sporočila šifrirajo po bitih, pri blokovnih pa se sporočilo razdeli na več velikih blokov3, ki se nato šifrirajo.
3. Splošne značilnosti napadov na informacijski kanal in na sporočila
Eden izmed pogostih napadov na informacijski kanal je onesposobitev prenosnega medija. To lahko dosežemo s fizičnim (blokiranje voda) ali programskim posegom (blokiranje strežnika). V določenih primerih je mogoče tudi prisluškovati ali spreminjati lastnosti informacijskega kanala (npr. povzročitev prekomerne obremenitve). Če pri napadu ostane sporočilo nespremenjeno, potem gre za pasiven napad. Med pasivne napade štejemo prisluškovanje (prestrezanje) in analizo prometa sporočil:
■	Prisluškovanje: I o je direkten napad na zasebnost, ki je izvedljiv, če ima napadalec dostop do informacijskega kanala. Ce prisluškovanja fizično ni mogoče preprečiti, potem moramo sporočila ustrezno šifrirati.
■	Analiza prometa: Napadalec skuša z analizo prometa in z analizo značilnosti sporočil ugotoviti določene podatke o pošiljatelju in prejemniku (npr. identiteto).
Ker pri pasivnih napadih običajno ne ostane nobena sled /a napadalcem, je tak napad težko opaziti. Zelo enostavna in popolnoma neopazna sta prisluškovanje in analiza prometa v mejah lokalnega omrežja. Za napad na sporočila, ki se prenašajo po drugih omrežjih, je treba najprej vdreti v enega izmed strežnikov, ki so vključeni v določeno lokalno omrežje.
Aktivni napadi povzročajo modifikacijo sporočila (podatkovnega toka) ali pa ustvarjajo lažno sporočilo (podatkovni tok). Ker gre za spremenjena sporočila, lahko zaznamo prisotnost aktivnih napadov. Razdelimo jih v tri kategorije:
■	Spreminjanje: gre za napad na celovitost sporočila, zaradi katerega je lahko sporočilo spremenjeno ali zakasnjeno. Primer takšnega napada je sporočilo "Dovoli Maji, da dostopa do bančnega računa" spremenjeno v "Dovoli Branku, da dostopa do bančnega računa".
■	Ponovno pošiljanje: napadalec prekopira sporočilo in ga kasneje (ob neprimernem času) ponovno pošlje (npr. naročilo za nakup delnic, ukaz za umik brigade).
■	Spreminjanje lastnosti informacijskega kanala:
napadalec v celoti preprečuje, spreminja ali ovira normalno komuniciranje. Npr. napadalec zaustavi vsa sporočila namenjena določenemu cilju. Drugi primer je prekomerna obremenitev omrežja s sporočili, kar privede do njegovega zloma. m Pretvarjanje: napadalec se pretvarja za pooblaščeni) osebo in i/.koriŠča njene privilegije. Primer pretvarjanja je zajetje gesla, s katerim se napadalec lažno identificira in s tem pridobi določene privilegije.
4. Napadi in vdori v kriptografski sistem
Kakor hitro je iz tajnopisa mogoče izločiti originalno, odprto sporočilo, govorimo o vdoru v kriptografski sistem. Vdor je posledica uspešnega kfiptoanalitične-ga napada ali pa kraje ključa. V splošnem je odpornost kriptografskega sistema odvisna od vrste napada, njegov izbor pa od: zasnove šifrirnega sistema, ključa (dolžine ključa, njegovega distribuiranja) in napadalcu razpoložljivih informacij. Odpornost kriptografskih sistemov lahko z vidika napadalca predstavimo s količino napora, ki ga je treba vložiti za vdora.
Pred napadom mora napadalec oceniti ali je izbrani sistem sploh smiselno napasti in kakšna je najprimernejša vrsta napada. Kriptografski sistem je računsko vun'u (Staliings 1999), če so stroški vdora (desifriran-ja) večji od koristi deši tri ranega sporočila. Ker vrednost sporočila s časom pada, mora napadalec oceniti tudi Čas, potreben za vdor.
temelj varnosti vsakega kriptografskega sistema je ustrezen algoritem. Kljub temu, da je odpornost algoritma možno oceniti, se pogosto izkaže, da je dejanska odpornost nižja od ocenjene. Vzrok /a zmanjšanje
1	Tipičen predstavnik simetričnih Kriptografskih sistemov je sistem UES (Data Fncryption Standard).
2	Najtioli znan asimetrični kriptografski sistem /e sistem HSA, poimenovan po svojih avtorjih (Ronalct R¡vest, Adi Shamlr, Leonard Acllemaiv.
3	64 in več hlma beseda.
2001 ■ Stevrlka 3 ■ letnih IX
i >n ih «HNFORMATIKA
Matey ¿s/amo/i, Tomaž Dogša: Napuili na kriptografske sisteme
odpornosti je v raznih napakah, ki so nastale pri implementaciji. Posledice napak se kažejo v raznih hibah programske in strojne opreme. Poznavanje teh hib lahko zelo zmanjša varnost kriptografskega sistema. Prisotnost hib ugotavljamo z raznimi postopki preverjanja (npr. testiranje, formalno dokazovanje, itd.) (Dogša 1993). Ker bo stroški testiranja zelo visoki, je zelo malo kriptografskih sistemov, ki bi bili izredno dobro preverjeni. Problem visokih stroškov testiranja izdelovalci kriptografskih sistemov rešujejo z distri-buiranim testiranjem, V javnosti objavijo nekaj tipičnih informacij, ki so običajno napadalen znane (npr. tajnopis, del odprtega sporočila in šifrirni algoritem4 ) in nato razpišejo visoko nagrado za vdor5. Pogosto mora napadalec tudi pojasniti svojo metodo, če želi prejeti nagrado. Z odpravljanjem najdenih napak, se veča varnost kriptografskega sistema. Mnogi so mnenja, da so zadovoljivo preverjeni le sistemi, ki so bili podvrženi distribuiranemu testiranju.
Tabela I prikazuje zanimivo primerjavo med odpornostjo simetričnih in asimetričnih kriptografskih sistemov, glede na dolžino uporabljenega ključa. Vidimo lahko, da je potreben za enako odpornost za simetrične šifrirne sisteme bistveno krajši ključ kot za asimetrične.
Vsaka informacija o kriptografskem sistemu in sporočilu pomaga napadalcu. Vrsta napada je odvisna od količine in vrste napadalcu razpoložljivih sporočil, njegovega znanja in računalniške podpore. Napadalcu lahko pomagajo zlasti naslednje informacije: vrsta algoritma, vsebina sporočila, vrsta
Simetrični šifrirni sistem	ASIMETRIČNI šifrirni sistem RSA ECC (Elliptic Curve Crypt o system)	
40 bitov	274 bitov	57 bitov
56 bitov	384 bitov	80 bitov
64 bitov	512 bitov	106 bitov
80 bitov	768 bitov	132 bitov
96 hitov	1024 bitov	160 bitov
112 bitov	1792 bitov	185 bitov
120 bitov	2048 bitov	211 bitov
128 bitov	2304 bitov	237 bitov
Ta bet .i 1:
Primerjava meti dolžinami hljučev potrebnih za enako stopnjo odpornosti v simetričnih in asimetričnih sistemih (Moscaritolo 1999).
sporočila (besedilo, slika, program itd.), jezik, v katerem je napisano sporočilo, statistične lastnosti jezika. S prikrivanjem teh informacij lahko dvigujemo varnost kriptografskega sistema. Napadalcu pri napadu koristita poznavanje določenih informacij in posedovanje sestavnih delov ali celotnega kriptografskega sistema:
■	skrival ni algoritem: napadalec sumi, da je v množici sporočil skrtt'1 tudi tajnopis. Npr. v eni izmed 10t) slik je skrito sporočilo. Brez poznavanja skriva ¡nega algoritma napadalec ne more odkriti skritega sporočila, ki je lahko odprto ali šifrirano (Johnson, Jajodia 1998).
■	en tajnopis: napadalec ima na razpolago samo tajnopis brez pripadajočega odprtega sporočila. Napadi, ki temeljijo samo na enem tajnopisu, so zelo redko uspešni, Eden izmed napadov, ki ga je možno izvesti tudi /. delom tajnopisa, je napad / grobo silo7, pri katerem napadalec poskuša vdreti sistematično - s preskušanjem vseh možnih ključev.
■	segmente odprtega sporočila in pripadajoče tajno* pise. Npr. v razpisu za napad na kriptografski sistem DF.S je bil znan tajnopis in začetek sporočila. Tudi v tem primeru je možno uporabiti napad z grobo silo.
m šifrirni sistem, s katerim lahko napadalec generira lajnopise, vendar ne pozna ključa, ker je le-ta npr. vgrajen v sistem. Napadalec lahko tvori poljubno število odprtih sporočil in tajnopisov in uporabi diferencialno analizo, kjer s premišljeno izbranimi sporočili8 sklepa o pravilnosti ključa.
■	končno število tajnopisov in dešifrirni sistem, Vendar ne pozna ključa. Na podlagi analize tajno-pisa in de šifrira nega sporočila sklepa o uspešnosti napada. Napadi s tovrstnimi informacijami so običajni /.a asimetrične kriptografske sisteme.
m celotni kriptografski sistem, vendar ne pozna tajnega ključa. Napad lahko izvede s pomočjo izbranih odprtih sporočil in pripadajočih tajnopisov, ima pa tudi možnost izbire tajnopisov in pri padajočih desifriranih sporočil. Na osnovi lega sklepa o pravilnosti izbranega ključa. I'a primer zelo redko nastopa.
V navedenih kategorijah količina informacij, katere napadalec pozna, narašča. Če napadalec uspe vdreti les poznavanjem samo enega tajnopisa, potem velja, da je kriptografski sistem slab. Za vdor v večino dobrih šifrirnih sistemov je potrebnih več informacij.
4	Izvršljivo kodo.
5	Primer. poziv, h ga je razpisal laboratorij RSA za napad na kriptografski sistem OCS ■ DES Challenge III: /itlp://wwi4ri;rsa,com/rsn/ai)s/(Jes3/
6	Veda, Hi se ukvarja metodo skrivanja podatkov, se imenuje steganografija.
7	An0.: ijrute tone attacA - exhaustive search.
H	Sorodna sporočila ? določenimi razpoznavnimi vzorci.
i iponiln «(INFORMATIKA
2001 številka 3-letnik tX
Matey ¿s/amo/i, Tomaž Dogša: Napuili na kriptografske sisteme
Kriptografski napadi se delijo (slika I) glede na strukturo kriptografskega sistema, napadalcu razpoložljivih informacij in sestavnih delov kriptografskega sistema.
4.1 Najpomembnejši napadi na blokovne simetrične kriptografske sisteme
Za blokovne kriptografske sisteme je značilno, da šifrirajo naenkrat velik blok podatkov. Takšen princip varuje pred različnimi statističnimi analizami, s pomočjo katerih je mogoče sklepati o vrsti odprtega sporočila in informacijah, ki jih vsebuje. Kljub temu pa obstaja nekaj vrst napadov, ki so pri tovrstnih kriptografskih sistemih lahko zelo uspešni.
4.1.1 Napad z ¿robo silo - obširno iskanje tajnega ključa
Obširno iskanje ključa, znano kot napad /. grobo silo, je najpreprostejša kriptoanalitična tehnika, ki omogoča identifikacijo pravilnega tajnega ključa na osnovi poskusov /. vsemi možnimi ključi. Pogoj za izvedbo tega napada je, da napadalec pozna:
■	majhen tlel odprtega sporočila in pripadajoči tajnopis ali
■	samo tajnopis, pri čemer mora imeti odprto sporočilo določene prepoznavne karakteristike. Sam postopek je sestavljen samo iz treh korakov:
izbor ključa, poskusno dešifriranje in ugotavljanje uspešnosti. Prva dva koraka je možno enostavno av-
tomatizirati, medtem ko lahko tretji v nekaterih prim erih pomeni velik problem. Uspešnost, to je pravilnost ključa se kaže v tem, da je dešifrirano sporočilo smiselno. Če je znan vsaj del odprtega sporočila, potem je ugotavljanje ključa zelo hitro in enostavno. V kolikor napadalec dela odprtega sporočila ne pozna, lahko o njem ugiba, npr. mnogi dopisi se začnejo s »Spoštovani«. Ce nima nobenih podatkov o sporočilu, je ugotavljanje uspešnosti ključa naj dolgotrajnejši korak. Ce ne pozna niti jezika, v katerem je napisano sporočilo, ali če gre za digitalno sliko, potem je napad z grobo silo največkrat neuspešen.
Napad /. grobo silo je mogoče izvesti s strojno ali programsko opremo. Primeren je za odkrivanje tajnih ključev konstantne dolžine v simetričnih in asimetričnih kriptografskih sistemih. Ker je zelo obširen, zahteva ogromno časa in uporabo izjemno hitrih računalnikov. Na pati na DHS s 56-bitnim ključem hi namreč kljub uporabi danes najhitrejšega računalnika lahko trajal več sto let. Večjo računalniško moč je možno doseči z distribuirano kriptoanalizo. Iskanje ključa je razdeljeno na večje število računalnikov, ki so povezani v mrežo. Pri d is l ritmi ranem iskanju kjijuča vsak računalnik obravnava le del množice možnih ključev.
Tabela 2 prikazuje povprečni čas, potreben za vdor v simetričen kriptografski sistem. Uporabljena sta dva parametra: velikost ključa in hitrost preizkušanja. Če je hitrost 1 ključ/ms, pomeni, da mora računalnik v eni
KRIPTOGRTAFSKI NAPADI
SNka 1: Vrste kriptografskih napadov.
2001 številka .1 ■ It'lnik IX
iiyotabiuA NFORM AT IKA
Matej ¿olomoo, Tomaž Dogéa. Napadi na kriptografske sisLomn
		Čas za preiskavo polovice vseh možnih ključev	
Velikost ključa	Število vseh možnih ključev	Hitrost dekodiranja: 1 kijUČ/MS	Hitrost dekodiranja: 10' ključev/j.is
32 bitov	232 = 4.3 -10 9	23Vs = 35.8min	2.15 ms
56 bitov	2 56 = 7.2 • 10 16	2 55 {.iS = 1142 let	10.01 ur
128 bitov	2128 — 3.4 • 1038	2lz?(.iS = 5.4'102" let	5.4 -1010 lat
Tabela 2: Povprečni čas potreben za napad z grobo silo pri dveh različnih hitrostih iskanja (Staltings 1999}.
mikrosekundi generirati ključ, izvesti poskusno deši-i oranje in ugotoviti uspešnost ključa. Tabela 3 prikazuje povprečni čas, ki ga potrebujejo posamezni napadalec ali skupine za preiskavo polovice vseh možnih ključev, V najslabšem primeru se seveda ti časi podvojijo.
Tabela 3 temelji na predpostavkah iz. leta 1997: a posamezni na padalec: samostojen računalnik z ustrezno programsko opremo. Hitrost iskanja; 217-2M ključev/sekundo.
■	majhna skupina: 16 računalnikov z ustrezno programsko opremo. Hitrost iskanja: 22l-22A ključev/ sekundo.
■	akademske omrežje: 256 računalnikov z ustrezno programsko opremo. Hitrost iskanja: 22r,-2~M ključev/sekundo.
■	velike organizacije: strojna oprema v okviru 1.000,000 USD. Hitrost iskanja: 243 ključev/sekundo.
■	vojaške agencije: strojna oprema z najnovejšo tehnologijo v okviru 1,000.000,11(10 USD. Hitrost iskanja: 2 ključev/sekundo.
19. januarja 1999 je neprofitni organizaciji Distribtt-
ted.nei, skupaj z ustanovo RFF (Electronic Frontier
Foundation), s posebnim superračunalnikom in s
približno 100.000 osebnimi računalniki povezanih prek Interneta, uspelo postaviti hitrostni rekord v odkrivanju 56-bitnega DES-ovega ključa. Znan je bil tajnopis in začetek odprtega sporočila "See you in Rome (second /t ES Conference, March 22-23, ¡999)". Med 72>057,594,037,927,936 možnimi ključi jim je / akcijo DES III Deep Crack uspelo odkriti pravega v 22 urah in 15 minutah. SuperraČunalnik so z;gradlli na osnovi strogo namenskega čipa AW I -4500 Deep Crack, ki ga je izdelala firma AVVT (Advanced Wireless Techifiolo-gies). Čip se sestoji iz 24. identičnih iskalnih enol", ki delujejo z uro frekvence 40MH/ in zmore testirati 60 milijonov ključev na sekundo (Kocher 1998), 64 takšnih čipov sestavlja, skupaj z ustrezno logiko za upravljanje, posebno matično ploščo. 29 taksnih plošč predstavlja šest računalnikov, ki skupaj s krmilnim Pt računalnikom (operacijski sistem Linux) tvorijo super-računalnik. Iskanje ključa poteka torej z več kot 1800 čipi AWT-4500, hitrost iskanja superračunalnika pa znaša 90 bilijonov ključev na sekundo.
Očitno je torej, da DFS ponuja le nekaj urno zaščito ob predpostavki, da je napadalcu znan del odprtega sporočila. Glede na rast procesne moči računalnikov lahko rečemo, da postaja DES na obravnavano vrsto napada vse manj odporen.
9 Angl, searc/i unit,.
Dolžina ključa	Posameznik	Majhna	Akademsko	Velike	Vojaške
	napadalec	skupina	omrežje	organizacije	agencije
40 bitov	tedni	dnevi	ure	milisekunde	mikrosekunde
56 hitov	stoletja	desetletja	leta	ure	sekunde
64 bitov	tišočletja	stoletja	desetletja	dnevi	minute
80 bitov	nemogočo	nemogoče	nemogoče	stoletja	stoletja
128 hitov	nemogoče	nemogoče	nemogoče	nemogoče	tisočletja
Tabefa 3: Povprečni čas, ki ga porabi posameznik ali skupina za preiskavo polovice vseli možnih ključev (Moscaritoto 1999).
iiptmtlniiANFORM ATIKA	2001 - Številka 3 - letnik IX
Matey ¿s/amo/i, Tomaž Dogša: Napuili na kriptografske sisteme
4.1.2	Diferencialna kriptoanaliza
Gre za zahteven in kompleksen napad, pri katerem ima napadalec Šifrirni sistem, vendar ne pozna ključa (Ritter 20(11). Šifrirni sistem napade tako, da izbira dve sorodni odprti sporočili in analizira dobljena tajno-pisa. Pri tem pričakuje, da bo tudi v pripadajočih tajnopisih mogoče zasledili podobnost, na osnovi katere bi lahko sklepal o ključu. S skrbno iterativno analizo dobljenih podatkov določi verjetnosti možnih ključev. V najbolj verjetnim poskusi dešifrirati enega izmed tajnopisov.
4.1.3	Linearna kriptoanaliza
To je napad, pri katerem napadalec razpolaga z odprtimi sporočili, ki jili sam ne more poljubno izbirati, ter pripadajočimi tajnopisi (Ritter 2001). Do posameznih informacij o ključu pride na osnovi zadostnega Števila parov odprtih sporočil in pripadajočih tajnopisov. Večje število takšnih parov poveča verjetnost uspešnega napada. I .inearna kriptoanaliza sistema DES poteka tako, da poskuša napadalec na osnovi razpoložljivih parov vzpostaviti statistično linearno povezavo med vhodnimi in izhodnimi hiti posamezne S-škalle"1.
Elementi diferencialne in linearne kriptoaiialize so združeni v novi obliki napada, imenovani difercncinl-nn-linenntp kriptnnrittliin*1.
4.1.4	Napad s pomočjo šibkih ključev
Znano je, da je varnost nekaterih kriptografskih sistemov odvisna tudi od vrednosti izbranega ključa. Pri nekaterih Vrednostih se kriptografski sistem odzove z določenim pravilnim obnašanjem, ki lahko olajša vdor. Takim ključen pravimo .šibki ključi, Odkritje šibkih ključev je zanimivo za načrtovalce kriptografskega sistema, saj lahko preprečijo, da bi si jih uporabnik izbral.
Za sistem DES so bili odkriti štirje šibki ključi (RSA Laboratories 1998). Njihov slučajni izbor povzroči enakost med šifrirnim in dešifrirnim postopkom, kar pomeni, da je rezultat dvakratnega zapovrstnega šifriranja odprtega sporočila z enim od takšnih ključev kar originalno odprto sporočilo. Verjetnost izbora takega ključa je zelo majhna (2 '-). Pri algoritmu 1DEA lahko zasledimo cel razred ključev, ki kriptoanalizo zelo olajšajo (RSA i aboratories 1998).
4.1.5	Algebraični napadi
t o je skupina tehnik, ki so uspešne v blokovnih kriptografskih sistemih, za katere je v algoritmu določena značilna matematična struktura. Algebraični napad je
lahko zelo uspešen v primeru kriptografskega sistema, ki ga je mogoče razdeliti na posamezne pod strukture, Napadalec napada posamezno podstrukfcuro in na ta način poskuša vdreti v celotni sistem. Pojavi pa se vprašanje, ali je neki šifrirni sistem sploh mogoče predstaviti s podstrukturami. Za DES je znano, da to ni mogoče.
4.1.6 Napad s knjigo kod1
Napadalec zbira odprta sporočila s pripadajočimi tajnopisi, tvorjenimi z istim ključem. Ko zasledi tajno-pis, ki ga ima v svoji knjigi kod, odkrije njemu pripadajoče odprtO sporočilo. Tovrstni napad je primeren za napad na blokovne Šifrirne sisteme, saj je le v tem primeru mogoče kontrolirati njegovo kompleksnost, ki zavisi od velikosti uporabljenih blokov in s tem števila elementov v knjigi kod.
4.2 Najpomembnejši napadi na tokovne simetrične kriptografske sisteme
Najobičajnejša varianta šifriranja s tokovnim kriptografskim sistemom je kombinacija tokovnega ključa1 in odprtega sporočila. Tokovni ključ se generira na osnovi tajnega ključa. To je naključna sekvenca bitov, ki se na bitnem nivoju kombinira" z biti odprtega sporočila. Večina napadov na tovrstne sisteme jem/ hOc, sicer pa so znani (RSA Laboratories 1998, 1995): korelacijski napad, napad na periodo tokovnega ključa, napad z linearnim pomičnim registrom s povratno zanko1', deli in premagaj.
4.2.1	Korelacijski napad
Tokovni ključ mora izkazovati naključnost, kar pomeni, da kljub njegovemu podaljševanju napadalec ne more priti do dodatnih informacij, ki hi mu omogočile predvideti posamezne bite v naključni sekvenci - ge-neriranem tajnopisu. Varen in zanesljiv tokovni šifrirni sistem mora prenesti številne statistične teste, s pomočjo katerih se ocenjuje več parametrov. Eden izmed njih je frekvenca pojavljanja posameznih hitov ali zaporednih bitnih vzorcev. Prav ti testi so osnova za t.i. korelacijski itapivl, pri katerem napadalec preverja korelaeijo med bitno sekveneo v izbranem časovnem intervalu ter sekvencami izven njega. Na tej osnovi poskuša odkriti celoten tokovni ključ.
4.2.2	Napad na periodo tokovnega ključa
Tokovni ključ ima lahko tudi strukturne slabosti. Najbolj očitna je perioda tokovnega ključu. Gre za primere,
lOAng. S-bax-gre za lafeto, s pomočjo katerih se izvaja šifriranje v sistemu DES,
11	Aiigl. aifferential-linearcfyptoa(\č)lysis.
12	Angf. voilehook attack.
13	Ang!.keystreani.
14	Običajno se izvaja logična operacija XOR
15	Angf. linenr leedback shift register.
2001 številka 3 letnik IX
li/AirtifiriHlNFORM&TIKA
Matej éalamon, Toma? Dogšn: Napadi na kriptografske sisteme
pri katerih prihaja do prehitrih ponovitev določenega število bitov v tokovnem ključu. Razlog za to je prekratek tokovni ključ. Napadalec poskuša odkriti določen del tokovnega ključa - periodo, ki bi mu omogočil dešifrirati določene dele tajnopisa. Tovrstni napad Opozarja, da je pri načrtovanju tokovnih Šifrirnih sistemov treba paziti na minimalno periodo tokovnega ključa ali izbrati ustrezno vrednost njene spodnje meje.
4.2.3	Napad z linearnim pomičnim registrom s povratno zanko
Določene strukturne slabosti so lahko eelo tako velike, da ponujajo napadalcu možnosti iskanja alternativnih poti za generiranje dela tokovnega ključa ali tokovnega ključa v celoti. Vodilni tovrstni pristop, ki omogoča reprodukcijo {izdelavo kopij) tokovnih ključev, je uporaba linearnega pomičnega registra s povratno zankn. Ta deluje tako, da na svojem vhodu prebere končno sekveneo bitov, na izhodu pa to sekvenco ponovno generira. Pri tem je pomembna dolžina registra, od katere zavisi dolžina prebrane ter kasneje ponovno generiranesekvence.
Varnost šifrirnega sistema se meri na osnovi line arite kompleksnosti sekvence, ki je določena z velikostjo linearnega pomičnega registra s povratno zanko, potrebnega za reprodukcijo te isle sekvence. Tokovni šifrirni sistem mora imeti torej čim večjo linearno kompleksnost.
4.2.4	Deli in premagaj
Razen iskanja ključa s pomočjo napada /, grobo silo je znan tudi razred napadov, ki jih lahko opišemo z izrazom tlel i in preiiiagaj]b V primeru tokovnih Šifrirnih sistemov gre /a napad na tokovni ključ, ki se generira na osnovi izbranega tajnega ključa. Napadalec uspe zajeti del tokovnega ključa in na osnovi lega prične z ugotavljanjem celotnega tajnega ključa. Z grobo silo napada posamezne dele tajnega ključa, pri čemer poskuša identificirati listi del, ki ima zelo očiten in neposreden učinek na generiran tokovni ključ. Napad je tem uspešnejši, čim bolj se napadalcev tokovni ključ ujema z dejansko prisotnim tokovnim ključem. Rezultati napada ilcti m premaguj so lahko v pomoč tudi pri izvajanju zelo hitrih in učinkovitih korelacijskih napadov.
4.3 Najpomembnejši napadi na asimetrične kriptografske sisteme
Nekateri najpomembnejši napadi na asimetrične kriptografske sisteme so; napad z grobo silo, napad na
zasebni ključ, vrinjeni posrednik17 (M1TM), časovni napadltf.
4.3.1	Napad z grobo silo
Podobno kot simetrične je tudi asimetrične kriptografske sisteme možno učinkovito napasti z grobo silo. Protiukrep je tudi tukaj enak: uporabiti je treba Čim daljše ključe. Sistemi z javnimi ključi temeljijo na inverznih matematičnih funkcijah, katerih računska kompleksnost ne narašča linearno z dolžino ključa, ampak običajno precej hitreje. Ključ mora bili dovolj dolg, da napad z grobo silo ni praktičen, po drugi strani pa dovolj kratek, da sta šifriranje in des i frira nje dovolj hitra.
4.3.2	Napad na zasebni ključ
Napadalec poskuša na osnovi znanega javnega ključa generirati pripadajoči zasebni ključ. Ta napad je izredno zahteven, saj je povezava med javnim in zasebnim ključem zelo zapletena. Pri sistemu KSA temelji tovrstna povezava na faktor i ran ju velikih praštevU, kar je izredno dolgotrajen postopek.
4.3.3	Vrinjeni posrednik
To je napad, kjer se napadalec (oseba C) pojavlja kot posrednik (man-in-the ntiddle) med pošiljateljem (oseba A) in prejemnikom (oseba B). C e Želi zavzeti vlogo posrednika, mora imeli možnost prestrezanja sporočila, ki je namenjeno osebi B. Princip napada ji1 naslednji: napadalec objavi svoj javni ključ in se pri tem izdaja za osebo B. Kadar želi oseba A poslati šifrirano sporočilo osebi B, uporabi njen javni ključ, ki pa je dejansko ključ napadalca - osebe C. Na ta način napadalec sprejema Šifrirana sporočila, ki j i It lahko brez težav dešifnra s svojim zasebnim ključem Ko prebere sporočilo, ga šifrira s pravim javnim ključem osebe B in ji ga pošlje, l ovrstni napad se preprečuje s L.i. potrditvijo javnega ključa.
4.3.4	Časovni napad
Gre za zelo sodoben, računsko nezahteven in precej neopazen napad. Šifriranje različnih sporočit običajno traja različno dolgo. Če lahko napadalec meri čas, po treben za izvajanje šifrirne operacije, lahko pride na osnovi ponovljivih meritev in z uporabo verjetnosti in statistike, do pomembnih informacij o tajnem ključu, s katerimi se opravljajo šifrirni izračuni. Časovni napad je posebej nevarna oblika napada, saj zahteva le tajnopis. Deluje dobro tudi, če meritve niso posebej natančne. Uporablja si' pri napadih na RS A, Dinie-Ilellmanovo metodo in metode, ki temeljijo na
l(i AngL divide ontJCQnquer. 17 man-in-the middle 18Anf<l, tmung attack.
i I/*>ÎÎ|IFJ ujl N FO R M AT IKÂ
2001 ■ številka 3 - letnik IX
Mütej éalamon. Tomaž Dogša: Napadi na kriptografske sisteme
eliptičnih funkcijah. Proti časovnim napadom na RSA sta predlagana dva načina obrambe: dodajanje naključnih zakasnitev v računski del algoritma in dodatno predhodno šifriranje z nekim drugim algoritmom.
5. Sklep
Za absolutno preprečitev napadov bi bilo treba zagotoviti stalno fizično zaščito celotnega komunikacijskega sistema, kar pa je večinoma nemogoče (npr. internet, telefonsko omrežje,...). Dejavnosti, ki jih lahko uporabimo za reševanje opisane problematike, lahko razdelimo v naslednje kategorije: fizična preprečitev dostopa, odkrivanje napada, onemogočanje napada. Z zaščitnimi strežniki lahko zavarujemo lokalni del omrežja pred zunanjimi napadalci. Če smo zaznali napad in imamo tudi varnostne kopije sporočil, potem je možna tudi njihova rekonstrukcija.
Vsaka informacija o kriptografskem sistemu in sporočilu pomaga napadalcu. Vrsta napada je odvisna od količine in vrste napadalcu razpoložljivih sporočil, njegovega znanja in računalniške podpore. S prikrivanjem nekaterih podatkov o kriptografskem sistemu in sporočilu lahko povečujemo varnost kriptografskega sistema. Praviloma bo do napada prišlo, ko bo napadalec ocenil, da so stroški vdora (dešifrira-nja) manjši od koristi dešifriranega sporočila. Ker vrednost sporočila s časom pada, mora oceniti tudi, koliko časa potrebuje.
Ker se bosta kriptoanaliza in hitrost računalnikov neprestano dvigovala na višjo raven, bo treba tudi neprestano vzdrževanje kriptografskih sistemov, če želimo ohranjati potrebno varnost
LITERATURA
[1] N. Pavešic (1997):
Informacija in kodi, Univerza v Ljubljani
\2\ W. Stalling (1999):
Cryptography and Network Security: Principles and Practica, Second Edition. Prentice-Hall
[3]	T. Dogša (1993):
Verifikacija in validad j a programske opreme, Tehniška fakulteta Maribor
[4]	Vmnie Moscarnolo (1999):
h 11 p//www. vmetig. com/vin nfe/CtyptO.html
[5| N. R Johnson, S. Jajodia (1998):
Exploring Steganography: Seeing the Unseen, IEEE Computer, februar 1998. str.26 34
[6]	Paul C. Kocher (1998):
Breaking DES, RSA Laboratories' CryptoBytes vol. 4. Number 2, Winter 1998
[7]	Terry Ritter (2001):
Research Comments from Ciphers By Ritter: h tip ://www. ciphcrsbyiiner.com/
[8]	RSA Laboratories (1998):
Frequently asked Question About Todays Cryptography V4.0
[9]	RSA Laboratories (199S):
Technical Report Hi-701: Stream Ciphers. July 1995
♦
Ma tej S j lamo n je diplomiral leta 1994 m magistriral leta 1999 na Fakulteti za elektrotehniko, računalništvo m informatiko v Mariboru, kjer je tudi zaposlen kot asistent ¿a področje elektronike. Na raziskovalnem področju se ukvarja predvsem s kaotičnimi in kriptografskimi sistemi.
♦
Tomaž Dogia je docent na mariborski Fakulteti za elektrotehniko, računalništvo in informatiko, kjer predava na dodiplomski in podiplomski stopnji m vodi Center za verifikacijo in validacijo sistemov Na raziskovalnem področju se ukvarja predvsem s preverjanjem programske opreme.
2001 élevilka 3- letnik IX
,b,,, HNfOfiMATIKA