<antirez>

antirez 6332 days ago. 22136 views.
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.

Originally published on oldblog.antirez.com on 17 July 2009.

32 comments from the original post

notaddicted 17 Jul 2009
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.
chupacabra 17 Jul 2009
Huh?
Leah Silber 17 Jul 2009
Looks like you're off to a good start :) Good luck, and thanks for participating!
antirez 17 Jul 2009
@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.
antirez 17 Jul 2009
@Hatem: "2^106 work, rather than the previously expected 2^160 work". The attack is only theoretical (un?)fortunately.
antirez 17 Jul 2009
@Leah: thanks
James Harton 18 Jul 2009
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.
Joel Klein 23 Jul 2009
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.
ash 23 Dec 2010
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.
<a href="http://yangutu.com/" rel="follow">dating chat</a> 23 Dec 2010
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.
<a href="http://www.fuelpumppros.com/audi-fuel-pump/">audi fuel pump assembly</a> 14 Jan 2011
I think maths is easy but if you like it.
<a href="http://www.fuelpumppros.com/audi-fuel-pump/">audi fuel pump assembly</a> 14 Jan 2011
<a href="http://www.fuelpumppros.com/audi-fuel-pump/">audi fuel pump assembly</a>
chevrolet turbo 16 Jan 2011
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
JeremyNathe 17 Jan 2011
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/
SelviLiems 18 Jan 2011
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/
houses for sale in San Antonio 19 Jan 2011
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/
Hcg dosage for weight loss 26 Jan 2011
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.
houses for sale in Indianapolis 10 Mar 2011
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.
Advanced SEO 24 Mar 2011
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.
hamilton mortgage broker 29 Mar 2011
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>
pei real estate 1 Apr 2011
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
Dual Watch winder 2 Apr 2011
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.
Single watch winder 2 Apr 2011
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.
Automatic watch winders 2 Apr 2011
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.
dead rising key 8 Apr 2011
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!
Investment 20 Apr 2011
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.
annapolis land rover 11 May 2011
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
airsoft256 12 May 2011
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/
Airsoft gun 13 May 2011
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/
blog comments powered by Disqus
: