Etikettarkiv: clang

LLVM 3.0 släppt

Version 3.0 av kompilatorsystemet LLVM släpptes den första december.

LLVM-loggan.

LLVM är ett öppen kod-projekt (med BSD-liknande licens) som sponsras av bland annat Apple, och är även den kompilator som finns i Apples utvecklingsmiljö Xcode – både för iOS och Mac OS X. Dock är LLVM inte specifikt för Mac, utan finns till många olika OS, bland annat som del av FreeBSD sedan ett drygt år tillbaka. Här är och en lista på produkter, system och projekt där LLVM används.

Det jag gillar med LLVM och inte minst dess C-kompilator clang är att dess förmåga att detektera fel och generera bra felmeddelanden. Speciellt i jämförelse med gcc är clang mycket mer hjälpsam. I mina tester genererar clang+LLVM mer kompakt kod än gcc, och oftast även snabbare program. Dessutom kompilerar oftast clang+LLVM snabbare än gcc.

LLVM inkluderar inte bara clang, utan flera andra bra verktyg. Debuggern LLDB är fortfarande ett relativt ungt verktyg, men är redan riktigt bra. Inte minst att LLDB går att integrera med Python öppnar upp för automatiserad debugging och analys. Ett annat verktyg i familjen jag tidigare skrivit om är den statiska kodanalysator som finns till clang.

Clang STA-rapport.
Exempel på rapport från Clangs STA-verktyg.

Det pågår även ett aktivt arbete med att utveckla nya funktioner runt LLVM. Projektet SAFECode är ett exempel. SAFECode försöker att genom en kombination av statiska och dynamiska kontrollmekanismer generera säker kod med minimala kostnader i form av kodstorlek och prestanda.

LLVM+clang är stabila verktyg som integrerar väl med befintliga kompileringsmijöer, speciellt GCC. Om du använder GCC men inte redan testat LLVM+clang tycker jag att det är dags att göra det.

Jakten på den fungerande kryptoimplementationen

Jag fick för en dryg vecka sedan skäl att börja arbeta med på en hårdvaruimplementation av blockkryptot CAST. Mer exakt CAST5 med stöd för 40, 80 och 128 bitars nyckel. Den referensdokumentation som finns för CAST är RFC 2144.

RFC:n innehåller tack och lov testvektorer. Men, vilket tyvärr är vädligt vanligt i kryptospecar brister det i entydighet. I fallet RFC 2144 är saker som bitordning på orden och nycklar mindre exakt specat. Det går att gissa, men hade underlättat om det var tydligare. Och det är nu en referensmodell är så värdefull.

Nu finns det ingen utpekad officiell referensmodell att hämta hem. Då är nästa steg att hitta en implementation, helst en som används och går att lita på fungerar. Tyvärr är kryptoimplementationer vanligen optimerade för prestanda med utrullade loopar, inline-assembler och andra trick som gör att dom strukturmässigt kan skilja rätt mycket mot specifikationen.

Sökning på nätet ger att Bruce Schneier har några stycken implementationer av CAST på den CD som följde med hans gamla bibel Applied Cryptography. Jag började titta på implementationen CAST-BAR (zipfil) och jösses.

Bibeln.
Bruce Schneiers stora röda. En bibel för kryptonörden. I dag ersatt av Cryptography Engineering.

Applied Cryptography är gammal, och CAST är ännu äldre (RFC 2144 är från 1997). Och koden i CAST-BAR har knappast åldrats med grace. Men det är faktiskt värre än så – den kan aldrig ha fungerat.

CAST är ett blockkrypto med en struktur som kallas SP-nät och är ett (balanserat) Feistel-krypto. Figuren nedan visar hur iterationen i CAST är uppbyggd:

Iterationen i CAST.

Notera speciellt de fyra lådorna märkta S-box1, …, S-box4. Dessa lådor innehåller de utbytestabeller (S-box) som ger olinjäriteten i CAST. Det finns fyra olika fixa S-boxar i CASTs iteration. Vidare finns det ytterligare fyra andra fixa (dvs med fixt innehåll, ej nyckel eller databeroende) S-boxar som del av kryptots nyckelexpansion. Totalt åtta tabeller om 256 stycken 32-bitars ord vilket kräver 8 kByte ROM-minne. Tabellerna finns listade i appendix A i RFC:n. Men i CAST-BAR finns inga tabeller.

Det som finns är en deklaration #include "cast_tab.h" som uppenbarligen pekar ut en fil där tabellerna skulle vara deklarerade. Men ingen sådan fil finns med i ZIP-filen. Nu var det inte jättesvårt att skapa sig en sådan fil med tabellerna och försöka bygga kryptot. Då kom nästa problem.

Jag kör som standard med den lysande kompilatorn clang (och llvm). Den hostade rejält på ett antal saker i koden. Inga speciellt allvarliga utifrån ett syntax-perspektiv. Men det det är uppenbart att C har blivit mycket striktare och (likt det jag efterfrågar från kryptospecar) mer entydigt. Koden i CAST-BAR är långt ifrån C99. Det gick dock bra att putsa till koden och få den att bygga (utan varningar). Dags att provköra:

js@snabbis>./cast
usage: cast [ n | -x | -y ]
n (integer) will encrypt n times (useful for timing tests)
-x will test the code by encrypting once (and print out the reference vector)
and then run the 1000000 iteration Full Maintenance Test (with reference output)
-y will test the code by encrypting once (and print out the reference vector)
and then run a shortened 1000 iteration Partial Maintenance Test (with reference output)
( which is more convenient for debugging than the Full test
This code is an implementation of CAST-128

js@snabbis>./cast -y
key is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a

Segmentation fault

Oops.
Test i debuggern visar att programmet hoppar rätt ut i skogen pekarmässigt. Lite koll på typer visar att det förutsätts implicit en massa storlekar som inte alls stämmer på en system med 64-bitars arkitektur. Jag testar att flytta koden till min utvecklingsmaskin sbox som kör 32-bit GNU/Linux. Och där fungerar det.

Dags att städa upp i typträsket. Jag gillar stdint.h. Den gör det entydigt vad man verkligen vill ha och kan vara (hyggligt) säker på att det man deklarerar stämmer på olika plattformar. En stunds arbete med att byta ut long int, unsigned char etc mot uint32_t, uint8_t etc och sedan är det dags för nytt försök på min 64-bitsmaskin:

js@snabbis>./cast -y
key is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a

Single Key-Plaintext-Ciphertext Test:
plaintext is: 01 23 45 67 89 ab cd ef
iter = 1
ciphertext is: 23 8b 4f e5 84 7e 44 b2
ref text is: 23 8b 4f e5 84 7e 44 b2
after decryption:
ciphertext is: 01 23 45 67 89 ab cd ef

Partial Maintenance Test (only 1000 iterations):
key is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a

a is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a
b is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a
a is: 23 f7 3b 14 b0 2a 2a d7 df b9 f2 c3 56 44 79 8d
ref a is: 23 f7 3b 14 b0 2a 2a d7 df b9 f2 c3 56 44 79 8d

b is: e5 bf 37 ef f1 4c 45 6a 40 b2 1c e3 69 37 0a 9f
ref b is: e5 bf 37 ef f1 4c 45 6a 40 b2 1c e3 69 37 0a 9f

Sådär. En fullt fungerande implementation av CAST. Synd bara att koden är skriven på ett i stort sett oläsbart och (försök till) prestandamaximerat sätt vilket gör den väsentligen oanvändbar som referensmodell.

Jag tycker att det inte är så konstigt om såpass gammal kod inte fungerar då de implicita förutsättningarna ändrats. I dag bör man i alla fall se till att koda på ett sätt som minimerar eller helst eliminerar implicita förutsättningar. Men att ingen sedan 1996 eller så testat CAST-BAR och sett att det saknas en fil är desto mer förvånande. Jag har haft kontakt med Bruce och levererat den uppdaterade, hela och fungerande versionen av CAST-BAR till honom. Den bör dyka upp på hans webbplats i närtid.

Så nu är det bara att jaga vidare efter en användbar referensmodell. Eller så får det bli som jag gjort mer än en gång – skriva en egen referensmodell i Python. Ett utmärkt språk för att skriva funktionella referensmodeller. All in a days work. Kul!

Om slumptal och entropikällan Haveged

Tidigare i vår, i samband med en säkerhetsanalys träffade jag på entropikällan Haveged. Vad är nu en entropikälla och vad ska man med en sådan till?

Datorer är digitala, exakta maskiner. Men för att fungera, och inte minst fungera säkert behöver ett datorsystem tillgång till slumptal. Både operativsystem och applikationer använder slumptal för att fungera. Processnummer, TCP-sekvensnummer, kryptonycklar, startvärden vid simuleringa eller för den delen vilka man kort får kort i datorns pokerspel kräver alla tillgång till bra slumptal. Därför finns det slumptalsgeneratorer i alla datorsystem.

En slumptalsgenerator (Random Number Generator – RNG, eller ibland True RNG) består väsentligen av två delar:

  1. En entropikälla
  2. En pseudo-slumptalsgenerator (Pseudo Random Number Generator – PRNG)

Entropikällan är något som mäter upp någon form av fysisk, slumpmässig process – något som ger entropi. Klassiska exempel är brus i halvledare, kosmisk strålning (pdf), radioaktivt sönderfall samt rörelserna i en Lava-lampa.

Lava-lampa

En viktig aspekt hos en bra entropikälla är att den inte enkelt ska kunna påverkas, utan att det går att lita på att de värden som mäts upp är slumpmässiga.

När tillräckligt med entropi samlats in används detta sedan för att intiera PRNGn. Eventuellt filtreras entropin innan den används (kallas whitening).

PRNGn å sin sida är en deterministisk algoritm som utifrån ett startvärde generar en sekvens av värden som utifrån statistisk analys möter en slumpmässig fördelning. Startvärdet kallas ofta frö eller initialvektor. Efter att ett antal värden genererats startas PRNGn om med ett nytt frö från entropikällan. Notera att om samma frö används mer igen kommer samma sekvens att genereras.

Det finns ett otal slumpmässiga fördelningar exempelvis Poissonfördelning och Normalfördelning. Men för saker som kryptonycklar vill man ha en fördelning där alla värden är lika troliga, dvs en rektangelfördelning (eller likafördelning).

Det finns en massa andra krav att ställa på PRNGn – att det ska vara snabb, men även att det inte ska gå att gissa vilket frö som använts eller att det ska gå att gissa föregående eller kommande värden utifrån att ha sett ett eller flera värden.

Det finns ett stort antal PRNG-konstruktioner, en del bättre och en del sämre – utifrån kriterier som prestanda, resursbehov och säkerhet. LFSR-kedjor har tidigare använts för att de ger en bra fördelning och kräver få resurser. Men säkerhetsmässigt är dom kort sagt usla och ska inte användas.

Yarrow och Fortuna är säkerhetsmässigt bra generatorer designade av bland annat Bruce Schneier och är bra exempel på där kryptografiska funktioner används för att bygga PRNGs. I Linux används kryptografiska hashfunktioner och i andra operativsystem används strömkryptot RC4 (vilket inte är speciellt bra rent säkerhetsmässigt). Men var får man sin entropi ifrån?

I Yarrow och Fortuna finns funktioner för att samla på sig entropi. Men var entropin ska komma ifrån finns det ingen information om. När det kommer till entropikällan är det av naturen lite svårare att med generella lösningar eftersom det beror på vilka fysiska processer som finns i det specifika systemet och som går att mäta på.

För vanliga datorer, servrar finns det ett dokument med råd om hur man kan göra. RFC 4086, Randomness Requirements for Security beskriver hur saker som tid mellan inkommande datapaket, tid mellan tryck på tangentbord, varvtal i hårddiskar och fläktar kan användas som entropikällor.

Men i ett inbyggt system som exempelvis ska bo i skogen och övervaka vatten-nivån i en cistern saknas ofta dessa entropikällor. Vatten-nivån varierar troligen så långsamt att den inte är en bra källa till entropi, något annat indikerar antagligen att det är dags för systemet att skicka ett larm.

För ett inbyggt system kan det alltså vara svårt att få tag på tillräckligt med entropi för att driva sin RNG. Är det dessutom ett UNIX-baserat system (Linux) kommer /dev/random (slumptalsgeneratorns nod i filystemet) att låsa vid anrop tills dessa att det finns slumptal att leverera. Detta innebär att applikationen hänger och kan inte göra sitt jobb. Att istället anropa /dev/urandom löser problemet med eventuell låsning, men då finns det å andra sida en risk att få återanvända, säkerhetsmässigt tveksamma slumptal. Och det är här Haveged (till slut, pust!) kommer in i bilden.

Haveged är en slumptalsgenerator som implementerar algoritmen HAVEGE – HArdware Volatile Entropy Gathering and Expansion. Havege är en algoritm som försöker tvinga processorn att bli en entropikälla. Detta innebär att det inte behövs någon extern, fysisk process att mäta på. Men hur fungerar den – och fungerar den verkligen?

I en modern processor som Intels Core i7 består av ett stort antal digitala funktioner som, även om dom var och en är exakta, tillsammans bildar ett dynamiskt system vars beteende på olika sätt kan vara svårt att gissa. Exempelvis kan tiden tiden det tar att utföra (exekvera) en instruktion variera. (Värsta exekveringstiden – WECT är ett mått som används för att estimera prestanda på en processor.)

Några saker som påverkar exekveringstiden är cacheminnen, inhämtningsbuffrar, schemaläggare, hoppspekulering etc. Det är detta Haveged utnyttjar.

I x86-processorer såväl som andra processorer finns det interna räknare (Time Stamp Ccounter – TSC) för att mäta exekveringstid. Dessa räknare går att läsa ut av program som körs av processorn.

Haveged består väsentligen av två delar. Den ena delen är ett program som med ett stort antal loopar och villkorade hopp försöker provocera fram missar i cacheminnen, hoppspekulering etc. Detta för att få till en spridning av exekveringstiden. Bland annat använder Haveged roligt nog Duff’s Device. Den andra delen är en insamlingsfunktion som läser av TSC och från den plockar värden som entropi.

För den som är intresserad finns det ett par forskningsartiklan om algoritmen HAVEGE att läsa. Artikel ett – HAVEGE: a user-level software heuristic for generating empirically strong random numbers. Artikel två – HArdware Volatile Entropy Gathering and Expansion: generating unpredictable random numbers at user level. Det finns även en preso om HAVEGE.

Eftersom jag arbetat med processorarkitekturer i många år blev jag naturligtvis nyfiken på Haveged. Hur mycket påverkas Haveged av designen hos de olika funktionerna i processorn? Hoppspekuleringen i Intels Core 2 Duo och nya, fräcka Core i7 skiljer en hel del. Andra saker som skiljer är såväl storlek som funktion hos cacheminnen. Och hur blir det när man kör Haveged på en helt annan arkitektur som inte har cacheminnen, exempelvis en microcontroler som Atmels AVR, en inbyggd processor som ARM7 eller för den delen i en virtuell maskin?

Atmel AVR-processor.

För att testa detta började jag labba med att köra Haveged på några olika x86-processorer jag har tillgång till. Haveged kommer med två testprogram – ent och nist. Det förra är ett enklare testprogram utvecklat av Havegeds skapare, det senare en impementation av NISTs testsvit.

Utifrån mina tester verkade det inte spela någon roll alls vilken x86-arkitektur jag använde. Sedan testade jag att köra virtualiserat med en Linux-installation i Virtualbox (Vbox). Nu är det så att Vbox kör så nära den fysiska maskinen som möjligt och det innebär att exekveringstiden som mäts i den virtuella maskinen blir samma som den fysiska exekveringstiden. Det vi behöver är en emulator där processorn också är simulerad och ger syntestiska värden på TSC.

Nu har jag inte tillgång till en bra emulator. Men en som har en bra emulator, och dessutom är riktig processorexpert är Jakob Engblom på Wind River (som köpte Virtutech).

Jakob Engblom på Wind River

Wind Rivers Simics är en simulator kapabel att simulera (emulera) ett helt datorsystem inkl all hårdvara och dessutom samla in mätdata på det simulerade systemet så att det går att analysera och därmed få klarhet i systemets dynamiska beteende. Mycket praktiskt.

Jag kontaktade Jakob som gjorde ett antal försök med Haveged. Resulatet har han dokumenterat i ett par utmärkta postningar (Execution Time is Random, How Useful, Evaluating HAVEGE Randomness) på sin även i övrigt utmärkta blog.

En sak med Haveged är att den, förutom att den är väldigt mycket kopplad till x86 integrerar sig med Linux. Den tillhandahåller inte slumptal direkt, utan skriver till /dev/random. Detta gör det svårt att separera slumptalen genererade med Haveged med slumptal genererade på annat sätt i systemet. Men det går ju alltid att hacka om. Det vi vill testa är ju hur bra entropi som trillar ut från Haveged och om hur de påverkas av arkitekturen.

Resultatet av Jakobs testkörningar visade ett par saker:

  1. Haveged fungerar, men beror till stor del på att andra processer och OS:ets interna funktion, som alltid pågår, stör exekveringen av Haveged och påverkar den uppmätta exekveringstiden.
  2. Havegeds mätsystem är riktigt trasigt. Även om Jakob tvingade TSC att rapportera konstanta värden meddelade testprogrammet ent glatt att det blev slumptal av hög kvalitet.

Nå, så vad är kontentan av dessa tester – går Haveged att använda? Ja Haveged verkar fungera och för ett inbyggt Linux-system på x86 kan Haveged tillföra en bra entropikälla. Speciellt i ett system med få processer – både fysiska att mäta på och sådana som snurrar i OS:et.

Men vad gäller Havegeds opålitliga testsysteme sätter det fingret på ett problem jag pratat om i några år nu. Att inte blint lita på sin slumptalsgenerator, men även svårigheten att mäta upp hur den fungerar och mår.

RFC 4086 nämner inget om hur man ska testa sin generator, vilket jag tycker att den borde. Ska man följa det dokumentet ska man flyga i blindo och hoppas att entropikällorna lever och mår bra. Men det är inte alls säkert att dom gör.

För ett par år sedan undersökte Travis Goodspeed generatorn i Texas Instruments Z-Stack. Han upptäckte att den hade mycket sämre slump än förväntat och repeterade på ett förutsägbart sett.

Mönster hos slumptalen från TIs PRNG.
Mönster hos slumptalen från TIs PRNG.

Detta problem är sedan dess fixat vilket Travis verifierat. Men frågan är hur många av TIs kunder som märkte problemet när dom utvecklade sina produkter och har mycket sämre säkerhet och funktion än dom vet om?

Andra exempel på entropikällor är de digitala oscillatorer man ofta bygger in på chip. Bitmönstret ut från flera oscillatorer mixas och används som entropikälla. I vissa fall, beroende på processhörn och temperatur har oscillatorerna låst till varandra på ett oönskat sätt och gett ett repeterbart mönster. En bra beskrivning av hur denna typ av RNG kan fungera finns i en artikel från Via. Notera att det inte är denna RNG jag avser som fallerat.

Ett ytterligare exempel jag sett är där man plockar de lägsta bitarna på värdet av en radiomottagares signalstyrka (RSSI) som entropikälla. Men då radiomottagare varit trasig har entropin inte alls varit så slumpmässig som man trott.

Det finns bra tester för att utvärdera slumptalsgeneratorer. Ett sådant testsystem är DIEHARD. Dessa tester kräver dock mycket testdata, är komplicerade och tar lång tid att köra. Att implementera DIEHARD på ett inbyggt system är ställer enligt mening i det flesta fallen orimliga krav på resurser. Däremot går det att i alla fall köra enkla tester som kan detektera om generatorn är ordentligt trasig. Några saker man bör klara av att testa på ett inbyggt system är:

  1. Generatorn fastnat och ger ett statiskt värde (bara nollor, bara maxvärde etc). Kräver att du har en enkel räknare som du resettar varje gång ett avläst värde från slumptalsgeneratorn skiljer från föregående värde, men räknar upp med ett om värdena är lika. Om räknarens värde är mycket större än något tiotal har du troligen problem med din generator.
  2. Slumptalen fyller ut fördelningsrummet, dvs min- och maxvärdena du ser över tiden. Om generatorn fungerar ska min- och max hamna nära de min- och maxvärden din talrymt kan ge. Om du har en generator som ger ut 8-bit värden bör du över tiden ha minvärdet 0 och maxvärdet 255. För att mäta detta behöver du jämföra genererat värde med tidigare sedda min- och maxvärden och dom det är mindre (eller större för max) uppdaterar ditt sparade värde.
  3. Medelvärdet är förskjutet. Om din generator ger 8-bit tal och medelvärdet över tiden ligger nära noll har du en rejäl förskjutning av medelvärdet.

Mitt råd är att som del av verifieringsarbetet under utveckling av din produkt, samt gärna även som del av kvalitetskontrollen i produktionen (och då stickprovsmässigt), testa din slumptalsgenerator ordentligt. Generera stora mängder med tal och klappa till dom med DIEHARD och liknande tester.

Sedan är mitt råd att du i systemet implementerar några enklare tester, exempelvis de jag beskrivit ovan för att kunna fånga upp de rent patologiska fallen. En lärdom från Haveged-undersökningen är att applicera dessa tester på entropikällan, inte hela generatorn. Det du vill testa är att den insamlade entropin som du driver din generator med inte är helt åt skogen. Även om ditt system sitter ute i skogen.

Men hur var det då med enklare processorer som AVR, ARM? Där är jag än så länge osäker på hur väl HAVEGE fungerar. För ett par dagar sedan fick jag skäl att fundera på den frågan igen.

Jag satt och körde den statiska kodanalys som finns för kompilatorn clang/llvm. Testobjektet för körningen är ett SSL-bibliotek för inbyggda system kallat PolarSSL. PolarSSL finns portat bland annat till ARM-processorn och 68k-baserade controllers. Och ser man på, PolarSSL innehåller faktiskt en implementation av HAVEGE-algoritmen i sin slumptalsgenerator! Jag har inte testat hur väl den fungerar, men det ska jag självklart göra.

clang STA
Exempel på resultat från STA-körning med clang.

Jag hoppas att denna text (som blev mycket, mycket längre än jag tänkt) har gett dig insikt i några saker. Det jag hoppas att du tar med dig är:

  1. Vad en slumptalsgenerator är. Entropikälla, RNG och PRNG
  2. Att det, inte minst för inbyggda system, kan vara svårt att få tag på tillräckligt med entropi
  3. Att exekveringstiden för instruktioner, speciellt i moderna, komplexa processorer varierar
  4. Vikten av att testa sina slumptalsgeneratorer

Och vad gäller HAVEGE på små inbyggda procesorer ber jag att få återkomma.