Advanced Encryption Standard (AES)

Muista

Vaikka kuudennessa moduulissa käytetään AES-salainta esimerkkinä, tässä kappaleessa kuvatut toimintamoodit ovat yleisiä lohkosalaimien toimintamoodeja. AES on siis vain yksi lohkosalain muiden joukossa.

Nyt pääsemme käyttämään ensimmäistä oikeaa salainta. Tässä osiossa kuvataan AES-lohkosalaimen toimintaperiaate. Seuraavissa osioissa käytämme salainta eri tavoilla.

Kuten edellisessä moduulissa mainittiin, lähihistorian aikana käytössä on ollut salaimia, joista on sittemmin luovuttu Yksi tällaisista salaimista on DES (Data Encryption Standard) ja siitä tuotettu 3DES eli ’TripleDES’.

DES tarjosi 56-bittisen turvallisuuden ja 3DES 112-bittisen turvallisuuden. Yksi 3DES-salauksen ongelma oli, että se vaati 168-bittisen avaimen saavuttaakseen 112-bittisen turvallisuuden. Tämä on yksi esimerkki tilanteesta, jossa avaimen pituus ei määritä turvallisuutta bitteinä. Muistutukseksi: 128-bittisellä avaimella haluamme symmetrisen salaimen turvallisuuden olevan \((t, \frac{t}{2^{128}})\). Toinen ongelma DES salauksessa oli sen hitaus silloisissa prosessoreissa.

Yhdysvaltojen National Institute of Standards and Technology (NIST) järjesti aikoinaan kilpailun löytääkseen sopivan korvaajan DES:lle.

Kilpailun voitti Rijndael-salain, jota on kilpailun jälkeen kutsuttu AES-salaimeksi. AES-salaimen toiminnan yksi osa käyttää suomalaisen emeritaprofessori Kaisa Nybergin kehittämää matemaattista korvausalgoritmia.

AES-salain on esimerkki Kerkhoffs-periaatteen mukaisesta salaimesta:

• Salaimen algoritmi ja toiminta ovat täysin nähtävissä.

• Avain on salassa pidettävä tieto.

---

AES-salaimen toiminta

Käydään läpi AES-lohkosalaimen osat sekä toiminnallisuus. Alla oleva lohkokaavio kuvaa AES-salaimen toiminnan eri vaiheet.

• Lohkosalain muodostaa salattavasta datasta 128-bittisiä lohkoja.

• Yksi salaimelle sisään menevä 128-bittinen lohko pilkotaan edelleen 16 tilalohkoksi (engl. states), jotka yleensä kuvataan 4x4 matriisina.

• Tätä yhtä 128-bittistä datalohkoa manipuloidaan käsittelykierroksilla.

• Käsittelykierroksissa dataa muunnetaan substituutio-permutaatio-verkolla sekä salausavaimesta generoidulla kierrosavaimella. 16 tilalohkoa siis korvataan ja permutoidaan (eli transponoidaan) algoritmin sääntöjen mukaan.

• Salain palauttaa lopuksi datan 128-bittisenä kokonaisuutena.

Voit halutessasi opiskella kaikki AES salaimen toiminnan yksityiskohdat AES-standardista.

---

Data lohkoiksi, lohkot tiloiksi

AES-lohkosalain ottaa käsiteltäväksi 128-bittisen datan. Tämä on AES-lohkosalaimen lohkon koko. Tämä 128-bittinen data jaetaan kuudeksitoista 8-bittiseksi tilaksi (engl. state). Nämä 8-bittiset tilat järjestetään kaksiulotteiseksi taulukoiksi alla olevan kuvan mukaisesti.

Vastaa edellisen tekstin avulla seuraaviin väittämiin.

Kysymys 1

Valitse oikea vaihtoehto.

Lohkosalain ottaa käsiteltäväksi 128-bittisen datan.

Lohkosalain ottaa käsiteltäväksi 196-bittisen datan.

Lohkosalain ottaa käsiteltäväksi 256-bittisen datan.

Kysymys 2

Valitse oikea vaihtoehto.

Käsiteltävä datalohko jaetaan 4 tilaksi (state).

Käsiteltävä datalohko jaetaan 8 tilaksi (state).

Käsiteltävä datalohko jaetaan 16 tilaksi (state).

Kysymys 3

Valitse oikea vaihtoehto.

Tilat mallinnetaan yleensä 1-ulotteisena listana.

Tilat mallinnetaan yleensä 2-ulotteisena taulukkona.

Tilat mallinnetaan yleensä 3-ulotteisena kuutiona.

---

Käsittelykierrokset

AES:ssä tilojen (state) datalohkoja manipuloidaan käsittelykierroksilla. AES:ssä käsittelykierrosten määrä riippuu käytetyn avaimen pituudesta. Käsittelykierroksella yhtä kokonaista 128-bittistä datalohkoa työstetään manipuloimalla yhteensä kuuttatoista 8-bittistä tilaa.

• Jos avain on 128-bittinen, lohkot prosessoidaan 10:llä kierroksella.

• Jos avain on 192-bittinen, lohkot prosessoidaan 12:lla kierroksella.

• Jos avain on 256-bittinen, lohkot prosessoidaan 14:llä kierroksella.

---

Vastaa edellisen tekstin avulla seuraaviin väittämiin.

Kysymys 1

Valitse oikea vaihtoehto.

Jos avain on 128-bittinen, lohko prosessoidaan 10:llä kierroksella.

Jos avain on 192-bittinen, lohko prosessoidaan 14:llä kierroksella.

Jos avain on 256-bittinen, lohko prosessoidaan 12:lla kierroksella.

Kysymys 2

Valitse oikea vaihtoehto.

Jos avain on 128-bittinen, lohko prosessoidaan 14:llä kierroksella.

Jos avain on 192-bittinen, lohko prosessoidaan 12:lla kierroksella.

Jos avain on 256-bittinen, lohko prosessoidaan 10:llä kierroksella.

Kysymys 3

Valitse oikea vaihtoehto.

Jos avain on 128-bittinen, lohko prosessoidaan 12:lla kierroksella.

Jos avain on 192-bittinen, lohko prosessoidaan 10:llä kierroksella.

Jos avain on 256-bittinen, lohko prosessoidaan 14:llä kierroksella.

---

Jokaisella käsittelykierroksella suoritetaan seuraavat toimenpiteet. Englanninkieliset termit on esitetty suluissa helpottamaan standardin lukua:

• Aluksi data prosessoidaan XOR-funktiolla avaimesta generoidulla kierrosavaimella (round-key)

• Seuraavaksi tilan (state) sisältö korvataan. Tätä tavujen korvausta kutsutaan substituutioksi s-boksilla (substition-box)

• Tämän jälkeen permutoidaan tilalohkot riveittäin (shift rows)

• Sitten suoritetaan tilojen sarakkeittain permutaatio (mix columns)

• Tämän jälkeen jatketaan seuraavaan kierrokseen kunnes 128-bittistä lohkoa on prosessoitu niin monta kierrosta kuin avaimen pituus vaatii.

Vastaa edellisen tekstin avulla seuraaviin väittämiin.

Kysymys 1

Valitse oikea vaihtoehto.

Lohkoa käsitellään kierrosavaimella.

Lohkoa ei käsitellä avaimella, vaan ulostulossa käytetään avainta.

Tilat yhdistetään toisiinsa XOR-funktiolla.

Kysymys 2

Valitse oikea vaihtoehto.

Tilojen korvausta kutsutaan permutaatioksi.

Tilan (state) koko on 8 bittiä ja jokainen tila korvataan s-boksin määrittämällä korvauksella.

Kierrosavainta käytetään s-boksin kanssa.

Kysymys 3

Valitse oikea vaihtoehto.

Rivien tiloja (state) permutoidaan kierroksella s-boksin käytön jälkeen.

Rivien tiloja (state) permutoidaan kierroksella ennen s-boksin käyttöä.

Sarakkeittainen permutaatio suoritetaan kierroksella ennen rivi-permutointia.

Kysymys 4

Valitse oikea vaihtoehto.

Kierroksen toiminteet voidaan tehdä missä järjestyksessä tahansa.

Kierrosavainta käytetään, kun suoritetaan sarakkeittainen permutaatio.

Kierroksen viimeinen operaatio on sarakkeittainen permutaatio.

Kysymys 5

Valitse oikea vaihtoehto.

Jos kierrosavaimeksi tulee nollavektori eli kaikki bitit ovat nollia, kierrokset voi keskeyttää ja palauttaa salauksen tulos, koska XOR-funktion suorittaminen nollavektorilla ei ole järkevää.

Jos koko tilataulu on pelkkää nollaa, lopetetaan kierrosten prosessointi ja palautetaan salauksen tulos.

Se, mitä arvoja kierrosavain tai tilat saavat kesken käsittelyn, on irrelevanttia. Kaikki avaimen mukaiset kierrokset suoritetaan loppuun.

---

AES-avain ja kierrosavain (engl. key expansion)

AES-standardi hyväksyy avaimen pituudeksi joko 128 bittiä, 192 bittiä tai 256 bittiä. Esimerkeissä käytämme 128-bittistä avainta.

Jokaisella käsittelykierroksella AES:ssä lasketaan uusi efektiivinen kierrosavain. Kierrosavaimen tuottavaa algoritmia kutsutaan avainlaajennukseksi (engl. key expansion). Jos menetelmä ei käyttäisi avainlaajennusta, jokaisella käsittelykierroksella käyttäisimme dataan samaa alkuperäistä avainta, joka puolestaan mahdollistaisi erään liu’utus hyökkäyksen.

Salaimien koodaaminen on haastavaa ja edellisellä luennolla annoimme vakavan kehotuksen välttää kryptografian primitiivien koodaamista itse. Tietokoneessa kryptografisesti tärkein salaisuus eli avain on jossain vaiheessa tallennettuna tietokoneen muistiin tai prosessorin rekistereihin selväkielisenä. Käyttöjärjestelmät, käyttörajoitukset sekä prosessorien suojausominaisuudet pyrkivät tekemään toisen käyttämän muistin lukemisen vaikeaksi tai mahdottomaksi. Jos kuitenkin käy niin, että esimerkiksi AES-salaimen toteutus jättää muistiin tai rekistereihin yhdenkin kierrosavaimista, mahdollistaa se kaikkien kierrosavaimien sekä salaukseen käytetyn avaimen selvittämisen.

Avain ja kierrosavaimet eivät saa olla salaimen toiminnan jälkeen tallennettuna mihinkään rekisteriin, muistiin, välimuistiin tai luku-/kirjoituspuskuriin.

Vastaa edellisen tekstin avulla seuraaviin väittämiin.

Kysymys 1

Valitse oikea vaihtoehto.

Avainlaajennus muuttaa esimerkiksi 128-bittisen avaimen 256-bittiseksi.

Avainlaajennus tehdään kerran salauskierrosten aikana.

Avainlaajennus suoritetaan jokaisella AES-käsittelykierroksella.

Kysymys 2

Valitse oikea vaihtoehto.

Avainlaajennuksen kierrosavaimia kannattaa säilyttää kovalevyllä.

Avain ei ole yhtä tärkeä suojattava tieto kuin kierrosavaimet.

Jos avain on 256-bittinen, tuotetaan 14 kierrosavainta.

---

Substituutio (engl. s-box)

AES:n substituutio on samankaltainen kuin mitä käytimme klassisissa Caesar- ja Vigenère-salaimissa. Caesarissa jokaiselle merkille oli sama substituutio, kun taas Vigenère-salaimessa jokaiselle merkille on oma substituutio. Kummassakin klassisessa salaimessa enkoodauksessa valittiin aakkosten välinen etäisyys. Dekoodauksessa käytettiin etäisyyttä negatiivisena. Kumpikin laskenta toteutettiin äärellisessä kentässä 29 eli (mod 29).

AES:ssä tilan (state) tavut korvataan toisilla tavuilla, ja substituutio-korvaustaulu on laskettu yleensä valmiiksi. Korvaus ei siis tapahdu aakkoston merkkietäisyyden mukaan vaan korvaus lasketaan matemaattisesti.

AES:ssä kahdeksan bittiä korvataan toisella kahdeksalla bitillä. Ohessa esimerkki tällaisesta substituutiosta:

• Enkoodauksessa tavu 0x00 korvataan tavulla 0x63 .

• Dekoodauksessa tavu 0x63 korvataan tavulla 0x00 .

Substituutiossa jokaiselle 8-bittiselle kuviolle, eli tavulle, on oma muunnos enkoodauksessa ja vastaava käänteinen muunnos dekoodauksessa.

AES:n substituutio on kuin Vigenère, mutta korvauksen laskeminen on matemaattisesti hieman mutkikkaampaa. Juuri tämä AES:n substituution laskenta on yksi suomalaisen emeritaprofessori Kaisa Nybergin innovaatioista. AES-salaimessa käytetään korvaustaulua, joka sisältää substituution jokaiselle 8-bittiselle bittikuviolle.

Substituutio luo AES-salaimelle osan salaimen epälineaarisuudesta.

Jos substituutiota ei suoritettaisi, salain olisi yhdistelmä lineaarisia operaatioita, joita pystyy ratkomaan lineaaristen yhtälöiden ratkaisumenetelmillä verrattain suoraviivaisesti.

Tämä laatikko sisältää vapaaehtoista lisämateriaalia. Voit lukea sen tai siirtyä osiossa eteenpäin.

Substituutio on toteutettu siten, että tavu korvataan sen käänteisluvulla tietyssä polynomikertolaskun kentässä. Matemaattisesti ilmaistuna tavulle on laskettu polynomikertolaskulla sen käänteisluku Galois-kentässä \(2^8\) GF(\(2^8\)), siten, että polynomikertolaskun tulos tuodaan äärelliseen kenttään \(x^8 + x^4 + x^2 +1\) modulolla. Kyseinen polynomi on pelkistymätön. Polynomin pelkistymättömyys tarkoittaa sitä, että se on jaollinen itsellään ja ykkösellä. Tavallisten lukujen maailmassa sama ominaisuus on alkuluvuilla.

Käänteislukutavu on nyt siis se tavu, joka tuottaa polynomikertolaskussa äärellisessä kentässä tuloksen 1. Substituutio suoritetaan tällä polynomikertolaskun käänteisluvulla.

Aiheesta on AES-standardissa lyhyt kuvaus luvussa 4.2, joka toimii käytännön johdantona miten laskenta on suoritettu kaikille muillekin AES:n operaatiolle.

---

Vastaa edellisen tekstin avulla seuraaviin väittämiin.

Kysymys 1

Valitse oikea vaihtoehto.

AES:n s-boksi on samankaltainen kuin Caesar- ja Vigenère-korvaus. Matematiikka on hieman erilaista, mutta periaate sama, eli yksi bittikuvio korvataan toisella.

AES:n s-boksi korvaa tavut yhdellä 29 kirjainmerkistä.

AES:n s-boksi korvausfunktio on yksinkertainen yhteenlasku.

Kysymys 2

Valitse oikea vaihtoehto.

Enkoodatessa tila (state), jossa on tavu 0x00, korvataan tavulla 0x63.

Enkoodatessa tila (state), jossa on tavu 0x63, korvataan tavulla 0x00.

S-boksi toteuttaa lineaarisuuden salaimeen.

---

Substituution-permutaatioon kuuluu tietenkin permutoinnit. Seuraavaksi katsomme kahta AES:n suorittamaa permutointia.

---

Rivien siirto eli permutointi (engl. shift rows)

Jokaisella kierroksella kierrosavaimen käytön ja tavusubstituution jälkeen rivejä siiretään eli permutoidaan.

• Ensimmäistä riviä ei muuteta.

• Toinen rivi permutoidaan niin, että vasemman reunan tila siirtyy oikeanpuoleisimmaksi ja muut saman rivin tilat siirtyvät loogisesti pykälän vasemmalle.

• Kolmas rivi permutoidaan niin, että kaksi vasemman reunan tilaa siirtyy oikeanpuoleisimmaksi ja kaksi oikeanpuoleista tilaa siirtyvät loogisesti vasemmalle.

• Neljäs rivi permutoidaan niin, että oikean reunan tila siirtyy vasemmanpuoleisimmaksi ja muut saman rivin tilat siirtyvät loogisesti pykälän oikealle.

Jos rivien permutointia ei suoriteta:

• Olisi mahdollista rakentaa jokaiselle sarakkeelle oma koodikirja, joka nykykoneilla selvittäisi salaimen sisällön sekunneissa. Koodikirja on yksi burte-force-hyökkäystapa. Tämä koodikirja ei ole sama asia kuin seuraavan osion lohkosalaimen käyttötapa.

• Salain ilman rivipermutointia ei ole taipumattomuutta. Taipumattomuus pitäisi ilmetä niin, että pieni (esimerkiksi yhden bitin) muutos salaimen sisäänmenossa aiheuttaa muutoksen suureen osaan (yleensä puoleen) salatuissa biteissä.

---

Sarakkeiden sekoitus eli permutointi & korvaus (engl. mix columns)

Lopuksi suoritetaan sarakkeiden sekoitus, jolla lisätään epälineaarisuutta ja bittikuvioiden tasajakautuneisuutta.

Sarakkeiden sekoitus perustuu rajoitettujen kenttien matematiikkaan, jossa bittikuvio korvataan toisella tietyn polynomilaskun pohjalta. Emme käy tätä syvällisesti läpi, mutta voit lukea tarkan kuvauksen toiminnasta AES-standardista.

---

Vastaa edellisen tekstin avulla seuraaviin väittämiin.

Kysymys 1

Valitse oikeat vaihtoehdot.

Rivien siirto ei muuta ensimmäistä tila riviä.

Aikaisemmassa korvaustaulussa, joka havainnollistaa rivien siirtoa \(S_{13}\) on siirtynyt yhden pykälän vasemmalle.

Rivien siirrossa vasemman yläkulman ja oikean alakulman tilat vaihtavat tilataulussa paikkaa.

Permutointi on tarpeen mm koodikirjahyökkäyksen estämiseksi.

Jos teemme vain rivien permutoinnin emmekä permutoi sarakkeita, ylin tilarivi muuttuu vain s-boksin ja kierrosavaimen ansiosta. Tällöin sen sisältämä informaatio ei diffusoidu muihin sarakkeisiin tai riveihin.

Kysymys 2

Valitse oikeat vaihtoehtot.

Sarakkeiden sekoitus lisää epälineaarisuutta.

Sarakkeiden sekoitus lisää entropiaa tasoittamalla bittien ja bittikuvioiden jakaumaa.

Moduloaritmetiikkaa ei tarvita lainkaan permutoinneissa.

Sarakkeiden sekoitus ei ole tarpeellinen operaatio ja se voidaan ohittaa kierroksilla.

---

---

Käsittelykierrosten jälkeen

Kun lohkosalain on suorittanut kaikki tarvittavat operaatiot, lohkosalain tuottaa salatekstin \(C\) . Viimeisellä kierroksella sarakkeiden sekoitusta ei enää suoriteta. Salain käyttää vielä viimeiseksi tuotettuun lohkoon kierrosavainta XOR-funktion avulla ja palauttaa tämän jälkeen salaimen tuloksen \(C\).

---

Yhteenveto

AES-lohkosalaimessa käytetään siis substituutiota, permutaatiot ja matemaattisia operaatiota kun bittikuvioita manipuloidaan.

Seuraavissa kolmessa kappaleessa käytämme lohkosalainta eri tavoilla.

• Ensimmäiseksi käytämme salainta puhtaana lohkosalaimena koodikirja-moodissa eli ECB-moodissa. Huomaamme sen aiheuttavan lopulta ongelmia.

• Seuraavaksi käytämme lohkosalainta salainlohkojenketjutus-moodissa eli CBC-moodissa.

• Viimeiseksi muutamme lohkosalaimen toimimaan jonosalaimen tavoin laskuri-moodissa eli CTR-moodissa.

Palautusta lähetetään...

×

Identtinen palautus

Tämä palautus on identtinen aikaisemman palautuksen kanssa. Oletko varma, että haluat lähettää palautuksen?

Peruuta Lähetä