1

Capitulo 1: Introducción

66.69 CRIPTOGRAFÍA Y SEGURIDAD INFORMÁTICADepartamento de Electrónica Facultad de Ingeniería. Universidad de Buenos Aires.

Condiciones Aprobación• 1 Examen con 2 recuperatorios.• Para rendir el examen se debe entregar el tp

obligatorio 1.• Coloquio Integrador.• Para rendir el Coloquio Integrador se debe

entregar el tp obligatorio 2• Trabajo Optativo Final: Permite subir hasta

2 puntos la nota Final.66.69 CRIPTOGRAFÍA Y SEGURIDAD INFORMÁTICA

2

Libros

TAPA LIBRO

Crytpography and Network Security, Third EditionWilliam Stallings PRENTICE HALL

• Cifradores• Protocolos Criptograficos• Seguridad: Ip Security – Firewalls

Practical Unix & Internet Security, 3rd EditionSimson Garfinkel, Gene Spafford, Alan Schwartz3rd Edition February 2003 - O'Reilly

• Unix

66.69 CRIPTOGRAFÍA Y SEGURIDAD INFORMÁTICA

Libros

66.69 CRIPTOGRAFÍA Y SEGURIDAD INFORMÁTICA

TAPA LIBRO

UNIX Programming Environment, Theby Brian W. Kernighan, Rob Pike

Hacking Exposed: Network Security Secretsand Solutions 4th Editionby Stuart McClure, Joel Scambray, George KurtzPaperback - 700 pages 4th edition (February 25, 2003)McGraw-Hill Professional Publishing; ISBN: 0072227427

3

Libros Alternativos

TAPA LIBRO

Criptograf´ia y Seguridad enComputadoresTercera Edici´ on (Versi´ on 2.10). Mayo de 2003Manuel Jos´e Lucena L´ opeze-mail: mlucena@ujaen.eshttp://www.kriptopolis.com

Applied CryptographySecond EditionBy Bruce SchneierJohn Wiley & Sons, 1996

66.69 CRIPTOGRAFÍA Y SEGURIDAD INFORMÁTICA

RELACIÓN ENTRE MECANISMOS Y SERVICIOS

DE SEGURIDADMecanismo

Servicio CifradoFirma Digital

Control de Acceso

Integridad de Datos

Autentica-ción

Traffic padding

RoutingControl

Notariza-tion

Peer entity authentication S S SData origin authentication S SControl de Acceso sConfidencialidad S STraffic flow confidentiality S S SIntegridad de Datos S S SNo Repudio S S SDisponibilidad S S

Fuente: [STAL01] Criptography and Network Security

66.69 CRIPTOGRAFÍA Y SEGURIDAD INFORMÁTICA

1

Criptografía y Seguridad InformáticaBASADO EN:

•Third Edition by William Stallings Lecture slides by Lawrie Brown•Seguridad Informática y Criptografía: Dr. Jorge RamióAguirre - Universidad Politécnica de Madrid

Introducción

• Los temas se usan en– AES, Elliptic Curve, IDEA, Public Key

• Grupos, anillos y campos del algebra• Campos Finitos

2

Grupo Abeliano• Grupo: Un conjunto de elementos (S) o

“números” y una operación– (a1) Cerrado si a y b pertenecen a S

=> a+b también

– (a2) Ley asociativa:(a+b)+c = a+(b+c)– (a3) Identidad 0+a = a+0 = a– (a4) Inversa aditiva -a: a+(-a)= 0

• (a5) Conmutativa a+b = b+a

Los enteros con la suma forman un grupo abeliano

Los numeros modulo 7 con la suma?

Grupo Ciclico

• define exponentiation as repeated application of operator– example: a-3 = a.a.a

• and let identity be: e=a0

• a group is cyclic if every element is a power of some fixed element– ie b = ak for some a and every b in group

• a is said to be a generator of the group

3

Anillo

• Conjunto de números con dos operaciones (S,+,.) (suma y multiplicación):

• Grupo abeliano con respecto a la suma • multiplicación:

– (m1) cerrada Si a ^ b eS => a*b e S– (m2) Asociativa a.(b.c) = (a.b).c– (m3) distributiva respecto de la suma:

a(b+c) = ab + ac

Básicamente un anillo es un conjunto de números donde se puede sumar restarY multiplicar sin salir del conjunto

Anillo

• ANILLO CONMUTATIVO:– (m4)Si la operación de multiplicación es

conmutativa a.b = b.a

• Dominio– (m5) Identidad multiplicación a.1 = 1.a = a– (m6) No zero divisors Si a.b = 0 => a=0 o b=0

4

Campo

• (S,+,*) :– Grupo Abeliano para la suma – Anillo - dominio – (m7) Inversa multiplicativa

• Si a eS ^ a ? 0, a-1 eS / a. a-1 = 1

• EJ: reales, complejos, campo finito.

Figura 4.1 del Stallings

5

Aritmetica Modular

• Definiendo a mod n al resto de a al dividirlo por n

• b residuo de a mod na = qn + b

• usualmente 0 <= b <= n-1-12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7

6

• congruencia:

– Sean dos números enteros a y b: se dice que a es congruente con b en el módulo o cuerpo n (Zn) si y sólo si existe algún entero k que divide de forma exacta la diferencia (a - b) .

• A y b son congruentes modulo n a = b mod n

– Al ser divididos por n, a & b tienen el mismo resto

– ej. 100 = 34 mod 11

a - b = k ∗ na ≡ n b

a ≡ b mod n

Conceptos básicos de congruencia

Modulo 7 Example

... -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 67 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 33 34 ...

(-12 = -2 x 7 + 2) = (-5 = -1 x 7 + 2) = ( 2 = 0 x 7 + 2) = ( 9 = 1 x 7 + 2)

7

• Propiedad Reflexiva:a ≡ a mod n ∀ a ∈ Z

• Propiedad Simétrica:a ≡ b mod n ⇒ b ≡ a mod n ∀ a,b ∈ Z

• Propiedad Transitiva:Si a ≡ b mod n y b ≡ c mod n

⇒ a ≡ c mod n ∀ a,b,c ∈ Z

Propiedades de la congruencia en Zn

Grupo Abeliano– (a1) Cerrado si a y b pertenecen a Zn

=> a+b también

– (a2) Propiedad asociativaa + (b + c) mod n ≡ (a + b) + c mod n

– (a3) Identidad a + 0 mod n = 0 + a mod n = a mod n = a

– (a4) Inversa aditiva a-1: a.a-1 = 0a + (-a) mod n = 0 (3 + 4) mod 7 = 0

• (a5) Conmutativa a + b mod n ≡ b + a mod n

8

Anillo

• Conjunto de números con dos operaciones (S,+,.) (suma y multiplicación):

• Grupo abeliano con respecto a la suma • multiplicación:

– (m1) cerrada Si a ^ b eS => a*b e S– (m2) Asociativa a.(b.c) mod n = (a.b).c mod n– (m3) distributiva respecto de la suma:

a ∗ (b+c) mod n ≡ ((a ∗ b) + (a ∗ c)) mod n

a ∗ (b+c) mod n = ((a ∗ b) + (a ∗ c)) mod n

Anillo

• ANILLO CONMUTATIVO:– (m4)Si la operacion de multiplicacion es

conmutativa a ∗ b mod n ≡ b ∗ a mod n

• Dominio– (m5) Identidad multiplicación

a ∗ 1 mod n = 1 ∗ a mod n = a mod n = a

– (m6) No zero divisors Si a.b = 0 => a=0 o b=0

9

Campo

• Un conjunto de números con dos operaciones:– Grupo Abeliano para la suma – Anillo - dominio – (m7) Inversa multiplicativa

• Si a eS ^ a ? 0, a-1 eS / a. a-1 = 1

• a ∗ (a-1) mod n = 1 (no siempre existe)

Divisor

• Un numero no cero b divide a a– a=mb (a,b,m enteros)

• Resto cero

• Se escribe b|a• 12|24 5|15

10

Operaciones Modulares

• Suma, multiplicación y división modulo n• Se puede reducir

– a+b mod n = [a mod n + b mod n] mod n

– A*b mod n = [a mod n * b mod n] mod n– a100 mod n = a(50+50) mod n

= a50 a50 mod n =[a50 mod n * a50 mod n] mod n

Modular Arithmetic

• Aritmética modulo n con un conjunto finito de n elementos: – Zn = {0, 1, … , n-1}

• Anillo conmutativo con la suma• Campo finito para n primo• Particularidades

– Si (a+b)=(a+c) mod n => b=c mod n– Si (ab)=(ac) mod n => b=c mod n only

Solo se a es primo relativo a n

11

Modulo 8 Example

Máximo común divisorGreatest Common Divisor (GCD)

• Es un problema común en teoría de números

• GCD (a,b) es aquel factor que divide a ambos. – eg GCD(60,24) = 12

• Primo Relativo– Dado que GCD(8,15) = 1– entonces 8 & 15 son primos relativos

12

Algoritmo de Euclides

• GCD(a,b) = GCD(b, a mod b)• b = k * b’• A = k * a’ a’>b’ (supongo)• A mod b = r = a – b*q • r = k*a’ – k*b’*q=• r =k*(a’-b’q)

=> r tiene de factor a k Sucesión decreciente

Algoritmo de Euclides

• Manera eficiente de calcular MCD(a,b)– GCD(a,b) = GCD(b, a mod b)

• Pseudocodigo• GCD(a,b):

– A=a, B=b– while B>0

•R = A mod B•A = B, B = R

– return A

13

Ejemplo GCD(1970,1066)

1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0)

Campos de Galois

• finite fields play a key role in cryptography• can show number of elements in a finite

field must be a power of a prime pn

• known as Galois fields• denoted GF(pn)• in particular often use the fields:

– GF(p)– GF(2n)

14

Galois Fields GF(p)

• GF(p) is the set of integers {0,1, … , p-1} with arithmetic operations modulo prime p

• these form a finite field– since have multiplicative inverses

• hence arithmetic is “well-behaved” and can do addition, subtraction, multiplication, and division without leaving the field GF(p)

Example GF(7)

15

Inversas

• Algoritmo de Euclides extendido:EXTENDED EUCLID(m, b)1. (A1, A2, A3)=(1, 0, m);

(B1, B2, B3)=(0, 1, b)2. if B3 = 0

return A3 = gcd(m, b); no inverse3. if B3 = 1

return B3 = gcd(m, b); B2 = b–1 mod m4. Q = A3 div B35. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)6. (A1, A2, A3)=(B1, B2, B3)7. (B1, B2, B3)=(T1, T2, T3)8. goto 2

Inverse of 550 in GF(1759)

16

RSA

• Rivest, Shamir & Adleman del MIT en 1977

• Es el mas conocido• Usa enteros grandes (ej. 1024 bits)• Seguridad dado el costo de factorizar

números grandes– nb. Ek mejor algoritmo toma O(e log n log log n)

operaciones

Algoritmo RSA

17

• Teorema de Euler:– aø(n)mod N = 1 donde gcd(a,N)=1

• En rsa– N=p.q– ø(N)=(p-1)(q-1)– e y d inversas mod ø(N) => e.d=1+k.ø(N)

Entonces:Cd = (Me)d = M1+k.ø(N) = M1.(Mø(N))q = M1.(1)q = M1 = M mod N

Algoritmo AES (Rijndael)

• Descripción Básica• Introducción Matemática (Cap4 Stallings)• Descripción del Algoritmo (Cap5 Stallings)

18

Historia

• En 1997 el NIST (National Institute of Standardsand Technology) se propuso reemplazar el algoritmo de uso federal.

• DES: En uso desde 1977, hasta 1998.• Se convoco a concurso publico con congresos

anuales (4), objetivos del Standard:– Resistencia a ataques conocidos– Codigo compacto y simple– De dominio publico (sin patentes que limiten el uso)

Historia 2

• Primera ronda (congreso) quedaron 5 finalistas Ago99:– MARS, RC6, Rinjdael Serpent y Twofish.

• Hasta mayo 2000: Se recibieron comentarios e impugnaciones.

• 26/11/01 se eligio el rinjdael– estuvo entre los mejores en todas las pruebas– Desarrollado por cientificos y totalmente libre

de patentes.

19

Arquitectura del AES• El algoritmo Rijndael es un block cipher que cifra bloques de 128, 192, o

256 bits, y usa claves simétricas también de 128, 192 o 256 bits.

• Consiste de una ronda inicial (AddRoundKey), de un numero r de rondas que es de 10,12 o 14 dependiendo de la longitud del bloque y de la clave, las primeras r-1 rondas son iguales y la ultima ligeramente diferente

• Las Primeras r-1 rondas consisten de 4 transformaciones:– ByteSub (substitucion de bytes)– ShiftRow (corrimiento de filas)– MixColumn (multiplica columnas)– AddRoundKey (suma de subclave)

• La ultima ronda consiste solo de – ByteSub, ShiftRow y AddRoundKey

• Para entender el algoritmo es necesario ver primero elementos depolinomios y GF.

Aritmetica de Polinomios

• Al trabajar con polinomios del tipo

• Hay varias alternativas:– Aritmética polinomial normal– Trabajar los coeficientes modulo p– Trabajar los coeficientes modulo p y los

polinomios mod M(x)

20

Aritmética de Polinomios Normal

• Sumar o restar los coeficientes como enteros

• Ej: f(x) = x3 + x2 + 2 g(x) = x2 – x + 1

f(x) + g(x) = x3 + 2x2 – x + 3f(x) – g(x) = x3 + x + 1f(x) x g(x) = x5 + 3x2 – 2x + 2

Aritmética polinomial con coeficientes en mod p

• Los coeficientes se calculan modulo p• P puede ser cualquier primo => el espacio

con que se trabajan los coeficientes es un Campo Finito.

• Trabajaremos modulo 2– Todos los coeficientes son 0 o 1– ej. Si f(x) = x3 + x2 y g(x) = x2 + x + 1

21

Aritmética polinomial con coeficientes en mod 2

• Si p es modulo 2:• La Suma y la resta modulo 2

• Multiplicación

+ 0 10 0 11 1 0

- 0 10 0 11 1 0

* 0 10 0 01 0 1

Aritmética polinomial con coeficientes en mod p

• Trabajaremos modulo 2– Todos los coeficientes son 0 o 1– ej. Si f(x) = x3 + x2 y g(x) = x2 + x + 1f(x) + g(x) = x3 + x + 1(Se hace la xor de los coeficientes)

f(x) x g(x) = x5 + x2

22

Aritmetica polinomial Modular

• Podemos escribir un polinomio:– f(x) = q(x) g(x) + r(x)– Interpretar r(x) como el resto– r(x) = f(x) mod g(x)

• Si r(x)=0 => g(x) divide a f(x)• Si g(x) tiene de factores a 1 y el mismo, se

dice que es irreductible (Polinomio primo)• arithmetic modulo an irreducible

polynomial forms a field

Campo de Polinomios

• Suma de polinomios y multiplicacion de polinomios modulo un polinomio escerrada y se porta “BIEN”

• Si el polinomio es irreductible (primo) genera un campo (Finito)

23

GCD Máximo común Divisor de Polinomios

• c(x) = GCD(a(x), b(x)) – c(x) es el polinomio de mayor grado que divide a

a(x) y a b(x)EUCLIDES– EUCLID[a(x), b(x)]1. A(x) = a(x); B(x) = b(x)2. 2. if B(x) = 0 return A(x) = gcd[a(x), b(x)]3. R(x) = A(x) mod B(x)4. A(x) ¨ B(x)5. B(x) ¨ R(x)6. goto 2

Campos Finitos GF(2n)

• El campo GF(2n) – Polinomios con coeficientes modulo 2– El grado del polinomio es n– Se debe reducir por un polinomio grado n

(Solo para multiplicación)

• Forman un campo Finito• Siempre existe la inversa

– Algoritmo de euclides extendido

24

EJEMPLO GF(23)

LAS CUENTAS SE REDUCEN MODULO f(x)=x3+x+1Ver Pag 125 y 128 stallings ver3

Computos en GF(2n)

• Dado que los coeficientes son 0 o 1, se puede representar como un bit string

• Suma es XOR • multiplicación son shifts & XOR• Algoritmo de multiplicación rápido usado

en AES

25

RESUMEN

• AES• Matemática del AES

1

Cryptography and Network Security

Third Editionby William Stallings

Lecture slides by Lawrie Brown

AES –Advanced Encryption Standard

2

Orígenes

• Era necesario un reemplazo al DES– Tenia ataques teóricos– Se demostró posible los ataques de fuerza bruta

• El Triple DES no es opción para paquetes chicos

• El NIST realizo un concurso publico en 1997• 15 candidatos fueron aceptados en Jun 98 • Se redujo a 5 en Ago 99 • En Oct 2000 se selecciono el Rijndael

Estándar FIPS PUB 197 de Nov de 2001

Requerimientos para el AES

• De clave simétrica• 128-bit de datos, 128/192/256-bit de clave.• Mejor y mas rápido que el Triple-DES • Se estima una vide de 20-30 years (+

tiempo para archivo) • Que este disponible la especificación

completa.• Implementaciones en C y Java disponibles

3

AES Criterios de evaluación

• Criterio inicial:– Seguridad – esfuerzo en el criptoanálisis– costo – computacional– Características del algoritmo y de la implementación

• Criterio Final– Seguridad– Disponibilidad de implementaciones en HW y SW

sencillas– Flexibilidad

Finalistas

• Aug-99: – MARS (IBM) - complex, fast, high security margin – RC6 (USA) - v. simple, v. fast, low security margin – Rijndael (Belgium) - clean, fast, good security margin – Serpent (Euro) - slow, clean, v. high security margin – Twofish (USA) - complex, v. fast, high security margin

4

The AES Cipher - Rijndael

• Rijmen-Daemen en Bélgica• No usar tipo feistel

– Trata los datos como una matriz de 4*4 bytes– Opera en todos los bytes en cada ronda

• Se diseño:– Resistente a ataques conocidos– Rapido y compacta ( CPUs )– Diseño simple

Rijndael

• Matriz de Estado 4 gupos de 4 bytes

• Tiene 128/192/256 bit de clave y 128 bitde dato

5

Rijndael

Byte Substitution (caja S)

• Substitución Byte a byte con una tabla (caja S) de 16x16 bytes conteniendo la permutación de los 256 valores de 8-bit

6

CAJA S

• Inicializar la caja S con el valor {xy} para la fila x columna y

• Cambiar cada componente por su inversa modulo GF(28)

• Si cada byte se representa por b7b6b5b4b3b2b1b0. Se aplica la transformación:

• Si S1,1= {53} => S’1,1= {ed}

7

Shift Rows

• Desplazamiento circular

Mix Columns

• Cada columna se procesa en forma separada

• Cada byte se reemplaza por un promedio ponderado de toda la columna

• La multiplicación en GF(28) con m(x) =x8+x4+x3+x+1

8

Mix Columns

Add Round Key

• Se hace XOR del estado con los 128-bits de la clave de ronda

9

AES Round

AES Key Expansion

• Toma 128-bit (16-byte) de la clave y la expande a 44/52/60 words de 32-bits

10

Implementation Aspects

• Al trabajar en GF(28) se puede implementar en CPUS de 8bits– La caja S es una tabla de 256 posiciones– shift rows: Es un corrimiento simple de bytes– add round key: XOR – mix columns multiplicacion en GF(28),

algoritmo acelerado

• Tanto en HW como en SW

Resumen

• have considered:– the AES selection process– the details of Rijndael – the AES cipher– looked at the steps in each round– the key expansion– implementation aspects

1

Chapter 3 – Block Ciphers

Cifradores de Bloque “Modernos”

• Son muy usados • Permiten obtener seguridad y servicios de

autenticación• Vimos el DES y el AES

2

Cifradores en Bloque vs Stream

• block ciphers: procesan los mensajes en en bloques

• stream ciphers: procesa los mensajes de a bit o bytes

• La mayoría como el AES son cifradores de bloque

Stream: One Time Pad o Bernam

• El “one-time pad” es de Major Joseph Mauborgne and Gilbert Bernam (1917)

• Es considerado como un algoritmo con secreto perfecto (irrompible)

• La teoría es simple:– Se genera una clave "string" aleatorio del mismo tamaño que

la clave.– Nunca debe ser reusada– Es incondicionalmente seguro porque siempre se puede

encontrar una clave que lleve el texto cifrado a cualquier frase.

• Dificultades: – Generar la clave– Transmitirla

3

Block Cipher Principles

• Son como una sustitución

• Ejemplo en 64 bits se puede implementar como una tabla de 264 entradas

Claude Shannon and Substitution-Permutation Ciphers

• in 1949 Claude Shannon introduced idea of substitution-permutation (S-P) networks– modern substitution-transposition product cipher

• these form the basis of modern block ciphers • S-P networks are based on the two primitive

cryptographic operations we have seen before: – substitution (S-box)– permutation (P-box)

• provide confusion and diffusion of message

4

Confusion and Diffusion

• cipher needs to completely obscure statistical properties of original message

• a one-time pad does this• more practically Shannon suggested

combining elements to obtain:• diffusion – dissipates statistical structure

of plaintext over bulk of ciphertext• confusion – makes relationship between

ciphertext and key as complex as possible

Elementos Diseño cifradores Bloque

• Estructuras de Feistel• numero de rondas• Caja S

– provides “confusion”, is nonlinear, avalanche

• Clave• Expansión de clave

– complex subkey creation, key avalanche

5

Modos de operación

• Los cifrados en bloque cifran en bloques de tamaño fijo

• eJ. DES 64-bit blocks, con 56-bit de clave

• Los modos de operación se estandarizaron para el DES en el Standard ANSI X3.106-1983 Modes of Use

• Se extendió el uso al AES• Hay modos tipo Bloque y stream

Electronic Codebook Book (ECB)

• El mensaje se parte en bloques de tamaño fijo

• Cada bloque es substituido por el cifrado en forma independiente de los otrosCi = AESK1 (Pi)

• usos: para valores únicos

6

Electronic Codebook Book (ECB)

Consideraciones ECB

• Las repeticiones de un mensaje traen problemas

• El uso principal es para enviar pequeños paquetes

7

Cipher Block Chaining (CBC)

• Se parte el mensaje en bloque pero están vinculados por el proceso de encripcion

• Se encadena con el texto cifrado anterior • Para iniciar el proceso se usa un Vector

Inicial (IV)Ci = DESK1(Pi XOR Ci-1)C-1 = IV

• uses: Encripcion de archivos

Cipher Block Chaining (CBC)

Ci = DESK1(Pi XOR Ci-1)C-1 = IV

8

Consideraciones CBC

• Cada bloque del texto cifrado depende de todos los bloques de entrada

• Entonces un cambio en la entrada altera todos los bloques a partir de este.

• Necesita una semilla (Initial Value IV) conocida por ambas partes– Si IV se envia en claro, un atacante puede cambiarlo

el IV e influir sobre el primer bloque. – Entonces IV debe ser fijo o enviado con ECB antes

Cipher FeedBack (CFB)

• El mensaje es tratado como un stream de datos• Se hace un xor con la salida del bloque anterior

y el resultado es realimentado• El standard permite que la realimentación tome

los bits de a 1,8 o 64– Estos se llaman CFB-1, CFB-8, CFB-64 etc

• El mas eficiente es el de 64 bits (CFB-64)Ci = Pi XOR DESK1(Ci-1)C-1 = IV

• usos: encriptado tipo stream, autenticación

9

Cipher FeedBack (CFB)

Consideraciones CFB

• Generalmente usado cuando los datos llegan de a bits o bytes

• Es el modo stream mas común • Notar que el cifrador es usado en modo

encripcion de los dos lados • Errores se propagan

10

Output FeedBack (OFB)

• El mensaje es tratado como un stream• La salida es realimentada y sumada (xor)

al mensaje• La realimentación es independiente del

mensajeCi = Pi XOR OiOi = DESK1(Oi-1)O-1 = IV

• Usos: stream en canales ruidosos

Output FeedBack (OFB)

11

Consideraciones OFB

• Parecido al CFB • Realimentación independiente del mensaje• Es una variación del Vernam

– Nunca se debe usar nuevamente la semilla (key+IV)

• EL que envía y recibe deben estar sincronizados

• Solo se usa el OFB-64• Es un OTP donde la clave es un generador de

números pseudo-aleatorios

Counter (CTR)

• Es nuevo• Parecido al OFB pero se usa un contador• Debe tener una clave distinta (cuenta)

para cada mensajeCi = Pi XOR OiOi = DESK1(i)

• usos: redes alta velocidad

12

Counter (CTR)

Consideraciones del CTR

• Eficiente– Permite paralelizar– Bueno para enlaces rápidos– Hardware sencillo

• No se debe usar nuevamente la clave

13

Resumen

• Cifradores:– Stream– Bloque

• Modos de cooperación– ECB, CBC, CFB, OFB, CTR

1

Cryptography and Network SecurityBasado en:

•Third Edition by William Stallings•Lecture slides by Lawrie Brown

Repaso RSA (CH9) Administración claves (ch10)

2

Criptografía de clave Publica

• 2 claves publica y privada• Asimétrico• Se complementa con la tradicional clave

simétrica• Secreto: cifro con la publica• Autenticación: cifro con la privada

Anillo de claves

3

Por que?

• Permite:– Distribución de claves- evitar el uso de KDC.– Firma Digital – Verificar quien envió un mensaje o

genero un documento.– Seguridad (encripción) - Autenticación

• El concepto fue publicado por Whitfield Diffie & Martin Hellman de la Stanford Uni en 1976 (con distribución de claves) – Supuestamente era conocido desde antes en el DOD

Secreto y Autenticación

4

Seguridad en esquemas PKI• La búsqueda exhaustiva por fuerza bruta es

aplicable, pero las claves son largas (>512bits) • Generalmente hay un problema matemático de

difícil solución. Ej. RSA factorizar un numero muy grande.

• Requiere el uso de números muy grandes, por lo tanto es mas lenta que los esquemas de clave simétrica

RSA

• Rivest, Shamir & Adleman del MIT en 1977

• Es el mas conocido• Usa enteros grandes (ej. 1024 bits)• Seguridad dado el costo de factorizar

números grandes– nb. Ek mejor algoritmo toma O(e log n log log n)

operaciones

5

Algoritmo RSA

• Teorema de Euler:– aø(n)mod N = 1 donde gcd(a,N)=1

• En rsa– N=p.q– ø(N)=(p-1)(q-1)– e y d inversas mod ø(N) => e.d=1+k.ø(N)

Entonces:Cd = (Me)d = M1+k.ø(N) = M1.(Mø(N))q = M1.(1)q = M1 = M mod N

6

Exponentiation

Ch10/6 – Administración de Claves; Distribución de claves

7

Administración de claves(key management)

• Posibilidades:– Distribución de claves publicas

• Public announcement• Publicly available directory• Public-key authority• Public-key certificates

– Uso de claves publicas para distribuir claves simétricas

Anuncio publico

• Los usuarios distribuyen sus claves– ej. Incorporar las claves PGP al enviar claves

PGP.

• Debilidad– Cualquiera puede enviar un email haciéndose

pasar por otro

8

Directorio Publico

• Las claves se registran en un directorio publico• Debe ser confiable y cumplir con:

– Tener entradas {nombre, clave publica}– Los usuarios se deben registrar de forma segura– Los participantes deben poder hacer un ABM de sus

entradas– Debe ser publico– Debe poder ser accedido electrónicamente

• NO ES ESCALABLE• Único punto de falla

Autoridad de claves publicas(Public-Key Authority)

• Mejora la seguridad validando las claves que retorna el directorio (mediante firma digital)

• Requiere que los usuarios conozcan la clave publica de la autoridad

• Los usuarios consultan con la autoridad para obtener la clave– Requiere acceso en línea con la autoridad

9

Autoridad de claves publicas(Public-Key Authority)

Certificados: Autoridad Certificante

• Permiten el intercambio de claves sin el acceso en línea con la autoridad PKI

• El certificado es equivalente una cedula de identidad, la identidad es demostrada por el certificado – Usualmente contiene la identidad, periodo de validez, derechos

de uso, etc.

• Es un archivo con un formato especifico que contiene registros. Dicho archivo es firmado por la autoridad certificante. (Certificate Authority CA)

• Puede ser verificado por cualquiera que conozca la clave publica de la autoridad.

10

Certificados: Autoridad Certificante

Distribución de claves simétricas por medio de PKI

• Usar cualquiera de los métodos anteriores para obtener las claves publicas de las partes

• Se negocia una clave de sesión.• Generada

– Por una de las partes– Por las dos partes Ej. Diffie Hellman

11

Merkle: Generación de clave de sesión

– A generates a new temporary public key pair– A sends B the public key and their identity– B generates a session key K sends it to A

encrypted using the supplied public key– A decrypts the session key and both use

• Un tercero puede interponerse y personificar al lado A

Public-Key Distribution of Secret Keys

• Requisito, claves publicas ya intercambiadas:

12

Generación de claves compartidasDiffie-Hellman

• Primer esquema de doble clave • Diffie & Hellman en 1976

– Supuestamente James Ellis (UK CESG) lo propuso secretamente en 1970

• Es un método para generar claves de sesión

• Usado en protocolos como ipsec y SSL

Diffie-Hellman Setup

• Se ponen de acuerdo en parámetros:– Un primo grande o polinomio q– a es una raíz primitiva de q

• Cada usuario (eg. A) genera su clave– Un numero secreto: xA < q– Calcula su clave publica: yA = axA mod q

• Esta parte se hace publica

13

Diffie-Hellman Key Exchange

• La clave entre A y B es KAB: KAB = axA.xB mod q= yA

xB mod q (which B can compute) = yB

xA mod q (which A can compute)

• Si se quieren seguir comunicando usan la misma clave o seleccionan una nueva clave publica

• Para obtener X un atacante debe obtener el logaritmo de y

14

Ejemplo de Diffie-Hellman

• Alicia y Bob Esponja:• Se ponen de acuerdo en el primo q=353 y a=3• Seleccionan sus claves al azar:

– A xA=97, B xB=233• Calculo de la parte publica:

– yA=397 mod 353 = 40 (Alicia)– yB=3233 mod 353 = 248 (Bob)

• Cada uno puede calcular la clave de sesión con:KAB= yB

xA mod 353 = 24897 = 160 (Alicia)KAB= yA

xB mod 353 = 40233 = 160 (Bob)

1

§ Taher El Gamalpropone en 1985 un algoritmo que hace uso del problema del logaritmo discreto PLD.

§ Este algoritmo fue diseñado específicamente para firma digital

Algoritmo asimétrico El Gamal

§ Se elige un grupo multiplicativo Zp*, donde p es un primo grande§ Del grupo p se elige una raíz α, generador del grupo§ Cada usuario elige un número aleatorio λ dentro de p

§ El valor λ será la clave privada§ Cada usuario calcula αλ mod p

§ Los valores (αλ mod p) y p serán la clave pública§ Seguridad del sistema

§ Para descubrir la clave privada, el atacante deberá enfrentarse al problema del logaritmo discreto para p grande

Algoritmo asimétrico El Gamal

"http://web.usna.navy.mil/~wdj/book/node48.html

2

§ El usuario B ha elegido su clave privada b dentro del cuerpo del número primo p que es público.

§ El usuario B ha hecho pública su clave αb mod p.

§ El emisor A genera un número aleatorio ν de sesión y calcula αν mod p.

§ Con la clave pública de B (αb) el emisor A calcula:

§ (αb)ν mod p y N∗(αb)ν mod p

§ A envía a B el par: C = [αν mod p, N∗(αb)ν mod p]

Operación Cifrado: A cifra un número N que envía a B

Operación de cifra con ElGamal

§ El usuario B recibe C = [αν mod p, N∗(αb)ν mod p].

§ B toma el valor αν mod p y calcula (αν)b mod p.

§ B descifra el criptograma C haciendo la siguiente división: [N∗(αb)ν mod p ] / [(αν)b mod p] ... porque (αb)ν = (αν)b

§ El paso anterior es posible hacerlo porque existirá el inverso de (αν)b en el grupo p al ser p un primo. Luego:

[N∗(αb)ν ∗ {inv (αν)b, p}] mod p = N

Operación Descifrado: B descifra el criptograma C que envía A

Operación de descifrado con ElGamal

3

Adela (A) enviará a Benito (B) el número N = 10 cifrado dentro del cuerpo p = 13 que usa Benito.

Claves públicas de Benito: p = 13, α = 6, (αb) mod p = 2

Adela (A) elige por ejemplo ν = 4 y calcula:

(αν) mod p = 64 mod 13 = 9

(αb)v mod p = 24 mod 13 = 3

N∗(αb)v mod p = 10∗3 mod 13 = 4

Y envía a (B): (αν) mod p, N∗(αb)v mod p = [9, 4]

CIFRADO

Ejemplo de cifrado con ElGamal

DESCIFRADOLa clave privada de Benito (B) es b = 5Benito recibe: [(αν) mod p, N∗(αb)v mod p] = [9, 4]Benito calcula:

(αν)b mod p = 95 mod 13 = 3[N∗(αb)v] ∗ inv[(αν)b, p] = 4 ∗ inv (3, 13) = 4 ∗ 9N = 4 ∗ 9 mod 13 = 10 (se recupera el valor)

Recuerde que α debe ser una raíz de p. Como ya hemos visto, si α no es una raíz, aunque sí puede hacerse la cifra, se facilitaría el ataque al problema del logaritmo discreto.

Ejemplo de descifrado con ElGamal

1

Cryptography and Network SecurityBasado en:

•Third Edition by William Stallings•Lecture slides by Lawrie Brown

Message Authentication y Funciones Hash Ch11Stallings

2

Por que es necesaria la autenticación

• Confidencialidad– disclosure– traffic analysis

• Autenticacion de mensajes– masquerade– content modification– sequence modification– timing modification

• Firma digital– source repudiation– destination repudiation

Autenticación de Mensajes

• Se necesita: – Proteger la integridad del mensaje – Validar la identidad del origen– No-repudio del origen (resolución de disputas)

• Para esto se usan tres alternativas o funciones:– Encripción del mensaje– message authentication code (MAC)– Funciones de HASH

3

Función de encripción: simétrica

• La simple encripción permite cierto grado de autenticación

• Si se usa un sistema simétrico:– El receptor puede suponer que el origen es

valido– Dado que solo el origen y el receptor conocen

la clave– El contenido no puede ser alterado

• Siempre y cuando el mensaje tenga alguna estructura, redundancia o un checksum.

Función de encripción: asimétrica

• Si se usa clave publica:– Con la privada autentico el origen– Y con la publica obtengo el secreto– Permite detectar intentos de modificación o

alteraciones– Al costo de un doble cifrado (Autenticación +

secreto)

4

Message Authentication Code (MAC)

• El algoritmo de MAC genera un bloque de bits de tamaño fijo:– La salida depende del mensaje y de una clave– Parecido a una encripcion, pero no es reversible

• Se concatena al mensaje • El receptor realiza el mismo calculo y verifica el

MAC• Permite asegurar que el mensaje no fue

alterado

Message Authentication Code

M MensajeC Función MACK clave|| Concatenación

5

Message Authentication Codes

• Se puede usar en conjunto con el cifrado– Generalmente se usan claves distintas– El MAC se puede incorporar antes o después– Generalmente el MAC se incorpora antes de cifrar

• Porque MAC?– A veces se necesita solamente autenticar– Otras se necesita que el MAC persista para por

ejemplo ser archivado

• MAC no es Firma Digital

Propiedades de las MAC

• Un MAC es un resumen criptográficoMAC = CK(M)

– Convierte un mensaje de tamaño arbitrario en un autenticador de tamaño fijo de pocos bytes.

• Es una función muchos-uno– Potencialmente hay muchos mensajes con la

misma MAC– Encontrarlos debe ser muy dif ícil

6

MAC: Requerimientos

• El MAC debe satisfacer::1. Conocido un mensaje y su MAC,debe ser

computacionalmente imposible encontrar otro mensaje con el mismo MAC

2. Las MAC deben estar distribuidas uniformemente.

3. La MAC debe depender de todos los bits del mensaje.

Uso de cifradores simétricos para construir un MAC

• Se puede usar cualquier algoritmo con un modo de operación de los encadenados y quedarse con el ultimo bloque

• Data Authentication Algorithm (DAA) es un MAC basado en DES-CBC– IV=0 y zero-pad del bloque final– El ultimo bloque es el MAC

• Actualmente el algoritmo no es considerado seguro (56 bits)

7

Data Authentication Algorithm(DAA)

• MAC basado en DES-CBC

Función de HASH

• Una de las aplicaciones más interesantes de la actual criptografía es la posibilidad real de añadir a un mensaje su firma digital: autenticación.

• Para ello se utiliza el modelo de cifrado asimétrico con clave pública. Con los antiguos sistemas de clave simétrica esto era inviable o bien muy complejo.

• Dado que los sistemas de clave pública son muy lentos, en vez de firmar digitalmente el mensaje completo, en un sistema criptográfico se incluirá como firma digital una operación de cifra con la clave privada del emisor sobre un resumen o HASH de dicho mensaje

8

Funciones de HASH

• Resume un mensaje en un resumen criptográfico de tamaño fijo unos pocos BYTES

• La funcion de Hash es publica y no usa claves• Permite detectar cambios en el mensaje• Al no tener clave es un auxiliar de los métodos

de cifrado.• Con la clave publica componen la Firma Digital

Firma Digital y Funciones de Hash

9

Propiedades de las funciones hash

• h(M) será segura si tiene las siguientes características:• Unidireccionalidad: conocido un resumen h(M), debe ser

computacionalmente imposible encontrar M a partir de dicho resumen.

• Compresión: a partir de un mensaje de cualquier longitud, el resumen h(M) debe tener una longitud fija. Lo normal es que la longitud de h(M) sea menor que el mensaje M.

• Facilidad de cálculo: debe ser fácil calcular h(M) a partir de un mensaje M.

• Difusión: el resumen h(M) debe ser una función compleja de todos los bits del mensaje M: si se modifica un solo bit del mensaje M, el hash h(M) debería cambiar la mitad de sus bits aproximadamente.

• Colisión simple: será computacionalmenteimposible conocido M, encontrar otro M’tal que h(M) = h(M’). Esto se conoce como resistencia débil a las colisiones.

• Colisión fuerte: será computacionalmentedifícil encontrar un par (M, M’) de forma que h(M) = h(M’). Esto se conoce como resistencia fuerte a las colisiones.

10

Simple Hash Functions

• are several proposals for simple functions• based on XOR of message blocks• not secure since can manipulate any

message and either not change hash or change hash also

• need a stronger cryptographic function (next chapter)

Estructura Básica de un Hash

11

• Función de Hash Iterada: md5 sha:1• Toma el mensaje de entrada y lo parte en

bloques de b bits.• Si es necesario se completa el ultimo

bloque (padding)• La salida de la ultima función es la salida

del HASH• F: función de compresión

Birthday Attacks

• might think a 64-bit hash is secure• but by Birthday Paradox is not• birthday attack works thus:

– opponent generates 2 m/2 variations of a valid message all with essentially the same meaning

– opponent also generates 2 m/2 variations of a desired fraudulent message

– two sets of messages are compared to find pair with same hash (probability > 0.5 by birthday paradox)

– have user sign the valid message, then substitute the forgery which will have a valid signature

• conclusion is that need to use larger MACs

12

Block Ciphers as Hash Functions

• can use block ciphers as hash functions– using H0=0 and zero-pad of final block– compute: Hi = EMi [Hi-1]– and use final block as the hash value– similar to CBC but without a key

• resulting hash is too small (64-bit)– both due to direct birthday attack– and to “meet-in-the-middle” attack

• other variants also susceptible to attack

Hash Functions & MAC Security

• like block ciphers have:• brute-force attacks exploiting

– strong collision resistance hash have cost 2m/2

• have proposal for h/w MD5 cracker• 128-bit hash looks vulnerable, 160-bits better

– MACs with known message-MAC pairs• can either attack keyspace (cf key search) or MAC• at least 128-bit MAC is needed for security

13

Hash Functions & MAC Security

• cryptanalytic attacks exploit structure– like block ciphers want brute-force attacks to

be the best alternative• have a number of analytic attacks on

iterated hash functions– CVi = f[CVi-1, Mi]; H(M)=CVN

– typically focus on collisions in function f– like block ciphers is often composed of rounds– attacks exploit properties of round functions

Summary

• have considered:– message authentication using– message encryption– MACs– hash functions– general approach & security