jueves, 18 de octubre de 2012

[CRIPTOGRAFÍA] Block Cipher - FROG

Cifrado por bloques

Esta semana se encargó investigar sobre alguna unidad de cifrado por bloques, una unidad de cifrado de clave simétrica que opera en grupos de bits de longitud fija, llamados bloques, aplicándoles una transformación invariante.

Cuando realiza cifrado, una unidad de cifrado por bloques toma un bloque de texto plano como entrada y produce un bloque de igual tamaño de texto cifrado.

La transformación exacta es controlada utilizando una segunda entrada — la clave secreta. El descifrado es similar: se ingresan bloques de texto cifrado y se producen bloques de texto plano.






FROG

Para mi ejemplo, encontré un algoritmo llamado FROG. FROG es un algoritmo de cifrado por bloques realizado por Georgoudis, Leroux y Chaves. Puede trabajar con bloques de tamaño entre 8 y 128 bytes, con tamaños de clave comprendidos entre los 5 y los 125 bytes. El algoritmo consiste en 8 rondas y tiene un desarrollo de la clave muy complicado.

Se envió en 1998 a la competición AES como candidato para convertirse en el Advanced Encryption Standard. En 1999, David Wagner y otros encontraron un número de claves débiles para FROG, que afectaba aproximadamente a una cada mil millones. Otros problemas eran un inicio de la clave muy lento y una velocidad de cifrado relativamente lenta. FROG no llegó a ser elegido finalista.

Algoritmo


Frog opera de la siguiente manera:

Primero que nada se necesitan de ciertas cosas antes de empezar:

  • Clave de 16 bytes.
  • Una S-box invertible de 8 entradas, 8 salidas dependiente de la clave.
  • Una secuencia de 0 a 15 ordenada en forma aleatoria.
Esto teniendo en cuenta que necesitamos los bloques aleatorios y nuestro texto plano.

Cada ronda consiste en 16 pasos; uno para cada byte del bloque, en cada paso se realiza lo siguiente:
  1. Se aplica un XOR al byte seleccionado del texto con el de la clave.
  2. Se reemplaza el resultado por el sustituto en la S-box.
  3. Se hace XOR con el byte del bloque correspondiente y se toma el resultado.
  4. Se toma un número de la secuencia que corresponde a la posición de un byte del bloque y se hace XOR con ese byte.
  5. Se repiten los pasos.
Ejemplo

Haré un ejemplo sencillo con un "hola mundo". Trataré de cifrar el texto y de decifrarlo utilizando un bloque. Primero que nada se transforma la cadena en binario para hacer las operaciones. y se agregarán ceros para completar los 16 bytes, quedando de la siguiente manera:

"h" - 01101000 
"o" - 01101111 
"l" - 01101100 
"a" - 01100001 
" " - 00100000 
"m" - 01101101 
"u" - 01110101 
"n" - 01101110 
"d" - 01100100 
"o" - 01101111 
"0" - 00110000 
"0" - 00110000 
"0" - 00110000 
"0" - 00110000 
"0" - 00110000 
"0" - 00110000

Se genera una clave de 16 bytes aleatoria formateada en binario:

01100011 00110011 00110000 00101010 10101111 11011100 01100101 11111001
01100110 01010110 11111100 10000011 10001000 11111111 10000100 10101000

Se genera una secuencia de números del 0 al 15:

10   8   9   2  12   5   4  11   6   1  14  15  13   7   3   0

Se toma la posición 0 y se procede:

01101000
01100011
________
00001011

La S-box:



El valor del S-box de 0000 - 1011 es: 01011000 y se reemplaza por 00001011 y viceversa para generar los bloques de decifrado.

El bloque 1 es :

11110011 11110111 01101101 10000111 01011010 00100011 00101110 01011010
11101000 11111111 10111101 11110000 01011101 01001100 11010011 10010100

Se toma el primer valo:

11110011
01011000
________
10101011

Se toma el segundo valor según la secuencia:

11111111
10101011
________
01010100

Se guarda el valor como cifrado.

Los primeros números resultantes con este procedimiento son:

01010100
01000110
10000100
10110011
...

Para obtener el Texto plano se hace el mismo procedimiento pero desde atrás hacia adelante.

Ventajas y desventajas

Como se había mencionado antes, FROG era uno de los algoritmos que participó en la competencia para ser el próximo AES pero no fue seleccionado para las finales.

Tambien se mencionó que el algoritmo tiene debilidades frente a ciertas claves afectando una en mil millones. Sin embargo la debilidad que tiene es fácil de resolver aplicando en sus últimas 4 rondas el modo de descifrado.

FROG no es rápido al ejecutar, debido a que genera las claves de una manera lenta, sin embargo es rápido encriptando y desencriptando. Por lo que se si generan las claves anteriormente no debería ser un problema.

1 comentario: