Bogus digital signatures, Re: OT: utility account transfer frauds

[Charles Lindsey]

	On Sat, 12 Oct 2002 07:54:46 +0100
	"John R T Brazier" <prunesquallor@proproco.co.uk> said...

> 
> Charles stated:
> 
> > Now the bad guy comes along, and he has to find some other meaningful
> > text that hashes to the same as the original. Worse than that, he
> > has to find some text whose meaning is such as to be useful in
> > embarassing/blackmailing/whatever the victim. That is a hard problem,
> > and the birthday paradox gives you no help at all.
> 
> The convention is that you produce your two texts (one for the punter to
> sign, the other incriminating), and then play with the white space. You swap
> spaces for tabs, and so forth. You can also append extra spaces, add and
> then cancel out format markers, etc. A decent program should be able to
> generate very large numbers of, say, Word documents that are apparently
> identical but have different internal bit patterns (especially if you've got
> 'Track Changes' on, so that deleted material is still actually retained in
> the file). You can rapidly approach the position where you have some text
> with the random bit streams invisibly mixed in. At this point the birthday
> 'paradox' returns to give you aid.

You still have to generate, on average, 2^64 versions of the document.
And at the end, an expert witness who draws attention to the _very_
peculiar contents of the 'Track Changes' part of the Word document could
undo all your good work.

I also noticed today, when checking something else in the PGP format,
that the signature does NOT contain the MD5 hash in the clear (just the
first two bytes of it). The first two bytes are worth 2^16, but that
still means that you have to perform 2^48 full RSA decodings before you
find your match.

Charles H. Lindsey ---------At Home, doing my own thing------------------------
Tel: +44 161 436 6131 Fax: +44 161 436 6133   Web: http://www.cs.man.ac.uk/~chl
Email: chl@clw.cs.man.ac.uk      Snail: 5 Clerewood Ave, CHEADLE, SK8 3JU, U.K.
PGP: 2C15F1A9      Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5