-[ 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 * 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