Ejemplo Criptosistema McEliece en SAGE

En el 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de los Códigos. Dado que esta teoría es muy compleja, los expertos recomiendan una familiarización matemática preliminar con la Teoría de la Codificación, los Códigos de Goppa, y los Cuerpos de Galois.

 En el sistema de McEliece, cada usuario ha de elegir un polinomio irreducible de grado $delta$, y construir una matriz generadora del correspondiente código de Goppa, matriz G, de orden k x n. También ha de calcular la llave pública, que es una matriz generadora del código Goppa. Este código debe ser  tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño. La llave pública es obtenida a partir de la multiplicación de una matriz aleatoria no singular de orden 2^m-k*m, y una matriz de permutaciones de orden 2^m. Todos los usuarios del sistema mantienen sus respectivas llaves públicas, mientras que las matrices S,G e P serán secretas.

A continuación presentamos el algoritmo para generación de las llaves, cifrado de un texto plano y descifrado de un texto cifrado, según wikipedia, y su respectiva implementación mediante un ejemplo en SAGE. Es necesario "correr" primero la última de las celdas de este post, la cual contiene los algoritmos auxiliares como por ejemplo el algoritmo de Patterson.

Generación de Llaves

1. Alicia selecciona un código de Goppa binario Gamma com parâmetros (n,k) y capacidad de correción de delta errores; 
2. Alicia gera a matriz geradora $G$, de dimensiones n-m*k x n, del código \Gamma; Selecciona una matriz binaria no singular S, de dimensiones;n-m*k x n-m*k; 
3.  Selecciona una matriz de permutación P, de dimensión n; 
4.  Computa a matriz $G' = SGP; 
5.  La llave pública de Alicia é (G',delta) y su llave privada es (S,G,P).

Sistema Demostrablemente Seguro

Hace ya algunos dias que estoy queriendo dejar en claro algunos conceptos de seguridad que ya había aprendido y que por el paso del tiempo estaban confusos. Esos conceptos por ejemplo son nociones de seguridad, modelos de ataque, seguridad demostrable etc. Como siempre, lo que entiendo después de la lectura intentó escribirlo como se puede ver en mis entradas Propiedad de la Indistinguibilidad en Criptosistemas, Modelos de Ataque.

Siguiendo con la recordación, en esta entrada escribo un resumen acerca del concepto sistema demostrablemente seguro (provably secure).

Dado un criptosistema como podemos probar su seguridad?

• Tratando de montar un ataque
• Si el ataque fue encontrado entonces el criptosistema no es seguro.
• Si el ataque no fue encontrado no se puede decir nada acerca de la seguridad del criptosistema.
• Probando que no existe ataque bajo algunas asunciones.
• Publicar la verificabilidad de la prueba
• Ataque encontrado, entonces las asunciones fueron falsas

Como hacer esa prueba bajo asunciones?

• Describir  un criptosistema y sus modos operacionales,
• Formalmente definir la noción de seguridad a lograr = (objetivo que el atacante atacaria + modelo de ataque ). Ejm: IND-CCA2, IND objetivo e CCA2 modelo de ataque.
• Realizar asunciones computaciones, (problema factoración, problema logaritmo discreto, dureza de la decodificación de Códigos de Goppa Binário, etc).
• Exhibir una reducción entre un algoritmo que rompe la noción de seguridad y uno que rompe la asunción computacional. Ejemplo (RSA is reducible para OW-CCA2(S)).

¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!

Propiedad de la Indistinguibilidad en Criptosistemas

Actualmente esta propiedad la poseen la mayoría de criptosistemas. Un criptosistema es denominado seguro en términos de indistinguibilidad si, dado el par de textos planos M0, M1 y el texto cifrado C, no existe atacante que tenga probabilidad mayor al que tendría un atacante con la probabilidad 1/2, para poder afirmar si el texto cifrado C pertenece al cifrado de M0 o M1.

Indistinguibilidad bajo CPA (IND-CPA):

Para criptosistemas asimétricos esta propiedad es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:

1. El desafiador crea sus claves publica PK y privada SK;
2. El atacante puede usar PK para cifrar los mensajes de texto plano que el desee;
3. El atacante envía para el desafiador los textos planos M0 y M1;
4. El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);
5. El atacante es libre de hacer nuevas cifraciones. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).

Un sistema es dicho IND-CPA seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.

Indistinguibilidad bajo CCA (IND-CCA/IND-CCA2):

Al igual que en la propiedad anterior, esta es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:

1. El desafiador crea sus claves publica PK y privada SK;
2. Dado que el atacante tiene acceso a PK entonces puede hacer cualquier número de cifraciones, así como también puede descifrar texto cifrados usando un oracle de deciframiento.
3. El atacante envía para el desafiador los textos planos M0 y M1;
4. El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);
5. El atacante puede realizar mas cifraciones si lo desea. Si el modelo de ataque del desafiador es:
1. CCA entonces el atacante no puede realizar mas decifraciones de textos cifrados, usando el oracle.
2. CCA2 entonces el atacante puede realizar mas decifraciones de textos cifrados, usando el oracle, excepto C.
6. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).

Un sistema es dicho IND-CCA/CCA2 seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.

La indistinguibilidad bajo CPA (IND-CPA) es una propiedad que la poseen los sistemas denominados probadamente seguros. IND-CPA es equivalente a la propiedad de seguridad semántica en criptosistemas, por lo cual muchas veces esta equivalencia  es usado para pruebas criptográficas. Algunos sistemas criptográficos también ofrecen la indistinguibilidad bajo CCA (IND-CCA).

La indistinguibilidad contra ataques adaptativos para sistemas criptográficos de llave pública fue introducida por Rackoff and Simon.

Modelos de Ataque CPA y CCA

Ataque de Texto Plano Escogido.-  Es un modelo de ataque que tiene por objetivo descubrir la clave de cifrado de un criptosistema. Consiste en encriptar mensajes planos, por parte del atacante, con el fin de obtener información acerca de la clave usada para cifrar mensajes. En algunos casos el atacante solo necesita encriptar un pedazo del mensaje, para el objetivo descrito anteriormente, este caso es conocido como ataque de inyección de texto plano.

Ataque de Texto Cifrado Escogido.- Es un modelo de ataque con el objetivo, ambicioso, de obtener la clave de cifrado mediante la habilidad del atacante para engañar al que posee la clave. En este post usaré las siglas en inglés CCA para identificar este tipo de ataque. Para un mejor entendimiento de este tipo de ataque daré un ejemplo simple en un escenario para un criptosistema de llave simétrica:

Supongamos que el general Alfa esta enviando el mensaje cifrado BCFRET al general Beta. El atacante intercepta este mensaje y lo cambia por un mensaje cifrado aleatório FLOULN  Cuando el general Beta decifra este mensaje modificado obtiene un mensaje sin sentido AGHPJK  Perplejo, llama para el general Alfa y le pregunta porque me ha llegado el mensaje AGHPJK? Acaso han cambiado la clave?. Infelizmente esta llamada también esta siendo interceptada por el atacante, por lo cual el sabe que el mensaje cifrado FLOULN es decifrado en AGHPJK. El utiliza una (de las tantas) forma simple de obtener la llave restando estas dos palabras EEHEBC. En este caso el atacante pudo obtener la llave con tan sólo un mensaje cifrado.

Se dice que un ataque CCA es no adaptativo si el atacante no usa el texto plano resultante del proceso de engañar al que posee la clave. Y, se dice que el modelo CCA es adaptativo (CCA2) si el atance usa el texto plano resultante del proceso de engañar a quien posee la clave para poder seguir enviando textos
cifrados elegidos. En el ejemplo anterior si Alfa continuara enviando mensajes, después de lo que ocurrió, y usa AGHPJK para crear otro mensaje cifrado aleatório, sería entonces un ejemplo de CCA adaptativo.

¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!