teoria de la informacion - manejo de claves

Teoría de la información

Manejo de claves

Principios, herramientas y protocolos de criptografía

Yann Frauel – Semestre 2007-1

Seguridad de un criptosistema

Todos los elementos deben ser seguros:➔ Algoritmo➔ Protocolo➔ Clave

2do principio de Kerckhoffs: la seguridad no debe derivarse del secreto del algoritmo, sólo de la clave

¿Cómo medir la seguridad de una clave?

1. Teoría de la información(Claude Shannon 1948)


Idea 1: longitud del mensaje Pero comparar:

➔ 110010101110➔ 439203984738

Idea 2: número de bits necesarios para codificar el mensaje➔ binario: 1 bit/carácter➔ decimal: 4 bits/carácter➔ letras: 5 bits/carácter

¿Cómo medir la cantidad de información de un mensaje?


Pero no se usan todas las combinaciones posibles... Idea 3: número de bits en promedio (fraccional) Ejemplo: lanzar un dado

¿Cómo medir la cantidad de información de un mensaje?

Lanzados Combinaciones Bits totales Bits/car.1 6 3 3.0002 36 6 3.0003 216 8 2.6674 1296 11 2.7505 7776 13 2.600

200 4.27E+155 517 2.585


¿Cómo obtener directamente el número de bits promedio H?

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Número de valores posibles

Núm

ero

de b

its

H = log2(n), n: Número de valores posibles


Ejemplo: Dado de 4 caras ➔ p(0) = 3/4➔ p(1) = 1/8➔ p(2) = 1/16➔ p(3) = 1/16

Cambio de codificación:➔ 0 → 0 1 → 10 2 → 110 3 → 111

Número de bits promedio:➔ H = 3/4 × 1 + 1/8 × 2 + 1/16 × 3 +1/16 × 3

¿Qué pasa si no todos los valores tienen la misma probabilidad?

= 11/8 = 1.38 b/c

Entropía

H X =− ∑i=1

n

pi log2 pi

Sea una variable aleatoria X

Puede tomar n valores: x1, x

2... x

n con probabilidades

P( X = xi) = p

i

Se define la entropía de X:

Mide la cantidad de información proveida por X

Entropía

Ejemplo 1: evento equiprobable➔ p

1 = p

2 = ... = p

n = 1/n

➔ H(X) = log2 (n)

➔ Volvemos a encontrar la fórmula intuitiva➔ Es el valor máximo que se pueda encontrar para n valores

Ejemplo 2: evento seguro➔ p

i =1 y p

j = 0 para j ≠ i

➔ H(X) = 0➔ Es el valor mínimo que se pueda encontrar

La entropía mide la incertidumbre

Redundancia

Ejemplo 1: ¿Qué viene después de una letra Q? Ejemplo 2: ¿Qué significa INST NAC COMPUT

CIENT? ¡Podemos reconstituir más de la mitad del mensaje! Una parte de la información de un texto normal no

es necesaria, es redundante En un lenguaje natural, la entropía no es máxima:

➔ frecuencias diferentes para diferentes letras, bigramas...➔ reglas gramaticales, sintácticas...

→ Los lenguajes naturales tienen mucha redundancia

Redundancia

Entropía absoluta por carácter Ha:

➔ es la entropía máxima posible (caracteres equiprobables)➔ para el alfabeto de 26 letras, H

a = 4.7 b/c

Entropía real por carácter Hr:

➔ es la entropía calculada sobre el lenguaje real➔ para el inglés o el español, H

r ~ 1.5 b/c

Redundancia por carácter R:➔ es la diferencia R = H

a – H

r

➔ para el inglés o el español, R ~ 3.2 b/c

Distancia de unicidad

Ataque por fuerza bruta: probamos todas las claves hasta encontrar un texto con sentido

¿Cuántos caracteres necesitamos para reconocer el texto claro sin ambigüedad?

Entropía del espacio de claves:➔ H(K) = log

2 (número de claves)

Distancia de unicidad:

U=H K

R

Distancia de unicidad

Ejemplo: substitución monoalfabética Número de claves = números de alfabetos = 26!

U=log226!

3.2=28caracteres

2. Generación y almacenamientode claves

Evolución histórica de las claves Sin clave (sin parámetro libre): el secreto está en el

algoritmo mismo➔ Atbash (alfabeto invertido)➔ César (desplazamiento de 3)➔ Tritemio (desplazamiento incrementado para cada letra)

Palabra clave➔ Substitución monoalfabética con alfabeto desordenado➔ Vigenère

Clave aleatoria➔ Hill➔ Máquinas con rotores➔ Cifrado modernos

Claves y contraseñas

Cuando no requiere memorizar: clave➔ Algoritmos para cifrar➔ Algoritmos para firmar

Cuando requiere memorizar: contraseña➔ Autenticación y control de acceso ➔ Aplicar una firma➔ Descifrar un mensaje, un archivo


Clave = más seguridad➔ Larga➔ Aleatoria

Contraseña = más conveniencia➔ Fácil de memorizar➔ Fácil de teclear

→ Combinar los dos


Algoritmos simétricos➔ Contraseña = palabra o frase (tamaño variable)➔ Se le aplica una función resumen de sentido único➔ Reducción (o extensión) a un tamaño fijo

Ábrete Sésamo

Contraseña Función resumen Clavesimétrica

La entropía de la clave es reducida a la entropía de la contraseña


Algoritmos asimétricos➔ clave privada aleatoria ➔ clave privada almacenada en el disco➔ clave privada cifrada con un algoritmo simétrico

Ábrete Sésamo

Contraseña Funciónresumen

Clavesimétrica

Clave privadacifrada

Si el disco es accesible, la seguridad es la de la contraseña

Contraseñas

Seguridad aumenta con la longitud Datos personales (2do apellido, fecha nacimiento)

➔ Se puede adivinar Palabra conocida/nombre (flor, planeta, futbolista)

➔ Ataque de diccionario Generalmente posible encontrar 40 % de las

contraseñas con estos ataques! Seguridad aumenta con la entropía

Contraseñas

Mezclar mayúsculas, minúsculas, dígitos y caracteres especiales

Fácil de memorizar, sin necesidad de escribirlo Difícil de adivinar, incluso por una persona cercana Más de 8 caracteres Puede ser tecleado rápidamente (evitar espías)

Ej.: Iniciales de una frase:

Creo que Alicia conoció a Bob en Guanajuato; no crees?

→ CqAcaBeG;nc?

Contraseñas

Escógelo misterioso Entre más largo, mejor Cámbialo frecuentemente No lo dejes tirado en cualquier lugar No lo compartas con tus amigos

Los passwords son como los calzones...

Claves

Aleatoria (entropía máxima) Generada con generador aleatorio real o seudo-

aleatorio criptográficamente seguro Si el algoritmo es ideal, la seguridad depende del

tamaño de la clave (mejor ataque = fuerza bruta)➔ Clave de n bits: 2n claves posibles (complejidad

exponencial)➔ No usar clave menor a 128 bits para algoritmos simétricos

Ejemplo: clave DES tiene 56 bits➔ 1981: máquina de $50 M → 2 días➔ 1993: máquina de $1 M → 3.5 horas➔ 1996: NSA → 15 minutos

Claves

El tamaño de la clave no es una garantía Puede haber mejores ataques que fuerza bruta Ej. 1: Substitución monoalfabética

➔ 26! claves posibles (permutaciones del alfabeto)➔ 26! = 4.1026 ~ 88 bits➔ Pero podemos atacar por análisis de frecuencias!

Ej. 2: Algoritmo RSA➔ Mejor ataque = buscar factorización de la clave pública➔ clave de 128 bits: se factoriza en 1 s en una laptop!!➔ No usar clave menor a 1024 bits para algoritmos

asimétricos

Respaldo de claves

Problema: perdida de clave➔ Olvido de la contraseña➔ Desaparición del creador de la contraseña➔ Disco borrado

Custodia de clave (key escrow)➔ Un tercero tiene copia de las claves➔ También para la policía (ej. clipper para teléfono 1993)➔ Problema de confianza/seguridad

Secreto compartido➔ Dar parte de las claves a varias personas➔ Reconstituir la clave requiere que se junten

Expiración de claves Claves deben tener una vida limitada

➔ limita tiempo/datos para criptoanálisis➔ limita los datos perdidos si la clave es comprometida

Renovar clave frecuentemente si➔ es fácil de encontrar (contraseña)➔ es usada para información importante

Clave privada comprometida➔ permite leer mensajes (incluso anteriores)➔ permite robo de identidad➔ fijar fecha de expiración y/o➔ preparar certificado de revocación (al generar la clave, en

caso de perdida de la clave privada)

3. Intercambio de claves

Claves de sesión

Problema: la clave debe transmitirse por un canal seguro

Es difícil renovarla Solución:

➔ una clave principal (permanente)➔ claves de sesión generadas para cada nuevo mensaje➔ la clave principal es poco usada (criptoanálisis difícil)➔ poca información perdida si clave de sesión comprometida

Claves simétricas

Establecer una clave para cada par de usuario➔ n usuarios: n(n-1)/2 claves➔ muchas claves, muchos intercambios por canal seguro

Claves simétricas

Tercero de confianza: centro de distribución de claves (KDC)

El KDC tiene las claves principales de todos El KDC distribuye claves de sesión

A1

A2

A3

A4

A5

A6

Centro dedistribución

de claves

Intercambio con claves simétricas

Alicia BobKDC“Quiero comunicar

con Bob”

KS

KA

KS

KB


Comunicación cifrada


Requiere confianza absoluta en el KDC ➔ puede “escuchar” todas las comunicaciones➔ (puede modificar las comunicaciones)➔ (puede hacerse pasar por cualquier usuario)

Todas las llaves están comprometidas si el KDC está comprometido

Todas las comunicaciones están bloqueadas si el KDC está indisponible

Claves asimétricas

Cada usuario tiene su clave privada y su clave pública➔ n usuarios: n claves➔ pocas claves➔ sólo se requiere transmitir las claves públicas➔ la clave pública puede ser obtenida del usuario o de un

KDC➔ no hay problema con atacantes pasivos: no pueden hacer

nada con la clave pública

Intercambio con claves asimétricas

Alicia

Bob

KDC

KB pub

KS

KB pub

Intercambio con claves asimétricas

Comunicación cifrada

Ataque del hombre-en-el-medio

Alicia Atacante Bob

“Quiero comunicarcon Bob”

priv priv

“Quiero comunicarcon Bob”

priv priv

privpriv

pubpub

Ataque del hombre-en-el-medio

Alicia Atacante Bob

priv privpub

pub

pub

Alicia Atacante Bob

priv privpub

pub

pub

Verificación de claves

Las claves asimétricas no resuelven el problema de un atacante activo con control completo

Autenticidad de la clave verificada por una firma:➔ de una Autoridad de Certificación (certificados)➔ de otros usuarios confiables (PGP)

Hace falta conocer la clave pública del certificador!

teoria de la informacion - manejo de claves

Documents