Print 
PDFI 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:
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):
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.
Senaste kommentarer