2011-06-14

GRC haystack 2 - rainbow tables

I did not intend to spend so much time on this topic but @itinsecurity had the time to listen to the 37 minute podcast and the claim is this padding scheme is immune to rainbow tables.  I intentionally did not do rainbow table analysis because I already had a long post.  Also, to even enter this discussion we have to assume the application in question does not store passwords plaintext and instead hashes them.  Additionally, we assume the attacker already has all the hashes.

Lets start with
password: Summer
[A-Za-z][a-z]{5}
52^1 * 26^5 which is roughly 2^29.203

Lets pick some potential padding characters: [., ].  Alright how about the character sets:
[A-Za-z][a-z]{5}[a-z., ][., ]{1,4}
52^1 * 26^5 * 29^1 * 120 which is roughly 2^40.968
length 8 to 11

[A-Za-z][a-z]{5}[a-z., ][., ]{1,8}
52^1 * 26^5 * 29^1 * 9840 which is roughly 2^47.325
length 8 to 15


Perhaps users will cease to append years to the end of the password and add a padding character every password change?  Alright lets go for larger character sets:
[A-Za-z][a-z]{5}[a-z.,<->\*\[\] ][.,<->\*\[\] ]{1,4}
52^1 * 26^5 * 35^1 * 7380 which is roughly 2^47.181
length 8 to 11

Does this mean it is rainbow table proof?  Hardly.  It just means traditional tables may not be useful but plenty of options exist to defeat them: length, unicode, etc.  Sure some users may put padding at the beginning, at the end, make it really long, etc. but this just gets silly.  Using 4 randomly selected words from diceware's list gives you 7776^4 or 2^51.699 and that's purely lower case, no padding, no symbols, etc.  Average length of a word is 4.2 characters.

No comments:

Post a Comment