Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
ECRYPT eSTREAM » Kryptoblog

Archive for the ‘ECRYPT eSTREAM’ category

Fas tre av eSTREAM inledd

April 11th, 2007

I början av april avslutades officiellt fas två av eSTREAM och fas tre inleddes. Under fas två var arbetet med att hitta nya strömkrypton i första hand inriktade på de fokuskandidater som under 2006 hade identifierats bland de dryga 30 kandidater som skickats in till projektet.  Jag bloggade om detta i mars förra året och listade då fokuskandidaterna:

För profil ett (SW) är fokuskandidaterna:

  • Dragon-128

  • HC-256

  • LEX

  • Phelix

  • Py

  • Salsa20

  • Sosemanuk

För profil två (HW) är fokuskandidaterna:

  • Grain

  • Mickey-128

  • Phelix

  • Trivium  


Jag hade förväntat mig att man till fas tre skulle skära bort ytterligare några kandidater för att få fram finalister till att bli godkända eSTREAM-standarder. Men det som istället har inträffat är att konceptet med fokuskandidater has slopats, och att det nu är fler algoritmer som är med till nästa omgång. För de olika profilerna ser det ut så här:
Profil ett (sw)

  • CryptMT

  • Dragon

  • HC

  • LEX

  • NLS

  • rabbit

  • Salsa20

  • SOSEMANUK 

Profil två (hw)

  • DECIM

  • Edon80

  • F-FCSR

  • Grain

  • Moustique

  • Pomaranch

  • Trivium


Motiveringen till att inte ha fokuskandidater, vilka kandidater som gått vidare respektive inte gått vidare finns beskrivet i den rapport om fas två som tagits fram. En överraskning som även diskuterats på eSTREAMs forum är att algoritmkandidaten Phelix av Bruce Schneier & Co ej gått vidare efter att ha varit. fokuskandidat under fas två.  Motivieringen för detta beslut är dels att algoritmen i förhållande till AES inte ger vare sig mycket bättre prestanda och inte är tillräckligt resurssnål. Vidare finns det diskussioner om säkerheten hos Phelix, mer specifikt om kravet på att inte initialvektorn (IV) inte får återanvändas är ett rimligt krav. I rapporten skriver man:

Furthermore, we believe that the attack does constitute a genuine threat against real life systems using Phelix. It does seem plausible that an attacker would be able to mount an attack against such a system, re-using nonces, and that recovering the key would be a serious outcome. Attackers are not usually bound by usage rules.


Tittar man på fas tre-kandidaterna i övrigt kan man se att:

  • De mer experimentella algoritmkandidaterna som baseras på helt nya koncept eller försök att hitta minimal komplexitet klarar sig bra. Både Moustique och Trivium är med.

  • Ingen av de algoritmer som var med i fas två i båda profilerna är längre med i båda profiler. Salsa20 är nu bara med för profil ett. Detta beror tror jag på att man har ett krav på att hw-implementationerna skall vara för små, resursbegränsade implementationer (läs: RFID, smartcards). Jag hade gärna sett att man i större grad tagit hänsyn till de artiklar som publicerats som visar på skalbarheten hos implementationerna.

  • Svenskalgoritmen Grain av Johansson & Co klarar sig bra. Den andra algoritmen med Svensk anknytning, Polar Bear har nu fått lufsa hem. 

Tidplanen nu är att fas tre skall pågå fram till nästa SASC-konferens där beslut om vilka kandidater som går till final fattas. Om drygt ett år finns det förhoppningsvis nya, snabba och blänkande strömkrypton att börja använda. Visst är det spännande?!

 

 

 

 

Svagheter hos arraybaserade strömkrypton

March 25th, 2007

Konferensen SASC 2007 har genomförts, och från den och det pågående arbetet med eSTREAM trillar det just nu ut många spännande kryptonyheter. En nyligen publicerad, intressant artikel är On the (In)security of Stream Ciphers based on Arrays and Modular Addition av Souradyuti och Preneel. Vad artikeln handlar om, och varför är den intressant? Det här:

Det finns ett antal strömkrypton som i grunden är uppbyggda på likartat sätt: En array fylld med dataelement där initialordningen av element styrs av den hemliga nyckeln. Genom enkla aritmetiska operationer styrs hur elementen i arrayen flyttas runt i arrayen. Motsvarande enkla operationer avgör även vilket element i arrayen som är (bas för) nästa genererade kodelement. Figuren visar ett exempel på hur detta går till:

Exemplet är hämtat från det troligen mest kända kryptot av den här typen – RC4. RC4 har tyvärr haft många problem med säkerheten i algoritmen, och trots flera försök att förbättra säkerheten (ex RC4A) är det i dag en ganska sargad algoritm. Det Souradyuti och Preneel visar i sin artikel, vilket kan förklara många av de problem som vi sett, är att det finns en inbyggd svaghet i den generella algoritmuppbyggnaden i sig. Författarna skriver:

We argue, counter-intuitively, that the most useful characteristic of an array, namely, the association of array-elements with unique indices, may turn out to be the origins of distinguishing attacks if adequate caution is not maintained.

In short, an adversary may attack a cipher simply exploiting the dependence of array-elements on the corresponding indices. Most importantly, the weaknesses are not eliminated even if the indices and the array-elements are made to follow uniform distributions separately.


Författarna går sedan vidare och attackerar inte bara eSTREAM-kandidaterna Py och Py6, utan även äldre krypton, bland annat min gamla favorit ISAAC. Just ISAAC är ett exempel på ett krypto som är inspirerat av RC4, och fram till i dag varit ansedd som ett starkt krypto. Men i artikeln presenteras attackresultat som gör ISAAC till ett praktiskt sätt knäckt krypto. Spännande och lite skrämmande.

Status för eSTREAM-kandidaterna

February 26th, 2007

Det har trillat in mycket artiklar med analyser av och attacker mot de olika eSTREAM-kandidaterna, inte minst på SASC 2007 presenterades ett flertal attacker. Daniel J Bernstein har en sida som håller koll på status för alla eSTREAM-kandidater. Jag tycker dock att det är intressant att snabbt kolla över status för fokuskandidaterna:

  • Dragon – En attack snabbare än brute force, men kräver mer än 2^64 bit data.

  • HC-256 – Ingen attack publicerad.

  • Lex – Ingen attack publicerad.

  • Phelix – Ingen attack publicerad.

  • Py – Knäckt.

  • Salsa20 – Salsa20 med fem och sex rundor knäckta.

  • SOSEMANUK - Ingen attack publicerad

  • Grain – Första versionen knäckt. Ny version av grain publicerad.

  • Mickey-128 – Ingen attack publicerad.

  • Trivium – Ingen attack publicerad.

Även om de flesta algoritmerna så här långt ser ut att vara robusta pågår det samtidigt en het debatt på eSTREAM om varför krypton med så liten nyckel som 80 bitar över huvud taget togs med. Allt mer tyder på att dessa krypton kommer att erbjuda en för liten säkerhetsmarginal för att de skall komma att bli intressanta att använda.

Mer information om RFID-kretsen för pass med biometri

August 23rd, 2006

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.

Java-bibliotek med eSTREAM-kandidater

August 16th, 2006

Markus Hahn har gett sig i kast med att implementera effektiva versioner av eSTREAMkandidaterna i Java. Markus bibliotek estreamJ innehåller ett flertal eSTREAMkandidater 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.

Fas ett av eSTREAM avslutad

March 27th, 2006

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.

Resultat från prestandautvärdering av kandidater i till eSTREAM

February 25th, 2006

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.

Svenska bidragen till eSTREAM borta

November 22nd, 2005

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, ett annat Svenskt bidrag till eSTREAM

September 26th, 2005

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.

Polar Bear, ett Svenskt bidrag till eSTREAM

September 26th, 2005

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.