Re: Collisions for hash functions: how to exlain them to your boss
>From: Eric Rescorla <[EMAIL PROTECTED]> Sent: Jun 14, 2005 9:36 AM >Subject: Re: Collisions for hash functions: how to exlain them to >your boss [Discussing the MD5 attacks and their practicality, especially the recent postscript demonstration.] ... >But everything you've just said applies equally to my >JavaScript example. It's not a security vulnerability in >the browser or the data format that it displays differently >depending on the context. It's an intentional feature! I think our disagreement here has to do with what we're seeing from the attack. You're seeing a specific attack vector--use conditional execution/display + the ability to find specific collisions of a particular form to yield these nice attacks where we have two messages that amount to X ||M0||M1 X*||M0||M1 where when the first part of the message is X, some kind of conditional execution displays M0, while X* leads to the display of M1. And I think you're right to say that in many cases, once you're viewing the result of blindly executing programs that I send you, you're vulnerable to other attacks that are about as damaging. Now, it's certainly possible imagine cases where this kind of conditional execution wouldn't be allowed to access anything outside the file, but once you've decided to put in a full featured scripting language, it's not that much of a stretch to think you'll let me read the system time. I'm seeing a more general pattern of attacks, in which X and X* amount to context for the display of whatever follows them. That seems to me to encompass a lot more than macros and script files with conditional execution. And even when I don't have a specific attack in mind, it worries me that if I'm trying to help someone safely use MD5, I've got to think through whether there is any way at all to make this kind of attack pattern work. It's a heck of a lot easier to say "don't use MD5." ... >-Ekr --John Kelsey - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Collisions for hash functions: how to exlain them to your boss
John Kelsey <[EMAIL PROTECTED]> writes: >>From: Eric Rescorla <[EMAIL PROTECTED]> >>Sent: Jun 13, 2005 5:09 PM >>To: "Weger, B.M.M. de" <[EMAIL PROTECTED]> >>Cc: cryptography@metzdowd.com, >> Stefan Lucks <[EMAIL PROTECTED]> >>Subject: Re: Collisions for hash functions: how to exlain them to your boss > > ... >>Yes, this is all true, but it's kind of orthogonal to my point, >>which is that if you're willing to execute a program, this >>attack can be mounted *without* the ability to produce hash >>collisions. The fact that so few people regard PS, HTML, Word, >>etc. as software just makes this point that much sharper. >>As far as I can tell, the ability fo produce hash collisions just >>makes the attack marginally worse. > > Hang on a minute. The issue isn't whether your data format is being > executed (in some sense almost any nontrivial data format can be seen > as a scripting language interpreted by the viewer). The issue is that > I can make two different documents, one of which displays exactly what > you tell me you want it to display, the other of which displays > anything I like, with the same MD5 (MD4, RIPEMD, SHA0, SHA1) hash > output. You can view the document on a viewer you trust, without any > security vulnerabilities in the viewer/data format, but you still > get fooled. > > Saying "inspect the code/data/whatever" as an answer to this problem > isn't too useful, since an inspection intended to turn up security > problems may not turn up the fact that the executable code has some > region of data in it which could be varied in just the right way for > the MD5 or SHA1 attacks to work, without making it an invalid > program. (I've been thinking about how these attacks apply to > validated software in voting and gaming machines) But everything you've just said applies equally to my JavaScript example. It's not a security vulnerability in the browser or the data format that it displays differently depending on the context. It's an intentional feature! > Fundamentally, it's just really hard to safely use a hash function for > which collisions can be found cheaply. It requires every crypto > engineer to become an expert on both how the collision attack works > (and all the possible variants!) and also an expert on what ambiguity > may exist in each data format he may ever want to hash. I agree with this. I'm merely observing that many of those data formats in practice have features that let you mount isomorphic attacks even if you can't break the hash function. And it's equally impractical for people to be experts on which of them allow such dual interpretations. And because of this the *incremental* insecurity offered by the current generation of hash attacks is extremely small. -Ekr - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Collisions for hash functions: how to exlain them to your boss
>From: Eric Rescorla <[EMAIL PROTECTED]> >Sent: Jun 13, 2005 5:09 PM >To: "Weger, B.M.M. de" <[EMAIL PROTECTED]> >Cc: cryptography@metzdowd.com, > Stefan Lucks <[EMAIL PROTECTED]> >Subject: Re: Collisions for hash functions: how to exlain them to your boss ... >Yes, this is all true, but it's kind of orthogonal to my point, >which is that if you're willing to execute a program, this >attack can be mounted *without* the ability to produce hash >collisions. The fact that so few people regard PS, HTML, Word, >etc. as software just makes this point that much sharper. >As far as I can tell, the ability fo produce hash collisions just >makes the attack marginally worse. Hang on a minute. The issue isn't whether your data format is being executed (in some sense almost any nontrivial data format can be seen as a scripting language interpreted by the viewer). The issue is that I can make two different documents, one of which displays exactly what you tell me you want it to display, the other of which displays anything I like, with the same MD5 (MD4, RIPEMD, SHA0, SHA1) hash output. You can view the document on a viewer you trust, without any security vulnerabilities in the viewer/data format, but you still get fooled. Saying "inspect the code/data/whatever" as an answer to this problem isn't too useful, since an inspection intended to turn up security problems may not turn up the fact that the executable code has some region of data in it which could be varied in just the right way for the MD5 or SHA1 attacks to work, without making it an invalid program. (I've been thinking about how these attacks apply to validated software in voting and gaming machines) Fundamentally, it's just really hard to safely use a hash function for which collisions can be found cheaply. It requires every crypto engineer to become an expert on both how the collision attack works (and all the possible variants!) and also an expert on what ambiguity may exist in each data format he may ever want to hash. There's an obvious solution to this in principle, though the huge installed bases of MD5 and SHA1 make it painful >-Ekr -John Kelsey - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Collisions for hash functions: how to exlain them to your boss
"Weger, B.M.M. de" <[EMAIL PROTECTED]> writes: > > Technically speaking you're correct, they're signing a program. > But most people, certainly non-techies like Alice's boss, > view postscript (or MS Word, or format that allows macros>) files not as programs but as static > data. In being targeted at non-techies I find this attack more > convincing than those of Mikle and Kaminsky, though essentially > it's a very similar idea. > > Note that opening the postscript files in an ASCII-editor > (or HEX-editor) immediately reveals the attack. Stefan Lucks > told me they might be able to obfuscate the postscript code, > but again this will only fool the superficial auditor. Yes, this is all true, but it's kind of orthogonal to my point, which is that if you're willing to execute a program, this attack can be mounted *without* the ability to produce hash collisions. The fact that so few people regard PS, HTML, Word, etc. as software just makes this point that much sharper. As far as I can tell, the ability fo produce hash collisions just makes the attack marginally worse. -Ekr - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Collisions for hash functions: how to exlain them to your boss
On 6/13/05, Eric Rescorla <[EMAIL PROTECTED]> wrote: > While this is a clever idea, I'm not sure that it means what you imply > it means. The primary thing that makes your attack work is that the > victim is signing a program which he is only able to observe mediated > through his viewer. But once you're willing to do that, you've got a > problem even in the absence of collisions, because it's easy to write > a program which shows different users different content even if you > without hash collisions. You just need to be able to write > conditionals. Well, it's partially true. 1) It is possible to create a program that does exactly the same without the need of collisions 2) A program creating similar effect without the use of collisions must use some external data to make decision. Therefore, it is possible to prove that it may (under some circumstances) behave in a different way. If you have a program that has all the data hard-coded (i.e. static, internal), it will behave provably only in the prescribed way. (Of course some strange 'if' may cause suspicion). That's where the collision comes in. For one version of the PostScript document, it can be proven that it will always display the same thing (no matter what date or what user, provided that it is interpreted with an interpreter compliant to postscript specification). The problem arises when a person believes that by signing the program, it will be the same code (which was proven to do exactly one thing) that matches the signature next time the signature will be checked. Which it won't, because of collisions. You can't accomplish this without use of collisions. 3) There is also a psychical point of view - most people don't know that postscript files are actually code. So are PDFs. Strength of post-script part of language was cut down, but there is javascript, however not many viewers except Adobe reader support it. Other 'code/data' formats are e.g. MS Excel, MS Word, OpenOffice Writer files, in fact almost any complex file format. This is something you can't do on paper (well, except for some tricks like invisible inks that become visible after some time). I've had a talk on this a few months ago with a couple of other cryptographers. The result was that there is no such thing as 'unique representation of document' like it is for a plain old sheet of paper. It depends on viewer application. 4) You don't even need conditionals. For one conference I've created an a pair of Excel spreadsheets that used a simple sum over a couple of fields. I picked Excel, because it is widely known application. Both files had identical md5 hash, but different result. There was no need for scripting. It works like this: you put some believable numbers on the sheet, then create a region colored white letters on white background ;-) You create a collision in the region, so the nonsense numbers are not visible. On the next row, you are 'behind' the collision (in terms of position in the file data stream). So you put anything you want in both files in the next rows, it only has to be the same for both colliding files. So create another region with white on white, put some 'bulgarian constants' (*) in there and put a SUM or some unsuspicious operation as one of the visible items. Now both xls's have the same md5 hash, but each displays something else even without the use of VisualBasic scripts. Sure, you can create white on white document without the use of collisions, but then either a) you have to use scripting with external-data-based conditionals or b) you can't make their hashes equal without use of collisions (*) def. 'bulgarian constant' - a number you add to your result if it doesn't match the expected result :-) 5) Most document formats cannot be viewed without a viewer application (unless you make an effort to decode it by hand, which most people won't or can't). Ondrej Mikle - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Collisions for hash functions: how to exlain them to your boss
Hi Eric, Technically speaking you're correct, they're signing a program. But most people, certainly non-techies like Alice's boss, view postscript (or MS Word, or ) files not as programs but as static data. In being targeted at non-techies I find this attack more convincing than those of Mikle and Kaminsky, though essentially it's a very similar idea. Note that opening the postscript files in an ASCII-editor (or HEX-editor) immediately reveals the attack. Stefan Lucks told me they might be able to obfuscate the postscript code, but again this will only fool the superficial auditor. Grtz, Benne = Technische Universiteit Eindhoven Coding & Crypto Groep Faculteit Wiskunde en Informatica Den Dolech 2 Postbus 513 5600 MB Eindhoven kamer HG 9.84 tel. (040) 247 2704, bgg 5141 e-mail: [EMAIL PROTECTED] www: http://www.win.tue.nl/~bdeweger = > -Original Message- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Eric Rescorla > Sent: maandag 13 juni 2005 17:05 > To: Stefan Lucks > Cc: cryptography@metzdowd.com > Subject: Re: Collisions for hash functions: how to exlain > them to your boss > > Stefan Lucks <[EMAIL PROTECTED]> writes: > > Magnus Daum and myself have generated MD5-collisons for > PostScript files: > > > > http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/ > > > > This work is somewhat similar to the work from Mikle and > Kaminsky, except > > that our colliding files are not executables, but real documents. > > > > We hope to demonstrate how serious hash function collisions > should be > > taken -- even for people without much technical background. > And to help > > you, to explain these issues > > > > - to your boss or your management, > > - to your customers, > > - to your children ... > > While this is a clever idea, I'm not sure that it means what you imply > it means. The primary thing that makes your attack work is that the > victim is signing a program which he is only able to observe mediated > through his viewer. But once you're willing to do that, you've got a > problem even in the absence of collisions, because it's easy to write > a program which shows different users different content even if you > without hash collisions. You just need to be able to write > conditionals. > > For more, including an example, see: > http://www.educatedguesswork.org/movabletype/archives/2005/06/ > md5_collisions.html > > -Ekr > > > > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to > [EMAIL PROTECTED] > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Collisions for hash functions: how to exlain them to your boss
Stefan Lucks <[EMAIL PROTECTED]> writes: > Magnus Daum and myself have generated MD5-collisons for PostScript files: > > http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/ > > This work is somewhat similar to the work from Mikle and Kaminsky, except > that our colliding files are not executables, but real documents. > > We hope to demonstrate how serious hash function collisions should be > taken -- even for people without much technical background. And to help > you, to explain these issues > > - to your boss or your management, > - to your customers, > - to your children ... While this is a clever idea, I'm not sure that it means what you imply it means. The primary thing that makes your attack work is that the victim is signing a program which he is only able to observe mediated through his viewer. But once you're willing to do that, you've got a problem even in the absence of collisions, because it's easy to write a program which shows different users different content even if you without hash collisions. You just need to be able to write conditionals. For more, including an example, see: http://www.educatedguesswork.org/movabletype/archives/2005/06/md5_collisions.html -Ekr - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
