Voir la source de RC4

{{confusion|Route coloniale 4}}
[[Image:RC4.svg|vignette|droite|320px|Schéma d'un tour de RC4]]
'''RC4''' (Rivest Cipher 4) est un algorithme de [[chiffrement en continu]] conçu en 1987 par [[Ronald Rivest]], l'un des inventeurs du [[Rivest Shamir Adleman|RSA]], pour les [[Laboratoires RSA]]. Il est supporté par différentes normes, par exemple dans [[Transport Layer Security|TLS]] (anciennement SSL) ou encore [[Wired Equivalent Privacy|WEP]].

== Histoire ==
RC4 a été conçu par [[Ronald Rivest]] de [[RSA Security]] en [[1987]]. Officiellement nommé ''Rivest Cipher 4'', l'acronyme ''RC'' est aussi surnommé ''Ron's Code'' comme dans le cas de [[RC2]], [[RC5 (chiffrement)|RC5]] et [[RC6]].

Les détails de RC4 furent initialement tenus secrets mais en 1994, une description du chiffrement fut postée de manière anonyme sur la [[liste de diffusion]] ''Cypherpunks'' <ref>{{lien web|url=http://cypherpunks.venona.com/date/1994/09/msg00304.html|titre={{langue|en|Thank you Bob Anderson}}|date=09 09 1994|consulté le=20 10 2015|langue=en}}.</ref>. Le message apparut ensuite sur le [[Groupes de discussion sur la cryptologie|forum sci.crypt]] <ref>{{lien web|url=http://groups.google.com/group/sci.crypt/msg/10a300c9d21afca0|titre={{langue|en|RC4 Algorithm revealed}}|date = 14 09 1994|auteur=David Sterndark|consulté le = 20 10 2015|langue=en}}.</ref> puis sur divers sites. L'algorithme avait vraisemblablement fait l'objet d'une [[rétro-ingénierie]]. Sur le plan légal, RC4 est une [[marque déposée]] dont les implémentations non officielles sont autorisées sous un autre nom que RC4, car l'algorithme n'a pas été breveté. La version non officielle de RC4 est aussi connue sous le nom de « ''ARCFOUR'' », « ''ARC4'' » ou « ''Alleged RC4'' » (signifiant « RC4 supposé » puisque ''RSA Security'' n'a jamais officiellement publié les spécifications de l'algorithme).

Il a par la suite été utilisé dans des protocoles comme [[Wired Equivalent Privacy|WEP]], [[Wi-Fi Protected Access|WPA]] ainsi que [[Transport Layer Security|TLS]]. Les raisons de son succès sont liées à sa grande simplicité et à sa vitesse de chiffrement. Les implémentations matérielles ou logicielles sont faciles à mettre en œuvre.

== Principe général ==
RC4 fonctionne de la façon suivante : la clef RC4 permet d’initialiser un tableau de 256 octets en répétant la clef autant de fois que nécessaire pour remplir le tableau.
Par la suite, des opérations très simples sont effectuées : les octets sont déplacés dans le tableau, des additions sont effectuées, etc. Le but est de mélanger autant que possible le tableau. Finalement on obtient une suite de bits pseudo-aléatoires qui peuvent être utilisés pour chiffrer les données via un [[OU exclusif|XOR]].

== Description détaillée ==
RC4 est un [[générateur de nombres pseudo-aléatoires|générateur de bits pseudo-aléatoires]] dont le résultat est combiné avec le texte en clair via une opération [[OU exclusif|XOR]], le déchiffrement se fait de la même manière (voir [[masque jetable|chiffrement de Vernam]]).

Pour générer le flot de bits, l'algorithme dispose d'un état interne, tenu secret, qui comprend deux parties :

# une permutation <math>S</math> de tous les 256 octets possibles
# deux pointeurs <math>i</math> et <math>j</math> de 8 bits qui servent d'index dans un tableau

La permutation est initialisée grâce à la clé de taille variable, typiquement entre 40 et 256 bits, grâce au ''[[key schedule]]'' de RC4.

=== Génération de la permutation ===
[[Image:Keyschedule rc4.png|vignette|droite|256px|Image représentant l'état interne de la permutation sur les 256 itérations (axe vertical) avec la clé ''WIKIPEDIA''. Une ligne représente le tableau à l'itération correspondante. On voit que la première ligne symbolise la permutation identité et que l'algorithme permute progressivement les octets afin d'obtenir un contenu suffisamment mélangé à la dernière ligne.]]
La permutation <math>S</math> est initialisée grâce à la clé <math>K</math>. La longueur de la clé varie de 1 à 256 octets (8 à 2048 bits). En pratique, elle est souvent choisie de taille égale à 5 octets (pour 40 bits) ou 13 octets (pour 104 bits). La permutation se présente sous la forme d'un tableau de 256 entrées. Ses valeurs initiales correspondent à l'identité au sens mathématique (le premier octet est permuté avec le premier octet, etc) :

 [0] [1] [2] [3] [4] ... [255]

L'algorithme de ''[[key schedule]]'' travaille dans ce tableau et effectue 256 itérations :

 '''pour''' i '''de''' 0 '''à''' 255
     S[i] := i
 '''finpour'''
 j := 0
 '''pour''' i '''de''' 0 '''à''' 255
     j := (j + S[i] + clé[i [[Congruence sur les entiers|mod]] longueur_clé]) mod 256
     échanger(S[i], S[j])
 '''finpour'''

À la fin, le tableau pourrait se présenter comme suit :

 [184] [106] [163] [64] [70] ... [201]

Ce qui signifie que le premier octet serait échangé avec le {{185e}}, le deuxième avec le {{107e}}, etc. On remarque par ailleurs que l'opération la plus complexe dans la génération de la permutation est le [[Congruence sur les entiers|modulo]], mais que celui-ci peut être remplacé par un ''et'' logique si la longueur de la clé est une [[Puissance de deux|puissance de 2]]. Il en va de même pour le modulo 256 qui revient à retenir les 8 bits de poids faible.

=== Génération du flot pseudo-aléatoire ===
[[Image:RC4.svg|droite|vignette|320px|Structure du générateur avec la dernière opération de génération. L'octet en sortie pour le flux de chiffrement est choisi dans le tableau, à l'index S(i) + S(j). On retrouve en sortie cette valeur S(S(i) + S(j)) qui sera "xor"-ée avec l'octet correspondant du texte clair.]]
Tant qu'un octet doit être généré pour effectuer le [[OU exclusif|XOR]] avec le texte clair, le générateur modifie son état interne selon la série d'instructions suivantes :

 i := 0
 j := 0
 '''tant_que''' générer une sortie:
     i := (i + 1) mod 256
     j := (j + S[i]) mod 256
     échanger(S[i], S[j])
     octet_chiffrement = S[(S[i] + S[j]) mod 256]
     result_chiffré = octet_chiffrement XOR octet_message
 '''fintant_que'''

Cet algorithme garantit que chaque valeur de <math>S</math> est échangée au moins une fois toutes les 256 itérations.

=== Implémentation ===
D'autres chiffrements par flot sont basés sur des [[Registre à décalage à rétroaction linéaire|registres à décalages à rétroaction linéaire]] dont la structure est efficace dans les implémentations matérielles et un peu moins dans le cas [[logiciel]]. RC4 évite ce problème et s'avère efficace pour l'implémentation logicielle puisque seules des manipulations au niveau des octets sont nécessaires. Il nécessite peu de mémoire (256 octets pour l'état interne, quelques octets pour les variables et la clé) et les modulos peuvent être simplifiées selon la taille de la clé, voire ignorés dans le cas du modulo 256 (on effectue l'addition et on garde les bits de poids faible sans s'occuper du dépassement)

Voici une implémentation en [[Python (langage)|Python]]:
<syntaxhighlight lang="python">
class WikipediaARC4:
    def __init__(self, key = None):
        self.state = list(range(256)) # initialisation de la table de permutation
        self.x = self.y = 0 # les index x et y, au lieu de i et j
 
        if key is not None:
            self.init(key)
 
    # Key schedule
    def init(self, key):
        for i in range(256):
            self.x = (ord(key[i % len(key)]) + self.state[i] + self.x) & 0xFF
            self.state[i], self.state[self.x] = self.state[self.x], self.state[i]
        self.x = 0
 
    # Générateur
    def crypt(self, input):
        output = [None]*len(input)
        for i in range(len(input)):
            self.x = (self.x + 1) & 0xFF
            self.y = (self.state[self.x] + self.y) & 0xFF
            self.state[self.x], self.state[self.y] = self.state[self.y], self.state[self.x]
            output[i] = chr((ord(input[i]) ^ self.state[(self.state[self.x] + self.state[self.y]) & 0xFF]))
        return ''.join(output)
 
import base64
def encode(sh):
	return base64.b16encode(bytes(sh, 'latin')).upper()

if __name__ == '__main__':
    test_vectors = [['Key', 'Plaintext'], \
                    ['Wiki', 'pedia'], \
                    ['Secret', 'Attack at dawn']]
    for i in test_vectors:
        encode(WikipediaARC4(i[0]).crypt(i[1]))</syntaxhighlight>

Résultat (sortie en hexadécimal) :

RC4( "Key", "Plaintext" ) = BBF316E8D940AF0AD3

RC4( "[[Wiki]]", "pedia" ) = 1021BF0420

RC4( "Secret", "Attack at dawn" ) = 45A01F645FC35B383552544B9BF5

== Sécurité ==
De par sa popularité, RC4 a fait l'objet de nombreuses recherches. Il est désormais considéré comme peu sûr du point de vue [[Cryptographie|cryptographique]] et ne devrait pas être employé pour de nouvelles applications.

Le flux aléatoire généré par RC4 est légèrement biaisé en faveur de certaines séquences d'octets. La meilleure attaque utilisant cette faiblesse a été publiée par Scott Fluhrer et David McGrew. Leur attaque arrive à distinguer un flux pseudo-aléatoire RC4 d'un flux aléatoire, moyennant des données de l'ordre du gigaoctet.

RC4 n'utilise pas un [[vecteur d'initialisation]] séparé, en plus de la clé. Un tel vecteur est en général une nécessité pour garantir une sécurité suffisante, de manière que chiffrer le même message deux fois avec la même clé ne produise pas la même sortie. Une approche possible consiste à générer une nouvelle clé en hachant la [[concaténation]] de la clé principale avec un vecteur d'initialisation. Toutefois, des applications se contentent de concaténer la clé et le vecteur, sans les hacher. Une telle procédure peut s'avérer vulnérable si elle est mal conçue.

=== Attaque de Fluhrer, Mantin et Shamir (attaque FMS) ===
En [[2001]], Scott Fluhrer, Itsik Mantin et [[Adi Shamir]] ont présenté une nouvelle attaque. Parmi toutes les clés possibles en RC4, les statistiques sur les premiers octets du flux généré montrent un certain biais qui permet de retrouver des informations sur la clé. En d'autres termes, les premiers octets du flux utilisé pour le chiffrement ne sont pas aléatoires. Si l'on se contente de concaténer la clé et le vecteur d'initialisation pour produire la nouvelle clé, alors il est possible de découvrir des informations en utilisant un grand nombre de messages chiffrés avec cette clé augmentée. C'est ce type d'attaque qui a été utilisée pour casser le [[Wired Equivalent Privacy|WEP]] des réseaux sans fil, une action qui a abouti à la mise en place d'une version améliorée du chiffrement, à savoir [[Wi-Fi Protected Access|WPA]]. Dans le cas du WEP, un vecteur d'initialisation de 24 bits est utilisé, ce qui permet de produire environ 16,8 millions clés supplémentaires à partir d'une clé principale (celle du [[point d'accès]]). Ce nombre est insuffisant eu égard aux possibilités de l'attaque FMS.

Une parade consiste à mettre de côté la première portion du flot généré, par exemple les 1024 premiers octets.

=== Autres vulnérabilités statistiques ===
[[Bart Preneel]] et Souradyuti Paul ont montré en [[2004]] que la distinction entre un flot aléatoire et un flot de RC4 ne nécessitait que 2<sup>25</sup> octets produits par RC4. Ils ont entre autres montré que le biais ne disparaît pas même si les 256 premiers octets sont éliminés.

=== Espace des états ===
L'état interne du RC4 qui se résume au tableau de permutation s'élève à : <math>log_2{(2^8!)}~</math>, soit environ 1684 bits<ref>{{en}} Adi Shamir, Itsik Mantin, {{lien archive|url=http://citeseer.ist.psu.edu/mantin01practical.html|titre={{langue|en|A Practical Attack on Broadcast RC4}}|horodatage archive=20060508042238}}.</ref>. En 1994, peu après la publication de la description supposée de RC4, H. Finney a montré que certains états ne pouvaient se produire, quelle que soit la clé (environ 0,015% des états sont dans ce cas). Cette découverte laissait entrevoir des faiblesses dans les états internes de l'algorithme.

En [[2001]], Itsik Mantin et Adi Shamir ont présenté le principe d'« état prédictif » dans lequel ''a'' éléments du tableau de permutation ainsi que les pointeurs ''i'' et ''j'' sont connus (avec ''a'' < 256). Si l'état interne lors d'une [[itération]] est compatible avec un état prédictif, alors leur [[conjecture]] stipule que seuls ''a'' octets peuvent être prédits dans les 256 itérations suivantes. Cette conjecture ne fut prouvée qu'en [[2004]] par Souradyuti Paul et [[Bart Preneel]] mais ouvrait la voie à d'autres attaques statistiques grâce à la détection d'états internes particuliers.

== Cryptosystèmes basés sur RC4 ==
* [[Wired Equivalent Privacy|WEP]]
(WPA2 utilise quant à lui [[Advanced Encryption Standard|AES]])

== Variante ==
[[Arcfour]] est une méthode libre de chiffrement, similaire à RC4 et postée sur [[Usenet]] par un anonyme affirmant avoir désassemblé RC4.

== Notes et références ==
=== Notes ===
{{Références|groupe=note}}

=== Références ===
{{Références}}

== Annexes ==
=== Bibliographie ===
* {{en}} {{PDF}} S. Fluhrer, I. Mantin, A. Shamir, [http://www.crypto.com/papers/others/rc4_ksaproc.pdf ''Weaknesses in the Key Scheduling Algorithm of RC4'']
* {{en}} Lars R. Knudsen, Willi Meier, Bart Preneel, [[Vincent Rijmen]], Sven Verdoolaege, [http://citeseer.ist.psu.edu/524295.html ''Analysis Methods for (Alleged) RC4'']
* {{en}} {{PDF}} Adam Stubblefield, John Ioannidis, Aviel Rubin, [http://www.isoc.org/isoc/conferences/ndss/02/proceedings/papers/stubbl.pdf ''Using the Fluhrer, Mantin, and Shamir Attack to Break WEP'']
* {{en}} {{postscript}} Bart Preneel, Souradyuti Paul, [http://www.cosic.esat.kuleuven.be/publications/article-40.ps ''A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher'']

=== Liens externes ===
* Implémentation de l’algorithme RC4 en C [http://bradconte.com/rc4_c ''C implementation of RC4 algorithm'' ]
* [http://www.cityinthesky.co.uk/opensource/dcpcrypt ''Une implémentation de l'algorithme RC4''] (et de nombreuses autres méthodes de chiffrement) en [[Pascal Objet|Pascal objet]] au moyen d'un paquet [[Embarcadero Delphi|Delphi]] et [[Lazarus]].

{{Palette|Chiffrement de flux}}
{{Portail|Cryptologie}}

[[Catégorie:Algorithme de chiffrement par flot]]
[[Catégorie:Algorithme de cryptographie symétrique]]