Etikettarkiv: rc4

Svaga nycklar i strömkryptot RC4

I dag har organisationen IACR, International Association for Cryptologic Research accepterat en artikel av Secworks Joachim Strömbergson samt Simon Josefsson som beskriver en typ av svaga nycklar i strömkryptot RC4.

I artikeln The Perils of Repeating Patterns: Observation of Some Weak Keys in RC4 beskriver vi hur nycklar bestående av ett mönster repeterat två eller flera gånger kan ersättas med en nyckel lika lång som mönstret självt. Följande figur illustrerar vad vi menar:

Olika nycklar i RC4 som genererar samma sekvens
Två olika par med nycklar där nycklarna i varje par får RC4 att generera samma sekvens.

Notera att för de två paren är skillnaden mellan nycklarna att dom är olika långa samt består av olika antal iterationer av samma mönster. I det övre nyckelparet är mönstret 0X55 och i det nedre nyckelparet är mönstret 0X01020304.

Så hur kan det bli så här? Den sekvens RC4 genererar styrs av hur den interna tillståndstabellen S initieras. Detta sker med funktionen KSA (Key Scheduling Algorithm):

RC4:as nyckelberoende initiering.
Den nyckelberoende initieringen i RC4.

Först fylls S med mönstret [0, 1, .. , 255]. Sedan kastas värdena i S om genom att under ett svep över S byta värden på två positioner i taget. Vilka positioner som används är alltid positionerna [0, 1, 2, … 255] (som anges av i) samt positioner som anges av j, vilket beror av nyckeln K. Detta sker på kodrad (5).

Nyckeln består av ett antal bytes och dessa bytes används i tur och ordning för att ge ett positivt bidrag till j. Och när alla bytes i K använts börjar man använda första byten i nyckeln igen tills dess att svepet över S är färdigt.

Boven i dramat är att värdena i nyckeln används på detta cykliska sätt utan att nyckelns längd får vara med och påverka pekaren j. En nyckel som består av två mönster [PP] appliceras på S ger samma bidrag till j som en hälften så lång nyckel som bara består av mönstret [P].

Vi tror inte att vi är dom första som observerat beteendet, det är alldeles för enkelt och dessutom är konstruktionen med att cirkulärt applicera ett mönster relativt vanligt. Det är därför en aning märkligt att vi inte lyckas hitta en beskrivning av beteendet kopplat till RC4. Vi har verkligen försökt så gått vi kan läsa igenom allt om RC4 och nycklar vi kunnat hitta, och det finns rätt många. RC4 är tyvärr ett krypto där det finns många svagheter. Vi har även kontaktat forskare som publicerat några av dessa svagheter men dessa har inte heller känt till beteendet vi beskriver.

Det finns dock en beskrivning av beteendet av Bruce Schneier i sin artikel som introducerar blockkryptot Blowfish. Schneier skriver om hur nyckeln används för att initera Blowfish:

Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

Vi tycker dock att det är omvänt sätt att beskriva det hela. Problemet är inte att för en given nyckel N finns det längre nycklar n*N där n är ett heltal [2, 3, ..]. Nej problemet är att för en nyckel som består av ett mönster N repeterat x gånger finns det ett antal kortare och därmed svagare nycklar.

I exempelvis SSL/TLS genereras nyckeln av en internfunktion med bra kvalitet och sannolikheten att en nyckel som består av ett repeterat mönster används är därför liten. Även i andra tillämpningar där användaren anger nyckel sker ofta en processning av nyckeln genom att köra nyckeln i en kryptografisk hashfunktion (helst många gånger) eller genom ett systen som PBKDF2, bcrypt (som använder Blowfish internt) eller scrypt.

Men jag har tyvärr sett tillämpningar där RC4 används och nyckeln appliceras direkt. Tillämpningar där nyckeln varit av typen 0X0101010101010101 eller 0X0102030405060701020304050607. För dessa är nyckeln inte 64 eller 128 bitar utan 8 respektive 64 bitar.

Vi räknar med att höra av forskare och andra kunniga människor som pekar ut var beteendet och problemet finns beskrivet. Men om det inte sker hoppas vi att den här artikeln hjälper till att sprida kunskapen om beteendet. Vill du undvika de problem vi observerat när du använder kryptp RC4 bör du helt enkelt inte använda nycklar som består av ett repeterat mönster.

Har du synpunkter och information om artkeln får du mer än gärna höra av dig till mig och Simon.

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.

RFC 6229 – Test Vectors for the Stream Cipher RC4

Nu finns RFC 6229 – Test Vectors for the Stream Cipher RC4 publicerad hos Internet Engineering Task Force (IETF).

Detta dokument, skrivet av mig och Simon Josefsson är avsett att underlätta implementationer av strömkryptot RC4 genom att tillhandahålla testvektorer, något som tyvärr saknats. Inte minst viktigt är detta för varianter av RC4 där ett antal av de första nyckelströmsvärden genererade av RC4 förkastas, detta för att förbättra säkerheten. Exempel på denna typ av RC4-varianter är arcfour128 och arcfour256 specificerade i RFC 4345. De testvektorer som finns i vår RFC täcker bland annat in just dessa varianter.

RC4 är ett på många sätt trasigt och svagt krypto och ska inte användas. Tyvärr är ofta verkligheten inte så enkel att det går att helt undvika RC4, detta då algoritmen är väldigt spridd och används i SSL/TLS, WLAN och en oherrans massa applikationer och applikationsspecifika protokoll. Vi ser därför att RFC 6229 bör underlätta vid implementationer och bidra till att bättre varianter som arcfour128 och arcfour256 används där byte till helt andra agoritmer inte fungerar.

Att implementera krypton är intressant och skiljer sig från många andra algoritmer på så sätt att det inte finns något som kan kallas funktionellt nästan korrekt. Antingen är implementationen korrekt eller så är resultatet helfel, bokstavligt talat inte en siffra rätt. Att debugga kryptoimplementationer är därför inte lätt. Tillgång till facit – i form av testvektorer (kallas också Known Answer Test – KAT) och gärna även interntillstånd underlättar betydligt.

Ny version av draft med testvektorer för RC4

Jag och Simon Josefsson har arbetat ett tag med ett utkast till RFC-dokument för IETF med testvektorer för strömkryptot RC4. Efter att ha legat på is ett tag postade vi precis en ny version av utkastet. draft-josefsson-rc4-test-vectors-02 finns nu hos IETF.

Detta är förhoppningsvis den sista versionen av utkastet innan det blir en officiell RFC. Jag och Simon skulle därför uppskatta alla kommentarer och synpunkter på utkastet.

Uppdatering 2011-07-01: Draften har nu omvandlats till RFC 6229.