Categories
Hacking Generico

Matematica applicata alle Rainbow Tables

Piccolo aneddoto tratto dal forum della community freerainbowtables.
Un utente inesperto stava chiedendo il perchè non fosse possibile creare rainbow tables che riuscissero a craccare 12 caratteri LowerAlpha, UpperAlpha, Number e Symbol (che corrisponde a questo charset: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890!”£$%&/()=?^§)
Ed ecco quà che il matematico del forum (Sc00bz) risponde all’utente:

Why 12 characters, LowerAlpha, UpperAlpha, Numbers and Symbol-14 is infeasible.

log2((26+26+10+14) ^ 12) = 74.98
To store an index you’ll need at least 75 bits but currently everything is in 64 bit numbers. So even if you wanted to do this which will take forever and over 64 EiB of disk space. It will also take a rewrite of how “everything” works.

rows = multiplier * key space / chain length = 10 * (26+26+10+14)^12 / 100,000
size = rows * bytes per row / bytes per EiB = 3,713,326,247,319,550,139 * 20 / 2 ^ 60 = 64.42 EiB

http://en.wikipedia.org/wiki/EiB

** Side Note 1 **
15,000 chains/sec (current speed) means it will only take 7,844,496 years

If you can take into account disk space increases by a factor of 10 about every 5 years and computing power increases by a factor of 2 every 2 years.
So if everyone upgrades their computers every 2 years and no one else joins, then these tables will be done in 44 years, but this will be very expensive for a site that can only raise about $250 in a couple months. The hard drives will be $720/yr and servers well you could buy one or two and just swap out and store the HDs somewhere saving a lot of money on servers.

With that said in 44 years Microsoft won’t even be around so making this for NTLM would be dumb same with MD5, SHA1, SHA256, ect. MD5 “should not used in new applications” and SHA1 is also kinda dead. SHA256 is alive and kicking but the next round of hash functions are being made now and in a few years SHA256 will be kinda dead. Also in 44 years 12 characters, LowerAlpha, UpperAlpha, Numbers and Symbol-14 is only 1.9 years away starting from scratch. Well this is all assuming the world doesn’t end in 2012 :roll:.

** Side Note 2 **
multiplier is not really talked about since it’s just something you find out after you pick key space, chain length, chains/file, files/table, and number of tables.
Let’s look at a real world multiplier.

(I think there’s going to be 4 of these tables)
md5_loweralpha-numeric-symbol32-space#1-7_0_10000x70000000_distrrtgen_0

md5_loweralpha-numeric-symbol32-space#1-7_0_10000x70000000_distrrtgen_219
md5_loweralpha-numeric-symbol32-space#1-7_1_10000x70000000_distrrtgen_0

md5_loweralpha-numeric-symbol32-space#1-7_1_10000x70000000_distrrtgen_219

26+10+32+1 = 69
key space = 69 + 69^2 + … + 69^7 = 7,555,858,447,479
work = chain length * chains/file * files/table * tables (so far) = 10,000 * 70,000,000 * 220 * 2 = 308,000,000,000,000
multiplier = work / key space = 40.76

Chiaro no? 😀

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.