Chiffrements par flux

L'idée est d'imiter le one-time-pad en remplaçant le masque aléatoire connu des deux parties par un générateur pseudo-aléatoire, engendrant de part et d'autre des flux identiques lorsqu'il est initialisé avec la même clef.

  • Il est difficile de construire de bons générateurs pseudo-aléatoires.

  • On doit éviter que plusieurs messages soient chiffrés avec des flux identiques : même danger qu'avec le many-times pad.

Pour l'éviter, on préfixe au message un vecteur d'initialisation qui sera concaténé à la clef pour initialiser le générateur.

Pour le WEP, ce vecteur de 24 bits sera réutilisé au bout de quelques heures (mais il y a des failles beaucoup plus graves). ### Exemple : RC4

Le flux le plus utilisé est RC4 (Rivest Cipher 4, ou Ron's Code 4).

L'algorithme est simple et efficace.

Il possède un état interne (secret) :

  • une permutation S de tous les 256 octets possibles
  • deux pointeurs i et j de 8 bits qui servent d'index dans un tableau

La permutation est initialisée au moyen d'une clef de taille variable (40 à 256 bits)

In [1]:
# Initialisation
K = map(ord, 'password') # une clef de 64 bits
S = list(xrange(256))
j = 0
for i in xrange(256):
    j = (j + S[i] + K[i % len(K)]) % 256
    S[i], S[j] = S[j], S[i]
In [2]:
# Etat interne initial
for x in S: print x,
76 210 71 79 134 51 36 8 184 37 238 185 239 107 61 114 222 80 213 215 230 106 242 13 96 45 252 138 142 221 70 187 34 205 226 248 117 113 211 39 208 78 14 64 44 57 0 2 86 196 33 97 4 194 32 172 147 195 90 3 72 188 151 206 234 135 140 247 228 102 93 128 136 5 163 21 249 92 81 189 59 47 91 35 46 104 150 42 236 214 63 162 30 95 224 121 9 89 131 25 180 253 207 154 139 10 27 109 19 250 66 190 99 12 212 122 245 158 53 129 84 120 55 243 68 1 146 123 149 157 153 54 219 174 77 144 28 220 62 125 75 29 199 127 18 22 169 170 179 132 31 200 38 67 209 223 165 116 155 16 156 52 203 101 227 83 241 26 160 118 175 50 20 119 182 181 87 197 73 133 237 186 126 201 40 108 6 233 183 60 198 48 11 141 145 69 166 216 105 193 65 231 178 192 229 225 218 232 49 43 15 161 94 254 177 82 23 110 56 251 240 168 176 58 152 255 98 191 171 41 115 235 111 159 244 24 148 202 164 103 74 143 85 204 137 88 17 130 217 167 124 246 112 173 7 100

In [3]:
# Flux pseudo-aléatoire de N octets

def flux(N):
    res = []
    i = j = 0
    for k in range(N):
        i = (i+1) & 0xff         # i+1 % 256
        j = (j+S[i]) & 0xff      # aussi % 256
        S[i], S[j] = S[j], S[i]
        res.append(S[(S[i]+S[j]) & 0xff])
    return res
    
for x in flux(30): print x,
    
255 245 56 14 76 62 180 174 97 81 171 124 50 75 175 102 221 1 166 201 79 139 38 1 114 76 59 144 107 106

RC4 est une marque déposée de RSA security, dont les spécifications n'ont jamais été publiées. Il a cependant fait l'objet d'une rétro-ingénierie, dont le résultat est connu sous le nom de « ARCFOUR », « ARC4 » ou « Alleged RC4 », voir ici

In [4]:
from Crypto.Cipher import ARC4
In [5]:
r = ARC4.new('password')
m = '\0'*30
for x in map(ord,r.encrypt(m)): print x,
255 245 56 14 76 62 180 174 97 81 171 124 50 75 175 102 221 1 166 201 79 139 38 1 114 76 59 144 107 106

On pourra se reporter à l'article de Wikipedia pour un modèle d'une classe ARC4. Crypto.Cipher est écrit en C.

Le WEP et ses faiblesses

Avec une clef \(k\) et un vecteur d'initialisation \(v\), pour envoyer un message \(M\) de A à B : - calculer une somme de controle (CRC32) \(c(M)\) - le texte clair est \(P = M||c(M)\) - on chiffre avec le flux RC4 : \(C = P\oplus RC4(v,k)\) - on transmet \(C'= v||C\) - pour déchiffrer, on superpose à nouveau le flux

On notera que : - le contrôle d'intégrité ne dépend pas de la clef, et tout le monde peut forger un couple \((M,c(M))\) - Le standard WEP spécifie une clef de 64 bits, 40 pour \(k\) et 24 pour le vecteur d'initialisation - le vecteur d'initialisation est transmis en clair ! - risque de réutilisation du flux : si \(C_1=P_1\oplus RC4(v,k)\) et \(C_2=P_2\oplus RC4(v,k)\), on peut calculer \(C_1\oplus C_2 = P_1\oplus P_2\). - si \(P_1\) est connu, on déchiffre \(P_2\). - si on intercepte \(n\) fois le même flux, même risques qu'avec le many-times pad - le standard recommande de changer IV à chaque paquet, mais ne l'exige pas (!) - un point d'accès actif relayant des paquets de 1500 octets épuise son stock d'IV en une demi-journée - la génération aléatoire des IV peut produire des collisions tous les 5000 paquets (paradoxe des anniversaires) - beaucoup d'implémentations se contentent d'un compteur prédictible

Pour obtenir des couples \((P,C)\) et donc des flux - champs IP prédictibles - envoyer un mail et attendre que l'utilisateur le lise en wifi - envoyer des données au point d'accès et observer leur chiffrement

Attaque par dictionnaire - enregister les flux qu'on a pu obtenir dans une table de hachage avec les IV comme clefs - taille au maximum \(1500\times2^{24} \simeq 24\)GB.

On peut modifier les paquets - \(c(M\oplus D) = c(M)\oplus c(D)\) - l'attaquant peut calculer \(C'\) qui sera déchiffré comme \(M'=M\oplus D\) de son choix

On peut injecter du traffic - la station de base vérifie que les clients connaissent la clef en leur envoyant un challenge et en leur demandant de le chiffrer - si l'attaquant parvient a capturer un couple (challenge, réponse), il peut injecter du traffic, et récuperer d'autres flux.

Compte tenu de toutes ces remarques, diverses attaques ont pu être montées, voir par exemple cet exposé, l'article de Wikipedia, et la suite aircrack-ng.

Autres exemples

Le mode OFB d'un chiffrement par blocs est un chiffrement par flux.

On utilise aussi des registres à décalage linéaires ( LFSR, Linear Feedback Shift Registers). Mathématiquement, un registre à décalage engendre une suite récurrente linéaire modulo 2 : \[u_n = \sum_{k=1}^r a_k u_{n-k}\ \mod 2\] Les valeurs initiales \((u_0,\ldots,u_{r-1})\) de la suite constituent le vecteur d'initialisation, ou graine (seed) du générateur.

L'intérêt des LFSR est qu'ils peuvent être réalisés par des circuits électroniques.

Un LFSR travaillant au niveau des bits est dit en mode Fibonacci.

Les implémentations logicielles travaillent plutôt en mode Galois, c'est à dire sur des octets (les octets peuvent être vus comme des éléments du corps de Galois \({\mathbb F}_{2^8}\).

In [6]:
# Exemple en mode Fibonacci

iv = 0xace1
taps = '11101000000000001'
def fib(taps,iv):
    shifts = [i for i in range(len(taps)) if taps[i]=='1']
    state = iv
    while 1:        
        bit = reduce(lambda x,y:x^y, [state>>s for s in shifts])&1
        state =  (state >> 1) | (bit << 15)
        yield bit
    

f = fib(taps,iv)
print [f.next() for i in range(40)]
[1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1]

In [7]:
hex(int(taps[::-1],2))
Out[7]:
'0x10017'
In [8]:
# Exemple en mode Galois

pol = 0x10017
iv = 0xace1

def gal(pol,iv):
    state = iv
    while 1:
        lsb = state & 1
        state >>=1
        if lsb:
            state ^= pol
        yield state
    
In [9]:
u=gal(pol,iv)
In [10]:
print [u.next() for i in range(20)]
[87655, 109348, 54674, 27337, 79219, 105134, 52567, 91836, 45918, 22959, 76992, 38496, 19248, 9624, 4812, 2406, 1203, 66126, 33063, 82052]

L'algorithme A5/1 utilisé pour chiffrer les communications des téléphones mobiles GSM utilise trois registres à décalage. Cet algorithme a de nombreuses faiblesses, et la NSA peut facilement déchiffrer les communications interceptées. On trouvera ici du code C, et des outils dont je vous laisse deviner la finalité.

Les générateurs pseudo-aléatoires sont aussi utilisés pour engendrer des clefs ou des vecteurs d'initialisation. Récemment, une faiblesse due à l'utilisation d'un graine codée "en dur" (hardcoded) a permis de compromettre de nombreux VPN et routeurs Wifi (WPA2) (DUHK attack).

In [ ]: