Lakseviga fort #10 AES Mystery Cache

Fortet ved Lakseviga/Krageviga på Flekkerøya var det første kystfortet tyskerne bygget i Kristiansand etter invasjonen 1940. Fortet sorterte under krigen som 3. batteri i Marine Artillerie Abteilung 502 som hadde hovedkvarter på Odderøya. Lakseviga fungerte som et vestlig sperrebatteri ved hovedinnløpet til Kristiansand.

Kommandoplass og ild-ledning var på Gråheia, litt lengre mot søraust.

Området ligg like ved Oksøy-Ryvingen Landskapsvernområde, så sjølv om området der cachen ligg ikkje er verna  oppfordrar eg likevel geocachere til å sørga for at "all ferdsel skjer varsomt og tar hensyn til vegetasjon, dyreliv og kulturminner." 

(Henta frå xkcd under lisens Creative Commons Attribution-NonCommercial 2.5 License (Forklaring til  xkcd-stripe.)

AES er faktisk ikkje eit Feistel chiffer, i motsetning til forgjengaren, DES. AES er eit Substitution–permutation network.

AES

The Advanced Encryption Standard (AES), også kjent som Rijndael er ein spesifikasjon av kryptering av elektroniske data etablert av U.S. National Institute of Standards and Technology (NIST) i 2001.

AES er eit utvalg av Rijndael chiffer utvikla av to belgiske kryptografer, Vincent Rijmen and Joan Daemen. Rijndael er ein familie av chiffer med ulike blokk- og nøkkel-lengder

For AES valgte NIST tre medlemmer av Rijndael familien, alle med ein blokklengde på 128 bits, men med tre ulike nøkkellengder: 128, 192 and 256 bits.

Prinsipp

I eit moderne chiffersystem prøver ein å skjula mest mogleg av strukturar i inndata og strukturar i samenhengen mellom nøkkel, klartekst og chiffertekst.

Ein prøver å oppnå best mogleg confusion and diffusion. Litt enkelt kan ein seia at med confusion meiner me at ein liten endring i nøkkelen skal gje ein fullstendig forskjellig chiffertekst, og med diffusion meiner me at ein liten endring i klarteksten skal gje ein fullstendig forskjellig chiffertekst. (Du kan jo gå tilbake til dei klassiske chiffra i Belteviga serien og sjå på i kor stor grad dei oppfyller desse krava.) Dette vil gjera det vanskeleg å analysera samanhengen mellom nøkkel, klartekst og chiffertekst og dermed vansklegjera til dømes "known plaintext attacks" (cribs)

Eit chiffer som til dømes AES (Advanced Encryption Standard) består derfor av tre element:

1. Metoder for å stokke om på meldinga
2. Ein metode for å generera ulike delnøkklar
3. XOR mellom melding og delnøkkel. Dette vert gjort fleire gonger, og punkt 1 og 2 vert gjort mellom kvar gong.

AES algoritmen opererer på blokker av ein fast størrelse, og ser grovt sett slik ut for ei blokk m:

1. finn delnøkkel
2. M := delnøkkel XOR m
3. gjer dette fleire gonger:
   1. stokk om på M
   2. finn ny delnøkkel
   3. M := delnøkkel XOR M
4. når me kjem hit er M den krypterte versjonen av m

Dette må so pakkast inn i til dømes CBC for å senda lange meldinger, og ei starte gjerne ein seksjon av meldingar med Diffie-Hellman eller noko liknande for å få satt opp nøkkelen.

No skal me ha ein gjennomgang av ein svært forenkla versjon av AES, så kjem oppgåva, også avslutter me å samanlikna det me har gjort med den verkelege versjonen av AES.

Døme på AES-lik kryptering

Blokklengden for vårt demo-chiffer er 12 bits, og nøkkelen er 15 bits lang.

Me har fått nøkkelen 

101 110 010 101 011

og skal kryptera meldinga

000 011 101 110

1. Delnøkkel-generering
   Me bruker eit svært enkelt system for del-nøkkel-generering:
   Bruk dei tolv første bitsa. Før neste generering flytt dei tre ubrukte bitsa fremst. Me kjem til å trenga tre del-
   nøkklar, og dei vert:
   1. 101 110 010 101
   2. 011 101 110 010
   3. 101 011 101 110
2. Del opp meldinga i fire biter på tre bits kvar, og sett bitane opp i ein 2x2 tabell:
   
   

   000	101
   011	110

   
   Legg merke til rekkefølgen på delane, det er kolonnevis.
3. Sett opp førset delnøkkel tilsvarande og køyr ein XOR for å finn første versjon av M.
   
   

   000	101
   011	110

           XOR
   

   101	010
   110	101

           =
   

   101	111
   101	011

4. Utfør 2 gonger. Første gong
   
   1. Bytt ut innhaldet i kvar rute med å slå opp i denne tabellen (S-boksen) Bytt ut talet i venstre kolonne med talet i høgre kolonne.
      

      000	111
      001	110
      010	011
      011	010
      100	101
      101	100
      110	001
      111	000

      
      (Dette er faktisk 3-bits-versjonen av S-boksen frå teikninga)
      
      I følge S-boksen så skal
      101->100
      011->010
      111->000
      slik at den nye M vert:
      
      

      100	000
      100	010

       
   2. Det neste er å stokka rekkevis. Første rekke er uforandra, i andre rekke bytter me om dei to rutene. 
      
      

      100	000
      010	100

       
   3. Så stokker me kolonnevis. Først venstre kolonne. flytt bitane i øverste rute eit hakk mot høgre. Flytt bitane i nederste rute eit hakk mot venstre. Den høgre biten i øverste rekke flytter du ned til den ledige plassen til høgre i nederste rute, og den biten som var til venstre i nederste rute flyttar du opp til den ledige plassen til venstre i øverste rute. Samme i høgre kolonne.
      
      

      010	100
      100	000

   4. XOR med andre delnøkkel:
      
      

      010	100
      100	000

              XOR
      

      011	110
      101	010

              =
      

      001	010
      001	010

5. Utfør 2 gonger. Andre gong
   1. Bytt ut med verdiar frå S-boksen
      
      

      110	011
      110	011

   2. Stokk om rekkevis
      
      

      110	011
      011	110

   3. Stokk om kolonnevis
      
      

      011	101
      110	101

       
   4. XOR med den tredje delnøkkelen.
      
      

      011	101
      110	101

              XOR
      

      101	101
      011	110

              =
      

      110	000
      101	011

       
6. Kryptert melding er
   
   M=1101 0100 0011

For dekryptering gjer du alle dei samme tinga, berre motsatt og i motsett rekkefølge. (I dette dømet er mange (men ikkje alle) av operasjonane sin eigen invers, det vil seia at dei er like ved kryptering og dekryptering. 

Oppgåve

Bob har sett opp ein web server der Alice kan lasta ned posisjonen tile neste cache. Meldinga som skal lastast ned består av seks BCD-koda siffer  'ABCXYZ' og posisjonen er gjeve som N 58° 05.ABC E 008° 00.XYZ.

(Dette minimalistiske formatet er brukt for å gjera det mogleg å handrekna på dømet. AES og liknande system er berekna for bruk med datamaskiner, og er egna til  kryptera meldingar som er mykje lengre en dette!)

Bob brukar Diffie-Hellman med parametre som i cache 7 for å setta opp nøkkelen. Nøkkelen som vert brukt er dei 15 bakerste (minst signifikante) bitane i binær-representasjonen av s.

Chifferet som vert brukt er den 12-bits demo-versjonen av AES som er vist her, og sidan meldinga ineheld to blokker bruker me CBC som vist i cache 9.

Så Alice sin PC vel a = 231 321 og får B = 9 226 183 frå Bob sin server.

Så får Alice meldinga

0110 0101 0110 0000 1000 1101 0010 0000 0000

og dei kan møtast ved cachen.

Forskjellar frå verkeleg AES

1. Nøkkelen i AES er på 128 bits eller lengre. Metoden for å generera del-nøkklar er langt meir komplisert en den eg har brukt, og omfattar mellom anna modulær aritmetikk på polynom. Den verkelege algoritmen genererer delnøklar som er svært ulike kvarandre.
2. Blokklengda under AES er 128 bits, og desse bitane vert organisert kolonnevis i ein tabell på 4X4 ruter, med ein byte i kvar rute.
3. Vel, XOR er XOR, berre på fleire bits
4. Understega 1-4 vert utført 11 gonger (eller fleire for dei store nøkklane). Siste gong vert steg 3 droppa
   1. Oppslaget vert gjort i ein S-boks som er ein tabell med 256 verdiar, og som er generet med avansert matematikk for å blanda bitsa som godt som mogleg. Vår S-boks er lik under kryptering og dechiffrering, det er ikkje tilfellet under AES.  
   2. Stokking rekkevis er svært lik, men må utvidast litt sidan det er ein 4X4 tabell i staden for ein 2X2 tabell. I dømet er denne operasjonen lik for kryptering og dekryptering, det er ikkje tilfellet under AES. 
   3. Stokking kolonnevis er betydleg meir komplisert og omfattar mellom anna modulær aritmetikk på polynom. Som her bytter me ut kvar kolonne i tabellen med ei ny kolonne berkna ut frå den gammle, men i den verkelege algoritmen er den nye kolonna svært forskjellig frå den gammle, og ei lita endring i start-kolonna gjev store forskjellar i den nye.
   4. Vel, XOR er XOR
5. Ved verkelege Diffie-Hellmann utveksling brukar ein langt større tal for p (g treng ikkje vera veldig stort) for å få tilfredstillande sikkerhet. Eventuelt meir kompliserte metodar som Elliptic-curve Diffie–Hellman (ECDH) for å gjera samme jobben.

Moderne kryptografi er på mange måter meir komplisert en det me har sett her, men eg håper at at cache 6-10 ha gitt ein viss ide om kva det dreier seg om.

Dermed har du fullført dette kryptografikurset. Viss du har funne alle 10, og me trur på Kama Sutra, har du no berre 63 kunstar att å læra før du er klar for livet.

Kryptograficachane på Flekkerøya

Første serie, klassisk kryptografi

Belteviga fort #1 Cæsar-chiffer

Belteviga fort #2 Enkelt substitusjonchiffer

Belteviga fort #3 Vigenèrechiffer

Belteviga fort #4 Vigenèrechiffer 2

Belteviga fort #5 Enigma (Bonus)

Andre serie, moderne kryptografi, nøkkelutveksling

Krossodden fort #6 Modulær aritmetikk

Krossodden fort #7 Diffie–Hellman utveksling

Krossodden fort #8 RSA

Tredje serie, moderne kryptografi, Symmetriske chiffer

Laksevika fort #9 XOR

Laksevika fort #10 AES

1.april spesial, på fastlandet.

Batterie Vara #11 Desinformasjon