(Mycket PRNG-prylar just nu…)

Den senaste tiden har det dykt upp flera nyheter om slumptalsgeneratorer. Mer specifikt brister i slumptalsgeneratorerna i olika operativsystem. De händelser detta handlar om utspelade sig för några veckor sedan och kan därför tyckas vara gamla. Men jag tycker att det är så intressant, inte minst utifrån hur problem hanteras att jag vill ta upp det ändå.

Först ett klargörande: Det handlar alltså om pseudoslumpgeneratorer (PRNG), dvs algoritmer som körs på vanliga datorer och som (när de fungerar korrekt) genererar en sekvens av värden.

Den genererade sekvensen av värden uppvisar ett slumpmässigt beteende, vilket kan testas, exempelvis med Marsaglias Diehard-test. En viktig egenskap (om man vill använda generatorerna för IT-säkerhet) är att en yttre observatör genom att studera N föregående värden inte skall kunna gissa kommande värden eller fler äldre värden.

Normalt sett implementeras dessa algoritmer med någon slags rent deterministisk tillståndsmaskin där startpunkten och sekvensen som genereras beror av ett startvärde (frö). Fröt skapas sedan genom att samla in vad som förmodas är äkta slump (fysisk entropi) från datorn och dess omgivningar.

Som källor för entropin används exempelvis positionen på hårddiskens huvud, tiden mellan tangentbordstryckningar, infångat brus från mikrofoner, temperaturen i processorn, hastigheten på fläkten, signaler på nätverksportar etc.

Så långt teorin, men i verkligheten visar det sig vara svårt både att designa och implementera dessa generatorer. Felaktigheter i slumptalsgeneratorn kan leda till problem som att den genererade sekvensen avviker från förväntad fördelning, att sekvensen går att prediktera eller att fröt går att extrahera genom att observera sekvensen.

Nåväl, tillbaka till berättelsen. Allt startade med artikeln Cryptanalysis of the Random Number Generator of the Windows Operating System av Leo Dorrendorf, Zvi Gutterman och Benny Pinkas med analys av slumptalsgeneratorn i Windows. Den (av mig nedkortade) sammanfattningen av artikeln lyder:

Abstract: The pseudo-random number generator (PRNG) used by the Windows operating system is the most commonly used PRNG. The pseudo-randomness of the output of this generator is crucial for the security of almost any application running in Windows. Nevertheless, its exact algorithm was never published.
...
We examined the binary code of a distribution of Windows 2000, which is still the second most popular operating system after Windows XP…. We analyzed the security of the algorithm and found a non-trivial attack: given the internal state of the generator, the previous state can be computed in $O(2^{23})$ work (this is an attack on the forward-security of the generator, an $O(1)$ attack on backward security is trivial). The attack on forward-security demonstrates that the design of the generator is flawed, since it is well known how to prevent such attacks.
...
The implication of these findings is that a buffer overflow attack or a similar attack can be used to learn a single state of the generator, which can then be used to predict all random values, such as SSL keys, used by a process in all its past and future operation. This attack is more severe and more efficient than known attacks, in which an attacker can only learn SSL keys if it is controlling the attacked machine at the time the keys are used.

Artikeln uppmärksammades på Slashdot och därmed var lavinen i gång med en massa turbulens, hetluft och spekulationer.

Plötsligt dök det upp problem även i andra slumptalsgeneratorer. Först ut var Linux där SecurityFocus rapporterade om Linux Kernel Random Number Generator Local Denial of Service and Privilege Escalation Vulnerability. Problemet fick stor uppmärksamhet och speciellt följande stycke hittar man på massor med webbplatser där de flesta hänvisar till en sida hos Neowin.net från vilken stycket ser ut att komma:

According to security researchers, the Linux kernel is prone to a local vulnerability that may result in a DoS or privilege escalation, possibly allowing the attackers to run arbitrary code on the target system. This issue stems from a stack-based overflow in kernel memory; if uccessfully exploited this issue allows local attackers to trigger kernel crashes and, in certain circumstances, also allows them to gain elevated privileges. However, the attacker may require partial administrative access via granular assignments of superuser privileges. Linux kernel versions prior to 2.6.22.3 are affected by this issue.

Försöker man hitta källan till problemet hamnar man på en commitlog för Linux. I den hittar man i sin tur CVE-2007-3105 som innehåller länkar och referenser till PaX-teamet, som verkar vara de säkerhetsforskare man refererar till.

Värt att notera är att Zvi Gutterman och Benny Pinkas dvs författarna till artikeln om analys av generatorn i Window tillsammans med Tzachy Reinman år 2006 publicerade en artikel med analys av generatorn i Linux.

Nästa generator på slaktbänken var FreeBSDs implementation av slumptalsgeneratorn Yarrow, som även den visade sig innehålla ett fel.

Att det visar sig finnas fel i slumptalsgeneratorer och vilka problem det kan leda till är intressant. Och än mer intressant, på vilka sätt felen och de uppkomna problemen hanteras. Det är på detta vi den senaste tiden fått många exempel på hur olika man kan agera.

Reaktionen från Microsoft dröjde några dagar (vilket är ok) och det första svaret från Microsoft var att problemet bara gällde Windows 2000, inte XP eller Vista. Detta uttalande fick man senare ändra på:

As recently as last Friday, Microsoft hedged in answering questions about whether XP and Vista could be attacked in the same way, saying only that later versions of Windows “contain various changes and enhancements to the random number generator.” Yesterday, however, Microsoft responded to further questions and acknowledged that Windows XP is vulnerable

(Min förstärkning av contain various changes and enhancements to the random number generator.)

Symantec hoppade in i leken och enligt Computerworld hävdade Symantec problemet inte var en sårbarhet utan ett designfel:

Symantec Corp., which posted its own analysis last week, issued a low-level alert for it today to customers of its DeepSight threat network. Like Microsoft, Symantec didn’t classify the threat as a security vulnerability, but instead called it a design error.

Microsoft’s recognized this as a local information disclosure issue, and Symantec agrees,” Wayne Periman, director of development for Symantec’s security response, said on Monday. “The reason for the low rating is that in order to exploit this, there has to be a complex attack organized.

(Återigen min förstärkning.)

Microsofts sätt att hantera situationen går att jämföra med hur FreeBSD agerade. I FreeBSDs fall leder felet till ett säkerhetsproblem, ett problem som noga beskrivs i den säkerhetsrapport (Security Advisory – SA) FreeBSD publicerade.

I. Background
The random(4) and urandom(4) devices return an endless supply of pseudo-random bytes when read. Cryptographic algorithms often dependon the secrecy of these pseudo-random values for security.

II. Problem Description
Under certain circumstances, a bug in the internal state tracking on the random(4) and urandom(4) devices can be exploited to allow replaying of data distributed during subsequent reads.

III. Impact
This could enable an adversary to determine fragments of random values previously read, allowing them to defeat certain security mechanisms. Note that the attacker has to be in close proximity to the source of the pseudo-randomness, which typically means local access to the system.

Jag har svårt att köpa Microsofts (och Symantecs) förklaring att det är ett designfel, inte ett säkerhetsproblem. Som jag ser det står inte designfel i motsatsförhållande till säkerhetsproblem, utan det är frågan om orsak och potentiell verkan. Designfel är en (av flera möjliga) orsak till att olika problem uppstår. Säkerhetsproblem är en typ av problem som kan uppstå.

Vidare blir jag rädd när man tonar ned just designfel. I min värld är designfel oftast mycket värre än ett implementationsfel. Implementationsfel kan vara ett skrivfel eller en miss – men ett designfel handlar om feltänk. Typiska designfel är protokoll som visar sig inte fungera – och att byta ut protokoll är ingen enkel sak. Som en god vän brukar uttrycka det: Trasigt.

Tittar man i den officiella källkodspatchen för felet i FreeBSD ser man att programmeringsfelet är en enradare:

--- sys/dev/random/yarrow.c27 May 2007 18:54:58 -00001.47
+++ sys/dev/random/yarrow.c27 Nov 2007 17:17:29 -0000
@@ -296,6 +296,7 @@

random_state.outputblocks = 0; } retval += (int)tomove;
+cur = 0; } } else {


Dvs en räknare (cur) nollställdes inte på ett korrekt sätt i ett IF-fall. Känns som ett typiskt implementationsfel.

En annan sak som skiljer mellan de senaste tidens fel i PRNG:s är hur man publicerar åtgärderna. FreeBSD och Linux publicerar patchar, och som de öppen/fri-kod-projekt de är finns naturligtvis hela koden på nätet. Vill man kan man exempelvis titta på hela koden för implementationen av Yarrow i FreeBSD.

Microsoft å sin sida hävdar alltså att man utfört various changes and enhancements to the random number generator. Denna formulering ger inte mig en speciellt stark känsla av förtroende, inte minst då man först hävdar att Windows XP inte är sårbar, och sedan kommer fram till att det är den i alla fall. Har man inte koll på vilka various changes and enhancements man petat in i vilket OS?

Beroende på hur problemen i slumptalsgeneratorn yttrar sig och hur access till generatorn eller den sekvens den genererar går det i vissa fall att attackera ett system. Ett klassiskt exempel på en attack mot en slumptalsgenerator var den attack som Ian Goldberg och David Wagner utförde mot en tidig version av SSL i webbläsaren Netscape.

I fallet med Linux och FreeBSD konstaterar projekten alltså att de problem som kan uppstå öppnar upp för olika typer av attacker. I Microsofts fall säger alltså Symantec att attacken skulle vara så komplex att dom bedömer att det inte är något hot, och som tredje, rätt kompetent part bör vi kanske lita på Symantec.

Den sista aspekten på skillnaderna mellan hur de olika OS:en agerar vad gäller sina PRNG:s är information om vilken algoritm de använder. FreeBSD och Linux är som sagt öppen/fri-kod. Men tittar man på OpenSolaris från Sun eller Apple så hittar man även här information och källkod för PRNG-funktionerna.

MacOS X Leopard/Darwin 10.5 använder precis som FreeBSD en implementation av Yarrow. motsvarande kod hittar man i darwinsource/10.5/xnu-1228/bsd/dev/random. Jag är inte helt säker på att jag hittar motsvarande ställe i källkoden som i FreeBSD, men jag ser inte samma problem som i FreeBSD – uppenbarligen är det en helt separat implementation av Yarrow, vilket innebär att dom skulle kunna designfel, men antagligen inte implementationsfel. Det viktiga är dock att jag kan gå in och titta på koden, och tom kompilera och testa.

Vi vet inte (iaf lyckas inte jag hitta någon information om) vilka generatorer som Microsoft använder i sina OS. Vad bygger den på för principer? Vilka designval har man gjort? Hur har man testat implementationerna? Och (återigen) vad innebär various changes and enhancements.

Speciellt intressant i fallet Microsoft är att Niels Ferguson, en av skaparna av Yarrow/Fortuna faktiskt jobbar på Micrsosoft. Har han varit med och byggt om PRNG:n? Varför berättar man inte det? Det skulle iaf få lite cred hos mig (om det nu är värt något.)

Microsoft kör inte med egna krypton, ex en icke-kompatibel version av AES. Däremot har man stukat till Kerberos, hittat på egna autenticieringsmekanismer (NTLM) och ibland samarbetat med andra för utveckling av tunnelprotokoll (PPTP). Varför och i vilka tillfällen Microsoft bestämmer sig för att utveckla eget är för mig en gåta. Vad vinner man på att hacka sin egen PRNG?

Kontentan av allt det här är som jag ser det att:

1. Bygga PRNG:s – både design och implementation är svårt, så varför hacka en egen?


2. Det skiljer fundamentalt i hur man agerar när det dyker upp ett fel


3. Det är skillnad på fel och problem

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

• Previous Entry: Test av Yubicos kodgenerator
• Next Entry: Google TechTalk om krypto