<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<!-- DEFAULT COLORS -->
<meta name="color:Background" content="#fff"/>
<meta name="color:Title" content="#990000"/>
<meta name="color:Description" content="#777"/>
<meta name="color:Post Title" content="#990000"/>
<meta name="color:Text" content="#444"/>
<meta name="color:Inline Link" content="#990000"/>
<meta name="color:Quote" content="#888"/>
<meta name="color:Quote Border" content="#ff0"/>
<meta name="color:Quote Source" content="#555"/>
<meta name="color:Link Post" content="#990000"/>
<meta name="color:Conversation Background 1" content="#f4f4f4"/>
<meta name="color:Conversation Background 2" content="#e8e8e8"/>
<meta name="color:Conversation Border" content="#bbb"/>
<meta name="color:Conversation Text" content="#444"/>
<meta name="color:Date" content="#990000"/>
<meta name="color:Date Block" content="#990000"/>
<meta name="color:Date Block Text" content="#ff0"/>
<!-- END DEFAULT COLORS -->
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>alan dipert - My EngineYard Contest Odyssey</title>
<link rel="icon" href="http://24.media.tumblr.com/avatar_4ae064934cfd_16.png"/>
<link rel="alternate" type="application/rss+xml" title="RSS" href="http://alan.dipert.org/rss"/>
<meta name="viewport" content="width=800"/> <!-- iPhone -->
<script type="text/javascript" src="http://shjs.sourceforge.net/sh_main.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_css.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_html.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_java.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_sh.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_c.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_scala.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_cpp.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_php.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_ruby.min.js">
</script>
<script type="text/javascript"
src="http://shjs.sourceforge.net/lang/sh_javascript.min.js">
</script>
<link type="text/css" rel="stylesheet" href="http://shjs.sourceforge.net/sh_style.css">
<style type="text/css">
pre {
white-space: pre-wrap; /* css-3 */
white-space: -moz-pre-wrap; /* Mozilla, since 1999 */
white-space: -pre-wrap; /* Opera 4-6 */
white-space: -o-pre-wrap; /* Opera 7 */
word-wrap: break-word; /* Internet Explorer 5.5+ */
border: 1px solid #ccc;
padding: 4px;
}
li {
padding: 5px;
}
body {
margin: 0px;
background-color: #fff;
font-family: 'Lucida Grande', Helvetica, sans-serif;
}
a {
color: #990000;
}
h1 {
width: 580px;
padding: 0px 100px 20px 100px;
margin: 50px auto 10px auto;
/*border-bottom: solid 1px #ccc;*/
text-align: center;
font: Bold 55px 'Trebuchet MS', Helvetica, sans-serif;
letter-spacing: -2px;
line-height: 50px;
/*height: 128px;*/
background-image: url('http://27.media.tumblr.com/tumblr_kyxgl62AA11qzqgjfo1_100.jpg');
background-position: 0 -5px;
background-repeat: no-repeat;
position: relative;
}
div#info {
text-align: center;
font-size: 8pt;
padding-bottom: 20px;
margin-bottom: 30px;
border-bottom: 1px solid #ccc;
}
h1 a {
color: #990000;
text-decoration: none;
}
h1 img {
border-width: 0px;
position: absolute;
right: 0px;
bottom: 10px;
width: 43px;
height: 23px;
}
div#content {
width: 580px;
margin: auto;
position: relative;
}
div#content div#description {
position: absolute;
right: -170px;
width: 160px;
text-align: left;
}
div#description {
font: normal 17px Helvetica,sans-serif;
line-height: 20px;
color: #777;
}
div#description a {
color: #777;
}
div#searchresultcount {
margin: 15px 0 30px;
text-align: center;
}
div.post {
position: relative;
margin-bottom: 40px;
padding-right: 20px;
}
div.post div.date {
position: absolute;
left: -260px;
text-align: right;
width: 230px;
white-space: nowrap;
font: normal 34px Helvetica, sans-serif;
letter-spacing: -2px;
color: #990000;
text-transform: uppercase;
line-height: 35px;
}
div.post div.date div.date_brick {
float: right;
height: 30px;
width: 45px;
background-color: #990000;
color: #ff0;
font: Bold 12px Verdana, Sans-Serif;
text-align: center;
line-height: 12px;
margin-left: 10px;
padding-top: 5px;
letter-spacing: 0px;
overflow: hidden;
}
div.post img.permalink {
width: 14px;
height: 13px;
border-width: 0px;
background-color: #000;
display: none;
position: absolute;
right: 0px;
top: 0px;
z-index: 10;
}
div.post:hover img.permalink {
display: inline;
}
div.post h2 {
font-size: 18px;
font-weight: bold;
color: #990000;
letter-spacing: -1px;
margin: 0px 0px 5px 0px;
}
div.post h2 a {
color: #990000;
text-decoration: none;
}
div.post div.caption {
font-size: 14px;
font-weight: bold;
color: #444;
margin-top: 10px;
padding: 0px 20px 0px 20px;
}
div.post div.caption a {
color: #444;
}
/* Regular Post */
div.post div.regular {
font-size: 12pt;
color: #444;
line-height: 17px;
}
div.post div.regular blockquote {
font-style: italic;
border-left: solid 2px #444;
padding-left: 10px;
}
/* Quote Post */
div.post div.quote div.quote_text {
font-family: Helvetica, sans-serif;
font-weight: bold;
color: #888;
border-left: solid 5px #ff0;
padding-left: 10px;
}
div.post div.quote div.quote_text span.short {
font-size: 36px;
line-height: 40px;
letter-spacing: -1px;
}
div.post div.quote div.quote_text span.medium {
font-size: 25px;
line-height: 27px;
letter-spacing: -1px;
}
div.post div.quote div.quote_text span.long {
font-size: 16px;
line-height: 20px;
}
div.post div.quote div.quote_text a {
color: #888;
}
div.post div.quote div.source {
font-size: 16px;
font-weight: Bold;
color: #555;
margin-top: 5px;
}
div.post div.quote div.source a {
color: #555;
}
/* Link Post */
div.post div.link a.link {
font: Bold 20px Helvetica, sans-serif;
letter-spacing: -1px;
color: #990000;
}
div.post div.link span.description {
font-size: 13px;
font-weight: normal;
letter-spacing: -1px;
color: #444;
}
/* Conversation Post */
div.post div.conversation ul {
list-style-type: none;
margin: 0px;
padding: 0px 0px 0px 1px;
border-left: solid 5px #bbb;
}
div.post div.conversation ul li {
font-size: 12px;
padding: 4px 10px 4px 8px;
color: #444;
margin-bottom: 1px;
}
div.post div.conversation ul li span.label {
font-weight: bold;
}
div.post div.conversation ul li span.user_1 {
color: #c00;
}
div.post div.conversation ul li span.user_2 {
color: #00c;
}
div.post div.conversation ul li span.user_3 {
color: #0a0;
}
div.post div.conversation ul li.odd {
background-color: #f4f4f4;
}
div.post div.conversation ul li.even {
background-color: #e8e8e8;
}
/* Video Post */
div.post div.video {
width: 400px;
margin: auto;
}
/* Footer */
div#footer {
margin: 40px 0px 30px 0px;
text-align: center;
font-size: 15px;
font-weight: bold;
color: #444;
}
div#footer a {
text-decoration: none;
color: #444;
}
div#footer a:hover {
text-decoration: underline;
}
div#footer div#credit {
font: normal 13px Georgia, serif;
font-size: 13px;
margin-top: 15px;
}
.query { font-weight: bold; }
</style>
<meta http-equiv="x-dns-prefetch-control" content="off"/></head>
<body onload="sh_highlightDocument();">
<h1>
<a href="/">alan dipert</a>
<a href="/rss"><img src="/themes/5/rss.gif" id="rss" alt="RSS"/></a>
</h1>
<div id="info">
<a href="http://www.github.com/alandipert">github</a> / <a href="http://twitter.com/alandipert">twitter</a> / <a href="http://people.rit.edu/~awd4182/dipert_resume.pdf">resume</a> / <a href="mailto:alan@dipert.org">email</a>
</div>
<div id="content">
<div class="post">
<div class="date">
<div class="date_brick">
Jul<br/>
21st
</div>
Tue
</div>
<a href="http://alan.dipert.org/post/146555473/my-engineyard-contest-odyssey"><img src="/themes/5/permalink.gif"
class="permalink" alt="permalink"/></a>
<div class="regular">
<h2><a href="http://alan.dipert.org/post/146555473/my-engineyard-contest-odyssey">My EngineYard Contest Odyssey</a></h2>
<p>At 6PM PST EngineYard announced the end of their <a href="http://www.engineyard.com/blog/2009/programming-contest-win-iphone-3gs-2k-cloud-credit/">programming contest</a> for finding strings which, when SHA1 hashed, were the closest (by <a href="http://en.wikipedia.org/wiki/Hamming_distance">Hamming distance</a>) to the SHA1 hash of their <a href="http://www.engineyard.com/blog/2009/engine-yard-contest-challenge-phrase-and-dictionary/" target="_blank">challenge phrase</a>. The winning score was 30, and my best was 38; but working on the contest was some of the most fun I’ve had with computers in a long time. Here’s how it went down:</p>
<p>I heard about the contest through a friend and was initially not very interested. I did some rough calculations and was pretty intimidated by the the astronomical size of the key space. Despite my original misgivings, I decided I may as well “punch my ticket” and at least come up with a program capable of generating and comparing hashes according to the rules.</p>
<p>What followed was a nearly 24 hour computing odyssey that took me from Ruby, to C, to clusters of Amazon EC2 machines, and finally to a ragtag “guerilla flotilla” of a mix of 70 VPSs, AMIs, Mosso cloud servers, and personal machines that, by 9PM EST, were checking roughly 100 to 200 million keys a second.</p>
<p><img align="middle" src="http://5.media.tumblr.com/Y3uNSQkLgq747avi2zV9fYhPo1_400.png" alt="A GNU Screen session filled with Rackspace cloud servers checking hashes" width="397" height="142"/></p>
<p><b>The Beginning</b></p>
<p>Last night, my friend was working on a Ruby implementation which was awesome, but just didn’t have the speed. I’m a novice C programmer, and decided to try my hand with a C implementation. It took me a few hours to get my algorithm going, and the original version could check about 200k hashes a second. I decided early on that to permute everything I could - dictionary words, the 5 letter random string, and case - would just add unnecessary complexity to the program. After all, just using dictionary words, there are still 1000^12 valid hashes, something that even with a thousand dedicated cores would take longer than the Sun’s lifetime to compute. I decided on a “depth first” approach, building random 12-word strings from dictionary words, hashing them, and comparing the Hamming distance to the program’s current top score.</p>
<p>Running the program on my own machine, I got a hamming distance of 40 in an hour or two. I submitted my result, and took note of the leaderboard: the distance to beat was 31. While I was happy with what I had come up with, I decided I had the time and the inclination to give it a real shot. There were 18 hours until the contest ended. This is when things started to get kind of crazy.</p>
<p><b>The Quest</b></p>
<p>I started asking friends to run the program. I made a bash script that used curl to send results to a PHP script that logged cumulative scores across machines, which can be viewed here: <a href="http://engine.dipert.org/" target="_blank"><a href="http://engine.dipert.org/">http://engine.dipert.org/</a></a>. My good friend Jade even gave the “team bests” page a sweet CSS makeover. I started running the program on the handful of VPSes I operate for work and play, on prgmr, Linode, and Slicehost. By this morning, we had 39.</p>
<p>Having run out of favors, VPSs, and shared hosting accounts with shells, I looked to The Cloud. I went first with 20 Amazon EC2 nodes running Fedora 32 bit. At 10 cents per hour per machine, with ~15 hours to go, I was prepared to spend the $30 it would take to see this through. The game was most definitely “on.” I planned originally to build my own AMI image pre-loaded with the hash generator, but was off-put by the shenanigans of image building with the AWS tools. Instead, I wrote a script which, when invoked, would install necessary dependencies, download the program, start running it, and send results.</p>
<p>This was working well. While I didn’t manage to get anything lower than 39, the machines independently generated several different 39-distance answers. I felt like I was on the right track, but I had hit Amazon’s 20 ECU limit. I needed more power.</p>
<p><b>Power with Rackspace Cloud Servers</b></p>
<p>So, I decided to start up some Rackspace Cloud Servers. I was impressed with their web interface. I re-wrote my “bootstrap” script, and made major modifications to my code. As I looked at the results of others, some of whom decided only to permute the 5 random character end word, I realized that I might improve throughput by minimizing string concatenation. In my “naive” C implementation, I had a string buffer into which dictionary words were copied using memcpy. After 12 dictionary words were randomly picked, I was making 12 memcpy calls to fill the buffer for each attempted string. This buffer was then passed on to OpenSSL’s SHA1().</p>
<p>While glibc’s memcpy is surely as optimized as it could be, I decided that I might be better of sticking to the 5 character combinations only, and then change the dictionary words only when necessary. I figured this would reduce drastically the average number of memcpys per iteration, speeding up the program as a whole.</p>
<p>With this new approach, I started setting up Rackspace servers. By 11AM EST I had 20 of them going. I went to sleep and woke up to find a lower score, 38 - which would ultimately be my best. Excitedly, I began the manual process of setting up 30 additional Rackspace servers. For a low end cloud server, Rackspace is much cheaper. I paid 1.5 cents per hour per machine, and I didn’t have to worry about additional bandwidth charges, because finding hashes is purely computationally intensive.</p>
<p>By 4PM, I had 70 cloud servers, 3 VPSs, and 4 personal computers cranking away, all of which I was monitoring in lots of screen sessions and Terminal tabs. Owing to the improved efficiency of my re-write, the Mosso servers were going through strings at rates between 500k-1.5 million per second. Counting the contributions of the AMI machines, the VPSs, and the hodgepodge mix of other computers, my estimate for overall speed is 100 to 200 million checks per second.</p>
<p><b>In Which the Contest Ends Bittersweetly</b></p>
<p>Ultimately, despite my late-in-the-game Rackspace efforts, 38 would be my score. I wish I had spent more time thinking about my algorithm before the contest began, and I wish I would have identified Rackspace initially as the platform of choice. At 1.5 cents an hour with no limit on machines, it was clearly the way to go. I might even have used their API to automatically create machines and run the program, as they have what looks like an excellent REST/JSON API.</p>
<p>So! Here endeth one of the more epic “yak shaves” of my life. For me, my wife, and a few good friends it was our own personal Superbowl. Despite not having won, I learned a lot about cloud computing, and maybe even improved my C a bit.</p>
<p><i>Code: <a href="http://github.com/alandipert/engineyard-contest/tree/master" target="_blank"><a href="http://github.com/alandipert/engineyard-contest/tree/master">http://github.com/alandipert/engineyard-contest/tree/master</a></a> Note: I accidentally deleted my improved code when I shut down my Rackspace cluster; otherwise you’d see it on Github also.</i></p>
</div>
<div style="font-size: 10px; text-align: left;"><a href="http://alan.dipert.org/post/146555473/my-engineyard-contest-odyssey#disqus_thread">Comments (View)</a></div></div>
<script type="text/javascript">var disqus_url = "http://alan.dipert.org/post/146555473/my-engineyard-contest-odyssey"; var disqus_title ="My EngineYard Contest Odyssey";</script>
<div id="disqus_thread"></div><script type="text/javascript" src="http://disqus.com/forums/alandipert/embed.js"></script>
<a href="http://disqus.com" class="dsq-brlink">blog comments powered by <span class="logo-disqus">Disqus</span></a>
<script type="text/javascript">
//<![CDATA[
(function() {
var links = document.getElementsByTagName('a');
var query = '?';
for(var i = 0; i < links.length; i++) {
if(links[i].href.indexOf('#disqus_thread') >= 0) {
query += 'url' + i + '=' + encodeURIComponent(links[i].href) + '&';
}
}
document.write('<script type="text/javascript" src="http://disqus.com/forums/alandipert/get_num_replies.js' + query + '"></' + 'script>');
})();
//]]>
</script>
<div id="footer">
<div id="credit">
Powered by <a href="http://www.tumblr.com/"
target="_blank">Tumblr</a>
</div>
</div>
</div>
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
var pageTracker = _gat._getTracker("UA-965358-1");
pageTracker._trackPageview();
</script>
<!-- BEGIN TUMBLR CODE --><iframe src="http://assets.tumblr.com/iframe.html?9&src=http%3A%2F%2Falan.dipert.org%2Fpost%2F146555473%2Fmy-engineyard-contest-odyssey&pid=146555473&rk=hNiym82C&lang=en_US&name=alandipert&brag=0" scrolling="no" width="330" height="25" frameborder="0" style="position:absolute; z-index:1337; top:0px; right:0px; border:0px; background-color:transparent; overflow:hidden;" id="tumblr_controls"></iframe><!--[if IE]><script type="text/javascript">document.getElementById('tumblr_controls').allowTransparency=true;</script><![endif]--><script type="text/javascript">_qoptions={qacct:"p-19UtqE8ngoZbM"};</script><script type="text/javascript" src="http://edge.quantserve.com/quant.js"></script><noscript><img src="http://pixel.quantserve.com/pixel/p-19UtqE8ngoZbM.gif" style="display:none; border-width:0px; height:1px; width:1px;" alt=""/></noscript><!-- END TUMBLR CODE --></body>
</html>