Birthday attack

[David Howe]

at Friday, October 11, 2002 12:28 PM, Ken Brown <k.brown@ccs.bbk.ac.uk>
was seen to say:

> Of course the files would probably be gibberish...  but then we just
> have to say they are encrypted with a 1-time pad and we can
> make them say anything we want :-)
simpler solution is to give each a unique value in some admin field
(this is obviously more difficult if you want the actual text to differ
in a specific way, but not if you just want proof of concept)

The entire possible keyspace (128 bits) is 16 bytes wide; using a
printable ascii encoding of 7 bits of character (omitting non-printable
characters from a 8 bit ascii font) then that gives 19 characters, all
human readable - pretty long for a "your ref" field in a letter, but
tolerable. Given a sample letter, you could also encode a few bits in an
amount field - say ten bits converted to decimal then expressed in
thousands of pounds. Presumably a letter that has a different amount in
the body text would be more impressive to a judge than one that simply
had a different "your ref" header.

I am trying to think of an efficient way to search the keyspace in
parallel distributed.net fashion but can't. closest solution I could
think of would be for each workstation to generate a number (say 1024)
of documents, calculate the hashes, then upload the resulting block (16
K file) to a server. It could then download other blocks from
workstations with their blocks higher up the keyspace than itself,
compare their blocks to its own, and detect matches that way.