A5/1

Pour les articles homonymes, voir A5.

Schéma du A5/1 et ses trois registres à décalage. Un registre est décalé si le bit en orange correspond à la majorité des trois bits orange. On insère alors un bit correspondant à un XOR entre les bits en bleu.

A5/1 est un algorithme de chiffrement par flot utilisé dans le cadre des communications GSM. Il génère une suite pseudo-aléatoire avec laquelle on effectue un XOR avec les données. Plusieurs variantes existent : A5/1, A5/2. On trouve aussi le terme de A5/3 (KASUMI) bien que ce dernier ne soit pas un algorithme de chiffrement par flot mais de bloc.

L'algorithme A5 utilise une clé de 64 bits mais son implémentation dans le GSM n'utilise que 54 bits effectifs (10 bits sont mis à zéro).

Histoire

La version A5/1 est utilisée en Europe. La version A5/2 est plus vulnérable mais utilisée sur d'autres marchés. En 1994, l'architecture du A5/1, à l'origine secrète, est publiée. En 1999, les version 1 et 2 sont complètement spécifiées après de l'ingénierie inverse effectuée par Marc Briceno à partir d'un téléphone GSM. En 2000, on comptait environ 130 millions d'utilisateurs du GSM basé sur A5/1.

Principes

Une conversation GSM s'effectue par division en blocs temporels, chacun dure 4,6 millisecondes et contient 2×114 bits pour les deux canaux de communication (full-duplex). Une clé de session K est utilisée pour la communication. Pour chaque bloc, K est mélangée à un compteur de blocs et le résultat est utilisé comme état initial d'un générateur de nombres pseudo-aléatoires qui produit 228 bits. Ceux-ci servent au chiffrement après un XOR avec les données des deux canaux.

L'architecture de A5/1 est basée sur trois registres à décalage avec une rétroaction linéaire. Ils ont une longueur de 19, 22 et 23 bits. Pour insérer un nouveau bit dans le registre lors d'un décalage, on effectue pour chaque registre un XOR entre quelques bits déjà présents dans le registre. Les positions des bits utilisés sont constantes.

On récupère ensuite trois bits à des positions fixes, un par registre, avec lesquels on calcule une fonction « majorité » (le bit qui gagne est celui qui apparaît deux fois). Les deux registres ayant produits le bit qui a emporté la majorité sont alors décalés. La véritable sortie du générateur est un XOR entre les bits qui sont en tête de chaque registre.

Pour initialiser le système avec la clé de 64 bits et le compteur initial de 22 bits, on procède comme suit :

1. tous les registres sont mis à 0
2. on effectue 64 cycles pendant lesquels la clé de 64 bits est introduite dans le système
   1. pour le bit K_i de la clé, on effectue un XOR avec le bit de poids faible de chaque registre
   2. on décale tous les registres d'un cran
3. on effectue 22 cycles pendant lesquels le compteur de blocs (22 bits) est introduit dans le système
   1. pour le bit C_i du compteur, on effectue un XOR avec le bit de poids faible de chaque registre
   2. on décale tous les registres d'un cran

Attaques et vulnérabilités

Plusieurs attaques sur A5/1 ont été publiées. Certaines nécessitent un traitement préalable avec lequel on peut attaquer le chiffrement en quelques minutes.

Attaques à texte clair connu

En 1997, Golic présente une attaque basée sur la résolution d'un système d'équations linéaires. Son attaque a une complexité de 2^40.16 (nombre de solutions nécessaires pour résoudre le système).

En 2000, Alex Biryukov, Adi Shamir et David Wagner montrent que A5/1 peut être cryptanalysé en temps réel en utilisant une attaque avec un compromis temps-mémoire. Il est possible de retrouver la clé en quelques minutes à condition de disposer de deux minutes de communication en clair. Un calcul de 2⁴⁸ étapes est nécessaire alors pour préparer l'attaque (soit 300 GB de données).

La même année, Eli Biham et Orr Dunkelman publient une attaque avec une complexité de l'ordre de 2^39.91 itérations du générateur de nombres pseudo-aléatoires avec toutefois l'obligation de disposer de 2^20.8 bits de données non-chiffrées. L'attaque nécessite 32 GB et un précalcul de 2³⁸ opérations.

En 2003, Ekdahl et Johannson présentent une attaque sur l'initialisation de A5/1. En quelques minutes, il est possible de le casser en utilisant 5 minutes de conversation en clair. Avantage de taille, il n'est pas nécessaire de calculer une immense table au préalable. En 2004, Maximov et son équipe améliorent ce principe avec une minute de calcul et quelques secondes de conversation en clair.

Attaque sur des données chiffrées

En 2003, Barkan, Biham & Keller publient plusieurs attaques sur le système GSM. La première est active en forçant l'utilisation d'un chiffrement A5/2. Une fois cassé, le A5/2 fournit la clé qui est la même pour A5/1. Une autre attaque basée sur un compromis temps-mémoire est donnée et n'utilise pas de données en clair. Elle nécessite toutefois une grosse puissance pour précalculer la table.

Voir aussi

• E0
• RC4

• Portail de la cryptologie