1
Criptografía
DefinicionesDefinicionesConceptos previos
CriptografíaDefinicionesBases teóricasBases teóricasCriptografía clásicaClasificación de CriptosistemasCriptosistemas Simétricos
ClasificaciónCifradores de bloquesCifradores de flujo
Algoritmos de cifrado: DES, AES, IDEA, RC5
Ataques por fuerza brutaAtaques por fuerza brutaFunciones de Hash o resumen: MD5, SHA-1Criptosistemas Asimétricos
Algoritmos: Diffie-Hellman, ElGammal, RSAFirma digitalSeguridad en el correo electrónico: PGP, S/MIMECertificados digitales
2
DefinicionesCriptografía: “Arte de escribir con clave secreta o de un modo
i áti ”enigmático”
Imprecisiones:Arte: la criptografía ha dejado de ser un arte: es una ciencia.Escritura de documentos: no sólo se escriben mensajes; se envían o se guardan en un computador diversos tipos de documentos y formatos.Se supone una clave: los sistemas actuales usan una o dos. En varias aplicaciones de Internet entran en juego 4 claves.Clave secreta: existirán sistemas de clave secreta que usan una solaClave secreta: existirán sistemas de clave secreta que usan una sola clave y sistemas de clave pública (muy importantes) que usan dos: una clave privada (secreta) y la otra pública.Representación enigmática: la representación binaria de la información podría ser enigmática para nosotros los humanos pero no para los computadores... es su lenguaje natural.
Definiciones
Criptografía:Criptografía: Kriptos (secreto) y Graphos (escritura) Forma de escribir ocultando el significado
Criptoanálisis:Forma de esclarecer el significado de la escritura ininteligible
CriptologíaKriptos (secreto) y Logos (estudio, conocimiento)Criptografía + Criptoanálisis
3
Criptosistema: Componentes básicos
Espacio MensajesM = {m1, m2, …, mm}Conjunto mensajes en claro
Espacio de CifradosC = {c1, c2, …, cc}
Espacio de clavesK = {k1, k2, …, kk}
Transformaciones de cifradoEk: M→C
Transformaciones de descifradoDk: C→M
CriptografíaCaracterización sistema criptográfico:
operaciones de encriptaciónsustitucióntransposición
número de clavesSistema simétrico (clave única o secreta)Sistema asimétrico (dos claves o clave pública)
procesado texto en clarobloqueflujo
4
CriptografíaTexto Texto Clave Compartida
Canal
Texto Cifrado
Claro Claro
Cifrado Simétrico
Cifrado Asimétrico
Criptografía
Tipos de ataquesTipos de ataques
CriptoanálisisSólo texto cifradoTexto claro conocidoEl ió d j
Complejidad
Elección de mensaje
Fuerza bruta
5
Seguridad criptosistemas
Incondicionalmente seguroIncondicionalmente seguroTexto cifrado no proporciona suficiente información para determinar la clave o el texto en claro.
Computacionalmente seguroCoste rotura cifrado > Coste información cifradaCoste rotura cifrado > Coste información cifradaTiempo rotura cifrado > Vida útil información
Ataques por fuerza brutaTiempo medio requerido para búsqueda de claves exhaustiva
BitsClave
Claves posiblesTiempo Requerido(1 descifrado / μs )
Tiempo Requerido(106 descifrados / μs )
32 232 = 4.3 x 109 231 μs = 35.8 minutos 2.15 milisegundos
56 256 = 7.2 x 1016 255 μs = 1142 años 10.01 horas
128 2128 = 3.4 x 1038 2127 μs = 5.4 x 1024 años 5.4 x 1018 años
168 2168 = 3.7 x 1050 2167 μs = 5.9 x 1036 años 5.9 x 1030 años
26 caracteres(permutación) 26! = 7.2 x 1026 2x1026 μs = 6.4 x 1012 años 6.4 x 106 años
6
Ataques por fuerza bruta
L0phtCrack – LC5L0phtCrack LC5Plataforma Windows/Unixhttp://webproxy.com/products/lc/Ataques de diccionario y fuerza bruta
PasswordsPro y SAMInside Plataforma Windowshttp://www.insidepro.com/eng/index.shtmlAtaques diccionario y fuerza bruta
John the Ripper
Bases TeóricasPilares Fundamentales:
Teoría de la Información de ShannonInformación contenida mensajes y claves.Entropía
Teoría de NúmerosOperaciones de matemática discreta, logaritmos, etc.
Teoría de la Complejidad AlgorítmicaClasificación de los problemas como computacionalmente tratables o intratables.
7
Bases TeóricasTeoría de la Información de Shannon
C tid d d I f ióCantidad de Información
Entropía
)(log2 ii xpC −=1
ci
pi
0
0
)(log)()( 2 ii
i xpxpxH ∑ ⋅−=
Bases TeóricasTeoría de la Información de Shannon
R ti d l l jRatio del lenguaje
Redundancia
NMHr )(
=
Redundancia
rRD −=
8
CriptografíaCriptografía clásica procesado texto en claro
EscítalaPolybiosCifrado tipo César
operaciones de encriptación
sustituciónmonoalfabetopolialfabeto
bloqueDES
flujo
número de claves
clave privada
clave públicapolialfabeto
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
Criptografía clásica: escítalaSiglo V a.C. Pueblo griego de los lacedemonios.
Consistía en un bastón en el que se enrollaba una cinta de cuero y luego se escribía en ella el mensaje de forma longitudinal.
Cifrado por transposición: Al desenrollar la cinta, las letras aparecerán desordenadas.
Para descifrar el criptograma y recuperar el mensaje en claro habrá que enrollar dicha cinta en un bastón con el mismo diámetro que el usado en el extremo emisor y leer el mensaje de forma longitudinal. La clave del sistema se encuentra en el diámetro del bastón.
M = ASI CIFRABAN CON LA ESCITALA
C = AAC SIN ICT COA INL FLA RA AE BS
9
Criptografía clásica: PolybiosSiglo II a.C.
Cifrado por sustitución
El método se basa en una tabla, en cuyos ejes se ponían diferentes combinaciones de letras o números y dentro de la tabla las letras del alfabeto. Cada letra del mensaje a cifrar era sustituida por sus “coordenadas”
M = Polybios es el rey
C = CECDCAEDABBDCDDC AEDC AECA DBAEED
Criptografía clásica: CésarSiglo I a.C.
Desplazamiento de tres espacios (k=3) hacia la derecha de M
Es un cifrador por sustitución en el que las operaciones se realizan módulo n, (n = al número de elementos de M)
M = 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 zC = D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Ejemplo: M = BOMBA C = ERPED
Problema: cada letra se cifra siempre igual
Criptoanálisis usando estadísticas de M
10
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios, Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
Métodos monoalfabeto: PlayfairSiglo XIX
Intento de romper traslación estadísticas de M a C
Cifrado por poligramas. Matriz 5x5
CifradoM1M2 misma fila C1C2 son los dos caracteres de la derecha.ON/ÑMKI/J
HGFDB
EVALC
M1M2 misma columna, C1C2 son los dos caracteres de abajo.
M1M2 filas y columnas distintas C1C2 son los dos caracteres de la diagonal, desde la fila de M1.
ZYXWU
TSRQP
ON/ÑMKI/J
Ejemplo: M = BOMBA VA M = BO MB AV AX
C = HI IF VE FA
11
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
VigenèreCifrado por substitución polialfabetop pSoluciona la debilidad del cifrado César en que una letra se cifra siempre igual. Clave K de longitud L equivale a L cifrados Cesar
Cifrado : C(i) = M(i) + K(i) mod 27
Sea K = SOL y M = BOMBA VIENEM = B O M B A V I E N E M = A B C D E F G H I …K = S O L S O L S O L S A1 = S T U V W X Y Z A …C = T C X T O G A S Y W A2 = O P Q R S T U V W …
A3 = L M N O P Q R S T …
12
Vigenère: criptoanálisis
Longitud claveLongitud claveMétodos
Kasiskisufijos: -ez, -as, -os, …prefijos: in-, des-, en-, …palabras : con, y, de, el
M = DESCONFIANZA CON EL NUEVOK = GINGINGINGIN GIN GI GINGIC = JMFIWZLPNSHN IWZ KT SCSBW
9 caracteres
Índice de Coincidenciafrecuencia C vs. frecuencia MVarianza = = 0 ≤ MD ≤ 0.035
C = JMFIWZLPNSHN IWZ KT SCSBW
2
1)1(∑
=
−n
ii np 037.0)(
1
2 −∑=
n
ii
pÍndice de Coincidencia
(0.072)
Vigenère: mejoras
Cifrado autoclaveCifrado autoclavelongitud K = longitud MM = Enunlugardelamancha…K = Cervantesenunlugard…
One-Time PADOne Time PADlongitud K = longitud Mclave aleatoriano reutilización de claves
13
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios, Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
Rail Fence
Escritura de M en diagonalEscritura de M en diagonalLeer texto fila a fila
M = Con cien cañones por banda, viento en popa…
C c n ñ e o a a i t n p .o i c o s r n , e o p a .o i c o s r n , e o p a .n e a n p b d v n e o . .
C = ccnñeoaaitnpoicosrn,eopaneanpbdvneo
14
Transposición de filas
M se escribe en filas a lo largo de n columnasM se escribe en filas a lo largo de n columnasK = ordenación de las columnasC = reordenación de M según K
M = Con cien cañones por banda, no corta…
K = 4 3 1 2 5 6 7C O N C I E N
M = 01 02 03 04 05 06 07 08 09 10 1112 13 14 15 16 17 18 19 20 21C O N C I E N
C A Ñ O N E SP O R B A N D
C = NÑRCOBOAOCCPINAEENNSD
C1 = 03 10 17 04 11 18 02 09 16 01 0815 05 12 19 06 13 20 07 14 21
C2 = 17 01 13 04 08 20 10 16 06 03 0919 11 15 07 18 05 14 02 12 21
Repetir trasposición para incrementar seguridad
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios, Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
15
Product CiphersCifrado por substitución o transposición no seguro debido a características del lenguajeseguro debido a características del lenguaje
Concatenación cifrados2 substituciones substitución más compleja2 transposiciones transposición más complejasubstitución + transposición mucho más compejosubstitución transposición mucho más compejo
Puente entre criptografía clásica y moderna
Máquinas de Rotor
Ejemplo complejidad a través de múltiples etapas de cifradoEjemplo complejidad a través de múltiples etapas de cifradocifrado por substitución variable
Segunda Guerra MundialAlemanes (Enigma), Aliados (Hagelin), Japoneses (Purple)
Rotorposición determina la substituciónvaría después cifrado de cada letravaría después cifrado de cada letraencadenado a otros rotores
Ej: 3 rotores (26 letras) 263=17.576 alfabetos
16
Máquinas de Rotor: enigma5 posibles rotoresp
C5,3 * P3 = 60 posibilidades
ConfiguraciónRotores EscogidosPosición Inicial RotoresAnillos GiroAnillos GiroStecker (10 pares intercambio)Total ≈ 1023 combinaciones
Criptoanálisis: cribas
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios, Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
17
Cifrado en Bloque vs. en Flujo
Cifrado en bloqueCifrado en bloqueTexto se procesa en bloques (o palabras)Cada bloque se (des)encripta conjuntamenteBloque típico: 64 o 128 bitsAmpliamente usados
Cif d fl jCifrado en flujo(Des)Encriptación se aplica a un elemento de información (caracter, bit)
Comparativa de cifra: bloque vs flujoCIFRADO EN BLOQUE
Ventajas Inconvenientes
Alta difusión de los elementosen el criptogramaInmune: imposible introducir bloques extraños sin detectarlo
Baja velocidad de cifrado al tenerque leer bloque completoErrores de cifra: un error se propagará a todo el bloque
j
CIFRADO EN FLUJO
Alta velocidad de cifraResistente a errores: cifra no esdependiente entre elementos
Ventajas Inconvenientes
Baja difusión elementos en elcriptogramaVulnerable: pueden alterarse loselementos por separado
18
Cifrado en bloque ideal
Estructura cifrado FeistelTexto claro (2w bits)
Clave
Algoritmo de generaciónde subclaves
Etapa 1de subclaves
Etapa i
Etapa n
Texto cifrado (2w bits)
Etapa n
19
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios, Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
DES: Data Encryption StandardFue desarrollado por IBM a principios de los 70 como continuación del algoritmo Lucifer.Adoptado por NIST como algoritmo estándar de cifrado. Actualmente estándar de ANSIDES di ñó d f f i t t l i t áli i d á ill dDES se diseñó de forma que, fuera resistente al criptoanálisis y además sencillo para poderser implementado en un circuito electrónico con la tecnología de los años 70Cifra en bloques de 64 bits de texto claro, produciendo bloques del mismo tamaño de textocifrado. (es un cifrador de bloques)El tamaño de la clave es de 56 bits (256 posibles combinaciones)
Ha suscitado gran controversia:Tamaño de la clave 56 bits (Lucifer 128bits)Ciertos aspectos de su diseño están clasificados
Disposición de bits en una clave DES
20
Clave de 56 bitsTexto claro de 64 bits
Opción 1
DES: Data Encryption StandardEstructura Feistel
Permutación inicial Opción 1permutada
Opción 2permutada
Opción 2permutada
O ió 2
Etapa 1
Etapa 2
Rotación ala izquierda
Rotación ala izquierda
Pasos:
Permutación inicial p(x)x0 = p(x) = L0R0
16 iteraciones :Li= R
Representación general del algoritmo de cifrado DES
Texto cifrado de 64 bits
Permutación inicialinversa
Opción 2permutadaEtapa 16
Intercambiode 32 bits
Rotación ala izquierda
Li= Ri−1,Ri = Li−1 (+) f(Ri−1, ki)
Permutación inversa p(x)
y = p−1(R16L16)
DES: Efecto Avalancha Propiedad altamente deseablep
Alta variabilidad del cifrado ante pequeños cambios enclave texto en claro
Promedio DES:Cambio 1 bit entrada o claveCambio 1 bit entrada o claveCambio mitad bits texto cifrado
DES presenta alto efecto avalancha
Dificulta criptoanálisis
21
Criptoanálisis fuerza brutaAñ
os p
ara
rom
per e
l cód
igo
Longitud de la clave (bits)
Variantes de DES: Triple DES K1 K2 K3 K3 K2 K1
Se utilizan 3 claves (K1, K2, y K3)3 etapas:
El texto en claro se cifra con K1
S f
E D E P C D E D C P A ABB
DES modo de descifrado, usando K2
Se realiza otro cifrado usando K3
Existen variantes con claves de 168 bitsSe utilizan tres claves en lugar de dos(FIPS)
22
Algoritmo Rijndael. AES
El 12 de septiembre de 1997 el National Institute ofStandars and Technology (NIST), hace unllamamiento público para la presentación dealgoritmos candidatos al Advanced EncryptionStandard (AES)
Se establecen unos requisitos mínimos:Se establecen unos requisitos mínimos:El algoritmo debe ser de clave secreta (simétrico)El algoritmo debe ser un algoritmo de bloqueEl algoritmo debe ser capaz de soportar las combinaciones clave-bloque de los tamaños 128-128, 192-128 y 256-128
AES Evaluation Criteria
Criterios iniciales:Criterios iniciales:seguridad (esfuerzo requerido criptoanálisis)coste (eficiencia computacional)algoritmo & caracterísiticas implementación
Criterios finalesid d lseguridad general
facilidad implementación software y hardwareataques a la implementaciónflexibilidad (des/cifrado, clave, etc.)
23
Algoritmo Rijndael. AES (y II)
Diseñado por Joan Daemen y Vincent RijmenDiseñado por Joan Daemen y Vincent RijmenAdoptado por el NIST en Octubre del 2000 como algoritmo criptográfico no militarSu elección, desarrollo y estudio se realizó de forma pública y abiertaT ñ d l i bl 128 192 256 bitTamaño de clave variable: 128, 192 y 256 bitsSe considera más rápido y seguro que Triple DES
Modo CFB (Cipher Feedback)Modos operación cifra en bloques
Modo CBC (Cipher Block Chaining):La entrada al algoritmo de cifrado es el XOR entre el bloque de texto claro y el bloque de texto cifrado anterior.
DES DES DES
Tiempo = 1 Tiempo = 2 Tiempo = N
(a) Cifrado
(b) Descifrado
DES DES DES
24
CriptografíaCriptografía clásica procesado texto en claro
Escítala, Polybios, César, …
operaciones de encriptación
sustituciónmonoalfabeto
César, Polybios, Playfair, …polialfabeto
Vigenere
bloqueFeistelDES, 3DES, AES
flujo
número de claves
clave privada
transposiciónrail fencetransposición de columnas
productoDES
clave públicaRSA
Cifradores Flujo: Estructura
25
Cifradores Flujo: Propiedades
Consideraciones de diseño:Consideraciones de diseño:periodo extenso sin repeticiones (key stream)generación clave quasi-aleatoriatamaño clave
Si el diseño el correcto, puede considerarse tan seguro como un cifrador en bloque (con el mismo tamaño de l )clave)
VentajasSimplicidadRapidez
RC4Cifrado propietario RSA Security
CaracterísticasTamaño Clave Variable (1-256 bytes)Trabajo con bytesSimplicidad y eficacia
Ampliamente usadoweb SSL/TLSwireless WEP
key forms random permutation of all 8-bit values uses that permutation to scramble input info processed a byte at a time
26
RC4 Key Schedule
S: estado interno cifradoS: estado interno cifradoClave determina intercambio seguro
for i = 0 to 255 doS[i] = iT[i] = K[i mod keylen])
Inicialización
j = 0for i = 0 to 255 do
j = (j + S[i] + T[i]) mod 256 intercambiar (S[i], S[j])
PermutaciónInicial de S
RC4: EncriptaciónGeneración Flujo: intercambio valores S
Encriptación/Desencriptación: S[t] XOR (Byte M)
i = j = 0 para cada byte del mensaje Mi
i = (i + 1) mod 256j = (j + S[i]) mod 256
swap(S[i], S[j])
t = (S[i] + S[j]) mod 256Ci = Mi XOR S[t]
27
RC4 Overview
RC4 Security
Criptoanálisis RC4Criptoanálisis RC4varios métodos publicadosninguno práctico (con clave longitud razonable)
Cifrado altamente no-lineal
Problema Seguridad WEPgeneración clave K
Top Related