A5/1

A5/1

Page d'aide sur l'homonymie 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).

Sommaire

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 Ki 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 Ci 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 240.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 248 é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 239.91 itérations du générateur de nombres pseudo-aléatoires avec toutefois l'obligation de disposer de 220.8 bits de données non-chiffrées. L'attaque nécessite 32 GB et un précalcul de 238 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

  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « A5/1 ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article A5/1 de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • A5/1 — is a stream cipher used to provide over the air communication privacy in the GSM cellular telephone standard. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the… …   Wikipedia

  • A5/1 — es un algoritmo cifrador de flujo usado para proporcionar privacidad en la comunicación al aire libre en el estándar GSM, es decir, el algoritmo que cifra la conversación entre 2 terminales GSM cuando el mensaje viaja por el aire. Inicialmente… …   Wikipedia Español

  • A5 (Algorithmus) — A5 ist ein Satz von Chiffren zur Sicherung der Kommunikation in Mobilfunknetzen nach dem GSM Standard. Der Standard definiert drei Chiffren. Inhaltsverzeichnis 1 A5/1 2 A5/2 3 A5/3 4 Weblinks …   Deutsch Wikipedia

  • A5 — is commonly used to refer to an ISO 216 international standard paper size, measuring (148×210 mm).A5, A05, A 5, A V or A 5 may refer to: * A5, a German rocket design in World War II * A5 band (Apple 5), a Chinese band of 5 boys born in 1980s: Qu… …   Wikipedia

  • A5 — steht für: A5 (Algorithmus) (Stromchiffre A5/1 bzw. A5/2, Blockchiffre A5/3), Verschlüsselungsstandard in GSM Mobilfunknetzen A5 (Rakete), Raketenprojekt im nationalsozialistischen Deutschland Airlinair, französische Fluggesellschaft (IATA Code)… …   Deutsch Wikipedia

  • A5/2 — is a stream cipher used to provide voice privacy in the GSM cellular telephone protocol.The cipher is based around a combination of four linear feedback shift registers with irregular clocking and a non linear combiner.In 1999, Ian Goldberg and… …   Wikipedia

  • A5/2 — est un algorithme de chiffrement par flot utilisé dans le cadre des communications GSM en dehors de l Europe. Il crée une suite pseudo aléatoire avec laquelle on effectue un XOR avec les données. En 1999, Ian Goldberg et David Wagner l ont… …   Wikipédia en Français

  • A5 — puede referirse a: A5 (cohete), cohetes alemanes de 1938. Autostrada A5, una autopista italiana que conecta Turín con el Túnel del Mont Blanc. Línea A5, un servicio regoinal de ferrocarril convencional entre Algeciras y Granada. Audi A5, un… …   Wikipedia Español

  • A5 — У этого термина существуют и другие значения, см. A5 (значения). Предупреждение на экране сотового телефона об отсутствии шифрования на сети …   Википедия

  • A5 — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre > Sigles de deux lettres   Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”