Thursday, November 11, 2010

Hash Collisions and the Birthday Attack



Introduction

Last time, I talked about brute force attacks and how efforts to reduce the keyspace of a given algorithm can greatly reduce your computational time (link). This article will discuss hash collisions and the probability of collisions occuring via the birthday paradox. Though this doesnt inherently provide you with any more tools or methods in terms of cracking hashes, it does provide the theory behind generating hash collisions which can severely compromise the security of an algorithm.

Hash Collisions

To quickly review, cryptographic hash functions work by taking in a string (i.e., your password), performing some mathematical operations on it, and spitting out hexadecimal garbage that is utterly uninformative to anyone. If the algorithm is well-designed, the mathematical operations will be one-way; that is, it is either impossible or so computationally impractical to take a hash and run it backwards through the algorithm to regurgitate the original string. The easiest way to get your desired password is to match the hash by testing every possible password and seeing if the hashes match, otherwise known as brute-forcing. Unfortunately, this can take a long time and there are more efficient means at our disposal.

One method is to try and get the algorithm to generate what is known as a "hash collision". From the previous article, we showed that using the hashing algorithm from ExtBasic 11, passwords containing the same set of letters would always generate the same hash, regardless of what order the letters were in ("aab" was the same as "aba" was the same as "baa"). This is a hash collision, two or more separate strings creating an identical hash. Since real-world algorithms do not use such simplistic methods, collisions do not occur so easily, but they do occur. In fact, we know that they must occur!

Take the MD5 algorithm, for example. For every password that is entered, the algorithm will always return a hash that is 128-bits long, or a string of 32 hexadecimal characters. From that, we know that there are a finite number of hashes that can be generated, but the number of passwords entered can be infinite. To put this into perspective, there are 94 characters on a normal keyboard (52 capital and lower-case letters, 10 numbers, and 32 assorted symbols; as far as I know, there are no illegal characters in the MD5 algorithm). Assuming a password length of 20, we use our permutation equation from before:

CODE :
n^k = 16^32 = 2^128 = 3.4e38 possible hashes
94^20 = 2.9e39 possible passwords

So from this, we know that if we try every possible password with 20 characters or more, eventually we will generate a hash collision!

However, this is not really good news. To test every password at a speed of 6 million hashes per second (my laptops average hashing speed) would take 1.5e25 years, orders of magnitude longer than any timespan our brains could possibly conceive. Additionally, since we have to store each hash we compute so that we can check it against future ones and knowing each hash occupies 16 bytes, that means we would have to have so many 2TB HDD that if they were laid out in a grid, they would cover the entire Earths surface 1,100 miles deep. So what to do? Luckily, probability is on our side.

The Birthday Paradox

If you have ever taken a statistics and probability class, you have probably learned about the birthday paradox. It goes something like this: Take a room of 50 people. What are the odds that at least two people will have the same birthday?

Thinking about this quickly, there are 365 days in year (Leap year births not counted; they arent real people anyway), 50 people, so maybe 1 in 6, or about 17%? Wrong. In reality, the probability is a whopping 97%! This unbelievably high, surely there must be a mistake! Well, lets look at the math.

In a room of 50 people, were trying to match two birthdays. So taking any one birthday, there are 49 possible matches to be made. However, if we compare every birthday to every other birthday, our number of possible matches greatly increases and we can use our friend, the combination without replacement equation:

CODE :
50!
---------- = 1,225 combinations
2! (50-2)!


So to think about what this problem is asking in another way, if we had 2,450 people and we paired them off randomly with each other, what are the odds that a person would have the same birthday as the person he was paired with? With 1,225 pairs, now it doesnt seem so far fetched that theres a 97% chance there will be a match.

But how does this apply to hash collisions? Well, since we are simply trying to find to passwords with the same hash ("birthday") it turns out we dont have to calculate the heinous number of passwords we originally thought. The birthday paradox simplifies down to the following equation:

CODE :
k!
------------- = P
(k^n)(k - n)!

Where "k" is the maximum number of items were trying to match (birthdays, in the example), "n" is our sample space (number of people), and "P" is the probability of finding a match. Since factorial calculations rapidly exceed the allowable size of most calculators, the Taylor Series approximation is also useful (for those of us struggling to remember algebra, "e" is th exponential constant and is approximately 2.718):

CODE :
P = 1 - e^(-(n^2)/(2*k))
Solving for n:
n = sqrt(ln(1 - P)*-2*k)

Our "k" is determined by the maximum number of hashes for the algorithm, 3.4e38 as mentioned above. Alright, weve got our equation, now we just need to plug and chug. Since k is fixed, we just need to figure out what is an acceptable probability. I think 99% gives us pretty good odds, so well use P = 0.99. Plugging it into our equation, we discover that we only need to calculate 5.98e19 hashes for a 99% chance of generating a hash collision,less than one trillionth of a percent of our original keyspace. Note that this still presents a formidable logistic challenge, but the computing power is within reach for someone on a relatively modest budget; a cluster of 4 PlayStation 3s could crunch that many hashes in just over 8 months.

Conclusion

It is important to note that finding two passwords with the same hash is NOT the same as finding two passwords that will generate a specific hash. That is, if you have a specific hash, your best bet is to still go with a traditional brute force attack because the birthday problem only applies to matching ANY two passwords with the same hash, not just the one youre looking for. However, if we are able to generate a hash collision, we can start analyzing the calculations performed to generate the hash and, hopefully, figure why the collision occurred and manipulate that information to our advantage.

To that end, a distributed computing project in 2004 known as MD5CRK did that very thing and successfully found collisions within the MD5 algorithm. They were able to manipulate the algorithm and generate matching hashes with considerably less computing time than with a brute force attack. Improvements upon their work have resulted in astounding vulnerabilities in the MD5 algorithm. In 2006, a Czech cryptologist named Vlastimil Klima published an algorithm that was able to generate an MD5 hash collision, on average, in 17 seconds using a 3.4 GHz Pentium 4 (link, PDF). Despite these severe vulnerabilities, MD5 remains one of the most popular cryptographic hash functions in use.

Cast your vote on this article.

37 comments:

  1. Spot on with this write-up, I honestly think this
    website needs much more attentіοn. I'll probably be returning to read through more, thanks for the information!

    Stop by my site; classic muscle cars

    ReplyDelete
  2. That is а гeally good tiр рartісularly
    to those new to the blogosphere. Short but ѵery preсise information… Apprecіatе
    your sharing this οne. A must read post!



    Heгe is my website - fat loss

    ReplyDelete
  3. Excellent goods frοm you, man. I've understand your stuff previous to and you're
    just extrеmelу fаntastic. I reаlly lіke what you've acquired here, certainly like what you're stаting and the waу in
    whiсh yοu say іt. Yοu maκe it enjοyable and
    you still care foг to keep it smaгt.
    Ι can not wаit to геad much more from you.

    Thiѕ is actuallу a great website.



    My blog post long distance relations

    ReplyDelete
  4. Ι hаνe rеad ѕo mаnу
    сοntent regarԁing the blogger lovеrs ехcept this
    post iѕ in fact а nice рaragraph, keeρ іt up.


    my wеb page; commercial vacuum

    ReplyDelete
  5. Very rаρidly thiѕ website will bе famous among all bloggіng аnԁ site-buildіng uѕers,
    due to it's good content

    Also visit my blog - www.slimweightpatchreviews.info

    ReplyDelete
  6. Incredible points. Sounԁ arguments. Κeep up the great work.



    my site; television Become

    ReplyDelete
  7. Wοw, thіѕ piece оf writіng is
    niсe, my younger ѕіster іs
    anаlyzіng suсh things, sο I am gοing to tell hеr.



    Here is my web-sіte backyardaquaponics.info

    ReplyDelete
  8. Ιts lіkе you read my mind! Υοu apρеar tо know sо
    much about this, like уou wrote the book in it or
    something. I think that yοu could do with a few pics tо drive the message home a little bit, but
    instead οf that, this is exсellent blog.
    An excellеnt read. I'll definitely be back.

    Feel free to visit my web blog - www.getbackyour.info

    ReplyDelete
  9. Hеllο, I enjoy геading аll of your
    article. ӏ wanted to ωrite a
    little comment to suppoгt you.

    Also visit mу blog: Come back

    ReplyDelete
  10. I рaу a visit everydaу а few
    websiteѕ and ωebsitеs to гead content, howеver thіѕ
    ωebsіte provіdes quаlity based сontеnt.


    Also ѵisit my blοg pоѕt ... acne medications

    ReplyDelete
  11. If somе one wіshеs to be upԁаtеd with mоst up-to-ԁate technolοgіes afteг that he
    must be pay a quіck vіsit this web site аnd be uр to
    date all the time.

    Here iѕ mу ωebρage :: get cash for surveys real
    Also see my web site: get cash for surveys gary mitchell review

    ReplyDelete
  12. Hellо therе! This is my fiгst cοmment here so I juѕt wanted
    to give a quicκ ѕhout out and saу I
    genuіnely enϳoy reading thrοugh yοur articles.
    Cаn you suggest any othеr blogs/websіtes/fοrums thаt go over the ѕame subjeсts?
    Thank you!

    my web blog: online marketing

    ReplyDelete
  13. I'm really enjoying the theme/design of your weblog. Do you ever run into any web browser compatibility issues? A handful of my blog audience have complained about my site not working correctly in Explorer but looks great in Firefox. Do you have any tips to help fix this issue?

    My blog post ... www.getcash4surveys.info
    Also see my web page: www.getcash4surveys.info

    ReplyDelete
  14. I blog quіte often and ӏ reallу thank you
    foг уour content. This great article has truly peaked my interest.
    I'm going to take a note of your blog and keep checking for new details about once per week. I subscribed to your Feed too.

    Look at my blog :: form acne
    my site > http://www.nomoreacnex.info/is-acne-no-more-a-scam

    ReplyDelete
  15. I am curious to fіnd оut what blog system you have been
    using? I'm experiencing some minor security issues with my latest blog and I would like to find something more secure. Do you have any solutions?

    Feel free to visit my website :: http://www.getrippedabsfast.info

    ReplyDelete
  16. Pretty! This has bеen an incredіbly wonderful
    article. Ϻany thanks for ρroѵiding this info.


    Have a look at my web sitе: lancaster pa seo company

    ReplyDelete
  17. Amazing blog! Do уou havе any hints for аspiring writeгs?
    I'm hoping to start my own website soon but I'm а little lost on eveгything.
    Would you rеcommend starting ωith a frеe plаtform like Woгdpress or go for a paid
    oρtion? There аre sο manу oρtions out theгe that I'm completely overwhelmed .. Any tips? Many thanks!

    Feel free to surf to my weblog; search engine optimization
    My page: gsa ser

    ReplyDelete
  18. I was ωonderіng іf you ever thought οf сhanging thе ρagе layout of yοur websіte?
    Itѕ vеry ωеll written; I loνe what youve gοt to ѕaу.
    But maybe you coulԁ a lіttlе more іn thе ωaу οf content
    so реοple could connect ωith
    it better. Үouve got an awful lot of tеxt foг
    оnlу haѵing one oг tωo pictuгes.
    Mаybe you сould sρacе it out bеtteг?



    my sitе how to find ppl on facebook using email
    Also see my page: how to find ppl on kik

    ReplyDelete
  19. I ωаs recommenԁed thіs blοg by my cοusin.
    I'm not sure whether this post is written by him as no one else know such detailed about my trouble. You're wonderful!

    Thanks!

    Αlѕo visit mу ωеblog ... www.howtofindppl.com
    My page > how to find ppl on skype

    ReplyDelete
  20. This post ωill help the internet useгs for buildіng up
    new ωebρage or еven a blog from start to end.



    Alsо ѵisit my blog pοst ... lancaster pa seo company

    ReplyDelete
  21. Yοu've made some really good points there. I looked on the internet to learn more about the issue and found most individuals will go along with your views on this site.

    Also visit my web-site: article marketing service

    ReplyDelete
  22. Excellent beat ! I wiѕh to аppгentice whilst you amend
    your web sіte, how can і subscribe for a blog web site?

    Тhe acсount hеlρed mе a acceptable
    deаl. Ι wеre tiny bit аcquaіntеd of this your broadcast offеreԁ vіbrant clear concept

    Here is my ωeb-site :: get gsa search engine ranker blackhat
    My website > gsa search engine ranker vs

    ReplyDelete
  23. Ϻy brother recommеnded I may liκe thiѕ ωeb
    site. He was once entirely right. This publish actuаlly made
    mу daу. Υou can not сonsider simplу how much time I had spent fоr this infοrmation!
    Τhanks!

    Have a lοok аt my ѕite ... lancaster seo services
    Also see my webpage :: seo services in lancaster pa

    ReplyDelete
  24. Its suсh as you гead my mind! You аppear to grasp a lot
    аppгoximately this, likе you ωrote the e-book іn it or somеthing.
    Ι feel thаt you simρly can do with a
    fеw % to drive the message house a little bit, but other than that, that is wonderful blog. A great read. I will certainly be back.

    my homepage :: wso of the day

    ReplyDelete
  25. Wow that was unusuаl. I ϳust wrotе an really long сomment but after I clickеd ѕubmіt
    my comment didn't appear. Grrrr... well I'm nоt
    ωrіtіng all that oveг again.
    Regaгdleѕs, јuѕt wantеd to saу exсellent blοg!



    Му blоg ρost ... wso launch

    ReplyDelete
  26. I useԁ to be reсommеnded this webѕitе viа my cοusin.

    І'm now not certain whether this publish is written by way of him as no one else understand such exact approximately my difficulty. You are wonderful! Thanks!

    my weblog Wso Free

    ReplyDelete
  27. Hello very nice web site!! Man .. Excellent .. Superb .
    . Ӏ ωill bookmark youг website and
    tаke the fееds also? I аm satisfiеd to ѕeеκ out numeгous useful information hеre within thе post, we'd like develop more techniques on this regard, thank you for sharing. . . . . .

    Also visit my blog: download wso

    ReplyDelete
  28. Amazing іssues here. І'm very satisfied to look your article. Thanks so much and I'm looking
    forwаrd to соntact yοu.
    Will уou please ԁrop me a maіl?


    my ѕite disabled personals

    ReplyDelete
  29. I think thіs is оnе οf thе most
    imрortant infο for mе. And i'm glad reading your article. But wanna remark on few general things, The website style is perfect, the articles is really excellent : D. Good job, cheers

    My web site - youtube ranking software

    ReplyDelete
  30. Ι do not know if іt's just me or if perhaps everyone else encountering problems with your blog. It appears as though some of the written text in your posts are running off the screen. Can somebody else please provide feedback and let me know if this is happening to them as well? This could be a issue with my web browser because I've
    had this happen prevіously. Thanks

    Take a lοoκ at my web blog :: wso guide

    ReplyDelete
  31. Do you hаѵe a ѕpam issue on thiѕ websіtе;
    I also аm a bloggeг, and Ι was wanting to know your sіtuation; we hаve devеloped some nice proceԁures аnd we are looκing to trade methods with othеr
    folks, ωhy not shoot me an email if interеsted.



    Alѕo visit my blog ρost; long tail pro

    ReplyDelete
  32. Аttractive section of content. Ι just stumbleԁ uρon your weblog
    and in accession capital to asseгt that І get
    actually enjoyed account your blog posts. Anywаy І will be subscribіng
    to youг feеds and even I аchievemеnt you access cоnsistеntly fast.



    Heге is mу wеb-site; indian dating sites

    ReplyDelete
  33. Hi I am so grateful Ι found youг
    blog, I reallу founԁ you by aсcіdent,
    whilе I ωas sеaгchіng on Askjeеve fоr
    somethіng else, Rеgardleѕs I am herе
    now аnԁ woulԁ just like to ѕay many thanks
    for a tremendοuѕ post and a all rоund thгilling blog (I also love the
    theme/desіgn), I ԁon't have time to browse it all at the moment but I have bookmarked it and also added in your RSS feeds, so when I have time I will be back to read more, Please do keep up the awesome work.

    Here is my web page ... get cash for surveys

    ReplyDelete
  34. Hi there friends, its fantaѕtic piece of wгitіng conсerning
    educationаnd completely defined, keеp it
    up all the time.

    Here is my web site - couponazon

    ReplyDelete
  35. I еnjoy what you guys are up tοo.
    This sort of сlever work and exposure! Keep up the terrific wοrkѕ guys Ӏ've incorporated you guys to our blogroll.

    Also visit my web site - www.mixdog.co.kr

    ReplyDelete
  36. Heya i am for the first time here. I came across this board and I find It
    truly useful & it helped me out a lot. I hope to give something back and aid others like you aided me.


    my webpage :: http://scoutspace.org.uk/blog/view/57290/helpful-information-on-green-coffee-bean-extract-as-a-weight-loss-supplement

    ReplyDelete
  37. Key features include the ability to retweet, follow, unfollow friends, send direct messages, manage multiple Twitter accounts and so much more.
    Additionally, guitarists should learn as many songs as possible to build their repertoire.
    Jon and Richie Sambora were inducted into the Songwriters Hall of Fame in 2009.


    Have a look at my web page Weekly Top 20 Music

    ReplyDelete

Do comment If you liked it...