Etikettarkiv: RNG

Sidokanaler och trojaner i ASICar

De senaste veckorna har det varit mycket diskussioner om bakdörrar och säkerhet i hårdvara. Därför är det extra spännande att läsa ett par artiklar som belyser denna problematik.

Den första artikeln, On Measurable Side-Channel Leaks inside ASIC Design Primitives tittar närmare på vad som orsakar informationsläckage via en så kallad sidokakanal i form av strömförbrukning i kundspecifika digitala kretsar. Kundspecifika digitala kretsar (ASIC:ar) designas oftast genom att använda så kallad standard cell-teknik. Det innbär att den digitala funktionen bryts ner till instanser av grindar (kallade celler) som skapats och kvalificerats för en given tillverkningsprocess hos en tillverkare. Vill vi exempelvis producera vårt nya mobilchip i TSMCs 55-nm-process behöver vi använda ett bibliotek där cellerna instansierats i testkretsar och sedan testats för att se att deras elektriska egenskaper. En sådan leverantör är EDA-draken Synopsys som har kvalificerade cellbibliotek för flera leverantörers processer.

Det artikeln nu visar är hur differentiell strömförbrukning i ASIC:ar ger upphov till sidoinformation som går att mäta. Och dom kan koppla sidoinformationen till såväl vilka celler som används och placeringen av celler på kretsytan. Den senare är speciellt intressant då det visar att valet att det inte bara är den digitala funktionen och därmed vilka celler som används, utan även placeringen av cellerna påverkar (vilket iofs krav på drivstyrka och därmed vilken storlek på cellerna som används). Sedan går tyvärr artikeln in i diskussioner om hur celler kan byggas för att skydda mot oavsiktliga sidokanaler. Men som nästa artikel visar är det minst sagt svårt.

Den andra artikeln, Stealthy Dopant-Level Hardware Trojans (PDF) som presenterades på konferensen CHES 13 är mer spektakulär. I artikeln visar författarna hur man genom att ändra den så kallade dopningen kan påverka den digitala funktionen i en krets, utan att modifiera nätlistan [1]. Genom att selektivt modifiera dopningen lyckas man åstadkomma två saker.

  1. grindar celler att låsa i ett fast läge. Exemplet som används är en fristående implementation av Intels slumptalsgenerator RdRand/Bull Mountain som finns i Ivy Bridge och senare processorer.
  2. Få grindar att ändra elektriskt beteende och därmed förbruka mer ström än som är specat för vissa bitkombinationer. Exemplet är S-boxen i AES implementerad med grindar signade för att skydda mot sidokanalsläckage.

Utgångspunkten för den modifierade funktionen i slumptalsgeneratorn är att tvinga en vanlig, enkel inverterare att alltid låsa till ett fast värde ut oavsett värde in. Förändringen är subtil (vilket visar hur svårt det skulle vara att se vid granskning). Förändringen möter även de automatiska kontroller (Design Rule Check – DRC) som körs när masksetet skapas.

Trojansk inverterare
Trojansk inverterare

Men en inverterare som fastnat – det är ju ett vanligt problem och ska detekteras som del i produktionstest av kretsen, kan man tycka. Och normalt sett, om man använt bra ASIC-metodik ska detta upptäckas. I fallet med Intels slumptalsgenerator är det dock så att man av säkerhetsskäl undantagit generatorns digitala funktioner från att finnas med i scankedjor (som används för att läsa in olika testmönster i kretsen och sedan observera resultatet). Istället används en inbyggd självtestningsfunktion (Built In Self Test – BIST). Det är den lokala BIST-funktionalitetens uppgift att testa generatorn och sedan till övriga kretsen rapportera om generatorn fungerar eller ej. Ja eller nej. Ett eller noll.

Genom att både modifiera dopningen i grindar i generatorn OCH grindar i BIST-funktionaliteten får generatorn att generera mycket sämre slumptal utan att BIST-enheten rapportera att den är trasig. Lurigt.

Den andra attacken är mer subtil. Där ändras inte den logiska funktionen i grinden. Dessutom, vilket gör det mer intressant är de celler som används inte vanliga celler, utan celler som författarna tidigare utvecklat för att skydda mot den typ av sidoläckage som den första artikeln beskriver. Celler som är mycket mer robusta än de författarna till den första artikeln föreslår. Genom att påverka dopningen i en AOI (AND-OR-Invert)-grind får man grinden att förbruka energi även om den ger en logisk nolla ut och därmed ska dra mycket lite ström.

Trojansk AOI-cell.
Trojansk AOI-cell.

Resultatet är att även om cellen är så konstruerad att den inte ska läcka information om kryptonyckeln kan författarna visa att dom kan detektera nyckelns bitar genom att observera strömförbrukningen.

Läckage av nyckelinformation.
Läckage av nyckelinformation.

För mig som gillar hårdvara och ASICar är det här otroligt fräckt. Speciellt den senare attacken där den logiska funktionen inte ändras är riktigt snygg och rätt skrämmande.

Den jag saknar i artikeln är hotbildsanalysen – vem är det som är motståndaren och vilka resurser har denne. För att kunna ändra dopningen på specifika ställen på kretsen krävs insikt om kretsens funktion så att rätt område hittas. Och dessutom behöver detta ske någonstans mellan att underlaget till kretsen skett (sign-off) och testkretsar levererats. Det är relativt kort tid för att hitta rätt ställe att modifiera, analysera kretsen och föra in modifieringar i underlag för maskset. Att förstå en krets genom att titta på masksetet är inte enkelt (för att uttrycka det milt). Den som troligen utför attacken måste nästan sitta där designen av kretsen sitter, inte hos tillverkaren för att helt enkelt ha tillgång till så mycket designinformation att modifieringarna ska hinna göras. Sedan beror detta naturligtvis på var i utvecklingskedjan överlämning från designhus till tillverkaren sker.

Att dopning kan påverka funktionaliteten, inte minst hos mer analoga funktioner är inget nytt. När man tillverkar integrerade kretsar pratar man om processhörn (process corner), vilket är det gränser över vilka de olika process-stegen tillsammans ger kretsar med olika elektriska egenskaper. Om en krets innehåller en mer analog funktion kan dess beteende påverkas. Jag drar mig till minnes att Hifn en gång i tiden tillverkade och sålde en kryptokrets med inbyggd slumptalsgenerator byggd med en kedja av inverterare. Genom en olycklig kombination av processhörn och temperatur kunde vissa kedjan av inverterare (som skapar en oscillator) låsa mot en inre klocka. Följden blev att generatorn skapade tal i ett snyggt, periodiskt och inte alls speciellt slumpmässigt mönster. (Försöker hitta info och modellnummer om detta men hittar inte. Uppdaterar när jag har mer).

[1] Sidoförklaring: Nätlistan är beskrivningen över alla grindar och ledningar som kopplar ihop grindarna till den önskade kretsen. Andra attacker som presenterats försöker modifiera nätlistan eller i källkoden som genom kompilering (syntes) omvandlas till nätlistan. Nätlistan omvandlas genom flera steg till en uppsättning med polygoner (rektanglar) som tillsammans beskriver var på kretsytan olika ämnen (metall, kiseoxid etc) ska placeras i olika lager. Uppsättningen kallas maskset. Ett steg som beskrivs är var på den renda kiselytan joner ska injekteras i ytan för att göra delen av kretsytan potentiellt negativ eller positiv. Denna tidiga process kallas dopning.

Fysiker som bygger säkerhet kontra Intels Bull mountain

För några veckor sedan presenterade några fysiker en ny slumptalsgenerator baserad på kvantfenomen. Resultaten har fått viss uppmärksamhet.

Insamlingsutrustningen som används för att fånga kvantfenomenen.
Insamlingsutrustningen som används för att fånga kvantfenomenen.

Det är alltid spännande med nya forskningsresultat som ger oss insikt i hur vår verklighet fungerar. Jag gillar också att man försöker omvandla sina forskningsresultat till något som går att använda. Tyvärr kan jag utifrån ett säkerhetsperspektiv inte bli speciellt intresserad och imponerad. Skälet till detta är att jag återigen upplever att fysikerna tyvärr är blinda för det område de försöker applicera sina resultat. Det är inte första gången fysiker presenterar nya rön som man ser kan användas för krypto, säker kommunikation, eller som slumptalsgeneratorer. Det är i och för sig intressant och bra. Men problemet är att man ofta tror sig löst ett problem som inte längre är ett problem.

När det kommer till krypton och slumptalsgeneratorer har vi i dag lösningar som ger bra mycket skydd och hög prestanda/kapacitet till realistiska kostnader för väsentligen alla problem och användningsfall. Problemen är istället oftast att få till praktiskt fungerande implementationer, få till säker användning, hantera alla buggar, sidoattacker (inklusive social ingejörskonst) och rena misstag. Och för dessa enkla men viktiga problem är sällan rätt svar kvantfenomen som kräver masrar kylda med flytande väte för att fungera.

Tyvärr har fysikerna bakom den nya slumptalsgeneratorn dessutom fel i sak, vilket visar att dom inte kan applikationsomrepdet. Dom säger:

To date, most random number generators are based on computer algorithms. Although computer generated random numbers can be useful, knowing the input conditions to the algorithm will lead to predictable and reproducible output, thus making the numbers not truly random. To overcome this issue, random number generators relying on inherently random physical processes, such as radioactive decay and chaotic behaviour in circuits, have been developed.”

Detta är inte korrekt. Moderna slumptalsgeneratorer i operativsystem bygger inte på algoritmer som är deterministiska. Mer exakt – dom bygger inte bara på deterministiska algoritmer. Algoritm och fysiska slumpmässiga källor är inte ömsesidigt uteslutande. En modern slumptalsgenerator, som finns i alla operativsystem består grovt sett av två delar.

Den första delen är en eller flera entropikällor. Från entropikällorna samlas värden från slumpmässiga, fysiska händelser in. Exempel på entropikällor som används är tid mellan tangentbordstryckningar, skillnad i läshastighet från en hårddisk, digitala ringoscillatorer i chip eller termiskt brus i radiomottagare. Bra entropikällor ger många händelser/tidsenhet och är dessutom svåra eller helst omöjliga att manipulera. Kombinationen hög prestanda och tålig mot påverkan är svår att få till. Därför används ofta mer än en entropikälla och källorna övervakas för att detektera fel.

Den andra delen består ofta av en deterministisk algoritm – en psedudoslumpgenerator (PRNG). Oftast skapas PRNG:n genom att använda kryptografiska hashfunktioner som SHA-256, strömkrypton som RC4 eller Snow, eller blockkrypton som AES i en strömkryptomod som CTR. Den insamlade entropin anvönds för att initiera PRNGn. Efter att PRNG:n genererat ett visst antal värden startas PRNG:n om med nya värden från entropikällan. Ibland sker även en viss filtrering (whitening) mellan entropikällan och PRNG:n, detta för att ta bort värdemässiga vridningar (bias) så att de möjliga initieringsvärdena (ofta kallade frön) är så likafördelade som möjligt.

Kombinationen av flera entropikällor från vilka värden samlas in, och en bra, säker PRNG ger slumptalsgeneratorer som är tåliga mot störningar och med kapacitet att generera stora mängder slumptal med bra kvalitet. Ett bra exempel på detta är Intels nya slumptalsgenerator Bull Mountain som finns i Ivy Bridge-processorerna som släpptes igår 2012-04-23.

Bull Mountain har en entropikälla kapabel att generera flera Gbit/s i rådata. Rådatat filtreras med AES i CBC-mod. Värdena ut från filtreringen används sedan för att initiera en PRNG byggd med AES-CTR. Bull Mountain ger bättre prestanda än fysikernas generator, är kostnadseffektiv (i jämförelse med fysikernas lösning), drar lite ström, finns direkt tillgänglig för applikationer genom RdRand-instruktionen och kommer att finnas i miljontals med datorer, laptops och prylar inom ett par år.

Ivy Bridge-core
Intels Ivy Bridge-processor. De fyra processorkärnorna delar på en Bull Mountain-generator.

Ett annat bra exempel är slumptalsgeneratorn i Yubicos YubiHSM som har två olika entropikällor vilka matar en PRNG byggd med AES. Allt förpackat i en billig och enkel USB-sticka, vilket gör den lätt att integrera.

YubiHSM intui en server.
YubiHSM monterad i en server.

Intels Bull Mountain/RdRand och YubiHSM tycker jag är mycket, mycket mer spännande och viktigare ur ett användbart säkerhetsperspektiv än fysikernas labbutrustning.


Entropikällan i den nya generatorn.

(Fysikerna säger att den nya källan inte går att manipulera. Men jag fungerar på hur svårt det är att störa källan, ex med en annan laser. Även om kvantfenomenet i sig inte går att manipulera är sensorn ofta det som attackeras.)

Och till sist kan jag inte låta bli att sucka lite över hur fysikerna försöker få ut sin nya fina slumptalsgenerartor. Ja, det är jättefint att det finns ett JSON API (Github-projekt som pratar med generartorn), eller att jag kan gå och få några byte data genererat på webbsidan (som är seg). Men det finns ingen som helst säkerhet kopplad till API:t eller webbsidan.

Själva poängen med en bra slumptalsgenerator är ju att du ska kunna lita på den. Om generatorn sitter inuti min processor är det lättare att lita på den än om den befinner sig i Australien och att datat skickas utan något som helst skydd mot manipulation, äkthetskontroll eller avlyssning.

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.