RC4 (encryptie)

encryptie

RC4 is een algoritme voor stroomvercijferings op basis van symmetrische cryptografie. Het wordt veelvuldig in toepassingen gebruikt, waaronder het Secure Sockets Layer-protocol en het WEP-protocol voor draadloze beveiliging. Het algoritme zelf is eenvoudig en kan op vrijwel alle computers efficiënt worden geïmplementeerd. Hoewel RC erom bekendstaat dat het eenvoudig en snel is, heeft RC4 zwakheden. Het is bijzonder kwetsbaar wanneer bij het begin van de uitvoer, de sleutelstroom niet verwijderd wordt of wanneer niet willekeurige of gerelateerde sleutels worden gebruikt. Sommige implementaties van RC4 kunnen leiden tot een onveilig cryptisch systeem, zoals WEP.

RC4
Algemeen
Ontwerpers Ron Rivest voor 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

GeschiedenisBewerken

RC4 is ontworpen door Ron 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 naar de Cypherpunks-mailinglist werd gemaild. Snel daarna was deze beschrijving ook in de nieuwsgroep van sci.crypt en op veel internetsites te vinden. De gelekte code werd bevestigd als correct omdat de uitkomst gelijk was aan de uitkomst van software voor RC4 met een licentie. 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.

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

WerkingBewerken

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. Ontsleutelen 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 wordt 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 KSABewerken

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 gelijkstaat aan een sleutellengte van 40 - 128 bits. Eerst wordt de array S geïnitialiseerd naar de identieke afbeelding. 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 PRGABewerken

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-XOR'd wordt met de volgende byte van het bericht om de volgende byte te produceren van of de cijfertekst of de platte tekst. Ieder element van S wordt ten minste 1 keer per 256 iteraties met een ander element omgewisseld.

 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

VeiligheidBewerken

Indien correct gebruikt, biedt RC4 een sterke versleuteling die, voor zover bekend, in de praktijk niet kan worden gekraakt. 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. Volgens Jacob Appelbaum, die inzage heeft gehad in de documenten van Edward Snowden, kan de NSA de versleuteling binnen een seconde, 'in real time', kraken.[1][2]

Het is niet mogelijk om verschillende berichten met dezelfde sleutel te vercijferen. De XOR-relatie zou in dat geval 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 worden geproduceerd. Om deze reden wordt geadviseerd om de eerste 256 tot zelfs 1536[3] geproduceerde bytes weg te gooien, en pas daarna te beginnen met vercijferen.

Er is in februari 2015 een RfC[4] aangevraagd om RC4 te verbieden in SSL-encryptie. In Chrome, de browser van Google, wordt vanaf versie 48 websites die SSL met RC4-versleuteling aanbieden geblokkeerd en andere browsers zullen snel volgen.[5]