Rainbow Tables

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

1. RainbowTables
Gonzalo Álvarez Marañón

2. “Tengo el hashde
la contraseña.
¿Cómo puedo
obtener la
contraseña
original?”

3. Los hashes son
funciones
unidireccionales

4. )(pHhp
H Esto es
fácil

5. ppHh
H
1
)( Esto es
difícil

6. ¿Solución?

7. PppHh
iii ),( Calcular
todoslos
hashes

8. Calcularlos todos
de una vez
Calcularlos de
uno en uno

9. t
m
N ≈ m
2
t

11. Cadenas de hashes

12. Hellman Martin, “A Cryptanalytic
Time -Memory Trade-Off”

13. Función de reducción, R

14. aaaaaa 281DAF40 sgfnyd 920ECF10 kiebgt
H HR R

15. Proceso de creación de tablas

16. aaaaaa 281DAF40 sgfnyd 920ECF10 kiebgt
H HR R
punto inicial punto final
t

17. fabada F4300A82 mlabaz 941A5BC7 lpmaee
H HR R
aaaaaa kiebgt

18. fabada lpmaee
aaaaaa kiebgt
pttack 41032E55 cateto 0AB2291F pazxca
H HR R

19. fabada lpmaee
aaaaaa kiebgt
pttack pazxca
clpert 22F08D16 lmzclo 5A1C048E urtcre
H HR R

20. fabada lpmaee
aaaaaa kiebgt
pttack pazxca
clpert urtcre
m
… …

21. La tabla se crea una sola vez

22. Ordenada por los puntos finales
fabada
aaaaaa
pttack
clpert
lpmaee
kiebgt
pazxca
urtcre
Punto inicialPunto final

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

24. fabada
aaaaaa
pttack
clpert
lpmaee
admin
pazxca
urtcre
41032E55 cateto 0AB2291F pazxca
HR R
41032E55
H
pttack

25. Cuanto más larga es la cadena (t), más
pequeña es la tabla (m) y más lenta es
la búsqueda

26. Probabilidad de encontrar p

27. mt/N
t /N m /N

28. Problemas

29. La cadena no siempre contendrá el
valor de hbuscado

30. Supongamos que buscamos la
contraseña de FB107E70

31. fabada
aaaaaa
pttack
clpert
lpmaee
kiebgt
pazxca
urtcre
FB107E70 7503F4BA kiebgt
HR R
281DAF40 sgfnyd 920ECF10 kiebgt
H HR R
sgfnyd
aaaaaa

32. Falsas alarmas porque Rno es
resistente a colisiones

33. Si dos cadenas colisionan en un punto,
cubrirán las mismas contraseñas

35. Cuanto mayor la tabla, mayor
probabilidad de colisión …

36. … y menor número de contraseñas
cubiertas

37. No se puede detectar porque no se
almacenan los valores intermedios

38. m
i
t
j
j
éxito
N
it
N
P
1
1
0
1
)1(
1

39. m = N
1/3
t= N
1/3

40. Para compensar las colisiones se
crean múltiples tablas, l, con funciones
Rdistintas en cada una

41. l
m
i
t
j
j
éxito
N
it
N
P
1
1
0
1
)1(
1
1

42. Solución
RainbowTables

43. Philippe Oechslin, “Making a Faster
Cryptanalytic Time-Memory Trade-Off”

44. Usar una función de reducción R
i
distinta para cada elemento de la
cadena

45. ¿Pueden existir colisiones ahora?

46. El mismo valor debería coincidir en la
misma posición: P
colisión= 1/t

47. Tendrían el mismo valor final por lo que
podrían eliminarse duplicados

48. Proceso de creación de tablas rainbow

49. paquito ub40i moscar as400 parapal bix10 admin
duracell re2xei conejos 34ga0 teletubi p3p3l iphone
H
H
H H
H H
R
1
R
1
R
2
R
2
R
3
secreto yert4 debajo j0s3a arramai 9i0j8a secanot
H H HR
1 R
2 R
3
R
3

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

51. paquitoadmin
duracelliphone
secretosecanot
34ga0 picasso
R
3
34ga0

52. paquitoadmin
duracelliphone
secretosecanot 34ga0 teletubi p3p3l iphone
HR
2 R
3
34ga0

53. paquitoadmin
duracelliphone
secretosecanot
duracell re2xei conejos 34ga0
H HR
1
34ga0

54. AA 2a
H R
1 R
2 R
3
FB h3
H
HT 88
H
ZP 4b
H R
4
QT
BB y5
H R
1 R
2 R
3
TJ 4z
H
HT 88
H
ZP 4b
H R
4
QT
H R
1 R
2 R
3H H H R
4
AA 2a HT 88 UJ b1 KR 22 PO

55. Tablas perfectas
Las que cubren todas las contraseñas
sin colisiones

56. )1(y donde
)1(1
11
1
N
m
n
t
i
i
éxito
n
eNmmm
N
m
P

57. Aplicaciones de las
rainbowtables

58. ¿Cómo almacenan los ordenadores las
contraseñas?

59. Windows Unix
VistaXP, 2000/3Red HatLinuxUbuntuDebianFedoraMac OS X
FUNCIÓN
DES X X
MD5 X X X X
SHA SHA256
/512
SHA1
NTLM HashX X
NT Hash X
Salt X X X X X

60. Hagamos unos cálculos

61. algoritmo hash/s
LM 1.300.728
NTLM 2.623.294
MD5 3.401.360
SHA1 924.898

62. LM NTLM MD5 SHA1
10,7 min 5,3 min 4,1 min 15,1 min7
1
M3,83526
i
i
26 caracteres, longitud <= 7

63. 7
1
G6,8036
i
i 36 caracteres, longitud <= 7
LM NTLM MD5 SHA1
17,2 h 8,5 h 6,6 h 1,0 días

64. P72G102,7256
7
1
7
i
i 256 caracteres, longitud <= 7
LM NTLM MD5 SHA1
1.755,3 años870,3 años671,2 años2.468,5 años

65. E67G107,626
7
1
10
i
i 26 caracteres, longitud <= 14
LM NTLM MD5 SHA1
1.633.359,2 años809.881,0 años624.619,6 años2.297.070,7 años

66. LM
sucks!

67. 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 textoscifradosresultantesse
concatenanparaformarel hash LM de 16
bytes

70. 1
Desactiva los hashes LM en Windows

72. 2
Utiliza salts

73. 3
Utiliza contraseñas complejas

74. Si quieres protegertefrente a las
tablas rainbow…

76. gonzaloalvarez.com
elartedepresentar.info