[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20110220043556.GA8624@openwall.com>
Date: Sun, 20 Feb 2011 07:35:56 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com, passwdqc-users@...ts.openwall.com
Subject: passwdqc vs. KoreLogic's DEFCON 2010 contest passwords
Hi,
In team john-users contest writeup, I wrote:
"The files released by KoreLogic will play an important role in testing
and tuning of current and future password security software and
techniques. It is now possible to derive lists of cracked and uncracked
passwords. These passwords, through their hashes, have been tested by
many people from many teams using significant cumulative computing
resources, as well as many different tools, techniques, and wordlists.
This makes them very valuable."
http://contest.korelogic.com/team_john-users.html
Today, I finally got around to using those passwords to test passwdqc,
our password strength checking and policy enforcement tool set.
I have passwdqc 1.2.2 installed:
http://www.openwall.com/passwdqc/
This version was released prior to the contest, so it was not influenced
by the contest in any way.
My input files for this experiment were:
all_passwords.txt, uncracked-md5.txt, uncracked-ntlm.txt as released by
KoreLogic, along with
KoreLogic_Defcon2010.pot generated by Matt Weir:
http://www.openwall.com/lists/john-users/2010/08/24/1
I picked two hash types: one salted and somewhat slow (albeit not very
slow), the other non-salted and very fast. Neither has any other
special properties that would substantially affect my results (unlike
e.g. LM hashes).
I started with the MD5-based crypt(3) hashes:
$ grep '^\$1\$' KoreLogic_Defcon2010.pot | cut -d: -f2- | sort -u > all-md5
$ sort -u uncracked-md5.txt > uncracked-md5
$ comm -23 all-md5 uncracked-md5 > cracked-md5
$ wc -l all-md5
4716 all-md5
$ wc -l cracked-md5 uncracked-md5
1543 cracked-md5
3173 uncracked-md5
4716 total
These numbers are "close enough" to those posted on the contest website:
http://contest.korelogic.com/stats.html
The posted numbers are 1557 cracked, 3224 uncracked. I don't know why
the discrepancy, but since there are some other discrepancies in the
posted numbers anyway, I am going to just accept/ignore it.
Now to test passwdqc, using its pwqcheck command-line program (by the
way, passwdqc also includes a PAM module and a library, and there's a
wrapper script for PHP):
$ pwqcheck -1 --multi < cracked-md5 > cracked-md5-pwqc
$ pwqcheck -1 --multi < uncracked-md5 > uncracked-md5-pwqc
$ grep -c ^OK: cracked-md5-pwqc
54
$ grep -c ^Bad cracked-md5-pwqc
1489
$ grep -c ^OK: uncracked-md5-pwqc
1419
$ grep -c ^Bad uncracked-md5-pwqc
1754
In other words, passwdqc with its default settings would permit 54
cracked passwords to pass. It would reject 1489 of those.
54 corresponds to 3.5% of the total number of cracked passwords (1543)
and to 1.1% of all passwords tested (4716).
Of the uncracked passwords, passwdqc would reject 45% (presumably those
were "crackable", just not cracked during the contest) and permit 55%
(presumably those were mostly "uncrackable", although indeed this
assumption may and will sometimes fail).
Overall, users would be permitted to set 31% of the passwords (1473 out
of 4716). Indeed, a policy that rejects two thirds (or even more) of
passwords that users would presumably attempt to set would make some
users upset... Yet the numbers above also show that there was little
room (if any) for relaxing the policy (as long as we consider offline
attacks on the hashes at all).
Looking at the 54 cracked yet permitted passwords, it is seen that many
of them were cracked due to their reliance on words from the tiny
contest specific wordlist. Many were permitted because of passwdqc not
using large external wordlists (it mostly relies on other kinds of
checks, then uses a tiny embedded wordlist) - this may be something for
us to improve. On the other hand, this also confirms that support for
larger wordlists is not terribly important - 3.5% and 1.1% are
significant percentages, but they are (arguably) not too large (it
depends on value of individual accounts, though).
Here's how this number can be reduced with adjustments to passwdqc
policy settings:
$ pwqcheck -1 --multi min=disabled,24,11,8,7 < cracked-md5 | grep -c ^OK:
54
$ pwqcheck -1 --multi min=disabled,24,11,9,8 < cracked-md5 | grep -c ^OK:
24
$ pwqcheck -1 --multi min=disabled,24,11,10,8 < cracked-md5 | grep -c ^OK:
15
$ pwqcheck -1 --multi min=disabled,24,11,10,9 < cracked-md5 | grep -c ^OK:
10
The first command above was a sanity check, specifying a default policy
setting explicitly. Yes, 54 cracked passwords are permitted with that
default setting. Other commands alter the policy, ultimately reducing
the number of cracked passwords that would pass from 54 to 10. Of
course, such changes also result in fewer of the uncracked passwords
being accepted:
$ pwqcheck -1 --multi min=disabled,24,11,9,8 < uncracked-md5 | grep -c ^OK:
856
$ pwqcheck -1 --multi min=disabled,24,11,10,8 < uncracked-md5 | grep -c ^OK:
520
$ pwqcheck -1 --multi min=disabled,24,11,10,9 < uncracked-md5 | grep -c ^OK:
326
As you can see, such policy changes would annoy the users a lot more,
which confirms that the defaults were sane.
Now let's see the effect of another setting. Sanity check (default
specified explicitly):
$ pwqcheck -1 --multi match=4 < cracked-md5 | grep -c ^OK:
54
Actual test:
$ pwqcheck -1 --multi match=3 < cracked-md5 | grep -c ^OK:
24
$ pwqcheck -1 --multi match=3 < uncracked-md5 | grep -c ^OK:
934
That's a little bit better - we got down to 24 cracked yet permitted
passwords, yet reduced the number of permitted uncracked passwords to
934 rather than to 856 (like we did with min=disabled,24,11,9,8).
However, a reason why we (the authors of passwdqc) did not make match=3
the default is that some of the resulting rejects would be confusing to
users, unlike rejects caused by min=..., which are easily explained.
So, once again, this confirms that the defaults are sane.
We can also try a combination of these changes:
$ pwqcheck -1 --multi min=disabled,24,11,9,8 match=3 < cracked-md5 | grep -c ^OK:
10
$ pwqcheck -1 --multi min=disabled,24,11,9,8 match=3 < uncracked-md5 | grep -c ^OK:
418
We happened to get to the exact same risk level (as far as these tests
permit us to estimate) that we could achieve with
min=disabled,24,11,10,9, but we reduced the number of permitted
uncracked passwords to 418 rather than to 326. So this is a reasonable
combination of settings, albeit extremely annoying to users (only 9% of
their presumably desired passwords would be accepted).
Now to NTLM hashes:
$ grep '^\$NT\$' KoreLogic_Defcon2010.pot | cut -d: -f2- | sort -u > all-nt
$ tail +2 uncracked-ntlm.txt | sed 's/ .*$//; s/ .*$//' | sort -u > uncracked-nt
$ comm -23 all-nt uncracked-nt > cracked-nt
$ wc -l all-nt
30641 all-nt
$ wc -l cracked-nt uncracked-nt
28775 cracked-nt
1870 uncracked-nt
30645 total
There's some minor discrepancy, presumably due to passwords ending with
whitespace characters. Unfortunately, KoreLogic released
uncracked-ntlm.txt in a format inconsistent with that of
uncracked-md5.txt (full John the Ripper output while cracking vs.
cracked passwords only). These numbers are similar to those published
by KoreLogic on the contest website, but there's minor discrepancy with
those as well. Like before, I am going to accept/ignore it.
Let's test the passwords:
$ pwqcheck -1 --multi < cracked-nt > cracked-nt-pwqc
$ pwqcheck -1 --multi < uncracked-nt > uncracked-nt-pwqc
$ grep -c ^OK: cracked-nt-pwqc
10032
$ grep -c ^Bad cracked-nt-pwqc
18743
$ grep -c ^OK: uncracked-nt-pwqc
1611
$ grep -c ^Bad uncracked-nt-pwqc
259
As expected, things are a lot worse. passwdqc would permit as many as
35% of cracked passwords, or 33% cracked of all. This tells us that
applying a password policy when the hash type is weak (saltless and very
fast) is of very limited help against offline attacks on the hashes (it
is of more help against remote attacks). Yet a reduction of the
percentage of cracked passwords from 94% to something like 33% would be
somewhat helpful. Unfortunately, this is not exactly what would happen:
when a user's desired password falls into the rejected 62%, the user
would not always pick a password that would not get cracked. In many
cases, they would just bypass the policy (which is something the contest
passwords tried to demonstrate, applied to other/dumber policies).
Assuming that the likelihood of a passing password getting cracked stays
the same for subsequent attempts of a user to set a password (not an
entirely correct assumption), with NTLM there may be a 33% chance of an
eventually-accepted password getting cracked. This gives us the
following estimate: 33% plus (33% of 62%) = 53% passwords would get
cracked from their NTLM hashes on a system with passwdqc deployed.
This effect is also present for better hash types, but I expect that its
consequences are a lot less significant there. Using the same approach,
we get the following estimate for the MD5-based crypt(3) hashes:
1.1% plus (1.1% of 69%) = 1.86%.
Now, the effect of stricter policies on NTLM:
$ pwqcheck -1 --multi min=disabled,24,11,9,8 < cracked-nt | grep -c ^OK:
5573
$ pwqcheck -1 --multi min=disabled,24,11,10,8 < cracked-nt | grep -c ^OK:
3377
$ pwqcheck -1 --multi min=disabled,24,11,10,9 < cracked-nt | grep -c ^OK:
2136
$ pwqcheck -1 --multi match=3 < cracked-nt | grep -c ^OK:
6051
$ pwqcheck -1 --multi min=disabled,24,11,9,8 match=3 < cracked-nt | grep -c ^OK:
2577
$ pwqcheck -1 --multi min=disabled,24,11,10,9 match=3 < cracked-nt | grep -c ^OK:
1320
Wow, this makes a difference, but even with extreme policies the
percentage of cracked passwords is significant: 1320 of 30645 is 4.3%.
Let's see the side-effect of these policies (fewer of the uncracked
passwords being accepted):
$ pwqcheck -1 --multi min=disabled,24,11,9,8 < uncracked-nt | grep -c ^OK:
1059
$ pwqcheck -1 --multi min=disabled,24,11,10,8 < uncracked-nt | grep -c ^OK:
696
$ pwqcheck -1 --multi min=disabled,24,11,10,9 < uncracked-nt | grep -c ^OK:
454
$ pwqcheck -1 --multi match=3 < uncracked-nt | grep -c ^OK:
1391
$ pwqcheck -1 --multi min=disabled,24,11,9,8 match=3 < uncracked-nt | grep -c ^OK:
769
$ pwqcheck -1 --multi min=disabled,24,11,10,9 match=3 < uncracked-nt | grep -c ^OK:
188
$ pwqcheck -1 --multi min=disabled,24,11,10,9 match=3 < all-nt | grep -c ^OK:
1508
So the extreme policy where only 4.3% cracked passwords of all would be
permitted has a side-effect where it would only permit 4.9% of all. In
other words, a user only has a 0.6% chance of getting a new password
accepted from the first try. When their password gets rejected, which
happens 99.4% of the time, they may end up picking a password that will
fall into the 4.3% crackable ones. Using the same approach at
estimating the effect of this, we conclude that we'll have 8.6%
"crackable" passwords even with an extreme policy like this.
My conclusion is that password policies make little sense as it relates
to offline attacks against weak hashes (saltless and fast), but they
make a lot of sense as it relates to non-targeted offline attacks on
proper hashes (salted and slow). (For targeted attacks on individual
high-value accounts, things could be different - somewhere inbetween,
because the effect of salts is "undone", but the slowness of hashes
remains.)
I tested passwdqc on real-world passwords before (using some of the many
public lists of hashes and their corresponding cracked passwords, which
may be found e.g. on insidepro.com forums), with similar results and with
the same conclusion. The percentages of cracked yet passing passwords for
salted and slow hashes were somewhat lower, though. Perhaps the
combined performance of the contest teams exceeded that of volunteers on
those forums, which is what made this data more valuable (in a sense).
Perhaps hints given during the contest, such as via cracked passwords of
other hash types, have resulted in more passwords being cracked.
Finally, here are the 54 cracked yet permitted passwords:
$ grep ^OK: cracked-md5-pwqc
OK: !$Defcon06
OK: !@...g@S
OK: !ASv3gAs
OK: !Asv3gAs
OK: ##Lasvegas
OK: $:Lasvegas
OK: $a1vator3
OK: $vegas210
OK: &%Korelogic
OK: 00Nets2'
OK: 01Bears2:
OK: 01^Doven
OK: 03Bears6:
OK: 04Kings7:
OK: 68:busadm
OK: :#Mtnbike
OK: :'Whiteh@t
OK: :Oct2010
OK: :\k0rel0g1c
OK: Aug??2010
OK: C0rn3liu$
OK: Cavel:676
OK: Chri$t0pher
OK: Cuteme13:
OK: Defc:on1988
OK: Defcon2008!
OK: Febr112!
OK: Febr117$
OK: Febr118$
OK: Fodge:703
OK: Janu113@
OK: Janu117!
OK: Kri$t0f3r
OK: Oesch:212
OK: Red Banks
OK: Rio Verde
OK: Sept113$
OK: Vega:s994
OK: ^:L4sv3g4s
OK: chri$top3r
OK: cool2010@
OK: december.2009
OK: defco.n2009
OK: febr110@
OK: hello_2010
OK: hotdog2010@
OK: janu112$
OK: kORE1OGIC
OK: korelOG1c
OK: kri$toph3r
OK: r00$3v31t
OK: sept114$
OK: sept119$
OK: {:Defcon
These 24 would remain with a stricter policy:
$ pwqcheck -1 --multi min=disabled,24,11,9,8 < cracked-md5 | grep ^OK:
OK: !$Defcon06
OK: !ASv3gAs
OK: !Asv3gAs
OK: ##Lasvegas
OK: $:Lasvegas
OK: &%Korelogic
OK: 01Bears2:
OK: 03Bears6:
OK: 04Kings7:
OK: 68:busadm
OK: :\k0rel0g1c
OK: Chri$t0pher
OK: Defc:on1988
OK: Defcon2008!
OK: Kri$t0f3r
OK: Oesch:212
OK: Rio Verde
OK: Vega:s994
OK: ^:L4sv3g4s
OK: december.2009
OK: defco.n2009
OK: hotdog2010@
OK: kri$toph3r
OK: r00$3v31t
These 24 would remain with another stricter policy:
$ pwqcheck -1 --multi match=3 < cracked-md5 | grep ^OK:
OK: !$Defcon06
OK: !ASv3gAs
OK: !Asv3gAs
OK: ##Lasvegas
OK: $:Lasvegas
OK: &%Korelogic
OK: 01Bears2:
OK: 03Bears6:
OK: 04Kings7:
OK: 68:busadm
OK: :\k0rel0g1c
OK: Chri$t0pher
OK: Defc:on1988
OK: Defcon2008!
OK: Kri$t0f3r
OK: Oesch:212
OK: Rio Verde
OK: Vega:s994
OK: ^:L4sv3g4s
OK: december.2009
OK: defco.n2009
OK: hotdog2010@
OK: kri$toph3r
OK: r00$3v31t
These 10 would remain with the strictest reasonable policy:
$ pwqcheck -1 --multi min=disabled,24,11,9,8 match=3 < cracked-md5 | grep ^OK:
OK: !$Defcon06
OK: :\k0rel0g1c
OK: Chri$t0pher
OK: Defc:on1988
OK: Defcon2008!
OK: ^:L4sv3g4s
OK: december.2009
OK: defco.n2009
OK: hotdog2010@
OK: kri$toph3r
Indeed, "Defcon", "Christopher", "December", and "hotdog" are not on
passwdqc's embedded tiny wordlist... which may be something to address
in one way or another. Yet it's only 10 of 4716, so things are not
exactly bad.
I hope many of you will find this posting useful, despite of its length.
Comments are welcome.
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
