Kryptoblog

Elektroniktidningen har publicerat ett par artiklar som tillsammans ger en hel del ny information om de nya passen med RFID-kretsar för lagring av biometrisk information.

Den första artikeln innehåller nyheten att den krets utvecklad av Infineon, på initiativ av Smarticware, och som bland annat sitter i den nya Svenska passen, nu även skall användas i USAs nya pass. Vidare berättar artikeln att samma krets i dag används av 20 olika länder för att lägga till elektroniskt lagrad identitetsinformation.

Den första artikeln länkar sedan vidare till artikeln (med den i mitt tycke tveksamma rubriken) Rfid - ett vapen mot terrorrism. Den artikeln innehåller desto mer information om kretsen. Bland annat får man reda på att:

• Kretsen tillverkas i 0.22um CMOS-process.
• Innehåller 16-bits mikrokontroller.
• Stödjer ISO14443, A och B.
• Kryptoaccelation för RSA och ECC med 1100 bitars nyckel (oklart om det är RSA, ECC eller båda som har 1100 bitars nyckel).
• Kryptoacceleration för DES och 3DES.
• 136 kByte ROM för lagring av ett operativsystem från Axalto.
• 64 kByte EEPROM eller FLASH för datalagring.
• 5 kByte RAM.

Utifrån detta går det ganska lätt att identifiera kretsen som SLE66CLX641P. Infineon har en hel serie kretsar där detta är den just nu mest avancerade kretsen.

Markus Hahn har gett sig i kast med att implementera effektiva versioner av eSTREAM-kandidaterna i Java. Markus bibliotek estreamJ innehåller ett flertal eSTREAM-kandidater samt några andra krypton som referens. Biblioteket utökas hela tiden och just nu innehåller det följande krypton:

• AES med CTR-mod (Referenskrypto.)
• Dragon
• HC-256
• Hermes8 (Både Hermes8-128 och Hermes8-80.)
• MICKEY (Både gamla versionen och MICKEY-128.)
• Phelix (Phelix och Phelix96)
• RC4 (Referenskrypto.)
• Salsa20

Markus har även satt upp en webbsida där dom olika algoritmerna körs i tur och ordning, och där man som användare kan variera bufferstorlek och datastorlek. När jag körde med 10 MByte data och buffer på 1024 fick jag följande:

testing [AESCTR128_lean] … OK, 3505 kB per second
testing [AESCTR128_mean] … OK, 4871 kB per second
testing [Dragon-128] … OK, 10343 kB per second
testing [Dragon-256] … OK, 10893 kB per second
testing [HC-256] … OK, 13161 kB per second
testing [Hermes8-128] … OK, 1652 kB per second
testing [Hermes8-80] … OK, 1188 kB per second
testing [MICKEY] … OK, 802 kB per second
testing [MICKEY128] … OK, 554 kB per second
testing [Nil] … OK, 365714 kB per second
testing [Phelix] … OK, 10858 kB per second
testing [Phelix96] … OK, 14970 kB per second
testing [RC4] … OK, 17326 kB per second
testing [Salsa20] … OK, 5458 kB per second
Done.

Som synes är raketerna bland eSTREAM-kandidaterna Dragon, Hermes8 och Phelix. Salsa20 är i alla fall snabbare än AES. MICKEY-128, som i första hand är tänkt för inbyggda system är klart långsammast. I all fall i programvaruimplementationer.

I dag avslutades officiellt fas ett av eSTREAM-projektet och går nu över i fas två. Det finns som jag tidigare beskrivit två olika så kallade profiler i eSTREAM. Profil ett är algoritmer är avsedda för maximal prestanda på högpresterande 32-bitars processorer. Profil två är algoritmer avsedda för att kunna implementeras effektivt i hårdvara och på processorer för inbyggda system. För respektive kategori finns det nu ett antal huvudkandidater utvalda.

För kategori ett är huvudkandidaterna:

• Dragon-128
• HC-256
• LEX
• Phelix
• Py
• Salsa20
• Sosemanuk

För kategori två är huvudkandidaterna:

• Grain
• Mickey-128
• Phelix
• Trivium

Notera att algoritmen Phelix (av Bruce Schneier, Niels Fergusson med flera) finns med som huvudkandidat i båda profilerna.

Förutom huvudkandidaterna finns ett antal andra algoritmer som går vidare till andra omgågen. Men jag gissar att vinnarna av eSTREAM i respektive profil finns bland dessa. Jag kommer den närmaste tiden att berätta mer om dessa kandidater.

Arbetet med att ta fram nya strömkrypton, vilket sker i eSTREAM-pojektet rullar på. under vintern her det tagits fram en utvärderingsmiljö som gör det möjligt att kompilera upp och köra samtliga kandidater samt mäta upp prestandan. Testmiljön är en aning Linux-ifierad och kräver bland annat GNU Make för att kompilera ordentligt, men fungerar utmärkt så vitt jag kan bedöma av de enkla tester jag gjort.

Resultaten har börjat sammanställas och det finns ett antal olika referenskrypton som används som jämförelse, exempelvis RC4, Snow och AES i CTR-mod. Tyvärr är resultatsammanställningen en aning rörig så det är inte helt lätt att skatta vilken algoritm som är bäst.

En person som gjort ett flertal prestandamätningar på olika plattformar och sedan gjort en egen sammanställning är Daniel J. Bernstein. Han har dessutom skrivit en artikel där han presenterar sina resultat. DJB har även publicerat en kortare sammanställning på det diskussionsforum som finns för eSTREAM:

Here are the top ten ciphers for 576-byte packets on the Pentium M, starting from the fastest: ABC version 1 (currently claiming 96-bit security, I believe), ABC version 2 (128), Salsa20/8 (256), Rabbit (128), NLS (64), Py6 (64), SOSEMANUK (128), Salsa20 (256), LEX (128), Py (64).

On the Athlon 64: ABC version 1 (96), ABC version 2 (128), Salsa20/8 (256), Rabbit (128), TRIVIUM (80), Phelix (128), NLS (64), SOSEMANUK (128), Salsa20 (256), LEX (128).

Top ten streaming ciphers on the Pentium M: Py (64), Py6 (64), ABC version 1 (96), ABC version 2 (128), HC-256 (256), SOSEMANUK (128), Salsa20/8 (256), TRIVIUM (80), NLS (64), Rabbit (128).

On the Athlon 64: ABC version 1 (96), ABC version 2 (128), Salsa20/8 (256), Py6 (64), Py (64), TRIVIUM (80), SOSEMANUK (128), HC-256 (256), Rabbit (128), Phelix (128).

Top ten ciphers for parallel streams on the Pentium M: SOSEMANUK (128), Salsa20/8 (256), TRIVIUM (80), Rabbit (128), NLS (64), Py6 (64), Salsa20 (256), LEX (128), Phelix (128), Dragon (256).

On the Athlon 64: Salsa20/8 (256), SOSEMANUK (128), TRIVIUM (80), Rabbit (128), Phelix (128), NLS (64), Salsa20 (256), Dragon (256), LEX (128), Mir-1 (32).

Som synes varierar topplistan beroende på vilken arkitektur som används. En annan sak som gör stor skillnad är initieringsfasen, exempelvis försvinner ABC snabbt från topplistorna när det skall ske många nyckelbyten, vilket kräver många initieringar av krypot. Dock är det ändå min uppfattning att det är relativt konsekvent resultat med ABC, Py, Salsa20, Phelix, TRIVIUM, NLS, Rabbit och några till som dyker upp i toppen hela tiden.

Värt att notera att detta är C-implementationer på 32- eller 64-bit processor. Fortfarande är det inte klart hur utvärdering i hårdvara eller för inbyggda system med 8- 16- eller små 32-bitsprocessorer skall ske.

Arbetet med eSTREAM går framåt och många av de kandidater till kryptoalgoritmer som föreslagits har funnits innehålla brister. För flera av dessa är bristerna sådana att kandidaterna har fallit (eller återkallats). Följande är en snabb lista på algoritmer som fallit

ABC version 1
Achterbahn version 1
DECIM version 1
DICING version 0
F-FCSR-H
F-FCSR-8
Grain
MAG
Polar Bear
POMARANCH (CJCSG) version 1
Self-Synchronous SOBER (SSS)
TSC-3
WG version 1


Grain och Polar Bear är de bidrag med Svensk koppling. Tråkigt, speciellt med Grain som har en snygg inbyggd skalbarhet i storlek och prestanda. Men det skall vara säkert också.

Några av favoriterna, Daniel J Bernsteins salsa20 och Schneiers et als Phelix är kvar i tävlingen.

Grain är ett bidrag av Martin Hell och Thomas Johansson från LTH tillsammans med Willi Meier från Schweiz. Grain är ett krypto för kategori två, mer specifikt för inbyggda system.

Thomas Johansson har tidigare varit med och utvecklat strömkryptot Snow. Version 1.0 av Snow var en kandidat till NESSIE - New European Schemes for Signatures, Integrity, and Encryption. Snow 1.0 visade sig dock innehålla svagheter vilket gjorde att den inte blev antagen i NESSIE-sviten (det gjorde inga andra strömkrypton heller, och är en anledning till eSTREAM-satsningen).

Svagheterna i Snow hanterades i en andra verision av Snow och jag trodde att Snow 2.0 skulle bli inskickad som bidrag till eSTREAM. Men Grain är ett helt annat krypto.

Grain är ett krypto direkt avsett för implementation i hårdvara och är byggt för att minimera logik- och minnesresurser. Några egenskaper:

• Nyckellängd på 80 bitar med initialvektor (IV) på 64 bitar.
• Består av två skiftregister sammankopplade med en icke-linjär filterfunktion.
• Skalbar prestanda baserad på parallellkoppling av flera stycken Grain-krypton.

De två skiftregistren är bitbaserade. Det ena skiftregistret är ett linjärt skiftregister (LFSR) medan det andra är ett icke-linjärt skiftregister (NFSR). Båda skiftregistren är 80 bitar långa.

Vid initiering laddas nyckeln och IV:n in i kedjorna. Sedan stegas maskinen 160 cykler. Detta innebär att en initiering tar drygt 160 cykler. Inte speciellt mycket, men klart mer än AES/Rijndael. Det är även långsammare än Bluetooth-kryptot E0 eller A5/1 i GSM, två krypton som Grains skapare jämför med i sin artikel.

Skalbarheten åstadkoms i Grain genom att återmatningsfunktionerna för skiftregistren och filterfunktionen dubbleras. Därmed fås en linjär skalning av prestandad med linjär ökning av hårdvaruresurserna. De resurser som krävs är logik (grindar) och routing (ledningar). Skiftregistren är byggda så att de lägsta 16 bitarna inte används i återmatningsfunktionerna. Detta gör att Grain enkelt går att skala från 1 till 16 bitar.

Författarnas implementation i en Altera Cyclone skalar i prestanda från 280 Mbit/s till 3.1 Gbit/s med en faktor fyra i storlek. Imponerande. Jag gillar verkligen skalbarheten i prestanda. Det jag skulle vilja ha förutom skalbarhet i prestanda är skalbarhet i nyckellängd. 80 bitar är i min mening i underkant. Upp till 128 bitar hade nog varit bra.

Grain är i mitt tycke ett mycket intressant krypto.

Jag har börjat gå igenom bidragen till ECRYPT:s eSTREAM för att försöka skatta och jämföra de olika bidragens hårdvaruresurser.

Det finns (minst) två bidrag med Svenskt deltagande.

Polar Bear är ett bidrag av Johan Håastad på NADA/KTH och Mats Näslund på Ericsson Research Communications Security Lab. Deras bidrag är avsett för både profil ett och profil två, dvs både för implementation på dator och i inbyggda system eller i hårdvara. Polar Bear kan enklast beskrivas som en variant av RC4, men där initieringen av tillståndstabellen utförs med hjälp av ett Rijendael/AES-baserat blockkrypto. Det finns även två stycken LFSR-kedjor i nästa tillstånds-delen av kryptot. Några saker jag noterar när jag läser Polar Bear-artikeln:

• För att begränsa tiden för initiering körs Rijndael-kryptot fem varv (rounds).
• Utdata från kryptot är fyra Bytes, dvs troligen ett 32-bit ord. Ändå säger författarna att kryptot är långsammare än RC4 på större datapaket. Deras implementation på en 1400 MHz Pentium (måste vara fel, 1400 MHz är troligen en Pentium III eller en Pentium IV). ger ca 190 MByte/s ut.
• Nyckellängden är 128 bitar, but shorter key lengths are accepted.

Om jag fattat Polar Bear rätt så sitter det väsentligen en komplett AES-variant som en del av kryptot. Eftersom den bara körs framåt, dvs krypterar behöver nyckeln inte expanderas för att få vettig prestanda, det sparar minne. Men, med S-boxar, LFSR-kedjor på 112 och 144 bitar samt ett permutationsminne på vad jag uppfattar vara 256 Bytes stort (dvs som i RC4) går det åt mer än 512 Bytes bara för tabeller. Sedan tillkommer AES-blocket som i Polar Bear är på 256 bitar.

För mig låter detta som mycker minne för exempelvis en PIC eller en AVR. Visserligen kan man lägga in S-boxen tillsammans med programkoden, men det är ändå rätt mycket arbetsminne som krävs för att hålla tillståndet i Polar Bear.

Att kryptot skulle gå långsammare än RC4 låter märkligt, speciellt efter att initieringskostnaden har amorterats av, dvs på längre datapaket. Än mer märkligt är enligt men mening att man tar fram ett nytt strömkrypto som inte är väsentligt snabbare än RC4. Jag förväntar mig att ett nytt strömkrypto är ordentligt mycket snabbare, alternativt kräver mindre resurser än RC4, men med bättre säkerhet.

Säkerhetsmässigt vågar jag inte ha för mycket åsikter. Att initieringsfasen använder en variant av AES, vilket innebär S-boxar gissar jag att Daniel J Bernstein kan ha en och annan åsikt om.

Det finns ett annat Svenskt bidrag, men det tar vi i morgon.

Från ECRYPT:s arbete med att få fram nya strömkrypton har det kommit en statusrapport.

En sak som förvånat mig är att det är så många av kandidaterna som är inriktade mot kategori II - inbyggda system och hårdvaruimplementation. Innan eSTREAM-kandidaterna presenterades verkade det som om de flesta kandidater skulle vara för kategori I - implementation på modern 32-bit processor, dvs en PC eller liknande. Men istället är majoriteten antingen både för denna kategori och katergori II alternativt bara kategori II.

En annan sak att notera är att man har varit tvungen att lägga till underkategorier för kandidater som även inkluderar autenticiering. Detta då flera kandidater, bland annat Phelix av Doug Whiting, Bruce Schneier med flera inkluderar autenticiering som en direkt funktion av kryptot. Speciellt för inbyggda system med begränsade resurser är det som jag ser det mycket intressant att få autenticiering direkt i kryptofunktionen.

Rapporten eSTREAM - Update 1 September 2, 2005