Quote:
Originally Posted by Chainsaw13
I wonder how long a brute force crack would take?
|
The equation you want is called "Anderson's Formula". Here is an example from an Illinois University exam.
4. (30pts) Given an alphabet size of 400, and an opponent capable of checking 24000 passwords a second.
a. [10 pts] What formula would you use to decide on the required size of the password, to achieve an upper bound p on the probability of a brute force attack being successful within a given time period, and a given password cracking processing rate?
Anderson’s Formula P>=TG/N
P – Probability of guessing a password
T – Time
G – No. of guesses in a time period
N – No. of possible passwords
b. [10 pts] Find out the minimum size of the password for an user, if you want probability of discovery within a year to be less than 20%
400**x = (24000*60*60*24*365)/0.2
Solving for x we get x = 4.83385
Therefore password has to be at least 5 characters long
c. [10pts] What limitations, if any, can you identify for the formula used in part a?
Anderson’s Formula is based on the assumption that passwords are uniformly distributed. In practice passwords are not randomly picked and so not uniformly distributed. Therefore an attacker may first go through most common or weak passwords and crack passwords much faster than estimated by Anderson’s formula.
------------------------------------------
Now, for our purposes, we are only using 52 characters (26 upper and 26 lower case letters) and a password length of (about) 50 characters.
So P is the probability of cracking the password.
T is the amount of time, so let's say 1 year. T=60*60*24*365 = 3.1536 * 10**7.
G is the number of guesses per second. A reasonable number is G=50000.
N is the password space size, which for us is 52**50.
So for P>=TG/N, we have:
P >= (3.1536*10**7)*50000)/(52**50)
P >= (1.5768*10**12) /(52**50)
P >= 2.0*10**(-74) is the probability of cracking this password in 1 year or less.
this means that with a 52 character alphabet and a 50 character password that the probability of cracking the password in a year or less is very close to 0.
-------------------------------------------------------
If we want to know how many days it will take to crack the password using brute force, then the formula gives:
1.0 = ((60*60*24*Y)*(50000))/(52**50)
52**50 = Y*(60*60*24*50000)
Y = (52**50) / (4.32*10**9)
Y = 1.46*10**76 days ~= 4*10**73 years
Mind you, this is a statistical average and not a hard floor. It is possible to guess the right password on the first stab, so the minimum is 1 and the average over many passwords (not one specific one) is as above. This is counter-intuitive but the password length really makes all the difference (since it used as an exponent).
PS: in practice, most systems that allow the use of a very long (64-128 character) password really only use a maximum of 8 characters internally for historical reasons. If this is the case, well, then the password will be broken quite fast.
PPS: I'm on Benadryl, so your math may vary and, in fact, be more accurate.
PPPS: As a modern Intel 6 core processor will be able to guess several more orders of magnitude per second and even more if the code is properly threaded, it would be interesting to see how many guesses per second one would need to crack that password on average. This is left as an exercise for the student.
and finally
PPPPS: a network of computers can bring this down even more since breaking up the password space is pretty simple to do, so you could ask how many Intel 6 core computers will it take. Quite possibly not as many as you may think.
from a former computer science instructor whose information security program was a top 25 in the nation as ranked by several TLA (three letter acronym) US government agencies.