criptosistema - departamento de ingeniería telemática
TRANSCRIPT
Tema 3: Cifrado simétrico 1
CRIPTOSISTEMA
ORIGEN ORIGEN DESTINO DESTINO
CIFRADO C=E(Kc ,M)
CANAL DE COMUNICACIÓN
DESCIFRADO M=D(Kd ,C)
Clave, K c Texto claro, M
Criptograma, C Criptograma
Clave, Kd Texto claro, M ADVERSARIO
CRIPTOANÁLISIS M ≈ (C,E,D,K c ,K d )
TERCERO DE CONFIANZA
CANAL SEGURO
Tema 3: Cifrado simétrico 2
TIPOS DE SEGURIDAD
Incondicional (teórica) Sistema seguro frente ataques con tiempo y
recursos ilimitados Computacional (práctica)
Sistema seguro frente ataques con tiempo y recursos limitados
Probable No se ha demostrado que el sistema sea
inseguro Condicional
Sistema seguro mientras no se tengan recursos para atacarlo
Tema 3: Cifrado simétrico 3
TIPOS DE SEGURIDAD
Incondicional (teórica) Sistema seguro frente ataques con tiempo y
recursos ilimitados Computacional (práctica)
Sistema seguro frente ataques con tiempo y recursos limitados
Probable No se ha demostrado que el sistema sea
inseguro Condicional
Sistema seguro mientras no se tengan recursos para atacarlo
RSA-200 Challenge (May 2005)
The number to factorize was
27.997.833.911.221.327.870.829.467.638.722.601.621.070.446.786.955.428.537.560.
009.929.326.128.400.107.609.345.671.052.955.360.856.061.822.351.910.951.365.788.637.105.954.482.006.576.775.098.580.557.613.579.098.734.950.144.178.863.178.946.295.187.237.869.221.823.983 (200 dígitos ~ 660 bits)
and its prime factors are
3.532.461.934.402.770.121.272.604.978.198.464.368.671.197.400.197.625.023.649.3
03.468.776.121.253.679.423.200.058.547.956.528.088.349
and
7.925.869.954.478.333.033.347.085.841.480.059.687.737.975.857.364.219.960.734.330.341.455.767.872.818.152.135.381.409.304.740.185.467
Tema 3: Cifrado simétrico 4
TIPOS DE SEGURIDAD
Incondicional (teórica) Sistema seguro frente ataques con tiempo y
recursos ilimitados Computacional (práctica)
Sistema seguro frente ataques con tiempo y recursos limitados
Probable No se ha demostrado que el sistema sea
inseguro Condicional
Sistema seguro mientras no se tengan recursos para atacarlo
RSA-200 Challenge (May 2005)
The number to factorize was
27.997.833.911.221.327.870.829.467.638.722.601.621.070.446.786.955.428.537.560.
009.929.326.128.400.107.609.345.671.052.955.360.856.061.822.351.910.951.365.788.637.105.954.482.006.576.775.098.580.557.613.579.098.734.950.144.178.863.178.946.295.187.237.869.221.823.983 (200 dígitos ~ 660 bits)
and its prime factors are
3.532.461.934.402.770.121.272.604.978.198.464.368.671.197.400.197.625.023.649.3
03.468.776.121.253.679.423.200.058.547.956.528.088.349
and
7.925.869.954.478.333.033.347.085.841.480.059.687.737.975.857.364.219.960.734.330.341.455.767.872.818.152.135.381.409.304.740.185.467
251959084756578934940271832400483985714292821262040320277771378
360436620207075955562640185258807844069182906412495150821892985
591491761845028084891200728449926873928072877767359714183472702
618963750149718246911650776133798590957000973304597488084284017
974291006424586918171951187461215151726546322822168699875491824
224336372590851418654620435767984233871847744479207399342365848
238242811981638150106748104516603773060562016196762561338441436
038339044149526344321901146575444541784240209246165157233507787
077498171257724679629263863563732899121548314381678998850404453
64023527381951378636564391212010397122822120720357 (RSA 2048 -
604 dígitos)
Premio: $200.000
Tema 3: Cifrado simétrico 5
Sólo texto cifrado
C D Espacio completo de claves (k1..kn)
M1
M2
…
Mn
¿M?
Texto cifrado y parte del texto en claro Ej: se cifra un texto de 8 caracteres ASCII
Si descifro con todas las claves… ¿cuántos ‘Mi’ serán válidos?
¿Cuántos textos cifrados necesito capturar para obtener la clave de cifrado?
ATAQUES DE SEGURIDAD
Tema 3: Cifrado simétrico 6
CIFRADO TRADICIONAL
Esteganografía: ocultación de la información
Técnicas de Sustitución: sustituir unos símbolos por otros
Técnicas de Transposición: cambio de orden de los símbolos dentro del texto
Cifrado evolutivo: Vernam (1918)
Técnicas combinadas: rotores (Scherbius 1918, Enigma 1930, etc.)
Tema 3: Cifrado simétrico 7
CRIPTOGRAFÍA CLÁSICA
Esteganografía: ocultación de la información dentro de otra información
Tema 3: Cifrado simétrico 8
CRIPTOGRAFÍA CLÁSICA
Técnicas de Sustitución: Cifrado monoalfabético: sustitución de símbolos
uno a uno Algoritmo de César (S. I A.C.): C=(M+2) mod 26 Sustitución Afín (caso general): C=(aM+b) mod n Cifrado simple: sustitución arbitraria (nº claves= n!)
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
V I N I V I D I V I N C I C C C C C C C C C C C C C X K P K X K F K X K P E K
X= (V+C) mod 26 23=(21+2) mod 26
Tema 3: Cifrado simétrico 9
CRIPTOGRAFÍA CLÁSICA
Técnicas de Sustitución: Cifrado monoalfabético: sustitución de símbolos
uno a uno Algoritmo de César (S. I A.C.): C=(M+2) mod 26 Sustitución Afín (caso general): C=(aM+b) mod n Cifrado simple: sustitución arbitraria (nº claves= n!)
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
V I N I V I D I V I N C I C C C C C C C C C C C C C X K P K X K F K X K P E K
X= (V+C) mod 26 23=(21+2) mod 26
Número de alfabetos que pueden generarse permutando n símbolos
FRECUENCIA DE APARICIÓN
Problema de monoalfabéticos: frecuencia de aparición de letras (mono/bi/tri-gramas)
10
Tema 3: Cifrado simétrico 11
CRIPTOGRAFÍA CLÁSICA
Cifrado homofónico: múltiples sustitutos para el mismo símbolo (habrá más sustitutos cuanto más frecuente sea el símbolo).
Cifrado de múltiples letras (bigramas o trigramas): Playfair (1854): cifra de dos en dos letras
– Matriz 5x5 de cifrado: escribir una clave sin letras repetidas y rellenar con el resto del alfabeto.
– Separar los caracteres del texto plano en parejas, incluyendo el carácter X entre dos caracteres iguales o al final para ajustar.
– Cada letra se sustituye por la letra que caiga en su posición dentro de la columna de su pareja.
– Si la pareja a cifrar está en la misma columna, se reemplaza cada una por la letra de debajo.
– Si la pareja a cifrar está en la misma fila, se reemplaza cada una por la letra que esté a su derecha.
Hill (1929)
Letra Homófonos A 17 19 34 41 56 60 67 83 I 08 22 53 65 88 90 L 03 44 76 N 02 09 15 27 32 40 59 O 01 11 23 28 42 54 70 80 P 33 91 T 05 10 20 29 45 58 64 78 99
cifrado P L A I N P I L O T 91 44 56 65 59 33 08 76 28 78
Tema 3: Cifrado simétrico 12
CRIPTOGRAFÍA CLÁSICA
Cifrado homofónico: múltiples sustitutos para el mismo símbolo (habrá más sustitutos cuanto más frecuente sea el símbolo).
Cifrado de múltiples letras (bigramas o trigramas): Playfair (1854): cifra de dos en dos letras
– Matriz 5x5 de cifrado: escribir una clave sin letras repetidas y rellenar con el resto del alfabeto.
– Separar los caracteres del texto plano en parejas, incluyendo el carácter X entre dos caracteres iguales o al final para ajustar.
– Cada letra se sustituye por la letra que caiga en su posición dentro de la columna de su pareja.
– Si la pareja a cifrar está en la misma columna, se reemplaza cada una por la letra de debajo.
– Si la pareja a cifrar está en la misma fila, se reemplaza cada una por la letra que esté a su derecha.
Hill (1929)
Tema 3: Cifrado simétrico 13
Texto plano: COMERCIO ELECTRONICO
EJEMPLO PLAYFAIR M A S T E R B C D F G H I/J K L N O P Q U V W X Y Z
CO ME RC IO EL EC TR ON IC OX BP AM BD HP FU SF MD PO PI PW
Mejora mucho con respecto a los monoalfabéticos (en total 26x26 = 676 bigramas)
Con un texto suficientemente largo, sigue siendo posible el criptoanálisis, pues mantiene mucha estructura
CRIPTOGRAFÍA CLÁSICA
Cifrado polialfabético: sustitución de símbolos en función de su posición en el texto Cifrado de Vigenère (1586): Ci= (Mi+Ki) mod 26 Cifrado de Beaufort (1710): Ci= (-Mi+Ki) mod 26
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P E T E R L E G R A N D I S A G O O D F R I E N D O F N A P O L E O N L E G R A N D E D G A R E D G A R E D G A R E D G A R E D G A R E D G A R E D G A R E D G A R E D T H Z E I P H M R R R G O S R K R U D W V L K N U S I T A G S O K O E P H M R R R G
T H I S I S T H E S A M E O L D S T U F F W I N D W I N D W I N D W I N D W I N D W D B F L O Q U W S Q N R S U C A E P T Y R
VIGENÈRE
BEAUFORT T=19, -T mod 26=7, W=22
(-T+W) mod 26= 29 mod 26= 3 = D (-D+W) mod 26= (23+22) mod 26= 19 = T
30
Tema 3: Cifrado simétrico 15
CRIPTOGRAFÍA CLÁSICA
Letras ordenadas por rango frecuencia (inglés)
Cifrado Playfair
Texto plano
Cifrado polialfabético aleatorio
Cifrado Vigenère
Tema 3: Cifrado simétrico 16
CRIPTOGRAFÍA CLÁSICA
Cifrado evolutivo Autoclave de Vigenère ( suma de textos) Vernam (1918): XOR del texto plano con una clave cíclica o
pseudo-aleatoria de la misma longitud
One-time pad: XOR del texto plano con clave aleatoria de la misma longitud
Seguridad incondicional: no hay relación texto claro/cifrado Sólo para un uso: la distribución de claves es un problema
Transposición: cambio de orden de los símbolos Rail fence (por filas): Por columnas:
Transposición genérica: la clave es el patrón de ordenación (transposición aleatoria)
C M R I E E T O I O O E C O L C R N C
Clave: 4 3 1 2 5 6 7 Texto plano: a t a q u e p
o s t p u e s t o h a s t a l a u n a a m
Texto cifrado: ATHUQPAHTSAOAOTLUUSAEETAPSAM
CMRIEETOIOOECOLCRNC
Tema 3: Cifrado simétrico 17
CRIPTOGRAFÍA CLÁSICA
Cifrado evolutivo Autoclave de Vigenère ( suma de textos) Vernam (1918): XOR del texto plano con una clave cíclica o
pseudo-aleatoria de la misma longitud
One-time pad: XOR del texto plano con clave aleatoria de la misma longitud
Seguridad incondicional: no hay relación texto claro/cifrado Sólo para un uso: la distribución de claves es un problema
Transposición: cambio de orden de los símbolos Rail fence (por filas): Por columnas:
Transposición genérica: la clave es el patrón de ordenación (transposición aleatoria)
C M R I E E T O I O O E C O L C R N C
Clave: 4 3 1 2 5 6 7 Texto plano: a t a q u e p
o s t p u e s t o h a s t a l a u n a a m
Texto cifrado: ATHUQPAHTSAOAOTLUUSAEETAPSAM
CMRIEETOIOOECOLCRNC
Tema 3: Cifrado simétrico 18
MÁQUINAS DE ROTORES
Son cifradores eletromecánicos que se usaron entre 1930 y 1950: Enigma (Alemania), Sigaba (EEUU), Purple y Red (Japón), Hagelin (Suecia)
Cada rotor corresponde a un cifrado de sustitución
La salida de un rotor es la entrada del siguiente
Después de cada símbolo, el rotor ‘rápido’ gira
Después de una rotación entera, gira el rotor adyacente Una máquina de ‘n’ rotores genera un
cifrado polialfabético de período 26n
Tema 3: Cifrado simétrico 19
MÁQUINA ENIGMA
Tema 3: Cifrado simétrico 20
MÁQUINA ENIGMA dirección del giro dirección del giro
rotor lento rotor medio rotor rápido rotor lento rotor medio rotor rápido
disposición inicial disposición tras una pulsación
Tema 3: Cifrado simétrico 21
FILMOGRAFÍA
Tema 3: Cifrado simétrico 22
Clave secreta: Cifrado simétrico
Cifradores de flujo Cifradores de bloque
Códigos de autentificación de mensajes (MACs) Mecanismos de autentificación e intercambio de claves
Clave pública: Cifradores asimétricos Firmas digitales Mecanismos de autentificación e intercambio de claves
Sin clave: Funciones hash
CRIPTOGRAFÍA MODERNA
S
Tema 3: Cifrado simétrico 23
La clave de cifrado y la de descifrado son iguales
CIFRADOR M C
DESCIFRADOR C M
K
CIFRADO SIMÉTRICO
Tema 3: Cifrado simétrico 24
Cifrador de bloque: Esquema de cifrado que divide el texto plano en trozos (bloques)
de tamaño fijo y los cifra de forma independiente
Cifrador de flujo: Cifra ristras de bits de forma continua y de tal forma que cada
operación de cifrado depende también del cifrado anterior
CIFRADOR DE
BLOQUE K
M1, M2, …, Mn C1, C2, …, Cn Ci= fK(Mi)
CIFRADOR DE
FLUJO K
M1, M2, …, Mn C1, C2, …, Cn Ci= fK(Mi, Mi-1, …, M1)
MEMORIA
TIPO DE CIFRADORES
Tema 3: Cifrado simétrico 25
CONFUSIÓN Y DIFUSIÓN
Confusión: el texto cifrado depende de la clave y del texto plano de la forma más
complicada posible Conseguido por sustitución
Difusión: los caracteres del mensaje se ven mezclados y redistribuidos al cifrarlos
Conseguido por transposición
Los cifradores modernos aplican una serie de rondas (iteraciones) para conseguir ambos efectos:
La dependencia del texto cifrado, la clave y el texto plano es muy complicada
La variación de 1 bit en el texto plano o la clave conlleva una variación del 50% del texto cifrado (avalancha)
SAC: Strict Avalanche Criterion
Tema 3: Cifrado simétrico 26
SUSTITUCIÓN ALEATORIA
La seguridad que proporcionan los mecanismos de sustitución aleatoria sería suficiente
Para un alfabeto de ‘s’ símbolos ordenados, hay s! formas de cambiar su orden (biyecciones posibles)
La clave serían los ‘s’ símbolos reordenados
Si se tiene un bloque de ‘n’ bits, habría 2n símbolos en el alfabeto y el tamaño de la clave sería de n·2n bits
Para n=64 bits la clave ocuparía del orden de 1021 bits Solución: cifradores de producto, que intercalan
sustituciones simples y transposiciones
00 01 10 11
01 10 11 00
Alfabeto de 4 símbolos
(2 bits)
24 posibles ordenaciones
La ordenación elegida sería la clave
01101100
Tema 3: Cifrado simétrico 27
CIFRADO SIMÉTRICO: DES
Origen: concurso del NBS (1973) Lucifer de IBM (1975) Adoptado en 1977 (FIPS46) hasta 1998 (FIPS46-3) Debilidad: longitud de la clave.
1977: 20 millones $ para romperlo en 24 horas 1993: 1 millón $ para romperlo en 3 horas 1997: 1er desafío RSA (96 días) 1998: EFF (210.000 $), 56 horas 1999: DesCrack, 22 horas AES1 (1998), AES2 (1999), AES3 (2000) 2001: Rijndael (AES-FIPS197) sustituye oficialmente a DES 2004: se propone la retirada del FIPS46-3
National Bureau of Standards, ahora NIST: National Institute of Standards and Technology
Tema 3: Cifrado simétrico 28
CIFRADO SIMÉTRICO: DES
Origen: concurso del NBS (1973) Lucifer de IBM (1975) Adoptado en 1977 (FIPS46) hasta 1998 (FIPS46-3) Debilidad: longitud de la clave.
1977: 20 millones $ para romperlo en 24 horas 1993: 1 millón $ para romperlo en 3 horas 1997: 1er desafío RSA (96 días) 1998: EFF (210.000 $), 56 horas 1999: DesCrack, 22 horas AES1 (1998), AES2 (1999), AES3 (2000) 2001: Rijndael (AES-FIPS197) sustituye oficialmente a DES 2004: se propone la retirada del FIPS46-3
Tema 3: Cifrado simétrico 29
PROPIEDADES DEL DES
Cifrador de bloque Sólo hardware hasta 1981
DEA (Data Encryption Algorithm) ANSI X9.32
Tamaño del bloque = 64 bits Tamaño de la clave = 56 bits Efecto avalancha del 50% Claves débiles (4) Ekd[Ekd(M)]=M Claves semidébiles (12) Eks2[Eks1(M)]=M
DES
M (64 bits)
C (64 bits)
K (56 bits)
Tema 3: Cifrado simétrico 30
PROPIEDADES DEL DES
Cifrador de bloque Sólo hardware hasta 1981
DEA (Data Encryption Algorithm) ANSI X9.32
Tamaño del bloque = 64 bits Tamaño de la clave = 56 bits Efecto avalancha del 50% Claves débiles (4) Ekd[Ekd(M)]=M Claves semidébiles (12) Eks2[Eks1(M)]=M
DES
M (64 bits)
C (64 bits)
K (56 bits)
0000000 0000000 1111111 1111111 0000000 1111111 1111111 0000000
Tema 3: Cifrado simétrico 31
secretos
01110011 01100101 01100011 01110010 01100101 01110100 01101111 01110011
73 65 63 72 65 74 6f 73 115 101 99 114 101 116 111 115
|ÒÊ�ü" 7c d2 1f ca 81 fc 22 c2 124 210 31 202 129 252 34 194
01111100 11010010 00011111 11001010 10000001 11111100 00100010 11000010
DES
‘claveuno’: 63 6c 61 76 65 75 6e 6f
TEXTO PLANO CÓDIGO ASCII CÓDIGO ASCII EN HEXADECIMAL
CÓDIGO ASCII EN BINARIO
CLAVE EN ASCII EN HEXADECIMAL
TEXTO CIFRADO
EJEMPLO DE CIFRADO DES
Tema 3: Cifrado simétrico 32
0101101010111011
0101101010111011
0101101010111011
0101101010111011
Texto plano
0101101010111011
0101101010111011
Iteración 2
Iteración 3
Iteración 4
Iteración 1
Iteración n
Texto cifrado
…
0101101010111011
ITERACIONES
Tema 3: Cifrado simétrico 33
ESTRUCTURA DE BLOQUES DES
Tema 3: Cifrado simétrico 34
ESTRUCTURA DE BLOQUES DES
Iteración 1 bit 38 → bit 17
Tema 3: Cifrado simétrico 35
ESTRUCTURA INTERNA
Tema 3: Cifrado simétrico 36
ESTRUCTURA INTERNA
Tema 3: Cifrado simétrico 37
ESTRUCTURA INTERNA
Tema 3: Cifrado simétrico 38
ESTRUCTURA INTERNA
Tema 3: Cifrado simétrico 39
Cifradores de bloque Esquema de cifrado que divide el texto plano en trozos
(bloques) de tamaño fijo y los cifra de forma independiente.
Más fáciles de construir que los cifradores de flujo Si el tamaño de los datos a cifrar es menor que el
tamaño de bloque relleno (padding)
Si el tamaño de los datos a cifrar es mayor que el tamaño de bloque modos de operación
CIFRADOR DE
BLOQUE K
M1, M2, …, Mn C1, C2, …, Cn Ci= fK(Mi)
MODOS DE OPERACIÓN
Tema 3: Cifrado simétrico 40
RELLENO
El mecanismo de relleno no es exclusivo de los algoritmos de cifrado
Ej.: Ethernet necesita alinear, etc.
Introduce redundancia Debe tener un formato conocido para poderlo
eliminar en el receptor
Disminuye la eficiencia del cifrado Relación Texto plano/Texto cifrado
Es necesario Si no se usa hay que esperar a recibir más bits
para poder cifrar el bloque completo
Tema 3: Cifrado simétrico 41
Ejemplo de relleno: Poner patrón de datos conocido al final (rellenar
con ‘1’ o con ‘0’ o con una secuencia alterna de ‘0’ y ‘1’)
Problema: ¿y si el texto plano tiene el formato del relleno?
PKCS#5 (RFC2630, sección 6.3) Se rellena con los octetos necesarios, conteniendo
cada octeto añadido la representación binaria del número de octetos añadido
Problema: ¿y si el texto plano no necesita relleno y contiene un patrón de relleno?
RELLENO
Tema 3: Cifrado simétrico 42
Ejemplo de relleno: Poner patrón de datos conocido al final (rellenar
con ‘1’ o con ‘0’ o con una secuencia alterna de ‘0’ y ‘1’)
Problema: ¿y si el texto plano tiene el formato del relleno?
PKCS#5 (RFC2630, sección 6.3) Se rellena con los octetos necesarios, conteniendo
cada octeto añadido la representación binaria del número de octetos añadido
Problema: ¿y si el texto plano no necesita relleno y contiene un patrón de relleno?
RELLENO
Alineación a 32 bits del texto plano 10010101:
10010101 00000011 00000011 00000011
Tema 3: Cifrado simétrico 43
Electronic Code Book (ECB) Útil para cifrado de información muy reducida, sin
regularidades estructurales (ej. claves)
Cipher Block Chaining (CBC) Útil para transmisiones orientadas a bloques
Cipher Feedback (CFB) Útil para transmisiones de flujos continuos
Output Feedback (OFB) Útil para transmisiones de flujos continuos en
medios ruidosos
MODOS DE OPERACIÓN
Tema 3: Cifrado simétrico 44
E mi ci
K
D mi ci
K
E mi ci
64 bits
+
ci -1
K
D ci mi
64 bits
+
ci -1
K
ECB (Electronic CodeBook Mode)
CBC (Cipher Block Chaining Mode)
MODOS DE OPERACIÓN
m1
m2
m3
c0
c1 c1
c0
Tema 3: Cifrado simétrico 45
E mi ci
K
D mi ci
K
E mi ci
64 bits
+
ci -1
K
D ci mi
64 bits
+
ci -1
K
ECB (Electronic CodeBook Mode)
CBC (Cipher Block Chaining Mode)
MODOS DE OPERACIÓN
m1 m2
m3
c1
c2 c1
c0
c2 c1
Tema 3: Cifrado simétrico 46
E mi ci
K
D mi ci
K
E mi ci
64 bits
+
ci -1
K
D ci mi
64 bits
+
ci -1
K
ECB (Electronic CodeBook Mode)
CBC (Cipher Block Chaining Mode)
MODOS DE OPERACIÓN
m2
m3
c2 c1
c2 c2 c3 c3
Tema 3: Cifrado simétrico 47
E mi ci
K
D mi ci
K
E mi ci
64 bits
+
ci -1
K
D ci mi
64 bits
+
ci -1
K
ECB (Electronic CodeBook Mode)
CBC (Cipher Block Chaining Mode)
MODOS DE OPERACIÓN
m1
c0
c1 c1
m1
m2
m3
Tema 3: Cifrado simétrico 48
E mi ci
K
D mi ci
K
E mi ci
64 bits
+
ci -1
K
D ci mi
64 bits
+
ci -1
K
ECB (Electronic CodeBook Mode)
CBC (Cipher Block Chaining Mode)
MODOS DE OPERACIÓN
m2
c1
c2 c2 c3
m1
m2
m3
Tema 3: Cifrado simétrico 49
c3
E mi ci
K
D mi ci
K
E mi ci
64 bits
+
ci -1
K
D ci mi
64 bits
+
ci -1
K
ECB (Electronic CodeBook Mode)
CBC (Cipher Block Chaining Mode)
MODOS DE OPERACIÓN
m3
c2
c3
m1
m2
m3
Tema 3: Cifrado simétrico 50
ECB, CBC
ECB Uso directo del algoritmo como cifrador de bloque Útil para mensajes cortos La modificación de 1 bit se propaga a todo el
bloque CBC
Utiliza un vector de inicialización (C0 o Vi) Encadena el cifrado de los diferentes bloques
Bloques iguales se cifrarán de forma diferente Propagación de errores a un bloque adicional Autosincronización
Modificación o pérdida de bloques
Tema 3: Cifrado simétrico 51
mi ci +
64 bits
Descarte
E 64 b
64 b
‘n’ bits
‘n’ bits
‘n’ bits ‘n’ bits ‘n’ bits mi ci +
64 bits
Descarte
E 64 b
64 b
‘n’ bits
‘n’ bits
‘n’ bits
‘n’ bits mi ci +
64 bits
Descarte
E 64 b
64 b ‘n’ bits
‘n’ bits mi
‘n’ bits ci +
64 bits
Descarte
E 64 b
64 b ‘n’ bits
‘n’ bits
CFB (Cipher FeedBack Mode)
OFB (Output FeedBack Mode)
MODOS DE OPERACIÓN
Tema 3: Cifrado simétrico 52
CFB, OFB
CFB El tamaño de bloque es variable (múltiplo de 8)
Se aproxima más al funcionamiento de un cifrador de flujo Disminuye la eficiencia del cifrado
Ej: n=8 cada byte exige un cifrado diferente Propagación de errores a un bloque de 64 bits Autosincronizante:
Modificación o pérdida de bloques
OFB El cifrador y descifrador son idénticos Se utiliza el algoritmo como generador de una secuencia
pseudo-aleatoria (que puede precomputarse) No hay propagación de errores No hay autosincronización frente a pérdidas de bloques
Tema 3: Cifrado simétrico 53
DOBLE DES
Objetivo aumentar el tamaño efectivo de la clave aplicando
DES de forma sucesiva varias veces
Cifrado DES
M
Cifrado DES
K1
K2
C
K1, K2 Descifrado
DES
C
Descifrado DES
K2
K1
M
K1, K2
Tema 3: Cifrado simétrico 54
DOBLE DES
Ataque ‘meet-in-the-middle’ X=EK1[M]=DK2[C] Conseguir un par M/C Cifrar M con las 256 posibles K1 y descifrar C con
las 256 posibles K2 ¿Habrá coincidencias? Hay 2112 posibles claves y sólo 264 salidas
Dado un par M/C, el número de dobles claves que hacen C=EK2[EK1[M]] puede ser de 2112/264 = 248
Capturado otro par M’/C’, el ratio de falsas alarmas se reduce a 248/264 = 1/216
Tamaño efectivo de la clave: 257
Tema 3: Cifrado simétrico 55
TRIPLE DES (TUCHMAN 79)
Compatibilidad con DES (K=K1=K2)
Cifrado DES
M
Descifrado DES
K1
K2
Cifrado DES
K1
C
K1, K2
Descifrado DES
C
Cifrado DES
K1
K2
Descifrado DES
K1
M
K1, K2
Tema 3: Cifrado simétrico 56
No ha sido posible criptoanalizar DES por completo
Debilidad: longitud de la clave (fuerza bruta) 1977: 20 millones $ para romperlo en 24 horas 1993: 1 millón $ para romperlo en 3 horas 1997: 1er desafío, resuelto en 96 días (DESCHALL) 1998: 2º desafío, resuelto en 56 horas por EFF (210.000 $) Inicio del proceso AES (se recomienda ya TDES) 1999: 3er desafío, resuelto en 22 horas (Descrack) AES2 (1999), AES3 (2000) 2001: Rijndael (AES-FIPS197) sustituye oficialmente a DES 2004: se propone la retirada del FIPS46-3
ELECCIÓN DE OTRO ESTÁNDAR
Tema 3: Cifrado simétrico 57
AES: RIJNDAEL
AES (Advanced Encryption Standard) en 2001 Creadores: Vincent Rijmen y Joan Daemen Criterios de diseño: no sigue la estructura
Feistel, simplicidad, velocidad, seguridad Bloque 128 y clave 128, 192 y 256 bits Iteración:
Add Round Key: XOR de la subclave de iteración Byte Sub: sustitución de cada byte del bloque Shift Row: desplazamiento de filas Mix Column: reordenación de columnas
Número de iteraciones en función del tamaño de la clave: 10, 12 ó 14
ARK
BSB SR MC
ARK ...
BSB SR
ARK
Tema 3: Cifrado simétrico 58
ESTRUCTURA RIJNDAEL
Tema 3: Cifrado simétrico 59
FIPS 197: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Tema 3: Cifrado simétrico 60
EJEMPLO AES
Tema 3: Cifrado simétrico 61
DISTRIBUCIÓN DE CLAVES
Envío físico Seguro pero de relativa utilidad
Uso de una clave antigua EKs[Ks+1] Con capturar una de las claves el sistema falla
por completo
Uso de una clave específica Hace falta un protocolo adicional que proporcione
protección a la distribución
Tercero de confianza Complica el mecanismo de distribución
Tema 3: Cifrado simétrico 62
ENVÍO DIRECTO
(1) EKab[KS]
(1) EKab[KS || TA || B]
A B
A B
Tema 3: Cifrado simétrico 63
ENVÍO DIRECTO (II)
(1) NA
(2) EKab[KS || NA || NB || A]
(3) EKs[NB]
A B
Tema 3: Cifrado simétrico 64
B C
A D
E F
Número de claves necesarias (que hay que intercambiar y almacenar):
N= 100 nodos 5000 N=1000 nodos 500000
DISTRIBUCIÓN DE CLAVES
Tema 3: Cifrado simétrico 65
NEEDHAM-SCHROEDER
(2) EKa[KS || B || NA || EKb[KS || A]]
(1) A || B || NA
(3) EKb[KS || A]
(4) EKs[NB]
(5) EKs[f(NB)]
A B
KDC
Tema 3: Cifrado simétrico 66
CONCLUSIONES
El cifrado asimétrico NO es más seguro que el cifrado simétrico
Para obtener un grado similar de seguridad: Cifrado simétrico: claves de 128 bits Cifrado asimétrico: claves de 1024 bits
Es bastante más lento que el cifrado simétrico 1000 veces en hardware y 100 veces en software.
No sustituye al cifrado simétrico. Se usan para cosas distintas y son complementarios
Cifrado simétrico: sirve para cifrar la información con una clave de sesión
Cifrado asimétrico Permite intercambiar claves de sesión Firmas digitales
Tema 3: Cifrado simétrico 67
BIBLIOGRAFÍA
Cryptography and network security. Principles and Practice. Fouth edition Williams Stallings. Prentice Hall. 2006 http://williamstallings.com/
Network security : private communication in a public world C. Kaufman, R. Perlman, M. Speciner, E. Cliffs. Prentice Hall, 1995
Handbook of applied cryptography Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone.2001. http://www.cacr.math.uwaterloo.ca/hac/
The Codebreakers David Kahn. Scribner. 1996. http://david-kahn.com/