Etikettarkiv: verktyg

Mac OS X får stöd för virtualisering

(Uppdaterad 2011-07-05, tack JakobS.)

Apple förväntas släppa en ny version av sitt operativsystem för datorer och servrar inom ett par veckor. I går, fredag 2011-06-01 släpptes Golden Master (GM) till utvecklare, och om inget allvarligt hittas är det sannolikt att det blir den officiella versionen. Mac OS X 10.7 med kodnamnet Lion kommer med ett flertal förbättringar som Apple visat upp sedan tidigare.

Men en sak som dök upp i går är att desktopversionen av Mac OS X får samma rätt att köra virtualiserad som serverversionen. Macrumors skriver om den nya funktionaliteten:

For the first time, Apple is allowing owners of OS X (client version) to run multiple virtual copies on the same machine. Previously, Apple extended this ability to Mac OS X Server only. Running separate instances of Mac OS X should be possible under virtualization solutions such as VMware Fusion and Parallels. This functionality allows you to deploy different sandboxed installations of OS X, typically for enterprise purposes.

Virtualisering på Mac.

Mac OS X har sedan tidigare stöd för att stänga in, sandboxa enskilda applikationer, en funktion som förbättras i Lion. Ett bra exempel på hur applikationer kan stoppas in i en sandlåda är IronFox och IronBird.

Att kunna virtualisera hela OS:et gör det enklare att sektionera sin användning till olika områden, inte bara på enskilda applikationer. Du får därmed kontroll över flera applikationer samt data på en gång, mycket bra inte bara för företagsbruk. Det finns en avtalsmässig begränsning av antalet instanser du kan köra samtidigt, vilket dock kanske är tillräckligt många:

(iii) to install, use and run up to two (2) additional copies or instances of the Apple Software within virtual operating system environments on each Mac Computer you own or control that is already running the Apple Software.

Detta är en av flera bra nya säkerhetsfunktioner jag ser fram emot att få testa närmare om ett par veckor.

Hur du kommer igång med SDL

Fick ett tips om att Microsoft släppt en packe med mallar för att hjälpa till att sätta upp och komma igång med SDL – Security Development Lifecycle.

SDL-loggan.

I bloggpostningen I’m starting to use the SDL, but how do I…? beskriver Jeremy Dallman från Microsofts SDL-team hur man kommer igång med SDL genom att börja jobba med de olika SDL-stegen och hur mallarna stöttar detta arbete.

Packen med templates är en zipfil på 6.3 MByte med ett antal DOCX-filer. (En liten detalj är att filerna inte ligger i en egen mapp.) Jag tittade igenom dokumentet för hotmodellering och tycker att det såg mycket bra ut. Enkelt att förstå och en bra bas för att genomlysa ett systemförslag utifrån säkerhetsaspekter. Inte minst gillar jag sektionen om att lista alla antaganden man gjort. Min erfarenhet är att det är implicita antaganden som ofta leder till överraskande problem.

Bra verktyg: Immunitydebugger

Ett snabbt tips på ett i mitt tycke bra verktyg för att analysera, undersöka och laborera med assemblerkod: Immunity Debugger. Förutom att ha många av de vanliga debugger-funktionerna kan man få funktionsgrafer. Men den stora fördelen är att debuggern är skriven i Python och kommer med ett omfattande API som gör att det går att bygga nya kodverktyg.

En gång i tiden körde jag GNU DDD – Data Display Debugger en grafisk debugger som bland annat gör att du kan titta på datastrukturer under körning av program. Så här kan det se ut:
Datastruktur i DDD.

När jag arbetade med att utveckla optimerare för nätlistor (ett VLSI-syntesverktyg) var detta en funktion som var en oerhörd hjälp. Tyvärr verkar DDD vara ett övergivet projekt – ingen ny version sedan 2009.

Cookie-RFCn 6265

Daniel Stenberg har skrivit en bra postning om den nya RFC, RFC 6265 – HTTP State Management Mechanism som dokumenterar Cookies.

Det är rätt märkligt att en mekanism på Internet som är så otroligt vanlig inte varit ordentligt specificerad. Min uppfattning är att denna brist på specifikation och dokumentation är ett skäl till att cookies varit en källa till sårbarheter och säkerhetsproblem. Förhoppningsvis leder den nya RFCn till att det går att städa upp implementationer. Och inte minst att RFCn blir ett avstamp för vidareutveckling.

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!

Konvertera sbox till hårdvara

Sitter och tittar på Bentfunktioner. Dessa används i vissa fall för att skapa ersättningstabeller (sbox) i krypton. Ett krypto som använder detta är det symmetriska blockkryptot CAST.

För att analysera hur en sbox beter sig bitmässigt kan det vara intressant att omvandla tabellen till en uppsättning ANF-nät. Detta är nätlistor med logiska AND-OR-operationer med tabellens inoperands bitar som invärden. En nätlista skapas för varje bit ut från tabellen. Och som tur är det har Bo Zhu vid Shanghais universitet hackat ihop ett verktyg som gör detta.

Sbox2ANF är ett GPL-licensierat Pythonprogram som kan ta en Sbox-tabell och generera nätlistor för alla utbitar:
The sample sbox
y = sbox(x) = (0, 2, 4, 6, 7, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15)
has been translated to ANF Boolean functions

y0 = x2 + x0x2 + x1x2 + x0x1x2 + x3 + x2x3 + x0x2x3 + x1x2x3 + x0x1x2x3
y1 = x0 + x2 + x0x2 + x1x2 + x0x1x2 + x2x3 + x0x2x3 + x1x2x3 + x0x1x2x3
y2 = x1 + x2 + x0x2 + x1x2 + x0x1x2 + x2x3 + x0x2x3 + x1x2x3 + x0x1x2x3
y3 = x0x2 + x1x2 + x0x1x2 + x2x3 + x0x2x3 + x1x2x3 + x0x1x2x3

Eftersom det är ett Pythonprogram går det naturligtvis även att importera in och använda som byggblock i sina egna program. Väldigt praktiskt, exempelvis som i mitt fall där jag bygger generatorer för hårdvarubeskrivningar av krypton och vill kunna välja hur en sbox ska implementeras. Antingen som en tabell som kräver ROM-minne, eller som en uppsättning logiska grindar.

Analysera chip med degate

(Tipstack till JonasT) Det finns ett verktyg kallat Degate avsett att användas för att analysera digitala integrerade kretsar (chip). Degate har bland annat använts för att analysera en chip-implementation av kryptot i DECT.

Degate
Degate.

Att analysera kretsar är inget nytt och det finns flera olika företag som gör detta, ex Flylogic Engineering och Chipworks. Dessa företag kör antingen med kommersiella verktyg eller egenutvecklade. Att se ett öppen kod-verktyg för den här typen av arbete har jag dock aldrig sett.

Och Degate är inte bara användbart för att göra analys av befintliga chip, utan är even avändbart under utveckling och debug på låg nivå. Degate inkluderar bland annat funktionalitet för kontrollera designregler (DRC).

sidan med dokumentationen för Degate finns även en del filmer och presentationer som visar analys av olika chip, hur man plockar kapseln av ett chip och skapar bilder att analysera.

libssh2 1.2.8 släppt

I går släpptes en ny version av ssh-klientbiblioteket libssh2. Version 1.2.8 innehåller i första hand buggfixar, men inkluderar även en del nya funktioner samt en klart förbättrad prestanda för sftp. Ändringslistan ser ut som följer:

Changes:
* added libssh2_free, libssh2_channel_get_exit_signal and libssh2_session_handshake
* SFTP read/write remade and now MUCH faster, especially on high latency connections
* added new examples: ssh2_echo.c, sftp_append.c and sftp_write_sliding.c
* userauth: derive publickey from private
* NEWS: now generated from git

Bug fixes:
* Support unlimited number of host names in a single line of the known_hosts file.
* fix memory leak in userauth_keyboard_interactive()
* fix memory leaks (two times cipher_data) for each sftp session
* session_startup: manage server data before server identification
* SCP: allow file names with bytes > 126
* scp_recv: improved treatment of channel_read() returning zero
* libssh2_userauth_authenticated: make it work as documented
* variable size cleanup: match internal variable sizes better with the sizes of the fields used on the wire
* channel_request_pty_size: fix reqPTY_state
* sftp_symlink: return error if receive buffer too small
* sftp_readdir: return error if buffer is too small
* libssh2_knownhost_readfile.3: clarify return value
* configure: stop using the deprecated AM_INIT_AUTOMAKE syntax
* Fixed Win32 makefile which was now broken at resource build
* kex_agree_hostkey: fix NULL pointer derefence
* _libssh2_ntohu64: fix conversion from network bytes to uint64
* ssize_t: proper typedef with MSVC compilers
* zlib: Add debug tracing of zlib errors
* decomp: increase decompression buffer sizes

IDG listar Sveriges främsta IT-säkerhetsexperter

IDG har publicerat sin årliga lista över Sveriges främsta IT-säkerhetsexperter. I år har Robert Malmgren hamnat i topp.

Robert Malmgren
Robert Malmgren

Ett bra och välförtjänt val. Stort grattis! IDG har även en läsvärd intervju med Robban som visar hur insatt och pedagogisk han är. Få kan sätta IT-säkerhet i sitt sammanhang lika bra. Grattis Robban!

Värt at notera att Robert Malmgren och hans företag ligger bakom IronFox och IronBird. Dessa program gör Firefox och Thunderbird mycket säkrare genom att stoppa in dom i en sandlåda. Är du Mac-användare och använder dessa verktyg bör du testa dessa.

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.