Collisions for hash functions: how to exlain them to your boss

Ondrej Mikle ondrej.mikle at gmail.com
Mon Jun 13 16:35:28 EDT 2005


On 6/13/05, Eric Rescorla <ekr at rtfm.com> 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 majordomo at metzdowd.com



More information about the cryptography mailing list