RC4

En cryptographie , RC4 (Rivest Cipher 4, également connu sous le nom d'ARC4 ou ARCFOUR , ce qui signifie prétendument RC4, voir ci-dessous) est un chiffrement de flux . Bien qu'il soit remarquable pour sa simplicité et sa rapidité dans les logiciels, de multiples vulnérabilités ont été découvertes dans RC4, le rendant peu sûr. Il est particulièrement vulnérable lorsque le début du flux de clés de sortie n'est pas supprimé, ou lorsque des clés non aléatoires ou liées sont utilisées. Des utilisations particulièrement problématiques de RC4 ont conduit à des protocoles très peu sûrs tels que WEP .

En 2015 , on spécule que certaines agences cryptologiques nationales pourraient posséder la capacité de casser RC4 lorsqu'il est utilisé dans le protocole TLS . L'IETF a publié la RFC 7465 pour interdire l'utilisation de RC4 dans TLS ; Mozilla et Microsoft ont émis des recommandations similaires.

Plusieurs tentatives ont été faites pour renforcer RC4, notamment Spritz, RC4A, VMPC et RC4 ⁺ .

RC4 a été conçu par Ron Rivest de RSA Security en 1987. Bien qu'il soit officiellement appelé « Rivest Cipher 4 », l'acronyme RC est également compris comme signifiant « Ron's Code » (voir également RC2 , RC5 et RC6 ).

RC4 était initialement un secret commercial , mais en septembre 1994, une description de celui-ci a été publiée anonymement sur la liste de diffusion Cypherpunks . Il a rapidement été publié sur le groupe de discussion sci.crypt , où il a été cassé en quelques jours par Bob Jenkins . De là, il s'est répandu sur de nombreux sites Internet. Le code divulgué a été confirmé comme étant authentique, car il s'est avéré que son résultat correspondait à celui d'un logiciel propriétaire utilisant RC4 sous licence. Comme l'algorithme est connu, il n'est plus un secret commercial. Le nom RC4 est une marque déposée, donc RC4 est souvent appelé ARCFOUR ou ARC4 (qui signifie prétendu RC4 ) pour éviter les problèmes de marque. RSA Security n'a jamais officiellement publié l'algorithme ; Rivest a cependant fait un lien vers l' article de Wikipédia en anglais sur RC4 dans ses propres notes de cours en 2008 et a confirmé l'histoire de RC4 et de son code dans un article de 2014 qu'il a rédigé.

RC4 a été intégré à certains protocoles et normes de chiffrement couramment utilisés, tels que WEP en 1997 et WPA en 2003/2004 pour les cartes sans fil, et SSL en 1995 et son successeur TLS en 1999, jusqu'à ce qu'il soit interdit pour toutes les versions de TLS par la RFC 7465 en 2015, en raison des attaques RC4 affaiblissant ou cassant RC4 utilisé dans SSL/TLS. Les principaux facteurs du succès de RC4 sur une gamme aussi large d'applications ont été sa rapidité et sa simplicité : des implémentations efficaces, tant au niveau logiciel que matériel, étaient très faciles à développer.

RC4 génère un flux pseudo-aléatoire de bits (un flux de clés ). Comme pour tout chiffrement par flux, ceux-ci peuvent être utilisés pour le chiffrement en le combinant avec le texte en clair en utilisant le ou exclusif au niveau du bit ; le déchiffrement est effectué de la même manière (puisque le ou exclusif avec des données données est une involution ). Ceci est similaire au bloc-notes à usage unique , sauf que des bits pseudo-aléatoires générés , plutôt qu'un flux préparé, sont utilisés.

Pour générer le flux de clés, le chiffrement utilise un état interne secret composé de deux parties :

1. Une permutation de tous les 256 octets possibles (notés « S » ci-dessous).
2. Deux pointeurs d'index 8 bits (notés « i » et « j »).

La permutation est initialisée avec une clé de longueur variable , généralement comprise entre 40 et 2048 bits, à l'aide de l' algorithme de planification de clé (KSA). Une fois cette opération terminée, le flux de bits est généré à l'aide de l' algorithme de génération pseudo-aléatoire (PRGA).

L' algorithme de planification de clés est utilisé pour initialiser la permutation dans le tableau « S ». La « longueur de clé » est définie comme le nombre d'octets dans la clé et peut être comprise entre 1 ≤ longueur de clé ≤ 256, généralement entre 5 et 16, correspondant à une longueur de clé de 40 à 128 bits. Tout d'abord, le tableau « S » est initialisé à la permutation d'identité . S est ensuite traité pendant 256 itérations de manière similaire au PRGA principal, mais mélange également des octets de la clé en même temps.

pour i de 0 à 255 S[i] := i fin pour j := 0 pour i de 0 à 255 j := (j + S[i] + clé[i mod longueur de clé]) mod 256 échanger les valeurs de S[i] et S[j] fin pour

Pour autant d'itérations que nécessaire, le PRGA modifie l'état et génère un octet du flux de clés. À chaque itération, le PRGA :

• incréments i ;
• recherche le i ème élément de S , S[ i ] , et l'ajoute à j ;
• échange les valeurs de S[ i ] et S[ j ] , puis utilise la somme S[ i ] + S[ j ] (modulo 256) comme index pour récupérer un troisième élément de S (la valeur du flux de clés K ci-dessous) ;
• puis un OU exclusif au niveau du bit ( XOR ) avec l'octet suivant du message pour produire l'octet suivant du texte chiffré ou du texte en clair.

Chaque élément de S est échangé avec un autre élément au moins une fois toutes les 256 itérations.

je := 0 j := 0 pendant la génération de la sortie : i := (i + 1) mod 256 j := (j + S[i]) mod 256 échanger les valeurs de S[i] et S[j] t := (S[i] + S[j]) mod 256 K := S[t] sortie K pour finir

Ainsi, cela produit un flux de K[0], K[1], ... qui sont XORés avec le texte en clair pour obtenir le texte chiffré . Ainsi, ciphertext[ l ] = plaintext[ l ] ⊕ K[ l ] .

Plusieurs systèmes d'exploitation incluent arc4random, une API issue d' OpenBSD qui permet d'accéder à un générateur de nombres aléatoires basé à l'origine sur RC4. L'API ne permet pas de seeding, car la fonction s'initialise elle-même en utilisant /dev/random . L'utilisation de RC4 a été progressivement abandonnée dans la plupart des systèmes implémentant cette API. Les pages de manuel du nouvel arc4random incluent le rétroacronyme « A Replacement Call for Random » pour ARC4 comme mnémonique, car il fournit de meilleures données aléatoires que rand() .

• Dans OpenBSD 5.5, publié en mai 2014, arc4randoma été modifié pour utiliser ChaCha20 . Les implémentations d'arc4random dans FreeBSD , NetBSD utilisent également ChaCha20.
  • Linux utilise généralement glibc , qui n'a pas proposé arc4random avant 2022. À la place, une bibliothèque distincte, libbsd, propose la fonction ; elle a été mise à jour pour utiliser ChaCha20 en 2016. En 2022, glibc a ajouté sa propre version d' arc4random , également basée sur ChaCha20.
• Selon les pages de manuel fournies avec le système d'exploitation, dans la version 2017 des systèmes d'exploitation macOS et iOS , Apple a remplacé RC4 par AES dans son implémentation d'arc4random.

Les nouveaux générateurs de nombres aléatoires proposés sont souvent comparés au générateur de nombres aléatoires RC4.

Plusieurs attaques sur RC4 sont capables de distinguer sa sortie d’une séquence aléatoire .

De nombreux chiffrements de flux sont basés sur des registres à décalage à rétroaction linéaire (LFSR), qui, bien qu'efficaces au niveau matériel, le sont moins au niveau logiciel. La conception de RC4 évite l'utilisation de LFSR et est idéale pour une implémentation logicielle, car elle ne nécessite que des manipulations d'octets. Il utilise 256 octets de mémoire pour le tableau d'état, S[0] à S[255], k octets de mémoire pour la clé, key[0] à key[k−1], et des variables entières, i, j et K. L'exécution d'une réduction modulaire d'une valeur modulo 256 peut être effectuée avec un ET au niveau du bit avec 255 (ce qui équivaut à prendre l'octet de poids faible de la valeur en question).

Ces vecteurs de test ne sont pas officiels, mais ils sont pratiques pour quiconque teste son propre programme RC4. Les clés et le texte en clair sont en ASCII , le flux de clés et le texte chiffré sont en hexadécimal .

Contrairement à un chiffrement de flux moderne (comme ceux d' eSTREAM ), RC4 n'utilise pas de nonce séparé à côté de la clé. Cela signifie que si une seule clé à long terme doit être utilisée pour crypter de manière sécurisée plusieurs flux, le protocole doit spécifier comment combiner le nonce et la clé à long terme pour générer la clé de flux pour RC4. Une approche pour résoudre ce problème consiste à générer une clé RC4 « fraîche » en hachant une clé à long terme avec un nonce . Cependant, de nombreuses applications qui utilisent RC4 concaténent simplement la clé et le nonce ; la planification de clé faible de RC4 donne alors lieu à des attaques de clés liées , comme l' attaque Fluhrer, Mantin et Shamir (qui est célèbre pour avoir brisé la norme WEP ).

Comme RC4 est un chiffrement par flux , il est plus malléable que les chiffrements par blocs courants . S'il n'est pas utilisé avec un code d'authentification de message fort (MAC), le chiffrement est alors vulnérable à une attaque par retournement de bits . Le chiffrement est également vulnérable à une attaque par chiffrement par flux s'il n'est pas implémenté correctement.

Il convient toutefois de noter que RC4, en tant que chiffrement de flux, a été pendant un certain temps le seul chiffrement commun à être immunisé contre l' attaque BEAST de 2011 sur TLS 1.0 . L'attaque exploite une faiblesse connue dans la façon dont le mode de chaînage de blocs de chiffrement est utilisé avec tous les autres chiffrements pris en charge par TLS 1.0, qui sont tous des chiffrements par blocs.

En mars 2013, de nouveaux scénarios d'attaque ont été proposés par Isobe, Ohigashi, Watanabe et Morii, ainsi que par AlFardan, Bernstein, Paterson, Poettering et Schuldt qui utilisent de nouveaux biais statistiques dans la table de clés RC4 pour récupérer du texte en clair avec un grand nombre de chiffrements TLS.

L'utilisation de RC4 dans TLS est interdite par la RFC 7465 publiée en février 2015.

Français En 1995, Andrew Roos a observé expérimentalement que le premier octet du flux de clés est corrélé aux trois premiers octets de la clé, et que les premiers octets de la permutation après le KSA sont corrélés à une combinaison linéaire des octets de la clé. Ces biais sont restés inexpliqués jusqu'en 2007, lorsque Goutam Paul, Siddheshwar Rathi et Subhamoy Maitra ont prouvé la corrélation flux de clés–clé et, dans un autre travail, Goutam Paul et Subhamoy Maitra ont prouvé les corrélations permutation–clé. Ce dernier travail a également utilisé les corrélations permutation–clé pour concevoir le premier algorithme de reconstruction complète de clé à partir de la permutation finale après le KSA, sans aucune hypothèse sur la clé ou le vecteur d'initialisation . Cet algorithme a une probabilité de succès constante dans un temps, qui est la racine carrée de la complexité de la recherche de clé exhaustive. Par la suite, de nombreux autres travaux ont été réalisés sur la reconstruction de clés à partir des états internes RC4. Subhamoy Maitra et Goutam Paul ont également montré que les biais de type Roos persistent même lorsque l'on considère des indices de permutation imbriqués, comme S[S[i]] ou S[S[S[i]]] . Ces types de biais sont utilisés dans certaines des méthodes de reconstruction clés ultérieures pour augmenter la probabilité de succès.

Le flux de clés généré par le RC4 est biaisé à des degrés divers vers certaines séquences, ce qui le rend vulnérable aux attaques de distinction . La meilleure attaque de ce type est due à Itsik Mantin et Adi Shamir , qui ont montré que le deuxième octet de sortie du chiffrement était biaisé vers zéro avec une probabilité de 1/128 (au lieu de 1/256). Cela est dû au fait que si le troisième octet de l'état d'origine est nul et que le deuxième octet n'est pas égal à 2, alors le deuxième octet de sortie est toujours nul. Un tel biais peut être détecté en observant seulement 256 octets.

Paul Souradyuti et Bart Preneel du COSIC ont montré que le premier et le deuxième octets du RC4 étaient également biaisés. Le nombre d'échantillons requis pour détecter ce biais est de 2,25 ^octets .

Scott Fluhrer et David McGrew ont également montré des attaques qui distinguaient le flux de clés du RC4 d'un flux aléatoire étant donné un gigaoctet de sortie.

La caractérisation complète d'une seule étape de RC4 PRGA a été réalisée par Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra et Goutam Paul. En considérant toutes les permutations, ils ont prouvé que la distribution de la sortie n'est pas uniforme étant donné i et j, et par conséquent, les informations sur j sont toujours filtrées dans la sortie.

En 2001, Fluhrer, Mantin et Shamir ont fait une découverte nouvelle et surprenante : sur toutes les clés RC4 possibles, les statistiques des premiers octets du flux de clés de sortie sont fortement non aléatoires, ce qui laisse fuiter des informations sur la clé. Si le nonce et la clé à long terme sont simplement concaténés pour générer la clé RC4, cette clé à long terme peut être découverte en analysant un grand nombre de messages chiffrés avec cette clé. Cet effet et d'autres effets connexes ont ensuite été utilisés pour casser le chiffrement WEP (« wired equivalent privacy ») utilisé avec les réseaux sans fil 802.11 . Cela a provoqué une ruée vers un remplacement basé sur des normes pour le WEP sur le marché 802.11 et a conduit à l' effort IEEE 802.11i et au WPA .

Les protocoles peuvent se défendre contre cette attaque en supprimant la partie initiale du flux de clés. Un tel algorithme modifié est traditionnellement appelé « RC4-drop[ n ] », où n est le nombre d'octets du flux de clés initial qui sont supprimés. La valeur par défaut de SCAN est n = 768 octets, mais une valeur prudente serait n = 3072 octets.

L'attaque Fluhrer, Mantin et Shamir ne s'applique pas au SSL basé sur RC4, car SSL génère les clés de chiffrement qu'il utilise pour RC4 par hachage, ce qui signifie que différentes sessions SSL ont des clés sans rapport.

En 2005, Andreas Klein a présenté une analyse du chiffrement par flux RC4, montrant davantage de corrélations entre le flux de clés RC4 et la clé. Erik Tews, Ralf-Philipp Weinmann et Andrei Pychkine ont utilisé cette analyse pour créer aircrack-ptw, un outil qui craque le RC4 104 bits utilisé dans le WEP 128 bits en moins d'une minute. Alors que l'attaque Fluhrer, Mantin et Shamir utilisait environ 10 millions de messages, aircrack-ptw peut casser des clés 104 bits en 40 000 trames avec une probabilité de 50 %, ou en 85 000 trames avec une probabilité de 95 %.

Un problème combinatoire lié au nombre d'entrées et de sorties du chiffrement RC4 a été posé pour la première fois par Itsik Mantin et Adi Shamir en 2001, selon lequel, sur les 256 éléments au total dans l'état typique de RC4, si seulement x éléments ( x ≤ 256) sont connus (tous les autres éléments peuvent être supposés vides), alors le nombre maximum d'éléments qui peuvent être produits de manière déterministe est également x dans les 256 tours suivants. Cette conjecture a été mise au repos en 2004 avec une preuve formelle donnée par Souradyuti Paul et Bart Preneel .

En 2013, un groupe de chercheurs en sécurité du groupe de sécurité de l'information de Royal Holloway, Université de Londres, a signalé une attaque qui peut devenir efficace en utilisant seulement 2 ³⁴ messages chiffrés. Bien qu'il ne s'agisse pas encore d'une attaque pratique pour la plupart des objectifs, ce résultat est suffisamment proche d'une attaque pour conduire à la spéculation selon laquelle il est plausible que certaines agences cryptologiques d'État puissent déjà avoir de meilleures attaques qui rendent RC4 non sécurisé. Étant donné qu'en 2013 , une grande quantité de trafic TLS utilise RC4 pour éviter les attaques sur les chiffrements par blocs qui utilisent le chaînage de blocs de chiffrement , si ces meilleures attaques hypothétiques existent, cela rendrait la combinaison TLS-avec-RC4 non sécurisée contre de tels attaquants dans un grand nombre de scénarios pratiques.

En mars 2015, les chercheurs de Royal Holloway ont annoncé des améliorations à leur attaque, en fournissant une attaque 2 ²⁶ contre les mots de passe chiffrés avec RC4, comme utilisé dans TLS.

Lors de la conférence Black Hat Asia 2015, Itsik Mantin a présenté une autre attaque contre SSL en utilisant le chiffrement RC4.

En 2015, des chercheurs en sécurité de la KU Leuven ont présenté de nouvelles attaques contre RC4 dans TLS et WPA-TKIP . Baptisée attaque NOMORE (Numerous Occurrence MOnitoring & Recovery Exploit), il s'agit de la première attaque de ce type à avoir été démontrée en pratique. Leur attaque contre TLS peut décrypter un cookie HTTP sécurisé en 75 heures. L'attaque contre WPA-TKIP peut être réalisée en une heure et permet à un attaquant de décrypter et d'injecter des paquets arbitraires.

Comme mentionné ci-dessus, la faiblesse la plus importante de RC4 vient de la planification insuffisante des clés ; les premiers octets de sortie révèlent des informations sur la clé. Cela peut être corrigé en supprimant simplement une partie initiale du flux de sortie. Ceci est connu sous le nom de RC4-drop N , où N est généralement un multiple de 256, comme 768 ou 1024.

Plusieurs tentatives ont été faites pour renforcer RC4, notamment Spritz, RC4A, VMPC et RC4 ⁺ .

Souradyuti Paul et Bart Preneel ont proposé une variante de RC4, qu'ils appellent RC4A.

RC4A utilise deux tableaux d'état S1 et S2 et deux index j1 et j2 . Chaque fois que i est incrémenté, deux octets sont générés :

1. Tout d’abord, l’algorithme RC4 de base est exécuté en utilisant S1 et j1 , mais dans la dernière étape, S1[ i ]+S1[ j1 ] est recherché dans S2 .
2. Deuxièmement, l'opération est répétée (sans incrémenter i à nouveau) sur S2 et j2 , et S1[S2[ i ]+S2[ j2 ]] est généré en sortie.

Ainsi, l'algorithme est :

Toutes les opérations arithmétiques sont effectuées modulo 256 je := 0 j1 := 0 j2 := 0 pendant la génération de la sortie : je := i + 1 j1 := j1 + S1[i] échanger les valeurs de S1[i] et S1[j1] sortie S2[S1[i] + S1[j1]] j2 := j2 + S2[i] échanger les valeurs de S2[i] et S2[j2] sortie S1[S2[i] + S2[j2]] endwhile

Bien que l'algorithme nécessite le même nombre d'opérations par octet de sortie, il offre un plus grand parallélisme que RC4, ce qui permet une amélioration possible de la vitesse.

Bien que plus puissant que RC4, cet algorithme a également été attaqué, avec Alexander Maximov et une équipe de NEC développant des moyens de distinguer sa sortie d'une séquence véritablement aléatoire.

La composition de permutation modifiée variablement (VMPC) est une autre variante de RC4. Elle utilise un programme de clés similaire à celui de RC4, avec j := S[(j + S[i] + key[i mod keylength]) mod 256] itérant 3 × 256 = 768 fois au lieu de 256, et avec 768 itérations supplémentaires facultatives pour incorporer un vecteur initial. La fonction de génération de sortie fonctionne comme suit :

Toutes les opérations arithmétiques sont effectuées modulo 256. je := 0 pendant la génération de la sortie : a := S[i] j := S[j + a] sortie S[S[S[j] + 1]] Échanger S[i] et S[j] ( b := S[j]; S[i] := b; S[j] := a) ) je := i + 1 pour finir

Cela a été attaqué dans les mêmes articles que RC4A et peut être distingué dans 2 ³⁸ octets de sortie.

RC4 ⁺ est une version modifiée de RC4 avec une planification de clé en trois phases plus complexe (prenant environ trois fois plus de temps que RC4, ou le même temps que RC4-drop512), et une fonction de sortie plus complexe qui effectue quatre recherches supplémentaires dans le tableau S pour chaque sortie d'octet, prenant environ 1,7 fois plus de temps que RC4 de base.

Toutes les opérations arithmétiques modulo 256.  << et >> sont décalés vers la gauche et vers la droite, ⊕ est OU exclusif
 lors de la génération de la sortie : je := i + 1 a := S[i] j := j + a Échanger S[i] et S[j] ( b := S[j]; S[j] := S[i]; S[i] := b; ) c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3] sortie (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b] endwhile

Cet algorithme n’a pas été analysé de manière significative.

En 2014, Ronald Rivest a donné une conférence et co-écrit un article sur une refonte mise à jour appelée Spritz. Un accélérateur matériel de Spritz a été publié dans Secrypt, 2016 et montre qu'en raison des multiples appels imbriqués nécessaires pour produire des octets de sortie, Spritz fonctionne plutôt lentement par rapport à d'autres fonctions de hachage telles que SHA-3 et la meilleure implémentation matérielle connue de RC4.

Comme d'autres fonctions éponge , Spritz peut être utilisé pour créer une fonction de hachage cryptographique, un générateur de bits aléatoires déterministe ( DRBG ), un algorithme de cryptage prenant en charge le cryptage authentifié avec des données associées (AEAD), etc.

En 2016, Banik et Isobe ont proposé une attaque capable de distinguer Spritz du bruit aléatoire. En 2017, Banik, Isobe et Morii ont proposé une solution simple qui supprime le distinguateur dans les deux premiers octets du flux de clés, ne nécessitant qu'un seul accès mémoire supplémentaire sans diminuer considérablement les performances du logiciel.

• WEP
• TKIP (algorithme par défaut pour WPA , mais peut être configuré pour utiliser AES-CCMP au lieu de RC4)
• Cryptage du protocole BitTorrent
• Microsoft Office XP (implémentation non sécurisée puisque le nonce reste inchangé lorsque les documents sont modifiés )
• Chiffrement point à point Microsoft
• Transport Layer Security / Secure Sockets Layer (était facultatif, puis l'utilisation de RC4 a été interdite dans la RFC 7465)
• Secure Shell (en option)
• Protocole de bureau à distance (en option)
• Kerberos (en option)
• SASL Mechanism Digest-MD5 (en option, historique , obsolète dans RFC 6331)
• Gpcode.AK, un virus informatique de début juin 2008 pour Microsoft Windows, qui prend des documents en otage contre rançon en les masquant avec un cryptage RC4 et RSA-1024
• PDF
• Skype (sous forme modifiée)

Lorsqu'un protocole est marqué « (en option) », RC4 est l'un des nombreux chiffrements que le système peut être configuré pour utiliser.