quick.links

recent.news

2010-09-14 - the slides from my recent (re-)presentation (with lots of extra bits) at SEC-T 2010, will soon be online! exploit code [...]

2009-12-18 - The slides from my recent presentation at CRESTCon 2009, the 'replacement' for CHECKCon, are now online! exploit code for the demonstrations [...]

:.home.other stuff.breakingrandom passwords

how random is your password?

"Anyone who considers arithmetical methods of producing random digits is,
of course, in a state of sin" - John von Neumann

MkPasswd

MkPasswd is a random password generator written by Tim Brown, it is written in PERL and licensed under the GPL. The algorithm itself is capable of constructing random passwords of a fixed length of 8 characters and utilises lower/upper-case alphanumeric characters extended with a subset of special characters. The latest version of MkPasswd is available from: MkPasswd-1.2.tar.gz (local, as of September 21st 2007, there have been 308 downloads).

Algorithm

MkPasswd Algorithm

where Pc, [a,b]c denotes the cth element of the list P and the set/range [a,b] respectively. Furthermore, the set U corresponds to the set of characters,

U = {"`", "!", "\"", "%", "^", "&", "*", "(", ")", "_", "-", "+", "=", "{", "}", "[", "]", ":", ";", "~", "'", "<", ">", ",", ".", "|"}

Analysis

The number of possible passwords for the MkPasswd algorithm is given below, compared to the total number of possible lower/upper-case alphabetic passwords of length 8:

However, it is possible to further reduce this bound by observing that the algorithm can never construct a password containing the characters "z", "Z", "9" or "|", this has the effect of further reducing the number of permissable passwords to:

Code

mkpasswd.c attacks the MkPasswd algorithm through its dependance on the time() system call. The algorithm generates (and tests) all "possible" passwords for values of time() less-than a given value (or the current time()).