ˇSifriranjezavtentikacijo NejcˇStrubelj

Univerza v Ljubljani

Fakulteta za raˇ cunalniˇ stvo in informatiko Fakulteta za matematiko in fiziko

Nejc ˇ Strubelj

Sifriranje z avtentikacijo ˇ

DIPLOMSKO DELO

INTERDISCIPLINARNI UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE

RA ˇCUNALNIˇSTVO IN MATEMATIKA

Mentorica : izr. prof. dr. Arjana ˇ Zitnik

Ljubljana, 2021

tatov diplomske naloge je potrebno pisno privoljenje avtorja, fakultete ter mentorja.

Besedilo je oblikovano z urejevalnikom besedil L^ATEX.

Kandidat: Nejc ˇStrubelj

Naslov: Sifriranje z avtentikacijoˇ

Vrsta naloge: Diplomska naloga na univerzitetnem programu prve stopnje Raˇcunalniˇstvo in matematika

Mentorica: izr. prof. dr. Arjana ˇZitnik

Opis:

ˇSifriranje z avtentikacijo zagotavlja poleg zasebnosti tudi pristnost in ce- lovitost sporoˇcil, kar je ˇcedalje bolj pomembno za varno komunikacijo v digitalnem svetu. V diplomskem delu predstavite razliˇcne stopnje varno- sti ˇsifrirnih shem in analizirajte odnose med njimi. Na primer, semantiˇcna varnost pred napadom z izbranim besedilom in celovitost kriptogramov, ki definirata ˇsifriranje z avtentikacijo, zagotavljata tudi varnost pred napadom z izbranim kriptogramom. Predstavite tudi razliˇcne paradigme za izvedbo ˇsiftriranja z avtentikacijo: generiˇcna sestava z uporabo ˇsifriranja in kode za avtentikacijo ter integrirane sheme. Kot predstavnika vsake od paradigem podrobneje opiˇsite naˇcin s ˇstevcem GCM (Galois Counter Mode) in naˇcin OCB (offset codebook mode).

Kazalo

Povzetek Abstract

1 Uvod 1

2 Osnove ˇsifriranja 5

2.1 Kriptosistem . . . 6

2.2 Bloˇcne ˇsifre . . . 9

2.3 Naˇcini uporabe bloˇcnih ˇsifer . . . 10

2.4 Varnost kriptosistemov . . . 15

2.5 AES . . . 19

3 Zgoˇsˇcevalne funkcije in celovitost 21 3.1 Celovitost kriptograma . . . 22

3.2 Zgoˇsˇcevalna funkcija s kljuˇcem . . . 23

4 Sifriranje z avtentikacijoˇ 29 4.1 Generiˇcna sestava . . . 30

4.2 Integrirane sheme . . . 38

5 Zakljuˇcek 47

Literatura 49

Seznam uporabljenih kratic

kratica angleˇsko slovensko

AE authenticated encryption ˇsifriranje z avtentikacijo AES Advanced Encryption Stan-

dard

napredni ˇsifrirni standard CPA chosen plaintext attack napad z izbranim besedilom MAC message authentication code zgoˇsˇcevalna funkcija s kljuˇcem GCM Galois-counter mode Galoisov naˇcin s ˇstevcem OCB offset codebook mode kodna knjiga z zamikom SSL Secure Sockets Layer internetni varnostni protokol IPSEC Internet Protocol Security varen internetni protokol

SSH secure shell protokol za upravljanje

raˇcunalnika na daljavo

EtM encrypt-then-MAC ˇsifriraj nato uporabi

zgoˇsˇcevalno funkcijo s kljuˇcem MtE MAC-then-encrypt uporabi zgoˇsˇcevalno funkcijo s

kljuˇcem nato ˇsifriraj

EaM encrypt-and-MAC ˇsifriraj in uporabi zgoˇsˇcevalno funkcijo s kljuˇcem

ECB electronic code book elektronska kodna knjiga CBC cipher block chaining veriˇzenje kodnih blokov

CM counter mode naˇcin s ˇstevcem

Povzetek

Naslov: Sifriranje z avtentikacijoˇ Avtor: Nejc ˇStrubelj

ˇSifriranje nas neopazno obdaja vsakokrat, ko uporabljamo mobilne komuni- kacije, spletne storitve in podobno. Zahteve po uˇcinkovitem ˇsifriranju pa se vsak dan poveˇcujejo.

V delu predstavljamo ˇsifriranje z avtentikacijo, ki je eno najbolj uˇcinkovitih orodij za zagotavljanje varne komunikacije, saj zagotavlja tako zaupnost kot avtentiˇcnost poslanih sporoˇcil. Pokaˇzemo, pred katerimi napadi je takˇsen sistem varen in razloˇzimo zakaj. Razloˇzimo delovanje zgoˇsˇcevalne funkcije s kljuˇcem in pokaˇzemo, kako nam ta pomaga pri ohranjanju verodostojnosti podatkov. Za konec predstavimo naˇcine, kako sestaviti sistem za ˇsifriranje z avtentikacijo, ter opiˇsemo algoritma OCB in GCM, ki takˇsen sistem realizi- rata.

Kljuˇcne besede: kriptografija, ˇsifriranje z avtentikacijo, MAC, AES, OCB, GCM.

Abstract

Title: Authenticated encryption Author: Nejc ˇStrubelj

Encryption surrounds us imperceptibly every time we use mobile communi- cations, online banking, online services and the like. Meanwhile the demand for efficient encryption is growing daily.

In this thesis, we present authenticated encryption, which is one of the most powerful tools for ensuring secure communications, since it provides both privacy and authenticity. We show which kind of attacks a system like that is effective against and explain why. We describe message authentication codes and show how they assure data integrity. Finally, we present different approaches to constructing authenticated encryption schemes: generic com- positions which combine an encryption scheme and a message authentication code, and integrated schemes. Two algorithms that realize such systems are then presented: GCM and OCB.

Keywords: cryptography, authenticated encription, MAC, AES, OCB, GCM.

Poglavje 1 Uvod

Potreba po ˇsifriranju se je v ˇcloveˇski civilizacija pojavila zelo zgodaj. V delu na primer omenimo Cezarjevo ˇsifro, poimenovano po rimskemu diktatorju Gaju Juliju Cezarju, za katero vemo, da je bila v uporabi ˇze leta 100 pred naˇsim ˇstetjem. Ko je bila pismenost med prebivalstvom ˇse relativno nizka, so zadoˇsˇcale ˇze preproste ˇsifre, vendar pa je potreba po moˇcnejˇsih orodjih hitro naraˇsˇcala in naraˇsˇca ˇse danes.

Pravi preporod je kriptografijo doletel ob razvoju interneta. Pogosto je najbolj varen prenos sporoˇcil v ˇzivo, torej fiziˇcni prenos informacij, a je ta ravno tako pogosto nepraktiˇcen. Veliko varneje je na primer banˇcne soritve opravljati na banki, vendar ali zares ˇzelimo obiskati banko za vsak vpogled v naˇse stanje na raˇcunu? Uporabo takˇsnih storitev je internet moˇcno olajˇsal.

Prenos informacij je z internetom postal hitrejˇsi in enostavnejˇsi kot kadarkoli prej in tudi zato se je uporaba le tega razˇsirila zelo hitro. A hitro je bilo opaziti, da informacij, ki potujejo po fiziˇcnih kanalih, ni teˇzko prestreˇci in jih zlorabiti. Cilj kriptografije je torej zasnovati tak sistem, kjer takˇsnega kanala in sporoˇcil, ki se po njem pretakajo, ni treba dobesedno skriti, ampak jih lahko vidi kdorkoli. Sporoˇcila je le treba spremeniti na tak naˇcin, da bi jih znali prebrati le tisti, za katere ˇzelimo, da jih znajo.

Razvijati so se zaˇceli sistemi, ki so nas uspeˇsno branili pred neˇzelenimi prisluˇskovalci, vendar so slednji kmalu postali pametnejˇsi. Ugotovili so, da

1

morda ni potrebno vedno samo prebirati tujih sporoˇcil in da je vˇcasih dovolj, da obstojoˇca tuja sporoˇcila le spremenijo ali pa jih v celoti ustvarijo sami in se pretvarjajo, da jih je poslal nekdo drug. To je za kriptografijo predstavljalo veliko teˇzji problem in tukaj pride na vrsto ˇsifriranje z avtentikacijo. Kot bomo videli, je ˇsifriranje z avtentikacijo naˇcin ˇsifriranja, ki se od obiˇcajnega ˇsifriranja razlikuje v tem, da ne nudi le zaˇsˇcite pred tem, da bi neˇzelene osebe lahko prebrale vsebino naˇsih sporoˇcil, temveˇc zagotavlja tudi to, da sporoˇcila med prenosom niso bila spremenjena in da jih je zares poslala tista oseba, ki naj bi jih. Zares pomembno pri ˇsifriranju z avtentikacijo pa je to, da nam dve preprosti, a premiˇsljeno izbrani zahtevi, omogoˇcita doloˇcen nivo varnosti, katerega bi teˇzko slutili intuitivno.

Se ne tako dolgo nazaj je zadoˇsˇˇ calo, da so bili sistemi varni pred na- padom z golim kriptogramom ter napadom z znanim besedilom, sedaj pa to ne zadoˇsˇca veˇc. V delu bomo pokazali, kako se lahko zaˇsˇcitimo pred napadom z izbranim kriptogramom, kar je smatrano za precej viˇsji nivo var- nosti. To doseˇzemo tudi s ˇsifriranjem z avtentikacijo (AE). Preko iger med napadalcem in izzivalcem bomo definirali pojme, kot so semantiˇcna varnost pred napadom z izbranim besedilom (CPA-varnost), semantiˇcna varnost pred napadom z izbranim kriptogramom (CCA-varnost), celovitost kriptograma ter povedali, kaj pomeni, da je neka zgoˇsˇcevalna funkcija s kljuˇcem varna (MAC-varnost) [4]. Predstavili bomo algoritma OCB [12] ter GCM [15] ter pogoje, pod katerimi dosegata standarde AE-varnosti, kar je tudi cilj tega dela. Kljuˇcen del zaˇsˇcite, ki jo nudi ˇsifriranje z avtentikacijo, je tudi upo- raba tako imenovanih pridruˇzenih podatkov [16], ki jih razloˇzimo v delu in pokaˇzemo, kako nas lahko ti obvarujejo pred napadi s strani administratorjev podatkovnih baz.

To delo je strukturirano na naslednji naˇcin. Na zaˇcetku bomo predstavili osnove kriptografije in s primeri razloˇzili teoretiˇcna dejstva, da bo bralec zaˇcutil, kaj je bistvo kriptografije ter s kakˇsnimi problemi se le-ta ukvarja.

Nato bomo razloˇzili nekoliko zahtevnejˇse teme kot so zgoˇsˇcevalne funkcije, vrste napadov, celovitost kriptograma in drugo, ki so ravno tako sestavni del

Diplomska naloga 3 osrednjega poglavja in bistveni za razumevanje problema, ki ga reˇsujemo. V ˇcetrtem, osrednjem, poglavju definiramo ˇsifriranje z avtentikacijo in opiˇsemo dva naˇcina za njegovo izvedbo: generiˇcno sestavo in integrirane sheme. V 5.

poglavju delo zakljuˇcimo s pregledom obravnavane tematike in s sklepnimi mislimi.

Poglavje 2

Osnove ˇ sifriranja

Beseda kriptografija izhaja iz grˇskih besed krypt´os in graphein, kar bi do- besedno prevedli v skrita pisava, kar precej dobro zajame bistvo te vede.

Veda kriptografija se namreˇc osredotoˇca na preuˇcevanja varne komunikacije ob prisotnosti nezaˇzelenega napadalca. Povedano drugaˇce, zanima nas, kako zapisati neko sporoˇcilo na tak naˇcin, da ga bo sposoben prebrati le tisti, ki mu je sporoˇcilo namenjeno, in da ga bo ta prejel v celoti in nespremenjenega.

Nezaˇzeleni napadalec je lahko fiziˇcna oseba ali pa le raˇcunalnik, ki je vnaprej sprogramiran, da se odziva glede na to, kakˇsne informacije je prestregel. ˇZelja takˇsne neˇzelene entitete ni nujno le prisluˇskovanje, lahko je tudi spreminjanje sporoˇcila, prepreˇcevanje poˇsiljanja in podobno.

Nekoˇc je bil edini cilj kriptografije skrivanje besedila, sedaj pa veda za- jema veˇc podroˇcij:

• zaupnost podatkov (angl. confidentiality) omejevanje vpogleda nepoo- blaˇsˇcenim osebam,

• celovitost podatkov (angl. data integrity) zagotavljanje nespremenjeno- sti sporoˇcila s strani neavtorizirane osebe,

• avtentikacija oziromaoverjanje (angl. authentication) potrditev izvora sporoˇcila,

5

• prepreˇcevanje tajenja oziroma nepriznavanja (angl. non-repudiation) prepreˇcevanje zanikanja obljube oziroma dejanja.

V nadaljevanju se bomo osredotoˇcili na ˇsifriranje. Podali bomo formalno definicijo kriptosistema, pokazali, kako ˇsifriramo daljˇsa sporoˇcila, definirali, kaj pomeni, da je kriptosistem varen in opisali kriptosistem AES, ki je velja- ven standard. V nadaljevanju bomo sledili knjigam [4, 29].

2.1 Kriptosistem

Namen kriptosistema je formalizacija ˇsifriranja, ˇcigar namen je pretvarjanje besedil (angl. plaintext) v kriptograme (angl. ciphertext). Besedila so lahko na primer gesla ali pa sporoˇcila, ponavadi nek berljiv niz znakov, ki nosi neko informacijo. Kriptogrami pa so nizi znakov, za katere pogosto ˇzelimo, da izgledajo, kot da so izbrani nakljuˇcno.

Proces takˇsne pretvorbe imenujemoˇsifriranje (angl. encryption). Takˇsne procese izvajajo kodirne funkcije, ˇce pa ˇzelimo doseˇci obratno pretvorbo, torej ˇce ˇzelimo pretvoriti kriptogram nazaj v besedilo, pa uporabimo dekodirne funcije. Takˇsen proces imenujemo deˇsifriranje (angl. decryption ).

Kljuˇc (angl. key) je ponavadi niz ˇstevk ali znakov, s pomoˇcjo katerega ˇsifriramo besedilo oziroma deˇsifriramo kriptogram. Varnost ˇsifriranja temelji na tem, da napadalec ne pozna kljuˇca za deˇsifriranje. To je odvisno tudi od dolˇzine kljuˇca, naˇcina, kako kljuˇc generiramo, ter naˇcina, kako si kljuˇce izmenjamo s tistim, s katerim si izmenjujemo ˇsifrirane podatke. Ker je pri- poroˇcljivo ˇsifrirne kljuˇce pogosto spreminjati in ker je dandanes uporaba ˇsifriranja zelo pogosta, je varna izmenjava kljuˇcev ˇse posebej pomembna.

Vsaka prijava v e-poˇstni raˇcun ali socialno omreˇzje se izvede preko ˇsifriranja in avtentikacije, zato bi bilo nepraktiˇcno kljuˇce izmenjevati osebno. V ta namen se je razvila prva varna izmenjava kljuˇcev po ne-varnem kanalu, ime- novana Diffie-Hellmanova izmenjava kljuˇcev [5].

Kriptosistem je mogoˇce definirati na veˇc ekvivalentnih naˇcinov, za potrebe tega dela pa se bomo drˇzali definicije iz knjige Douglasa R. Stinsona [29].

Diplomska naloga 7 Kriptosistem (kodirna shema, ˇsifra) je peterka (K,M,C,E,D) za katero velja:

1. Kje konˇcna mnoˇzica kljuˇcev, 2. Mje konˇcna mnoˇzica besedil, 3. C je konˇcna mnoˇzica kriptogramov,

4. E ={E_k: M → C;k ∈ K} je druˇzina kodirnih funkcij, kjer c=E_k(m) pomeni, da jec kriptogram, ki smo ga dobili s ˇsifriranjem sporoˇcila m s kljuˇcem k,

5. D = {D_k : C → M;k ∈ K} je druˇzina dekodirnih funkcij, kjer m =D_k(c) pomeni, da je c kriptogram, ki smo ga dobili s ˇsifriranjem sporoˇcila m s kljuˇcem k,

6. za vsak kljuˇc e ∈K obstaja kljuˇc d ∈ K, da velja D_d(E_e(m)) =m za vsak m∈ M.

Opazimo, da iz ˇseste toˇcke sledi, da so kodirne funkcijeEk∈ E injektivne.

Izrek 2.1. Vsaka kodirna funkcija E_k ∈ E je injektivna.

Dokaz. Naj bosta e ∈ K kodirni kljuˇc in d ∈ K ustrezen dekodirni kljuˇc. Recimo, da funcija E_e ni injektivna. Tedaj obstajata razliˇcni besedili m₁, m₂ ∈ M, da velja:

E_e(m₁) =E_e(m₂).

Potem velja tudi:

D_d(E_e(m₁)) =D_d(E_e(m₂)) in po 6. toˇcki definicije kriptosistema ˇse

m₁ =m₂.

To pa je protislovje, saj smo trdili, da sta sporoˇcili m1 ter m2 razliˇcni. Sledi

torej, da je funkcija E_e res injektivna.

Dodatna lastnost kriptosistema je simetriˇcnost.

Definicija 2.1. Pravimo, da je kriptosistemsimetriˇcen, ˇce poznamo uˇcinkovit algoritem (takˇsen, ki deluje v polinomskem ˇcasu, glede na velikost kljuˇcev), ki za vsak kodirni kljuˇc e ∈ K izraˇcuna pripadajoˇci dekodirni kljuˇc d ∈ K.

Ce kriptosistem ni simetriˇˇ cen, je asimetriˇcen.

Pri uporabi simetriˇcnega kriptosistema, se prejemnik in poˇsiljatelj v na- prej dogovorita za kljuˇck ∈ K, ki sluˇzi tako ˇsifriranju kot deˇsifriranju. Teˇzava takˇsnega sistema je, da si stranki teˇzko skrivaj izmenjata kljuˇck, saj so ravno takˇsne skrivne komunikacije tisto, kar ˇzelimo doseˇci. Kljuˇc si lahko varno izmenjata v ˇzivo, vendar je to pogosto nepraktiˇcno. Zato se je razvila komu- nikacija z asimetriˇcnim kriptosistemom ali kriptosistemom z javnim kljuˇcem (angl. public-key cryptosistem) [17].

Ideja pri takˇsni komunikaciji je, da je morda mogoˇce najti takˇsen krip- tosistem, kjer je raˇcunsko nemogoˇce pridobiti dekodirni kljuˇc d, ˇce poznamo le kodirni kljuˇc e. Tedaj bi kodirni kljuˇc lahko javno objavili in zato tak kljuˇc imenujemo javni kljuˇc (angl. public key), dekodirni kljuˇc pa zasebni kljuˇc (angl. private key), saj zasebnega kljuˇca ne bi smeli deliti z niko- mer. ˇCe bi torej neka oseba Ana objavila svoj javni kljuˇc, bi lahko z njenim kljuˇcem kdorkoli ˇsifriral sporoˇcila, deˇsifrirala pa bi jih lahko le Ana s svojim deˇsifrirnim kljuˇcem.

Takˇsno komunikacijo si lahko predstavljamo z analogijo kljuˇcavnice s ˇstevilˇcnico. Oseba Blaˇz lahko v ˇskatlo zapre poljuben (dovolj majhen) pred- met in ˇskatlo zaklene z Anino kljuˇcavnico. Ker samo Ana pozna ˇstevilko svoje kljuˇcavnice je samo ona tista, ki lahko odpre ˇskatlo.

Idejo o takˇsnem kriptosistemu sta leta 1976 predstavila Diffie in Hell- man [5], leto kasneje pa so Rivest, Shamir in Adleman razvili znani kriptosi- stem z javnim kljuˇcem, imenovan RSA [24].

Kot zgled preprostega kriptosistema si oglejmo Cezarjevo ˇsifro. S takˇsnim ˇsifriranjem bi na primer iz besedila

”sestanek ob osmih na forumu“ dobili kriptogram

”uhuzˇcrhn sd suplk rˇc istˇzpˇz“. Oˇcitno je, da je bilo ˇze tako preprosto ˇsifriranje zelo uporabno, saj kriptogram na prvi pogled izgleda kot nakljuˇcen niz.

Diplomska naloga 9

Slika 2.1: Cezarjeva ˇsifra Formalni zapis Cezarjeve ˇsifre je sledeˇc:

• M=C =K={0,1, ...,24}=Z25,

• kodiranje: E_k(x)≡x+k (mod 25),

• kodiranje: D_k(y)≡y−k (mod 25).

Kodiranje in dekodiranje pa raˇcunamo v Abelovi grupi (Z25, +).

Naj omenimo, da raˇcunamo vZ25, ker je 25 ˇstevilo ˇcrk v slovenski abecedi.

Ce bi na primer ˇsifrirali besedilo v angleˇsˇˇ cini, bi raˇcunali v Z²⁶.

Sifre, ki ˇsifrirajo po en znak naenkrat, so raˇˇ cunsko in prostorsko zelo uˇcinkovite, vendar pa je razbijanje takˇsnih ˇsifer ponavadi enostavno. V sploˇsnem za ˇsifro reˇcemo da je razbita, ˇce znamo uˇcinkovito deˇsifrirati krip- tograme, ki jih ˇsifra ustvari. Pri zgledu s Cezarjevo ˇsifro opazimo, da ˇce enkrat ugotovimo naˇcin, kako je besedilo ˇsifrirano, ni teˇzko deˇsifrirati nadalj- nih kriptogramov, saj je na voljo zelo malo kljuˇcev, s katerimi lahko besedilo ˇsifriramo. Ob uporabi slovenske abecede pri vsakem prestreˇzenem kripto- gramu napadalec preizkusi le 24 moˇznih kljuˇcev, to je 24 moˇznih zamikov znakov.

2.2 Bloˇ cne ˇ sifre

Izkazalo se je, da lahko delo napadalcem hitro oteˇzimo, ˇce ne ˇsifriramo vsa- kega znaka posebej, ampak ˇsifriramo veˇc znakov hkrati. ˇCe bi torej obstajal

sistem, ki bi ˇsifriral veˇc znakov hkrati in ob tem ne bi preveˇc oteˇzil avtori- ziranega deˇsifriranja (takˇsnega, ki ga ne izvajajo napadalci), bi bilo to zelo praktiˇcno. V ta namen, so se razvile bloˇcne ˇsifre (angl. block ciphers).

Kriptosistem S = (K,M,C,E,D) je bloˇcna ˇsifra, ˇce zanj velja, da sta mnoˇzica sporoˇcil in mnoˇzica kriptogramov enaki, torej velja M=C.

Pravimo, da je kriptosistem bloˇcna ˇsifra dolˇzine n, ˇce velja M = C ⊆ {0,1}ⁿ. Besedilo, ki ga ˇzelimo ˇsifrirati razdelimo, na bloke dolge n bitov in vsakemu priredimo blok iz mnoˇzice kriptogramov na naˇcin E_k(b) = c, kjer velja k ∈ K, b ∈ B, ter c ∈ C. Iz ˇseste toˇcke definicije kriptosistema sledi, da je funkcija E injektivna. Ker sta tudi njeno definicijsko obmoˇcje in zaloga vrednosti enako moˇcni mnoˇzici (M = C), je kodirna funcija na tem definicijskem obmoˇcju bijektivna in ima inverz, ki je kar deˇsifrirna funkcija.

2.3 Naˇ cini uporabe bloˇ cnih ˇ sifer

Iz definicije bloˇcnih ˇsifer opazimo, da so te definirane na enem bloku, medtem ko so besedila, ki jih ˇzelimo ˇsifrirati, obiˇcajno daljˇsa od enega bloka. Pojavi se vpraˇsanje, kako ˇsifrirati daljˇse besedilo.

Besedilo b razdelimo na bloke tako, da velja b =b₁ k b₂ k ...k b_m, kjer z znakom

”k“ oznaˇcim stik nizov. Stik je operacija, ki zdruˇzi dva niza poljubne dolˇzine. Na primer, ˇce staainbniza, da veljaa=

”kripto“ inb =

”graf ija“, tedaj lahko z akb oznaˇcimo nov niz in velja akb=

”kriptograf ija“.

Vsi blokibi nizabnaj bodo iste dolˇzine, denimon, razen morda zadnjega, ki je lahko krajˇsi. ˇCe je zadnji blok krajˇsi, ga dopolnimo do velikosti ostalih blokov (angl. padding). Nastale bloke lahko ˇsifriramo na razliˇcne naˇcina.

2.3.1 Elektronska kodna knjiga (ECB)

Prvi naˇcin, ki se ga domislimo, je, da s kljuˇcem k ˇsifriramo vsak blok po- sebej. Takˇsen naˇcin imenujemo elektronska kodna knjiga (angl. electronic codebook). Algoritem za ˇsifriranje besedila s takˇsnim naˇcinom je sledeˇc:

Diplomska naloga 11 b = b_1||b_2||...||b_m

c <- prazen niz

for (i = 1; i <= m; i++) c_i = E_k(b_i)

c = c||c_i return c

Tedaj deˇsifriramo na naslednji naˇcin:

c = c_1||c_2||...||c_m b <- prazen niz

for (i = 1; i <= m; i++) b_i = D_k(c_i)

b = b||b_i return b

Prednost pri takˇsnem ˇsifriranju je to, da napaka pri prenosu enega bloka ne vpliva na ostale bloke. Ob napaki izgubimo le informacije, ˇsifrirane v bloku z napako. Vseeno pa takˇsno ˇsifriranje ni pretirano varno, saj se identiˇcni bloki besedila (pri istem kljuˇcu) ˇsifrirajo v identiˇcne bloke kriptograma, kar povzroˇci, da kriptogram ne izgleda tako nakljuˇcen, kot bi si ˇzeleli. ˇCe bi na primer ˇsifrirali sliko, katere piksli so zapisani z bloki bitov, bi bili podobni deli slike ˇsifrirani v podobne kriptograme. To se lepo vidi na sliki 2.2, kjer je slika v sredini ˇsifrirana na naˇcin ECB.

Slika 2.2: Teˇzava ECB ˇsifriranja

Ce napadalec prestreˇˇ ze sporoˇcilo, ga lahko tudi enostavno spreminja.

Sporoˇcilu lahko na primer spremeni vrstni red blokov, kar je posebej neu- godno, ˇce so v kriptogramu ˇsifrirani na primer denarni zneski.

2.3.2 Veriˇ zenje kodnih blokov (CBC)

Kljuˇcna teˇzava pri ˇsifriranju z elektronsko kodno knjigo je, da identiˇcne bloke besedila ˇsifriramo v identiˇcne bloke kriptograma. Pri naˇcinu z veriˇzenjem kodnih blokov (angl. cipher block chaining) ˇzelimo to teˇzavo odpraviti.

Izberemo inicializacijski vektor IV dolˇzine n, ki je lahko javno dostopen, fiksen ali nakljuˇcen. Tedaj algoritem za ˇsifriranje z naˇcinom CBC izgleda takole:

b = b_1||b_2||...||b_m c <- prazen niz

c_i = IV

for (i = 1; i <= m; i++) c_i = E_e(b_i xor c_i) c = c||c_i

return c

V tem primeru, deˇsifriranje izgleda tako:

c = c_1||c_2||...||c_m b <- prazen niz

c_i = IV

for (i = 1; i <= m; i++) b_i = D_d(c_i) xor c_i b = b||b_i

return b

Opazimo, da ob kodiranju identiˇcnih blokov bi in bj ne sledi nujno, da sta tudi bloka c_i in c_j identiˇcna, saj je c_j odvisen od b_j, bj−1, ..., b₁ in IV.

Diplomska naloga 13 S takˇsnim kodiranjem lahko zaznamo tudi zamenjavo blokov b_i in b_j, saj takˇsna zamenjava vpliva na ˇsifriranje vseh nadaljnih blokov, kar je kljuˇcno pri ˇsifriranju z avtentikaciju. Prav tako zaznamo spremembe v kriptogramu, saj napadalec ne more enostavno zamenjati delov kriptograma, kot je to lahko storil pri ˇsifriranju z elektronsko kodno knjigo.

Pomanjkljivost takˇsnega naˇcina je razvidna, ko ˇzelimo ˇsifrirati veliko ˇstevilo blokov. Ker je vsak blok kriptograma odvisen od prejˇsnjega bloka, je tak naˇcin nemogoˇce raˇcunati vzporedno (paralelno). ˇZeleli bi si, da lahko vsak blok raˇcunamo neodvisno od drugih blokov. To pa je ravno prednost naˇcina s ˇstevcem, ki ga bomo predstavili v naslednjem podrazdelku.

2.3.3 Naˇ cin s ˇ stevcem (CM)

Ce ˇˇ zelimo ˇsifrirati z moˇznostjo vzporednega raˇcunanja, morajo biti bloki kriptograma med seboj neodvisni. To lahko doseˇzemo z uporabo naˇcina s ˇstevcem (angl. Counter mode, CM).

Naj bo ˇstevec ctr dolˇzine n. Tedaj ˇsifriramo kot:

b = b_1||b_2||...||b_m c <- prazen niz

for (i = 1; i <= m; i++)

l_i = ctr + i - 1 (mod 2^n) c_i = b_i xor E_e(l_i) return c

In deˇsifriramo kot:

c = c_1||c_2||...||c_m b <- prazen niz

for (i = 1; i <= m; i++)

l_i = ctr + i - 1 (mod 2^n) b_i = c_i xor E_e(l_i) return b

Tako so bloki kriptograma med seboj neodvisni in lahko vsak blok raˇcunamo posebej in vzporedno. Hitro je tudi deˇsifriranje, saj lahko vse vrednosti oblike E_e(l_i) prejemnik izraˇcuna vnaprej, raˇcunanje operacije xor (oznaˇceno tudi kot

⊕) pa je ˇcasovno zelo nezahtevno.

Zavedati pa se je potrebno, da moramo pri ˇsifriranju z naˇcinom s ˇstevcem ob vsakem ˇsifriranju novega sporoˇcila pozorno spremeniti tudi vrednost ˇstevca.

Opazimo, da pri ˇsifriranju besedila uporabljamo spremenljivko l_i, ki je od- visna od vrednosti ˇstevca ctr. Vrednost te spremenljivke z vsakim novim blokom poveˇcamo (razen v primeru, ko vrednost preraste 2ⁿ). Naj bo L_a = {l_a1, l_a2, ..., l_ah} mnoˇzica vseh vrednosti, ki jih spremenljivka zasede med ˇsifriranjem sporoˇcila a in naj bo L_b = {l_b1, l_b2, ..., l_bk} mnoˇzica vseh vredno- sti, ki jih spremenljivka zasede med ˇsifriranjem sporoˇcila b. Za vsaki takˇsni sporoˇcili ain b iz mnoˇzice sporoˇcil, ki jih ˇsifriramo mora veljati L_a∩L_b =∅.

Ce tega pravila ne bi upoˇstevali in bi sporoˇˇ cilo a ˇsifrirali v kriptogram c, ter sporoˇcilo b v kriptogram c⁰ z istimi vrednostmi ˇstevcev in bi napadalec prestregel kriptograma cter c⁰, bi ta lahko izraˇcunal:

c_i ⊕c⁰_i =a_i⊕E_e(l_i)⊕b_i⊕E_e(l_i) =a_i⊕(E_e(l_i)⊕E_e(l_i))⊕b_i =a_i⊕b_i. Ce bi napadalec poznal blok sporoˇˇ cila a, na primer a_i, bi lahko enostavno izraˇcunal tudi blok sporoˇcila b_i, saj velja:

(c_i ⊕c⁰_i)⊕a_i = (a_i⊕b_i)⊕a_i = (a_i⊕a_i)⊕b_i =b_i.

Z ugibanjem delov besedil lahko nato rekonstruira obe besedili ali vsaj veˇcji del obeh besedil.

Oglejmo si ˇse napad (po vzoru [10, stran 12]), ki ga napadalec lahko izvrˇsi, ˇce pozna par besedilo - kriptogram. Tedaj lahko napadalec ˇsifrira sporoˇcila po lastni izbiri, ne da bi poznal ˇsifrirno funcijoE_e. Recimo, da napadalec ve, da je sporoˇcilo b =b₁ kb₂ k..._m ˇsifrirano v kriptogram c=c₁ kc₂ k...kc_m. Tedaj lahko izraˇcuna vrednosti niza E_e(l_i) za vsak i, saj je E_e(l_i) = b_i⊕c_i. Tako lahko za sporoˇcilo po lastni izbiri, ki je krajˇse ali enako dolgo kot sporoˇcilo b, izraˇcuna kriptogram. Recimo da bi ˇzelel napadalec izraˇcunati

Diplomska naloga 15 kriptogram sporoˇcilab⁰ =b⁰₁ kb⁰₂ k...kb⁰_m. Vse kar bi moral napadalec tedaj storiti je poraˇcunati:

c⁰ =b⁰₁⊕E_e(l₁)kb⁰₂⊕E_e(l₂)k...kb⁰_m⊕E_e(l_m).

Eksplicitno bi njegov kriptogram izgledal kot:

c⁰ =b⁰₁⊕b₁⊕c₁ kb⁰₂⊕b₂⊕c₂ k...kb⁰_m⊕b_m⊕c_m.

2.4 Varnost kriptosistemov

Ce kriptografija razvija postopke za zagotavljanje informacijske varnosti, jeˇ kriptoanaliza zlobna sestra dvojˇcica, ki ˇzeli te postopke izniˇciti. Ker ponavadi ˇsifriramo pomembne informacije, se pogosto pojavi interes po deˇsifriranju teh besedil s strani tistih, ki jim to sporoˇcilo ni bilo namenjeno. ˇCe ti poskuˇsajo deˇsifrirati ali spremeniti kriptogram, to imenujemo napad.

Bolj natanˇcno so cilji napadov lahko razliˇcni:

• odkriti dekodirni kljuˇc,

• deˇsifrirati celotni kriptogram ali del le-tega,

• izvedeti kakˇsne podatke o besedilu,

• prikrito spremeniti besedilo.

Pri preuˇcevanju napadov se moramo zavedati Kerchoffovega principa, ki pravi, da

”nasprotnik pozna kriptosistem oziroma algoritme, ki jih upora- bljamo, ne pa tudi kljuˇcev, ki nam zagotavljajo varnost“. Kodirni postopki so pogosto javno dostopni. Vsakiˇc na primer, ko raˇcunalnik preverja digi- talno identiteto, v ozadju izvaja znane algoritme. Tako se torej ni pametno zanaˇsati na to, da napadalec kodirnih postopkov ne pozna. Napadalce loˇcimo naaktivne ter pasivne glede na to, kaj zmorejo s svojimi napadi doseˇci.

2.4.1 Pasivni napadalec

Pasivni napadalci sporoˇcila le opazujejo in shranjujejo njim koristne podatke.

Takˇsni napadi ogroˇzajo zaupnost besedil. Med pasivne napade spadajo:

• napad z golim kriptogramom (angl. ciphertext only attack),

• napad z znanim besedilom (angl. known plaintext attack),

• napad z izbranim besedilom (angl. choosen plaintext attack) ali CPA.

Napad z golim kriptogramom je napad, kjer predvidevamo, da ima na- padalec dostop do omejene mnoˇzice kriptogramov. Pri napadu z znanim besedilom pa ima napadalec dostop do omejene mnoˇzice parov (besedilo, kriptogram).

Obramba pred napadoma z golim kriptogramom ter znanim besedilom kmalu ni veˇc zadoˇsˇcala in se sedaj smatra za nizek standard varnosti. Izkaˇze pa se, da je obramba pred napadom z izbranim besedilom skupaj z celovi- tostjo kriptograma (o tem pozneje) za napadalca precej trˇsi oreh.

2.4.2 Napad z izbranim besedilom

Za napad z izbranim besedilom (angl. chosen plaintext attack) velja takˇsen napad, ki predpostavlja, da lahko napadalec dostopa do kriptogramov za iz- brana sporoˇcila. To je ekvivalentno trditvi, da ima napadalec dostop do ko- dirnega postopka. Napadalec torej generira pare (m, c) za izbrana sporoˇcila m in iz mnoˇzice parov (m, c) poskuˇsa doseˇci enega od zgoraj naˇstetih ci- ljev. ˇCe je ˇsifra odporna na takˇsne vrste napadov, reˇcemo, da je ˇsifra varna pred napadom z izbranim besedilom, oziroma krajˇse, da je CPA-varna (angl.

CPA-secure). Formalna definicija CPA-varna ˇsifre sledi iz naslednje igre [4, stran 178].

V igri nastopata dva igralca, izzivalec in napadalec A, ki ˇzeli doseˇci doloˇcen cilj. Naj bo S = (K,M,C,E,D) kriptosistem. Z oznako k −→ K^R oznaˇcimo nakljuˇcen izbor elementakiz mnoˇziceK. Definiramo dva poskusa, Poskus 0 ter Poskus 1. Naj bo p∈ {0,1}. Poskus p izgleda takole:

Diplomska naloga 17

• Izzivalec si izbere nakljuˇcen kljuˇc k←^R− K.

• Napadalec A sproˇzi nekaj poizvedb proti izzivalcu, kjer i-ta poizvedba vsebuje par sporoˇcilm_i0, m_i1 ∈ M, ki sta enako dolgi. Izzivalec izraˇcuna c_i =E(k, m_ip) in poˇslje c_i napadalcu.

• Napadalec nato vrne ˆp∈ {0,1}.

Za p ∈ {0,1}, naj bo W_p dogodek, da A vrne 1 v Poskusu p. Prednost napadalca A glede na kriptosistemS definiramo kot:

CPAadv[A,S] :=|Pr[W0]−Pr[W1]|, kjer s Pr[W_p] oznaˇcimo verjetnost dogodka W_p.

Definicija 2.2. Pravimo, da je kriptosistemS = (K,M,C,E,D)semantiˇcno varen pred napadom z izbranim besedilom (angl. semantically secure against chosen plaintext attack) oziroma CPA-varen (angl. CPA-secure), ˇce je za vsakega nasprotnikaA, ˇcigar napadi so ˇcasovno uˇcinkoviti (polinomski), vre- dnost CPAadv[A,S] zanemarljiva.

Ideja takˇsne definicije je to, da ˇce je napadalec enako verjetno vraˇcal vrednosti 0 in 1 ne glede na prejeti kriptogramc_i, potem ni vedel, ali je prejeti kriptogram ˇsifrirano sporoˇcilo mi0 ali mi1. Izkaˇze se, da je to ekvivalentno zahtevi, da napadalec na osnovi prestreˇzenega kriptograma ne izve niˇcesar o besedilu (v polinomskem ˇcasu) [28, stran 292].

To, da je funkcija zanemarljiva pomeni, da se v neskonˇcnosti zelo hitro bliˇza niˇcli. Formalna definicija je zapisana v viru [4, stran 28] in pravi:

Definicija 2.3. Za funkcijo f : N → R reˇcemo, da je zanemarljiva, ˇce za vsak c ∈ R⁺ obstaja tak n₀ ∈ N, da za vsako celo ˇstevilo n ≥ n₀, velja

|f(n)|<1/n^c.

2.4.3 Aktivni napadalec

Aktivni napadalci lahko spremenijo vsebino sporoˇcil oziroma podatkov. Takˇsni napadalci torej ogroˇzajo tudi celovitost besedil. Za aktivne napade ˇstejemo:

• napad z izbranim kriptogramom (angl. choosen ciphertext attack) ali CCA,

• prilagodljivi napad z izbranim kriptogramom (angl. adaptive chosen ciphertext attack) ali CCA2.

2.4.4 Napad z izbranim kriptogramom

Za dani kriptosistem S = (K,M,C,E,D), napadalca A ter izzivalca je var- nost pred napadom z izbranim kriptogramom definirana z naslednjo igro [4, stran 357]. Za p∈ {0,1} definiramo poskus p:

• Izzivalec si izbere nakljuˇcen kljuˇc k ←− K.^R

• NapadalecA nato sproˇzi nekaj poizvedb proti izzivalcu in poizvedba je lahko ena od dveh vrst:

– Sifrirna poizvedba, kjer jeˇ i-ta takˇsna poizvedba sestavljena iz para sporoˇcil (m_i0, m_i1)∈ M². Izzivalec nato izraˇcuna kriptogramc_i = E(k, m_ip) in ga poˇsljeA-ju,

– Deˇsifrirna poizvedba, kjer je j-ta takˇsna poizvedba sestavljena iz kriptograma ˆc_j ∈ C, ki ni en od prejetih kriptogramov, ki je bil odgovor izzivalca na ˇsifrirno poizvedbo, torej:

ˆ

c_j ∈ {c/ ₁, c₂, ...}.

Izzivalec nato izraˇcuna besedilo ˆmj =D(k,ˆcj) in ga poˇslje napa- dalcu A.

• Napadalec nato vrne ˆp∈ {0,1}

Naj bo W_b dogodek, kjer A na koncu poskusa p vrne 1. Tedaj prednost A glede na kriptosistem S definiramo kot :

CCAadv[A,S] := |P r[W₀]−P r[W₁]|.

Diplomska naloga 19 Definicija 2.4. Za kriptosistem S pravimo, da je semantiˇcno varen pred napadom z izbranim kriptogramom (angl. semantically secure against chosen ciphertext attack) oziromaCCA-varen, ˇce je za vsakega nasprotnika A, ˇcigar napadi so ˇcasovno uˇcinkoviti (polinomski), vrednost CCAadv[A, S]zanemar- ljiva.

Povedano enostavneje, ˇce je napadalec vraˇcal 0 in 1 neodvisno od tega, ali je izzivalec izvajal poskus p = 0 ali p = 1, potem napadalec ni vedel kateri poskus je izzivalec izvajal. Poslediˇcno, napadalec ni vedel, ali je izzi- valec ˇsifriral sporoˇcilo m_i0 ali m_i1. Sledi torej, da napadalec ni razloˇcil med kriptogramoma sporoˇcilm_i0 ter m_i1.

Igra se zdi zelo podobna igri, ki smo jo navedli v podrazdelku 2.4.2, vendar moramo biti pozorni na to, da lahko napadalec v tej razliˇcici igre sproˇzi tudi deˇsifrirno poizvedbo. To pa je dodatno oroˇzje, saj ima napadalec tako veˇc podatkov iz katerih lahko sklepa o kriptogramih sporoˇcilmi0 ter mi1. Iz tega je razvidno, da CCA-varnost pomeni viˇsji nivo varnosti kot CPA-varnost.

2.5 AES

Primer bloˇcne ˇsifre je napredni ˇsifrirni standard (angl. Advanced Encryp- tion Standard) oziroma AES. AES je leta 2001 vzpostavil Ameriˇski narodni urad za standarde in tehnologijo (NIST) in je trenutno standard za ˇsifriranje obˇcutljivih podatkov. ˇSifra je manj znana pod prvotnim imenom Rijndael bloˇcna ˇsifra (angl. The Rijndael Block Cipher) po Joanu Daemenu ter Vin- centu Rijmenu, ki sta jo iznaˇsla [3] in jo predloˇzila nateˇcaju, ki ga je razpisal NIST. AES velja za eno najvarnejˇsih ˇsifer in je pogosto temelj ˇsifrirnih sis- temov.

AES je iterativna bloˇcna ˇsifra, z bloki dolˇzine 128 bitov, kljuˇci pa so lahko treh dolˇzin in sicer so lahko 128, 192 ali 256 bitni. To, da je AES ite- rativna ˇsifra pomeni, da je sestavljena iz kroˇzne funkcije, razporeda kljuˇcev ter ˇsifriranja skozi Nr podobnih krogov. Z zaˇcetnim nakljuˇcnim binarnim kljuˇcem K doloˇcene dolˇzine, generiramo podkljuˇce, ki jih uporabimo v vsa-

kem krogu algoritma. Podkljuˇce imenujemo kroˇzni kljuˇci in jih oznaˇcimo z K¹, ..., K^Nr. Seznamu kroˇznih kljuˇcev (K¹, ..., K^Nr) pravimorazpored kljuˇcev.

Kroˇzna funkcija g sprejme dva argumenta in sicer kroˇzni kljuˇc (K^r) ter tekoˇce stanje (w^r−1) in z njima generira naslednje stanje w^r=g(w^r−1, K^r).

AES je simetriˇcna ˇsifra kar pomeni, da za ˇsifriranje in deˇsifriranje uporabi isti kljuˇc. Deˇsifriranje je moˇzno tedaj, ko je funkcija g injektivna za vsak fiksen kljuˇc K. To pomeni, da za vsak kljuˇc K in stanje w, obstaja g⁻¹, da velja:

g⁻¹(g(w, K), K) =w.

Oglejmo si, kako izgleda ˇsifriranje. Naj boxbesedilo, ki ga ˇzelimo ˇsifrirati.

Tedajxvzamemo za zaˇcetno stanjew₀. Kriptogramyje stanje poN_r krogih, torej:

y=g(g(...g(g(x, K¹), K²)..., K^Nr−1), K^Nr).

Deˇsifriranje, tedaj izgleda takole:

x=g⁻¹(g⁻¹(...g⁻¹(g⁻¹(y, K^Nr), K^Nr−1)..., K²), K¹).

Kroˇzna funkcija je pri AES (razen za zadnji krog) sestavljena iz substi- tucije (zamenjave zlogov), permutacije (permutacije mest), linearne trans- formacije in priˇstevanja kljuˇca. S tem je poskrbljeno, da je vsak znak krip- tograma odvisen od vseh znakov sporoˇcila (razprˇsitev) in da je zveza med kriptogramom in kljuˇcem ˇcim bolj zapletena, nelinearna (zmeda) [3].

Poglavje 3

Zgoˇ sˇ cevalne funkcije in celovitost

Zgoˇsˇcevalna funcija (angl. hash function) je funkcija, ki besedilu poljubne dolˇzine priredi niz fiksne dolˇzine. Tak prirejeni niz imenujemo izvleˇcek.

Zaˇzeljeno je, da je raˇcunanje izvleˇcka hitro in enostavno ter da izvleˇcek iz- gleda kot nakljuˇcen niz. ˇCe se torej dve besedili malo razlikujeta, ˇzelimo, da njuna izvleˇcka izgledata povsem drugaˇcna.

Uporaba zgoˇsˇcevalnih funkcij je moˇcno narastla tudi s popularnostjo krip- tovalut. Znana kriptovaluta bitcoin uporablja zgoˇsˇcevalno funkcijo SHA-256 (SHA je kratica za Secure Hash Algorithm oziroma varen zgoˇsˇcevalni algo- ritem) za zgoˇsˇcevanje uporabnikovega javnega kljuˇca za kreiranje javnega naslova. S tem zavaruje uporabnikovo identiteto, zgoˇsˇcen naslov pa je tudi krajˇsi kot javni kljuˇc kriptovalute bitcoin, kar pripomore k laˇzjemu shranje- vanju. Tudi tako imenovanorudarjenje kriptovalut (angl. mining) je proces, ki vkljuˇcuje raˇcunanje zgoˇsˇcevalne funkcije SHA-256.

Zgoˇsˇcevalne funcije pa so uporabne tudi izven podroˇcja kriptografije. Pri- ljubljen programski jezik Python na primer uporablja zgoˇsˇcevalne funcije za hitro delovanje podatkovne strukture imenovane slovar (angl. dictio- nary) [23].

Kadar ˇzelimo zgoˇsˇcevalne funkcije uporabiti za potrebe kriptografije, ˇzeli- 21

mo, da izpolnjujejo dodatne lastnosti. Zahtevamo, da je raˇcunsko nemogoˇce:

• za poljuben izvleˇcek z poiskati besedilo, kateremu zgoˇsˇcevalna funkcija priredi izvleˇcek z (odpornost praslik),

• za dano sporoˇcilo poiskati drugaˇcno sporoˇcilo z enakim izvleˇckom (od- pornost drugih praslik),

• poiskati dve razliˇcni sporoˇcili z enakim izvleˇckom (odpornost na trke).

Enostavno je opaziti, kako lahko zgoˇsˇcevalne funkcije pripomorejo k pre- verjanju celovitosti besedila. Kot ˇze reˇceno, je o celovitosti besedila govora takrat, ko nas zanima, ali smo prejeli enako sporoˇcilo, kot je bilo poslano, ali je bilo to spremenjeno. ˇCe je bilo sporoˇcilo spremenjeno, bo izvleˇcek preje- tega besedila (zelo verjetno) izgledal drugaˇce kot izvleˇcek prvotnega besedila.

Prednost primerjave izvleˇckov pa je ta, da je izvleˇcek obiˇcajno kratek, torej nam ni potrebno primerjati celotnega besedila, ampak lahko primerjamo le izvleˇcka.

3.1 Celovitost kriptograma

Potreba po ohranjanju celovitosti besedil se pojavi tako pri poˇsiljanju besedil, kot tudi hranjenju le-teh. Ce zagotovimo celovitost besedil, se lahko naˇ primer izognemo neˇzeljenim spremembam podatkov na naˇsih trdih diskih ali v podatkovnih bazah. ˇCe je neka ˇsifra odporna na spremembe informacij v sporoˇcilu z neavtoriziranimi sredstvi, reˇcemo, da ˇsifra zagotavlja celovitost kriptograma.

Celovitost je za potrebe ˇsifriranja z avtentikacijo definirana z igro celovi- tosti kriptograma (angl. Ciphertext integrity game) [4, strani 353-354]. V igri spet nastopata izzivalec in napadalecA. Za kriptosistemS = (K,M,C,E,D) in za danega nasprotnika (napadalca) A, so tedaj pravila igre sledeˇca:

• Izzivalec si izbere nakljuˇcen kljuˇc k ←− K.^R

Diplomska naloga 23

• Napadalec A izbere nekaj sporoˇcil iz mnoˇzice M in sproˇzi nekaj poi- zvedb izzivalcu, kjeri-ta poizvedba vsebujei-to sporoˇcilo, ki ga oznaˇcimo zm_i. Izzivalec izraˇcuna c_i =E_k(m_i) in c_i posreduje A-ju.

• Na koncu A odda kandidat za kriptogram c ∈ C, ki ni vsebovan v mnoˇzici kriptogramov, ki jih prejel od izzivalca, torej c /∈ {c₁, c₂, ...}.

Slika 3.1: Igra celovitosti kriptograma

Pravimo, da napadalec A zmaga, ˇce je c veljaven kriptogram s kljuˇcem k, torej obstaja neko sporoˇcilom, da jeD_k(c) = m. S CIadv[A,E] (iz angleˇskega izrazacyphertext integrity advantage) oznaˇcimo verjetnost, da boA zmagal.

Definicija 3.1. Pravimo, da sistem S = (K,M,C,E,D) zagotavlja celovi- tost kriptograma (angl. ciphertext integrity), ˇce je za vsakega nasprotnika A, ˇcigar napadi so ˇcasovno uˇcinkoviti (polinomski), vrednost CIadv[A,E] zanemarljiva.

Ce napadalec z dovolj veliko verjetnostjo ne zna sestaviti ustreznega krip-ˇ tograma, tedaj tudi ne more spremeniti obstojeˇcega besedila, saj bi to po- menilo, da je znal sestaviti veljaven kriptogram.

3.2 Zgoˇ sˇ cevalna funkcija s kljuˇ cem

Zgoˇsˇcevalna funkcija s kljuˇcemali krajˇseMAC (angl. Message authentication code) je zgoˇsˇcevalna funcija, ki zgoˇsˇcuje podatke glede na podan kljuˇc. Kot

vhodni podatek vzame kljuˇc in sporoˇcilo, ki ga ˇzelimo zgostiti, in vrne znaˇcko, ki jo vˇcasih poimenujemo karMAC sporoˇcila. MAC ali zgoˇsˇcevalna funkcija s kljuˇcem je definirana na sledeˇc naˇcin [4, stran 214].

Definicija 3.2. Zgoˇsˇcevalna funkcija s kljuˇcem nad (K,M,T) je par uˇcinkovi- tih algoritmov S in V, kjer S imenujemo algoritem za podpisovanje V pa algoritem za overjanje. Mnoˇzica Mje konˇcna mnoˇzica besedil, K je konˇcna mnoˇzica kljuˇcev in T je konˇcna mnoˇzica znaˇck. Algoritem S uporabljamo za generiranje znaˇck, algoritemV pa za preverjanje znaˇck. Naj bo k kljuˇc iz mnoˇzice kljuˇcevK,m sporoˇcilo iz mnoˇzice sporoˇcilMint znaˇcka iz mnoˇzice znaˇck T. Tedaj:

• V :K ×M×T → {sprejmem, zavrnem}je deterministiˇcen algoritem, torej tak, ki ob enakih vhodnih podatkih vrne enak rezultat. Vrednost, ki jo vrne pa je

”sprejmem“ ali pa

”zavrnem“.

• S :K × M → T je lahko verjetnostni ali pa deterministiˇcen algoritem.

• Zahtevamo, da za vsak kljuˇc k ∈ K in vsako sporoˇcilo m∈ M, algori- tem V sprejme znaˇcko t, ki jo je generiral algoritem S.

3.2.1 Igra napada na zgoˇ sˇ cevalno funkcijo s kljuˇ cem

V novejˇsi literaturi je varnost zgoˇsˇcevalne funkcije s kljuˇcem definirana z igro napada na zgoˇsˇcevalno funkcijo [4, strani 214-216]. Recimo, da nasprotnik A napade MAC sistem I = (S, V), mi pa smo v vlogi izzivalca. Naj bo k nakljuˇcno izbran kljuˇc iz mnoˇziceK. Nasprotniku dopustimo, da za poljubno sporoˇcilo m povpraˇsa o znaˇcki t = S(k, m). Nasprotnik si lahko pridobi poljubno ˇstevilo parov sporoˇcilo-znaˇcka, ki jih imenujemo podpisani pari. V konkretnem primeru bi to ˇstevilo seveda omejili, vendar bi v teoriji lahko bilo teh parov poljubno mnogo. Takˇsen napad imenujemo napad z izbranim sporoˇcilom (angl. chosen message attack).

Sedaj pa nasprotnika izzovemo, da proizvede nov par (m, t), torej takˇsen, ki ni v mnoˇzici podpisanih parov, ki smo mu jih poslali. Za sporoˇcilo m ne

Diplomska naloga 25 zahtevamo, da je smiselno in je lahko popolnoma nakljuˇcno. Tak nov par imenujemoobstojeˇca MAC poneverba (angl. existential MAC forgery).

Sistem oznaˇcimo zavaren, ˇce nasprotnik, kljub izvedbi napada z izbranim sporoˇcilom, torej dejstvu, da si je priskrbel veliko ˇstevilo podpisanih parov, ne more ustvariti obstojeˇce MAC poneverbe.

Bolj formalno so za zgoˇsˇcevalno funkcijo s kljuˇcemI = (S, V) nad (K,M,T), izzivalca in za danega nasprotnika (napadalca) A, pravila igre sledeˇca:

• Izzivalec si izbere nakljuˇcen kljuˇc k←^R− K.

• Nasprotnik A nekajkrat sproˇzi poizvedbo proti izzivalcu, kjer i-ta po- izvedba vsebuje sporoˇcilo m_i ∈ M. Izzivalec izraˇcuna t_i =S(k, m_i) in ti posreduje A-ju.

• Sˇcasoma A odda kandidata za ponarejeni par (m, t) ∈ M × T, ki ni vsebovan v mnoˇzici podpisanih parov. Za takˇsen par (m, t) torej velja (m, t)∈ {(m/ 1, t1),(m2, t2), ...,(mn, tn)}.

Igro si lahko ogledamo na sliki 3.2.

Pravimo, da A zmaga, ˇce je (m, t) veljaven par s kljuˇcem k, torej velja V(k, m, t) =

”sprejmem“. Z MACadv[A,I] oznaˇcimo verjetnost, da bo A zmagal proti sistemuI.

Definicija 3.3. Pravimo, da je MAC sistem I MAC-varen (angl. MAC- secure), ˇce je za vsakega nasprotnika A, ˇcigar napadi so ˇcasovno uˇcinkoviti (polinomski), vrednost MACadv[A,I] zanemarljiva.

MAC sistem je torej MAC-varen, ˇce nasprotnik dovolj verjetno ne zna pravilno podpisati nakljuˇcnega sporoˇcila m, kljub temu, da si lahko priskrbi poljubno ˇstevilo primerov podpisanih sporoˇcil.

Slika 3.2: Igra napada na zgoˇsˇcevalno funkcijo s kljuˇcem

3.2.2 GHASH - primer zgoˇ sˇ cevalne funkcije s kljuˇ cem

Naj boX ={0,1}¹²⁸in`= 2<sup>32</sup>−1. GHASH je zgoˇsˇcevalna funkcija s kljuˇcem nad (K,M,T), kjer jeK =T =X in M=X<sup>≤`</sup> =∪^`_i=1Xⁱ. ElementeX si lahko predstavljamo kot elemente konˇcnega obsega GF(2¹²⁸), ki je definiran z nerazcepnim polinomomg(x) := x¹²⁸+x⁷+x²+x+ 1. Elementi obsega so polinomi stopnje manj kot 128 s koeficienti iz GF(2), ki jih lahko predstavimo kot 128-bitne nize: bit na mestu i predstavlja koeficient prixⁱ⁻¹. Seˇstevanje elementov obsega je potem kar seˇstevanje nizov po komponentah po modulu dva, torej operacija XOR. Dva elementa pa zmnoˇzimo tako, da zmnoˇzimo ustrezna polinoma in vzamemo ostanek pri deljenju s polinomom g(x). Do- bimo spet polinom stopnje manj kot 128, ki ga lahko gledamo kot niz dolˇzine 128. Naj bo k ∈ Kin z ∈ M, recimo, daz ∈ X^v. Potem GHASH(k, z) vrne vrednost polinoma s koeficienti z v toˇckik ∈GF(2¹²⁸), torej

GHASH(k, z) =z[0]k^v +z[1]k^v−1+· · ·+z[v−1]k ∈GF(2¹²⁸). (3.1) Vrednost polinoma obiˇcajno izraˇcunamo iterativno s Hornerjevim algorit- mom. ˇCe napadalec kljuˇca k ne pozna, potem tudi ne more izraˇcunati vre- dnosti polinoma v tej toˇcki.

Kot bomo videli kasneje, je GHASH funkcija, ki jo za pridobivanje znaˇcke uporablja algoritem GCM. Sluˇzi za zgoˇsˇcevanje pridruˇzenih podatkov. Pri- druˇzeni podatki (angl. associated data) so podatki, ki jih poˇsljemo skupaj

Diplomska naloga 27 s kriptogramom in o njem nosijo informacije. ˇCe bi na primer ˇsifrirali po- datke o omreˇznem protokolu, bi v pridruˇzene podatke zapisali naslove, pri- kljuˇcke, ˇstevilko verzije protokola in pa na primer podatke o tem, kako rav- nati s kriptogramom. Pozorni moramo biti na to, da med pridruˇzene po- datke ne vkljuˇcimo informacij, za katere ˇzelimo, da ostanejo tajne, saj namen zgoˇsˇcevanja ni ˇsifriranje.

Pridruˇzene podatke lahko uporabimo tudi za zagotavljanje dodatne var- nosti kriptograma. Zavarujejo nas lahko na primer pred napadi s strani ad- ministratorja podatkovnih baz. Recimo, da imamo v podatkovni bazi shra- njene osebe in je eden od atributov oseb njihovo banˇcno stanje. ˇCe tudi bi bili podatki o osebah ˇsifrirani in neberljivi, bi uporavljalec podatkovne baze lahko zamenjal banˇcni stanji dveh oseb in tako ne bi rabil niˇcesar ˇsifrirati ali deˇsifrirati. ˇCe bi v shranjevanju podatkov v podatkovno bazo uporabili pri- druˇzene podatke, se to ne bi moglo zgoditi. V pridruˇzene podatke banˇcnega stanja bi na primer zapisali, kateri osebi to stanje pripada. Deˇsifrirni posto- pek bi ob zamenjavi dveh stanj opazil nepravilnost in deˇsifrirnja ne bi izvrˇsil do konca. Opis funkcije GHASH iz 3.1 bomo zapisali ˇse v obliki algoritma (povzeto po [15]).

Naj bosta n in u para pozitivnih celih ˇstevil takˇsna, da je ˇstevilo bitov kriptograma c enako (n−1)·128 +u, kjer je 1 ≤ u ≤ 128. Kriptogram je sestavljen iz zaporedja n 128-bitnih nizov in dodatnega niza, ki je velikosti u bitov. Kriptogram c razdelimo na zaporedje c₁, c₂, ..., cn−1, c^∗_n in vsakega od nizov c_i za i = 1, ..., n, imenujemo blok. Niz c^∗_n vsebuje u bitov, torej morda ni 128-biten in velja c=c₁ k c₂ k...kcn−1 kc^∗_n. Pridruˇzene podatke a oznaˇcimo kot a₁, a₂, ..., am−1, a^∗_m, kjer je ˇstevilo bitov bloka a^∗_m enako v, kar morda ni enako 128. Tako sta m in v takˇsni pozitivni ˇstevili, da je ˇstevilo bitov pridruˇzenih podatkova enako (m−1)·128 +v in 1≤v ≤128.

Zgoˇsˇcevalni kljuˇc oznaˇcimo s h. Niz 128-ih zaporednih niˇcel oznaˇcimo z 0¹²⁸, len(a) pa je 64-bitni zapis ˇstevila bitov argumenta a.

Tedaj funkcija GHASH izgleda takole:

1: procedure GHASH(h, a, c)

2: t= 0

3: for i=1 to m-1 do

4: t =mnoˇzi(t⊕a_i, h) . Algoritem mnoˇzi je definiran spodaj

5: t=mnoˇzi(t⊕(a^∗_m k0^128−v), h)

6: for i=m+1 to m+n-1 do

7: t =mnoˇzi(t⊕c_i, h)

8: t= (t⊕(c^∗_m k0^128−u), h)

9: t=mnoˇzi(t⊕(len(a)klen(c)), h)

10: return t . Vrnemo znaˇcko

Zapiˇsimo ˇse algoritem za mnoˇzenje v GF(2¹²⁸), ki smo ga uporabili zgoraj.

Naj velja X, Y, Z ∈ GF(2¹²⁸). Naj X_i oznaˇcuje i-ti bit n-bitnega ˇstevila X.

Najbolj levi bit ˇstevilaX torej oznaˇcimo zX₀, najbolj desnega pa zX₁₂₇. Za konstanto R naj velja R = 11100001||0¹²⁰. Funkcija rightshift(V) premakne bite ˇstevilaV za eno mesto v desno, torej, ˇce veljaW =rightshift(V), je tedaj W_i =Vi−1 za 1 ≤i≤127 in W₀ = 0. Tedaj algoritem za mnoˇzenje ˇstevil X inY izgleda takole:

1: procedure mnoˇzi(X, Y)

2: Z ←0

3: V ←X

4: for i= 0 to i= 127 do

5: if Y_i == 1 then

6: Z ←Z⊕V

7: if V127 == 0 then

8: V ← rightshift(V)

9: else

10: V ← rightshift(V)⊕R

11: return Z

Poglavje 4

Sifriranje z avtentikacijo ˇ

Namen ˇsifriranja z avtentikacijo je ta, da hkrati nudi tako zaupnost kot ve- rodostojnost - preverjen izvor ter celovitost - podatkov. Takˇsno ˇsifriranje je namenjeno obrambi pred najmoˇcnejˇsimi napadalci, ki lahko napadajo tako poˇsiljatelja kot tudi prejemnika, torej je lahko ogroˇzen tako ˇsifrirni, kot deˇsifrirni postopek. Pomemben del takˇsne enkripcije je tudi to, da zavraˇca deˇsifriranje napaˇcno zgrajenih kriptogramov, kar je pogosto del napadalskih taktik. ˇCe sistem nudi enkripcijo z avtentikacijo, reˇcemo, da je sistem AE- varen (angl. AE-secure). V nadaljevanju sledimo knjigi Dana Boneha in Victorja Shoupa [4].

Definicija 4.1. ˇSifra jeAE-varna, ˇce je CPA-varna in zagotavlja celovitost kriptograma, ki je definirana z igro celovitosti kriptograma.

Razlog, zakaj je ˇsifriranje z avtentikacijo tako pomembno, je to, da je definicija AE-varnega sistema relativno nezahtevna, vendar pa je rezultat AE-varnega sistema izjemno moˇcna obramba pred ˇstevilnimi napadi. Zah- tevamo le, da je sistem CPA-varen in zagotavlja celovitost kriptograma, v zameno pa dobimo zagotovilo, da je takˇsen sistem tudi CCA-varen. Na- mesto da bi neposredno dokazovali, da je nek sistem CCA-varen, je dovolj dokazati le, da je CPA-varen in da zagotavlja celovitost kriptograma, to pa je zadosten pogoj za to, da je sistem tudi CCA-varen.

29

Ce ponazorimo z zgledom napada. Recimo, da Ana poˇslje Blaˇˇ zu nekaj sporoˇcil ˇsifriranih z AE-varnim kriptosistemom S, preko javnega omreˇzja.

Recimo, da je pogovoru prisoten tudi napadalec A. Ker je sistem S CPA- varen, prepreˇcuje napadalcu, da bi ta izvedel kaj o sporoˇcilih, ki jih je Ana poslala Blaˇzu. Vendar, ali lahko napadalec poˇslje sporoˇcila Blaˇzu pod pre- tvezo, da so poslana sporoˇcila priˇsla od Ane? Trdimo, da se tudi to ne more zgoditi. Ana ˇsifrira sporoˇcilo m in generiran kriptogram cpoˇslje Blaˇzu. Re- cimo, da napadalecAprestreˇze kriptogramcin ˇzeli generirati tak kriptogram ˆ

c, da velja ˆm := D(k,c),ˆ mˆ 6= m in dekodirni postopek kriptograma ne za- vrne. Takˇsen ˆc bi Blaˇza prepriˇcal, da je Ana poslal sporoˇcilo ˆm namesto sporoˇcila m. Vendar, ˇce bi A lahko generiral takˇsen kriptogram ˆc, bi tedaj lahko zmagal igro celovitosti kriptograma, ker pa smo predpostavili, da sis- tem S zagotavlja celovitost kriptograma, to ni mogoˇce. Napadalec A torej ne more spremeniti kriptograma c, ne da bi bilo to mogoˇce zaznati, hkrati pa tudi ne more prelisiˇciti Blaˇza, da je neko sporoˇcilo poslala Ana in ne A sam.

Ce ˇsifriramo z avtentikacijo, se pogosto posluˇˇ zujemo tudi uporabe pri- druˇzenih podatkov [16]. Kot omenjeno v podrazdelku 3.2.2, so to podatki sporoˇcila, ki jih ne ˇsifriramo z namenom skrivanja informacij, ki jih nosijo, vendar pa sluˇzijo dodatni varnosti in informativnosti.

Za izgradnjo sistema za ˇsifriranje z avtentikacijo prednjaˇcita dva naˇcina.

Prvi naˇcin se imenuje generiˇcna sestava (angl. generic composition), ki zdruˇzuje CPA-varno ˇsifro z zgoˇsˇcevalno funkcijo s kljuˇcem (MAC). Drugi naˇcin se imenuje integrirane sheme (angl. integrated schemes), ki pa zgradi ˇsifriranje z avtentikacijo neposredno iz bloˇcne ˇsifre, ne da bi prej zgradili samostojno ˇsifro ali pa MAC.

4.1 Generiˇ cna sestava

Generiˇcno sestavo lahko izvedemo na tri naˇcine, ki se po uporabnosti raz- likujejo. Naj bo (K,M,C,E,D) kriptosistem in (S, V) zgoˇsˇcevalna funkcija

Diplomska naloga 31 s kljuˇcem nad (K,M,T). Naj bo k_enc ˇsifrirni kljuˇc, k_mac kljuˇc zgoˇsˇcevalne funcije s kljuˇcem inmsporoˇcilo, ki ga ˇzelimo ˇsifrirati. Tedaj naˇcine generiˇcne sestave razdelimo takole:

• Encrypt-and-MAC. ˇSifriramo sporoˇcilo m kot c ← Ekenc(m) ter za sporoˇcilo m izraˇcunamo znaˇcko t ← S(k_mac, m). Rezultat zapiˇsemo kot E_kenc(m)kM AC_kmac(m) oziroma ckt (zgled na sliki 4.1, desno).

Uporabo te paradigme najdemo pri protokolu SSH [14].

• MAC-then-Encrypt. Za sporoˇcilo m najprej izraˇcunamo znaˇcko t ←S(k_mac, m) in nato ˇsifriramo znaˇcko t, torej c← Ek_enc(t). Rezul- tat je kriptogram c, ki ga zapiˇsemo z nizom E_kenc(m k M AC_kmac(m)) oziroma c (zgled na sredini slike 4.1). Primer protokola, ki uporablja to paradigmo je IPSEC, na katerem je zgrajena internetna plast navi- deznih zasebnih omreˇzij (angl. virtual private network ali VPN) [30].

• Encrypt-then-MAC. ˇSifriramo sporoˇcilom tako, da pridobimo krip- togram c ← Ek_enc(m) in za kriptogram c izraˇcunamo znaˇcko t ← S(k_mac, c). Rezultat je par (c, t), kar zapiˇsemo z nizom E_kenc(m) k M AC_kmac(E_kenc(m)) oziroma c k t (zgled na sliki 4.1, levo). Takˇsne paradigme se posluˇzuje protokol SSL [7].

Slika 4.1: Vizualna predstavitev rezultatov paradigem generiˇcne sestave Opiˇsimo vsakega od naˇcinov za generiˇcno sestavo podrobneje.

4.1.1 Encrypt-and-MAC (EaM)

ParadigmaEncrypt-and-MAC ne definira izvajanja zgoˇsˇcevalne funcije s kljuˇcem (MAC). Osnoven algoritem za podpisovanje pri tem naˇcinu uporablja deter- ministiˇcen algoritem in pri uporabi le tega, se lahko pojavijo teˇzave. Za primer vzemimo kontrolno vsoto. Recimo, da ˇsifriramo sporoˇcilo sestavljeno iz devetih ˇstevk, ˇcemur prikljuˇcim eno dodatno ne ˇsifrirano ˇstevko, ki je kontrolna vsota prvih devetih ˇstevk. ˇCe mi nekako uspe odkriti osem ˇstevk od devetih ˇsifriranih, lahko s pomoˇcjo kontrolne vsote odkrijem, katera je manjkajoˇca deveta ˇstevka.

Teˇzava je razvidna tudi iz zgoraj navedenega rezultata te paradigme Ekenc(m) k M ACkmac(m). Zadnji del rezultata (M ACkmac(m)) bo pri de- termistiˇcnem MAC-u in istem sporoˇcilu enak. ˇCe torej napadalec poseduje kriptogram ˇsifriran s to paradigmo, lahko poskuˇsa ˇsifrirati razliˇcna sporoˇcila in opazuje, za kateri kriptogram bo MAC enak temu zadnjemu delu kripto- grama, ki ga ˇzeli deˇsifrirati. ˇCe ugane takˇsno sporoˇcilom, da bo kriptogramc tega sporoˇcilo imel enak izvleˇcek, kot ga napadalec opazi pri zadnje delu pre- streˇzenega sporoˇcila, potem je sporoˇcilomzelo verjetno enako prestreˇzenemu sporoˇcilu.

Sledi, da naˇcin Encrypt-and-MAC ni najbolj primeren za doseganje ciljev ˇsifriranja z avtentikacijo.

4.1.2 MAC-then-encrypt (MtE)

Nepraktiˇcnost naˇcina MtE je, da skupaj z besedilom ˇsifrira tudi MAC. Tako ne moremo preveriti celovitosti sporoˇcila, ne da bi prej deˇsifrirali celotno sporoˇcilo, kar pomeni potencialno zapravljanje raˇcunskih virov, saj morda deˇsifriramo sporoˇcilo, ki je bilo spremenjeno.

Obstajajo pa tudi primeri uporabe CPA-varnih ˇsifer skupaj z varnim MAC-om, ki ob uporabi naˇcina MtE ustvarijo sistem, ki ni nujno AE-varen, glej [4, 364-366], kjer je opisan napad, imenovan padding oracle attack on SLL.

Diplomska naloga 33

4.1.3 Encrypt-then-MAC (EtM)

Naj bo kriptosistemS = (K,M,C,E,D) in naj bo I = (S, V) sistem MAC, definiran nad (K_m,C,T). Sistem encrypt-then-MAC E_EtM = (E_EtM, D_EtM) je definiran kot:

EEtM((ke, km), m) := (c, t); c←Eke(m), t←S(km, c) D_EtM((k_e, k_m),(c, t)) :=

( zavrnem D_ke(c)

; ˇceV(k_m, c, t) vrne

”zavrnem“

; sicer

)

Sistem EtM je definiran nad (K_e× K_m,M,C × T). Pokazati je mogoˇce, da sistem E_EtM = (E_EtM, D_EtM) nudi ˇsifriranje z avtentikacijo (dokaz najdemo v [4, strani 362-363]).

Prav tako pa tudi znaˇcka, izraˇcunana za kriptogram, jamˇci nespremenje- nost le-tega. V tem primeru napadalec ne more iz MAC-a pridobiti nobenih informacij o sporoˇcilu, saj je znaˇcka dobljena le iz kriptograma, ki sesta- vlja prvi del prestreˇzenega besedila, in ne iz golega besedila. Tako nam ni potrebno skrbeti za varnost funkcije MAC, saj v tem primeru sluˇzi le podpisovanju. V najslabˇsem primeru, ˇce napadalec uspe razbiti MAC, dobi le kriptogram prvotnega besedila, ne pa tudi besedila. Tako je paradigma Encrypt-then-MAC najbolj primerna za doseganje cilje ˇsifriranja z avtenti- kacijo, uporabnikom pa je priporoˇcena uporaba ˇze obstojeˇcih ˇsifrirnih stan- dardov, kot je na primerGalois counter mode aliGCM na kratko.

4.1.4 Naˇ cin GCM

Naˇcin GCM zdruˇzi delovanje varne zgoˇsˇcevalne funkcije s kljuˇcem (MAC) ter CPA-varne ˇsifre, na primer AES. Naˇcin GCM je AEAD shema (angl. Authen- ticated Encryption with Associated Data), kar pomeni, da nudi ˇsifriranje z avtentikacijo s pridruˇzenimi podatki. Algoritem GCM je mogoˇce opisati na veˇc razliˇcnih naˇcinov, v delu sem sledil viroma [4, 15].

Naj bo kriptosistemS = (K,M,C,E,D) bloˇcna ˇsifra za katero veljaM= C ={0,1}¹²⁸. Naj bo b ∈ {0,1}^∗ besedilo in a ∈ {0,1}^∗ pridruˇzeni podatki.

Naj bosta n in u para naravnih ˇstevil, takˇsna, da je ˇstevilo bitov besedila b enako (n − 1)· 128 +u, kjer je 1 ≤ u ≤ 128. Besedilo je sestavljeno iz zaporedja n 128-bitnih nizov in dodatnega niza, ki je velikosti u bitov.

Besedilo b razdelimo na zaporedjeb₁, b₂, ..., bn−1, b^∗_n in vsakega od nizov b_i za i = 1, ..., n imenujem blok. Niz b^∗_n morda ni polne velikosti, torej morda ni 128-biten. Veljab =b₁ kb₂ k...kbn−1 kb^∗_n. Prav tako razdelimo pridruˇzene podatke a=a₁ ka₂ k...kam−1 ka^∗_m, kjer je ˇstevilo bitov blokaa^∗_m enako v, kar je morda manjˇse kot 128. Tako sta m in v takˇsni naravni ˇstevili, da je ˇstevilo bitov pridruˇzenih podatkov aenako (m−1)·128 +v in 1≤v ≤128.

Naj bo N 128-bitno ˇstevilo, ki ga bomo uporabili le enkrat. ˇStevilo N imenujemo tudi nonce iz angleˇskega izraza

”number only used once“. Tedaj ˇsifriranje pri algoritmu GCM, ki si ga lahko ogledamo tudi na sliki 4.2, izgleda takole:

1: procedureGCM-encypher(kljuˇck, sporoˇcilob, pridruˇzeni po- datki a, nonce N)

2: h←E_k(0¹²⁸) . generiraj kljuˇc za GHASH

3: N⁰ ←incr(N) . zaˇcetna vrednost ˇstevca

4: c←prazen niz

5: for i=1 to n-1 do

6: . b_i je i-ti blok sporoˇcila in c_i je i-ti blok kriptograma

7: ci =bi⊕Ek(N⁰)

8: c=ckc_i

9: N⁰ ←incr(N⁰)

10: . funkcija MSB vrne prvih u bitov niza Ek(N⁰) iz leve proti desni

11: c^∗_n=b^∗_n⊕M SB_u(E_k(N⁰))

12: c=ckc^∗_n

13: t=M SB_z(GHASH(h, a, c)⊕E_k(N))

14: return (c, t)

Diplomska naloga 35

Slika 4.2: Postopek ˇsifriranja. Za enostavnejˇso predstavitev kodiramo le en blok pridruˇzenih podatkov in dva bloka besedila. E_k oznaˇcuje ˇsifriranje bloka s kljuˇcem k, mult_h pa mnoˇzenje z zgoˇsˇcevalnim kljuˇcem h v GF(2¹²⁸), incr pa oznaˇcuje poveˇcanje ˇstevca N⁰.

Vsako sporoˇcilo, ki ga ˇzelimo poslati mora biti krajˇse kot 2³² blokov, pri- poroˇceno pa je, da z istim kljuˇcem ne ˇsifriramo veˇc kot 2³² sporoˇcil. Dolˇzino znaˇcke t lahko poljubno skrˇcimo s parametrom z, ki definira njeno velikost.

Oglejmo si, kako pri GCM poteka deˇsifriranje.

Algoritem za deˇsifriranje kot vhod vzame kljuˇc k ∈ K, par kriptogram- znaˇcka (c, t)∈ C ×T, pridruˇzene podatkea∈ Mter ˇstevilo nonceN. Algori- tem najprej izraˇcuna ˇsifrirni kljuˇc za funkcijo GHASH, torejh←Ek(0¹²⁸) in preveri ustreznost znaˇcke t. ˇCe je znaˇcka ustrezna, algoritem vrne deˇsifriran kriptogram c, torej besedilo b∈ M.

Deˇsifriranje torej izgleda takole:

1: procedure GCM-decypher(kljuˇc k, kriptogram c, znaˇcka t, pridruˇzeni podatki a, nonce N)

2: h←E_k(0¹²⁸) . generiraj kljuˇc za GHASH

3: t⁰ =MSB_z(GHASH(h, a, c)⊕E_k(N)

4: if t! =t⁰ then

5: return NAPAKA, znaˇcki se ne ujemata

6: p← prazen niz

7: for i=1 to ndo

8: N ←incr(N) . zaˇcetna vrednost ˇstevca

9: . b_i je i-ti blok sporoˇcila in c_i je i-ti blok kriptograma

10: b_i =c_i⊕E_k(N)

11: b=bkb_i

12: . funkcija MSB vrne prvih u bitov niza E_k(N) iz leve proti desni

13: b^∗_n=b^∗_n⊕M SB_u(E_k(N))

14: b =bkb^∗_n

15: return b

Opazimo, da je ˇsifriranje pri naˇcinu GCM podobno kot ˇsifriranje pri naˇcinu s ˇstevcem, ki smo ga opisali v podrazdelku 2.3.3. Na koncu ˇsifriranja le iz kriptogramov in pridruˇzenih podatkov izraˇcunamo ˇse znaˇcko in jo vrnemo skupaj s kriptogramom. Pomembno je opaziti, da znaˇcko sestavimo iz krip-