A5/1
From Wikipedia, the free encyclopedia
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.
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).
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 :
- tous les registres sont mis à 0
- on effectue 64 cycles pendant lesquels la clé de 64 bits est introduite dans le système
- pour le bit Ki de la clé, on effectue un XOR avec le bit de poids faible de chaque registre
- on décale tous les registres d'un cran
- on effectue 22 cycles pendant lesquels le compteur de blocs (22 bits) est introduit dans le système
- pour le bit Ci du compteur, on effectue un XOR avec le bit de poids faible de chaque registre
- on décale tous les registres d'un cran
