RC4

 Ne doit pas être confondu avec Route coloniale 4.

Schéma d'un tour de RC4

RC4 est un algorithme de chiffrement à flot conçu en 1987 par Ronald Rivest, l'un des inventeurs du RSA, pour les Laboratoires RSA. Il est supporté par différentes normes, par exemple dans SSL ou encore 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 et RC6.

Les détails de RC4 furent initialement tenus secrets mais en septembre 1994, une description du chiffrement fut postée de manière anonyme sur la liste de diffusion Cypherpunks ^[1]. Le message apparut ensuite sur le forum sci.crypt ^[2] 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 WEP, WPA ainsi que 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 XOR.

Description détaillée

RC4 est un générateur de bits pseudo-aléatoires dont le résultat est combiné avec le texte en clair via une opération XOR, le déchiffrement se fait de la même manière (voir chiffrement de Vernam).

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

1. une permutation S de tous les 256 octets possibles
2. deux pointeurs i et j 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 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 S est initialisée grâce à la clé K. 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 16 octets (pour 128 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 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 184^e, le deuxième avec le 106^e, etc. On remarque par ailleurs que l'opération la plus complexe dans la génération de la permutation est le modulo, mais que celui-ci peut être remplacé par un et logique si la longueur de la clé est une 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

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 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 S est échangée au moins une fois toutes les 256 itérations.

Implémentation

D'autres chiffrements par flot sont basés sur des 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:

class WikipediaARC4:
    def __init__(self, key = None):
        self.state = 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 xrange(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)
 
if __name__ == '__main__':
    test_vectors = [['Key', 'Plaintext'], \
                    ['Wiki', 'pedia'], \
                    ['Secret', 'Attack at dawn']]
    for i in test_vectors:
        print WikipediaARC4(i[0]).crypt(i[1]).encode('hex').upper()

Résultat (sortie en hexadécimal) :

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

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

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

Une implémentation en C peut être trouvée ici

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 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 à ce 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 WEP des réseaux sans fil, une action qui a abouti à la mise en place d'une version améliorée du chiffrement, à savoir 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 les 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²⁵ 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 à : $log_2{(2^8!)}~$, soit environ 1684 bits^[3]. 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

• WEP
• WPA (WPA2 utilise quant à lui 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

1. ↑ Thank you Bob Anderson
2. ↑ RC4 Algorithm revealed.
3. ↑ A Practical Attack on Broadcast RC4, Adi Shamir, Itsik Mantin

Sources

• (en) [PDF] S. Fluhrer, I. Mantin, A. Shamir, Weaknesses in the Key Scheduling Algorithm of RC4
• (en) Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen, Sven Verdoolaege, Analysis Methods for (Alleged) RC4
• (en) [PDF] Adam Stubblefield, John Ioannidis, Aviel Rubin, Using the Fluhrer, Mantin, and Shamir Attack to Break WEP
• (en) [ps] Bart Preneel, Souradyuti Paul, A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher

Liens externes

RC4 algorithm implementation C implementation of RC4 algorithm