Some math about the Engineyard contest

Friday, 17 July 09
I did some math, and I think this is the probability of two random SHA1 strings having the hamming dinstance of 'D': 
(1/2^160)*(160!/((160-d)!*d!))
This is why. For example imagine we want to compute the probability of an hamming distance of 2. I want the first bit to be not equal, that occurs with a probability of .5, the second bit to be not equal too, again .5, the others to be equal, that is .5 each. This are independent events, so we need to multiply them together, basically for any given pattern of equal/not equal we want there is a probability of .5^160 for a specific arrangement of equal/not-equal of the bits.

But... with an hamming distance of 2 it is required that 2 bits are not equal and 158 are equal, in any kind of order. How many ways there are to arrange 160 items, two black and 158 white? 160!/(158!*2!), so I actually have to multiply the probability of a single arrangement for the number of possible arrangements.

Ok, what are the practical implications of this? That with an optimized C program you can compute around 3.25 million sha1 hashes per second per core (this is what I got with my implementation). So if you have a server farm with 250 computers that happen to be quad cores, you need the following amount of hours to get a given hamming distance: 
6 hours for an h.d. of 33
26 hours for an h.d. of 32
108 hours for an h.d. of 31
it looks like that university clusters can bring us a solution with an HD of 32 or 31 with a bit of luck.

People having just ten quadcore boxes can expect to reach an HD of 35 in 12 hours.

I could love to know if my math is correct, I'm not particularly strong on probability theory... but it looks correct to me.
20625 views*
Posted at 10:54:37 | permalink | 32 comments | print
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.

Note: you'll not see this box again if you are a usual reader.

Comments

1
notaddicted writes:
17 Jul 09, 11:54:32
Assume the xor of your test hash with their desired hash is just 160 random bits. Furthermore, choose a certain number N, and assert: they must be white!! What is the probability that this is true: (0.5 for each bit)^(number of bits you chose).

So given 160 random bits, what are the chances of there being atlead N bits set to zero? (0.5^N)*(ways to choose N from 160).

(0.5^N)*(160!/(N!*(160-N)!)).

define d = 160 - N

0.5^(160-d)*(160!/((160-d)!*d!))

So I think that you are miscalculating by a bit, that is why & how.
2
chupacabra writes:
17 Jul 09, 13:12:15
Huh?
3
Leah Silber writes:
17 Jul 09, 14:07:45
Looks like you're off to a good start :) Good luck, and thanks for participating!
4
antirez writes:
17 Jul 09, 14:43:04
@notaddicted: I'm not sure we are calculating the same thing, my goal was to compute the probability of two random 160 bit strings to have an hamming distance of *exactly* N.
5
Hatem Nassrat writes:
17 Jul 09, 14:43:16
There are some shortcuts that can shorten that time:

http://eprint.iacr.org/2004/304
6
antirez writes:
17 Jul 09, 14:46:32
@Hatem: "2^106 work, rather than the previously expected 2^160 work". The attack is only theoretical (un?)fortunately.
7
antirez writes:
17 Jul 09, 14:46:43
@Leah: thanks
8
James Harton writes:
17 Jul 09, 22:00:42
My demo code has managed to hit a hamming distance of 35 in six different 12 hour runs. I'm finding it very hard to get any closer though.
9
Joel Klein writes:
23 Jul 09, 10:36:19
Could you say more about how you get 3.25 million hashes/second per core? I've only gotten up to about half that, using Polar SSL's SHA1 code. My questions would be: what hash code did you use (link?), what hardware you're running on, and whether you had any particular optimizations particular to the contest situation.
10
bathroom vanities writes:
15 Dec 10, 20:50:35
Its a good place to take a rest after you have a hard week. We need to give us pleasure you know. They also have a good swimming pool. I choose to swim than to play golf.
http://www.esleepmasters.com/Bathroom_Vanities_s/2...
11
ash writes:
23 Dec 10, 06:17:31
Even to come close to a 30, One Would need a very large number of processors Powerful, gold Some hardware Designed to do calculations. Steve Worley has released CUDA implementation for The Contest is nVidia's forums of <a href="http://yangutu.com/"; rel="follow">dating chat</a>. High-end nVidia GPUs Were Able to process Hundreds of millions of hashes per second, "whereas lowly CPU-only implementations" could only do a few "one million per second per core.
12
<a href="http://yangutu.com/" rel="follow">dating chat</a> writes:
23 Dec 10, 06:18:13
Even to come close to a 30, One Would need a very large number of processors Powerful, gold Some hardware Designed to do calculations. Steve Worley has released CUDA implementation for The Contest is nVidia's forums a few "days ago. High-end nVidia GPUs Were Able to process Hundreds of millions of hashes per second, "whereas lowly CPU-only implementations" could only do a few "one million per second per core.
13
<a href="http://www.fuelpumppros.com/audi-fuel-pump/">audi fuel pump assembly</a> writes:
13 Jan 11, 20:22:10
I think maths is easy but if you like it.
14
<a href="http://www.fuelpumppros.com/audi-fuel-pump/">audi fuel pump assembly</a> writes:
13 Jan 11, 20:22:30
<a href="http://www.fuelpumppros.com/audi-fuel-pump/";>audi fuel pump assembly</a>
15
chevrolet turbo writes:
16 Jan 11, 14:26:16
Well a very informative one we get to know about cardiac problems and other relevant problems such nice one thanks well very nice effort keep up the good work thanks for sharing your precious information with us thanks
16
JeremyNathe writes:
17 Jan 11, 09:30:49
Like this site. They help me by giving idea bout making two account. I never think of that before. I use to have one account and I cant control my money. http://pokiesslotmachines.com/
17
SelviLiems writes:
18 Jan 11, 07:10:26
My boyfriend like to see this site too. He like to read all the innovation that they have ion here. I think he will make something in everything that they hav ein here. He is really creative. http://www.centredegenetique.ca/
18
houses for sale in San Antonio writes:
19 Jan 11, 18:03:27
Not that home sellers are going to try and take advantage of you, but they are definitely going to try and make the highest sale that they can get; this is still a business. So knowing what to do and not to do when you are already in the stage of negotiation is a must. http://www.housesforsaleinsanantonio.org/
19
Hcg dosage for weight loss writes:
26 Jan 11, 07:57:27
You will be encouraged to weigh yourself each day and monitor your progress. It is also important to have a bowel movement at least every other day to avoid prolonging your progress. If you are having difficulty with bowel movements, you can increase the amount of fiber you are eating to help with your weight loss program. Adding a few apples to your diet each day can help.
20
houses for sale in Indianapolis writes:
09 Mar 11, 21:34:20
Well, I am so excited that I have found this your post because I have been searching for some information about it almost three hours. You helped me a lot indeed and reading this your article I have found many new and useful information about this subject.
21
Advanced SEO writes:
24 Mar 11, 06:06:15
I am speechless. This is a fantastic site and very engaging too. Excellent work! That's not really much coming from an amateur publisher like me, but it's all I could think after enjoying your posts. Not like other sites. You really know what you're talking about too. So much that you made me want to explore more. Your site has become a stepping stone for me, my friend. Thanks for the detailed journey. I really enjoyed the posts that I have read so far.
22
hamilton mortgage broker writes:
29 Mar 11, 19:53:13
Hamilton mortgage brokers will help you have a say in your property’s mortgaging. According to Wikipedia, A Mortgage broker acts as an intermediary who brokers mortgage loans on behalf of individual s or businesses. That means a mortgage broker is the one who works for you, for your property, for your interest, to give you best deal and would not charge you anything.

<a href=www.hamiltonmortgagebrokers.org>hamilton mortgage broker</a>
23
pei real estate writes:
31 Mar 11, 20:45:41
There are several different choices, sizes, and styles of cottage properties within the available PEI real estate selections that make it possible for families to have their own little piece of the world to enjoy during the bright and sunny months of the summer along the water’s edge.
http://www.peirealestate.org
24
Dual Watch winder writes:
02 Apr 11, 13:31:35
Great things you’ve always shared with us. Thanks. Just continue composing this kind of post. The time which was wasted in traveling for tuition now it can be utilized for studies. Thanks for this knowledgeable blog.
25
Single watch winder writes:
02 Apr 11, 13:33:00
The post is written in very a good manner and it entails many useful information for me. I am happy to find your distinguished way of writing the post. Now you make it easy for me to understand and implement the concept. Thank you for the post.
26
Automatic watch winders writes:
02 Apr 11, 13:34:58
What a great article, I read all of it then i am satisfied to say that It’s a terse idiom, and if you’re concerned about the performance you must not have a database or anything else that consumes resources orders of magnitude greater. Consider yourself lucky, otherwise don’t optimize at this level unless you really need to. Keep blogging.
27
dead rising key writes:
07 Apr 11, 21:47:17
I must say that overall I am really impressed with this blog.It is easy to see that you are impassioned about your writing. I wish I had got your ability to write and definitely will stick your blog routinely!
28
Investment writes:
20 Apr 11, 17:30:47
It takes a whole lot to learn how to make a wise investment. An investment is by no means a "sure thing", risk is constantly there and it may be big when it goes the wrong way. You'll find so a lot of approaches to invest. So it might be a smart move to ask for professionals just before you make your decison.
29
Hardcorevideos writes:
22 Apr 11, 05:59:01
Thank you for the post.
http://www.telebizarr.de
http://www.spannertv.com
http://www.spanner-tv.com
30
annapolis land rover writes:
10 May 11, 23:55:36
I wanted to write you one tiny observation to help thank you so much once again for your personal incredible thoughts you've documented in this article. It has been seriously open-handed of you to supply openly what exactly some people would have advertised as an e-book in order to make some dough for themselves, chiefly seeing that you might have tried it if you ever considered necessary. Those smart ideas in addition worked as the easy way to recognize that other people have a similar desire the same as my own to know much more when it comes to this condition. I am sure there are a lot more pleasurable occasions up front for people who examine your blog.

http://www.landroverhuntvalley.com
31
airsoft256 writes:
12 May 11, 04:51:30
I just wanted to leave a comment to say that I enjoy your blog. Looking at the number of comments, I see others feel the same way! Congratulations on a very popular blog. http://www.junnicairsoft.com/
32
Airsoft gun writes:
13 May 11, 04:16:12
I just wanted to leave a comment to say that I enjoy your blog. Looking at the number of comments, I see others feel the same way! Congratulations on a very popular blog.http://airsofgun.yolasite.com/
comments closed