RC4 (encryptie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
RC4
Algemeen
Ontwerpers Ron Rivest (RSA Security)
Uitgegeven op Gelekt in 1994 (Ontworpen in 1987)
Details
Sleutel grootte 40-2.048 bits
Staat grootte 2.064 bits
Rondes 256
Snelheid 7 rondes per byte op de originele Pentium

RC4 is een cryptografisch stroomvercijferingsalgoritme op basis van symmetrische cryptografie. Het wordt veelvuldig gebruikt in toepassingen, waaronder het Secure Sockets Layer protocol en het WEP protocol voor draadloze beveiliging. Het algoritme zelf is buitengewoon eenvoudig en kan efficiënt geïmplementeerd worden op vrijwel alle computers. Hoewel RC bekend staat om zijn simpelheid en snelheid in software, heeft RC4 zijn zwakheden. Het is bijzonder kwetsbaar wanneer bij het begin van de output, de sleutelstroom niet verwijderd wordt; of wanneer niet willekeurige of gerelateerde sleutels worden gebruikt. Sommige implementaties van RC4 kunnen leiden tot zeer onveilige cryptische systemen zoals WEP.

Geschiedenis[bewerken]

RC4 is ontworpen door Ronald Rivest van RSA Security in 1987. De afkorting staat voor "Rivest Cipher 4", maar wordt ook vaak gelezen als "Ron's Code". Rivest ontwikkelde ook de blokvercijferingsalgoritmes RC2, RC5 en RC6, waarvan de laatste twee in samenwerking met anderen.

De werking van RC4 werd aanvankelijk geheimgehouden, maar in September 1994 lekte dit geheim uit doordat een beschrijving werd ge-mailed naar de Cypherpunks mailing list. Snel daarna was deze beschrijving ook in de sci.crypt nieuwsgroep te vinden en op vele sites op het internet. De gelekte code werd bevestigd als correct omdat de uitkomst gelijk was aan de uitkomst van gelicenseerde software die een gelicenseerde versie van RC4 gebruikte. Naar de uitgelekte versie van het algoritme wordt soms verwezen onder de naam ARCFOUR (voor alleged-RC4), enerzijds omdat RSA Security nooit heeft bevestigd dat het een correcte beschrijving van het algoritme betreft, anderzijds om juridische problemen te voorkomen. Omdat het algoritme bekend is, is het niet langer een merknaam.

In 2001 ontdekten Fluhrer, Mantin en Shamir een zwak punt in de wijze waarop RC4 gebruik maakt van sleutels. Indien een reeks berichten is vercijferd met sleutels die onderling weinig verschillen, kan de gehele sleutel achterhaald worden door analyse van een groot aantal berichten. Met deze benadering kan de WEP encryptie voor draadloze verbindingen in de praktijk eenvoudig gekraakt worden.

Werking[bewerken]

De kern van RC4 wordt gevormd door een cryptografische toevalsgenerator die een eindeloze rij bytes produceert. Deze bytes worden door middel van een XOR bewerking gecombineerd met de bytes van de klare tekst, resulterend in de cijfertekst. Ontcijferen bestaat uit precies dezelfde handelingen als vercijferen. Om de sleutelstroom te genereren maakt men gebruik van een geheime interne staat die uit twee delen bestaat:

  1. Een permutatie van alle 256 bytes (in het voorbeeld aangeduid als S)
  2. Twee 8-bit index-pointers (in het voorbeeld aangeduid als i en j)

De permutatie word geïnitialiseerd met een variabele sleutellengte, meestal tussen de 40 en 256 bits, door middel van het key-scheduling algoritme (KSA). Zodra dit voltooid is wordt de stroom van bits gegenereerd door middel van het pseudo-random generation algoritme (PRGA).

Key-scheduling algoritme (KSA)[bewerken]

RC4 werkt met sleutels van ten minste 1 en ten hoogste 256 bytes. De sleutel wordt gebruikt om de generator in een begintoestand te brengen volgens onderstaande pseudocode.

Het key-scheduling algoritme wordt gebruikt om de permutatie in de array S te initialiseren. keylength is gedefinieerd als het aantal bytes in de sleutel die zich in range 1 tot en met 256 bevinden, meestal tussen de 5 en 16 wat gelijk staat aan een sleutellengte van 40 - 128 bits. Eerst wordt de array S geïnitialiseerd naar de identiteits-permutatie. S wordt vervolgens gedurende 256 iteraties geproduceerd.

 for i from 0 to 255
     S[i] := i
 endfor  
 j := 0
 for i from 0 to 255
     j := (j + S[i] + sleutel[i mod sleutellengte]) mod 256
     swap(S[i],S[j])
 endfor

Pseudo-random generation algoritme (PRGA)[bewerken]

RC4.svg

Na het verwerken van de sleutel kan de generator gebruikt worden voor het produceren van bytes. Onderstaande pseudocode produceert één byte. Door de code meerdere malen aan te roepen kunnen zoveel bytes geproduceerd worden als nodig is.

Voor zoveel iteraties als nodig, wijzigt het PRGA de staat en geeft een byte van de sleutelstroom. In elke iteratie verhoogt het PRGA i, haalt het ie element op uit S en voegt dat toe aan j, verwisselt de waarde van i en j, en gebruikt vervolgens de totale waarde van S[i] en S[j] (modulo 256) als een index voor het derde element van S, wat vervolgens ge-XORed wordt met de volgende byte van het bericht om de volgende byte te produceren van of de cijfertekst of de platte tekst. Elk element van S wordt ten minste 1 keer per 256 iteraties omgewisseld met een ander element.

 i := 0
 j := 0
while GenererenOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap(S[i],S[j])
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

Veiligheid[bewerken]

Indien correct gebruikt, biedt RC4 een sterke vercijfering die, voor zover bekend, in de praktijk niet gekraakt kan worden. In de loop van de tijd zijn echter een aantal problemen ontdekt waarmee bij het gebruik van RC4 rekening moet worden gehouden. Veel cryptografen raden het gebruik van RC4 daarom af voor nieuwe applicaties.

Het is niet mogelijk om verschillende berichten te vercijferen met dezelfde sleutel. In dat geval zou de XOR-relatie tussen de klare teksten hetzelfde zijn als de XOR-relatie tussen de cijferteksten, wat het zeer eenvoudig maakt om de cijferteksten te kraken. Dit kan opgelost worden door aan elk bericht een uniek serienummer toe te wijzen, en de sleutel voor dat bericht te berekenen met een cryptografische hashfunctie over de basissleutel en het serienummer.

De verwerking van sleutels is een zwak punt in RC4. Dit is verschillende malen aangetoond, het duidelijkst door de aanval van Fluhrer, Mantin en Shamir. In het bijzonder is het onveilig om de berichtsleutel te vormen door een serienummer achter een basissleutel te plakken (zoals gedaan wordt in het WEP protocol). Sleutels moeten daarom eigenlijk altijd voorbewerkt worden met een cryptografische hashfunctie zodat er in de RC4-sleutel geen systematische patronen kunnen zitten.

De toevalsgenerator van RC4 lekt informatie over de sleutel in de eerste bytes die geproduceerd worden. Om deze reden wordt geadviseerd om de eerste 256 tot zelfs 1536 [1] geproduceerde bytes weg te gooien, en pas daarna te beginnen met vercijferen.