SET 39 Call For Papers

¿Eres un hacker? Si deseas pasar a formar parte de la historia del hacking hispano, colabora con la próxima edición de SET 39 enviándonos un artículo. No esperes más, esta es tu oportunidad de demostrar lo que sabes. Ayúdanos a construir una revista de hackers para hackers. SET Staff

A5 - Tocado y hundido

      2539

Autor: Falken
-[ 0x08 ]--------------------------------------------------------------------
-[ A5 - TOCADO Y HUNDIDO ]---------------------------------------------------
-[ by Falken ]--------------------------------------------------------SET-14-


                                .o.         oooooooo 
                               .888.       dP""""""" 
                              .8"888.     d88888b.   
                             .8' `888.        `Y88b  
                            .88ooo8888.         ]88  
                           .8'     `888.  o.   .88P  
                          o88o     o8888o `8bd88P'   

                               ___
                                | _  _ _. _| _
                                |(_)(_(_|(_|(_)

                                       \/
                                       /

                              |_    ._  _|o _| _
                              | ||_|| |(_||(_|(_)

                                      by
                                    Falken


INTRODUCCION
-=-=-=-=-=-=

    En SET 13 vimos por encima las medidas de seguridad que se llevan a cabo
en GSM. Repasando un poquito, recordamos que por una parte estan las
medidas de seguridad que identifican al usuario ante la red GSM, para
evitar que este sea suplantado. Y por otra parte, esta la codificacion de la
comunicacion, para garantizar la privacidad de la misma.

    Es en esto en lo que nos vamos a centrar.


LA CODIFICACION EN GSM
-=-=-=-=-=-=-=-=-=-=-=

    Existen muchas leyendas sobre los procesos que se siguen en las
comunicaciones moviles para codificar la informacion. Entre ellas podemos
destacar aquellas que afirman que la telefonia analogica usa encriptacion,
cosa que algunos radioaficionados podran demostrar que no es asi. (Erre que
si !! ;) )

    Pero la que mas me gusta de todas es esa que dice que es imposible
desencriptar la informacion codificada en GSM en tiempo real. Acabaramos !!

    A ver... Un poquito de sentido comun. Acaso no lo hacen continuamente
las centralitas GSM? Para ser mas exactos, las BTS. (Sigla definida en
SET 13)

    Claro, que las BTS son muy grandes y muy potentes... Ja! Tambien lo hace
el terminal movil, o que os creiais? 

    En este punto conviene aclarar que la codificacion en GSM se realiza
exclusivamente entre el terminal movil y la BTS, o lo que es lo mismo, en
la interfaz de radio o interfaz Um. Los que dise€aron la red GSM consideraron
que el resto de los elementos de la red no estaban comprometidos en lo que
a seguridad se refiere, pues para interceptarlos seria preciso una
intervencion fisica. Vamos, un pinchazo. Pero un escaner de radio lo puede
tener cualquiera, y ademas, de forma legal. Y no veais lo entretenidas que
son algunas conversaciones de moviles que se pillan de vez en cuando con
estos aparatitos. (No te preocupes... Solo lo sabemos tu, el, y los que
estabamos a la escucha con el escaner ;> )

    Hombre, por algun lado tiene que estar la trampa. Y es que solo ellos
conocian cual era el metodo de encriptacion que se usa en el interfaz Um.
Y digo "conocian", puesto que como vamos a ver seguidamente, esta
informacion va a ser libre... como el ave que escapo de su prision, y puede
al fin volar.... ( :-?! )

    Pues resulta que este metodo es el conocido como algoritmo A5, como ya
deciamos en SET 13. Pero claro, decir que usa el A5 es como decir que usa
DES o IDEA, o incluso PGP. Esto no sirve de nada si no se explica que hay
detras de ese nombre.

    Aun asi, antes de pasar a explicar con detalle el algoritmo A5, vamos
a ver algo de criptografia basica, para que todo se entienda mejor luego.


CRIPTOQUE ?!?!?!
-=-=-=-=-=-=-=-=

    La criptografia, esa ciencia tan maravillosa que nos permite ocultar
la informacion de las formas mas variopintas. Algo tan antiguo como el mundo.
O quizas mas.

    Seguro que todos habeis oido hablar ya del cifrado del Cesar, e incluso
puede que alguno haya leido algo sobre cifradores de bloque, como los usados
en DES. Es evidente que sabeis, al menos por referencia, que es encriptar
algo, porque sino, no estariais leyendo esto.

    Y si todavia os perdeis, pues no teneis mas que pensar que la simple
escritura en un metodo de codificacion, una encriptacion que nos ense€an
desde peque€os para plasmar ideas. Ojala el A5 fuera tan sencillo.

    Pero ni esto es una clase de Lenguaje, ni vamos a extendernos mucho
con la criptografia. Vayamos directamente a lo que influye en el A5, y si
quereis mas criptografia, pues ya sabeis donde pedirla.

    Por un momento nos colocaremos en el lugar de los dise€adores de este
fastuoso sistema criptografico. Pero solo por un momento, eh? Que luego
es dificil volver al estado de locura inicial.

    Resulta que tenemos una comunicacion fluida. Que los interlocutores sean
fluidos (no liquidos, con facilidad de palabra ;> ), o no, eso ya es otra
cosa. Pero lo que nadie me negara es que la informacion desde el mismo
instante en el que se produce la llamada hasta que finaliza no deja de fluir.

    Por otro lado, tenemos unos cuantos metodos de criptografia. Podriamos
usar algo similar al cifrado del Cesar. Pero no, es poco fiable, ademas de
otros problemas a€adidos. Se ven mas claro en el siguiente ejemplo.

    Podriamos usar algun cifrador de bloque... Pero esto implica que
necesitamos un minimo de datos para empezar a encriptar. Y para colmo, ha
de ser un cifrador simetrico.

    Podriamos seguir asi un buen rato, pero seguro que os cansariais rapido
y dejariais de leer estos comentarios.

    Y por fin, podriamos usar algun cifrador de flujo, que va cifrando
segun le llegan datos a codificar.

    Nos hemos dejado atras a metodos como la clave publica, el pago
electronico, etc. Pero sinceramente. Creeis vosotros que tendrian sentido
aqui?

    Ademas, resulta que A5 usa cifradores de flujo, por lo que no hacen falta
mas explicaciones, no?


LINEAR FEEDBACK SHIFT REGISTER
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Esto es lo mismo que: "Registro de desplazamiento con retroalimentacion
lineal" (Joers, que bien se me da el ingles ;> ) O tambien, LFSR para los
amigotes.

    Para empezar, decir que a la hora de usar algun cifrador de flujo, los
basados en registros de desplazamiento se llevan la palma. No en vano son
los empleados por los militares en sus cifradores de flujo desde los
comienzos de la electronica. A esto hay que a€adirle la facilidad de
implementacion con circuitos electronicos simples y la gran velocidad de
cifrado por hardware.

    Un Registro de Desplazamiento no es mas que un registro en el que se
almacena un dato (o no seria registro), y que a cada se€al de reloj, lo
desplaza X posiciones hacia alguno de los extremos, definido de antemano.
Lo mas general es el registro de desplazamiento que a cada ciclo de reloj
desplaza un bit a la derecha, siendo el antiguo bit menos significativo la
salida del registro.

    Un Registro de Desplazamiento con Retroalimentacion consiste de dos
partes. Por un lado tenemos la funcion de Retroalimentacion, que tomando
algunos de los bits del registro como entrada, genera una salida de un bit,
que sera el nuevo bit a la entrada del registro. Llega un momento en el que
la secuencia de salida se repite. La longitud de esta secuencia de salida
hasta el momento en el que empieza a repetirse es lo que se conoce como
periodo del Registro. Aqui teneis un esquemita de un FSR (Feedback Shift
Register):


                 .--------------------------------------. 
          .----> | bn | bn-1 | .... | b4 | b3 | b2 | b1 | -----> 
          |      `--------------------------------------'
          |         |     |            |    |    |    |
          |         |     |            |    |    |    |
          |         v     v            v    v    v    v  
          |      .--------------------------------------.
          `------|     Funcion de Retroalimentacion     |
                 `--------------------------------------'


    La forma mas simple de este tipo de registros en el Registro de
Desplazamiento con Retroalimentacion Lineal o LFSR. En este caso, la funcion
de retroalimentacion es una simple operacion XOR de ciertos bits del
registro. Un ejemplo de este tipo de registros es el siguiente:


                       .-------------------.
                .----> | b4 | b3 | b2 | b1 | ----->
                |      `-------------------'
                |         |             |         Bit de Salida
                |         `----> ^ <----'
                |                |
                `----------------'
                        

    Este es un registro de 4 bits, y se dice que esta bloqueado en su primer
y cuarto bit. En el caso de que el registro fuese inicializado con el valor
0x0F o 1111, obtendriamos los siguientes estados internos:


       1111 - 0111 - 1011 - 0101 - 1010 - 1101 - 0110 - 0011 - 1001
       0100 - 0010 - 0001 - 1000 - 1100 - 1110


    Lo que produciria la siguiente salida: 111101011001000 .... 

    Por simple calculo binario, comprobamos que un LFSR de n bits, puede
pasar por uno de 2^n - 1 estados. Asi, vemos que el maximo periodo de uno
de estos registros es 2^n - 1. Es trivial determinar porque no es 2^n. Tan
simple como que un estado de todos los bits a 0 no cambia.

    Aquellos LFSR que pasan por los 2^n - 1 estados son denominados LFSR de
periodo maximo, y la salida pasa a denominarse secuencia m.

    Esta claro que lo que interesa cuando se cifra algun mensaje es que este
sea lo mas aleatorio posible. QUE NO ?!?!?! Me parece que lo tuyo no es la
criptografia, eh?

    Si se detecta algun patron en el mensaje cifrado, pues nada, ya tenemos
algo por donde atacar a la hora de realizar el criptoanalisis. Pero si esta
secuencia es lo mas aleatoria que se nos ocurra, pues el criptoanalisis se
complica.

    Es por esto por lo que cuando se usa algun cifrador LFSR, siempre se
busca que la salida sea lo mas diferente posible. O lo que es lo mismo, que
el LFSR sea de periodo maximo, tal y como hemos leido hace 4 parrafos.

    Para ver que bits de un registro LFSR de n-bits han de usarse en la
funcion de retroalimentacion con la intencion de conseguir que dicho LFSR
sea de periodo maximo, formamos un polinomio formado por estos bits mas 1.
El grado del polinomio coincidira con la longitud del registro, pues el bit
mas significativo siempre forma parte de los bits seleccionados. A este
conjunto de bits se le denomina secuencia tap. Y lo dejo en tap porque no
me convence niguna de las traducciones de este termino.

    Entonces se dice que el LFSR es de periodo maximo si el polinomio en
cuestion es lo que se llama un polinomio primitivo modulo 2. (TOMA YA !!!)
A estas alturas podria justificarme diciendo que no soy un matematico y que
no puedo explicar esto. Y ademas, quedaria como un se€or. Aun asi, intentare
explicarlo lo mejor posible.

    En general, para un polinomio de grado n, se dice que es primitivo no
cuando va a por la polinomia cachiporra en mano. Se tratara de un polinomio
primitivo cuando sea divisor del polinomio x^(2^n - 1) + 1, y a su vez no lo
sea de x^d + 1 para cualquier d que divida a 2^n - 1.

    Dicho de otra forma, un polinomio es primitivo cuando no es producto de
otros polinomios. Asi, tomando un ejemplo, x^3 + x + 1 es primitivo, mientras
que x^3 + 1 no lo es, puesto que se obtiene de (x + 1) * (x^2 - x + 1).

    La verdad, no es facil generar polinomios primitivos en modulo 2 de un
grado determinado. Es mas, la forma mas facil es coger un polinomio al azar
y comprobar si es o no primitivo.

    Aunque existe otra manera mas facil. Buscarlo en la tabla que viene a
continuacion.


                   .--------------------------------------.
                  {  POLINOMIOS   PRIMITIVOS   MODULO   2  }
                   `--------------------------------------'
   .-----------------.-----------------.-----------------.---------------.
   |            1 0  |         47 5 0  | 88 8 5 4 3 1 0  |     135 11 0  |
   |          2 1 0  |     48 9 7 4 0  |        89 38 0  |     135 16 0  |
   |          3 1 0  | 48 7 5 4 2 1 0  |        89 51 0  |     135 22 0  |
   |          4 1 0  |         49 9 0  |     89 6 5 3 0  |  136 8 3 2 0  |
   |          5 2 0  |     49 6 5 4 0  |     90 5 3 2 0  |     137 21 0  |
   |          6 1 0  |     50 4 3 2 0  |     91 8 5 1 0  |  138 8 7 1 0  |
   |          7 1 0  |     51 6 3 1 0  | 91 7 6 5 3 2 0  |  139 8 5 3 0  |
   |          7 3 0  |         52 3 0  |     92 6 5 2 0  |     140 29 0  |
   |      8 4 3 2 0  |     53 6 2 1 0  |         93 2 0  | 141 13 6 1 0  |
   |          9 4 0  |     54 8 6 3 0  |        94 21 0  |     142 21 0  |
   |         10 3 0  | 54 6 5 4 3 2 0  |     94 6 5 1 0  |  143 5 3 2 0  |
   |         11 2 0  |        55 24 0  |        95 11 0  |  144 7 4 2 0  |
   |     12 6 4 1 0  |     55 6 2 1 0  | 95 6 5 4 2 1 0  |     145 52 0  |
   |     13 4 3 1 0  |     56 7 4 2 0  |    96 10 9 6 0  |     145 69 0  |
   |     14 5 3 1 0  |         57 7 0  | 96 7 6 4 3 2 0  |  146 5 3 2 0  |
   |         15 1 0  |     57 5 3 2 0  |         97 6 0  | 147 11 4 2 0  |
   |     16 5 3 2 0  |        58 19 0  |        98 11 0  |     148 27 0  |
   |         17 3 0  |     58 6 5 1 0  |   98 7 4 3 1 0  | 149 10 9 7 0  |
   |         17 5 0  |     59 7 4 2 0  |     99 7 5 4 0  |     150 53 0  |
   |         17 6 0  | 59 6 5 4 3 1 0  |       100 37 0  |      151 3 0  |
   |         18 7 0  |         60 1 0  |    100 8 7 2 0  |      151 9 0  |
   |     18 5 2 1 0  |     61 5 2 1 0  |    101 7 6 1 0  |     151 15 0  |
   |     19 5 2 1 0  |     62 6 5 3 0  |    102 6 5 3 0  |     151 31 0  |
   |         20 3 0  |         63 1 0  |        103 9 9  |     151 39 0  |
   |         21 2 0  |     64 4 3 1 0  |  104 11 10 1 0  |     151 43 0  |
   |         22 1 0  |        65 18 0  |       105 16 0  |     151 46 0  |
   |         23 5 0  |     65 4 3 1 0  |       106 15 0  |     151 51 0  |
   |     24 4 3 1 0  |     66 9 8 6 0  |    107 9 7 4 0  |     151 63 0  |
   |         25 3 0  | 66 8 6 5 3 2 0  |       108 31 0  |     151 66 0  |
   |     26 6 2 1 0  |     67 5 2 1 0  |    109 5 4 2 0  |     151 67 0  |
   |     27 5 2 1 0  |         68 9 0  |    110 6 4 1 0  |     151 70 0  |
   |         28 3 0  |     68 7 5 1 0  |       111 10 0  |  152 6 3 2 0  |
   |         29 2 0  |     69 6 5 2 0  |       111 49 0  |      153 1 0  |
   |     30 6 4 1 0  |     70 5 3 1 0  |        113 9 0  |      153 8 0  |
   |         31 3 0  |         71 6 0  |       113 15 0  |  154 9 5 1 0  |
   |         31 6 0  |     71 5 3 1 0  |       113 30 0  |  155 7 5 4 0  |
   |         31 7 0  |    72 10 9 3 0  |   114 11 2 1 0  |  156 9 5 3 0  |
   |        31 13 0  | 72 6 4 3 2 1 0  |    115 8 7 5 0  |  157 6 5 2 0  |
   |     32 7 6 2 0  |        73 25 0  |    116 6 5 2 0  |  158 8 6 5 0  |
   | 32 7 5 3 2 1 0  |     73 4 3 2 0  |    117 5 2 1 0  |     159 31 0  |
   |        33 13 0  |     74 7 4 3 0  |       118 33 0  |     159 34 0  |
   |    33 16 4 1 0  |     75 6 3 1 0  |        119 8 0  |     159 40 0  |
   |     34 8 4 3 0  |     76 5 4 2 0  |       119 45 0  |  160 5 3 2 0  |
   | 34 7 6 5 2 1 0  |     77 6 5 2 0  |    120 9 6 2 0  |     161 18 0  |
   |         35 2 0  |     78 7 2 1 0  |       121 18 0  |     161 39 0  |
   |        36 11 0  |         79 9 0  |    122 6 2 1 0  |     161 60 0  |
   | 36 6 5 4 2 1 0  |     79 4 3 2 0  |        123 2 0  |  162 8 7 4 0  |
   |     37 6 4 1 0  |     80 9 4 2 0  |       124 37 0  |  163 7 6 3 0  |
   | 37 5 4 3 2 1 0  | 80 7 5 3 2 1 0  |    125 7 6 5 0  | 164 12 6 5 0  |
   |     38 6 5 1 0  |         81 4 0  |    126 7 4 2 0  |  165 9 8 3 0  |
   |         39 4 0  |     82 9 6 4 0  |        127 1 0  | 166 10 3 2 0  |
   |     40 5 4 3 0  |   82 8 7 6 1 0  |        127 7 0  |      167 6 0  |
   |         41 3 0  |     83 7 4 2 0  |       127 63 0  |     170 23 0  |
   |     42 7 4 3 0  |        84 13 0  |    128 7 2 1 0  |      172 2 0  |
   | 42 5 4 3 2 1 0  | 84 8 7 5 3 1 0  |        129 5 0  |     174 13 0  |
   |     43 6 4 3 0  |     85 8 2 1 0  |        130 3 0  |      175 6 0  |
   |     44 6 5 2 0  |     86 6 5 2 0  |    131 8 3 2 0  |     175 16 0  |
   |     45 4 3 1 0  |        87 13 0  |       132 29 0  |     175 18 0  |
   |     46 8 7 6 0  |     87 7 5 1 0  |      133 9 8 0  |     175 57 0  |
   | 46 8 5 3 2 1 0  |    88 11 9 8 0  |       134 57 0  |      177 8 0  |
   `-----------------^-----------------^-----------------^---------------'


    En esta tabla se encuentran bastantes polinomios primitivos en modulo 2.
Aun asi, existen infinidad de polinomios primitivos en modulo 2. Y por si no
os basta con los que hay en esta tabla, aqui va otra mas... OS PILLE !!

    No es necesario andar con mas tablas. Con la dada hay mas que suficiente,
incluso para obtener otros polinomios primitivos que no esten en la misma.
Solo es necesario saber que si un polinomio p(x) es primitivo, tambien lo
es x^n * p(1/x).

    Por ejemplo, si tenemos el polinomio formado por (4 1 0) como indica en
la tabla, tenemos tambien que es primitivo el polinomio (4 3 0). Y si cogemos
el polinomio (8 4 3 2 0), deducimos que el polinomio (8 6 5 4 0) es primitivo
de la misma forma.

    Matematicamente, para el primer ejemplo, n = 4. Asi, originalmente
tenemos un polinomio x^4 + x + 1. El calculo para el polinomio resultante es
el siguiente:


                      /  1     1       \
               x^4 * (  --- + ---  + 1  )  -->  1 + x^3 + x^4 
                      \ x^4    x       /


    Un ejemplo practico de LFSR, usando la tabla, lo podemos realizar con
el polinomio dado con la entrada de la tabla (32 7 5 3 2 1 0). El polinomio
correspondiente es el siguiente:


                    x^32 + x^7 + x^5  + x^3 + x^2 + x + 1


    De aqui sacamos un LFSR de periodo maximo, cuya longitud es el grado del
polinomio (32). La secuencia de exponentes indica la secuencia de bits o
secuencia tap que sera usada en la funcion de retroalimentacion del registro.
siguiendo con el ejemplo, este seria el LFSR representado de forma grafica:


               .----------------------------------------------. 
        .----> | b32 | ... | b7 | b6 | b5 | b4 | b3 | b2 | b1 | ---->
        |      `----------------------------------------------'
        |         |           `-------. |         |    |    |
        |         `-----------------. | |         |    |    |
        |                           v v v         |    |    |
        |                          .-----. <------'    |    |
        `------------------------- | XOR | <-----------'    | 
                                   `-----' <----------------'


    El codigo fuente en C para este registro seria como sigue:


<++> set_014/a5/lfsr.c
/* Funcion que simula un registro LFSR de 32 bits de periodo maximo
 * SET 14 - Abril 1998
 */

int LFSR () {
        static unsigned long RegDesp = 1;

        /* El registro puede tomar cualquier valor, salvo el 0 
         * pues el resultado seria un flujo de 0 en la salida
         */

        RegDesp = ((((RegDesp >> 31)
                  ^ (RegDesp >> 6)
                  ^ (RegDesp >> 4)
                  ^ (RegDesp >> 2)
                  ^ (RegDesp >> 1)
                  ^ RegDesp))
                  & 0x00000001)
                  << 31)
                  | (RegDesp >> 1);
        return RegDesp & 0x00000001;
}
<-->


    Evidentemente, si usamos un LFSR cuya longitud sea mayor que la palabra
del ordenador, el codigo fuente se complica ligeramente, pues no se puede
trabajar con el registro directamente.

    Ah! Lo de palabra... pues algo asi como byte, pero lo maximo que el
ordenador puede manejar de un solo golpe. Generalmente se habla de palabras
de 16 y 32 bits, aunque tambien las hay de 64 e incluso de 128 bits.

    Un dato mas a tener en cuenta a la hora de realizar un LFSR es lo que
se llama la densidad del polinomio. Un polinomio es denso cuando tiene muchos
coeficientes.

    En si, cuando el polinomio tiene pocos coeficientes, es mas facil de
romper, siguiendo el procedimiento de ataque por correlacion. Asi que cuantos
Mas coeficientes tenga el polinomio, mas dificil es romper la encriptacion.
Pero hay que a€adir un problema mas. La velocidad del programa disminuye a
medida que aumenta el numero de coeficientes, cosa solucionada si los
LFSR se implementan directamente en circuitos del tipo VLSI.

    Aun asi, se ha desarrollado mucho en el campo de la programacion de LFSR,
sobre todo en el ambito militar, pues es donde mas apreciados son los
cifradores de flujo. De hecho existen algunos ordenadores que llevan en su
juego de instrucciones algunas que permiten la implementacion de LFSR
vectorizados directamente en lenguaje maquina. Estos son en su mayoria
ordenadores Cray, como los Cray 1, Cray X-MP y Cray Y-MP.

    Bueno, y eso es todo por hoy.

    Como! Que estabamos hablando del A5 y no he mencionado nada?!?!?! Ups!
Sigamos ;)


Por fin, el A5
-=-=-=-=-=-=-=

    El A5 es el algoritmo de cifrado usado en GSM. Ah! Que ya lo sabiais.
Entonces ya sabreis que se trata tambien de un cifrador de flujo, y que solo
es usado para encriptar la informacion de la interfaz Um o interfaz de radio
entre el movil y la BTS. El resto de la comunicacion se produce en claro, es
decir, sin codificacion de ningun tipo. Para que luego digan que las
operadoras de telefonia movil no pueden espiar tus comunicaciones.

    La historia cuenta como en la fase de desarrollo del GSM hubo un gran
debate politico para decidir si el sistema que se usase para codificar las
comunicaciones deberia ser fuerte o no. Por una parte estaba la opinion de
los alemanes, que querian un sistema robusto, pues estaban muy proximos a
la ex-Union Sovietica. Aun asi, el resto de los paises en el acuerdo no
compartian la misma opinion. Y definitivamente se opto por un sistema frances
que es el que hoy conocemos como A5.

    Durante algun tiempo, se creyo que el algoritmo A5 era muy fuerte.
Posteriormente se demostro que no era asi, e incluso hubo rumores de que se
habia hecho creer que se trataba de un sistema robusto para que Saddam
Hussein comprara los chips A5 en el mercado negro, etc.

    La verdad, estos politicos y militares estan mas paranoicos que todos
nosotros juntos.


Vale, pero... Y el A5?
-=-=-=-=-=-=-=-=-=-=-=

    De acuerdo, pasemos al ataque.

    El A5 se basa en el uso de tres registros LFSR de 19, 22 y 23 bits de
longitud. En esta ocasion, los polinomios correspondientes a los registros
son poco densos, esto es, con pocos coeficientes. La salida del algoritmo
es el resultado hacer un XOR con las salidas de los tres registros.

    Claro, que necesitamos un reloj que indique cuando se debe producir el
desplazamiento en cada registro. Asi, cada registro basa su reloj en su
bit central, XOReado con el inverso de la funcion de umbral de los bits
centrales de los tres registros. (Aireeee!) De esta forma, lo mas normal es
que dos de los tres registros realicen el desplazamiento en cada ciclo.

    De los tres registros, solo se sabe con certeza el polinomio del registro
de 19 bits. Los polinomios de los otros dos registros se suponen, aunque no
han sido confirmados... por el momento. Estos son los polinomios:


                          x^19 + x^5 + x^2 + x + 1
                          x^22 + x^9 + x^5 + x + 1
                          x^23 + x^5 + x^4 + x + 1


OK. Tengo el A5, y ahora, que?
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Bueno, no lo tenemos todo todavia. Aun falta saber como se codifica la
informacion que se transmiten por el interfaz Um.

    Un detalle que no se os deberia haber pasado por alto es que cada movil,
o bien usa un polinomio distinto (ein?!?), o bien el A5 necesita algo asi
como unos parametros de entrada que son exclusivos del movil.

    A ver, los que se decanten por la primera opcion, que levanten la mano.
Nadie!?!? Espera... Me parece ver... Si, alli al fondo!! Alguien ha levantado
la mano!! No puede ser. La documentacion, por favor. AArrgghh!! Una foto de
Mr. Gates y otra de Villa... Quien ha dejado pasar a este espia ???

    Por donde iba. A, si. Continuemos.

    Como hemos visto, el A5 necesita algunos datos de entrada, que si sois
fieles seguidores de esta ezine, recordareis haber leido por algun sitio del
pasado numero.

    En SET 13 os adelantabamos que el A5 usa una clave, Kc, y el numero de
trama TDMA correspondiente a la trama donde van los datos a cifrar. Para
aquellos que no lo recordais del todo, una trama TDMA presenta la siguiente
estrcutura:


                   +---+----+---+----+---+----+---+------+
                   | 3 | 57 | 1 | 26 | 1 | 57 | 3 | 8.25 |
                   +---+----+---+----+---+----+---+------+
       Tail bits <---+   |    |   |    |    |   |     +-----> Guard bits
       Data bits <-------+    |   |    |    |   +-----------> Tail bits
   Stealing bits <------------+   |    |    +---------------> Data bits
   Training bits <----------------+    +--------------------> Stealing bits


    Aqui observamos la presencia de dos campos de 57 bits que se corresponden
con los datos, y que seran los unicos en ser codificados.

    De SET 12 recordareis que a cada trama TDMA se le asigna un numero, que
puede ir desde el 0 hasta el 2715647. Y una trama TDMA tiene una duracion de
120/26 ms, asi que este valor no se repite hasta pasadas 3h 28m 53s 760ms

    Por su parte, Kc se obtiene de pasar Ki y el numero aleatorio RAND por
el algoritmo A8 (Otro mas). Pero de este no sabemos nada por el momento.
En SET 13 se describe que son Ki y RAND, asi que el que lo quiera saber, ya
sabe. Que releea SET 13, o la baje de alguno de estos sitios.

    Visto esto, vemos que en funcion de el numero de trama TDMA y Kc, el
algoritmo A5 produce una salida, que es XOReada con los 114 bits de datos
de la trama TDMA, de forma que se cifra la informacion.

    La forma para descifrarlo es simple. La BTS tiene tambien Kc y el numero
de trama TDMA, lo unico que tiene que hacer es pasarselos como parametro al
A5, y XORear los datos cifrados. Et voila !


Y ahora que?
-=-=-=-=-=-=

    Pues ahora a disfrutar y cacharrear con el fuente que os dejo aqui.
Simula el A5, teniendole que suministrar la clave de sesion Kc y el texto
a cifrar.


<++> set_014/a5/a5.c
/* Program writen by Mike Roe <mrr@cl.cam.ac.uk>
 * June, 1994
 *
 * Main function coded by Falken
 * April, 1998
 *
 * In writing this program, I've had to guess a few pices of information:
 *
 * 1. Which bits of the key are loaded into which bits of the shift register
 * 2. Which order the frame sequence number is shifted into the SR (MSB
 *    first or LSB first)
 * 3. The position of the feedback taps on R2 and R3 (R1 is known).
 * 4. The position of the clock control taps. These are on the `middle' one,
 *    I've assumed to be 9 on R1, 11 on R2, 11 on R3.
 */

/*
 * Look at the `middle' stage of each of the 3 shift registers.
 * Either 0, 1, 2 or 3 of these 3 taps will be set high.
 * If 0 or 1 or one of them are high, return true. This will cause each of the
 * middle taps to be inverted before being used as a clock control. In all
 * cases either 2 or 3 of the clock enable lines will be active. Thus, at least
 * two shift registers change on every clock-tick and the system never becomes
 * stuck.
 */

#define MAX 15       /* Lenght in bytes of Alice->Bob or Bob->Alice
                      * key stream.
                      */

static int threshold(r1, r2, r3)
unsigned int r1;
unsigned int r2;
unsigned int r3;
{
int total;

  total = (((r1 >>  9) & 0x1) == 1) +
          (((r2 >> 11) & 0x1) == 1) +
          (((r3 >> 11) & 0x1) == 1);

  if (total > 1)
    return (0);
  else
    return (1);
}

unsigned long clock_r1(ctl, r1)
int ctl;
unsigned long r1;
{
unsigned long feedback;

 /*
  * Primitive polynomial x**19 + x**5 + x**2 + x + 1
  */

  ctl ^= ((r1 >> 9) & 0x1);
  if (ctl)
  {
    feedback = (r1 >> 18) ^ (r1 >> 17) ^ (r1 >> 16) ^ (r1 >> 13);
    r1 = (r1 << 1) & 0x7ffff;
    if (feedback & 0x01)
      r1 ^= 0x01;
  }
  return (r1);
}

unsigned long clock_r2(ctl, r2)
int ctl;
unsigned long r2;
{
unsigned long feedback;

  
 /*
  * Primitive polynomial x**22 + x**9 + x**5 + x + 1
  */   

  ctl ^= ((r2 >> 11) & 0x1);
  if (ctl)
  {
    feedback = (r2 >> 21) ^ (r2 >> 20) ^ (r2 >> 16) ^ (r2 >> 12);
    r2 = (r2 << 1) & 0x3fffff;
    if (feedback & 0x01)
      r2 ^= 0x01;
  }
  return (r2);
}

unsigned long clock_r3(ctl, r3)
int ctl;
unsigned long r3;
{
unsigned long feedback;

 /*
  * Primitive polynomial x**23 + x**5 + x**4 + x + 1
  */

  ctl ^= ((r3 >> 11) & 0x1);
  if (ctl)
  {
    feedback = (r3 >> 22) ^ (r3 >> 21) ^ (r3 >> 18) ^ (r3 >> 17);
    r3 = (r3 << 1) & 0x7fffff;
    if (feedback & 0x01)
      r3 ^= 0x01;
  }
  return (r3);
}

int keystream(key, frame, alice, bob)
unsigned char *key;   /* 64 bit session key              */
unsigned long frame;  /* 22 bit frame sequence number    */
unsigned char *alice; /* 114 bit Alice to Bob key stream */
unsigned char *bob;   /* 114 bit Bob to Alice key stream */
{
unsigned long r1;   /* 19 bit shift register */
unsigned long r2;   /* 22 bit shift register */
unsigned long r3;   /* 23 bit shift register */
int i;              /* counter for loops     */
int clock_ctl;      /* xored with clock enable on each shift register */
unsigned char *ptr; /* current position in keystream */
unsigned char byte; /* byte of keystream being assembled */
unsigned int bits;  /* number of bits of keystream in byte */
unsigned int bit;   /* bit output from keystream generator */

  /* Initialise shift registers from session key */

  r1 = (key[0] | (key[1] << 8) | (key[2] << 16) ) & 0x7ffff;
  r2 = ((key[2] >> 3) | (key[3] << 5) | (key[4] << 13) | (key[5] << 21)) & 0x3fffff;
  r3 = ((key[5] >> 1) | (key[6] << 7) | (key[7] << 15) ) & 0x7fffff;


  /* Merge frame sequence number into shift register state, by xor'ing it
   * into the feedback path
   */

  for (i=0;i<22;i++)
  {
    clock_ctl = threshold(r1, r2, r2);
    r1 = clock_r1(clock_ctl, r1);
    r2 = clock_r2(clock_ctl, r2);
    r3 = clock_r3(clock_ctl, r3);
    if (frame & 1)
    {
      r1 ^= 1;
      r2 ^= 1;
      r3 ^= 1;
    }
    frame = frame >> 1;
  }

  /* Run shift registers for 100 clock ticks to allow frame number to
   * be diffused into all the bits of the shift registers
   */

  for (i=0;i<100;i++)
  {
    clock_ctl = threshold(r1, r2, r2);
    r1 = clock_r1(clock_ctl, r1);
    r2 = clock_r2(clock_ctl, r2);
    r3 = clock_r3(clock_ctl, r3);
  }

  /* Produce 114 bits of Alice->Bob key stream */

  ptr = alice;
  bits = 0;
  byte = 0;
  for (i=0;i<114;i++)
  {
    clock_ctl = threshold(r1, r2, r2);
    r1 = clock_r1(clock_ctl, r1);
    r2 = clock_r2(clock_ctl, r2);
    r3 = clock_r3(clock_ctl, r3);

    bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01;
    byte = (byte << 1) | bit;
    bits++;
    if (bits == 8)
    {
      *ptr = byte;
      ptr++;
      bits = 0;
      byte = 0;
    }
  }
  if (bits)
    *ptr = byte;

  /* Run shift registers for another 100 bits to hide relationship between
   * Alice->Bob key stream and Bob->Alice key stream.
   */

  for (i=0;i<100;i++)
  {
    clock_ctl = threshold(r1, r2, r2);
    r1 = clock_r1(clock_ctl, r1);
    r2 = clock_r2(clock_ctl, r2);
    r3 = clock_r3(clock_ctl, r3);
  }

  /* Produce 114 bits of Bob->Alice key stream */

  ptr = bob;
  bits = 0;
  byte = 0;
  for (i=0;i<114;i++)
  {
    clock_ctl = threshold(r1, r2, r2);
    r1 = clock_r1(clock_ctl, r1);
    r2 = clock_r2(clock_ctl, r2);
    r3 = clock_r3(clock_ctl, r3);

    bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01;
    byte = (byte << 1) | bit;
    bits++;
    if (bits == 8)
    {
      *ptr = byte;
      ptr++;
      bits = 0;
      byte = 0;
    }
  }
  if (bits)
    *ptr = byte;

  return (0);

}

  /* Main function added by Falken */

void
main (void)
{
unsigned char key[8];       /* 64 bit session key */
unsigned char alice[15];    /* 114 bit Alice to Bob key stream */
unsigned char bob[15];      /* 114 bit Bob to Alice key stream */
unsigned char data[101];     /* 114 bit of data */
unsigned long frame;        /* 22 bit frame sequence number */

int i, ii;   /* counters for loops */
int len;     /* Lenght of data */

  /* Initialise variables */

  for (i = 0; i < 101; i++)
  {
    if (i < 8)
      key[i] = 0x00;
    if (i < MAX)
      alice[i] = bob[i] = 0x00;
    data[i] = 0x00;
  }
  frame = 0;

  printf ("\nA5 - GSM Stream Cipher/Cifrador de Flujo GSM - Version 1.0 - 13/4/1998");
  printf ("\nFirst published in/Publicado por primera vez en: SET 14");
  printf ("\nWritten by/Escrito por: Falken\n\n");

  printf ("---> Clave de sesion : ");
  gets (key);
  printf ("---> Texto a cifrar  : ");
  gets (data);
  printf ("\n*** Texto sin cifrar:\n---> ");
  i = 0;
  len = strlen (data);
  while (i < len)
  {
    if (data[i] < 0x0f)
      printf ("0%x", data[i]);
    else
      printf ("%x", data[i]);
    i++;
  }

  /* Data encryption.
   * Alice sends data to Bob.
   */

  for (i = 0; i <= len / MAX; i++)
  {
    keystream (key, frame, alice, bob);
    for (ii = 0; ii < MAX; ii++)
      data[ii + (i * MAX)] ^= alice[ii];
    frame++;
  }

  printf ("\n*** Texto cifrado:\n---> ");
  i = 0;
  while (i <= (len / MAX + 1) * MAX)
  {
    if (data[i] < 0x0f)
      printf ("0%x", data[i]);
    else
      printf ("%x", data[i]);
    i++;
  }

  printf ("\n\n... Pulsa una tecla para descifrar ...");
  getch();

  /* Data decryption */

  frame = 0;
  for (i = 0; i <= len / MAX; i++)
  {
    keystream (key, frame, alice, bob);
    for (ii = 0; ii < MAX; ii++)
      data[ii + (i * MAX)] ^= alice[ii];
    frame++;
  }

  printf ("\n\n*** Texto descifrado:\n---> ");
  i = 0;
  while (i < len)
  {
    if (data[i] < 0x0f)
      printf ("0%x", data[i]);
    else
      printf ("%x", data[i]);
    i++;
  }
}
<-->


ANEXO: De como por la boca muere el pez
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

    La verdad es que se ha visto que el A5 es un algoritmo bastante simplon,
facil de romper mediante un maximo de 2^40 cifrados: Se da un valor a los
dos primeros registros y se intenta determinar el tercero mediante la clave
de cifrado o clave de flujo, como seria conveniente llamarla. Esta ultima
clave es la salida del A5.

    Es mas, con un chip Xilinx (De esos que hacen el A5 tan rapidamente)
reprogramado para hacer una busqueda de claves, y un crackeador de A5. Junta
unas pocas docenas con un potencial de busqueda de 2 claves por microsegundo.
Y hoy dia se conocen metodos de ataque bastante buenos y rapidos para los
cifradores de flujo, en especial, el A5, la mayoria basados en los ataques
por correlacion lineal. Para mas info, los boletines Cryptologia.

    El A5 gozo de buena reputacion mientra no fue conocido. Toda la seguridad
que daba, se basaba en el desconocimiento generalizado por parte del publico
en general del algoritmo en si.

    Pero hace unos a€itos, una compa€ia telefonica britanica (me abstengo de
decir nombres) dio esta documentacion a la Universidad de Bradford, sin
imponerles un acuerdo de no distribucion. Asi que con el tiempo, acabaron
apareciendo descripciones del A5 por todas partes, incluso fuentes de
cifradores A5.

    Y es que parece que todavia no les ha entrado en la cabeza que la
seguridad no se basa en el secretismo sobre el metodo de cifrado, si este
es bueno. Y si no, miren al PGP. La seguridad ha de basarse en el compromiso
de la clave, y nada mas.

    Claro, que el A5 goza de una gran ventaja. Que alguien intente descifrar
una comunicacion movil GSM en tiempo real. Si, de esas del estilo de: "En
la pizzeria, a las 20:00". Y es que con lo que cuestan las llamadas, a ver
quien es el guapo que habla mas tiempo. ;)


That's all folks !
Falken <falken@latinmail.com>