KeeLoq es un cifrado de bloque basado en el componente de software " NLFSR ". NLFSR es un registro de desplazamiento de retroalimentación no lineal. El protocolo de transferencia de comandos unidireccional fue desarrollado por Frederic Brouwer, director ejecutivo de Nanoteq Pty Ltd.
El algoritmo criptográfico en sí fue desarrollado a mediados de los años 80 por Gideon Kuhn con una implementación de silicio de Willem Smith en Nanoteq Pty Ltd (una división de Sudáfrica) y fue vendido a Microchip Technology , Inc. en 1995 por $10 millones. El algoritmo es un "código flotante", codificado y decodificado utilizando chips NTQ105/106/115/125D/129D y HCS2XX/3XX/4XX/5XX. KeeLoq se utiliza en la mayoría de los sistemas de control remoto de cerraduras de Chrysler , Daewoo , Fiat , General Motors , Honda , Toyota , Volvo , Volkswagen Group , Clifford , Shurlok , Jaguar .
El cifrado se produce en bloques de 32 bits utilizando una clave de 64 bits, un bloque de texto se cifra en 528 rondas. La función NLF es una retroalimentación no lineal que toma el valor 0x3A5C742E o F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ace ⊕ abd ⊕ a B C. El algoritmo usa los bits 1, 9, 20, 26 y 31 de NLFSR para la salida durante el cifrado y los bits 0, 8, 19, 25 y 30 durante el descifrado. La salida se somete a XOR con dos de los bits de estado de NLFSR (bits 0 y 16 en el cifrado y bits 31 y 15 en el descifrado) y con un bit de clave (bit 0 del estado de la clave en el cifrado y bit 15 del estado de la clave en el descifrado) y esta operación retroalimentaba el estado NLFSR en cada ronda.
NLF 0x3A5C742E - función de retroalimentación, F
F(a,b,c,d,e) = d⊕e⊕ac⊕ae⊕bc⊕be⊕cd⊕de⊕ade⊕ace⊕abd⊕abc
Retroalimentación:
𝜑=𝐹(𝑦 𝑖 31,𝑦 𝑖 26,𝑦 𝑖 20,𝑦 𝑖 9,𝑦 𝑖 1)⊕𝑦 𝑖 16 ⊕ 𝑦 𝑖 0 ⊕𝑘 𝑖 0
Texto: 𝑅 𝑖+1 =(𝜑,𝑦 𝑖 31 ,…,𝑦 𝑖 1 )
Clave: 𝐾 𝑖+1 =(𝑘 𝑖 0,𝑘 𝑖 63,…,𝑘 𝑖 1)
Comentarios : _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Texto: 𝑅 𝑖+1 =(𝑦 𝑖 30,…,𝑦 𝑖 0,𝜑)
Clave: 𝐾 𝑖+1 =(𝑘 𝑖 62,…,𝑘 𝑖 0,𝑘 𝑖 63)
Aquí se describen ejemplos de la implementación del algoritmo en C.
Cifrado:
# define KeeLoq_NLF 0x3A5C742E # define bit(x,n) (((x)>>(n))&1) # define g5(x,a,b,c,d,e) (bit(x,a)+bit (x,b)*2+bit(x,c)*4+bit(x,d)*8+bit(x,e)*16) u32 KeeLoq_Encrypt ( datos const u32 , clave const u64 ){ u32 x = datos , r ; para ( r = 0 ; r < 528 ; r ++ ) x = ( x >> 1 ) ^ (( bit ( x , 0 ) ^ bit ( x , 16 ) ^ ( u32 ) bit ( tecla , r & 63 ) ^ bit ( KeeLoq_NLF , g5 ( x , 1 , 9 , 20 , 26 , 31 ))) << 31 ); devuelve x ; }Descifrado:
u32 KeeLoq_Decrypt ( datos const u32 , clave const u64 ){ u32 x = datos , r ; para ( r = 0 ; r < 528 ; r ++ ) x = ( x << 1 ) ^ bit ( x , 31 ) ^ bit ( x , 15 ) ^ ( u32 ) bit ( clave ,( 15 - r ) & 63 ) ^ bit ( KeeLoq_NLF , g5 ( x , 0 , 8 , 19 , 25 , 30 )); devuelve x ; }KeeLoq fue analizado por primera vez por Andrey Bogdanov, quien utilizó el método del promedio móvil y aproximaciones lineales efectivas. Nicholas Courtois atacó a KeeLoq usando una media móvil y métodos algebraicos. Los ataques de Bogdanov y Courtois no representaron una amenaza para las implementaciones actuales del algoritmo, que probablemente sean más vulnerables a la fuerza bruta del espacio clave. Una implementación separada de "código flotante" también suele ser vulnerable a un ataque de repetición que interfiere con el canal, interrumpe y secuestra el código en sí, y aumenta aún más el tiempo de ejecución en 4 veces el tiempo estándar. Esta vulnerabilidad de KeeLoq permitió la creación de los llamados "grabbers", populares entre los secuestradores, que usan chips FPGA para enumerar la clave principal de KeeLoq.
En 2007, investigadores del grupo COSIC de la Universidad de Lovaina ( Bélgica ), en colaboración con colegas de Israel, descubrieron una nueva forma de atacar el sistema [1] . Usando detalles del algoritmo que se filtraron al público en general en 2006, los investigadores comenzaron a estudiar las vulnerabilidades del algoritmo. Después de determinar la parte de la llave que es responsable de ciertos modelos de automóviles, la parte única de la llave se puede descifrar al interceptar la sincronización de la llave y el automóvil.
Hay cuatro formas de atacar el cifrado KeeLoq: ataque deslizante, enfoque de correlación, paso de línea y ataque de canal lateral .
Este tipo de ataque fue propuesto por primera vez por [D. Wagner] (David Wagner) y [A. Biryukov] (Alex Biryukov). Se aplica principalmente a los códigos de múltiples rondas, cada una de las cuales es una transformación simple del bloque original usando solo una clave. La clave puede repetirse o ser diferente para cada ronda. Lo importante es que las vueltas sean idénticas y fácilmente reversibles.
En la primera etapa, es necesario marcar alrededor de 2 𝑛/2 (donde n es la longitud de la clave adivinada en bits) pares de texto cifrado simple. Esto resulta ser suficiente, según la paradoja del cumpleaños, para tropezar con “pares de diapositivas” con una probabilidad significativa.
Además, (M,C) es uno de esos pares. F es la función de transformación redonda. La esencia del método: si (M',C') es tal que P'= F(K,M) y C'= F(K,C), entonces K es la clave deseada.
Para Keeloq, los primeros 32 bits son reversibles. Por lo tanto, la parte clave (<=32b) se puede determinar de esta manera.
Para definir aún más la clave, puede utilizar la propiedad NLF-Cor(F)=1.
Resulta que para 𝑥2,𝑥3,𝑥4 distribuidos uniformemente se cumple lo siguiente:
– Pr {NLF(𝑥4, 𝑥3, 𝑥2, 𝑥1, 𝑥0) = 0 | 𝑥0 ⊕ 𝑥1 = 0} = 5/8
– Pr {NLF(𝑥4, 𝑥3, 𝑥2, 𝑥1, 𝑥0) = 1 | 𝑥0 ⊕ 𝑥1 = 1} = 5/8
Usando esto y aproximando el NLF en términos de probabilidad, se puede lograr la determinación de la siguiente parte de la clave.
Los últimos 16 bits de la clave se determinan de forma bastante sencilla si se conocen todos los anteriores. Basado en el hecho de que si conocemos el 48 estado completo en el ciclo , entonces podemos escribir : 48 16⊕𝑘48
Desde aquí encontramos - 𝑘48. Completamente similar a 𝑘49…𝑘63
Andrey Bogdanov estima la complejidad de los tres ataques juntos en ~2 52
En marzo de 2008, investigadores del Departamento de Embedded Security de la Ruhr University en Bochum ( Alemania ) presentaron un truco completo de control remoto de llaves basado en la tecnología KeeLoq RFID . Su ataque funciona en todos los vehículos conocidos y sistemas de distribución de control de acceso que utilizan el cifrado Keeloq. El ataque de Bochum permite la recuperación de claves criptográficas secretas incrustadas tanto en el receptor como en el mando a distancia . Su método se basa en administrar el consumo de energía del dispositivo durante el cifrado. Usando el llamado "ataque de canal lateral" en la distribución de energía, los investigadores pueden extraer la clave correcta de los fabricantes de receptores, que se puede usar como una "clave maestra" para generar la clave correcta para el control remoto de un fabricante específico.
A diferencia de los ataques criptográficos descritos anteriormente, que requieren fuerza bruta del orden de 65536 pares de cifrado de texto y varios días de computación en una computadora personal para recuperar la clave, se puede aplicar un ataque de canal lateral al llamado KeeLoq "flotante". modo de código", que es ampliamente utilizado para sistemas de "llave remota" (garajes, automóviles).
La consecuencia más grave de un ataque de canal lateral es que un atacante, habiendo aprendido previamente la clave maestra del sistema, puede copiar cualquier codificador legítimo e interceptar solo los dos mensajes necesarios de ese sensor a una distancia de 100 metros. Otro ataque permite restablecer el contador interno del receptor (puerta del garaje, puerta del automóvil), lo que imposibilita que los usuarios legítimos abran las puertas.
El microchip, basado en KeeLoq IC, introducido en 1996, utiliza un desplazamiento de inicio de 60 bits. Si se utiliza un desplazamiento de inicio de 60 bits, el atacante necesitará aproximadamente 100 días para procesar en un equipo especial para "fuerza bruta" antes de que el sistema sea pirateado.