git » homepage.git » master » tree

[master] / archive / linked-pages / raw / ca875c273d569629.html

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
<!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&#8217;ve had with computers in a long time.  Here&#8217;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 &#8220;punch my ticket&#8221; 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 &#8220;guerilla flotilla&#8221; 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&#8217;t have the speed.  I&#8217;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&#8217;s lifetime to compute.  I decided on a &#8220;depth first&#8221; approach, building random 12-word strings from dictionary words, hashing them, and comparing the Hamming distance to the program&#8217;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 &#8220;team bests&#8221; 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 &#8220;on.&#8221;  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&#8217;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&#8217;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 &#8220;bootstrap&#8221; 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 &#8220;naive&#8221; 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&#8217;s SHA1().</p>
<p>While glibc&#8217;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&#8217;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 &#8220;yak shaves&#8221; 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&#8217;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&amp;pid=146555473&amp;rk=hNiym82C&amp;lang=en_US&amp;name=alandipert&amp;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>