Método y aparato para la configuración IV no lineal en generadores de secuencia de clave.

Metodo para realizar una "etapa de configuracion de desafio lector en una fase de autenticación",

de acuerdo con un protocolo de autenticación y cifrado MIFAREO utilizando cifrado CRYPT0-1, en un "dispositivo de etiqueta", en donde, el tame° de un estado interno de cifrado, llamado "ST" es de 6 bytes , en el tiempo t, el estado interno de cifrado esta representado por STt ≥ (STt[0],..., STi[5]), un desafio lector (28), llamado "RC", de longitud de 4 bytes, se indica por: RC ≥ (RC[0], RC[3]) una función lineal "LF" que realiza una funcion de retroalimentación lineal de un registro de desplazamiento de retroalimentación lineal cifrado CRYPTO-1 Mifare© , y una funcion no lineal, "NLF", realizando un generador de filtro de dos capas cifrado CRYPT0-1 Mifare© utilizando dos funciones de filtrado Ga y Gb, para actualizar el valor de dicho ST usando dicho RC, caracterizado porque dicho método comprende al menos las siguientes etapas:

- creación de cuatro tablas f1i, f1 p, f2i, f2p

- desde un estado inicial de dicha etapa de configuración del desafio lector indicado como STto, los sucesivos estados STt0+8, STt0+24, STto+32 se calculan mediante el calculo byte por byte de un valor de retroalimentación lineal utilizando dicha funcion LF

- insertando byte por byte dicha "RC" en la mencionada ST utilizando dicha función NLF, calculandose los bytes de entrada de Ga y Gb utilizando bits de ST y las cuatro tablas f1i, lip, 121, f2p.

Método y aparato para la configuración IV no lineal en generadores de secuencia de clave.

La invención se refiere a un método y un aparato para la configuración IV no lineal en los generadores de corriente de clave.

Más precisamente. la invención describe la implementación de software eficiente de un cifrado de flujo orientado al hardware.

La invención se refiere a la tecnología MIFARE sin contacto utilizada dentro de las redes de transporte público para aplicaciones de gestión de venta de entradas y acceso.

En la siguiente descripción. se utilizarán algunas funciones lineales. Las funciones lineales se pueden implementar 15 utilizando tablas y las tablas definen fácilmente las correspondiente funciones lineales. "Función lineal" y "tablas" se utilizarán de igual manera.

El principal bloque de construcción criptográfica de MIFARE es un cifrado de flujo llamado CRYPTO-1. La estructura general de CRYPTO-1 se puede esbozar tal como sigue:

1) Un registro de desplazamiento de estado de 48 bits indicado (en el tiempo t>O) por STt = (st. .... st+47) . con si ? {0.1}. i~O.

2) Una función configuración de clave 3) Una función de configuración de IV

4) Una función de generación de flujo de claves 3 O La parte más crítica del cifrado de flujo CRYPTO-1 con respecto a las actuaciones de implementación de software es la función de configuración de IV. la cual es una función no lineal. Para la fase de configuración de IV. los sucesivos bits de realimentación no lineales utilizados para actualizar el registro de desplazamiento se calculan. para cada uno. como una función no lineal del estado anterior incluyendo los bits de realimentación anteriores.

Dejemos que STtO = (stO..... stO+47) sea el estado del cifrado antes de realizar la función de configuración de IV (suponemos que la función de configuración de clave ha sido ya realizada) . El estado STtO será actualizado mediante el uso de una función boolena no lineal nlf y una IV de 32 bits = (IVO..... IV31) inyectada bit a bit en el estado de la siguiente manera:

O PARA i = O a 31 HACER

stO+48+i = nfl (stO+i..... stO+47+i. IVi)

STtO+i+1 = (stO+i+1 ..... stO+i+48) .

Después de la inyección de un IV de 32 bits en STtO. el nuevo estado del cifrado es STtO+32 = (stO+32..... stO+79) . Ahora. el cifrado está listo para generar un flujo de clave. por ejemplo para completar el protocolo de autenticación Mifare.

O La función nfl "efectivamente" depende sólo de 28 variables (en lugar de 49) . Sin pérdida de generalidad. cualquier función F booleana n-variable puede ser representada utilizando el Formulario Normal Algebraico por:

F (x1 ..... xn) = G (x1 ..... xn) xor L (x1 ..... xn) .

donde L es una función booleana lineal y G (x1 ..... xn ) es una función no lineal. La función nlf cae dentro de una clase particular de funciones booleanas. es decir. funciones booleanas del tipo:

G (x1 ..... xn) =GU (x1 ..... xn-k) x ó GH (xn-k+1 ..... xn) .GV (x1 ..... xn-k) donde k es un entero pequeño en comparación con n.

La función nlf está "orientada al bit". Una implementación directa de nlf hace uso de un gran número de selecciones de bits (básicamente. se puede implementar utilizando un desplazamiento derecha/izquierda y Byte-Y ó Byte-O) . Los valores de bits se combinan a continuación utilizando bit-XO y bit-Y.

Una solución clásica para convertir una implementación orientada a bits en un implementación orientada a bytes es reemplazar selecciones de bits por tablas de consulta y operaciones orientadas a de bits por operaciones orientadas a bytes. Sin embargo, esta solución clásica no se puede aplicar directamente cuando el valor de bit sj se calcula utilizando una función no lineal que no depende linealmente de sj-1 y/o sj-2 y/o ... y/o sj-8.

K. Mayes et al., "The MIFARE Classic storr y " proporcina una visión global de la ta~eta MIFARE® Clásica. 5

w. Teepe, "Making the Best of Mifare Classic" describe contramedidas contra la recuperación y clonado de estado de MIFARE® Clásica.

La invención describe un método para actualizar Un estado inyectando una IV utilizando un registro de 10 desplazamiento de retroalimentación no lineal que únicamente hace uso de mirar arriba tablas y operaciones básicas en palabras de 8 bits.

El tamaño del estado interno del cifrado es N = 8*n. Un valor típico para n es n = 6 ó n = 32. En el tiempo t, el estado interno del cifrado está representado por STt = (STt[O], ..., STt[n-1J) , o equivalentemente por STt = (st, ... , st+8n-1 ) .

Suponemos que una función de configuración de clave se ha realizado en el estado del cifrado (por ejemplo, la clave se ha cargado en el estado) antes de comenzar la fase de configuración de IV. No se hace ninguna suposición sobre la función de configuración de clave.

O Fase de configuración de IV:

Dejemos que STtO = (stO, ... , stO+8n-1) sea el estado inicial del cifrado para la fase de configuración de IV, donde tO> O es un valor predeterminado. Durante esta fase, el estado interno del cifrado se actualiza usando un Valor de Inicialización (IV) de longitud 8*m bits, m>O (un valor típico para m es m = 4, m = 8, m = 12 ó m = 16) . Denotamos los bytes IV por: IV = (IV[O], ..., IV[m-1J) .

El estado final de la fase de configuración de IV es: STtO+8m = (stO+8m, ... , stO+8 (m+n) -1)

Debido a que la fase de configuración de IV no resultaría ser "fácil" de invertir, es decir, conocer el estado final de la fase de configuración de IV, no debería ser fácil recuperar el estado inicial de la fase de configuración de IV, la función utilizada para actualizar el estado durante el fase de instalación de IV es generalmente elegido que no sea lineal.

Actualización No Lineal del Estado (NLF) .

Desde el estado inicial STtO, los estados sucesivos m STtO+8, STtO+16, ... , STtO+8m se calculan mediante la inyección byte por byte de la IV en el estado a través de una función de actualización no lineal denominada 14 O byteNLF.

En el tiempo t = tO, T+1=tO+8, ..., T+m-1 =tO+8* (m-1) , el estado de cifrado SIT+i, Osism-1, es actualizado utilizando IV[i] mediante el cálculo de un valor-byte que es SIT+i+1[n-1]. De hecho, asumiendo que en el tiempo T+i, el estado es:

SIT+i = (SIT+i[O) , SIT+i[1], ... , SIT+i[n-1J)

Entonces, el estado en el tiempo T +i+1 es: 50 SIT+i+1 = (SIT+i[1], SIT+i[2]. .. , SIT+i[n-1], SIT+i+1[n-1J) = (SIT+i+1[0], SIT+i+1[1]. .. , SIT+i+1[n-2], SIT+i+1[n-1]) En otras palabras, SIT+i+1[jJ= SIT+i[j+1], para j=O, ... , n-2, y sólo un valor de un-byte (es decir, SIT+i+1[n-1J) 55 necesita ser calculado. Calculamos este valor de byte mediante una función no lineal denominada 1-byteNLF. La función 1-byteNLF. Esta función hace uso de: 1) La tablas de consulta n de tamaño (8 bits) * (8 bits) indicadas por LFO, LF1, ..., LFn-1 (posiblemente, existe 60 (i, j) , OSi<j<n tales que LFi = LFJ, y/o existe i, Osi<n, tal que LFi = 0) . 2) Las tablas de consulta 2n de tamaño (8 bits) * (4 bits) indicadas por BFIO, BFrO, BF11, BFr1, ... , BFln-1, BFrn1 (posiblemente, existe (i, j) , OSi<j<n tal que BFxi = BFyj donde x, y?{r, I}, y/o existe i, Osi<n, tal que BFxi = 0 donde x ?{r, I}) . En implementaciones particulares es posible utilizar tablas n de tamaño (8 bits) * (8 bits) . Los 2 5

tamar'los de tablas anteriores hablan de tamar'los útiles de tablas. Es posible almacenar una tabla de tamar'lo útil de (8 bits) * (4 bits) , dentro de una tabla de tamar'lo real de (8 bits) * (8 bits) . 3) Dos funciones de filtrado: Ga: {O, 1}A{8*k} -> {0, 1}A8;

Gb: {0, 1}A{8*k} -> {0, 1}A8;

con k tal que 0< k s n -1. Dependiendo de la implementación, los valores de entrada de Ga y Gb son por ejemplo k bytes ejemplo o palabras 1<14 de 32 bits. 4) Una tabla de consulta 10 de tamaño (8 bits) * (8 bits) El cálculo de STT +i+1 [n-1] = (st+8 (n+i-1) , ..., st+8 (n+i) -1) incluye los siguientes pasos: 1) Cálculo de los valores intermedios de 1-byte: (S[T +i], para alguna i, O S i S n-1) representa una selección de 8 bits a partir de dos bytes de S. Xi = BFli [S[T +i]], para alguna i, O S i S n-1 Yi = BFri [S[T +i]], para alguna i, O S i S n-1

2) Cálculo de dos valores de 1-byte U y V: U se calcula utilizando la función Ga, aplicada a 4 bytes. Cada uno de estos bytes se ha calculado utilizando un valor Xi, y un valor Vi. Esto también puede ser descrito de la siguiente manera:

U =Ga (Xi1, ..., Xik, Yi1, ..., Yik') , donde 1 S k, k' S 8*n V se calcula utilizando la función Gb, aplicada a 4 bytes. Cada uno de estos bytes se ha calculado utilizando un valor Xi, y un valor Vi. Esto también puede ser descrito... [Seguir leyendo]

1. Método para realizar una "etapa de configuración de desafío lector en una fase de autenticación", de acuerdo con un protocolo de autenticación y cifrado MIFARE© utilizando cifrado CRYPTO-1, en un "dispositivo de etiqueta", 5 en donde, el tamaño de un estado interno de cifrado, llamado "ST" es de 6 bytes, en el tiempo t, el estado interno de cifrado está representado por STt = (STt[O], ... , STt[5]) , un desafio lector (28) , llamado "RC", de longitud de 4 bytes, se indica por: RC = (RC[O], ... , RC[3]) una función lineal "LF" que realiza una función de retroalimentación lineal de un registro de desplazamiento de retroalimentación lineal cifrado CRYPTO-1 Mifare©, y una función no lineal, "NLF", realizando un generador de filtro de dos capas cifrado CRYPTO-1 Mifare© utilizando dos funciones de filtrado Ga y

Gb, para actualizar el valor de dicho ST usando dicho RC, caracterizado porque dicho método comprende al menos las siguientes etapas:

-creación de cuatro tablas f1 i, f1 p, f2i, f2p

-desde un estado inicial de dicha etapa de configuración del desafio lector indicado como STta, los sucesivos estados STto+8, STtO+16, STtO+24, STtO+32 se calculan mediante el cálculo byte por byte de un valor de retroalimentación lineal utilizando dicha función LF

-insertando byte por byte dicha "RC" en la mencionada ST utilizando dicha función NLF, calculándose los 2 O bytes de entrada de Ga y Gb utilizando bits de ST y las cuatro tablas f1 i, f1 p, f2i, f2p.

2. Método según la reivindicación 1, caracterizado porque dicho método comprende una etapa preliminar de disposición de bits "ST" en un byte para almacenar, en un nibble los bits con rango par, y en el otro nibble los bits con rango impar.

3. Método según la reivindicación 1 o la reivindicación 2, caracterizado porque dicha función de retroalimentación lineal se define utilizando 6 tablas pre-calculadas de 8 bits x 8 bits Lo, ... , L5 tal que:

LF (ST 8t+; [O], ... , ST8t+; [5]) =Ls [ST8t+; [5]] 0~[ST8t+; [4]]0 ... 0 Lo [ST8t+; [O]] 30

4. Método según la reivindicación 3, caracterizado porque, dicha función "NLF" se define por:

5 Un registro de tamaño de 8 bits, llamado "Bufr', que se ha inicializado o actualizado utilizando la función lineal LF aplicada en ST y la tabla 10 se calcula para un byte de RC

Cuatro tablas pre-calculadas de 8 bits x 8 bits f1 i, f1 p, f2i, f2p aplicadas en el estado ST

O una función "Ga", aplicada en cuatro valores de bytes "a", "b", "e" y "d" Yque produce un valor de un byte, tal que:

Ga (a, b, c, d) =« (a" d) & (a " b" (b &e) ) ) " OxFF" d)

una función "Gb", aplicada en cuatro valores de bytes "a", "b", "e" y "d" Yque produce un valor de un byte, tal como:

Gb (a, b, e, d) = «a" (b &d» & (e " a) " (a &d»

O una función "G" que recibe las salidas de dichas funciones Ga, Gb y valores de dos bytes, indicados por U y V que se inicializan con bits de dicho ST y, valores de dos bytes, indicados por UU y W que se inicializan con bits de dicho ST y posiblemente, con bits de dicho registro Buff, dichos valores UU y W se actualizan utilizando 8 pasos antes de la actualización final de dicho registro Buff y el citado registro Buff.

cuando todos los bits de dicho registro Buff se han calculado, el primer byte de dicho ST es borrado, todos los demás bytes se desplazan a la izquierda, y el registro Buff se inserta como sexto rango.

5. Método según la reivindicación 4, caracterizado porque, dicho registro de "Bufr' contiene el byte actual de dicho RC para calcular, mediante el modo XOR con el byte proporcionado por la citada función lineal "LF".