Cripto Serie: Mifare Crypto1

Seifreed · 12-Oct-2009, 09:54

Volvamos a la Criptografía. En esta ocasión os voy a contar cómo funciona el famoso cifrado Crypto1 incorporado en las Mifare Classic, unas tarjetas RFID utilizadas típicamente para acceso a edificios pero también para muchos otros sistemas: Oyster Card en Londres, OV-Chipkaart en Holanda, etc.
No hablaremos de los detalles del protocolo en sí, ni de cómo funcionan los ataques publicados, aunque al final del post tenéis un par de enlaces interesantes al respecto

.
Nota: Imágenes obtenidas de los papers enlazados al final del post.
El cifrado Crypto1
El cifrado Crypto1 es un cifrado de flujo propietario de NXP que se encuentra en los tags RFID del tipo Mifare Classic. En primera instancia, el cifrado fue estudiado por Karsten Nohl realizando ingeniería inversa del chip. Esta información fue publicada en el CCC 07, aunque no se publicaron excesivos detalles del cifrado en sí.
Paralelamente, en la Radboud Universiteit de Nijmegen estaba estudiando este tipo de tarjetas y con la ayuda de la información publicada en el CCC llegó a realizar una ingeniería inversa completa sobre el cifrado. Veamos pues cómo funciona.
Crypto1 es un cifrado basado en un LFSR, que utiliza un único LFSR con una función de realimentación lineal y una función de filtro para generar la salida (keystream):

Crypto1 - Estructura general

La estructura del cifrado fue revelada en la presentación del CCC, pero el polinomio generador (la realimentación del LFSR) y la función de filtro no lo fue. El polinomio generador, publicado por Karsten Nohl y otros en Usenix’08, es el siguiente:

$g(x) = x^{48} + x^{43} + x^{39} + x^{38} + x^{36} + x^{34} + x^{33} + x^{31} + x^{29}+x^{24} + x^{23} + x^{21} + x^{19} + x^{13} + x^9 + x^7 + x^6 + x^5 + 1$

Esto significa que los bits 43,39,38…,7,6,5,0 son utilizados para formar el nuevo bit que entrará en el registro. Además de estos bits, se utiliza el bit de entrada y se realiza un XOR de todos para generar el próximo bit del registro. Este polinomio es un polinomio primitivo: irreducible y que genera todos los $2^{48}-1$ estados antes de volver a generar el estado inicial.

Por otra parte, las funciones de filtrado fueron publicadas por la gente de RU Nijmegen en Esorics’08. La siguiente figura muestra dichas funciones de filtro junto con el resto del cifrado.

Crypto1 - Estructura detallada

Cada uno de los números hexadecimales identificando las funciones de filtro debe leerse como un mapa de bits donde el bit más a la izquierda será producido como salida cuando todas las entradas son uno y el bit más a la derecha será la salida cuando todas las entradas son ceros. Por ejemplo, 0×26c7 traducido a binario sería:

0010 0110 1100 0111

Lo que significa que para las entradas (1,1,1,1), (1,1,1,0), (1,1,0,0), (1,0,0,1), (0,1,1,0), (0,1,0,1) y (0,1,0,0) el resultado de la función filtro sería 0 y para el resto de entradas sería 1.

Links

Con esto queda descrito completamente el cifrado Crypto1 utilizado en los chips Mifare Classic. No quiero entrar en más detalles acerca de la estructura del cifrado ni del protocolo utilizado, entre otras cosas porque tampoco lo he analizado a fondo, así que para más información acudid a los siguientes enlaces:
Reverse-Engineering a Cryptographic RFID Tag – Karsten Nohl et al. Usenix’08
Dismantling MIFARE Classic – Flavio D. Garcia et al. (RU Nijmegen). Esorics’08
Lecture on Mifare Classic from HW and OS Security course at RU Nijmegen

Fuente