Loading AI tools
algorithme de chiffrement de flux De Wikipédia, l'encyclopédie libre
Ne doit pas être confondu avec Route coloniale 4.
RC4 (Rivest Cipher 4) est un algorithme de chiffrement en continu 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 TLS (anciennement SSL) ou encore WEP.
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 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.
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.
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 :
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.
La permutation est initialisée grâce à la clé . 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 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 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.
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 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
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 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.
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 225 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 à : , 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.
(WPA2 utilise quant à lui AES)
Arcfour est une méthode libre de chiffrement, similaire à RC4 et postée sur Usenet par un anonyme affirmant avoir désassemblé RC4.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
