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"
>David Wagner wrote: >> Ben Laurie writes: > > >> 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? > >They do not relate to the known MD5 collisions - these are general >collisions, which we do not know how to create, not the restricted ones >we do know how to create. I disagree; I think it might be possible with the current cryptanalysis on MD5. The collisions that can be currently produced only flip a couple of bits, and you can add what you want before and after the 1024-bit block. Imagine some code that reads the image (or whatever bit-string) as a textual string, in one case it doesn't read the whole bit-array because there is a null string-terminating character, in the other case (collision) the character is not present and causes a buffer overflow. I think something like that can be done today. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
solution, Re: The Pointlessness of the MD5 "attacks"
Ben Laurie wrote:
David Wagner wrote:
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.
They do not relate to the known MD5 collisions - these are general
collisions, which we do not know how to create, not the restricted ones
we do know how to create.
"we do not know how to create" != "we will not know how to create"
The fear of a possible (likely?) attack as described by Wagner should
be countered by a concrete solution, not by considering it a time bomb
with a hopefully long enough fuse.
I think such a concrete solution exists, still using MD5. Even though
MD5 is not collision-resistant. The solution applies to everything that
Ben says, as well.
If Microsoft chooses a salt value for an MD5-HMAC, which salt value
Microsoft does not disclose to the programmer and the world until the
file is (1) quality-controlled and (2) handled for distribution, the
programmer would NOT be able to find the collision. Security is easily
assured by Microsoft choosing the salt only after (1) QC. Distribution
of any software, or text, can be likewise protected -- just don't let
the attacker control everything.
The problem here is not MD5. The problem is allowing the attacker to
have too much power.
Cheers,
Ed Gerck
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 "attacks"
John Kelsey wrote: 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.) There is certainly no inherent reason to think its impossible. What prevents this attack _right now_ is that we don't know how to generate a collision that satisfies the required properties. 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? Blimey. Finally. An attack I can actually believe in. Excellent. Indeed, here is such a pair: D131DD02C5E6EEC4693D9A0698AFF95C2FCAB58712467EAB4004583EB8FB7F8955AD340609F4B30283E488832571415A085125E8F7CDC99FD91DBDF280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E2B487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080A80D1EC69821BCB6A8839396F9652B6FF72A70001B is prime D131DD02C5E6EEC4693D9A0698AFF95C2FCAB50712467EAB4004583EB8FB7F8955AD340609F4B30283E4888325F1415A085125E8F7CDC99FD91DBD7280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E23487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080280D1EC69821BCB6A8839396F965AB6FF72A70001B is not prime both have MD5 b4b12dc7ec1b9422f6596d2a863d7900. Cool. 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"
James A. Donald wrote: -- On 15 Dec 2004 at 8:51, Ben Laurie wrote: 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 could circulate watermarked versions of copyrighted material without it being apparent that they were watermarked. That was the attack I was not disputing :-) -- 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:
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?
They do not relate to the known MD5 collisions - these are general
collisions, which we do not know how to create, not the restricted ones
we do know how to create.
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.
I claim I already have.
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.
Absolutely not, I would not argue for a second that we should continue
to trust MD5, I am merely making a very narrow argument about the nature
and utility of the newly found collisions.
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.
It would if it were possible, but it isn't.
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.
I have made, I think, quite clear arguments why this attack is pointless.
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.
I am not suggesting we trust MD5. My point is that this attack does not
cause me to trust it any less than I already did, and nor does it offer
any more useful exploit of MD5 than we already had.
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"
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"
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*. That's not what Ben is saying at all. He's saying that once you give the adversary the power to do the sorts of things that are required for this (like being able to replace a give C with C'), there are easier ways for the attacker to get the desired result than playing with collisions. I do, however, feel the need to be a bit pedantic and say that tables for state machines are seldom random (for some suitable definition of random). Nor are graphics, sound, nor video. Inserting the artifacts into them you need to make this work is really, really obvious for the same reasons that Shamir and Van Someren showed that finding key material is so easy. I have an attack that I just came up with that pretty much proves Ben's point. I can, using this technique, make any MD5 preimage give you any desired hash value. It's trivial, once I can replace code C with C'. Give up? Answer below. Hint: it works just as well against SHA1. Or SHA-256. Or Whirlpool. Or pick your hash. Answer: patch the md5 software. put in a table that gets searched -- when you see hash x, return y. if you want to be clever, obfuscate the check and the result. toss in some xoring so you don't have the direct target and result hashes there, so simple grepping doesn't give the trick away. But once you can replace C with C', why bother doing bit-flipping when you can just compile the code you want, and replace the code that rats you out? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 "attacks"
On Wed, 15 Dec 2004 10:06:10 -0500 (GMT-05:00), John Kelsey <[EMAIL PROTECTED]> wrote: > > 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*. > > 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. > Exactly. Yes, malware can be distributed without any use of any hash function. I try to demonstrate on an example, what the MD5 collision provides and how to make it 'innocent'. You don't have to put malicious code in the program. For example, telnet is not secure, but there are uses of it which don't need encryption/authentication. Similarly, HTTP is widely used, but HTTPS can be used when needed. Take a bank as an example. Some transactions require secure connection, but not every page on the bank server has to be transmitted using a secure connection. If an attacker would cause the software to switch from HTTPS to HTTP in the "right" moment, it could lead to disaster. Most of data (file) formats have some sort of header. An attacker can do this: He will say that the colliding block is a header, with first four bytes being the 'magic bytes' as you know from many formats (e.g. exe has MZ, bmp has BM, elf executables have ELF). Next, he will proclaim that the rest of the 1024 bits are some data, e.g. some counts of something and the differing bits/bytes will be some flags. The point is to use the bits in some calculation that is legitimate. That means, it "moves the question of trust" onto the data package. A person doing inspection would not find anything wrong, since the person receives correct executable and the "good" data package. That is the difference between use and non-use of MD5 collision. An obfuscated malicious code can be discovered, even though it may be difficult. When you use collision, it may not be discovered, since there is no "evil" action in the code. The "evil" is created as a race condition using the "evil" colliding package. Now, I try an example (I know it's not the best one, but I hope it makes the point clear): Suppose an attacker is packager in a company and his role is to take software, pack it up and create installation scripts. The package is still reviewed after his packaging. Let's suppose the company is working on some server-bundle-software which installs http server, IDS and optionally SSH and Telnet. By default, Telnet is disabled. Telnet's role may be for example so that anyone could telnet to the machine and have e.g. statistics of server usage or some non-sensitive information or computation. That's the justification of having the telnet there in the software. If one wanted to use it, he would enable it and configure it correctly so that anonymous users can't do any harm or get to sensitive information. Well, there is the flag in the header (=the colliding block) saying if it should be installed or not. After packaging is complete, it is inspected once more and if no flaw is found, it is put on company's ftp/web server for distribution along with MD5 sums published on multiple places. Then the attacker (as an insider) swaps the two packages. Anyone believing the MD5 sums would install the software and wouldn't realize that telnet is installed and not configured (documentation says something different). That could open a way for anyone in. To sum it up, the MD5 collision allows: -have code and data, that do not do anything unwanted (can be proven by inspecting the code) -the other colliding package does the same, but it creates some unnecesary service/action that is dangerous in given context. The presence of the service is justified, though. In default installation it is disabled. So says the manual. But that's not true. So the MD5 collision itself does not do much, but with additional trickery it could be used. If the flaw would be discovered in the software, who would be held responsible in the company? The testers, inspectors of code. Not the packager. He could sell the knowledge of the security hole to spammers, virus writers, etc. I'm not saying the MD5 collision allows for a highly practical attack (at least the example involves an insider), but when we know it's possible, why should we c
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'
C. Scott Ananian wrote: 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. Exactly so, thankyou. 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"
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"
-- On 15 Dec 2004 at 8:51, Ben Laurie wrote: > 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 could circulate watermarked versions of copyrighted material without it being apparent that they were watermarked. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG brRAUUDlwL/ZhPKf51gh0pzlr6ISDbBPNAbnzJfI 41Hx46udB9H+g9Lkm68G20fQMC+F6YzLxJhmwuZu4 - 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]
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]
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]
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]
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 Wed, 15 Dec 2004 08:51:29 +, Ben Laurie <[EMAIL PROTECTED]> wrote: > 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. Here's an example, although I think it's a stupid one, and agree with you that the MD5 attack, as it's currently known to work, isn't a material problem (although it's a clear signal that one shouldn't use MD5): I send you a binary (say, a library for doing AES encryption) which you test exhaustively using black-box testing. The library is known not to link against any external APIs (in fact, perhaps it's implemented in a language and runtime with a decent security sandbox model, e.g., Java). You then incorporate it into your application and sign the whole thing with MD5+RSA to vouch for its accuracy. I incorporate several copies of a suitable MD5 collision block in my library, so one of them will be at the correct 64-byte block boundary. I can then modify bits inside of my library, which car checked by the library code and cause it to change the functionality of the library, yet the signature will still verify. This would be pretty easy to do as a proof-of-concept, but I don't have the time. - Tim - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 "attacks"
On Tue, 14 Dec 2004, Ben Laurie wrote:
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.
No. The C library, running on hardware without serious defenses, is
sufficiently obscure, that one more possibility of spoofing makes things
worse.
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.
Yes, but having a crack for a crypto hash makes all these things easier.
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.
It can help disguise such 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.
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.
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. 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.
oo--JS.
-
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: 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. 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. 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"
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. Cheers - Bill - Bill Frantz| The first thing you need when | Periwinkle (408)356-8506 | using a perimeter defense is a | 16345 Englewood Ave www.pwpconsult.com | perimeter. | Los Gatos, CA 95032 - 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"
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"
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"
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]
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]
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]
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]
