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.

4 reaktioner på ”Om slumptal och entropikällan Haveged

  1. Tack för en mycket intressant postning.

    Jag tycker att du sätter fingret på något synnerligen intressant när du adresserar kvaliteten på entropikällor för mindre inbyggda system. I förlängningen så kan det vara en riktigt stygg svaghet.

    Idén att bygga in en enklare entropitest låter helt klockren den med. Att blint förlita sig på sina entropikällor kan verkligen få förödande resultat, speciellt om den matar någon kryptografiskt klen mekanism för att generera slump.

    Jag ser fram emot att höra mer om HAVGE och inyggda processorer.
    /Kalle

  2. Mycket intressant!

    Utan något som helst eget behov, för tillfället iaf, undrar jag om det inte finns några trevliga effekter på kisel som går att använda som källa till entropi? Spontant känns det som att man hårdvarumässigt borde kunna göra någon funktion som läser av de olika källorna av brus som finns på ett chip, och att det borde kunna vara ännu bättre än att mäta bruset av exekveringstid. Kanske finns ingen anledning, lättare att göra det mjukt såklart, och då behöver man inte göra sina egna chip heller!

    /Peter

    1. Aloha!

      Jo, det finns flera analoga effekter att mäta på chip. Ett vanligt sätt är att sätta upp ett antal kedjor med inverterare, väsentligen binära ringoscillatorer. Sedan mixar man värdena dessa genereras. Tyvärr har dom visat sig känsliga för processvariationer, temperatur och bias-påverkan genom yttre växelfält. Mina förslag att testa gäller fortsatt.

      Det går även att mäta backspänning på dioder som uppvisar fint brus.

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *