PDF de programación - Cifrado Simétrico en Bloques

Cifrado Simétrico en Bloque

(Tema 3 y apéndice C)

Cifrado y descifrado genérico en bloque

MENSAJE (N bits)

BLOQUE A

BLOQUE B

A ⊕ Xi

B ⊕ Xi

N/2

⊕

FUNCIÓN f

Xi

⊕

A ⊕ Xi

N/2

ki

⊕

B ⊕ Xi

⊕

FUNCIÓN f

Xi

ki

⊕

⊕

A
B
Puesto que Y ⊕ Xi ⊕ Xi = Y

© Jorge Ramió Aguirre Madrid (España) 2006

Cifrado tipo Feistel

Horst Feistel: inventor (IBM) del algoritmo LUCIFER a comienzos de
los años 70. El algoritmo fue utilizado por el Reino Unido. En 1974 se
propone a la NSA como estándar y en ese año dará origen al DES.

• Dado un bloque de N bits (típico
64) éste se dividirá en dos mitades.
• Existirá una función unidireccional F
(muy difícil de invertir).
• Se realizan operaciones con la clave
ki sólo con una mitad del bloque, y
se permutan en cada vuelta las dos
mitades, operación que se repite
durante n vueltas.

© Jorge Ramió Aguirre Madrid (España) 2006

Un ejemplo básico de cifrado tipo Feistel
El algoritmo usará bloques de tamaño 8 caracteres. Tendrá dos
vueltas y en cada vuelta realizará una operación de sustitución
S y una permutación P sobre la 1ª mitad.
Sustitución: Ci = (Mi +1 ) mod 27
Permutación: Ci = ∏3241 (el carácter 1º pasa a la 4ª posición
en el criptograma, el 4º a la 3ª, el 2º a la 2ª y el 3º a la 1ª)

Mensaje: M = STAR WARS, LA MISIÓN CONTINÚA

© Jorge Ramió Aguirre Madrid (España) 2006

Cifrado tipo Feistel en cuerpo n = 27

M = STAR WARS, LA MISIÓN CONTINÚA

M1 = STAR WARS LAMI SION CONT INUA
S1 = TUBS WARS MBNJ SION DPÑU INUA
P1 = BUST WARS NBJM SION ÑPUD INUA

M2 = WARS BUST SION NBJM INUA ÑPUD
S2 = XBST BUST TJPÑ NBJM JÑVB ÑPUD
P2 = SBTX BUST PJÑT NBJM VÑBJ ÑPUD

Si: +1 mod 27
Pi: ∏3241
Primera
vuelta

Segunda
vuelta

C = SBTX BUST PJÑT NBJM VÑBJ ÑPUD
Aunque parezca increíble, el DES hará prácticamente lo mismo
trabajando con bits y con funciones un poco más “complejas”.

© Jorge Ramió Aguirre Madrid (España) 2006

Cifradores de bloque más conocidos

Vueltas

Clave (bits)
Algoritmo Bloque (bits)
128 16
Lucifer 128
16
56
64
DES
64

16
Loki
64
--
64 variable
RC2
CAST 64

8
16
64 variable
Blowfish
IDEA

64
128
8

64



Skipjack
RIJNDAEL

64 80
128

128 o más

32


flexible 

© Jorge Ramió Aguirre Madrid (España) 2006

Características de estos algoritmos

• Lucifer: algoritmo original tipo Feistel que dará lugar al DES.
• DES: algoritmo tipo Feistel que se convirtió en estándar durante

casi treinta años. Hoy es vulnerable por su longitud de clave.

• Loki: algoritmo australiano similar al DES, tipo Feistel.
• RC2: algoritmo propuesto por Ron Rivest y que se incluye en

navegadores de Internet desde 1999.

• CAST: algoritmo tipo Feistel que se ofrece como cifrador por

defecto en últimas versiones de PGP.

• Blowfish: algoritmo tipo Feistel propuesto por Bruce Schneier.
• IDEA: algoritmo europeo usado en el correo electrónico PGP.
• Skipjack: propuesta de nuevo estándar en USA a finales de los

90 para comunicaciones oficiales (tiene puerta trasera).

• RIJNDAEL: nuevo estándar mundial desde finales de 2001.

© Jorge Ramió Aguirre Madrid (España) 2006

Otros cifradores de bloque

Algoritmo Bloque (bits)
Twofish
Khufu
Khafre
Gost


RC5
SAFER 64
Akelarre
FEAL

128
64

64

64

variable
64

variable

64

Vueltas
Clave (bits)
variable variable
512 16, 24, 32
128 más vueltas
256
variable
64
variable
64

32
variable
8
variable
32

De éstos, los más conocidos son Twofish -uno de los candidatos a
AES y que lo encontraremos en últimas versiones de PGP- y RC5.

© Jorge Ramió Aguirre Madrid (España) 2006

Características de estos algoritmos

• Twofish: Propuesto por Bruce Schneir después de Blowfish, de
tipo Feistel, diseño simple, sin claves débiles y multiplataforma.

• Khufu: algoritmo propuesto por Ralph Merkle con una clave

generada con un sistema de “cajas” S.

• Khafre: algoritmo propuesto por Ralph Merkle en el que la

clave ya no depende de las cajas S.

• Gost: algoritmo similar al DES con cajas S secretas propuesto

en la Unión Soviética.

• RC5: algoritmo propuesto por Ron Rivest; realiza operaciones

or exclusivo, suma modular y desplazamiento de bits.

• SAFER 64: algoritmo propuesto por James Massey.
• Akelarre: algoritmo español propuesto en 1996 por el CSIC,

Consejo Superior de Investigaciones Científicas.

• FEAL: algoritmo propuesto en Japón.

© Jorge Ramió Aguirre Madrid (España) 2006

Algunas tasas de cifra comparativas

Velocidad de cifra de algoritmos en un PC 486 a 33 MHz
Algoritmo Kbytes/seg
Algoritmo Kbytes/seg
35
DES

Triple DES 12
53
IDEA
FEAL (32 v) 91
221
Khufu (16 v)
Khufu (32 v) 115
127
RC5 (8 v)
RC5 (16 v) 65
81
SAFER (6 v)
SAFER (12 v) 41
Blowfish (12 v) 182
Blowfish (20 v) 110

Fuente: Criptografía Digital. Fundamentos y
Aplicaciones. J. Pastor, M.A. Sarasa, J.L. Salazar,
Prensas Universitarias de Zaragoza (2001).

Dada la baja velocidad
del PC , estos valores
son sólo indicativos y
de comparación.

© Jorge Ramió Aguirre Madrid (España) 2006

Algoritmos DES, IDEA y AES

Profundizaremos  en estas diapositivas en los algoritmos
DES, Triple DES, IDEA y AES. ¿Por qué?

 DES es un cifrador de Feistel, ha sido un estándar y en

aplicaciones bancarias se seguirá usando durante tiempo.

 DES es de muy fácil comprensión y usa cajas S como varios

algoritmos más modernos y el actual estándar AES.
 Triple DES sigue siendo un estándar en e-commerce.
 IDEA es un algoritmo seguro que hace uso de los conceptos de

inversos en un cuerpo finito, como todos los algoritmos de
cifra modernos, y se usa entre otros en la aplicación PGP.
 AES es el nuevo estándar de cifra avanzada: RIJNDAEL.

© Jorge Ramió Aguirre Madrid (España) 2006

Modos de cifra

Todos los algoritmos pueden usarse aplicando diversos
modos de cifra, entre ellos:

ECB: Electronic CodeBook (libro electrónico de códigos)
CBC: Cipher Block Chaining (encadenamiento de bloques)
CFB: Cipher FeedBack (realimentación de bloques)
OFB: Output FeedBack (realimentación bloque de salida)

Analizaremos los dos primeros para el caso del DES,
aunque el estudio es extensible a todos los demás ya que en
estos modos el cifrador se considera una caja negra.

© Jorge Ramió Aguirre Madrid (España) 2006

Data Encryption Standard DES

DES (Data Encryption Standard) ha sido el estándar utilizado
mundialmente durante 25 años, generalmente en la banca. Hoy
presenta signos de envejecimiento y ha sucumbido a los diversos
criptoanálisis que contra él se viene realizando hace ya años.


FECHAS DE INTERÉS


1973: En EEUU la NBS National Bureaux of Standards llama a
concurso público para buscar un algoritmo criptográfico estándar.
1974: La NSA National Security Agency declara desierto el
primer concurso, publica unas segundas especificaciones y elige
Lucifer, algoritmo original de IBM (años 70) con variaciones.
1976: El DES se adopta como estándar y se autoriza para ser
utilizado en las comunicaciones no clasificadas del gobierno.

© Jorge Ramió Aguirre Madrid (España) 2006

Especificaciones del algoritmo DES

Especificaciones del concurso

• El nivel de seguridad computacional debe ser alto.
• El algoritmo debe ser fácil de entender y deberá estar

especificado en todos sus detalles.

• La seguridad del sistema no debe verse afectada por la

publicación y divulgación del algoritmo.

• Debe estar disponible para cualquier usuario.
• Deberá poder usarse en diferentes aplicaciones.
• Fabricación con dispositivos electrónicos de bajo costo.
• Se debe poder usar como validación.
• Debe ser exportable.

No se cumplen en 1973 pero sí en 1974, aunque ...

© Jorge Ramió Aguirre Madrid (España) 2006

El papel de la NSA en el DES

La NSA impone una limitación en la longitud de la clave:

De los 128 bits de Lucifer,
NSA deja la clave en 64
bits. Al final, la clave sólo
son 56 bits efectivos puesto
que al ser datos de 8 bits, se
conoce el bit de paridad.
Luego, el espacio de claves
es 256 = 7.2 ·1016, tan sólo
72 mil billones de valores.

© Jorge Ramió Aguirre Madrid (España) 2006

¿Por qué esta reducción?

Hay distintas versiones sobre esta
reducción del espacio de claves: una
habla de la dificultad de diseñar
chips capaces de operar de forma
eficiente con una clave de 128 bits
en esos años; la otra sobre una
política de seguridad interna para
proteger información sensible ante
ataques externos y ser capaces, no
obstante, de practicar criptoanálisis
en un tiempo razonable.

© Jorge Ramió Aguirre Madrid (España) 2006

Especificaciones técnicas finales del DES

• Bloque a cifrar: 64 bits
• Clave: 8 bytes (con paridad, no caracteres ASCII)
• Normas ANSI:

– X3.92: Descripción del algoritmo.
– X3.108: Descripción de los modos de operación

(ECB, CBC, OFB).

• Fácil implementación en un circuito integrado.

Veremos su descripción y modos de operación.

© Jorge Ramió Aguirre Madrid (España) 2006

Visión gen