2013.02.10 - password cracking vs. time

when talking about passwords or passwords' (salted) hashes and time required to break them, we assume that passwords that will take significant amount of years to be break are secure. for instance say you have 10 digits password, with lower and upper case characters, digits and special characters. assuming no extra knowledge about the password, this gives about 82 possible characters at each position. having 10 characters means 13744803133596058624 (~10^19) possible passwords.

now assume that you can check 2 millions passwords per second, which gives 63072000000000 attempts per year (~10^14). btw: note that 2 millions attempts per second is not that much – in fact MD5 can be cracked at a speed of about 200 million passwords per second, on a modern GPU).

using the usual approach, this means that we need:

13744803133596058624 / 63072000000000 = 217922

wow – 217922 years to break it. sounds serious? well… there is “a little” flaw in this approach – we assume the same computer will do the calculations thought all that period. although Moore's law is no longer valid, since few years now, and is expected to end for good in a foreseeable future, due to the physical size limits of the transistor, computing power is not doomed. it is just more networked and more parallel over a time. derived from the Moore's law we could expect roughly 2x speedup over 18 months¹⁾. this gives about 1.33 speedup a year. what is happening is we have more than that with the could computing taking over.

even assuming we have pps=1.33 (processing power) speedup a year, and are starting with apy~=10^14 attempts per year for N years we compute a following number of passwords:

pps*apy^0 + pps*apy^1 + pps*apy^2 + ... + pps*apy^(N-1)

this is of course geometric sequence sum, which is:

apy*(1-pps^N)/(1-pps)

to see how many years will it actually take we need to solve the equation:

apy*(1-pps^N)/(1-pps) = ctt

whre ctt is combinations to test (in our example ~10^19). a little maths and we come up with:

N = ln((apy-ctt*(1-pps))/apy) / ln(pps)

which in our example gives… 38 years! though this is a long time, comparing it to the original results of 217922 years, this gives a significant error! to make things worse, we assumed full search, while on average you are expected to find the result after doing just half of all computations (here: after 36 years). this is hell a lot of time, but definitely within ones lifetime. if you add more computational power, say 1000 machines, we can narrow it to 14 years, and if hash happened to be MD5… on average we're expected to find answer in just over a year!

if you'd like to toy around with with parameters here is the BC script for calculating expected time to crack a password.