A5/1

A5/1 est un algorithme de chiffrement par flot utilisé dans le cadre des communications GSM. Il produit une suite pseudo-aléatoire avec laquelle on effectue un XOR avec les données. Une autre variante existe, la 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.

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.

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, notamment en Amérique du Nord^{[réf. nécessaire]}. En 1994, l'architecture du A5/1, à l'origine secrète, est publiée. En 1999, les versions 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 à rétroaction linéaire. Ils ont une longueur de 19, 22 et 23 bits. Ces degrés n'ont pas été choisis au hasard : comme les degrés de ces trois registres sont premiers entre eux, la période est égale au produit des périodes des trois registres. Ainsi la période de A5/1 (avant répétition) est de 2^64 bits (2 puissance 64).

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 au moins deux fois). Les registres ayant produit 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 Go 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 Go 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 important, 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.

En décembre 2009, le Chaos Computer Club annonce que le chiffrement du GSM aurait été cassé par Karsten Nohl qui devra faire la démonstration de sa technique en août 2010. Si cette information est confirmée en août 2010, cette technique permettrait d'écouter les conversations chiffrées en A5/1.

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.

Le 13 décembre 2013, le Washington Post révèle que la NSA peut écouter les conversations téléphoniques de GSM, sur la base de documents fournis par Edward Snowden.

Utilisation de A5/1 comme générateur pseudo-aléatoire

Comme les degrés des trois registres à décalage sont premiers entre eux, la période est égale au produit des périodes des trois registres, ce qui représente 2^64 bits (2 puissance 64).

On pourrait penser utiliser A5/1 comme générateur pseudo-aléatoire avec une graine d'initialisation de 64 bits (taille de la clé), mais il n'est pas fiable. Il perd son caractère aléatoire après seulement 8 Mo (qui représente la période du plus grand des trois registres).

Articles connexes

• E0
• RC4