Results 1 to 13 of 13

Thread: Generate Your Own MD5 Collisions In Under a Minute

  1. #1

    Generate Your Own MD5 Collisions In Under a Minute

    Let me begin this post by quoting myself:
    Posted by LLXX @ 09-27-2005, 03:32 AM
    And a few years ago we all thought it was impossible to generate MD5 collisions within a short amount of time. I predict that within the next few years MD5 will be as secure as CRC32 is today, with the speed of computer hardware increasing at its present rate.

    What would really be interesting would be arbitary binary data that MD5'd to some 16-byte long ASCII message. However at the moment it is still nearly impossible to reverse MD5. All we can do is generate collisions quickly.
    My prediction seems to be correct

    Frodevitoyem: http://eprint.iacr.org/2006/104.pdf
    Poter omgpet: http://eprint.iacr.org/2006/105.pdf

    The method of generating the collisions is by "bit tunneling", and looks obscure at first but after a few days of pondering the ephiphany is reached and you'll probably be thinking "why didn't I think of that?" like I am right now... the technique is simply to adjust various bits in the data so that the changes cancel each other, resulting in the same hash. Finding those critical bits is where "tunneling" process is used.

    *nix source: http://web.mit.edu/AFS/sipb/project/fastcoll/
    win32 source: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip
    win32 binary: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip

    Attached is an example of two little files with the same MD5 (hash them yourself if you don't believe )
    Attached Files Attached Files

  2. #2
    Administrator dELTA's Avatar
    Join Date
    Oct 2000
    Location
    Ring -1
    Posts
    4,204
    Blog Entries
    5
    Nice, thanks for the info.
    "Give a man a quote from the FAQ, and he'll ignore it. Print the FAQ, shove it up his ass, kick him in the balls, DDoS his ass and kick/ban him, and the point usually gets through eventually."

  3. #3
    mylo
    Guest
    Quote Originally Posted by LLXX View Post
    Let me begin this post by quoting myself:
    My prediction seems to be correct
    While interesting, I think that implying that MD5 is as "broken" as CRC32 is a bit premature. It's possible - under some limited conditions to generate two files with the same MD5 hash.

    However it's still not practical to, for any given file, generate another file that hashes to the same MD5 value.

    i.e. you may not find it any easier to generate a file with the MD5 value "5ccd8b8c6e6ae27dd2ceb62a3d99343e" than you did before discovering this attack.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  4. #4
    hi,

    i follow the md5 attacks, too, over the years. i remember the demonstrations with the signatures of pdf files. the collisions are "just collisions", so the impact is only in some cases valuable/"useable"

    i don't think md5 can be cracked "within the next years", but things like the collision attacks show that the effort is going somewhere and enable us things we didnt think they are possible, so ... i watch for further surprises ...

    the links are _very_ good, thank you LLXX!

    cheers, 0xf001

  5. #5
    hi,

    i just looked the link up for completeness, as they are so nice documents :

    How to Break MD5 and Other Hash Functions
    Xiaoyun Wang and Hongbo Yu
    http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf

    and
    Colliding X.509 Certificates
    Arjen Lenstra1,2 , Xiaoyun Wang3 , and Benne de Weger2
    http://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf

    from http://www.woodmann.com/forum/showpost.php?p=47633&postcount=4

    regards, 0xf001

  6. #6
    If you are interested, here's a nice post about some colliding .EXEs with same crc32, and more than just 2 colliding files (8 files with same MD5).

    http://hexale.blogspot.com/2005/12/taking-advantage-of-md5-for-real.html

    If anybody is interested in details of this constructs, let me know

  7. #7
    Super Moderator Shub-nigurrath's Avatar
    Join Date
    May 2004
    Location
    Obscure Kadath
    Posts
    430
    well, interested for sure. Post it or PM ..
    (`._.[*~-.,.-~* ŜħůβŇĝŕřāŧħ ₪*~-.,.-~*]._.)
    There are only 10 types of people in the world: Those who understand binary, and those who don't
    http://www.accessroot.com

  8. #8
    Of course you can have more than 2 files with the same MD5, just generate multiple copies of the second collision block (which is generated randomly within certain constraints -- to satisfy the hash of the first).

  9. #9
    yes, that's one way. What I'm doing is different.

    As the method allows for generating collisions on an arbitrary IV, what I do is take the MD5 of the first block and use that as IV to generate a collision. This way, generating 2 collisions give me 4 colliding files. In general, this can be chained, and the method gives 2^n colliding files generating n collisions.

    At one point I had generated 128 chained collisions, what would gave me 2^128 colliding files. Of course I did not generate the 2^128 files, because I son't have enough storage

    This scheme could be used to encode 128 bits of information, and all the different possibilities would have the same MD5. (for example, to leave messages somewhere where the integrity is checked using MD5)

  10. #10
    Quote Originally Posted by Shub-nigurrath View Post
    well, interested for sure. Post it or PM ..
    specifically what do you want more info on?
    if it's a general question, I may be able to give you some links to follow,
    but I could try to answer a more specific question inline

  11. #11
    is there a tool that on a given hash (md5) it can create a data that will result same hash ?

  12. #12
    http://www.freerainbowtables.com/en/tables/md5/

  13. #13
    dongs
    Guest
    Quote Originally Posted by LaBBa View Post
    is there a tool that on a given hash (md5) it can create a data that will result same hash ?
    That is known as a pre-image attack --- no attack is known for MD5 that would be faster than exhaustive search, i.e. about 2^127 tries.

    However, in most cases there is extra information about how the hash was generated, e.g. derived from a password. Rainbow tables are useful in that case, or smart password bruteforcing (trying the most likely words/character combinations).
    I promise that I have read the FAQ and tried to use the Search to answer my question.

Similar Threads

  1. IDA Pro - Generate TIL for directX headers
    By majin in forum Tools of Our Trade (TOT) Messageboard
    Replies: 0
    Last Post: October 2nd, 2013, 09:26
  2. Understand the "Generate License Code" Mechanism
    By Nixkap in forum The Newbie Forum
    Replies: 4
    Last Post: September 6th, 2008, 16:43
  3. How to Generate the INTEL HEX File?
    By shidlingayya in forum The Newbie Forum
    Replies: 3
    Last Post: February 16th, 2008, 04:01

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •