Lita inte på slumpen - så fungerar slumpgeneratorer

Vi har i ett antal artiklar tittat närmare på olika krypton. Nu har det blivit dags att gå ännu djupare i ämnet och undersöka slumptal och hur dessa genereras.

Slumptal används i många olika typer av applikationer, inte bara för att skapa kryptonycklar. En vanlig tillämpning är spel, där man vill ta till slumpen för att göra spelet mer omväxlande. Slumptal används även vid simuleringar för att pröva olika scenarion och vilka resultat de ger.

Finns i många os
Ett program kan innehålla en egen slumptalsgenerator, men tillgång till slumptal är ett så vanligt behov att även de flesta operativsystem innehåller någon slags slumptalsgenerator som applikationerna kan använda. Exempel på det här är lagring av lösenord, där slumptal används för att försvåra attacker, eller identitetsnummer för processer och sekvensnummer för tcp-sessioner.

Men vad är ett slumptal? Är talet tre ett slumptal? Eller 42? Det beror inte på talet i sig, utan snarare på varifrån talet kommer, och om talets värde var givet på förhand eller ej.

Ett slumptal är helt enkelt ett tal som plockats från en hög av tal. Det är avsaknaden av kännedom om innehållet i högen samt att inte på förhand veta vilka tal som kommer ut ur högen som gör talen som kommer från högen slumpmässiga. Att inte på förhand kunna gissa värdet på ett tal gäller oavsett om den som försöker gissa värdet sett alla föregående värden eller ej. Ju svårare det är att gissa värdena i en sekvens av tal desto mer slumpmässiga är talen.

Ett problem med att generera slumptal med ett program är att slumpmässighet strider mot essensen hos en dator, alltså att alltid köra ett program på samma sätt. Ett program som beräknar summan av två tal ska om talens värden aldrig ändras alltid ge samma svar.

Pythonkod med en enkel prng av linjär kongurent-typ som är rätt vanlig. Generatorn ger tyvärr inte en tillräckligt bra sekvens för att användas i säkerhetsapplikationer.

Från frö till slump
Trots det finns det program som givet ett startvärde genererar en sekvens av tal som ser ut att vara slumpmässiga. Startvärdet kallas frö och programtypen kallas pseudoslumpgenerator, prng (pseudo random number generator). Koden på bilden till vänster är ett exempel på en enkel prng.

Fördelen med en prng är att det går att upprepa den sekvens som generatorn skapar givet ett specifikt frö – om samma frö används flera gånger genereras alltid samma sekvens. För simuleringar och faktiskt även för kryptering är denna egenskap viktig.

Strömkrypton, till exempel rc4, är prng-program och kryptonyckeln är programmets frö. Ett meddelande krypteras genom att kombinera meddelandets innehåll med den sekvens av tal som rc4 genererar. Vid dekryptering återskapar mottagaren talsekvensen genom att starta rc4 med samma nyckel.

En annan typ av slumptalsgenerator är så kallade äkta slumptalsgenerator, trng (true random number generator), även kallat bara rng (random number generator). De drivs av händelser insamlade från en slumpmässig fysikalisk process, så kallade entropikällor.

Vi provkör vår Pythonbaserade slumptalsgenerator med två olika frön. Notera att generatorn med de olika fröna ger helt olika sekvenser av värden.

Vad är en bra källa?
Klassiska exempel på entropikällor är kosmisk bakgrundsstrålning och radioaktivt sönderfall. En mer udda generator är lavageneratorn, i vilken en kamera filmar en lavalampas slumpmässiga mönster och filmen sedan omvandlas till slumptal.

En bra entropikälla ska inte gå att förutsäga, och den får inte heller gå att påverka. Tyvärr har många bra källor relativt låg kapacitet med få händelser per tidsenhet. En entropikälla som inte går att manipulera och har hög kapacitet har visat sig svår att hitta.

Kosmisk strålning är en mycket bra entropikälla, alltså partiklar och elektromagnetisk strålning som träffar jorden från rymden. De har en hög grad av slumpmässighet och är svåra att manipulera. Men i vanliga datorer finns tyvärr sällan detektorer för kosmiskt strålning, så vad ska du då använda? Exempel på vanliga entropikällor i datorer är tangenbordstryckningar, musrörelser, läsningar från hårddisken eller klockan i datorn. Dokumentet RFC 4086 från IEFT ger en bra beskrivning av hur du ska gå till väga för att samla in entropi och generera slumptal i en dator. Dokumentet säger dock inget om hur du kontrollerar att din entropikälla faktiskt fungerar.

Så här är en modern rng uppbyggd, med entropikällor, insamling och prng.


Äkta slump
Moderna generatorer av den typ som finns i de flesta operativsystem ser till att skapa äkta slump med hög kapacitet genom att kombinera entropikällor med en prng.

Slumpmässiga händelser samlas in av en entropipool och från den skapas sedan periodiskt frön som används för att generera sekvenser av tal med en prng. Det är dessa sekvenser som används av operativsystemet och applikationer. Ofta sker även någon slags tvättning av fröna för att se till att de är så slumpmässiga som möjligt.

En metod för att tvätta värden skapad av John von Neumann är att titta på den genererade bitströmmen två bitar i taget. Om bitarna har samma värden kastas bitarna bort och nästa par av bitar i bitströmmen bearbetas. Om värdet på bitparet är 01 ersätts det av en nolla. Om värdet på bitparet är 10 ersätts det av en etta. Genom detta förfarande elimineras sekvenser av likadana bitar, men kostnaden för tvätten är att mer än hälften av bitströmmen försvinner.

Det kan även finnas funktionalitet som tittar på fröna för att bedöma om entropikällorna fungerar.

Det finns verktyg för att undersöka om en rng genererar bra slumptal genom att ta in en ordentlig mängd tal från generatorn och utsätta varje tal för ett antal test som på olika sätt letar efter mönster.
Men notera att en enda godkänd undersökning inte bevisar att generatorn fungerar, bara att testen inte hittar några mönster. Det behövs flera test, och ju fler godkända test, desto troligare är det att generatorn fungerar. I vår undersökning använder vi testprogrammet Dieharder.

Nu behöver vi hitta några olika generatorer. Ett förslag i dokumentet RFC 406 är att samla in bakgrundsljud med en mikrofon och sedan komprimera data med en filkomprimerare som letar efter mönster i data som förekommer flera gånger och kodar om data så att redundansen kan tas bort. Bra slumptal ska inte innehålla några mönster och därmed gå att komprimera.

De generatorer vi använder i undersökningen är:

• Bakgrundsljud inspelat med mikrofon

• Generatorn från kodexemplet i bilden på sidan 54
• Generatorn i Openssl
• Strömkryptot rc4
• /dev/random i Mac OS X Lion

För att jämföra med saker som inte ska vara slumpmässiga har vi skapat en rampgenerator. Den genererar sekvenser med tal som börjar med ett och ökar sedan med ett hela tiden, ett mycket enkelt och allt annat än slumpmässigt mönster.

Från varje källa har vi genererat data om minst 10 miljoner tal. Vi har testat att komprimera data med filkomprimeraren gzip.
För insamlat ljud och rampsekvensen har gzip inga problem att hitta många mönster. För Openssl, rc4 och Mac OS X lyckas gzip inte hitta några mönster.

Efter komprimeringstestet släppte vi lös testprogrammet Dieharder, och då både på okomprimerade och komprimerade data. I tabellen till höger ser du originalstorlek, storlek efter kompression och antalet klarade tester i Dieharder.

Som väntat visar Dieharder att rampen inte är någon slumpmässig sekvens, inte ens i komprimerat format. Även vår exempelkod visar sig vara riktigt dålig. Det inspelade ljudet i råformat är inte alls speciellt slumpmässigt. Efter komprimering ser det bättre ut, men långt ifrån så bra som rc4, Openssl och Mac OS X, alla
tre generatorer byggda för hög säkerhet.

Dessa tre generatorer ligger alla över 25 klarade tester, vilket indikerar att de är bra generatorer. Intressant nog blev både Openssl och rc4 mycket bättre efter komprimering. Mac OS X med sin Yarrow-generator ger stabil och bra kvalitet.


Som synes ger strömkryptot rc4 samt generatorerna i Mac OS X och Openssl slumptal med hög kvalitet. Vi kan också se att komprimering eliminerar mönster, vilket ökar slumpmässigheten.

Om lampan slocknar
En viktig sak att notera med entropi-källor är att de innebär antaganden om den fysiska miljön. Om dessa antaganden inte gäller fungerar inte entropikällan som det var tänkt – om till exempel lampan i lavalampan skulle slockna stelnar lavan och slut-ar röra sig slumpmässigt.

Nyligen presenterade en grupp forskare vid Princeton University resultatet av en undersökning där man sökt igenom internet efter publika nycklar och jämfört dessa. De upptäckte ett stort antal maskiner med identiska nycklar, till exempel routrar av en viss modell för konsumentbruk där drygt 9 000 av 27 000 enheter hade genererat samma nyckel. Problemet i det fallet är troligen när maskinerna generera sina nycklar när de konfigureras för första gången. I det läget har maskinerna inte mycket entropi, så samma nycklar genereras.

Den kan även vara fel på den prng som används. 2008 upptäcktes det att en städning i den version av Openssl som paketerades in i Debian Linux innebar att en kodrad för initieringen av generatorn i Openssl hade försvunnit. Det här resulterade i att det frö som användes för att initiera prng:n bara kunde vara ett av 32 768 olika värden.

Det finns i dag en stark trend mot virtualisering och att köra flera datorer på samma fysiska maskin. För de virtualiserade maskinerna kan det innebära att de antaganden deras entropikällor baseras på påverkas. Många virtuella maskiner har låg lokal interaktivitet med musrörelser och tryck på tangentbord. Även hårddiskar kan vara ersatta med filer inlästa i den fysiska maskinens minne. Och även om de virtualiserade datorerna får tillgång till värdsystemets rng kan denna rng bli utarmad – den att den töms på sitt förråd av värden fortare än den är den är kapabel att fylla förrådet. Då fastnar den virtualiserade datorn i väntan på nya slumptal.

Ett sätt att lösa det här problemet är att lägga till en generator som fyller på de generatorer som används. I Linux, Mac OS X och andra Unix-baserade system går det att tillföra entropi genom att skriva till /dev/random. Den påfyllningen kan ske i såväl den virtualiserade datorn som i värdsystemet. Generatorn Havege eller fysiska produkter som YubiHSM från Yubico samt SG100 från Protego går att använda för att tillföra entropi.

Entropikällan i Intels nya processorarkitektur Ivy Bridge har två transistorer och två motkopplade inverterare.


Ingen entropi med flash
En annan trend är att ersätta mekaniska hårddiskar med minneskretsar, till exempel flashbaserad ssd. Plötsligt försvinner då de motorer och rörliga delar som bidrog till den variation i lästid som flera operativsystem använder som entropikälla.

För att minimera externa beroenden vore det bästa om entropikällan fanns i själva processorn. Det finns faktiskt flera processorer med inbyggd rng, exempelvis flera av Vias x86-processorer. Även Intel har haft rng i sina processorer, men det har hittills inneburit problem – generatorer i processorer har dragit mycket ström, har kunnat påverkas utifrån samt varit känsliga för temperatur och hur själva chipet tillverkats.

Men i Intels nya processorarkitektur Ivy Bridge kommer en ny rng kallad Bull Mountain som ser ut att lösa problemen. Den inkluderar både en ny entropikälla och en prng baserad på blockkryptot aes.

Styrs av processorklockan
Den nya entropikällan är en rent digital konstruktion och består av två sammankopplade inverterare samt två transistorer styrda av processorns klocka. När klocksignalen är noll kopplas båda inverterarna till kretsens strömmatning, vilket tvingar värdet på ingången till båda inverterarna att vara ett.

Men när klocksignalen blir ett börjar inverterarna att kämpa om att hitta ett stabilt läge där den ena inverteraren ger en nolla och den andra en etta. Vilket läge som uppstår beror på det termiska brus som finns i kretsen, ett slumpmässigt fysikaliskt fenomen som är svårt att manipulera.

Eftersom entropikällan styrs av processorns klocka kommer entropikällan att generera bitvärden i takt med klockan. Intel uppger att utdata från entropikällan minst ska klara 3 gigabit per sekund.
De genererade bitarna samlas ihop och används för att driva en hashfunktion kallas cbc-mac, även den byggd med kryptot aes. Resultatet är ett ord på 256 bitar som används för att initiera prng-delen av Bull Mountain.

Enligt Intel ska den nya generatorn kunna generera slumptal med hög kapacitet och hög kvalitet men inte förbruka mycket ström.
Generatorn är en resurs som delas mellan de processorkärnor som finns i processorn, vilket mycket väl skulle kunna innebära att program som körs på en kärna förbrukar de slumptal ett program på en annan kärna behöver. Enligt Intel ska generatorn klara av att skala upp i prestanda och möta prestandakraven från serverapplikationer.

Ett program som vill läsa ut värden från den nya generatorn behöver använda den nya instruktionen rdrand. Vid utläsning av värden från rdrand kommer carry-flaggan cf ange om generatorn kunde leverera ett värde eller ej. Om cf är satt till noll fanns det inga värden tillgängliga.

TechWorlds slutsats
Vår slutsats är att slumptal inte är så enkelt som det kan verka. De flesta operativsystem har i dag bra generatorer, men de generatorerna bygger på antaganden om sin fysiska verklighet. Om de antagandena inte längre gäller kan du behöva stödja generatorn så att den fortsätter fungera.

Om du använder din rng för säkerhetskritiska tillämpningar är det TechWorlds rekommendation att du inte flyger i blindo, utan ser till att göra ett ordentligt test av generatorn i den miljö där du tänker använda den.