Subject: processing of "speculative" key ids: MAY -> SHOULD|MUST

From: [email-masked]
Date: Thu, 20 Jan 2000 00:56:26 +0900

in section 5.1 i see:

   An implementation MAY accept or use a Key ID of zero as a "wild card"
   or "speculative" Key ID. In this case, the receiving implementation
   would try all available private keys, checking for a valid decrypted
   session key. This format helps reduce traffic analysis of messages.

i think the use of MAY here seriously undermines the usefulness of the
"speculative" key id.  i think it would be better if implementations
SHOULD (or even better MUST) process "speculative" key ids.

gnupg supports generation and processing, but since pgp doesn't seem
to handle processing (please correct me if i'm wrong on this point),
speculative key ids are not very useful when conversing w/ folks using
pgp.

to any active developers of pgp: please add at least processing of
speculative ids to pgp!  it shouldn't be hard at all.  it could even
be made a user option.

generation shouldn't be hard either -- it's just a matter of zeroing
some bytes.

p.s. if there are any other implementations of rfc 2440 out there in
use, same comment goes for them too if they don't support the
processing of speculative key ids.

---

From: [email-masked]
Date: Sat, 22 Jan 2000 01:56:38 +0900

w/ permission from "David P. Kemp" <[email-masked]>:

> [email-masked] wrote on Fri, 21 Jan 2000 01:16:05 +0900:
> 
>speculative key ids can be useful in the context of a mailing list
>that has its own keypair plus the public keys of all recipients.  it
>can prevent people from finding out who all of the subscribers are via
>the interception of a single message ...

wolfgang> Clever idea! I had not thought about this type of usage.
wolfgang> 
wolfgang> I admit that in this context, speculative key ids would gain us
wolfgang> something that could not easily be done otherwise.

dpkemp> I'm missing something.  Doesn't a message from a mail list
dpkemp> server to a single recipient contain no information which would
dpkemp> indicate the existence of other recipient(s)?

you may already know the following, but for reference, the way that
encrypting a message (using rfc 2440 methods) to several recipients
works is roughly:

  1) a session key is generated to encrypt the message,

  2) the message is symmetrically encrypted using the session key,

  3) the session key is encrypted using the public keys of the recipients
     and the results of these encryptions are all bundled into the
     final message

by default the keyids of recipients are included in the final package
because they are contained in the public-key-encrypted session keys
(see section 5.1 of the rfc).

this is positive from a performance perspective because it means that
the receiving end does not have to try to decrypt any extra encrypted
session keys -- it only has to try decrypting encrypted session keys
for key ids that it has secret keys for.  if there are a lot of
recipients this can make a significant difference, as has been pointed out
by [email-masked].

it is negative from the perspective of trying to prevent traffic
analysis because the key ids of all recipients are available to anyone
who intercepts the message.

(a classic see-saw case perhaps?)

consider the following (rough) design [2] of a mailing list w/ a key
pair:

  -the public key of each subscriber is available to the list software
   (i'm not fond of suggesting that the public keys can be obtained
   via keyservers but it is a possibility that i heard very recently)

  -messages to the list can be encrypted using the public key of
   the list -- messages can also be signed by subscribers and
   verified by the list if desired using the public keys of the
   subscribers

  -incoming messages are decrypted [1] using the private key of the list,
   then the resulting plain text is encrypted using the method described 
   above using the public keys of the subscribers.  

   the simplest method to implement involves just sending the single
   resulting message body to all recipients -- however, if speculative 
   key ids are not used, the message will contain a key id for each
   recipient.

   so this situation is actually worse than a no-encryption vanilla
   mailing list from an anti-traffic-analysis perspective.  for a
   vanilla mailing list, you typically would not learn this from 
   interception of the message body alone.

   it is possible to split up the single rfc 2440 message into parts, 
   and reassemble as many messages as there are subscribers in such a way
   so that the message sent to each subscriber only contains the
   session-key-encrypted message and the public-key-encrypted session
   key for the subscriber only (thus leaving out all other 
   public-key-encrypted session keys) -- conceptually this is a very
   straight-forward operation.  each subscriber can then be sent a separate
   message.

   note, it is still nice to have speculative key ids at this point so that 
   interception of the message body does not give away the key id of the 
   recipient -- header information can be removed by other mechanisms such 
   as anonymous remailers.

   the message splitting and reassembly would be greatly simplified if 
   there were good, open libraries for manipulating rfc 2440 packets
   (are there any?) or if pgp or gnupg contained the functionality already.  
   it doesn't seem like the splitting and reassembling should require much 
   in terms of processing power as this doesn't involve anything as 
   complicated as encryption/decryption -- it's basically parsing and gluing.
   
   however, making existing arbitrary mailing list software send out a
   different message to each subscriber is not necessarily easy.

p.s. [email-masked], thank you for your reply, i will reply in
     full later.  need to catch up on sleep first!

[1] note that w/ a moderator that can decrypt the list's secret key,
    it is possible to arrange things so that the secret key does not live
    on the server (though this means that if the moderator is not active,
    the list sends out no traffic).

[2] note that this design has appeared in a number of different places,
    including this list, in the past.