Re: [PHP] Re: reverse MD5 ???
Richard Lynch wrote: On Fri, June 10, 2005 3:01 pm, Jason Barnett said: That is incredibly interesting stuff, many thanks for that link! So the position seems to be that it may not be feasible to reverse MD5, but it is now feasible to create forged documents / binaries / whatever that result in exactly the same MD5 hash as the original. No. Richard, did you actually go to the site that Greg showed and look at the example? Two very different (as in content) postscript documents... same MD5 hash. I actually tried it out for myself... and indeed the two different documents produced the exact same MD5 sum. That's a one in a billion chance... So, if your binary file HAPPENS to match that meaningless string, you could use that OTHER meaningless string instead... Again I say... did you look at the other meaningless string in the example? I don't pretend to understand how the authors made it work, but it wasn't just some meaningless string that they got to match. I'll bet neither of the two strings has any real-world meaning They just happen to be the two strings that are easy to find that have the same MD5. This has absolutely NO meaning in real-world uses of MD5. You'd have heard a LOT more screaming and wailing and gnashing of teeth if this mattered. :-) Unless of course most people dismiss it the same way that you seem to be dismissing it. ;) -- NEW? | http://www.catb.org/~esr/faqs/smart-questions.html STFA | http://marc.theaimsgroup.com/?l=php-generalw=2 STFM | http://php.net/manual/en/index.php STFW | http://www.google.com/search?q=php -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
RE: [PHP] Re: reverse MD5 ???
In that framework there is no such thing as decrypting an MD5 digest, because an MD5 digest is not an encrypted version of the message to start with. No amount of CPU power will change this basic fact -- though CPU power can be used to do a brute force search for strings which will generate a given MD5 value. However, as stated before, at current levels of computing power this is not feasible for messages beyond I think 7 or 8 characters long (don't quote me on that). One real-world example of the potential weakness of 'md5 out of the box' comes from a consultancy project I was involved in not so long back. The app in question was storing the md5 value of 4-digit PINs in the background database, and the owners of the app were quietly confident that this meant the PINs were 'encrypted' and 'secure'. Of course, there are only 10,000 possible PIN values between and , regardless of whether or not they're stored in plaintext or md5 hashed form, and I guess it took me less than 15 minutes to build a reference table of all md5 hash values for the possible plaintext PINs and therefore effortlessly retrieve the plaintext PIN values from their table. Imagine their surprise. And if *I* could do it... Md5 is a very handy way of 'securing' [1] password information, but only when the plaintext value offers enough possible variation in length and / or value to make building a 'possible variations' lookup table a difficult proposition. Regards, Murray Footnotes: [1] Without wanting to get into a technical debate of exactly what constitutes 'secure' when it comes to hashing / encrypting sensitive information -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
Murray @ PlanetThoughtful wrote: The app in question was storing the md5 value of 4-digit PINs in the background database, and the owners of the app were quietly confident that this meant the PINs were 'encrypted' and 'secure'. Amazing. Thanks for sharing that. It's a great example. :-) Of course, there are only 10,000 possible PIN values between and , regardless of whether or not they're stored in plaintext or md5 hashed form, and I guess it took me less than 15 minutes to build a reference table of all md5 hash values for the possible plaintext PINs and therefore effortlessly retrieve the plaintext PIN values from their table. There are efforts to create these types of tables for arbitrary strings: http://md5.rednoize.com/ Of course, it's worth noting that these methods aren't reversing MD5. Md5 is a very handy way of 'securing' [1] password information, but only when the plaintext value offers enough possible variation in length and / or value to make building a 'possible variations' lookup table a difficult proposition. Exactly, and this is why it's a good practice to use a seed when you generate MD5s for passwords. Thanks again for the story, frightening as it was. :-) Chris -- Chris Shiflett Brain Bulb, The PHP Consultancy http://brainbulb.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
RE: [PHP] Re: reverse MD5 ???
Amazing. Thanks for sharing that. It's a great example. :-) You're very welcome! If it helps just one other developer avoid the same pitfall, then today is a very good day. :-) Exactly, and this is why it's a good practice to use a seed when you generate MD5s for passwords. Which is exactly what I suggested, and what they ended up implementing, thanks to the fact that I could provide them with the original plaintext PIN values for the existing records. Still, once I'd had a chance to look at the plaintext PINs, it was depressing to notice the frequency of 'easy' PIN values, such as '', '1234', '' etc. Even with a seed, those values would have been relatively easy to guess at with frequency analysis, and it goes beyond my meager hostile decryption skills to guess at whether that made deriving the seed any easier or not. I suggested implementing a class that randomly selected from somewhere between 5 to 10 possible seed values when hashing the PIN for storage, which would have meant simply using all 5 or 10 seeds when comparing the PIN for subsequent validation, to reduce the frequency of hash-to-easy-PIN repetition, but it hadn't been implemented by the time my consultancy ended and I'd be willing to bet a year's pay it, or any other method of providing some sort of buffering against frequency analysis, hasn't been since. Of course, there's a whole conversation to be had regarding the fact that if your db server has been compromised to the point where the contents of tables are exposed, then it's reasonable to at least speculate (depending on your server setup and method by which it was accessed) that perhaps your entire app has been compromised, and your seed values may now be known to the hostile entity as well. Still and all, there's absolutely no reason to make the job of compromising your data any easier on a hypothetical hacker than is within your level of competency as a developer. Adding a seed value to md5 hashes is a simple and effective method under most circumstances that even beginner to intermediate developers can employ. In other words, It Is A Very Good Thing. ;-) Regards, Murray -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
On 4/22/05, Richard Lynch [EMAIL PROTECTED] wrote: On Thu, April 21, 2005 10:28 am, Ryan A said: Interesting reading, even though most of it went over my head :-) There ar'nt any tools freely available to the average joe to decypher a md5 hash though...right? No, there aren't. And even the collisions found don't really mean much in the grand scheme of things, from what I've read. http://www.cits.rub.de/MD5Collisions/ snip Technical Background: How did you do it? Based on [WY05], we implemented an attack to find random collisions for the MD5 compression function. It took just a few hours on a customary PC. /snip -- Greg Donald Zend Certified Engineer http://destiney.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
That is incredibly interesting stuff, many thanks for that link! So the position seems to be that it may not be feasible to reverse MD5, but it is now feasible to create forged documents / binaries / whatever that result in exactly the same MD5 hash as the original. I actually tried it out for myself... and indeed the two different documents produced the exact same MD5 sum. Now I'm wondering... does this mean that I now need to download PHP binaries from multiple trusted sources, do the checksums on each separate download, *and* do a diff for each binary? That way a cracker has to infiltrate multiple servers in order for me to be affected by a cracked PHP binary? Very interesting indeed... -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
On Fri, June 10, 2005 3:01 pm, Jason Barnett said: That is incredibly interesting stuff, many thanks for that link! So the position seems to be that it may not be feasible to reverse MD5, but it is now feasible to create forged documents / binaries / whatever that result in exactly the same MD5 hash as the original. No. I actually tried it out for myself... and indeed the two different documents produced the exact same MD5 sum. That's a one in a billion chance... So, if your binary file HAPPENS to match that meaningless string, you could use that OTHER meaningless string instead... I'll bet neither of the two strings has any real-world meaning They just happen to be the two strings that are easy to find that have the same MD5. This has absolutely NO meaning in real-world uses of MD5. You'd have heard a LOT more screaming and wailing and gnashing of teeth if this mattered. :-) -- Like Music? http://l-i-e.com/artists.htm -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
If you are happy with infinite answers, I guess that is Ok. In practice, since you would probably wouldn't expect numbers (or strings) infinetly long, assuming that you just have N possible initial values, you would have N/3 possible answers. I thought the question was about getting one answer. Greg Donald [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] On 4/21/05, Satyam [EMAIL PROTECTED] wrote: If I tell you that dividing a certain number by three gives you a remainder of 2, would you be able to guess the first number? Yes. 5, 8, 11, 14, etc. Same thing with MD5, it is just one way, it can't be reversed. MD5 collisions were found last year: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf Just a matter of time/cpu power. -- Greg Donald Zend Certified Engineer http://destiney.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
On Thu, April 21, 2005 10:28 am, Ryan A said: Interesting reading, even though most of it went over my head :-) There ar'nt any tools freely available to the average joe to decypher a md5 hash though...right? No, there aren't. And even the collisions found don't really mean much in the grand scheme of things, from what I've read. The worst-case scenario is that in a few years' time, more likely in MANY years' time, somebody will figure out a way to use hardware not yet available to crack MD5... Even that is more likely to be crack one out of every 2 billion MD5 values rather than crack any old MD5 they run across. I really wouldn't sweat this in terms of your day-to-day life/programming, other than to keep your code modular enough to replace md5 with something else in the year 2020 or whatever. MD5 collisions were found last year: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf Just a matter of time/cpu power. Maybe I'm mis-remembering the article and its implications, but I don't think they can apply that to an arbitrary MD5 hash and reverse it to the plain-text original... It's more like a theoretical hole that may some day prove to be the first step in a long long long process of understanding something that might maybe some day yield a way to de-crypt MD5. -- Like Music? http://l-i-e.com/artists.htm -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
Hey, I really wouldn't sweat this in terms of your day-to-day life/programming, other than to keep your code modular enough to replace md5 with something else in the year 2020 or whatever. Thats fine by me, by 2020 the spaceship would have landed and I will be declared sub ruler of planet earth before being taken to planet #Xgdwgd to rule... BTW, I'm recruiting sub-sub rulers for earth if anybodys intrested requirments are: must be able to PHP program using MySql as the DB...no oracle high class sh*t. Cheers, Ryan P.S Just got up...feeling funny. -- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.308 / Virus Database: 266.10.1 - Release Date: 4/20/2005 -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
On 21 Apr 2005 Greg Donald wrote: Same thing with MD5, it is just one way, it can't be reversed. MD5 collisions were found last year: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf Just a matter of time/cpu power. I don't think that's right. Collisions allow certain kinds of cryptographic attacks against things like MD5-based signatures but that is not at all the same as being able to simply determine the original message content from the digest. Rather, they allow you to substitute the original message with a different one which generates the same MD5 hash. This may or may not be useful as an attack, depending on how MD5 is being used. -- Tom -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
I don't think that's right. Collisions allow certain kinds of cryptographic attacks against things like MD5-based signatures but that is not at all the same as being able to simply determine the original message content from the digest. Rather, they allow you to substitute the original message with a different one which generates the same MD5 hash. This may or may not be useful as an attack, depending on how MD5 is being used. Anyone ever tried using ENCODE and DECODE functions in mysql ? -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
On 4/22/05, Richard Lynch [EMAIL PROTECTED] wrote: It's more like a theoretical hole that may some day prove to be the first step in a long long long process of understanding something that might maybe some day yield a way to de-crypt MD5. That's exactly my point. It's similar to how a local root exploit sometimes evolves into a remote root exploit once publicized and people begin working on it. Disclaimer: There are only about 5 or 6 people in the entire world who know anything about encryption.. and sadly I am not one of them. -- Greg Donald Zend Certified Engineer http://destiney.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
It's more like a theoretical hole that may some day prove to be the first step in a long long long process of understanding something that might maybe some day yield a way to de-crypt MD5. That's exactly my point. It's similar to how a local root exploit sometimes evolves into a remote root exploit once publicized and people begin working on it. Disclaimer: There are only about 5 or 6 people in the entire world who know anything about encryption.. and sadly I am not one of them. MD5 is hashing which is not the same as encryption. Hashing is normally defined as a one-way conversion of a plaintext message into a fixed-length digest or hash. Encryption is normally defined as conversion of a plaintext message into ciphertext which cannot be read until it is decrypted -- i.e. encryption normally implies the possibility of decryption. In that framework there is no such thing as decrypting an MD5 digest, because an MD5 digest is not an encrypted version of the message to start with. No amount of CPU power will change this basic fact -- though CPU power can be used to do a brute force search for strings which will generate a given MD5 value. However, as stated before, at current levels of computing power this is not feasible for messages beyond I think 7 or 8 characters long (don't quote me on that). The recently discovered hole is unrelated to the above. It is that under certain conditions it is possible to find two different plaintext messages which will generate the same MD5 digest. This could theoretically allow one to spoof a message and have it appear legitimate if MD5 is used for the legitimacy check, but it does not allow reversal of MD5, nor do the authors of articles on this problem seem to claim that it could. -- Tom -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
On 4/21/05, Satyam [EMAIL PROTECTED] wrote: If I tell you that dividing a certain number by three gives you a remainder of 2, would you be able to guess the first number? Yes. 5, 8, 11, 14, etc. Same thing with MD5, it is just one way, it can't be reversed. MD5 collisions were found last year: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf Just a matter of time/cpu power. -- Greg Donald Zend Certified Engineer http://destiney.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
Interesting reading, even though most of it went over my head :-) There ar'nt any tools freely available to the average joe to decypher a md5 hash though...right? Cheers, -Ryan On 4/21/2005 6:34:45 PM, Greg Donald ([EMAIL PROTECTED]) wrote: On 4/21/05, Satyam [EMAIL PROTECTED] wrote: If I tell you that dividing a certain number by three gives you a remainder of 2, would you be able to guess the first number? Yes. 5, 8, 11, 14, etc. Same thing with MD5, it is just one way, it can't be reversed. MD5 collisions were found last year: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf Just a matter of time/cpu power. -- Greg Donald Zend Certified Engineer http://destiney.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php -- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.308 / Virus Database: 266.10.1 - Release Date: 4/20/2005 -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: reverse MD5 ???
Nope.. nothing that'll easily decrypt MD5 back to it's original value. As the line below says and the rest of the thread explained, MD5 is a one-way function. In ordre to take an MD5 hash and get back to the original value, you'd basically have to take every possible combination of letters/numbers/etc and create an MD5 hash out of them and compare that with the one you're trying to Decrypt. So you're not really decrypting, just methodically guessing and then automatically trying the next guess. This is a VERY long and time consuming process and essentially isn't worth it. The short answer? No, there are no tools to decrypt MD5. It's a hash (like a checksum) not an encrypted string. You could write your own brute force program like above in about 2 minutes, but it wouldn't do you any practical good. -TG = = = Original message = = = Interesting reading, even though most of it went over my head :-) There ar'nt any tools freely available to the average joe to decypher a md5 hash though...right? Cheers, -Ryan Just a matter of time/cpu power. ___ Sent by ePrompter, the premier email notification software. Free download at http://www.ePrompter.com. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
