PROCEDIMIENTO DE CONTRAMEDIDA EN UN COMPONENTE ELECTRONICO PARA UN ALGORITMO DE CODIFICACION CON CLAVE SECRETA.

Procedimiento de contramedida que utiliza contra los ataques de tipo DPA una representación aritmética y una representación booleana que consiste en impedir el registro previo del consumo de la corriente generada por manipulaciones de bits por bits permitiendo pasar de manera eficaz de dicha representación boolena de datos,

dicha representación se llama D xor R, o xor designa la operación de tipo O-EXCLUSIVO, hacia dicha representación aritmética de datos, dicha representación se llama D+R, dicho procedimiento utiliza un dato x que debe protegerse, el dato protegido se llama x'' con x=x'' xor r, el entero r es un entero aleatorio, dicho procedimiento permite obtener un valor A tal como x=A+r, dicho procedimiento se caracteriza porque engloba las dos siguientes etapas:

1) 1 Para todos los valores del entero y posibles, generar una tabla T que contenga los valores: T(y)= (y xor r)-r

1) 2 Poner en un entero A el valor de T (x'')

Procedimiento de contramedida en un componente electrónico para un algoritmo de codificación con clave secreta.

La presente invención concierne un procedimiento de contramedida para un algoritmo de codificación con clave secreta.

Se ha puesto de manifiesto que la implementación en tarjeta inteligente de un algoritmo de codificación con clave secreta era vulnerable a ciertos ataques que consisten en un análisis diferencial de consumo de corriente que permite descubrir la clave secreta. Estos ataques se llaman ataques DPA, acrónimo por Differential Power Analysis. El principio de estos ataques DPA se basa en le hecho de que el consumo en corriente del microprocesador que ejecuta instrucciones varía según el dato manipulado.

Existen numerosos algoritmos con clave secreta en los que el algoritmo efectúa manipulaciones bits por bits de un dato que depende del mensaje que debe codificarse.

Por ejemplo, cuando el algoritmo de codificación comprende una permutación de datos, la implementación en tarjeta inteligente de esta permutación hace intervenir manipulaciones bits por bits del dato que debe permutarse.

Al analizar el consumo de corriente durante la ejecución por el microprocesador de estas manipulaciones bits por bits, es posible descubrir una parte o la totalidad del dato manipulado.

El conocimiento de este dato suministra informaciones en los resultados intermedios de la ejecución del algoritmo de codificación, que permiten descubrir la clave secreta de codificación.

En el algoritmo de codificación DES (por DATA Encryption Standard),el algoritmo codifica un mensaje claro de 64 bits en un mensaje codificado de 64 bits con una clave de 64 bits que incluye 8 bits de paridad. El algoritmo DES incluye 16 vueltas.

En cada vuelta, el algoritmo DES efectúa las siguientes manipulaciones:

1) Expansión-permutación con la parte derecha del dato en entrada. Esta operación hace intervenir manipulaciones bits por bits del dato.

2) Operación de tipo O-EXCLUSIVO con una subclave de la clave secreta.

3) Lectura en la tabla de tipo SBOX.

4) Permutación del dato. Esta operación hace intervenir manipulaciones bits por bits del dato.

5) Operación de tipo O-EXCLUSIVO con la parte izquierda del dato en entrada.

La ejecución de las operaciones 1) y 4) hace intervenir manipulaciones de datos bits por bits. Al registrar previamente el consumo de corriente que corresponde a una ejecución del algoritmo, cuando este bit es de 1, y el consumo de corriente cuando este bit es de 0, es posible descubrir el valor de este bit comparando el consumo de corriente con lo que fue registrado previamente.

Cabe la posibilidad de proteger la ejecución de las operaciones 1) y 4) que hace intervenir manipulaciones de datos bits por bits contra ataques de tipo DPA.

Para ello, antes de la ejecución de una operación de tipo permutación, anotada a continuación P, en un dato, anotado seguidamente D, se efectúa el sorteo de un número aleatorio, anotado a continuación U, que tiene el mismo tamaño que D. Se combina D y U por una operación de tipo O-EXCLUSIVO para obtener un dato anotado H. Se efectúa la operación P sucesivamente en Y y en H para obtener los resultados anotados PU y PH respectivamente. El resultado de la operación P en D se obtiene combinando PU y PH por una operación de tipo O-EXCLUSIVO.

Este procedimiento se aplica a las operaciones 1) y 4) descritas anteriormente.

Por la aplicación de este procedimiento a una operación de tipo permutación, los datos en los que se efectúa una manipulación bit por bit son aleatorios. Entonces ya no es posible realizar el ataque de tipo DPA descrito anteriormente. En efecto, el ataque de tipo DPA descrito anteriormente necesita el registro previo del consumo de corriente cuando un bit determinado del dato manipulado es de 1 y el consumo de corriente cuando este bit es de 0. Con el procedimiento descrito anteriormente, este registro no es posible, puesto que los datos manipulados U y H son aleatorios, y por tanto susceptible de cambiar en cada nueva ejecución. Además, los datos manipulados U y H no se conocen fuera de la tarjeta.

No obstante, sucede en ciertos casos que un procedimiento de codificación con clave secreta utilice igualmente operaciones aritméticas de tipo adición módulo con una potencia de dos. En estos casos conviene proteger igualmente estas operaciones. Ya sea D el dato que debe protegerse. El método consiste en añadir a D un azar R módulo una potencia de dos. De este modo, el dato D + R es aleatorio y el agresor no puede obtener información sobre D.

Así pues, sucede en ciertos casos que un procedimiento de codificación con clave secreta que manipule a la vez datos de la forma D xor R, o xor denote la operación de tipo O-EXCLUSIVO, y datos de la forma D+R, o + denote la adición de dos enteros módulo a una potencia de dos.

El procedimiento de la invención consiste en un método que permite pasar rápidamente y de manera asegurada de una representación a otra. La representación D xor R se llamará en el resto del documento representación booleana y la representación D+R se llamará representación aritmética.

El primer procedimiento de la invención describe un método que permite pasar de manera eficaz de una representación booleana a una representación aritmética. Se llama x el dato inicial que debe protegerse, y se llama x' al dato protegido. Se llama K el tamaño en bits de los enteros manipulados. De este modo tenemos x=x' xor r, donde r es un entero aleatorio. El procedimiento engloba las siguientes etapas:

1) Para todos los valores del entero y posibles, generar una tabla T que contenga los valores:

T(y)= (y xor r)-r

2) Poner en un entero A el valor de T (x')

El procedimiento descrito anteriormente permite obtener un valor A, tal como x=A+r, utilizando una tabla T que tome en entrada un entero de K bits y que envíe a la salida un entero de K bits, la tabla T se llama tabla de K bits hacia K bits. Así se obtiene una representación aritmética del entero x. Al agresor le resulta imposible deducir del procedimiento anterior cualquier tipo de información sobre el entero x, puesto que la variable x nunca ha sido manipulada.

El primer procedimiento de la invención engloba una variante que permite reducir el tamaño de la tabla T utilizada. En efecto, el primer procedimiento, tal y como se describió anteriormente necesita una tabla de tamaño K bits hacia K bits, cuando el tamaño de los enteros manipulados es de K bits. La tabla contiene entonces 2^K enteros de K bits, lo que para valores de K superiores a 8 hace impracticable el procedimiento. La variante del primer procedimiento permite efectuar conversiones en enteros largos, por ejemplo, de tamaño 32 bits, utilizando al mismo tiempo una tabla de K bits hacia K Bits, con K pequeño, por ejemplo K=4.

La variante del primer procedimiento consiste en efectuar una conversión de un enmascaramiento booleano hacia un enmascaramiento aritmético para enteros de tamaño 2.K bits, utilizando la tabla T anterior de K bits hacia K bits. La variante descrita utiliza otra tabla dicha tabla de retención que se llama C, que coge en entrada un entero r, que se inicializa de la siguiente manera:

1) Generar un entero aleatorio ? de tamaño K bits.

2) Para todos los enteros A de K bits, definir C(A) = 1+? mod 2^K si a+R = 2^k C(A) = ? si a+R < 2^k.

El procedimiento de conversión de la variante toma en entrada 2 enteros x' y r' de tamaño 2.K bits, tales como x=x' xor r', y envía a la salida dos enteros A y r'' de tamaño 2.K bits, tales como x=A+r'' mod 2^(2.K). El procedimiento incluye las siguientes etapas:

1) Separar x' en x₁' || x₂', ó x₁' y x₂' son enteros de K bits.

2) Separar r' en r₁' || r₂', ó r₁' y r' son enteros de K bits.

3) Remplazar x₁' por x₁' xor r

4) Remplazar x₁' por x₁' xor r₁'

5) Remplazar x₂' por x₂' xor r

6) Remplazar x₂' por x₂' xor r₂'

7) Efectuar A₁ = T(x₁') y A₂ = T(x₂')

8) Remplazar A₁ por A₂ -...

1. Procedimiento de contramedida que utiliza contra los ataques de tipo DPA una representación aritmética y una representación booleana que consiste en impedir el registro previo del consumo de la corriente generada por manipulaciones de bits por bits permitiendo pasar de manera eficaz de dicha representación boolena de datos, dicha representación se llama D xor R, o xor designa la operación de tipo O-EXCLUSIVO, hacia dicha representación aritmética de datos, dicha representación se llama D+R, dicho procedimiento utiliza un dato x que debe protegerse, el dato protegido se llama x' con x=x' xor r, el entero r es un entero aleatorio, dicho procedimiento permite obtener un valor A tal como x=A+r, dicho procedimiento se caracteriza porque engloba las dos siguientes etapas:

1) 1 Para todos los valores del entero y posibles, generar una tabla T que contenga los valores: T(y)= (y xor r)-r

1) 2 Poner en un entero A el valor de T (x').

2. Procedimiento de contramedida contra ataques de tipo DPA, que utiliza una representación aritmética y una representación booleana que consiste en impedir el registro previo del consumo de la corriente generada por manipulaciones de bits por bits permitiendo pasar de manera eficaz de dicha representación aritmética de datos, dicha representación se anota D+R, hacia dicha representación booleana de datos, dicha representación se anota D xor R, xor designa la operación de O-EXCLUSIVO, dicho procedimiento utiliza un dato x que debe protegerse, el dato protegido se anota A con x=A+r, el entero r es un entero aleatorio, dicho procedimiento permite obtener un valor x', tal como x=x' xor r, dicho procedimiento se caracteriza porque engloba las 2 siguientes etapas:

2) 1 Para todos los valores del entero y posibles, generar una tabla T que contenga los valores: T(y)= (y+r) xor r.

2) 2 Poner en la variable x' el valor de T(A).

3. Procedimiento de conversión según la reivindicación 1 que realiza una conversión de un enmascaramiento booleano hacia un enmascaramiento aritmético para enteros de tamaño 2.K bits, utilizando una tabla T de K bits hacia K bits, dicho procedimiento utiliza una tabla, llamada tabla de retención anotada C, que coge en entrada un entero r, y que se inicializa mediante las dos siguientes etapas:

1) Generar un entero aleatorio ? de tamaño K bits.

2) Para todos los enteros A de K bits, definir C (A) = 1+? mod 2^K si A+r = 2^k C(A)= ? si A+r < 2^k

dicho procedimiento toma en entrada 2 enteros x' y r' de tamaño 2.K bits, tales como x=x' xor r' , y envía a la salida dos enteros A y r'' de tamaño 2.K bits, tales como x=A+r'' mod 2^(2.K), caracterizado porque comprende las siguientes etapas:

1) Separar x' en x₁' || x₂', donde x₁' y x₂' son enteros de K bits.

2) Separar r' en r₁' || r₂', donde r₁' y r' son enteros de K bits.

3) Remplazar x₁' por x₁' xor r

4) Remplazar x₁' por x₁' xor r₁'

5) Remplazar x₂' por x₂' xor r

6) Remplazar x₂' por x₂' xor r₂'

7) Efectuar A₁ = T(x₁') y A₂ = T(x₂')

8) Remplazar A₁ por A₁ - C(A₂) mod 2^K T(x₂')

9) Efectuar r₁ = r + ? mod 2^k

10) Volver A = A₁ || A₂ y r'' = r₁ || r.

4. Procedimiento de conversión según la reivindicación 3, que realiza una conversión de un enmascaramiento booleano hacia un enmascaramiento aritmético para enteros de tamaño superior a 2.K bits, utilizando una tabla T y una tabla C de K bits hacia K bits.

5. Procedimiento de conversión según la reivindicación 2, que realiza una conversión de un enmascaramiento aritmético hacia un enmascaramiento booleano para enteros de tamaño 2.K bits, dicho procedimiento utiliza una tabla T anterior de K bits hacia K bits, dicho procedimiento utiliza una tabla de retención anotada C, dicha tabla toma en entrada un entero r y está inicializada mediante las dos etapas siguientes:

1) Generar un entero aleatorio ? de tamaño K bits.

2) Para todos los enteros A de K bits, definir C (A) = 1+? mod 2^K si A+r = 2^k C(A) = ? si A+r < 2^k

dicho procedimiento toma en entrada dos enteros A y r' de tamaño 2.K bits, tales como x=A+ r' mod 2^(2.K) y envía en salida dos enteros x' y r'' de tamaño 2.K bits, tales como x=x' xor r'' caracterizado porque incluye las siguientes etapas:

1) Generar un azar a de tamaño K bits,

2) Ya sea G = a || r

3) Remplazar A por A-G mod 2^(2.K)

4) Remplazar A por A+r' mod 2^(2.K)

5) Separar A en A₁ || A₂ con A₁ y A₂ de tamaño K bits.

6) Remplazar A₁ por A₁ + C(A₂) mod 2^K.

7) Remplazar a por a - ? mod 2^K.

8) Remplazar A₁ por A₁ - r mod 2^K.

9) Remplazar A₁ por A₁ + a mod 2^K

10) Efectuar x'₁ = T(A₁) y x'₂ = T(A₂)

11) Remplazar x₁' por x₁' xor ?

12) Remplazar x₁' por x₁' xor r

13) Volver x₁' = x₁' || x₂' y r'' = ? || r.

6. Procedimiento de conversión según la reivindicación 5, caracterizado porque está en condiciones de efectuar una conversión de un enmascaramiento aritmético hacia un enmascaramiento booleano para enteros de tamaño superior a 2 K bits, utilizando una tabla T y una tabla C de K bits hacia K bits.

7. Procedimiento de codificación con clave secreta, caracterizado porque utiliza cualquiera de las reivindicaciones anteriores.

8. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque se aplica a un objeto electrónico portátil de tipo tarjeta inteligente.