 |
|
|
"Crack Me If You Can" - DEFCON 2010 |
|
Back to [Teams] [Top]
Team john-users Link to original writeup (external) Graph of john-users' score over time Resources
Please refer to the full "Thanks" section at the end of this writeup for
more detail. (It was too long to start the writeup with it.)
The team and contributors.
With almost all cracked password uploads, except for a few early ones,
there was huge overlap with passwords cracked by others on our team -
typically on the order of 90% or more (that is, only around 10% or less
of independently-cracked passwords tended to be new/unique rather than
already cracked by others on our team).
Yet we're grateful to all who have contributed! The small numbers of
non-overlapping passwords simply reflect the nature of password cracking
and password security, confirming that it makes sense to detect and
eliminate weak passwords (then only relatively few of the remaining ones
are crackable by another attacker).
Computing resources.
Matt's probabilistic cracker (uses JtR) - used by Matt only.
rcracki-mt (on LM hashes, mostly overlapping with those cracked by JtR) -
used by Dhiru (LM) and Guth (Oracle SYS and SYSTEM usernames).
rcrack - used by jmk to crack the remaining two LM hashes.
ighashgpu (on NTLM hashes, cracking a total of 1732 by far most of which
overlapped with hashes cracked by JtR) - used by Dhiru only.
Custom code written or modified during the contest.
JtR wordlist rules and external modes.
Custom shell scripts to automate merging of uploaded files, to generate
cracked/uncracked password/hash lists and .chr files for the team to
possibly reuse, and to make contest submissions (on cron).
Wordlists.
Thus, people were joining during the first day of the contest (when some
of us were already cracking the hashes). Solar was completing setup of
the file exchange server, creating accounts, adding SSH keys,
troubleshooting some team members' login issues, etc. during the
contest. We used an OpenVZ container with and on an Owl system
(Openwall's Linux distro), with per-person accounts and some shared
directories, with file permissions set/adjusted during the contest as
needed - and eventually with some scripts on cron. Solar also setup a
private mailing list for discussions internal to the team; by the end of
the contest, we had 11 subscribers (most of them active team members,
some not - we gave everyone a chance).
The coordination was very loose, largely because of the lack of advance
planning, because Solar was also one of the primary people to actually
attack the hashes (leaving a lot less time for coordination), because it
is hard and often unreasonable to avoid overlap (avoiding it costs
people's time, so we could as well throw more CPUs at the task instead),
and frankly because many of us appeared to be unwilling to coordinate
(most went with whatever they liked to do, which is quite natural, yet
it resulted in higher overlap in attacks attempted and hashes cracked).
How the different hash types were approached.
Soon we reliably identified all hash types but the Oracle hashes, which
we were not 100% sure of.
As suggested by some team members, the hashes list that was provided to
us was eventually split into separate files by hash type, and then we
also created separate files with admin accounts only (which we assumed
were those with a GID of 0 or/and with the "admin" substring in the
username). This was not essential for use with JtR (which is why it was
not done right away), yet apparently it was convenient to some of us.
Closer to the end of the first day, we also had a cron job producing
per-hash-type lists of uncracked hashes - for faster further attacks on
salted hashes.
For all hash types, we ran JtR with default settings against them at
least briefly to catch the weakest passwords first. The per hash type
sections below mostly describe other attacks.
Anyhow, early attacks against NTLM hashes, besides JtR's default
settings, included runs of the RockYou list (with duplicates purged)
with small rulesets, and runs of smaller wordlists (password.lst,
RockYou Top N) with larger rulesets. Specifically, the "single crack"
mode ruleset was used with wordlist mode, and its "crazy" section was
uncommented and even expanded with 4-digit append/prepend rules.
A further attack was to run rockyou.chr released by Kore against NTLM
hashes on a Q6600 machine that Solar temporarily dedicated for the
purpose. The workload was distributed across 4 CPU cores by password
length: 0-5, 6, 7, and 8. The 0-5 run completed shortly, and was
replaced by other quick attacks (sequentially, sometimes leaving this
core mostly-idle for quite a while). These included --external=Keyboard
for lengths 1 to 10 (and a bit of 11), which only cracked a password of
length 7 and lots of length 8 (Kore, this lengths distribution is not
realistic). It also included four modified-KnownForce runs to
exhaustively search the abcd19nn, abcd20nn, 19nnabcd, and 20nnabcd
patterns (identified from previously cracked passwords), where abcd was
an arbitrary string of four lowercase letters ("aaaa" through "zzzz")
and nn was an arbitrary two-digit string ("00" through "99").
Closer to the second day of the contest, a list of contest-specific
words was compiled. Although early revisions of the list varied a bit,
ultimately (for our team) it was:
korelogic defcon Defcon blackhat facebook lasvegas LasVegas vegas
whitehat hello 1234 jan feb mar apr may jun jul aug sep oct nov dec
january february march april may june july august september october
november december janu febr marc apri augu sept octo nove dece monday
tuesday wednesday thursday friday saturday sunday one two three four
five six seven eight nine ten eleven twelve twenty thirty fourty fifty
sixty seventy eighty ninety hundred thousand million billion winter
spring summer autumn wintertime springtime summertime autumntime
(although some people on the team had their own lists). Yes, "fourty"
was misspelled, and this was not noticed, unfortunately (should have run
a spellchecker over the wordlist). Also, this did not include "fall" as
it did not appear to be common enough, but looking at Kore's published
rulesets it is there along with the common words above.
This list was run (on a free core of yet another quad-core machine)
against NTLM hashes with very large numbers of rules (a few million
after preprocessor expansion). Specifically, a very effective ruleset
line was:
We also combined this with case toggling. This was done by outputting
the tiny wordlist mangled with one set of rules (such as the above) to
"unique" and saving to a file, then applying a case-toggling ruleset
(the default "NT" ruleset or the like) to the resulting file.
Besides using the tiny contest-focused wordlist on its own, we were
combining it with itself (to form strings such as "sixtysix") and with
other common password lists using a variation of mix.pl (mentioned
above). And we also ran the above rules (and the dual-application of
rules approach) against common password lists on their own. We also
used "regular" rulesets (like the "single crack" mode one) against these
combined wordlists. All of this was very effective and quite quick.
Another very effective approach was to use all substrings of cracked
passwords (rather than cracked passwords in their entirety only) for
"wordlists". Substrings were being extracted with:
Then cracked-substr was subjected to the kinds of processing described
above (mix.pl and/or dual-applied rulesets).
Although the above text uses "we", these things were pretty much done by
Solar alone (others were invited to apply similar processes and extend
or revise them to reduce overlap, but did not report on having done so).
Overall, this cracked thousands of NTLM hashes, but it is impossible to
tell exactly how many because of the reuse of previously-cracked
passwords for wordlists (including those cracked by others on the team
who were using other methods).
At about the same time, Dhiru was running some NTLM hashes through
ighashgpu, eventually uploading 1732 of cracked passwords (a small
number compared to what the approaches described above achieved), most
of which overlapped with those cracked with JtR (but there were some
unique/new ones as well - mostly those containing more than two uncommon
characters).
On the second day of the contest, Solar made a build of JtR capable of
applying incremental mode to lengths up to 10:
http://www.openwall.com/lists/john-users/2007/07/04/6
The corresponding .chr file was generated based on contest passwords
cracked by that time. It was then run against NTLM hashes separately
for length 9 and length 10 on two CPU cores (on a third quad-core
machine that was finally put to use). It quickly cracked some new
passwords, but then its progress slowed down a lot (as expected).
Overall, by contest end this cracked only about 150 of new passwords.
Finally, closer to the end of the contest large wordlists such as
wikipedia-wordlist-sraveau-20090325 were run against NTLM hashes with
various rulesets created by that point. Some of those runs completed
quickly (resulting in hundreds of new cracks), whereas a couple of
others were still running by contest end time and slowly cracking more
passwords (on one of Solar's machines).
The limiting factor appeared to be the time of people on our team.
With more effort (not requiring any more computing power), we could have
reverse-engineered more of Kore's rules, patterns, and wordlists, which
would enable cracking more of the passwords before contest end. Without
those sufficiently specific rules and patterns, we had to be using more
generic but less efficient rules and wordlists, and we did not run
specific attacks on certain patterns that were seen. For example, we
never derived the exact list of Kore's character substitutions, although
we had the material to do so. We simply dropped not-so-common "Kore
words" such as "stdio" or sports teams because no one on our team would
compile a complete list of them anyway (so we were combining very common
"Kore words" listed above with pre-existing common (pass)word lists
instead). This was largely compensated for by the "all substrings"
approach, though, which obviously caught all common and not-so-common
words seen in cracked passwords (but it also caught some "noise").
One approach we considered on the second day of the contest was
auto-generating rulesets based on cracked passwords. JimF had posted
something along these lines to the john-users list in 2009:
http://www.openwall.com/lists/john-users/2009/07/27/3
There was a brief attempt (by Solar) to get someone interested in trying
this out - but almost no one was interested/available (it was just 12
hours to go). One person volunteered, but then never reported anything
back. It would still be curious to explore this area on contest hashes
even after the contest has ended.
Although we cracked all LM hashes, there was an issue with submitting
the corresponding passwords properly (see below).
As an exception, bartavelle actually spent some time on them,
re-encoding them from base64 to hex such that he could use his
unreleased faster raw SHA-1 code instead of the Netscape LDAP specific
code. Then he had to have them re-encoded back to base64 for
submission, because our submission script would filter out non-contest
hashes, which was in turn caused by one of the team members not cleaning
up their pot file for the contest. ;-)
The years range was previously determined from incremental mode runs
against NTLM hashes and then from the modified-KnownForce run over a much
wider years range against the NTLM hashes, which was described above.
Somehow this years range is slightly inconsistent with rules published
by Kore; we did not investigate whether it was due to an error on our
part or due to Kore using only a subset of the hashes that their
rulesets could generate. Anyhow, for NTLM hashes restricting the years
range did not matter, but for DES-based crypt ones it did (we'd need to
dedicate more than two CPU cores to the task to complete the exhaustive
search in time if the range were wider).
The above was done by Solar, informing others on the team in case anyone
would want to do it for other hash types (besides NTLM and DES crypt),
but apparently that was never done (which was OK - we did not have all
that many other hash types suitable for this attack given the resources
and time available... although SHA and SSHA were suitable).
elijah also did incremental mode runs against these hashes using
contest-specific .chr files (based on previously cracked passwords), and
he tried some custom substitution rules, as well as this ruleset
previously posted by Minga:
http://www.openwall.com/lists/john-users/2009/03/28/2
Given its origin, we probably should have played with it more (e.g.,
updated for year 2010 and ran against other hash types as well), but we
did not. On the other hand, other attacks we performed against NTLM
hashes should have covered these patterns.
Some others tried cracking the DES-based crypt hashes by various means
as well, but overall we did not focus on them as much as we did on NTLM.
Running an OpenMP-enabled build against these hashes (the 20 admin ones
only) on a dedicated quad-core machine (and we had some spare ones) was
briefly considered (by Solar), but was not attempted - running more
focused attacks against NTLM hashes appeared to be a better use of time.
Looking at the plaintext passwords published by Kore after contest end,
some of these could probably be cracked by running heavier rules on
cracked passwords from other hash types - but even that kind of attack
would be very time-consuming (albeit feasible) and hardly worth it
against hashes of this type (it would make more sense to focus on
uncracked admin hashes of other types), unless the scoring were different.
http://www.openwall.com/lists/john-users/2010/08/02/11
As it turned out (was noticed by us during the contest), Kore's
passwords contained an abnormally high number of colons. Of the
passwords we cracked, about 1000 contained colons. For submissions in
john.pot format, this would make no difference (although it could have
affected scripts we'd use during password cracking). However, when Kore
clarified that they wanted only the plaintexts, and complete ones for LM
hashes, Solar quickly hacked together a script that used "cut -d: -f2"
on a john.pot format file for non-LM hashes and
"john --show ... | cut -d: -f2" for LM hashes, planning to get back to
correcting this at a later time. Unfortunately, this was only recalled
1 hour before contest end, at which time Solar, needing to focus on lots
of contest-related tasks at once, only had sufficient time to make the
trivial change of "-f2" (field two only) to "-f2-" (fields starting with
the second) for non-LM hashes. The same trivial change would not work
right for LM hashes due to "john --show" output containing more than two
colon-delimited fields. A slightly more complicated fix for LM hashes
was introduced and tested only 10 minutes _after_ contest end (so if
Kore ever publishes scores for post-content submissions, this should be
seen). This should have affected hundreds of LM hash passwords.
Another issue was with DES-based crypt hashes, which process only 7 bits
of each character (ignoring the 8th bit). This means that for a given
valid passwords, many variations of it are possible (with the 8th bit of
every character possibly flipped), most of which will not match those on
Kore's list of correct passwords, yet all of them are correct. We ended
up submitting some of these passwords with the 8th bit on some
characters set (just because this is what was tested first in certain
attacks run by some members of our team). In many cases (but not in
all), we also had the pure 7-bit versions of the same passwords cracked,
and these were also being submitted (due to the non-use of "john --show"
for this hash type, all variations that we had cracked were being
submitted). This was noticed during the contest, and ideally we'd
convert all of these passwords to pure 7-bit, but we didn't have time
and arguably this was not worth the bother (it affected maybe around 100
passwords). We do not know whether Kore's scripts were smart enough to
count these valid passwords with 8-bit characters towards our team's
score or not.
Finally, it appears that some yet unidentified software in use by two
members of the team did not handle backslashes in passwords correctly.
Some of their uploads contained missing, double, or quadruple
backslashes in place of single backslashes in passwords. Luckily, most
of those passwords were also cracked by others of us, and all variations
were being submitted for all hash types but LM. For LM hashes, this
might have affected our score somewhat.
Overall, we deserve some penalty on our contest score (which we must in
fact have incurred) for not being very careful with our submissions.
Making use of otherwise-idle CPU cycles only.
For machines running OpenVZ kernels (two of the three quad-core
machines that were put to use), a dedicated OpenVZ container with an
x86-64 build of Owl was created (from a recent pre-created template
released by Openwall). The container was set to have a relatively low
number of cpuunits - specifically, it was set to 100 cpuunits, whereas
all others on the system were set to at least 1000 cpuunits each. Then
JtR's "Idle" setting was disabled (set to "N"), because OpenVZ uses a
two-level CPU scheduler anyway and we only needed to be "nice" to other
containers running on the system. Some quick tests proved that this
worked as expected.
For a machine running a "regular" (non-OpenVZ) Linux kernel, the "Idle"
setting was made use of (kept at its current default of "Y"), which had
been tested to work well before (during John development).
Summary.
The passwords were not real, and the distribution of different kinds of
passwords was somewhat non-realistic... but so what. This meant that
part of the challenge was for us (and for other teams) to quickly adapt
to attacking these somewhat unusual passwords. This also meant that
certain techniques that didn't work very well in this contest would have
in fact worked much better on real-world passwords, and vice versa.
For example, a few of the passwords hashed with Blowfish-based crypt
could be a lot weaker (and would actually get cracked): there exist
many systems that use hashes of this type without any password policy
enforcement. Most of the Oracle passwords would be weak and would get
cracked, and the corresponding usernames would be known reliably.
There would be lot more of digits-only passwords. The keyboard-based
patterns would not be magically restricted to length 8. Passwords would
sometimes be username-based. On the other hand, extensive case toggling
would be a bit less effective.
On the bright side, many of us learned new things, and we've identified
shortcomings of our approaches and software that are also relevant for
real-world password security audits. Certain improvements to
John the Ripper will likely be made as a result of this contest.
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.
Thanks.
We'd like to thank team bartavelle and Frank Dittrich for their
contributions to our team's cracked passwords pool. We're also grateful
to team smelly_weigand for offering their cracked passwords to us, and
we're sorry that we never merged those due to a coordination error on
our part.
Matt and Fyodor volunteered to represent our team at DEFCON, making our
participation official - thank you from the rest of us!
We would also like to thank all other teams that participated and made
this contest a real challenge for every team involved. Our special
thanks are to team CrackHeads who, while remaining completely separate
from us during the contest, have also made use primarily of
John the Ripper and provided useful feedback in their writeup:
http://www.openwall.com/lists/john-users/2010/08/03/1
Additionally, we'd like to thank KoreLogic for funding the contest,
including the cash prizes (and our "3rd eligible place" $100 prize
specifically), and CrackHeads for kindly donating $100 out of their $300
cash prize towards JtR development (with the remaining $200 covering
their Amazon EC2 costs).
Finally, we'd like to thank Alain Espinosa for contributing his
efficient NTLM hashing code (currently in JtR jumbo patch), which was
instrumental to efficient use of John the Ripper during the contest.
With approval from CrackHeads, we're going to direct the $200 ($100 from
team john-users and $100 from CrackHeads) to Alain as a way to thank him
in a more tangible way. His contribution is clearly worth it (and
more), and not only for the contest!
Alexander
|
Please contact us if you would like more information about our services, tools, or careers with us.
HOME : SOLUTIONS : RESULTS : TOOLS : RESOURCES : ABOUT KORELOGIC
Privacy Policy : Copyright 2012. KoreLogic Security. All rights reserved