PROCEDIMIENTO DE SEGURIZACION DE UN CONJUNTO ELECTRONICO DE CRIPTOGRAFIA CON CLAVE SECRETA CONTRA LOS ATAQUES POR ANALISIS FISICO.

Procedimiento de segurización de un conjunto electrónico mediante un proceso de cálculo criptográfico simétrico que utiliza una clave secreta,

caracterizada porque:

a)Se divide el proceso de cálculo criptográfico simétrico en varias partes de proceso de cálculo distintas efectuadas paralelamente e implementando resultados parciales intermedios distintos de los del cálculo criptográfico simétrico;

b)Se reconstituye el valor final obtenido por el cálculo criptográfico simétrico sin división, a partir de dichos resultados parciales intermedios distintos

Procedimiento de segurización de un conjunto electrónico de criptografía con clave secreta contra los ataques por análisis físico.

El presente invento se refiere a un procedimiento de segurización de un conjunto electrónico mediante un algoritmo criptográfico que utiliza una clave secreta. Con mayor precisión, el procedimiento contempla realizar una versión del algoritmo que no sea vulnerable frente a ningún tipo de ataques físicos -denominados Differential Power Analysis o High-Order Differential Power Analysis- para intentar obtener datos sobre la clave secreta a partir del estudio del consumo eléctrico del conjunto electrónico en curso de ejecución del cálculo.

Los algoritmos criptográficos considerados aquí utilizan una clave secreta para calcular una información de salida en función de un dato de entrada; puede tratarse de una operación de cifrado, de descifrado o de firma o comprobación de firma, o incluso de una autentificación o de no repudiación. Están construidos de manera tal que un ataque, conociendo entradas y salidas, no pueda en la práctica deducir ninguna información sobre la clave secreta propiamente dicha.

WO 98/52319 describe un método que permite proteger el algoritmo RSA-CRT.

Los ataques de tipo Análisis de Potencia Eléctrica, Power Analysis en lenguaje anglosajón, desarrollados por Paul Kocher y Cryptographic Research (Confer document Introduction to Differential Power Analysis and related Attacks by Paul Kocher, Joshua Jaffe, and Benjamin Jun, Cryptography Research, 870 Market St., Suite 1008, S. Francisco, CA 94102, edición del documento HTML en la dirección URL: http://www.cryptography.com/dpa/technical/index.html), proceden de la constatación que, en realidad, el atacante puede adquirir datos, diferentes de los simples datos de entradas y salidas, en caso de ejecución del cálculo, como p. ej. el consumo eléctrico del microcontrolador o la irradiación electromagnética emitida por el circuito.

El análisis de energía eléctrica diferencial, Differential Power Analysis en lenguaje anglosajón, abrevi. DPA, es un ataque que permite obtener datos sobre la clave secreta contenida en el conjunto electrónico, efectuando un análisis estadístico de los registros de consumo eléctrico efectuados en gran número de cálculos con esta misma clave.

Se considera, como ejemplo no limitativo, el caso del algoritmo DES (Data Encryption Standard), del que se puede encontrar una descripción en uno de los documentos:

El algoritmo DES se desarrolla en 16 etapas denominadas vueltas, cf. figura 1a. En cada una de estas 16 vueltas, una transformación F se efectúa sobre 32 bits. Esta transformación F utiliza ocho transformaciones no lineales de seis bits sobre cuatro bits, que se codifican, cada una, en una tabla denominada caja-S, cf. figura 1b, en donde las cajas S llevan la anotación S1, S2, ..., S8.

El ataque DPA en el DES puede ser introducido de la manera siguiente:

• 1ª etapa: se efectúan medidas de consumo en la primera vuelta, para 1000 cálculos de DES. Se anotan E[1], ..., E[1000] los valores de entrada de estos 1000 cálculos. Se anotan C[1], ..., C[1000] las 1000 curvas correspondientes de consumo eléctrico medidas durante estos cálculos. Se calcula también la curva promedio CM de las 1000 curvas de consumo.

• 2ª etapa: nos interesamos, por ejemplo, por el primer bit de salida de la primera caja-S durante la primera vuelta. Apuntamos b el valor de dicho bit. Es fácil ver que b depende sólo de seis bits de la clave secreta. El atacante se basa en una hipótesis sobre los seis bits atañidos. Calcula -a partir de estos seis bits y de los E[i]- los valores teóricos esperados para b. Esto permite separar las 1000 entradas E[1], ..., E[1000] en dos categorías: las que dan b = 0 y las que dan b = 1.

• 3ª etapa: se calcula ahora el promedio CM' de las curvas correspondientes a entradas de la primera categoría, es decir para las cuales b=0. Si CM y CM' presentan una diferencia notable, se considera que los valores retenidos para los seis bits de clave eran buenos. Si CM y CM' no presentan diferencias sensibles, en el sentido estadístico, es decir que no hay diferencia clara superior al desvío típico del ruido medido, se mide la 2ª etapa con otra opción para los seis bits.

• 4ª etapa: se repiten las etapas 2 y 3 con un bit diana b procedente de la segunda caja-S, luego de la tercera caja-S, ..., hasta la octava caja-S. Se obtienen así por último 48 bits de la clave secreta.

• 5ª etapa: los ocho bits restantes pueden encontrarse mediante búsqueda exhaustiva.

Este ataque no necesita ningún conocimiento sobre el consumo eléctrico individual de cada instrucción, ni sobre la posición en el tiempo de cada una de estas instrucciones. Se aplica de la misma manera si se supone que el atacante conoce salidas del algoritmo y las curvas de consumo correspondientes. Se basa únicamente sobre la hipótesis fundamental según la cual:

Hipótesis fundamental: existe una variable intermedia, que aparece en el cálculo del algoritmo, como el conocimiento de algunos bits de clave, en la práctica menos de 32 bits, permitiendo decidir si dos entradas, respectivamente dos salidas, dan o no el mismo valor para dicha variable.

Todos los algoritmos que utilizan cajas-S, como el DES son potencialmente vulnerables a la DPA, ya que los modos de realización corrientes permanecen en general en el marco de la hipótesis mencionada anteriormente.

Los ataques denominados por análisis de energía eléctrica de alto nivel, High-Order Differential Power Analysis, en lenguaje anglosajón, en abreviado HO-DPA, son una generalización del ataque DPA descrito anteriormente, pudiendo utilizar varias fuentes de información diferentes, además del consumo, poniendo en juego las medidas de irradiación electromagnética, temperatura, etc. e implementando procesamientos estadísticos más sofisticados que la simple noción de promedio, variables intermedias (que generalizan el bit b definido anteriormente) menos elementales.

No obstante, se basan exactamente en la misma hipótesis fundamental que la DPA.

El procedimiento de la invención tiene como objeto suprimir los riesgos de ataque DPA o HO-DPA de conjuntos o sistemas electrónicos de criptografía de clave secreta.

Otro objeto del presente invento es, por consiguiente, una modificación del proceso de cálculo criptográfico implementado por los sistemas electrónicos de criptografía protegidos de manera que la hipótesis fundamental anterior no sea verificada, a saber que ninguna variable intermedia depende del consumo de un subconjunto fácilmente accesible de la clave secreta, resultando entonces los ataques de tipo DPA ó HO-DPA inoperantes.

El procedimiento de segurización de un conjunto electrónico que pone en juego un proceso de cálculo criptográfico clásico que utiliza una clave secreta, objeto del invento, es notable por cuanto se divide el proceso de cálculo criptográfico en varias partes de cálculo distintas efectuadas paralelamente e implementando resultados parciales intermedios distintos de los del cálculo criptográfico clásico, y que se reconstituye el valor final, obtenido por el cálculo clásico en ausencia de división, a partir de los resultados parciales intermedios distintos. Por procesos de cálculo criptográfico clásico, se entiende cualquier proceso de cálculo secuencial o sucesivo que permita obtener valores cifrados, descifrados, valores de firma, de comprobación de firma, de autentificación y de no repudiación. Tal proceso permite inhibir los ataques de tipo DPA ó HO-DPA contra los conjuntos o sistemas embarcados provistos de funciones de cálculo criptográfico tales como las tarjetas de microcalculadores dedicadas a funciones de monética electrónica, tarjeta bancaria, tarjeta de control de acceso...

1.Procedimiento de segurización de un conjunto electrónico mediante un proceso de cálculo criptográfico simétrico que utiliza una clave secreta, caracterizada porque:

2. Procedimiento según la reivindicación 1, caracterizado porque cada variable o resultado (v) intermedio dependiente de los datos de entrada o salida implementados por el proceso de cálculo criptográfico simétrico queda sustituido por un número determinado k de variables intermedias parciales (v1, ..., vk), estando vinculadas las variables intermedias (v) e intermedias parciales (v1 a vk) por una función f, v = f (v1, v2, ..., vk) que permite reconstituir dicha variable intermedia (v).

3. Procedimiento según la reivindicación 2, caracterizado porque dicha función f, que vincula las variables intermedias parciales y dicha variable intermedia (v), es tal que el conocimiento de un valor de esta variable intermedia no permite nunca deducir el conjunto de los valores particulares parciales vi tales que exista un (k-1)-uplet (v1, ..., vi-1, vi+1 ... vk) que responde a la ecuación (v1, ..., vi, ..., vk) = v.

4. Procedimiento según la reivindicación 3, caracterizado porque dicha función es la función "O-exclusivo" bit a bit, y en dichas variables intermedias (v) y variables intermedias parciales (v1, ..., vi, ..., vk) se verifica la relación:

5. Procedimiento según la reivindicación 3, caracterizado porque para una variable intermedia (v) de valores en el grupo multiplicativo Z/nZ definido por el conjunto de los enteros módulo n, dicha función es la función producto módulo n, f (v1, ..., vk) = v1, v2, ... vk módulo n, en la cual dichas variables intermedias parciales son variables de valores en dicho grupo multiplicativo de Z/nZ.

6. Procedimiento según la reivindicación 3, caracterizado porque, dicha función f que vincula las variables intermedias parciales y dicha variable intermedia (v), las partes de proceso de cálculo distintas conducidas paralelamente son independientes y dichas partes de proceso de cálculo distintas conducidas paralelamente se conducen sin reconstitución de dicha variable intermedia (v) dependiente de los datos de entrada o de salida implementada por dicho proceso de cálculo criptográfico simétrico.

7. Procedimiento según la reivindicación 1, caracterizado porque dicha división se efectúa en dos partes distintas conducidas paralelamente.

8. Procedimiento según la reivindicación 1, caracterizado porque dicha división se efectúa en k partes y por que para un proceso de cálculo criptográfico simétrico que utiliza transformaciones no lineales de m bits sobre n bits descritas en tablas de conversión, en las que los n bits de Salida de la transformación se leen en una dirección que depende de los m bits de entrada, se sustituye cada transformación no lineal aplicada a una variable intermedia del proceso de cálculo criptográfico simétrico sin división, por una transformación no lineal parcial de km bits sobre kn bits aplicada al conjunto de las variables intermedias parciales, transformación no lineal parcial que se describe mediante k tablas de conversión parcial en las que los n bits de salida de la transformación se leen en una dirección que depende de los km bits de entrada.

9. Procedimiento según la reivindicación 8, caracterizado porque entre las k tablas de conversión parcial k-1 tablas de conversión parcial contienen variables aleatorias secretas.

10. Procedimiento según la reivindicación 8, caracterizado porque entre k tablas de conversión parcial, utilizadas para sustituir cada tabla de conversión no lineal, se utilizan siempre las mismas k-1 tablas aleatorias secretas.

11. Procedimiento según la reivindicación 1, caracterizado porque dicha división se efectúa en k partes, y porque, para un proceso de cálculo criptográfico simétrico que utiliza transformaciones no lineales de m bits sobre n bits descritas por tablas de conversión en las que los n bits de salida de la transformación se leen en una dirección que depende de los m bits de entrada, se sustituye cada transformación no lineal aplicada a una variable intermedia del proceso de cálculo criptográfico simétrico, sin división, por una transformación no lineal parcial de km bits sobre kn bits aplicada al conjunto de las variables intermedias parciales, (k-1)n de dichos bits de salida de esta transformación se calculan como función polinomial de los km bits de entrada y los n bits restantes de dichos bits de salida, obtenidos por lectura de una tabla de conversión en la que los n bits restantes se leen en una dirección que depende de los km bits de entrada.

12. Procedimiento según la reivindicación 2, caracterizado porque dicha división se efectúa en k partes y porque para un proceso de cálculo criptográfico simétrico que utiliza transformaciones no lineales de m bits sobre n bits descritas en tablas de conversión en las que los n bits de salida de la transformación se leen en una dirección que depende de los m bits de entrada, se sustituye cada transformación no lineal aplicada a una variable intermedia del proceso de cálculo criptográfico simétrico, sin división, por una transformación no lineal parcial de km bits sobre kn bits aplicada al conjunto de las variables intermedias parciales, transformación no lineal parcial ésta que se describe mediante k tablas de conversión, cada una de estas tablas de conversión recibe como entrada un valor obtenido por aplicación de una función biyectiva secreta f1 en dicha función f (v1, ..., vk) de las variables intermedias parciales según la relación fj o f (v1, ..., vk), j € [1, k], esta aplicación fj o f (v1, ..., vk) se efectúa mediante evaluación directa de un valor resultante, valor resultante aplicado en la entrada de la tabla de conversión que permite leer n bits de salida de la transformación en una dirección que depende de estos m bits de entrada.

13. Procedimiento según la reivindicación 12, caracterizado porque, entre las k tablas de conversión parcial, k-1 tablas de conversión parcial contienen valores aleatorios secretos.

14. Procedimiento según la reivindicación 12, caracterizado porque, entre las k tablas de conversión parcial utilizadas para sustituir cada tabla de transformación no lineal, se utilizan siempre las mimas k-1 tablas de conversión aleatorias secretas.

15. Procedimiento según la reivindicación 1, caracterizado porque las operaciones efectuadas en las diferentes partes procedentes de la división del proceso de cálculo criptográfico en varias partes de proceso de cálculo distintas se ejecutan secuencialmente.

16. Procedimiento según la reivindicación 1, caracterizado porque las operaciones efectuadas en las diferentes partes procedentes de la división del proceso de cálculo criptográfico en varias partes de proceso de cálculo distintas se ejecutan de manera imbricada.

17. Procedimiento según la reivindicación 1, caracterizado porque las operaciones efectuadas en las diferentes partes procedentes de la división del proceso de cálculo criptográfico en varias partes de proceso de cálculo distintas se ejecutan de manera simultánea en el caso de la multiprogramación.

18. Procedimiento según la reivindicación 1, caracterizado porque las operaciones efectuadas en las diferentes partes procedentes de la división del proceso de cálculo criptográfico en varias partes de proceso de cálculo distintas se ejecutan simultáneamente en procesos diferentes que trabajan en paralelo.

19. Utilización del procedimiento según la reivindicación 1 en una tarjeta de microcalculador.

20. Utilización del procedimiento según la reivindicación 1 para la segurización de proceso de cálculo criptográfico soportado por los algoritmos DES, Triple DES.