Kryptografi og nettverkssikkerhet (Kapittel 6: AES)

Dagens tekst er hentet fra kapittel 6 i Cryptography and Network Security. Advanced Encryption Standard er arvtakeren til DES, og algoritmen Rijndael gikk seirende ut av NISTs AES-konkurranse ved årtusenskiftet.

Bakgrunn

Det ble mot slutten av 90-årene klart at det var behov for en erstatter for DES. Det var etter hvert flere teoretiske angrep som kunne bryte algoritmen, og fremskritt i datakraft gjorde det etter hvert mulig å knekke DES-nøkler ved uttømmende søk for en overkommelig pris. Det var fortsatt mulig å bruke Triple-DES, men den var langsom og hadde fortsatt bare 64-bit blokkstørrelse. Det amerikanske National Institute of Standards and Technology (NIST) utlyste i 1997 en konkurranse for å finne en ny blokkchiffer-algoritme. 15 kandidater ble akseptert i juni 1998, og disse ble redusert til 5 finalister i august 1999 (deriblant den norsk-danske kandidaten Serpent). Rijndael ble utropt som AES i oktober 2000, og utgitt som FIPS PUB 197 standard i november 2001.

AES-chifferet Rijndael

Rijndael ble designet av Vincent Rijmen og Joan Daemen ved KU Leuven i Belgia. Den har 128/192/256 bit nøkler, 128 bit blokkstørrelse. Det er et iterativt snarere enn et Feistel chiffer, og prosesserer data som en blokk av 4 kolonner av 4 byte. Den opererer på hele datablokken I hver runde. Rijndael var designet for å være motstandsdyktig mot kjente angrep, ha rask og kompakt kode på mage CPUer, og ha et enkelt design.

Aritmetikk i endelige kropper

I AES blir alle operasjoner utført på 8-bit byter. De aritmetiske operasjonene addisjon, multiplikasjon, og divisjon utføres over den endelige kroppen GF(28). Som kjent er en kropp en mengde hvor vi kan utføre addisjon, subtraksjon, multiplikasjon, og divisjon uten å forlate mengden. Divisjon er definert ved følgende regel: a /b = a (b-1 )

Et eksempel på en endelig kropp (dvs. en kropp med et endelig antall elementer) er mengden Zp som består av alle heltall {0, 1, . . . . , p – 1}, hvor  p er et primtall og hvor aritmetikk utføres modulo p.

Hvis en av operasjonene i algoritmen er divisjon, må vi utføre aritmetikk definert over en kropp. Divisjon forutsetter at ethvert element som ikke er null har en multiplikativ invers. Av praktiske årsaker, og for effektiv implementering, ønsker vi å jobbe med heltall som passer akkurat inn i et antall bit, med ingen bortkastede bitmønstre, f.eks. heltall mellom 0 og  2n – 1, som passer inn i et n-bit “word”. Imidlertid er mengden av slike heltall, Z2n, ved bruk av modulær aritmetikk, ikke en kropp. For eksempel, heltallet 2 har ingen multiplikativ invers i Z2n, dvs. det finnes ikke noe heltall b, slik at 2b mod 2n = 1. Vi må derfor definere kroppen modulo et polynom, som vist i kapittel 5. En endelig kropp med 2n elementer refereres til som GF(2n). Ethvert polynom i GF(2n) kan representeres ved et n-bit tall.

Detaljert AES struktur

AES prosesserer hele datablokken som en enkelt matrise gjennom hver runde vha. substitusjoner og permutasjoner. Nøkkelen som gis som input ekspanderes til en matrise bestående av førtifire 32-bit “words”, w[i], fire av disse brukes i hver runde, som består av fire forskjellige stadier:

  1. Substitusjon av byter (Substitute bytes) – bruker en S-boks for å utføre en byte-for-byte substitusjon av blokken.
  2. Skift rader (ShiftRows) – en enkel permutasjon
  3. Miks kolonner (MixColumns) – en substitusjon som bruker aritmetikk over GF(28)
  4. Legg til rundenøkkel (AddRoundKey) – en enkel bitvis XOR av den gjeldende blokken med en del av den utvidede nøkkelen. Legg merke til at dette er det eneste stadiet som involverer nøkkelen. Denne funksjonen kan ses på som et slags Vernam-chiffer.

Chifferet begynner og slutter med å legge til rundenøkkel. Vi kan se på chifferet som alternerende operasjoner av XOR kryptering (AddRoundKey) av en blokk, fulgt av en “stokking” av blokken (de andre tre stadiene), fulgt av XOR kryptering, og så videre. Hvert stadium er lett å reversere. Dekrypteringsalgoritmen gjør bruk av den ekspanderte nøkkelen i omvendt rekkefølge, men den er ikke identisk med krypteringsalgoritmen. Tilstandene er de samme for både kryptering og dekryptering. Den avsluttende runden av både kryptering og dekryptering består av bare tre stadier (1, 2 og 4).

Substitusjon av bytes

Dette er en enkel substitusjon av hver enkelt byte. Vi har en tabell med 16×16 bytes som inneholder en permutasjon av alle 256 8-bit verdier. Hver byte i den gjeldende blokken byttes ut med innslaget i tabellen som man får ved å la de første 4 bitene (til venstre) velge raden, og de siste 4 (til høyre) velge kolonnen. F.eks. byte {95} byttes ut med byten vi finner i rad 9, kolonne 5 (som har verdien {2A}).

S-boksen er konstruert ved å bruke en definert transformasjon i GF(28), og er designet for å være motstandsdyktig mot alle kjente kryptoanalytiske angrep. Utviklerne av Rijndael ønsket et design som har lav korrelasjon mellom input bits and output bits, samt egenskapen at det du får ut ikke er en lineær matematisk funksjon av det du putter inn. Ikke-lineariteten oppnås grunnet bruken av den multiplikative inversen.

Skift av rader

Dette stadiet foretar en sirkulær forskyvning i hver rad. Den første raden forblir uendret, den andre forskyves en plass mot venstre, den tredje raden forskyves to plasser mot venstre, og den fjerde tre plasser mot venstre. Når man skal dekryptere, gjør man tilsvarende, bare med forskyvninger mot høyre. Ettersom den gjeldende blokken (“Tilstanden”) prosesseres etter kolonner, vil dette steget permutere bytene mellom kolonnene.

Dette er mer substansielt en det kan se ut som.  På samme måte som chifferets input (klartekst) og output (chiffertekst), behandles Tilstanden som en matrise av fire 4-byte kolonner. I begynnelsen av prosessen kopieres de første 4 bytene av klarteksten inn i den første kolonnen av Tilstanden, de fire neste i den andre kolonnen, osv.  Rundenøkkelen anvendes på Tilstanden kolonne for kolonne. Radskiftet flytter følgelig en individuell byte fra en kolonne til en annen, som er en lineær distanse som er et multiplum av 4 byte. Transformasjonen sikrer at de 4 bytene i 1 kolonne er spredd ut til 4 forskjellige kolonner.

Miks kolonner

Hver kolonne prosesseres separat, hver byte erstattes med en verdi som er avhengig av alle fire byte i kolonnen. I praksis er dette en matrisemultiplikasjon i GF(28) vha. et primsk polynom m(x) =x8+x4+x3+x+1. Koeffisienter av en matrise basert på en lineær kode med maksimal avstand mellom kodeord sørger for en god miksing av bytene i hver kolonne. “Miks-kolonner”-transformasjonen kombinert med skift av rader sørger for at etter noen få runder vil alle output-bits avhenge av alle input-bits.

Legge til rundenøkkel

De 128 bitene i Tilstanden XORes bitvis med de 128 bitene av rundenøkkelen. Vi kan se på dette som en kolonnevis operasjon mellom de fire bytene i en kolonne i Tilstanden og et word av rundenøkkelen – men vi kan også se på det som et byte-nivå operasjon. Dette er så enkelt som det kan få blitt, og påvirker hvert eneste bit i Tilstanden. Kompleksiteten i ekspansjonen av rundenøkkelen, plus kompleksiteten av de andre stadiene av AES sørger for sikkerheten.

AES nøkkelekspansjon

Nøkkelekspansjonsalgoritmen mates med en 16 byte nøkkel (4 word à 32 bit), og produserer et lineært array på 176 byte (44 word). Dette er tilstrekkelig for å fremskaffe en 16 byte rundenøkkel for den første AddRoundKey, samt for hver av de 10 rundene i chifferet.

Nøkkelen kopieres inn i de første 16 bytene av den ekspanderte nøkkelen, og resten av den ekspanderte nøkkelen fylles inn 16 byte (4 word) i slengen. Hvert nye word w[i] avhenger av wordet som kommer umiddelbart før, w[i – 1], og det word som befinner seg fire posisjoner bakover, w[i – 4]. I tre av fire tilfeller bruke rman en enkel XOR, men for et word hvis posisjon i W-arrayet er et multiplum av 4 bruke man en mer kompleks funksjon.

Rijndael-utviklerne designet nøkkelekspansjonsalgoritmen for å være motstandsdyktig mot kjente kryptoanalytiske angrep. Ved å ta med en rundeavhengig rundekonstant RC(j) elimineres symmetrien mellom måtene som rundenøklene genereres på i de forskjellige rundene. De spesifikke kriteriene som ble brukt var:

  • Kjennskap til en del av nøkkelen elle rrundenøkkelen gjør deg ikk I stand til å bergene mange andre bit i rundenøkkelen
  • Transformasjonen er inverterbar
  • Hastighet på et bredt spektrum av prosessorer
  • Bruk av rundekonstanter for å eliminere symmetrier
  • Diffusjon av endringer i chiffernøkkel-forskjeller inn i rundenøklene
  • Nok ikkelinearitet til å forhindre full bestemmelse av forskjeller i rundenøkler kun fra forskjeller i chiffernøkler
  • Enkel beskrivelse

Ekvivalent invers

AES dekryptering er IKKE identisk med krypteringsfunksjonen. Rekkefølgen av transformasjonene er forskjellig, men formen på nøkkelplanen (rundenøklene) er den samme. Ulempen er at man trenger to separate krypterings- og dekrypteringsmoduler i programvare eller maskinvare er nødvendige for applikasjoner som både skal kryptere og dekryptere.

Det er to separate endringer som er nødvendige for å tilpasse dekrypteringsstrukturen til krypteringsstrukturen; de to første stadiene i dekrypteringsrunden må byttes om, og det samme gjelder de siste to.

 Bytting av InvShiftRows og InvSubBytes

InvShiftRows påvirker sekvensen av bytes i Tilstanden men endrer ikke byte innhold og avhenger ikke av byte innhold for å utføre transformasjonen. InvSubBytes påvirker innholdet  av bytes i Tilstanden, men endrer ikke byte sekvensen og avhenger ikke av byte sekvensen for å utføre transformasjonen. Ergo er disse to operasjonene kommutative, og kan fritt byttes med hverandre.

Bytting av AddRoundKey og InvMixColumns

Transformasjonene AddRoundKey og InvMixColumns endrer ikke sekvensen av bytes i Tilstanden. Hvis vi ser på nøkkelen som en sekvens av Words, så opererer både AddRoundKey og InvMixColumns på Tilstanden en kolonne om gangen. Disse to operasjonen er lineære med hensyn til kolonne inputen.

Implementasjonsaspekter

AES kan implementeres veldig effektivt på en 8-bit prosessor (miljøet ved KU Leuven hadde lang erfaring med implementering av sikkerhetsløsninger for smartkort). AddRoundKey er en bytemessig XOR operasjon, ShiftRows er en enkel byte-skifting operasjon, og SubBytes opererer på byte level og krever kun en tabell på 256 byte. MixColumns krever matrisemultiplikasjon I kroppen GF(28), som betyr at alle operasjoner gjøres på bytes.

Vi kan også implementere AES effektivt på en 32-bit prosessor; stegene kan redefineres til å bruke 32-it word (4 byte), og fire tabeller av 256 words kan forhåndsutregnes. Hver kolonne i hver runde kan deretter beregnes vha. 4 tabelloppslag og 4 XORer, kun med kostnaden ved å lagre tabellene (4x4x256 = 4kB). Designerne er av den oppfatning at denne veldig effektive implementeringen var en nøkkelfaktor i valget av Rijndael som AES-chifferet.