Thursday, January 05, 2012

Is twelve bytes enough?

kw: computers, hacking, passwords

Following up on an earlier post: There are two things a cybercriminal needs to obtain to begin cracking a bunch of passwords from their encrypted record (hashes). Firstly, the file of the hashes themselves, and secondly, knowledge of the hashing algorithm. DES is quite popular, but is by no means the only one in use. The best feature of a good hashing algorithm is that it does not reveal the length of the original password. Heaven help you if your online bank uses a weak hash or doesn't hash at all!

So, having somehow stolen a file of passwords, the cracker proceeds by trying character strings in some logical sequence, producing the hash, and seeing if it matches any of the hashes in the file. This matching step can be very fast, but I suspect it takes a while if you have a million hashes to check.

The record speed of a special-purpose cracking machine is just under 1011 tests per second, when attacking a single hash. Obviously, it is much more efficient to sort the file of hashes using the hash as a key, then use a binary search to check a generated hash. A million hashes can be checked with only ten lookups. Not knowing how long those ten lookups might take, though, I'll continue the analysis by considering a hacker who is determined to get me, and has only one hash to test each iteration, at that 1011/sec rate. What do I need to do to hold off the attack for at least a year? Simply put, since a year has 3.156x107 seconds, I need a password long enough and complex enough to be a member of a universe with at least 3.156x1018 members. To push that out by a factor of a thousand, you need 3.156x1021 members.

Let us assume the perpetrator uses a logical series of steps, based on human nature. Shorter passwords are still most common; lower-case letters only and UPPER-case letters only are very common; adding a numeric digit, or a few, is getting more popular; MiXeD-case is somewhat rarer; mixed case plus digits is very rare, and the addition of special characters is done only if someone forces you to do it, or you are very, very paranoid. Someone having a super-cracker machine won't bother with a dictionary hack, but will just use all combinations.

Here is what it takes, for now, and for ten years from now when a cracking box might be 1,000 times as fast:
  • UPPER- or lower-case only. N = 26L. For L = 13, N = 2.48x1018, not quite enough, so go with 14 letters, where N = 6.45x1019, for now. For later, you need 16 letters
  • Either case plus some digits. N = 36L. For L = 12, N = 4.74x1018, OK for now. For later, L = 14.
  • MixEd-cASe letters. N = 52L. For L = 11, N = 7.52x1018, good for now. For later, L = 13.
  • Now add digits. N = 62L. You still need L=11 for now, because 6210 = 8.39x1017. For later, 12 is enough.
  • Finally, if the full ASCII set is allowed, N = 95L. For L = 10, N = 5.99x1019, more than good enough for now. For later, 11 characters is sufficient.
Of course, as one progresses down this list, it gets harder to remember the password unless you are quite clever creating it. If fourteenletter or FOURTEENLETTER is as hard to crack as M#nE3pa$5w, though, which one is the better choice? And for the future, dEEPsnowINspring, at 16 letters of mixed case, is from a universe of 2.86x1027; probably good for the rest of your life.

No comments: