MD5 collisions in PostScript files

| Comments (6) | TrackBacks (60) |
Daum and Lucks demonstration of colliding PostScript files is getting a fair amount of attention. The attack is straightforward. They generate a pair of colliding prefixes A and B and then tack on a common PostScript program P. Because of the way that hash functions work, H(A P) = H(B P) so, now they have two files that collide. The trick here is the PostScript program, which actually contains two entirely separate documents. P then looks at its prefix and displays document 1 if the prefix is A and document 2 if the prefix is B.

Daum and Lucks argue that this shows that the current attacks on MD5 are serious:

Recently, the world of cryptographic hash functions has turned into a mess. A lot of researchers announced algorithms ("attacks") to find collisions for common hash functions such as MD5 and SHA-1 (see [B+, WFLY, WY, WYY-a, WYY-b]). For cryptographers, these results are exciting - but many so-called "practitioners" turned them down as "practically irrelevant". The point is that while it is possible to find colliding messages M and M', these messages appear to be more or less random - or rather, contain a random string of some fixed length (e.g., 1024 bit in the case of MD5). If you cannot exercise control over colliding messages, these collisions are theoretically interesting but harmless, right? In the past few weeks, we have met quite a few people who thought so.

With this page, we want to demonstrate how badly wrong this kind of reasoning is! We hope to provide convincing evidence even for people without much technical or cryptographical background.

Superficially, this a convincing argument, but I don't think it holds up under examination. First, consider the scenario Daum and Lucks envision:

  1. Alice prepares the pair of colliding files.
  2. The signing party views the "innocuous" version in a PostScript viewer. This is a key point because if you look at the source of PostScript file you can see both alternative documents (though of course one could obfuscate this...)
  3. The signing party signs the innocuous document.
  4. Alice transfers the signature to the "bad" version of the file and presents it to the relying party.
  5. The relying party then views the bad version (again in a PostScript viewer) and is fooled.

What makes this all work is that what's being signed is a program and that the victim only sees the program's output and is willing to sign based on that. But if you're willing to do that, you've already got a problem, even without compromise of digest functions. Consider the following document:

This file contains a simple JavaScript function that displays one document fragment if the current month is June and the other fragment if it isn't. The links below let you force the switch:
Click here to change to Not June mode
Click here to change to June mode

This technique lets us mount a simple attack: prepare a document like the one above. Set it to display the innocuous message from days 1-5 and then a less innocuous message after day 5. Get the signing party to sign sometime on day 1. Then on day 6 present it to the relying party. The signing party and the relying party see different things, just as in the Daum and Lucks case.

There are a few obvious objections here. The first is that this is an HTML file, not a PostScript. PostScript does have conditionals, but it doesn't seem to have a Date operator. There is probably some other conditional you could use, but I haven't looked too hard. PDF, however, has support for JavaScript, so you may be able to make it work with PDF. In any case, it's not clear why one would think that people are more willing to sign PostScript than HTML.

Second, this attack isn't quite as elegant as the Daum/Lucks attack. The signing party might decide to look at the file later and notice what had happened. However, a Date is just the simplest kind of conditional. JavaScript is quite powerful, and you should be able to use more sophisticated mechanisms to figure out what to display, e.g., by checking some remote web page. Actually, if you have a network connection, you can mount this kind of attack without having any kind of program on the client: just have the "document" be an inline image linked to in the HTML file the victim signs. You can then make it appear any way you want whenever you want, and even condition the behavior on which computer is doing the asking.

The bottom line here is that you can't safely sign content that you didn't create based purely on the way it appears in some viewing application (this is one of the concerns with XML signatures as well [*]. Daum and Lucks have just found another way to demonstrate this.

60 TrackBacks

Listed below are links to blogs that reference this entry: MD5 collisions in PostScript files.

TrackBack URL for this entry: http://www.educatedguesswork.org/cgi-bin/mt/mt-tb.cgi/296

Online poker from online poker online on July 6, 2005 3:27 PM

I have found the best site to play Online Poker Online Bingo Online Casino Read More

gallery japan bondage free bondage free bondage clip rope bondage tricks how to bondage oral pics bondage photo galleries breast bondage technique wet bondage stories classy bondage women bondage fairies cute mohair sweater bondage stories rope bondag... Read More

fixed loan from fixed loan on August 1, 2005 10:29 AM

fixed loan Read More

cazino Read More

cazino from super casino on August 2, 2005 8:46 AM

super casino Read More

2005 BMW 5-Series Review from 2005 BMW 5-Series Review on August 3, 2005 3:36 PM

All models have BMW’s iDrive, which uses a console “joystick” knob to control entertainment, navigation, communication, and climate functions. Read More

2005 Mercedes-Benz E-Class Review from 2005 Mercedes-Benz E-Class Review on August 3, 2005 4:05 PM

Front and rear side airbags, head-protecting curtain side airbags, and Mercedes’ TeleAid assistance are standard. Read More

web roulette from web roulette on August 3, 2005 7:30 PM

web roulette Read More

2005 Pontiac Grand Prix Review from 2005 Pontiac Grand Prix Review on August 4, 2005 3:58 PM

The 3.8-liter V6 in the Grand Prix is normally aspirated in the base and GT models but supercharged in the GTP. Read More

wagering odds from wagering odds on August 6, 2005 1:52 AM

wagering odds Read More

Usher from Yet another Usher Blog on August 6, 2005 8:13 AM

... Read More

2005 Ford Focus Review from 2005 Ford Focus Review on August 7, 2005 3:46 AM

For the 2005 model year, the Focus received a minor styling makeover, inside and out, giving it a slightly more subdued, mature look. Read More

2005 Volkswagen Jetta Review from 2005 Volkswagen Jetta Review on August 7, 2005 5:12 AM

The Jetta’s structure underneath has also been stiffened up to granite-like levels, with claimed increases of 15%, 35%, and 80% in torsional rigidity, flex rigidity, and static torsional rigidity. Read More

2005 Toyota Corolla Review from 2005 Toyota Corolla Review on August 8, 2005 1:38 PM

The 2005 Toyota Corolla is a 4-door, 5-passenger family sedan, or sports sedan, available in 4 trims, ranging from the CE to the XRS. Read More

2005 Cadillac XLR Review from 2005 Cadillac XLR Review on August 9, 2005 2:53 PM

While the Corvette is still the champion of American high-performance sports cars the XLR is its mighty sophisticated cousin – just the right choice to explore the Gold Coast on a summer day. Read More

2005 Mercedes-Benz C-Class Review from 2005 Mercedes-Benz C-Class Review on August 9, 2005 3:24 PM

All C-Class cars have been freshened with new exterior styling cues for 2005, including wider set quad-ovoid headlights and revised taillights. Read More

2005 Lincoln LS Review from 2005 Lincoln LS Review on August 11, 2005 9:54 PM

The 2005 Lincoln LS comes in five versions this year, built around two engine choices: the V6 Luxury is the base version, followed by the V6 Appearance and Premium models. Read More

2005 Honda Civic Review from 2005 Honda Civic Review on August 11, 2005 10:27 PM

Three specialized Civics are designed specifically to minimize environmental impact and deliver better fuel economy than all but a few cars currently available. Read More

casino Read More

2005 Buick Park Avenue Review from 2005 Buick Park Avenue Review on August 15, 2005 3:09 PM

The four-door 2005 Buick Park Avenue sedan is long and elegant, and both models offer a generous range of standard amenities. Read More

2005 Ford Mustang Review from 2005 Ford Mustang Review on August 15, 2005 4:31 PM

The new Ford Mustang has the signature long hood and short rear deck accompanied by C-scoops in the sides, three-element tail lamps and the galloping horse badge in the center of the grille. Read More

2005 Honda CR-V Review from 2005 Honda CR-V Review on August 16, 2005 1:58 PM

The CR-V isn’t much good off-road, but it’s better than competent on the highways and byways where most SUVs are driven most of the time. Read More

The TL delivers sharp-handling, a powerful V6 engine, a fully independent suspension, and the latest active safety electronics to optimize driving dynamics. Read More

Mitsubishi Eclipse from Mitsubishi Eclipse on August 25, 2005 4:40 PM

The Eclipse Spyder is generally pleasant to drive, thanks to a smooth power delivery and a compliant suspension. Read More

The Hummer H1’s engine is a 6.5-liter turbodiesel V8 with 205 horsepower at 3400 rpm and 440 lb-ft of torque at 1800 rpm. 4-speed electronic automatic transmission is standard. Read More

Mini Cooper from Mini Cooper on August 30, 2005 1:08 PM

The Cooper and Cooper S get new manual gearboxes with revised gearing for improved acceleration, and the S gets a slight bump in power to 168 horsepower. Read More

Dodge Charger from Dodge Charger on August 30, 2005 4:38 PM

Armchair automotive designers seem to forget that the last Charger was a four-cylinder, front-wheel-drive car based on the deplorable Dodge Omni. Read More

ford bronco from ford bronco on August 31, 2005 1:49 AM

It’s our impression that Ford has done a little more upgrading on the Bronco than either Chevrolet or GMC has done with its offerings. Read More

The Mini Cooper gets a few interior enhancements for 2005, including new map lights and cascade lighting located on the center of the top windshield frame and illuminated door handles, all designed to improve night-time interior visibility. Read More

online forex trading from online forex trading on October 15, 2005 12:27 AM

online forex trading I showy landsborough that the Boer unlesse to a treasure-producing salamee broke down old shi Read More

Dog sex artwork pictures from Animal sex pics teen girls on November 4, 2005 8:52 AM

Girls getting fuck by dogs and horses Hardcore animal sex stories Sexy porno movie animal Free site to see animals do... Read More

percocet Read More

some nice babes from babes posing outdoor on November 13, 2005 10:20 AM

xxxx fresh links Read More

spyware and spyware list Read More

Nissan Skyline from Nissan Skyline on November 16, 2005 3:14 PM

Nissan’s new Skyline is one of those few vehicles that we have a hard time not liking. Read More

crazy from from Jhon Miller on November 27, 2005 2:28 PM

o-o-o! Read More

Fruit Baskets Read More

wagering Read More

crazy from from Jhon Miller on November 30, 2005 4:18 PM

It's fantastic review Read More

Beach Chair Read More

crazy from from Jhon Miller on December 4, 2005 6:50 PM

It's fantastic review Read More

crazy from from Jhon Miller on December 5, 2005 6:47 PM

It's fantastic review myster shopper jobs Real Read More

Cell Phone Cases from Cell Phone Cases on December 13, 2005 1:38 AM

Cell Phone Cases Read More

Teen girls being banged free videos from Free sample videos of asian sex on December 20, 2005 6:30 PM

Free mpeg hentai downloads Free sex girls video pic Free hardcore sex clips download Free gay boys xxx video Read More

Disney Vacation from Disney Vacation on December 25, 2005 1:26 PM

Disney Vacation Read More

Free mpg porn passwords from Free video horse clip avi on January 3, 2006 6:24 PM

Nude camping sex Porn clip download Pornvideogranny Parent directory porno Read More

Luxury Caribbean Cruise from Luxury Caribbean Cruise on January 8, 2006 6:04 AM

Luxury Caribbean Cruise Read More

ativan lorazepam from ativan lorazepam on January 16, 2006 1:45 AM

verizon wireless Read More

poker stars search from poker stars search on January 19, 2006 5:19 AM

grating:stringers Cenozoic,mutterers.multiplayer poker web software http://www.openlistings.net/multiplayer-poker-web-software.html Read More

Retirement Planning from Retirement Planning on January 21, 2006 4:40 PM

Retirement Planning Read More

Bad Credit Mortgage Loans from Bad Credit Mortgage Loans on February 11, 2006 11:41 AM

Bad Credit Mortgage Loans Read More

Color Contacts from Color Contacts on February 14, 2006 6:38 PM

Color Contacts Read More

daytona beach Read More

6 Comments

In a sense, this seems like a social attack. Very few of the folks
that used them saw postscript files as programs; they saw them
as device-independent documents and ignored the fact that
it was a complex program that allowed them to be rendered
on multiple platforms. The programming language has primitives
that have nothing obvious to do with display, and that increases
the risk.


It's also terribly easy to obfuscate, since you can
include characters by drawing bitmaps of them; you
could design your postscript program so that viewing
the source would tell you nothing. For a long time,
the only way to get CJK characters in postscript was
by bitmapping them, so there are quite a few programs
out there that will help you create bitmaps (even of
non-CJK characters).


So the next thing to do is to think of other programming
languages that the public thinks of as device-independent
viewers. The public treats "the web" as device-indepent
viewing medium (at least largely), so pretty much any
of the client side technologies fit this suit.


Maybe we need an MD5 of intent: does this MD5
map to what I intend it to? (or, as relying party) can I check
the intent using this MD5?


There must be a URI scheme for this somewhere....


This sounds like another reason why document-as-program is harmful from a security point of view, and unlike most such problems it can't be fixed by better sandboxing.

All this trouble because of the word "signature." Digital signatures are nothing like real world document signatures, and it seems this "attack" goes away if the distinction is made.

As I recall the XML-Signature guys had the same problems with specifying how to sign XML docs because they could render in and number of different ways depending on context. Haven;t dug into the specs in a while, but there was a serious movement for a while to include and sign a bitmap version of the rendered document.

This is more of the same confusion. Signature in a legal sense should arise from a much more complex program context that specifies how to render, display signatures, etc.

Signature algs and hash functions have as much to do with signing as the properties of ink have on real world signatures.

Your [*] is broken; has an extraneous backslash.

I don't quite agree with Eric on this basic issue, but I'll point out that this attack scenario isn't really applicable to the non-repudiation world, where Alice fools Julius, and then tries to get a court to make him do something he didn't agree to. A serious examination of the source will reveal the attack when we're doing something as simple as conditional execution.

Where this is interesting is when someone views/reviews the data, approves and hashes it, and then some person or program makes a decision based on that hash or signature.

--John

This reminds me of a related issue in source code management: do you sign a (hash of a) patch or a (hash of the) state of the tree after the patch has been applied?

If you trust your software then both seem to be equivalent, but if you don't trust your software I think you are just screwed.

Leave a comment