02 - Criptografia [clave privada].ppt [Modo de...

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


Escítala, Polybios, César, …


sustituciónmonoalfabeto

César, Polybios, Playfair, …polialfabeto

Vigenere

bloqueFeistelDES, 3DES, AES

flujo

número de claves

clave privada


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





César, Polybios Playfair, …polialfabeto

Vigenere


flujo

número de claves

clave privada


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






Vigenere


flujo

número de claves

clave privada


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






Vigenere


flujo

número de claves

clave privada


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






Vigenere


flujo

número de claves

clave privada


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






Vigenere


flujo

número de claves

clave privada


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


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


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






Vigenere


flujo

número de claves

clave privada


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

02 - Criptografia [clave privada].ppt [Modo de...

Documents

Transcript of 02 - Criptografia [clave privada].ppt [Modo de...