Exercice - 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. L'état interne du chiffrement consiste en deux octets i et j initialisés à 0 et d'un tableau S de 256 valeurs distinctes, représentant une permutation des entiers compris entre 0 et 255.

À partir de i, j et S l'algorithme produit une suite d'octets z1, ..., zL (où L désigne le nombre d'octets du message à chiffrer) de la façon suivante :

t:=1
i := 0
j := 0
tant_que t ≤ L
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    échanger(S[i], S[j])
    z[t] = S[(S[i] + S[j]) mod 256]
    t++
fintant_que

La suite z de bits pseudo-aléatoires est ensuite utilisé pour chiffrer les données via une somme modulo 256 octet par octet.

  1. Programmer la génération de cette suite chiffrante (prenant en entrée i, j et S) dans votre langage de programmation préféré.

  2. En notant S0[a] la valeur de S en a juste après l'initialisation et Si[a] la valeur de S en a après le i-ième tour de boucle, montrer que si S0[2]=0 et si S0[1] <> 1 alors z1 = 0 avec probabilité 1.

  3. En déduire que la distribution de z1 n'est pas uniforme lorsque S est initialisé à une permutation aléatoire.

  4. Supposons que l'on chiffre le même texte clair pour N destinataires différents ayant des clés RC4 différentes. Proposer un algorithme qui retrouve le second octet du clair. A partir de quelle valeur l'algorithme est-il efficace. Implanter cet algorithme.

L'initialisation de la permutation S se fait à partir d'une clé C dont la longueur varie de 1 à 256 bits et d'une valeur d'initialisation IV de 16 octets (transmise en clair avec le chiffré). En pratique, la clé est souvent choisie de taille égale à 5 octets (pour 40 bits) ou 16 octets (pour 128 bits).

Dans le cas d'une clé de 16 octets, on commence à remplir un tableau K de 256 octets : les premiers octets contiennent IV et les octets suivants contiennent C répétés 15 fois. La permutation S est ensuite générée par la procédure suivante :

pour i de 0 à 255
    S[i] := i
finpour
j := 0
pour i de 0 à 255
    j := (j + S[i] + K[i]) mod 256
    échanger(S[i], S[j])
finpour

  1. Programmer la génération de la permutation S (prenant en entrée IV et C de 16 octets chacun).

  2. Soit 16 ≤ B ≤ 255 et soit k = K[B]. On cherche à déterminer k en supposant les valeurs de K[l] connues pour l < B. Montrer que l'état S' de S et j'de j à la fin de la boucle de mélange d'indice B sont connus.

  3. On suppose de plus que K[0] = B et K[1] = 255. Montrer qu'avec une probabilité significative (qu'on peut estimer à e-3), la sortie z1 vaut S'[j'+S'[B]+k mod 256]

  4. On suppose que des clairs dont le premier octet est connu sont chiffrés de manière répétée avec la même clé et des IV différents. Proposer une attaque qui dévoile la clé à partir des chiffrés observés.

  5. Implanter cette attaque.
top
top