PDF de programación - Criptografía de Clave secreta: Cifrado en flujo

Criptografía de Clave secreta:

Cifrado en flujo

Amparo Fúster Sabater
Instituto de Física Aplicada C.S.I.C.
[email protected]

A. Fúster Sabater CCN Noviembre 2009

Contenido

Introducción

•
• Procedimientos de cifrado en flujo
• Criptoanálisis de estos procedimientos
• Cifrado en flujo hoy en día

A. Fúster Sabater CCN Noviembre 2009

Criptología

• Criptología = Criptografía + Criptoanálisis

• Criptografía: desarrolla métodos de cifrado para

proteger la información.

• Criptoanálisis:

rompe dichos métodos para

recuperar la información original.

A. Fúster Sabater CCN Noviembre 2009

Criptografía y Seguridad

Seguridad

Confidencialidad

Autenticidad
Autenticidad

receptor
receptor

Autenticidad
Autenticidad

emisor
emisor

• Antes

• Ahora

Confidencialidad
Confidencialidad

Seguridad
Seguridad

Control Acceso
Control Acceso

Integridad
Integridad

Protocolos
Protocolos

Repudio/
Repudio/
No repudio
No repudio

A. Fúster Sabater CCN Noviembre 2009

Procedimiento Criptográfico:

Esquema General

CLAVE

CLAVE

Texto claro

A

cifrado

Texto cifrado

descifrado

Texto claro

B

Criptoanálisis

descriptado

A. Fúster Sabater CCN Noviembre 2009

Criptografía: clasificación general

• Kc= clave de cifrado Kd= clave de descifrado

• Criptografía de clave secreta (simétrica)

Kc= Kd = K

• Criptografía de clave pública (asimétrica)

Kc Kd

Kc
Kd

conocida públicamente
conocida únicamente por el receptor

A. Fúster Sabater CCN Noviembre 2009

Criptografía Actual

Criptosistemas

actuales

Clave secreta

Clave pública

Cifrado en flujo

Cifrado en bloque

A. Fúster Sabater CCN Noviembre 2009

Criptografía de clave secreta

• Métodos de cifrado en flujo

La transformación se aplica sobre cada carácter del

mensaje original

Ejemplo: sobre cada bit del mensaje

• Métodos de cifrado en bloque

La transformación se aplica sobre un grupo de

caracteres del mensaje original

Ejemplo: sobre grupos de 64 bits (DES)

A. Fúster Sabater CCN Noviembre 2009

Etapas en Criptografía

• Criptografía pre-científica

Desde la Antigüedad (siglo V a. C.) hasta 1949

• 1949, Criptografía de clave secreta

“Communication Theory of Secrecy Systems” C.E.

Shannon

• 1976, Criptografía de clave pública

“New Directions in Cryptography” W. Diffie y M.

Hellman

• ??

A. Fúster Sabater CCN Noviembre 2009

Seguridad Criptográfica

• Seguridad incondicional (TEORICA)

Ejemplo: Cifrado de Vernam

• Seguridad computacional (PRACTICA)

Ejemplo: Criptosistema RSA

• Seguridad probable

Ejemplo: DES (Data Encryption Standard)

• Seguridad condicional

Ejemplo: Métodos clásicos

A. Fúster Sabater CCN Noviembre 2009

Principio de Kerckhoffs

• Criptografía en entornos militares y diplomáticos

La Criptografía permanece en el más absoluto secreto

• Principio de Kerckhoffs (s. XIX)

“El atacante tiene pleno conocimiento del método de

cifrado a excepción de la clave”

• Criptografía al alcance de todos

Aplicación del Principio de Kerckhoffs

a la mayoría de los criptosistemas actuales

A. Fúster Sabater CCN Noviembre 2009

Principios básicos (I)

• Sustitución

Clave:

A B C D E F G H I J K L M N O P Q R S T U V X Y Z

P L O K N M J U I B V G Y T F C X D R E S Z A Q H

Mensaje

E S T O

Criptograma

N R E F

E S

N R

U N

S T

E J E M P L O

N B N Y C I F

A. Fúster Sabater CCN Noviembre 2009

Principios básicos (II)

• Transposición

Clave:

Grupos de 4 letras

Transposición:

1234 ---- 4321

Mensaje

S I S T E M A S C L A S I C O S

Criptograma T S I S S A M E S A L C S O C I

A. Fúster Sabater CCN Noviembre 2009

Escenarios de posibles ataques

• Ataque sobre Texto Cifrado

únicamente (pasivo)

• Ataque sobre Texto Claro Conocido
• Ataque sobre Texto Claro (Cifrado)

Escogido (activo)

• Ataque Adaptativo (activo)

A. Fúster Sabater CCN Noviembre 2009

Seguridad de los criptosistema actuales

• ¿Cuándo un criptosistema es seguro?

En sentido estricto: NUNCA!!!!!
• No hay un criterio general que

determine la seguridad/no seguridad de
un criptosistema

• Se les asigna una “seguridad probable”
• Un criptosistema se considera “roto”

cuando el usuario deja de utilizarlo

A. Fúster Sabater CCN Noviembre 2009

Complejidad computacional

• Complejidad de Datos: Cantidad de información

adicional necesaria para llevar a cabo un ataque

con cierta probabilidad de éxito.

• Complejidad

temporal: Nº

de

operaciones

necesarias para llevar a cabo un ataque.

Pre-computacional

Ataque activo

• Complejidad de memoria: Cantidad de memoria

necesaria para llevar a cabo un ataque.

A. Fúster Sabater CCN Noviembre 2009

Métodos de Criptoanálisis (I)

• Búsqueda exhaustiva
• Ataques por diccionario
• Descripción equivalente
• Búsqueda de invariantes
• Paradoja del cumpleaños
• Ataque meet-in-the-middle
• Claves débiles para ataques particulares

A. Fúster Sabater CCN Noviembre 2009

Métodos de Criptoanálisis (II)

• Ataques algebraicos

 Plantear un sistema de ecuaciones cuyas

incógnitas son los bits de la clave

 Resolverlo (Método XL)

• Ataques por correlación

 Correlación generalizada (Edit Distance)

• Criptoanálisis Diferencial, Lineal, …etc.

A. Fúster Sabater CCN Noviembre 2009

Búsqueda exhaustiva

• Probar una a una todas las posibles claves
• Algunos números:

- 230 operaciones con un PC en unos

minutos

- 255 pruebas de clave con el DES en una red

de cientos de PCs tarda ≈ 10 días

- 270 operaciones por día con toda la
potencia computacional de Internet

• Claves de 128 bits 2128 posibles claves

A. Fúster Sabater CCN Noviembre 2009

Un poco de Criptoanálisis

• Poe publicó en 1843 un famoso
relato titulado “El escarabajo de
oro”, sobre un mensaje cifrado
en
la
localización de un fabuloso
tesoro.

indica

se

el

que

• Poe, gran criptoanalista a la par
que escritor, explica con mucho
detalle cómo se puede romper
un procedimiento de cifrado
mediante técnicas estadísticas.

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro (1843)

• Criptograma

53‡‡†305))6*;4826)4‡.)4‡);806*;48†8¶

60))85;1‡(;:‡*8†83(88)5*†;46(;88*96*?;

8)*‡(;485);5*†2:*‡(;4956*2(5*-4)8¶8*

;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48

†85;4)485†528806*81(‡9;48;(88;4(‡?34

;48)4‡;161;:188;‡?;

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro

Símbolo

No.

Símbolo

No.

Símbolo

No.

Símbolo

No.

Símbolo

No.

8

;

4

)

33

26

19

16

‡

*

5

6

16

13

12

11

†

1

0

9

8

8

6

5

2

:

3

?

5

4

4

3

¶

-

.

2

1

1

Frecuencias:

e

vocales

12%

40%

8 e

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro

• Criptograma

53‡‡†305))6*;4e26)4‡.)4‡);e06*;4e†e¶

60))e5;1‡(;:‡*e†e3(ee)5*†;46(;ee*96*?;

e)*‡(;4e5);5*†2:*‡(;4956*2(5*-4)e¶e*

;40692e5);)6†e)4‡‡;1(‡9;4e0e1;e:e‡1;4e

†e5;4)4e5†52ee06*e1(‡9;4e;(ee;4(‡?34

;4e)4‡;161;:1ee;‡?;

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro

• Buscar “the” = ;48

53‡‡†305))6* the 26)4‡.)4‡);e06* the †e¶

60))e5;1‡(;:‡*e†e3(ee)5*†;46(;ee*96*?;

e)*‡( the 5);5*†2:*‡(;4956*2(5*-4)e¶e*

;40692e5);)6†e)4‡‡;1(‡9 the 0e1;e:e‡1 the

†e5;4)4e5†52ee06*e1(‡9 the ;(ee;4(‡?34

the )4‡;161;:1ee;‡?;

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro

•

•

;(ee;4(‡?34 t(eeth(‡?3h t(ee th(‡?3h

r ( tree thr‡?3h

through

o ‡

u ?

g 3

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro

• †83(88 †egree

d

†

•

;46(;88* th6rtee*

i 6

n *

• 53 ‡‡† 5good a 5

A. Fúster Sabater CCN Noviembre 2009

El escarabajo de oro

•

a 5 n