Re: The Pointlessness of the MD5 attacks
C. Scott Ananian wrote: On Wed, 22 Dec 2004, Ben Laurie wrote: Blimey. Finally. An attack I can actually believe in. Excellent. D131DD02C5E6EEC4693D9A0698AFF95C2FCAB58712467EAB4004583EB8FB7F8955AD340609F4B30283E488832571415A085125E8F7CDC99FD91DBDF280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E2B487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080A80D1EC69821BCB6A8839396F9652B6FF72A70001B is prime D131DD02C5E6EEC4693D9A0698AFF95C2FCAB50712467EAB4004583EB8FB7F8955AD340609F4B30283E4888325F1415A085125E8F7CDC99FD91DBD7280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E23487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080280D1EC69821BCB6A8839396F965AB6FF72A70001B is not prime both have MD5 b4b12dc7ec1b9422f6596d2a863d7900. It's worth noting that the *currently known* MD5 collisions are very limited in number and form. Anyone who did not screen their binaries for these would be a fool. It was my understanding that they are very easy to generate. Are you scanning your binaries? Do you have a complete list? When more details emerge about the collision-generation technique, we'll be able to see if the MD5 collisions remain weak keys which we can efficiently check a binary for, or become general enough that it's impossible to rule out a collision in our binary material. But since Ben began this discussion by concentrating only on *currently-known* weaknesses in MD5, I would have to argue that this particular weakness, although possible to actually believe in, is pretty trivial to avoid. In fact, I'd argue strongly that any security review that neglected to notice a known MD5 collision in the key primes (in addition to checking that they are really prime, etc) would be incompetent. Given that we know (for some value of know) that these collisions can be generated with trivial amounts of work, but do not know how to detect them (yet), I wouldn't agree with this. What would be incompetent would be to rely on an MD5 hash. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Something that is interesting about this issue is that it involves transitive vulnerability. If there are only two actors there is no issue. If Alice is the user and Bob is the software maintainer and Bob is bad, then Alice will be exploited regardless of the hash function. If Alice is the user and Bob the maintainer and Bob is good then Alice will be safe, regardless. However if there is a third actor, Charles, from whom Bob accepts information that he will use in a limited way (for example an image or sound file, a patch to the source code which contains extensive comments and whitespace), then whether the hash function is collision-resistant becomes an issue. If Alice and Bob use a collision-resistant hash function, they can rest assured that any software package matching the hash is the package that Bob intended for Alice to use. If they use a hash function which is not collision-resistant they can't, even if the function is second pre-image resistant. This is interesting to me because the problem doesn't arise with only Alice and Bob nor with only Bob and Charles. It is a problem specific to the transitive nature of the relationship: Alice is vulnerable to Charles's choice of package because she trusts Bob to choose packages and Bob trusts Charles to provide image files. And because they are using a non-collision-resistant hash function. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 'attacks'
This isn't worked out enough to be a proof of concept, but I can imagine a piece of code that has a comment This can't overflow because value X computed from the magic bits table will always be between A and B. Get 0.1% speed boost by leaving out range check here but don't change magic bits. That doesn't even have to be so obscure. It provides a place to introduce a security hole that will not be noticed by substituting a new magic bits table without the protective property. Unless someone takes their copy of the source code that has MD5 equal to the MD5 of the sources that have been reviewed by the experts and verifies for themselves whether their magic bits table does compute a value X between A and B, they are vulnerable. If MD5 is trusted, there is no reason to audit every downloaded copy of the source code like that, as long as you are sure that someone has done the audit. -- sidney http://www.sidney.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
The Pointlessness of the MD5 attacks
Ben Laurie writes: Dan Kaminsky's recent posting seems to have caused some excitement, but I really can't see why. In particular, the idea of having two different executables with the same checksum has attracted attention. But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. I guess I disagree. Imagine that the code has some block cipher with some S-boxes hardcoded into it. The code uses this block cipher to decrypt an associated ciphertext and outputs (or takes some action based on) the resulting message. This is an example of code that could be used to fool a MD5 checksum. Moreover, I don't have a great deal of confidence that even a careful code inspection would cause the code to be considered suspicious. Consequently, I don't have great confidence that such an attack would be detected. I know it is tempting to think that, look, Wang et al only found a pair of random-looking messages that collide; they didn't claim to find a pair of meaningful messages that collide; and maybe we can hope that there is no way to come up with a pair of meaningful-looking colliding messages. But I think that kind of hope is unfounded, and acting on hope is asking for trouble. I believe the only safe course now is to assume that MD5's collision resistance is totally broken. If Wang et al can find meaningless-looking collisions today, it seems all too likely that someone else may be able to find meaningful-looking collisions tomorrow. Hoping that the latter will be hard even though the former is known to be easy seems too optimistic for my tastes. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
The Pointlessness of the MD5 attacks
Ben Laurie writes: Indeed, but what's the point? If you control the binary, just distribute the malicious version in the first place. Where this argument breaks down is that someone might have partial but not total control over the binary. This partial control might not be enough for them to distribute a malicious version straightforwardly, but just enough to exploit a MD5 collision. It is hard to be confident that such an attack scenario is impossible. To give one contrived example, imagine that the Windows 2010 binary comes with an image file that is displayed as part of the splash start screen. Imagine that the graphic designer is allowed to supply that image, but the graphic designer has no other authorized access to the source or binary of Windows. Now a disgruntled graphic designer might be able to arrange to find a MD5 collision MD5(img1) = MD5(img2) so that img1 looks like an entirely reasonable Windows splash screen, but img2 contains some scrawled epithet (Tired of Windows crashing all the time? Try Linux!). Or, even more contrived, imagine that img1.jpg looks like a completely normal JPG file, but img2.jpg exploits some buffer overrun in the startup screen's JPG decoder to overwrite the program's image with some other malicious code. Sure, these scenarios are contrived and unlikely. But how do you know that there is not some other (possibly more complex but less contrived) scenario that you would consider more troubling? People seem to be having a hard time grasping what I'm trying to say, so perhaps I should phrase it as a challenge: find me a scenario where you can use an MD5 collision to mount an attack in which I could not mount an equally effective attack without using an MD5 collision. I've got a better challenge: show me a convincing argument that no such scenario exists. What I'm trying to get at is that you've got the burden of proof backwards. Implicit in your challenge is the idea that we should keep trusting MD5 until someone finds a convincing argument that it is insecure in practice. My argument is that this is much too trusting. I believe that, given the theoretical results on MD5, we should not have any trust whatsoever in the security of MD5 as a collision-resistant hash until someone is able to offer a convincing argument that MD5 is secure enough in practice despite its known weaknesses. I could try to answer your challenge. I might even be able to devise some solution to your challenge that would satisfy you. For instance, maybe the image file attack above qualifies as a solution. Or maybe the S-box table attack in my previous email is good enough. But I don't really want to argue about whether I have found a valid answer to your challenge. I shouldn't be required to meet that burden -- the burden of proof should be on whoever wants to believe that MD5 is secure. Why should the burden be on MD5 defenders? Not just because I said so. Part of the reason is that there are just too many complex scenarios to consider. Suppose I conceded that I couldn't find a scenario you'd accept. What would that prove? Very little. Even if I can't think of a suitable scenario for you off the top of my head, that doesn't mean that with more thought I wouldn't find one. Even if I spent a month trying and still couldn't find one, that doesn't mean that others can't. My experience is that if it is possible to find a theoretical attack with one day's work, it is often possible to extend this to a more practical attack with, say, one week's work. Bruce Schneier puts this concisely: Attacks always get better. Trusting in MD5's collision-resistance amounts to assuming that cryptanalysts of MD5 will get this far, but no farther, and that seems like a pretty questionable assumption to me. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 'attacks'
On Wed, 15 Dec 2004, Tim Dierks wrote: Here's an example, although I think it's a stupid one, and agree with [...] I send you a binary (say, a library for doing AES encryption) which you test exhaustively using black-box testing. The black-box testing would obviously be the mistake. How can you tell that the library doesn't start sending plain-text for messages which start with a particular magic bytes, or some other evilness? You can't hope to test *all* messages. The word 'exhaustively' is where your example goes wrong. I'll play Ben's part and claim that if you can provide a library which will *only* be checked using black-box testing, it's much easier to skip the whole MD5 aspect and have it use a covert channel (leak key bits in padding or some such) or transmit plain-text after the first 100M of data encrypted or some such. There are lots of easy ways to get your maliciousness past a black-box test. The use of MD5 (a relatively *hard* way to be malicious) doesn't appreciably change the threat. --scott [it should be noted that any security-conscious tester will/ought to screen your binary for all of the *published* MD5 collisions, so you'll have to generate one yourself if you want to get away with this.] HTLINGUAL Hager Kennedy AEFOXTROT global action network assassinate Register to vote! http://www.yourvotematters.org/VerifiedVoting ( http://cscott.net/ ) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
John Kelsey wrote: So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. So, are you sure there can never be a program which allows such an exploit? I've seen programs that had embedded components (state machines in particular) which were not easily human-readable, and had themselves been generated by computer. And even large graphics, sound, or video sequences can really change the meaning of a program's actions in some ways; those might be susceptible to the requirements of the attack. I agree it's hard to see how to exploit the existing MD5 collision attacks in programs that would look innocent, but I don't see what makes it *impossible*. I did not say it was impossible, I said that such exploits would work just as well without MD5 collisions. For example, if you are going to trigger on some subtle distinction such as a single bit flipped, then make that a bit in a counter, or a bit in the input stream. Then you have data files, as Adam Back mentioned, which are often not human readable, but you'd still like to know if the signature on them is valid, or if they've been changed surreptitiously since the last time they were checked over. Finally, I'm very skeptical that the attacks that have been found recently are the best or only ones that can be done. Do we have any special reason to think that there will never be a way to adapt the attack to be able to slip something plausible looking into a C program? Once your hash function starts allowing collisions, it really just becomes a lot less valuable. I do not have a special reason to think anything about future attacks on MD5. I am discussing the present attacks. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Jay Sulzberger wrote: On Tue, 14 Dec 2004, Ben Laurie wrote: Ondrej Mikle wrote: [snipped many assertions without supporting evidence that MD5 cracks improve attacks] So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. That's true in theory, but it's different in real world. Take Microsoft software as an example. Many banks use their software (and sometimes even military). I don't think that all of them reviewed Microsoft's source code (I guess only a few, if any at all). There was an incident of a worm attacking ATMs. No, and they are therefore vulnerable to Microsoft. Note that MD5 is not required for Microsoft to attack them. Again, the MD5 crack helps. Here one attack is obvious: third parties may more easily make substitutions of code. No, they may not. This crack does _not_ allow a third party to do anything interesting. Another example, Enigma was being sold after WW 2, but the Allies knew it could be broken. The purchasers did not. Same as when US army sold some radio communications that used frequency hopping to Iraq during 1980's. US knew that it could be broken (just in case...). And MD5 helps with this how? Cheers, Ben. The MD5 crack helps here in several ways. Perhaps the most important is that if MD5 is thought to be uncracked, that simple MD5 checking might be considered so safe that no second check is used, at points where a second and third check would help, thus opening up a possible avenue of attack. You are simply restating the supposed attack here, without providing any evidence it is useful. Indeed, even before MD5 was widely known to be cracked, competent security folk often recommended that several hashes be used since in most applications the cost of computing hashes is small. This is true, but not germane. One point to remember is that the published cracks are likely only a small part of the cracks known to well funded professionals. The parallel to the case of the weak Enigmas is that many people buying the weak Enigmas thought they were uncracked, else they would not have bought them. Despite the recent published MD5 cracks, it is clear that the most interesting cracks of MD5 are as yet unpublished. Again, probably true, but definitely not germane. I am saying nothing about what future MD5 cracks may enable, I am only commenting on the cracks currently known. To be clear, I am not advocating the use of MD5, nor have I for many years. I am simply contesting the theory that the ability to produce collisions, as currently known[1], actually provides any useful attack vectors. Cheers, Ben. [1] I agree, future possible methods of producing collisions are likely to have a real impact on security. This is not what I am discussing. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
David Wagner wrote: Ben Laurie writes: Dan Kaminsky's recent posting seems to have caused some excitement, but I really can't see why. In particular, the idea of having two different executables with the same checksum has attracted attention. But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. I guess I disagree. Imagine that the code has some block cipher with some S-boxes hardcoded into it. The code uses this block cipher to decrypt an associated ciphertext and outputs (or takes some action based on) the resulting message. This is an example of code that could be used to fool a MD5 checksum. Moreover, I don't have a great deal of confidence that even a careful code inspection would cause the code to be considered suspicious. Consequently, I don't have great confidence that such an attack would be detected. Assuming you could find a collision s.t. the resulting decryption looked safe with one version and unsafe with the other (rather than gibberish), which I find an even bigger stretch than the idea that you could find a block that looked safe in one version and unsafe in another, I would have said that the mere fact of using a pointless decryption to control the action of the code would be suspect. I know it is tempting to think that, look, Wang et al only found a pair of random-looking messages that collide; they didn't claim to find a pair of meaningful messages that collide; and maybe we can hope that there is no way to come up with a pair of meaningful-looking colliding messages. That kind of thinking may tempt you, but it doesn't tempt me. I am not discussing what it might be possible to do, I am discussing what it is possibile to do. But I think that kind of hope is unfounded, and acting on hope is asking for trouble. I believe the only safe course now is to assume that MD5's collision resistance is totally broken. I had assumed that years ago. If Wang et al can find meaningless-looking collisions today, it seems all too likely that someone else may be able to find meaningful-looking collisions tomorrow. Hoping that the latter will be hard even though the former is known to be easy seems too optimistic for my tastes. Indeed. Not the point I am making. In a nutshell, yes, it is scary that Wang found collisions. No, it is not _more_ scary that you can use those collisions to fool people who aren't looking anyway. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
From: Ben Laurie [EMAIL PROTECTED] Sent: Dec 22, 2004 12:24 PM To: David Wagner [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: The Pointlessness of the MD5 attacks ... Assuming you could find a collision s.t. the resulting decryption looked safe with one version and unsafe with the other (rather than gibberish), which I find an even bigger stretch than the idea that you could find a block that looked safe in one version and unsafe in another, I would have said that the mere fact of using a pointless decryption to control the action of the code would be suspect. Hmm. So maybe I'm missing something. Here's my scenario: a. Alice decides to use GOST for encryption. She finds an implementation in C from Eve, which includes the S-boxes hard-coded in. Note that the specific S-boxes used for GOST are potentially pretty important for their security. b. She also finds a review from some well-known cryptanalyst, Bob, discussing the requirements on the S-boxes, and verifying that the above implementation uses good S-boxes, which includes the md5 hash of the C source code. c. Alice downloads the C source code, and checks the md5 hash. Since the hash is correct, she compiles the code, and starts using her known-secure version of GOST to encrypt sensitive data. d. Unknown to her, though, Eve has slipped in a changed version of the C source code, with the S-boxes changed in a way that makes the encryption much weaker. What prevents this attack from working? Alice counts on a review done by someone competent and a hash of the source code, but the weakness of the hash function means that she's vulnerable to an attack. The only thing that might keep it from working is if it happens to be impossible to choose a pair of sets of S-boxes so that one is weak, the other is strong, and the pair allows an md5 collision. I don't know whether this is possible or not, but there's no inherent reason to think it's impossible--just making some of the 4-bit wide S-boxes in GOST non-bijective has pretty big security implications. (Though 32 rounds covers a lot of sins in S-box selection, in terms of practical attacks rather than academic ones.) ... Indeed. Not the point I am making. In a nutshell, yes, it is scary that Wang found collisions. No, it is not _more_ scary that you can use those collisions to fool people who aren't looking anyway. I think you can use them in ways that may fool people who *are* looking. All you need is a legitimate reason to have a more-or-less arbitrarily chosen block of bits in a part of your program, and then the person reviewing the code says okay, that's random-looking, but reasonable enough. As an alternative example, consider embedding a large prime number in your code, to be used as the modulus when you're doing Diffie-Hellman. Someone reviews the code, and verifies that the number is prime and has all the other required properties. Then, you swap in a different bitstring of equal length, but which is composite and yields a reasonably easy attack on Diffie-Hellman. What prevents this? Ben --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Well the people doing the checking (a subset of the power users) may say I checked the source and it has this checksum, and another user may download that checksum and be subject to MITM and not know it. Or I could mail you the source and you would check it with checksum and compare checksum to web site. Or somone could just go ahead and change the source without changing the checksum or any of the changlog / cvs change notification stuff and people would not think there is a change to review. Some of this scenarios will likely work some of the time against users. Adam On Tue, Dec 14, 2004 at 11:21:13PM +, Ben Laurie wrote: Adam Back wrote: I thought the usual attack posited when one can find a collision on a source checksum is to make the desired change to source, then tinker with something less obvious and more malleable like lsbits of a UI image file until you find your collision on two input source packages. Quite so, but the desired change to source is either not visible, or suspicious. If it's not visible, then just make it malicious. And if it's suspicious then it shouldn't be run. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Adam Back wrote: I thought the usual attack posited when one can find a collision on a source checksum is to make the desired change to source, then tinker with something less obvious and more malleable like lsbits of a UI image file until you find your collision on two input source packages. Quite so, but the desired change to source is either not visible, or suspicious. If it's not visible, then just make it malicious. And if it's suspicious then it shouldn't be run. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Bill Frantz wrote: On 12/14/04, [EMAIL PROTECTED] (Ben Laurie) wrote: Dan Kaminsky's recent posting seems to have caused some excitement, but I really can't see why. In particular, the idea of having two different executables with the same checksum has attracted attention. But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. One scenario that might form an attack is to take code which is normally distributed in executable form, for example RPMs, and make it possible to have two different programs that pass the same signature check. Given that someone has arranged to have the doppleganger blocks generated as part of the output of the compiler, different binaries can later be injected into the distribution system without a signature verification failure. Indeed, but what's the point? If you control the binary, just distribute the malicious version in the first place. People seem to be having a hard time grasping what I'm trying to say, so perhaps I should phrase it as a challenge: find me a scenario where you can use an MD5 collision to mount an attack in which I could not mount an equally effective attack without using an MD5 collision. So, for example, in the scenario above, the attacker has control of a binary in which he can insert arbitrary content. Clearly, in his place, I can simply distribute malware without any MD5 collisions. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Is this the case? Can't we instead start with code C and malicious C' and try to find a collision on H(C||B) == H(C'||B') after trying 2^64 B values we'll find such a collision by the birthday principle. Now we can have people review and attest to the correctness of code C, and then we can MITM and change surrepticiously with C'. Adam On Wed, Dec 15, 2004 at 08:44:03AM +, Ben Laurie wrote: Adam Back wrote: Well the people doing the checking (a subset of the power users) may say I checked the source and it has this checksum, and another user may download that checksum and be subject to MITM and not know it. You are missing the point - since the only way to make this trick work is to include a very specific chunk of 64 bytes with a few bits flipped (or not), the actual malicious code must be present anyway and triggered by the flipped bits. So, all of these attacks rely on the code not being inspected or being sufficiently cunning that inspection didn't help. And, if that's the case, the attacks work without any MD5 trickery. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
From: Ben Laurie [EMAIL PROTECTED] Sent: Dec 14, 2004 9:43 AM To: Cryptography [EMAIL PROTECTED] Subject: The Pointlessness of the MD5 attacks Dan Kaminsky's recent posting seems to have caused some excitement, but I really can't see why. In particular, the idea of having two different executables with the same checksum has attracted attention. But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. So, are you sure there can never be a program which allows such an exploit? I've seen programs that had embedded components (state machines in particular) which were not easily human-readable, and had themselves been generated by computer. And even large graphics, sound, or video sequences can really change the meaning of a program's actions in some ways; those might be susceptible to the requirements of the attack. I agree it's hard to see how to exploit the existing MD5 collision attacks in programs that would look innocent, but I don't see what makes it *impossible*. Then you have data files, as Adam Back mentioned, which are often not human readable, but you'd still like to know if the signature on them is valid, or if they've been changed surreptitiously since the last time they were checked over. Finally, I'm very skeptical that the attacks that have been found recently are the best or only ones that can be done. Do we have any special reason to think that there will never be a way to adapt the attack to be able to slip something plausible looking into a C program? Once your hash function starts allowing collisions, it really just becomes a lot less valuable. Cheers, Ben. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Adam Back wrote: Is this the case? Can't we instead start with code C and malicious C' and try to find a collision on H(C||B) == H(C'||B') after trying 2^64 B values we'll find such a collision by the birthday principle. Indeed, but that is not the attack suggested. Now we can have people review and attest to the correctness of code C, and then we can MITM and change surrepticiously with C'. And with only 2^64 effort. Let me know when you're done. Adam On Wed, Dec 15, 2004 at 08:44:03AM +, Ben Laurie wrote: Adam Back wrote: Well the people doing the checking (a subset of the power users) may say I checked the source and it has this checksum, and another user may download that checksum and be subject to MITM and not know it. You are missing the point - since the only way to make this trick work is to include a very specific chunk of 64 bytes with a few bits flipped (or not), the actual malicious code must be present anyway and triggered by the flipped bits. So, all of these attacks rely on the code not being inspected or being sufficiently cunning that inspection didn't help. And, if that's the case, the attacks work without any MD5 trickery. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
On Tue, 14 Dec 2004 14:43:24 +, Ben Laurie [EMAIL PROTECTED] wrote: But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. There are many ways to obfuscate code so tha it will seem innocent, see for example International Obfuscated C Code Contest (http://www.ioccc.org/main.html). It can be based on variable modification using buffer overflows, integer overflows, strange side effects of expression evaluation, etc. Another possibility for an attacker is the use of deliberate and very rare race conditions, which only attacker knows how to trigger. Race conditions are very difficult to discover. Cf. Linux ptrace race condition (http://archives.neohapsis.com/archives/bugtraq/2001-10/0135.html). It's been there in kernels 2.2.0 - 2.2.19 and 2.4.0 to 2.4.9. It allowed for local privilege escalation. Took quite a long time to discover it, even though it was open source code. Quite a long time for opportunity, if we assumed an attacker would do similar attack deliberately. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. That's true in theory, but it's different in real world. Take Microsoft software as an example. Many banks use their software (and sometimes even military). I don't think that all of them reviewed Microsoft's source code (I guess only a few, if any at all). There was an incident of a worm attacking ATMs. Another example, Enigma was being sold after WW 2, but the Allies knew it could be broken. The purchasers did not. Same as when US army sold some radio communications that used frequency hopping to Iraq during 1980's. US knew that it could be broken (just in case...). Ondrej Mikle - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Ondrej Mikle wrote: On Tue, 14 Dec 2004 14:43:24 +, Ben Laurie [EMAIL PROTECTED] wrote: But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. There are many ways to obfuscate code so tha it will seem innocent, see for example International Obfuscated C Code Contest (http://www.ioccc.org/main.html). That does not make it seem innocent, it makes it seem incomprehensible. It can be based on variable modification using buffer overflows, integer overflows, strange side effects of expression evaluation, etc. I agree, but you do not need MD5 attacks to achieve these things. Another possibility for an attacker is the use of deliberate and very rare race conditions, which only attacker knows how to trigger. Race conditions are very difficult to discover. Cf. Linux ptrace race condition (http://archives.neohapsis.com/archives/bugtraq/2001-10/0135.html). It's been there in kernels 2.2.0 - 2.2.19 and 2.4.0 to 2.4.9. It allowed for local privilege escalation. Took quite a long time to discover it, even though it was open source code. Quite a long time for opportunity, if we assumed an attacker would do similar attack deliberately. Again, MD5 does not improve these attacks. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. That's true in theory, but it's different in real world. Take Microsoft software as an example. Many banks use their software (and sometimes even military). I don't think that all of them reviewed Microsoft's source code (I guess only a few, if any at all). There was an incident of a worm attacking ATMs. No, and they are therefore vulnerable to Microsoft. Note that MD5 is not required for Microsoft to attack them. Another example, Enigma was being sold after WW 2, but the Allies knew it could be broken. The purchasers did not. Same as when US army sold some radio communications that used frequency hopping to Iraq during 1980's. US knew that it could be broken (just in case...). And MD5 helps with this how? Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
The Pointlessness of the MD5 attacks
Dan Kaminsky's recent posting seems to have caused some excitement, but I really can't see why. In particular, the idea of having two different executables with the same checksum has attracted attention. But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
I thought the usual attack posited when one can find a collision on a source checksum is to make the desired change to source, then tinker with something less obvious and more malleable like lsbits of a UI image file until you find your collision on two input source packages. Adam On Tue, Dec 14, 2004 at 10:17:28PM +, Ben Laurie wrote: But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
