Rainbow Tables

76
Rainbow Tables Gonzalo Álvarez Marañón

description

¿Qué son y para qué sirven las rainbow tables? ¿Cómo pueden utilizarse para romper contraseñas? ¿Cómo protegerse frente a su ataque?

Transcript of Rainbow Tables

Page 1: Rainbow Tables

Rainbow TablesGonzalo Álvarez Marañón

Page 2: Rainbow Tables

“Tengo el hash de

la contraseña.

¿Cómo puedo

obtener la

contraseña

original?”

Page 3: Rainbow Tables

Los hashes son

funciones

unidireccionales

Page 4: Rainbow Tables

)( pHhp H

Esto es fácil

Page 5: Rainbow Tables

ppHh H 1

)(

Esto es difícil

Page 6: Rainbow Tables

¿Solución?

Page 7: Rainbow Tables

PppHh iii ),(

Calcular todos los hashes

Page 8: Rainbow Tables

Calcularlos todos

de una vez

Calcularlos de

uno en uno

Page 9: Rainbow Tables

t

m

N ≈ m2t

Page 10: Rainbow Tables
Page 11: Rainbow Tables

Cadenas de hashes

Page 12: Rainbow Tables

Hellman Martin, “A Cryptanalytic

Time - Memory Trade-Off”

Page 13: Rainbow Tables

Función de reducción, R

Page 14: Rainbow Tables

aaaaaa 281DAF40 sgfnyd 920ECF10 kiebgt

H HR R

Page 15: Rainbow Tables

Proceso de creación de tablas

Page 16: Rainbow Tables

aaaaaa 281DAF40 sgfnyd 920ECF10 kiebgt

H HR R

punto inicial punto final

t

Page 17: Rainbow Tables

fabada F4300A82 mlabaz 941A5BC7 lpmaee

H HR R

aaaaaa kiebgt

Page 18: Rainbow Tables

fabada lpmaee

aaaaaa kiebgt

pttack 41032E55 cateto 0AB2291F pazxca

H HR R

Page 19: Rainbow Tables

fabada lpmaee

aaaaaa kiebgt

pttack pazxca

clpert 22F08D16 lmzclo 5A1C048E urtcre

H HR R

Page 20: Rainbow Tables

fabada lpmaee

aaaaaa kiebgt

pttack pazxca

clpert urtcre

m

… …

Page 21: Rainbow Tables

La tabla se crea una sola vez

Page 22: Rainbow Tables

Ordenada por los puntos finales

fabada

aaaaaa

pttack

clpert

lpmaee

kiebgt

pazxca

urtcre

Punto inicial Punto final

Page 23: Rainbow Tables

¿Cuál es la contraseña de 41032E55?

Page 24: Rainbow Tables

fabada

aaaaaa

pttack

clpert

lpmaee

admin

pazxca

urtcre

41032E55 cateto 0AB2291F pazxca

HR R

41032E55

H

pttack

Page 25: Rainbow Tables

Cuanto más larga es la cadena (t), más

pequeña es la tabla (m) y más lenta es

la búsqueda

Page 26: Rainbow Tables

Probabilidad de encontrar p

Page 27: Rainbow Tables

mt / N

t / N m / N

Page 28: Rainbow Tables

Problemas

Page 29: Rainbow Tables

La cadena no siempre contendrá el

valor de h buscado

Page 30: Rainbow Tables

Supongamos que buscamos la

contraseña de FB107E70

Page 31: Rainbow Tables

fabada

aaaaaa

pttack

clpert

lpmaee

kiebgt

pazxca

urtcre

FB107E70 7503F4BA kiebgt

HR R

281DAF40 sgfnyd 920ECF10 kiebgt

H HR R

sgfnyd

aaaaaa

Page 32: Rainbow Tables

Falsas alarmas porque R no es

resistente a colisiones

Page 33: Rainbow Tables

Si dos cadenas colisionan en un punto,

cubrirán las mismas contraseñas

Page 34: Rainbow Tables
Page 35: Rainbow Tables

Cuanto mayor la tabla, mayor

probabilidad de colisión …

Page 36: Rainbow Tables

… y menor número de contraseñas

cubiertas

Page 37: Rainbow Tables

No se puede detectar porque no se

almacenan los valores intermedios

Page 38: Rainbow Tables

m

i

t

j

j

éxitoN

it

NP

1

1

0

1)1(1

Page 39: Rainbow Tables

m = N1/3

t= N1/3

Page 40: Rainbow Tables

Para compensar las colisiones se

crean múltiples tablas, l, con funciones

R distintas en cada una

Page 41: Rainbow Tables

lm

i

t

j

j

éxitoN

it

NP

1

1

0

1)1(1

1

Page 42: Rainbow Tables

Solución

Rainbow Tables

Page 43: Rainbow Tables

Philippe Oechslin, “Making a Faster

Cryptanalytic Time-Memory Trade-Off”

Page 44: Rainbow Tables

Usar una función de reducción Ri

distinta para cada elemento de la

cadena

Page 45: Rainbow Tables

¿Pueden existir colisiones ahora?

Page 46: Rainbow Tables

El mismo valor debería coincidir en la

misma posición: Pcolisión = 1/t

Page 47: Rainbow Tables

Tendrían el mismo valor final por lo que

podrían eliminarse duplicados

Page 48: Rainbow Tables

Proceso de creación de tablas rainbow

Page 49: Rainbow Tables

paquito ub40i moscar as400 parapal bix10 admin

duracell re2xei conejos 34ga0 teletubi p3p3l iphone

H

H

H H

H H

R1

R1

R2

R2

R3

secreto yert4 debajo j0s3a arramai 9i0j8a secanot

H H HR1 R2 R3

R3

Page 50: Rainbow Tables

¿Cuál es la contraseña de 34ga0?

Page 51: Rainbow Tables

paquito admin

duracell iphone

secreto secanot

34ga0 picasso

R3

34ga0

Page 52: Rainbow Tables

paquito admin

duracell iphone

secreto secanot 34ga0 teletubi p3p3l iphone

HR2 R3

34ga0

Page 53: Rainbow Tables

paquito admin

duracell iphone

secreto secanot

duracell re2xei conejos 34ga0

H HR1

34ga0

Page 54: Rainbow Tables

AA 2a

H R1 R2 R3

FB h3

H

HT 88

H

ZP 4b

H R4

QT

BB y5

H R1 R2 R3

TJ 4z

H

HT 88

H

ZP 4b

H R4

QT

H R1 R2 R3H H H R4

AA 2a HT 88 UJ b1 KR 22 PO

Page 55: Rainbow Tables

Tablas perfectas

Las que cubren todas las contraseñas

sin colisiones

Page 56: Rainbow Tables

)1(y donde

)1(1

11

1

N

m

n

t

i

iéxito

n

eNmmm

N

mP

Page 57: Rainbow Tables

Aplicaciones de las

rainbow tables

Page 58: Rainbow Tables

¿Cómo almacenan los ordenadores las

contraseñas?

Page 59: Rainbow Tables

Windows Unix

Vista XP, 2000/3 Red Hat Linux Ubuntu Debian Fedora Mac OS X

FUNCIÓN

DES X X

MD5 X X X X

SHA SHA256/512

SHA1

NTLM Hash X X

NT Hash X

Salt X X X X X

Page 60: Rainbow Tables

Hagamos unos cálculos

Page 61: Rainbow Tables

algoritmo hash/s

LM 1.300.728

NTLM 2.623.294

MD5 3.401.360

SHA1 924.898

Page 62: Rainbow Tables

LM NTLM MD5 SHA1

10,7 min 5,3 min 4,1 min 15,1 min

7

1

M3,83526i

i

26 caracteres, longitud <= 7

Page 63: Rainbow Tables

7

1

G6,8036i

i

36 caracteres, longitud <= 7

LM NTLM MD5 SHA1

17,2 h 8,5 h 6,6 h 1,0 días

Page 64: Rainbow Tables

P72G102,72567

1

7

i

i

256 caracteres, longitud <= 7

LM NTLM MD5 SHA1

1.755,3 años 870,3 años 671,2 años 2.468,5 años

Page 65: Rainbow Tables

E67G107,6267

1

10

i

i

26 caracteres, longitud <= 14

LM NTLM MD5 SHA1

1.633.359,2 años 809.881,0 años 624.619,6 años 2.297.070,7 años

Page 66: Rainbow Tables

LM sucks!

Page 67: Rainbow Tables

1. La contraseña se rellena con ceros o se trunca

a 14 bytes

2. Se divide en dos mitades de 7 bytes

3. Se convierten en una cadena binaria para usar

como dos claves DES, insertando un cero

después de cada 7 bits

4. Cada clave se utiliza para cifrar la cadena

KGS!@#$%

5. Los dos textos cifrados resultantes se

concatenan para formar el hash LM de 16

bytes

Page 68: Rainbow Tables
Page 69: Rainbow Tables
Page 70: Rainbow Tables

1Desactiva los hashes LM en Windows

Page 71: Rainbow Tables
Page 72: Rainbow Tables

2Utiliza salts

Page 73: Rainbow Tables

3Utiliza contraseñas complejas

Page 74: Rainbow Tables

Si quieres protegerte frente a las

tablas rainbow…

Page 75: Rainbow Tables
Page 76: Rainbow Tables

gonzaloalvarez.com

elartedepresentar.info