Looking for Elgamal sign+encrypt key information

[Kurt Fitzner]

>If Mallory can break a 1024-bit encryption key through brute
>force (as opposed to an algorithm-specific weakness), we can
>assume that she can also forge signatures from 1024-bit keys.
>This is the case that you are worried about.  BUT, if she does
>so even once, she introduces into the public record an example
>of a forged 1024-bit signature, and when the actual owner of
>that key is confronted with the fake signature (which would
>likely happen quickly if the signed document was of any importance),
>that owner will know that 1024-bit encryption can be broken and
>would be able to document that fact in public.

Yes, I've seen this argument before.  However, in my opinion, it makes
two errant assumptions: 1) It assumes that the "forgery" will be
discovered soon after it is created.  The whole point of a paper trail
is to leave a documentational record of actions.  Many paper trails,
however, are not fastidiously checked until and unless there are
problems.  The other problem (which is more important in my opinion): 2)
It assumes that the owner of the key will be believed when he or she
announces that it was broken.  Forgers aren't going to wear a sign
saying "I'm a key forger".  They are going to deny forging it, so that
the document appears real.  The whole point of digital signatures is to
add authenticity.  Forged documents are not going to be created on a
whim, they are going to be created when there is a dispute in order to
validate the oposing side's position.  In any dispute, there will be
people who believe both sides.  An example:

John is an employee at a cigarette manufacture; middle management in
advertising.  For a time, he is involved in a scheme perpetuated by
upper management to promote cigarettes in advertisements targetted to
teens and pre-teens.  After a certain length of time, his concience
causes him to go to government and civil anti-smoking groups.  A huge
lawsuit forms from this.  Part of the evidence is a 1024-bit-key signed
and dated document trail organizing the campaign, and these documents
cite upper-management as the source of authority and show that they were
CCed to upper management.  This, as you might guess, is a potentially
multi-billion-dollar type lawsuit.  These type of lawsuits are also
often many years in the making before they actually go to trial.

The cigarette manufacturer has the financial incentive to crack that
key.  During the ensuing court battle, John produces these documents
that are dated back to the time when he was an employee, and uses them
to show that upper management knew and directed the campaign.  The
defending cigarette manufacturer produces a different set of documents -
a paper trail that is identical to that shown by John, but that omits
any reference to upper-management's authority and omits references to
them being CCed to upper management.  The defense makes the argument
that he did the initiative on his own in order to increase sales and
obtain larger personal comissions, and when it was discovered by
upper-management, he was fired and then made up the story that the whole
affair was ordered by, and done with the knowledge of upper-management.

We now have two conflicting sets of documents.  Both apparently signed
by the same key.  Part of a large court battle.  Is the world in general
going to believe that the cigarette manufacturer cracked John's 1024-bit
key?  Or is the world going to believe that John is trying to cash in on
the anti-cigarette-manufacturer sentiment after having been caught in an
ilicit campaign to increase his own fortunes.

What I know, is that business and government has a large mass.  And a
controversy where there is a very plausible explanation just might not
have the inertia necessary to cause a global awakening and make people
use larger keys.  Especially if the public in general is convinced by
the cigarette manufacturer's spin doctors.  Oh, 1024-bit keys are
secure.  This was just a guy who got caught with his hands in the cookie
jar.  No need to panic.

The point is, if 1024-bit keys are not strong enough to trust with your
important encryption, they are not strong enough for your important
signatures.  For any signatures.  Who knows when and where a false
document will pop up, and who knows who will believe it is false.