Author | Message | Time |
---|---|---|
Skywing | http://lists.grok.org.uk/pipermail/full-disclosure/2005-November/038719.html Looks like it's time to move anything you have still using MD5 away from it. 45 minutes to generate a collision on a slow P4 is about as broken as you can get, makes it completely useless for any practical purposes now. | November 14, 2005, 7:53 PM |
rabbit | Wow...a post...from Skywing... Anyways, [quote]Average runtime on P4 1.6ghz - 5 seconds[/quote] Damn....but I guess it's still good for a hash of a program, as I assume it would be pretty hard to get executable code (or whatever) to collide with other other executable code. | November 15, 2005, 12:46 AM |
Quarantine | [me=Warrior]runs to update his website. :(![/me] | November 15, 2005, 1:38 AM |
Newby | Wow... | November 15, 2005, 2:09 AM |
KkBlazekK | [quote author=Warrior link=topic=13234.msg133983#msg133983 date=1132018729] [me=Warrior]runs to update his website. :(![/me] [/quote] I told you! Now what I thought would happen, actually did. | November 15, 2005, 2:16 AM |
Quarantine | Good thing PHP has built in sha1(). I'll have to make everyone resign up though. Not something top priority however. | November 15, 2005, 2:18 AM |
kamakazie | Now to see what the experts say about this. I'm surprised there was no discussion for that thread. | November 15, 2005, 2:38 AM |
Twix | [quote author=Warrior link=topic=13234.msg133987#msg133987 date=1132021119] Good thing PHP has built in sha1(). I'll have to make everyone resign up though. Not something top priority however. [/quote] Aint sha1 the structure of MD5 I could be wrong but that is what it says on wiki. | November 15, 2005, 3:05 AM |
Topaz | Wasn't MD5 cracked last year? hm... | November 15, 2005, 4:33 AM |
Newby | [quote author=Topaz link=topic=13234.msg134014#msg134014 date=1132029220] Wasn't MD5 cracked last year? hm... [/quote] Not with a mechanism for a 45 minute collision... | November 15, 2005, 4:52 AM |
Kp | [quote author=rabbit link=topic=13234.msg133973#msg133973 date=1132015583] Wow...a post...from Skywing... Anyways, [quote]Average runtime on P4 1.6ghz - 5 seconds[/quote] Damn....but I guess it's still good for a hash of a program, as I assume it would be pretty hard to get executable code (or whatever) to collide with other other executable code. [/quote] No, not at all. Programs are routinely quite large these days, and it's no trouble at all to pad your .rdata segment with whatever bytes are necessary to get the hash you want. Failing that, put the colliding bytes into your .text segment and just ensure that the code flow never tries to execute it. | November 16, 2005, 12:32 AM |
noob | It may have been cracked, but that doesn't make it useless. DES is still used after all. | November 16, 2005, 1:46 AM |
Yegg | [quote author=noob link=topic=13234.msg134150#msg134150 date=1132105588] It may have been cracked, but that doesn't make it useless. DES is still used after all. [/quote] It's safer to move onto newer, more advanced hashing algorithm's however. | November 16, 2005, 1:49 AM |
iago | [quote author=Skywing link=topic=13234.msg133945#msg133945 date=1131998013] makes it completely useless for any practical purposes now. [/quote] I disagree. As far as I know, there's still no practicle way (without a full brute force) to obtain the original data of MD5 based on the hash. In other words, it's still safe for storing passwords. [quote author=Warrior link=topic=13234.msg133987#msg133987 date=1132021119] Good thing PHP has built in sha1(). I'll have to make everyone resign up though. Not something top priority however. [/quote] You're replacing a dead algorithm with a dying algorithm. Not a good idea :-P I'd recommend that you start storing the SHA1 of the MD5. The advantages are: - Extra layer of security; even though if both are broken then together they're broken, it'll still keep away the riff raff. - You don't have to make people re-sign up. Just SHA1() their MD5() hashes. But if you're using it to store a password, I still don't think it's an issue. Odds are, for most passwords, it can be bruteforced with a dictionary attack anyways :) | November 16, 2005, 2:46 AM |
Quarantine | Yea, I thought of that after I posted. | November 16, 2005, 2:55 AM |
tA-Kane | It's an interesting read. I tried the provided sample Win32 executable, but it failed with an error of 0x8009000F. | November 16, 2005, 5:12 PM |
Skywing | [quote author=tA-Kane link=topic=13234.msg134273#msg134273 date=1132161170] It's an interesting read. I tried the provided sample Win32 executable, but it failed with an error of 0x8009000F. [/quote] I'll let him know and ask him to post an updated version. That's because he was doing something wrong with how he was generating a random number with cryptoapi. It should probably work if you reboot after running it, since the keyset it creates is temporary I think. (For that version, executions after the first are likely to break due to that bug.) | November 16, 2005, 6:47 PM |
tA-Kane | What I did is I loaded the source up in VS2005 and simply replaced "CRYPT_NEWKEYSET" with 0. However, since I'm not too familiar with the Cryptography API, I fear I may have broken the speed at which it works: it has been running for about four hours and has displayed "block #1 done" for several hours and has yet to display "block #2 done". Perhaps I misinterpreted the 45 minutes as being best-time rather than average-time? | November 16, 2005, 9:38 PM |
Arta | [quote author=iago link=topic=13234.msg134171#msg134171 date=1132109168] I disagree. As far as I know, there's still no practicle way (without a full brute force) to obtain the original data of MD5 based on the hash. In other words, it's still safe for storing passwords. [/quote] Not true at all -- if you can generate a collision, you don't need the original data. | November 17, 2005, 5:48 PM |
iago | To generate a collision, you need the password, don't you? Or is it actually possible to generate a collision based purely on the hashed data? | November 17, 2005, 5:51 PM |
Arta | It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet. | November 17, 2005, 11:11 PM |
iago | [quote author=Arta[vL] link=topic=13234.msg134416#msg134416 date=1132269076] It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet. [/quote] I thought that the collisions discussed here entailed finding two pieces of data that generates the same hash. Am I mistaken about that, or did we make different assumptions? I haven't read the paper or anything, so I could very well be wrong there. | November 18, 2005, 1:57 AM |
Kp | [quote author=iago link=topic=13234.msg134429#msg134429 date=1132279073][quote author=Arta[vL] link=topic=13234.msg134416#msg134416 date=1132269076]It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet.[/quote]I thought that the collisions discussed here entailed finding two pieces of data that generates the same hash. Am I mistaken about that, or did we make different assumptions? I haven't read the paper or anything, so I could very well be wrong there.[/quote] It depends what use of MD5 you're trying to defeat. If you obtain the MD5 of someone's password and you simply want to masquerade as that user (but are satisfied with never learning their original password), you need only come up with a data sequence which suffers a collision with the known hash. Then when you send that sequence off claiming it to be the password, the server will compute its MD5, get the same value as the MD5 as the correct password (since you picked this data sequence specifically for this property!), and conclude that you're the legitimate owner. If the target site is badly thought out, you could then edit his account settings to point the e-mail associated with it to an account you own, then trigger the "password recovery" feature to get his real password (instead of some random sequence which happens to collide with his password). On the other hand, if you're trying to spoof a document whose MD5 signature is known, you'd need the original document so you could check if your forgery looked even vaguely like the original. Though, given that we're dealing with hashing algorithms, if you have the original input data, you can compute the hash result easily enough. :) | November 18, 2005, 3:18 AM |
iago | [quote author=Kp link=topic=13234.msg134444#msg134444 date=1132283916] [quote author=iago link=topic=13234.msg134429#msg134429 date=1132279073][quote author=Arta[vL] link=topic=13234.msg134416#msg134416 date=1132269076]It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet.[/quote]I thought that the collisions discussed here entailed finding two pieces of data that generates the same hash. Am I mistaken about that, or did we make different assumptions? I haven't read the paper or anything, so I could very well be wrong there.[/quote] It depends what use of MD5 you're trying to defeat. If you obtain the MD5 of someone's password and you simply want to masquerade as that user (but are satisfied with never learning their original password), you need only come up with a data sequence which suffers a collision with the known hash. Then when you send that sequence off claiming it to be the password, the server will compute its MD5, get the same value as the MD5 as the correct password (since you picked this data sequence specifically for this property!), and conclude that you're the legitimate owner. If the target site is badly thought out, you could then edit his account settings to point the e-mail associated with it to an account you own, then trigger the "password recovery" feature to get his real password (instead of some random sequence which happens to collide with his password). On the other hand, if you're trying to spoof a document whose MD5 signature is known, you'd need the original document so you could check if your forgery looked even vaguely like the original. Though, given that we're dealing with hashing algorithms, if you have the original input data, you can compute the hash result easily enough. :) [/quote] The first scenario is the one I was considering. I fully agree that it's useless for signing documents now, that's not even an issue. For it to be an issue with passwords, it seems like it depends on how the passwords are used, then. To be a threat, you have to find some way to obtain the MD5 of the password. That could likely be done in 2 ways: 1. Sniff traffic containing the MD5 -- if you can sniff their traffic, odds are (in any webapp) you can see their password go by in plaintext. It's still rare to see SSL used for sites. So that's irrelevant. 2. Have access to the password database -- if they have access to the database of MD5's, odds are it's already game over. However, if all you have is access to the MD5 hash, and the server requires that you send it an MD5 hash, which I don't think is very common at all, then yeah, this MD5 weakness is a danger. But I don't believe I've ever seen a server that does that. For a web-app like, for example, Warrior's, I think the only weakenss in MD5 that could adversely affect its security is if there was a large amount of clustering, narrowing the number of brute-force attempts needed to guess the correct password. But I don't believe that MD5 contains that particular weakness, so that's not a problem. I guess what I'm saying is that whether or not it's a danger to an application depends rather strongly on how it's being used, and in the most common cases, web apps aren't secure anyway, so using MD5 to store passwords really doesn't matter. | November 18, 2005, 4:57 AM |
kamakazie | [quote author=Kp link=topic=13234.msg134444#msg134444 date=1132283916] If the target site is badly thought out, you could then edit his account settings to point the e-mail associated with it to an account you own, then trigger the "password recovery" feature to get his real password (instead of some random sequence which happens to collide with his password). [/quote] Minor nit-pick: Badly thought out as in storing a hash of the password and the password plain text. If the website only stores the hash, you're probably never going to recover the original password. | November 18, 2005, 5:34 AM |
Arta | Note that numerous web apps don't guard password hashes very carefully. They are often stored in a cookie to facilitate autologon, and are easily exposed by XSS attacks. | November 18, 2005, 2:36 PM |
JoeTheOdd | Personally, I bruteforced a password (a friend of mine's, we were exploiting a IPB, but enough about that) in about 45 seconds. It was two numbers and three letters, so not all that long, but eh? | November 18, 2005, 4:40 PM |
kamakazie | [quote author=Arta[vL] link=topic=13234.msg134504#msg134504 date=1132324611] Note that numerous web apps don't guard password hashes very carefully. They are often stored in a cookie to facilitate autologon, and are easily exposed by XSS attacks. [/quote] Well regardless, autologon is a pretty insecure concept as anyone with physical access can impersonate a user (unless you have the stored cookies expire after some set amount of time). I'm sure many websites don't even require physical access, just the contents of the stored cookie unless that cookie contains a hash of variables unique to a computer (i.e. IP address). | November 18, 2005, 6:49 PM |
iago | [quote author=Arta[vL] link=topic=13234.msg134504#msg134504 date=1132324611] Note that numerous web apps don't guard password hashes very carefully. They are often stored in a cookie to facilitate autologon, and are easily exposed by XSS attacks. [/quote] If they are stored in a cookie, then you don't need to find a collision. You just copy/paste the hash into your own cookie and proceed to log in. That's an interesting point, though. How would you recommend storing passwords in cookies? I was thinking of storing a salted hash, as well as the salt, but that wouldn't create any advantages versus packetlogs. Maybe the IP and the password (or password hash) together, hashed. But that would be annoying for dial-up users. | November 18, 2005, 10:51 PM |
Arta | You can't do it securely. It's just one of those times when lots of convinience outweighs a small security risk. | November 19, 2005, 12:04 AM |
iago | Ok, that's pretty much what I figured. Hashing it with the IP is probably the best plan, if I had to choose. But back to the MD5 thing: passwords stored in MD5 in cookies don't help you any unless you want to find a collision with his password for a different site that only accepts plaintext password, then compares it to MD5, which isn't really realistic. My point? MD5 is still ok for storing passwords for webapps, in general. :) | November 19, 2005, 12:20 AM |
kamakazie | [quote author=iago link=topic=13234.msg134593#msg134593 date=1132359631] But back to the MD5 thing: passwords stored in MD5 in cookies don't help you any unless you want to find a collision with his password for a different site that only accepts plaintext password, then compares it to MD5, which isn't really realistic. [/quote] Don't most sites accept a plain-text password, hash it server-side and compare? I wish there was a nice standard for hashing client-side (i.e. <input type="password" hash="md5"> or something). | November 19, 2005, 1:40 AM |
iago | [quote author=dxoigmn link=topic=13234.msg134610#msg134610 date=1132364436] [quote author=iago link=topic=13234.msg134593#msg134593 date=1132359631] But back to the MD5 thing: passwords stored in MD5 in cookies don't help you any unless you want to find a collision with his password for a different site that only accepts plaintext password, then compares it to MD5, which isn't really realistic. [/quote] Don't most sites accept a plain-text password, hash it server-side and compare? [/quote] Yeah, but if you're doing that you're sending your password plaintext over the network, so if you can sniff their traffic it doesn't matter if you can break md5.. | November 19, 2005, 5:21 AM |
kamakazie | [quote author=iago link=topic=13234.msg134624#msg134624 date=1132377679] [quote author=dxoigmn link=topic=13234.msg134610#msg134610 date=1132364436] [quote author=iago link=topic=13234.msg134593#msg134593 date=1132359631] But back to the MD5 thing: passwords stored in MD5 in cookies don't help you any unless you want to find a collision with his password for a different site that only accepts plaintext password, then compares it to MD5, which isn't really realistic. [/quote] Don't most sites accept a plain-text password, hash it server-side and compare? [/quote] Yeah, but if you're doing that you're sending your password plaintext over the network, so if you can sniff their traffic it doesn't matter if you can break md5.. [/quote] But most sites use SSL to encrypt the whole stream. | November 19, 2005, 6:11 AM |
iago | [quote author=dxoigmn link=topic=13234.msg134631#msg134631 date=1132380668] [quote author=iago link=topic=13234.msg134624#msg134624 date=1132377679] [quote author=dxoigmn link=topic=13234.msg134610#msg134610 date=1132364436] [quote author=iago link=topic=13234.msg134593#msg134593 date=1132359631] But back to the MD5 thing: passwords stored in MD5 in cookies don't help you any unless you want to find a collision with his password for a different site that only accepts plaintext password, then compares it to MD5, which isn't really realistic. [/quote] Don't most sites accept a plain-text password, hash it server-side and compare? [/quote] Yeah, but if you're doing that you're sending your password plaintext over the network, so if you can sniff their traffic it doesn't matter if you can break md5.. [/quote] But most sites use SSL to encrypt the whole stream. [/quote] I can't think of any normal sites that use SSL. eCommerce sites do, obviously. And porn sites do, which I suppose is a form of eCommerce. But it's definitely not common. | November 19, 2005, 8:09 AM |
Mephisto | [code]MD5CALC(MD5CALC(data)+data) = secure md5[/code] | November 30, 2005, 4:24 AM |
tA-Kane | [quote author=Mephisto link=topic=13234.msg135796#msg135796 date=1133324662] [code]MD5CALC(MD5CALC(data)+data) = secure md5[/code] [/quote]Except not. If MD5CALC(Data) == MD5CALC(FalsifiedData), then MD5CALC(MD5CALC(Data)+Data) == MD5CALC(MD5CALC(FalsifiedData)+FalsifiedData) == MD5CALC(MD5CALC(Data)+FalsifiedData) == MD5CALC(MD5CALC(FalsifiedData)+Data) | November 30, 2005, 5:09 AM |
Mephisto | [quote author=tA-Kane link=topic=13234.msg135801#msg135801 date=1133327355] [quote author=Mephisto link=topic=13234.msg135796#msg135796 date=1133324662] [code]MD5CALC(MD5CALC(data)+data) = secure md5[/code] [/quote]Except not. If MD5CALC(Data) == MD5CALC(FalsifiedData), then MD5CALC(MD5CALC(Data)+Data) == MD5CALC(MD5CALC(FalsifiedData)+FalsifiedData) == MD5CALC(MD5CALC(Data)+FalsifiedData) == MD5CALC(MD5CALC(FalsifiedData)+Data) [/quote] :( | November 30, 2005, 5:30 AM |
EpicOfTimeWasted | [quote author=Mephisto link=topic=13234.msg135796#msg135796 date=1133324662] [code]MD5CALC(MD5CALC(data)+data) = secure md5[/code] [/quote] MD5 is broken... calling it multiple times doesn't make it any less broken. | November 30, 2005, 7:19 AM |
Maddox | How is this the death of MD5? What this does is generate two sets of data that have the same hash. You can't generate false data from a given hash using this. | December 2, 2005, 6:07 PM |
kamakazie | [quote author=Maddox link=topic=13234.msg136077#msg136077 date=1133546842] How is this the death of MD5? What this does is generate two sets of data that have the same hash. You can't generate false data from a given hash using this. [/quote] http://www.schneier.com/essay-074.html | December 2, 2005, 7:19 PM |
Maddox | [quote author=dxoigmn link=topic=13234.msg136087#msg136087 date=1133551183] [quote author=Maddox link=topic=13234.msg136077#msg136077 date=1133546842] How is this the death of MD5? What this does is generate two sets of data that have the same hash. You can't generate false data from a given hash using this. [/quote] http://www.schneier.com/essay-074.html [/quote] Ok? | December 3, 2005, 10:33 AM |
kamakazie | [quote author=Maddox link=topic=13234.msg136184#msg136184 date=1133606007] [quote author=dxoigmn link=topic=13234.msg136087#msg136087 date=1133551183] [quote author=Maddox link=topic=13234.msg136077#msg136077 date=1133546842] How is this the death of MD5? What this does is generate two sets of data that have the same hash. You can't generate false data from a given hash using this. [/quote] http://www.schneier.com/essay-074.html [/quote] Ok? [/quote] Well let me outline the main points: [list] [li]One-way hash functions are supposed to have two properties.[/li] [li]One, they're one-way.[/li] [li]Two, they're collision-free.[/li] [li]Breaking a hash function means showing that either -- or both -- of those properties aren't true.[/li] [/list] You might argue that mathematically no hash function can be collision free. But that isn't the point. The point is it should be sufficiently difficult to find such a collision. Well no longer is it difficult. "Attacks always get better; they never get worse." | December 3, 2005, 10:04 PM |
tA-Kane | [quote author=dxoigmn link=topic=13234.msg136243#msg136243 date=1133647461] [li]Two, they're collision-free.[/li][/quote]Not so much collision-free (since that'll be pretty much impossible for any source value longer than the length of the hash) as relatively impossible to locate collisions in a timely manner (eg, even a few years is too soon). | December 4, 2005, 2:09 AM |
kamakazie | [quote author=tA-Kane link=topic=13234.msg136302#msg136302 date=1133662197] [quote author=dxoigmn link=topic=13234.msg136243#msg136243 date=1133647461] [li]Two, they're collision-free.[/li][/quote]Not so much collision-free (since that'll be pretty much impossible for any source value longer than the length of the hash) as relatively impossible to locate collisions in a timely manner (eg, even a few years is too soon). [/quote] Yea, I said that in my post... | December 4, 2005, 2:25 AM |
Adron | Still wonder about the uselessness of it. If you cannot find the original text from a hash, and you cannot find a collision for a hash given a hash, it still seems pretty useful. Being able to generate two completely plaintexts that give the same hash is not all that useful. For it to be useful, those two plaintexts need to both be meaningful. | December 7, 2005, 7:36 AM |
Arta | [quote] and you cannot find a collision for a hash given a hash [/quote] I think you can do that. [quote] For it to be useful, those two plaintexts need to both be meaningful. [/quote] That's not as hard as it sounds. For example, you can often stretegically pad documents with whitespace to achieve this, which most people wouldn't notice. Also, I'm not sure that both plaintexts need to be meaningful: that's only the case if the plaintext needs to 'fool' a person. | December 7, 2005, 3:28 PM |
Maddox | [quote author=Arta[vL] link=topic=13234.msg136705#msg136705 date=1133969280] I think you can do that. [/quote] Prove it. | December 8, 2005, 2:52 AM |
Kp | [quote author=Maddox link=topic=13234.msg136780#msg136780 date=1134010322] [quote author=Arta[vL] link=topic=13234.msg136705#msg136705 date=1133969280] I think you can do that. [/quote]Prove it.[/quote] Easy. There are an infinite number of possible inputs to MD5, but only 2[sup]128[/sup] outputs. Therefore, there exist multiple inputs which generate the same output. Given some particular output, a collision can be found by computing the hash of each member of the lexicographic enumeration of the possible inputs. | December 8, 2005, 7:32 AM |
iago | [quote author=Kp link=topic=13234.msg136812#msg136812 date=1134027174] [quote author=Maddox link=topic=13234.msg136780#msg136780 date=1134010322] [quote author=Arta[vL] link=topic=13234.msg136705#msg136705 date=1133969280] I think you can do that. [/quote]Prove it.[/quote] Easy. There are an infinite number of possible inputs to MD5, but only 2[sup]128[/sup] outputs. Therefore, there exist multiple inputs which generate the same output. Given some particular output, a collision can be found by computing the hash of each member of the lexicographic enumeration of the possible inputs. [/quote] To rephrase: prove that it can be done in a reasonable amount of time. | December 8, 2005, 4:12 PM |
Adron | [quote author=Arta[vL] link=topic=13234.msg136705#msg136705 date=1133969280] That's not as hard as it sounds. For example, you can often stretegically pad documents with whitespace to achieve this, which most people wouldn't notice. Also, I'm not sure that both plaintexts need to be meaningful: that's only the case if the plaintext needs to 'fool' a person. [/quote] Well, the paper describes an attack by flipping bits. If they can only attack md5 in a way that works when the data is random binary, I would say that is a limitation. I do not think their method for breaking md5 in a reasonable time could at all apply if the inputs are not arbitrary binary data, but limited to adding or removing whitespace. | December 9, 2005, 6:10 AM |
Arta | See here: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html | December 9, 2005, 3:15 PM |
Adron | [quote author=Arta[vL] link=topic=13234.msg136950#msg136950 date=1134141304] See here: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html [/quote] Ah, but again, it is a random string that they insert. Someone producing a document like this would easily be revealed as a fraud. | December 9, 2005, 8:38 PM |
Kp | [quote author=Adron link=topic=13234.msg137016#msg137016 date=1134160721] [quote author=Arta[vL] link=topic=13234.msg136950#msg136950 date=1134141304]See here: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html[/quote]Ah, but again, it is a random string that they insert. Someone producing a document like this would easily be revealed as a fraud.[/quote] Not necessarily. Many modern document formats (for instance, Microsoft Office Document) have quite a bit of garbage inside them that the UI never shows you. If the random string is inserted in one of these dead zones, you'd have to take the file apart to discover it. MD5 is also still used for validating that programs, source archives, etc. have not been altered. These formats also have the potential to remain "valid data" after having arbitrary bits inserted, provided that the arbitrary bits are put in the right place. For instance, put your junk string in the slack space of the .data segment, or destroy a debug message with your new data. | December 10, 2005, 12:41 AM |
Adron | Ah, yes, you can insert your junk overwriting a debug message or you can put it in a space that is not used, but then you as the author are conspiring to make a bad executable from the start. You could do that by just inserting obfuscated evil code. In the other case, where you produce a document and ask someone to sign that, then applying that signature to a different document, the existence of such inserted data means you can identify this as an attempt at fraud. | December 10, 2005, 1:21 AM |
Maddox | [quote author=Kp link=topic=13234.msg136812#msg136812 date=1134027174] [quote author=Maddox link=topic=13234.msg136780#msg136780 date=1134010322] [quote author=Arta[vL] link=topic=13234.msg136705#msg136705 date=1133969280] I think you can do that. [/quote]Prove it.[/quote] Easy. There are an infinite number of possible inputs to MD5, but only 2[sup]128[/sup] outputs. Therefore, there exist multiple inputs which generate the same output. Given some particular output, a collision can be found by computing the hash of each member of the lexicographic enumeration of the possible inputs. [/quote] Are you being particularly dense on purpose? | December 10, 2005, 1:31 AM |
Adron | [quote author=Kp link=topic=13234.msg136812#msg136812 date=1134027174] Easy. There are an infinite number of possible inputs to MD5, but only 2[sup]128[/sup] outputs. Therefore, there exist multiple inputs which generate the same output. Given some particular output, a collision can be found by computing the hash of each member of the lexicographic enumeration of the possible inputs. [/quote] Is it possible to find a collision for every 128-bit combination? | December 10, 2005, 6:34 AM |
tA-Kane | [quote author=Adron link=topic=13234.msg137049#msg137049 date=1134177682] Ah, yes, you can insert your junk overwriting a debug message or you can put it in a space that is not used, but then you as the author are conspiring to make a bad executable from the start. You could do that by just inserting obfuscated evil code. [/quote]Similarly, you'd also be conspiring to create a forged document. What's the difference? [quote author=Adron link=topic=13234.msg137049#msg137049 date=1134177682]In the other case, where you produce a document and ask someone to sign that, then applying that signature to a different document, the existence of such inserted data means you can identify this as an attempt at fraud. [/quote]You're missing the point, Adron. The inserted junk data would be junk -- probably in an unprintable area of the document, or perhaps just whitespace. But nonetheless, it would not alter the look of the document (except of course the wording perhaps, so you'd have (for example, in an executive order) "go to place Y" instead of "go to place X"). Thus, while it is a fraudulent document, anyone signing the document would note that the MD5 sum of the fraud matches the MD5 sum of the real document, and the fraud looks like a real document with which has not been tampered. | December 10, 2005, 10:10 AM |
Adron | [quote author=tA-Kane link=topic=13234.msg137075#msg137075 date=1134209435] [quote author=Adron link=topic=13234.msg137049#msg137049 date=1134177682] Ah, yes, you can insert your junk overwriting a debug message or you can put it in a space that is not used, but then you as the author are conspiring to make a bad executable from the start. You could do that by just inserting obfuscated evil code. [/quote]Similarly, you'd also be conspiring to create a forged document. What's the difference? [/quote] If you do not trust the author from the start, any amount of signatures is not going to make a difference. If you do trust the author not to prepare to fool you, there is no problem. [quote author=tA-Kane link=topic=13234.msg137075#msg137075 date=1134209435] [quote author=Adron link=topic=13234.msg137049#msg137049 date=1134177682]In the other case, where you produce a document and ask someone to sign that, then applying that signature to a different document, the existence of such inserted data means you can identify this as an attempt at fraud. [/quote]You're missing the point, Adron. The inserted junk data would be junk -- probably in an unprintable area of the document, or perhaps just whitespace. But nonetheless, it would not alter the look of the document (except of course the wording perhaps, so you'd have (for example, in an executive order) "go to place Y" instead of "go to place X"). Thus, while it is a fraudulent document, anyone signing the document would note that the MD5 sum of the fraud matches the MD5 sum of the real document, and the fraud looks like a real document with which has not been tampered. [/quote] No, you are missing the point. The important fact here is that there would be junk inserted into the document. Upon investigation, it would be clear that this is indeed a forgery. | December 10, 2005, 8:48 PM |
AcidAngel | as i pointed out on the aim dev forum, md5 can be reversed simply using precomputed hash tables, you can squeeze a rather large alphanumeric table onto a dvd, or use some of the available tools to generate your own tables based on what characters you want. I know of a couple sites that store precomputed tables for very very large tables (alphanumeric + symbols + lots of chars) but they all charge you to perform a look up (you submit an md5 and it returns to you all matches to that md5). finding the same tables already generated probably isnt that hard with a lil looking around though. And performing a lookup on said table takes very little time. just some 2 cents. | January 23, 2006, 5:02 PM |
AcidAngel | http://thepiratebay.org/details.php?id=3408209 1-7 character alphanumeric table yes i know this thread is oldnews | January 23, 2006, 5:07 PM |
iago | [quote author=AcidAngel link=topic=13234.msg142858#msg142858 date=1138035740] as i pointed out on the aim dev forum, md5 can be reversed simply using precomputed hash tables, you can squeeze a rather large alphanumeric table onto a dvd, or use some of the available tools to generate your own tables based on what characters you want. I know of a couple sites that store precomputed tables for very very large tables (alphanumeric + symbols + lots of chars) but they all charge you to perform a look up (you submit an md5 and it returns to you all matches to that md5). finding the same tables already generated probably isnt that hard with a lil looking around though. And performing a lookup on said table takes very little time. just some 2 cents. [/quote] There are also free tables. But any programmer with half a brain for security adds a salt, which makes pre-computed tables effectively useless. | January 23, 2006, 5:55 PM |
AcidAngel | any programmer with half a brain for security would not have used md5 as their authentication protection in the first place =) | January 23, 2006, 7:07 PM |
iago | Why not? MD5 is still fine for passwords, and I still use it for passwords. If there's some reason not to hash passwords with it, please tell me. | January 24, 2006, 12:30 AM |