RC4

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 ${\displaystyle S}$ est initialisée grâce à la clé ${\displaystyle 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 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 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 185^e, le deuxième avec le 107^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.

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

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 = 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]))

Résultat (sortie en hexadécimal) :

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

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

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

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 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.

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.

L'état interne du RC4 qui se résume au tableau de permutation s'élève à : ${\displaystyle 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.

• (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

• Implémentation de l’algorithme RC4 en C C implementation of RC4 algorithm
• Une implémentation de l'algorithme RC4 (et de nombreuses autres méthodes de chiffrement) en Pascal objet au moyen d'un paquet Delphi et Lazarus.