Rainbow TablesGonzalo Álvarez Marañón

“Tengo el hash de

la contraseña.

¿Cómo puedo

obtener la

contraseña

original?”

Los hashes son

funciones

unidireccionales

)( pHhp H

Esto es fácil

ppHh H 1

)(

Esto es difícil

¿Solución?

PppHh iii ),(

Calcular todos los hashes

Calcularlos todos

de una vez

Calcularlos de

uno en uno

t

m

N ≈ m2t

Cadenas de hashes

Hellman Martin, “A Cryptanalytic

Time - Memory Trade-Off”

Función de reducción, R

aaaaaa 281DAF40 sgfnyd 920ECF10 kiebgt

H HR R

Proceso de creación de tablas

aaaaaa 281DAF40 sgfnyd 920ECF10 kiebgt

H HR R

punto inicial punto final

t

fabada F4300A82 mlabaz 941A5BC7 lpmaee

H HR R

aaaaaa kiebgt

fabada lpmaee

aaaaaa kiebgt

pttack 41032E55 cateto 0AB2291F pazxca

H HR R

fabada lpmaee

aaaaaa kiebgt

pttack pazxca

clpert 22F08D16 lmzclo 5A1C048E urtcre

H HR R

fabada lpmaee

aaaaaa kiebgt

pttack pazxca

clpert urtcre

m

… …

La tabla se crea una sola vez

Ordenada por los puntos finales

fabada

aaaaaa

pttack

clpert

lpmaee

kiebgt

pazxca

urtcre

Punto inicial Punto final

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

fabada

aaaaaa

pttack

clpert

lpmaee

admin

pazxca

urtcre

41032E55 cateto 0AB2291F pazxca

HR R

41032E55

H

pttack

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

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

la búsqueda

Probabilidad de encontrar p

mt / N

t / N m / N

Problemas

La cadena no siempre contendrá el

valor de h buscado

Supongamos que buscamos la

contraseña de FB107E70

fabada

aaaaaa

pttack

clpert

lpmaee

kiebgt

pazxca

urtcre

FB107E70 7503F4BA kiebgt

HR R

281DAF40 sgfnyd 920ECF10 kiebgt

H HR R

sgfnyd

aaaaaa

Falsas alarmas porque R no es

resistente a colisiones

Si dos cadenas colisionan en un punto,

cubrirán las mismas contraseñas

Cuanto mayor la tabla, mayor

probabilidad de colisión …

… y menor número de contraseñas

cubiertas

No se puede detectar porque no se

almacenan los valores intermedios

m

i

t

j

j

éxitoN

it

NP

1

1

0

1)1(1

m = N1/3

t= N1/3

Para compensar las colisiones se

crean múltiples tablas, l, con funciones

R distintas en cada una

lm

i

t

j

j

éxitoN

it

NP

1

1

0

1)1(1

1

Solución

Rainbow Tables

Philippe Oechslin, “Making a Faster

Cryptanalytic Time-Memory Trade-Off”

Usar una función de reducción Ri

distinta para cada elemento de la

cadena

¿Pueden existir colisiones ahora?

El mismo valor debería coincidir en la

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

Tendrían el mismo valor final por lo que

podrían eliminarse duplicados

Proceso de creación de tablas rainbow

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

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

paquito admin

duracell iphone

secreto secanot

34ga0 picasso

R3

34ga0

paquito admin

duracell iphone

secreto secanot 34ga0 teletubi p3p3l iphone

HR2 R3

34ga0

paquito admin

duracell iphone

secreto secanot

duracell re2xei conejos 34ga0

H HR1

34ga0

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

Tablas perfectas

Las que cubren todas las contraseñas

sin colisiones

)1(y donde

)1(1

11

1

N

m

n

t

i

iéxito

n

eNmmm

N

mP

Aplicaciones de las

rainbow tables

¿Cómo almacenan los ordenadores las

contraseñas?

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

Hagamos unos cálculos

algoritmo hash/s

LM 1.300.728

NTLM 2.623.294

MD5 3.401.360

SHA1 924.898

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

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

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

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

LM sucks!

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

1Desactiva los hashes LM en Windows

2Utiliza salts

3Utiliza contraseñas complejas

Si quieres protegerte frente a las

tablas rainbow…

gonzaloalvarez.com

elartedepresentar.info