Subject: Removing Elgamal signatures

From: Werner Koch <[email-masked]>
Date: Sat, 29 Nov 2003 14:14:08 +0100

Hello!

In the light of the recent GnuPG bug, where I accidently used the same
small sized k for signature creation as it is used for encrypting, I'd
very much like to drop the ElGamal signing ability all together from
OpenPGP.  AFAIK, GnuPG is the only implementation with support for
these keys and by now the about 1100 known primary and subkeys should
have been revoked.  Thus there won't be any interoperability problem
anymore.

Type 20 should thus be declared as reserved (historic use) and all
security notes for this type of key removed.

If we can't agree on that, I'd suggest to declare type 20 keys to be
Elgamal sign only - this way a new problem with this algorithm will
at least not affect the encryption use.

  Werner

-- 
Werner Koch                                      <[email-masked]>
The GnuPG Experts                                http://g10code.com
Free Software Foundation Europe                  http://fsfeurope.org

To: [email-masked]
Subject: Removing Elgamal signatures
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
Date: Sat, 29 Nov 2003 14:14:08 +0100
Sender: [email-masked]

Hello!

In the light of the recent GnuPG bug, where I accidently used the same
small sized k for signature creation as it is used for encrypting, I'd
very much like to drop the ElGamal signing ability all together from
OpenPGP.  AFAIK, GnuPG is the only implementation with support for
these keys and by now the about 1100 known primary and subkeys should
have been revoked.  Thus there won't be any interoperability problem
anymore.

Type 20 should thus be declared as reserved (historic use) and all
security notes for this type of key removed.

If we can't agree on that, I'd suggest to declare type 20 keys to be
Elgamal sign only - this way a new problem with this algorithm will
at least not affect the encryption use.

  Werner

-- 
Werner Koch                                      <[email-masked]>
The GnuPG Experts                                http://g10code.com
Free Software Foundation Europe                  http://fsfeurope.org

Date: Mon, 24 Nov 2003 16:50:12 -0500
From: David Shaw <[email-masked]>
To: Christian Kanja <[email-masked]>
Cc: [email-masked]
Subject: Re: Non UTF-8 Text in Message Body
Mail-Followup-To: Christian Kanja <[email-masked]>, [email-masked]
Sender: [email-masked]

The way I read it, "Charset" is little more than a comment.  An
implementation may use the Charset header if it wants to, but on the
recipient side, the other implementation is free to ignore it.

The safe assumption if there is no Charset header should be that the
plaintext is UTF8.

I've cc'd the list, so perhaps someone there will comment as well.

David

> please have a look at felix question - its about the UTF8-handling in
> messages. PGP8 does it "different" and we would be happy about some
> clarification in this topic. what yould you suggest? is it worth to put
> it on the list and if, i would appreciate if you could just forward
> it... ;-).
> 
> thanks a lot,
> best regards,
> christian
> 
> -----Original Message-----
> Sent: Montag, 27. Oktober 2003 18:26
> To: [email-masked]'
> Subject: Non UTF-8 Text in Message Body
> 
> Hi,
> 
> just to clear things up a bit for me:
> Encoding: Is it allowed to encode the message body of a mail in any
> other character set than UTF-8 without using the "Charset" armor header
> key? If I interpret the standard and the current draft correctly, this
> header key MUST be used if text is encoded in any other character set,
> but I think there are some implementations that do not obey this rule...
> Decoding: Is it allowed to assume that an encoded message body is just
> plain ISO-8859-1 if no "Charset" armor header key is present?
> 
> Thanks and best regards,
> Felix Storm,
> Glueck & Kanja Technology AG
> http://www.glueckkanja.com

Subject: Re: private key CFB
Date: Fri, 21 Nov 2003 08:42:34 +0000
From: [email-masked]
To: [email-masked]
CC: [email-masked]
Sender: [email-masked]

> Two beginner questions:
..begets at least one beginner's answer:

#1. CFB shifts == the algorithm's block size.
    Blowfish, 3DES, CAST, & IDEA use 8 byte blocks.
    AES (128, 192, 256) and Twofish use 16 byte blocks.

#2. Given the string-to-key parameters:

    Hash algorithm: 2
    Salt: 0x61f8a7c834124c3a 
    Type: 3 
    Count code: 96
    Encryption algorithm: 9
    Passphrase: 'passphrase'

..the resulting string is (previously posted by Michael Young,
seconded by yours truly):
 0x 53 f2 fd a7 69 7d 0b a6 c0 ee 18 4f 89 db 1d f8 
    14 6c d4 ad 36 1b 8c 4e 63 13 ab 68 75 a7 ad 0b 

Grammatically-challenged, I gave up trying to figure out S2K mechanics
using the draft and eventually found a nice code sample at the link
below. I also gave up trying to improve on the documentation which
actually makes a lot more sense once the code is working. :)

My Python-ized version looks something like:

# Given string 'passphrase', string 'salt', integer 'count' (actual
# "big" count, not the "count code"), and integer keysize (16 for
# CAST, Blowfish, and AES128, 24 for 3DES and AES192, and 32 for
# AES256)
# 'hasher' is a magic MD5 or SHA1 hash machine
# len(x) : "length of x"

pos, run, result = 0, 0, ''
while pos < keysize:
    md = [] # reset message digest "hash context" every run
    done = 0
    for i in range(run): # preloaded 0x00s depending on iteration "run"
        md.append('\x00')
    if count < (len(passphrase) + len(salt)):
        count = len(passphrase) + len(salt)
    while (count - done) > (len(passphrase) + len(salt)):
        if (len(salt) > 0):
            md.append(salt)
        md.append(passphrase)
        done = done + len(passphrase) + len(salt)
    for i in range(len(salt)): # "for (i=0; i++; i<=len(salt))"
        if done < count:
            md.append(salt[i]) # byte index of 'salt'
            done += 1
    for i in range(len(passphrase)):
        if done < count:
            md.append(passphrase[i]) 
            done += 1
    hash = hasher.new(''.join(md)).digest() # list joining quirk
    size = len(hash)
    if (pos + size) > keysize:
        size = keysize - pos
    result = ''.join([result[:pos], hash[0:size]]) # quirk again
    pos += size
    run += 1
return result

Best of luck,
the poiboy

CVS source for Cryptix OpenPGP implementation
(file PGPIteratedAndSaltedS2K.java)
http://anoncvs.cryptix.org/co.php/projects/openpgp/src/cryptix/openpgp/algorithm/PGPIteratedAndSaltedS2K.java?r=1.8

To: IETF-Announce: ;
Cc: [email-masked]
From: [email-masked]
Reply-to: [email-masked]
Subject: I-D ACTION:draft-ietf-openpgp-rfc2440bis-09.txt
Date: Thu, 20 Nov 2003 15:23:53 -0500
Sender: [email-masked]

--NextPart

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the An Open Specification for Pretty Good Privacy Working Group of the IETF.

	Title		: OpenPGP Message Format
	Author(s)	: J. Callas, L. Donnerhacke, H. Finney, R. Thayer
	Filename	: draft-ietf-openpgp-rfc2440bis-09.txt
	Pages		: 71
	Date		: 2003-11-20
	
This document is maintained in order to publish all necessary
information needed to develop interoperable applications based on
the OpenPGP format. It is not a step-by-step cookbook for writing an
application. It describes only the format and methods needed to
read, check, generate, and write conforming packets crossing any
network. It does not deal with storage and implementation questions.
It does, however, discuss implementation issues necessary to avoid
security flaws.
OpenPGP software uses a combination of strong public-key and
symmetric cryptography to provide security services for electronic
communications and data storage.  These services include
confidentiality, key management, authentication, and digital
signatures. This document specifies the message formats used in
OpenPGP.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-09.txt

To remove yourself from the IETF Announcement list, send a message to 
ietf-announce-request with the word unsubscribe in the body of the message.

Internet-Drafts are also available by anonymous FTP. Login with the username
"anonymous" and a password of your e-mail address. After logging in,
type "cd internet-drafts" and then
	"get draft-ietf-openpgp-rfc2440bis-09.txt".

A list of Internet-Drafts directories can be found in
http://www.ietf.org/shadow.html 
or ftp://ftp.ietf.org/ietf/1shadow-sites.txt

Internet-Drafts can also be obtained by e-mail.

Send a message to:
	[email-masked].
In the body type:
	"FILE /internet-drafts/draft-ietf-openpgp-rfc2440bis-09.txt".
	
NOTE:	The mail server at ietf.org can return the document in
	MIME-encoded form by using the "mpack" utility.  To use this
	feature, insert the command "ENCODING mime" before the "FILE"
	command.  To decode the response(s), you will need "munpack" or
	a MIME-compliant mail reader.  Different MIME-compliant mail readers
	exhibit different behavior, especially when dealing with
	"multipart" MIME messages (i.e. documents which have been split
	up into multiple messages), so check your local documentation on
	how to manipulate these messages.

Below is the data which will enable a MIME compliant mail reader
implementation to automatically retrieve the ASCII version of the
Internet-Draft.

--NextPart
Content-Type: Multipart/Alternative; Boundary="OtherAccess"

--OtherAccess
Content-Type: Message/External-body;
	access-type="mail-server";
	server="[email-masked]"

Content-Type: text/plain
Content-ID:	<[email-masked]>

ENCODING mime
FILE /internet-drafts/draft-ietf-openpgp-rfc2440bis-09.txt

--OtherAccess
Content-Type: Message/External-body;
	name="draft-ietf-openpgp-rfc2440bis-09.txt";
	site="ftp.ietf.org";
	access-type="anon-ftp";
	directory="internet-drafts"

Content-Type: text/plain
Content-ID:	<[email-masked]>

--OtherAccess--

--NextPart--

Date: Tue, 18 Nov 2003 09:48:27 -0800
To: [email-masked]
Cc: 
Subject: Re: Shamir's Discrete Logarithm Hash 
From: <[email-masked]>
Sender: [email-masked]

On Mon, 17 Nov 2003 14:32:37 -0800 David Shaw <[email-masked]>
wrote:

[...]

>I don't feel qualified to argue for or against the SDLH in terms
>of
>its security.  I do, however, argue that any new algorithm needs
>more
>than one web page describing it before it should be included in
>OpenPGP.  There just aren't enough "inches of paperwork" yet.
>
>There was a very interesting thread about the SDLH and the Pure
>Crypto
>project on the cryptography mailing list a few months ago.
>http://www.mit.edu:8008/bloom-picayune/crypto/13163

Thanks, was a very interesting thread!

the only potential practical flaw that was mentioned in the thread, was
that by Peter Wayner, in the event that a signer could be tricked into

signing a specially constructed message,

this could easily be avoided by implementing the hash to have the signer
routinely add some 'salt' 
at the end of the message, after a disclaimer line saying:
"this added line is not part of the content of the message but is added
to avoid certain cryptographic attacks."

a similar approach could also be used by adding a line of plaintext to
an rsa encrypted message, and then signing the 
[rsa message + plaintext line ] 
and avoid a Ross Anderson type attack in those instances where the signature
is on an encrypted rsa message itself.

there is a 'proof' of security by Ron Rivest mentioned in the thread,

and while i agree with you, that it is not yet widely tested / studied
enough to be blanketly accepted as 'secure'

still,
perhaps then, it might find a place as  one of those 
'off-the-beaten-path' niceties offered in gnupg,
as a way to verify pcp signed messages using v3 keys

(with the appropriate cautions like,
"warning, hash not yet fully extensively evaluated by cryptographic community",
 etc.)

and then, as it 'does' get off the ground and get used, and evaluated,

then it will either have a vulnerability found,
or found to be a nice hash function of relatively predictable practical
durability,
(as long as the key size is considered 'secure')

anyway,
just a thought for those periods of 'lull-time' on this list ;-)

vedaal

Concerned about your privacy? Follow this link to get
FREE encrypted email: https://www.hushmail.com/?l=2

Free, ultra-private instant messaging with Hush Messenger
https://www.hushmail.com/services.php?subloc=messenger&l=434

Promote security and make money with the Hushmail Affiliate Program: 
https://www.hushmail.com/about.php?subloc=affiliate&l=427

Date: Mon, 17 Nov 2003 17:32:37 -0500
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Shamir's Discrete Logarithm Hash  //  for possible inclusion into open-pgp ?
Mail-Followup-To: [email-masked]
Sender: [email-masked]

On Mon, Nov 10, 2003 at 09:40:52AM -0800, [email-masked] wrote:
> 
> Shamir's Discrete Logarithm Hash was recently implemented by Ralf Senderek
> in a new small crypto program, PCP (Pure Crypto Project)
> 
> (hash description is here:)
> http://senderek.de/SDLH/
> 
> it has been around for a while, was proven to be collision resistant,
>  but hasn't really been implemented before, possibly because of the length
> of time required to sign directly with the rsa key
> 
> now, with faster processors,
> this may be an appropriate hash for e-mail-length messages,
> 
> and, as there are plans for the wider SHA hashes to be introduced,
> maybe it would be worthwhile considering a hash will remain secure as
> long as the keysize is considered secure

Back when NASA was gearing up for the Apollo moon missions, they had a
saying that the rocket wasn't launched until the stack of paperwork to
validate, document, analyze, attack, correct, and prove as much as
possible the correctness of the mission was as tall as the rocket
itself.

I don't feel qualified to argue for or against the SDLH in terms of
its security.  I do, however, argue that any new algorithm needs more
than one web page describing it before it should be included in
OpenPGP.  There just aren't enough "inches of paperwork" yet.

There was a very interesting thread about the SDLH and the Pure Crypto
project on the cryptography mailing list a few months ago.
http://www.mit.edu:8008/bloom-picayune/crypto/13163

David

Date: Mon, 17 Nov 2003 17:00:16 -0500
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: private key CFB
Mail-Followup-To: [email-masked]
Sender: [email-masked]

On Mon, Nov 17, 2003 at 04:04:08PM -0500, Michael Young wrote:

> > That's not what show-session-key is for.  It's for, well, showing
> > session keys ;)
> 
> I think you may have misread my comment as wanting to produce the
> session key that protects a secret key, based on the original
> context.

Given that the original poster was asking about decrypting his secret
key MPIs, I'm uncertain where a discussion of conventionally encrypted
messages came from.  Context is generally important in having a
discussion as it ties together various thoughts about the sunrise,
which was very pretty this morning.  If there is a GnuPG feature you
want, bring it up on one of the GnuPG lists.  I'll confess I'm not too
sure what behavior you are arguing for.

David

Date: Mon, 17 Nov 2003 16:04:08 -0500
From: Michael Young <[email-masked]>
To: [email-masked]
Subject: Re: private key CFB
Sender: [email-masked]

 > Isn't that too short for a 256-bit key?

Indeed, my post included a 128-bit key computation.  (I also
used MD5, rather than SHA1 as asked.)  Sorry about that.

For a 256-bit key, based on SHA1, I get:
     53.f2.fd.a7.69.7d.0b.a6.c0.ee.18.4f.89.db.1d.f8.
     14.6c.d4.ad.36.1b.8c.4e.63.13.ab.68.75.a7.ad.0b.

I also generated a 64k-sized file and tested with "sha1sum",
getting the same first 20 bytes.

 >>Sadly, GnuPG (1.2.2)'s --show-session-key doesn't seem to work on
 >>symmetrically encrypted packets, but it might be easy to tweak.
 >
 >
 > That's not what show-session-key is for.  It's for, well, showing
 > session keys ;)

I think you may have misread my comment as wanting to produce the
session key that protects a secret key, based on the original
context.
I did not. I was talking about a "conventionally encrypted" message,
using a Symmetrically Encrypted Data Packet.  If the S2K doesn't
include an (*optional*) encryption of the session key, then the S2K
computation result *is* the session key; I was simply trying to use
that feature to generate an S2K output to check mine.

I think that the intended purpose of GnuPG's session key feature is
equally applicable here.  If you disagree, I'd be happy to discuss it
in a GnuPG forum.  In any case, it's not an OpenPGP issue.

Date: Mon, 17 Nov 2003 14:03:46 -0500
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: private key CFB
Mail-Followup-To: [email-masked]
Sender: [email-masked]

On Mon, Nov 17, 2003 at 01:03:10PM -0500, Michael Young wrote:

> I made a quick tweak to my implementation (to emit the raw session
> key),
> so there's some chance I've goofed, but I got:
>     1d.43.a2.ec.02.75.db.29.c1.30.d9.a1.24.28.b6.c6.

Isn't that too short for a 256-bit key?

I got BD3511280C74BC56D12E066DF12C5E22E1D9776B068F3A276017D59C39397794

> Sadly, GnuPG (1.2.2)'s --show-session-key doesn't seem to work on
> symmetrically encrypted packets, but it might be easy to tweak.

That's not what show-session-key is for.  It's for, well, showing
session keys ;)

David

Date: Mon, 17 Nov 2003 13:03:10 -0500
From: Michael Young <[email-masked]>
To: [email-masked]
Subject: Re: private key CFB
Sender: [email-masked]

I made a quick tweak to my implementation (to emit the raw session
key),
so there's some chance I've goofed, but I got:
     1d.43.a2.ec.02.75.db.29.c1.30.d9.a1.24.28.b6.c6.

Sadly, GnuPG (1.2.2)'s --show-session-key doesn't seem to work on
symmetrically encrypted packets, but it might be easy to tweak.

Good luck!

Date: Mon, 17 Nov 2003 09:22:18 -0800
From: "Hal Finney" <[email-masked]>
To: [email-masked]
Subject: Re: private key CFB
Sender: [email-masked]

Douglas Maus writes:
> 1. In Private Key packets (tag 5, section 5.5.3), what is the bitsize of the CFB mode used in encrypting the secret MPI? For example, AES256 may be performed in CFB 1bit, CFB 8bit and CFB 128bit (1bit, 1octet, and 1block). Is this noted somewhere in the RFC that I'm missing?

CFB in PGP always uses one block shift widths.  That would be 128 bits for
AES.

> 2. Could someone please help me confirm a key from salt and passphrase?
> keysize of 256 (AES 256 - algorithm 9 in section 9.2)
> Iterated and salted mode (3.7.1.3)
> SHA1 hash (algorithm 2 in section 9.4)
> salt of 0x61f8a7c834124c3a
> coded count 96 (count then 65536)
> passphrase: 'passphrase'
>
> I get
> 0x66913d886546e5e352edaddff30255d26a4f0b969603131df274720b68d78f6f

Sorry, I don't have time to do this.

Hal Finney

Date: Mon, 17 Nov 2003 07:54:26 -0500 (EST)
From: Douglas Maus <[email-masked]>
Reply-To: Douglas Maus <[email-masked]>
To: [email-masked]
Subject: private key CFB
Sender: [email-masked]

Two beginner questions:

1. In Private Key packets (tag 5, section 5.5.3), what is the bitsize of the CFB mode used in encrypting the secret MPI? For example, AES256 may be performed in CFB 1bit, CFB 8bit and CFB 128bit (1bit, 1octet, and 1block). Is this noted somewhere in the RFC that I'm missing?

2. Could someone please help me confirm a key from salt and passphrase?
keysize of 256 (AES 256 - algorithm 9 in section 9.2)
Iterated and salted mode (3.7.1.3)
SHA1 hash (algorithm 2 in section 9.4)
salt of 0x61f8a7c834124c3a
coded count 96 (count then 65536)
passphrase: 'passphrase'

I get
0x66913d886546e5e352edaddff30255d26a4f0b969603131df274720b68d78f6f

(unfortunately this doesn't work in decrypting my MPI)

Thanks,
Douglas Maus

Date: Mon, 10 Nov 2003 11:03:30 -0800
From: "Hal Finney" <[email-masked]>
To: [email-masked]
Subject: Re: Shamir's Discrete Logarithm Hash  //  for possible inclusion into open-pgp ?
Sender: [email-masked]

Vedaal writes:
> Shamir's Discrete Logarithm Hash was recently implemented by Ralf Senderek
> in a new small crypto program, PCP (Pure Crypto Project)
>
> (hash description is here:)
> http://senderek.de/SDLH/

It's security properties are a little unusual, in that the creator of
the hash function can forge collisions.  Senderek has the creator be
the signer, which seems to work OK, but it is still different enough
from traditional hashes that it makes me wonder.

Traditionally, signature security proofs are based on a random oracle
model, while this hash function is like a random oracle with a trap door.
I don't know if there exist security proofs for that arrangement.

> (although it won't work for dh keys ;-(  )

I don't see why it can't.  The hash's RSA modulus has nothing to do
with the signature key.

Hal Finney

Date: Mon, 10 Nov 2003 09:40:52 -0800
To: [email-masked]
Cc: 
Subject: Shamir's Discrete Logarithm Hash  //  for possible inclusion into open-pgp ?
From: <[email-masked]>
Sender: [email-masked]

Shamir's Discrete Logarithm Hash was recently implemented by Ralf Senderek
in a new small crypto program, PCP (Pure Crypto Project)

(hash description is here:)
http://senderek.de/SDLH/

it has been around for a while, was proven to be collision resistant,
 but hasn't really been implemented before, possibly because of the length
of time required to sign directly with the rsa key

now, with faster processors,
this may be an appropriate hash for e-mail-length messages,

and, as there are plans for the wider SHA hashes to be introduced,
maybe it would be worthwhile considering a hash will remain secure as
long as the keysize is considered secure

(although it won't work for dh keys ;-(  )

just a thought,

vedaal

Concerned about your privacy? Follow this link to get
FREE encrypted email: https://www.hushmail.com/?l=2

Free, ultra-private instant messaging with Hush Messenger
https://www.hushmail.com/services.php?subloc=messenger&l=434

Promote security and make money with the Hushmail Affiliate Program: 
https://www.hushmail.com/about.php?subloc=affiliate&l=427

Date: Tue, 04 Nov 2003 14:27:52 -0800
To: Michael Young <[email-masked]>, [email-masked]
From: Trevor Perrin <[email-masked]>
Subject: Re: theory (was Re: Back-signatures proposal)
Sender: [email-masked]

At 12:43 PM 11/4/2003 -0500, Michael Young wrote:
>Content-Transfer-Encoding: 7bit
>
>
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Trevor Perrin wrote [excerpts quoted out of order]:
>...
> > I notice the patent has a signature on it, and I know the USPTO is
> > in the habit of signing pending applications with its own key.
> >
> > I go to a PGP key server and find a key claiming to belong to
> > USPTO. I use it to verify the application.  Since it verifies, I
> > jump to the conclusion that the key belongs to the USPTO.
>
>Yes, you have made a serious error in verifying that key.
>
>You wouldn't do this with a document you received insecurely.  You
>wouldn't do this if you considered the possibility that the USPTO
>site might vend documents signed by others, a perfectly reasonable
>possibility.
>
>You seem to be relying on this preface:
>
> > Suppose I download the patent application from USPTO's site, over a
> > secure link.

Yes, I'm relying on that.

>If you believe that the link is secure, why wouldn't you use it
>to retrieve the USPTO's key?

Agreed, that would be better.

I'm not saying that verifying a document with a key is a *good* way to 
authenticate the key.  I'm just saying it's something a foolish user might do.

Perhaps such a user deserves what he gets.

However, including relevant fingerprints (of the signing key and primary 
key) in every signature makes the above safe, whereas the subkey 
back-signature doesn't, entirely.  It also makes safe the case where 
subkeys are re-used under different primary keys.  Since I think the 
fingerprint solution is also simpler and more efficient, my vote is for that.

But I also agree with David when he says:

"...either of the proposed fixes raises the bar sufficiently to stop casual 
exploitation."

so I'm fine with either approach.

Trevor 

Date: Tue, 04 Nov 2003 12:43:18 -0500
From: Michael Young <[email-masked]>
To: [email-masked]
Subject: Re: theory (was Re: Back-signatures proposal)
Sender: [email-masked]

Trevor Perrin wrote [excerpts quoted out of order]:
...
 > I notice the patent has a signature on it, and I know the USPTO is
 > in the habit of signing pending applications with its own key.
 >
 > I go to a PGP key server and find a key claiming to belong to
 > USPTO. I use it to verify the application.  Since it verifies, I
 > jump to the conclusion that the key belongs to the USPTO.

Yes, you have made a serious error in verifying that key.

You wouldn't do this with a document you received insecurely.  You
wouldn't do this if you considered the possibility that the USPTO
site might vend documents signed by others, a perfectly reasonable
possibility.

You seem to be relying on this preface:

 > Suppose I download the patent application from USPTO's site, over a
 > secure link.

If you believe that the link is secure, why wouldn't you use it
to retrieve the USPTO's key?  [OK, they might not publish their
key this way.  Ask them to do so.  If they won't take that
seriously, why would you trust signatures gathered this way?]

Even this has its risks -- a generic "secure link" (like HTTPS)
doesn't carry the connotations that a key certification does.  But it
seems less likely that an organization would securely publish dubious
keys (particularly ones that refer to themselves) than documents
signed by third parties.  FAR less likely if the key is explicitly
introduced, for example with text to the effect "this is a USPTO
key".

Now, all that said, I'm quite happy with defining a subkey
cross-signature mechanism (and with David Shaw's proposal in
particular).  Let's just not overstate the problem.