Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [day] [month] [year] [list]
Date: Sat, 6 Jul 2013 13:24:58 +0400
From: Aleksey Cherepanov <aleksey.4erepanov@...il.com>
To: john-users@...ts.openwall.com
Subject: team john-users write-up for PHDays Hash Runner 2013 contest

Write-up for PHDays Hash Runner 2013

Resources summary

Active Members: 15

Names: Aleksey Cherepanov, Alexander Cherepanov, Dhiru Kholia,
elijah[w&p], Frank, guth, Jose Luis Herrera, Matt Weir, Agap1,
sftp, Solar, tab, ukasz, vn, Vasily Kulikov a.k.a. segoon.

Software: John the Ripper (with various patches), custom scripts.

Hardware: ~8 gpus, ~150 cpu cores at most

Preface

The contest was fun and challenging, it helped us test some
experimental John the Ripper code and identify areas for further
improvement.

We'd like to thank Positive Technologies for organizing the event. We
would also like to thank all other teams who participated and made it
tough for us to compete. ;-)

Resources

We got 4 new team members and we hope they'll stay with us. You could
join us too!

In addition to the active members listed above, community members with
too little time for participation helped us with preparations before
the contest and provided us helpful advice during the contest. We hope
they'll have more time to participate next time.

We used bleeding-jumbo version of John the Ripper right from our
public repository, and custom scripts.

I guess we had about 8 gpus and at most 150 cpu cores. Not all of
these powers were used or even accessible during both days. Some
members used just one computer or even a laptop.

Contest

The contest started with a registration. It was not clear how to
register our existing account for Hash Runner so I registered a new
account. It was not hard but the lack of information added stress. The
lack of information was the only major problem of this contest and
annoyed us many times. BTW I think smaller teams suffer much more from
the lack of information than bigger teams. Though the organizers were
very friendly and answered all questions. The end of the contest was
smooth and we were totally in cracking.

The beginning was not smooth for us because delayed start broke our
plans (some guys had to go to jobs). I spent a lot of time converting
hashes to canonical form. Though team members already started
cracking.

Dhiru Kholia made a format for sha3-256 (keccak-256) in 10 minutes. It
was amazing! Keccak provided us with noticeable amount of points in
the end. BTW keccak format was pushed into our public repository as
soon as it was created so any team was able to use it.

Also Dhiru Kholia made a format for md5-broken that was used during
the whole contest. He did this format in a short time too.
Nevertheless I did an alternative implementation being based on
different principle. Then Alexander Cherepanov added support to merge
results from these two implementations. So we had two fully featured
implementations of md5-broken. Both of them were used actively. The
alternative implementation allowed Solar to effortlessly use
experimental code for password generation on GPU (a.k.a. PG-test) made
by myrice (Dongdong Li) during GSoC 2012. Though we spent more time on
alternative implementation of md5-broken then we wanted.

Testing alternative implementation of md5-broken I found some
constellations and got the idea of hints on images based on a very
small part of image of the night sky. This idea was brought to our irc
and evolved into the idea of thematic wordlists very fast. So we got
the main idea of the contest in 7 hours. It was a great piece of luck.

Then it allowed us to totally crack all sha512crypt and descrypt
hashes. As soon as full hints were provided elijah[w&p] got a wordlist
and rules from Morris worm, using them guth cracked 152 sha512crypt
hashes remained after other attacks. With all sha512crypt cracks we
did a great jump forward and pushed the score over 50% border in about
one day.

Thematic wordlists created disbalance and made the contest prone to
wordlist-based attacks. But different elements of other attacks were
present too. Also things that mimic real life were present. We enjoyed
default passwords for descrypt, list of corporate workers for file
#11, user names for oracle hashes and other elements. Though we did
not fully use the ability to transfer patterns from fast hashes to slower
ones (like in pix-md5/keccak and md4/bcrypt pairs). All such elements
were miniature. But their exploitation was very interesting for us.

At the end of the first day most members went to sleep. It was a good
time for sleep. But after that we found us far from the first place.
It forced us to develop a real strategy. To make a rational decision I
crafted our internal scoreboard sorted by the potential of each hash
type because we knew that focused attention to any of hash types could
provide us with about all cracks from it. We focused on keccak and
bcrypt, also we wasted a lot of time on sha256crypt, other types of
hashes weren't that attractive for investment of time.

ukasz was the person who efficiently handled a lot of hardware during
both days. He used his own computers and our shared development box.
Totally he used 4 gpus and several cpus. Other members greatly helped
him using just one cpu. Some members noticed that they performed much
better with minimal amount of hardware. But such discrepancy in
hardware resources forced us to collaborate more. Team work was
incredible. Contests improve communication in our community. We like
contests very much due to that. This contest seems special due to its
thematic wordlists that were very good for our team work.

At the second day Frank joined us and directed ukasz to crack bcrypt
using patterns found in md4. Frank wasn't on our irc channel and used
only our mailing list. Solar warned me that I should post more onto
the list to involve list-only members. The advice was invaluable.
While the first day was spent mostly in irc the second day brought a
lot of messages on the list. A significant number of members joined us
on the list during the second day. We got a lot of ideas.

Though all useful ideas were investigated before the end. And we had
no ideas how to get more points at the end. It was a crisis. But we
overcame it, we found new dictionaries. In particular we found
Webster's Online Dictionary very useful to crack keccak. Though it had
its own price. I was busy cracking and committed neither hashes to
organizers nor internal scoreboard to my team. It caused very
pessimistic ideas among the team because everyone was tired. Also the
situation became very risky: I postponed all possible problems with
uploads, and I forgot that uploads are quite slow. Nevertheless I
uploaded all cracks 15 minutes before the end. But then our scripts
produced broken file for upload, and I am still not sure that we
pushed all our cracks while the last 15 minutes produced some due to
use of all known passwords as a wordlist. But it was enough for the
first place with 91%.

The jump to the first place was unbelievable and unpredictable. This
"strategic trick" occurred by accident. I was busy cracking hashes and
ignored that my team asked me many times to upload our cracks. Now I
realize how big a mistake it was. After the jump we weren't happy
because all emotions were messed up during these 15 minutes.

Regular uploads could make contest more interesting and fun. Automated
uploads reduce lags between cracks and uploads to a reasonable time
but we did not have automated uploads this time. There was a CSRF
shield on the form for submission. So our script for submission of
cracks needed changes. We did not implement them. We propose to
simplify submission of cracks. Even authentication is not really
needed for uploads: you could provide each team with a random number,
so team would not need to login but just send this number with cracks.

Also we have an idea how to incorporate earlier submissions into the
game. There could be a bonus for the first upload. The first team to
upload a certain crack gets 1% bonus to this crack's points (small
bonus is enough because difference in score between top teams is quite
small). Though it would increase the gap between smaller and bigger
teams.

We are curious why submission of cracks is so slow. Of course it is
not a problem with incremental submission. But we could not imagine
any real reason for such slow checks on the side of organizers (maybe
your DB needs an index?!).

We are pleased to say that the quality of the contest was improved
significantly. The contest was about solving interesting tasks and not
about solving problems just to proceed. Tasks were different. There
were minor problems with organization and we would like to see more
info in a canonical place at the right time: the perfect contest is
when teams do not need to ask organizers. We like that files number 5
and 7 were prepared for additional 12 hours and held (though we would
have liked to get info about it at the beginning when we found that
these files were empty), it is nice that organizers thought about
different cases. Good work!

The complexity of the contest matched abilities of big teams well.
There is only a bit to crack after the contest. The contest had about
nothing significant that needed luck from teams. Top 3 teams are very
close so it seems the contest was good for all big teams. But the
contest does not seem good for small teams despite efforts of
organizers. I'd say it is easier for smaller teams and novices to
proceed when at least a small part of each hash type could be cracked
using default attack. Also you could decide to add 1 hash of each type
with easy and well known password to check that team's cracker works
correctly and submission works.

There was a disbalance between general brain work and hardware work.
Hardware was not critical (though sha256crypt would benefit from
bigger hardware resources). This disbalance made the contest very
dynamic: most attacks spent less cpu time than human time, results of
a hard mind work were about immediate.

Themes were very interesting. We enjoyed investigation of Morris
worm's code. We puzzled our brains about tomatoes. But points for
sha256crypt did not seem right. Though taking into account easy
patterns and ability to crack a lot of hashes in a short time it was
an attractive target for attacks at the end (sha256crypt was able to
add 8% from total to the score). So the points don't look natural but
are quite good. Though tricky balance of points makes decisions harder
and could make a base for a luck-driven contest. We are looking
forward to see detailed statistics and the sources of the contest, so
that we can review our decisions.

Modifiers to base prices weren't provided during the contest. It added
more fog to the situation. It made some decisions harder but not
really much. Though in some cases more fog causes more unnecessary
problems and more results based on the luck. I guess well defined
process at all stages would be more comfortable for all teams. Though
well defined contest could become not interesting. Balance here is
subtle. Next time it would be nice to see 100% transparent to team
members scoring scheme no later than half-way through the contest.

Some members like to see their own progress during the contest. They
register their own teams and post cracks as two teams. It violated
rules this time. One solution could be to keep everything as is now
but provide detailed points for hashes right at the start or even
earlier so every team could manage any internal point counting system
they wish. Another solution is to add a special type of teams - not
eligible for prizes. So a person could be in one regular team and in
any number of special teams. It may be nice to disable such teams
after the first day of the contest to improve cooperation during the
end of the contest.

Personal write-ups of members

You could read more details and personal opinions in members'
write-ups:

Dhiru Kholia
  http://openwall.com/lists/john-users/2013/05/27/1
Frank
  http://openwall.com/lists/john-users/2013/06/01/1
guth
  http://openwall.com/lists/john-users/2013/06/10/1
elijah[w&p]
  http://openwall.com/lists/john-users/2013/07/01/2
Jose Luis Herrera
  http://openwall.com/lists/john-users/2013/07/03/5
Alexander Cherepanov
  http://openwall.com/lists/john-users/2013/07/05/1

Final words

The contest made us better in many ways: we improved relationships, we
got experience, we found bugs, we wrote new code. This contest was
very interesting. Great thanks for all that!

This time we worked as a real team. Everyone supported and helped each
other in different ways. We repeated our amazing experience of a great
team work and we would like to participate again to improve our tools,
our methods and our thoughts.

Thanks!

-- 
Regards,
Aleksey Cherepanov

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ