Subject: Fixing the secret keys, and a small apology

From: Jon Callas <[email-masked]>
Date: Tue, 4 Sep 2001 14:28:50 -0700

I screwed up the footers on the last draft, saying 2000 where it should
have said 2001 or 2002. Sorry.

Now then, one of the remaining things really on our agenda is to discuss
fixing the secret key format.

There are a few options for a solution we've discussed:

* Change the secret key version number and add in a check. The plus here is
that it causes the fewest visible changes. The downside is that it causes
skew between the public and private versions, and is going to create
problems and confusion down the road. Enough people expressed disgust at
this that I don't think it needs to be discussed further.

* Change the entire public key version number to 5, and add in a check.
This is the "right" way to the above. From a standards point of view, this
is the most correct way to solve it. However, the downside is that it will
force a lot of client software to have to be revised (nigh unto all of it).
Secret key packets typically do not wander further from the disk than main
memory, and it would be a pity to force everyone to upgrade software
everywhere for this. Lots of people just won't. (See my previous note ECC.)
I'm probably one of them, too. I am reminded of the aphorism that in
theory, theory is the same as practice, but in practice, this turns out not
to be the case. While this may be the best solution from a standards point
of view, it is arguably the worst one from a practical point of view.

* Change the String-to-Key specifier. The solution here is adding in the
tag 254 to 3.7.2.1 and have 254 denote an improved S2K. The benefit here is
that it causes the least change to user software, and is as secure as
anything else. The downside is that if someone uses a cipher algorithm
there, then they can't use algorithm 254. However, not only is using a
cipher algorithm deprecated, but our present max cipher number is 10. I
can't get too upset about this, myself, and it appears this is the best
solution.

Comments?

	Jon

---

From: "Michael Young" <[email-masked]>
Date: Tue, 4 Sep 2001 21:20:39 -0400

-----BEGIN PGP SIGNED MESSAGE-----

From: "Jon Callas" <[email-masked]>
> tag 254 to 3.7.2.1 and have 254 denote an improved S2K.

I concur with Jon's analysis and conclusion (favoring a new pre-S2K tag).

[It really has nothing to do with the S2K, though... it's the "pre-S2K"
byte, and it simply says that the encrypted data (that *follows* the S2K)
includes an MDC.  But I'll accept it whatever wording is used. :-]

---

From: "Michael Young" <[email-masked]>
Date: Tue, 4 Sep 2001 21:54:06 -0400

-----BEGIN PGP SIGNED MESSAGE-----

> fixing the secret key format.

Can I get something added to the agenda?

Last week, I asked how certificate revocation was supposed to work in
the presence of multiple certificates for the same key/userId (or
key/subkey or just key) material.  I don't buy the argument that the
spec shouldn't cover semantics here -- I don't care if the spec says
how an implementation should treat a revocation, but I think it's
critical that the sender and receiver agree on what is being revoked.

My proposal was to add a signature subpacket to contain the hash
algorithm and value from the certificate being revoked.  Old
implementations should ignore it (unless the sender marks it critical,
in which case they should ignore the revocation itself).  New
implementations can use it to positively identify the original.

Does this sound reasonable?  If not, do you disagree with the premise
that identification is useful?  Or, do you dislike the form of the ID?

(Plus, in doing so, the spec can remain silent on the meaning of
duplicate certificates.  I favor adding a "most recent prevails"
recommendation, but if I can revoke *specific* older ones to make
my intention clear, I don't need to depend on any other rules.)

---

From: Florian Weimer <[email-masked]>
Date: 05 Sep 2001 14:57:31 +0200

> * Change the entire public key version number to 5, and add in a check.

I think V5 should be started only if a few other adjustments are made,
too.  The certificate-does-not-cover-key-expiration-time problem comes
to my mind here. ;-)

> tag 254 to 3.7.2.1

and reserve 254 (and 255) in 9.2 for this kind of use.

> and have 254 denote an improved S2K. The benefit here is
> cipher algorithm deprecated, but our present max cipher number is 10.

This is not quite correct, the numbers 100 to 110 are already
assigned, too, technically speaking.  However, 254 was never an
official private/experimental symmetric algorithm identifier, so I
don't think we have to care about potential problems caused by using
254 at this particular place, especially since using symmetric
algorithm specifiers in this context is deprecated anyway.

-- 
Florian Weimer 	                  [email-masked]
University of Stuttgart           http://cert.uni-stuttgart.de/
RUS-CERT                          +49-711-685-5973/fax +49-711-685-5898

---

From: Werner Koch <[email-masked]>
Date: 05 Sep 2001 09:43:30 +0200

> tag 254 to 3.7.2.1 and have 254 denote an improved S2K. The benefit here is

This is fine with me.

Another question is the format.  Should we include only the public
parameters or more stuff in the MDC?  A solution I would like to see
is to just hash the fingerprint of the key along with the secret
parameters.  I predict that in future, implementations will use the
fingerprint to identify a key (and not just the keyID) and therefore
it is steadily available.

Implementations wouldn't have to worry about the public key parameters
when unprotecting the secret parameters of a secret key.  One might
think of putting the secet parameters on a hardware token and there
might be not enough space to store the public parameters - the
fingerprint and the secret parameters should be enough to put on a
(memory only) token.

> cipher algorithm deprecated, but our present max cipher number is 10. I

Given that we assigned 100-110 for experimental algorithms it is
unlikely that higher algorithms identifiers are ever used. 

   Werner

-- 
Werner Koch        Omnis enim res, quae dando non deficit, dum habetur
g10 Code GmbH      et non datur, nondum habetur, quomodo habenda est.
Privacy Solutions                                        -- Augustinus

---

From: "Michael Young" <[email-masked]>
Date: Wed, 5 Sep 2001 11:48:44 -0400

-----BEGIN PGP SIGNED MESSAGE-----

From: "Florian Weimer" <[email-masked]>
> assigned, too, technically speaking.  However, 254 was never an

But, as Jon pointed out, any use of a cipher algorithm number
here is deprecated.  In fact, the String-to-Key section has
the following commentary already.  Note the explicit mention of IDEA.

[2440bis-03, section 3.7.2.1]:
>    This last possibility, the cipher algorithm number with an implicit
>    use of MD5 and IDEA, is provided for backward compatibility; it MAY
>    be understood, but SHOULD NOT be generated, and is deprecated.

I'd be perfectly happy strengthening this to "MUST NOT be generated
for algorithms outside the ranges 1-10 and 100-110" (or just IDEA).

---

From: "Michael Young" <[email-masked]>
Date: Wed, 5 Sep 2001 13:55:02 -0400

-----BEGIN PGP SIGNED MESSAGE-----

From: "Werner Koch" <[email-masked]>
> is to just hash the fingerprint of the key along with the secret

I prefer hashing the full packet (v4-style, even for any v3 packets
that use an MDC), but I could live with hashing the fingerprint.  Old
v3 fingerprints are slightly flawed (in that they don't hash the MPI
sizes), but I suppose an exploit does seem unlikely here.  Hashing
the whole thing just feels more consistent.

> might be not enough space to store the public parameters - the

But this wouldn't be an OpenPGP format.  The OpenPGP secret key packet
includes the public key material.  Of course, an implementation can
use its own internal key storage format (and associated protection).
When such a hardware-token transformation cuts off the public key
parameters, it can cut off the MDC (and add a new one if it sees fit).
The spec need only deal with transmission among OpenPGP implementations.

Personally, I find it unlikely that an implementation would cut off
the public key parameters at all.  It would have to do so very
selectively, as many of them are necessary for private key operations
as well.  It also seems to me that you'd want the card to be able to
verify past results from its own key, in which case it might want the
public parts.  Lastly, it seems wise to perform consistency checks
between the public/private parts even in the presence of an MDC.

---

From: Werner Koch <[email-masked]>
Date: 05 Sep 2001 21:50:27 +0200

> But this wouldn't be an OpenPGP format.  The OpenPGP secret key packet

Right. It is an implementation detail which would help to avoid
unprotecting and re-protecting when transferring keys.

> the public key parameters at all.  It would have to do so very

I know devices which do not have enough storage capacity for all
parameters. 

> between the public/private parts even in the presence of an MDC.

I don't see a reason for this, if the MDC would not provide a sound
consistency check, what else would do?

   Werner

---

From: Jon Callas <[email-masked]>
Date: Thu, 6 Sep 2001 12:02:47 -0700

>it is steadily available.

As a couple people noted, I was probably too glib. The byte isn't actually
part of the S2K, it's a marker that says that an S2K follows.

I think that 254 would denote that we have an S2K and a hash. Let's not
call it an MDC, because we're going to get confused if we do. The questions
I see are:

Hash of what?

Is it inside or outside the envelope?

Where is it placed?

Are there any developers that want to come up with a design?

	Jon

---

From: Jon Callas <[email-masked]>
Date: Thu, 6 Sep 2001 12:06:49 -0700

Are there any comments on Michael's suggestion?

Here's a sketch design:

A signature subpacket called "revocation target" that contains a 1-octet
PKalg, a 1-octet hash algorithm, and then a hash body. It denotes that a
revocation signature is intended to revoke the signature so specified.

Comments?

	Jon

---

From: David Shaw <[email-masked]>
Date: Thu, 6 Sep 2001 15:46:24 -0400

> revocation signature is intended to revoke the signature so specified.

Is it worth adding the timestamp from the original signature to help
find it without having to look at the (larger) hashes?  On a uid with
many signatures, this could speed things up.  Once found, of course,
the hash could then be checked for confirmation.

David

-- 
David Shaw          |  Technical Lead
<[email-masked]>  |  Enterprise Content Delivery
617-250-3028        |  Akamai Technologies

---

From: "Michael Young" <[email-masked]>
Date: Thu, 6 Sep 2001 17:06:48 -0400

-----BEGIN PGP SIGNED MESSAGE-----

> revocation signature is intended to revoke the signature so specified.

Sounds good.  I didn't have the PK algorithm in my original proposal.
I don't feel a need for it, but I don't mind having it there, either.

From: "David Shaw" <[email-masked]>
> the hash could then be checked for confirmation.

I don't mind having the timestamp there, but I don't feel a need for
it, either.  While I feel a need for this subpacket, at the same time,
I expect this situation to be rare, and there are other ways to
control the cost:

  Note that this disambiguation is necessary only for signatures within
  the same context (key, key/user, key/subkey) and made by the *same
  creator*.

  Although the current packet ordering rules don't address certificate
  revocation, I'd suggest that a prudent ordering would put each after
  its target.  This would an even stronger hint.  I note that neither
  PGP6.5 nor GnuPG produces this ordering.  At first glance, it appears
  that they use order of arrival.  [Just the same, would anyone object
  to suggesting this ordering in section 10?]

  I expect many implementations will cache certificate verifications and
  revocation results upon receipt/incorporation, rather than doing them
  every time.

  An implementation that doesn't cache will have to compute the hash
  before using the PK algorithm to verify the original anyway.  Since
  the PK verification is (relatively) expensive, it makes sense to look
  for any revocations first.  A failing 20ish-byte hash match won't take
  longer than an (unaligned big-endian) 4-byte time match (and may fall
  out sooner); a successful match would require the 20ish-byte test anyway.
  If there's a match, the revocation certificate gets tested instead
  (and, assuming it verifies, the original verification can be skipped).

But as I said up front, I don't object strongly to having it.

---

From: Jon Callas <[email-masked]>
Date: Thu, 6 Sep 2001 14:33:10 -0700

>the hash could then be checked for confirmation.

My comments:

* The amount of time need to compare bytes is negligible compared to the
time needed to compare signatures. Byte compares are in the nanosecond to
microsecond range, and doing a signature check is in milliseconds. In
microsecond-land, a millisecond is a coffee break. In nanosecond-land, a
millisecond is an American (but not European) vacation.

* It's actually more likely to slow things down. Remember that hashes are
completely uncorrelated. So the first time I compare a byte, there's a
1/256 chance that they match, yet this is not the hash I'm looking for. For
ones that match the first byte, there's a 1/256 chance of a collision on
the second byte, and so on. In an optimal implementation that compares
bus-width quantities, (like 32, 64, or 128 bits), I'll almost never have a
collision beyond the first compare. Adding in the timestamp just gives me
more things to compare, things it is easier to have collisions on, and
therefore slows the process down.

* Having said all that, there's no good reason *not* to put the timestamp
in. The whole reason for having this is as a disambiguator, and why have a
disambiguator that isn't pretty darned specific, eh?

Now then, a question for implementors: If this gets put in, would you
implement it? "Yes, but not right away" is a fine answer, as are "Yes" and
"No."

	Jon

---

From: Jon Callas <[email-masked]>
Date: Thu, 6 Sep 2001 14:38:46 -0700

>  to suggesting this ordering in section 10?]

Yes. A change to the standard that requires all the implementations to
change is not desirable. I don't see what good it does for them other than,
"You'll thank me for this later." Telling them how to write their programs
adds complexity, and complexity lessens security.

	Jon

---

From: "Michael Young" <[email-masked]>
Date: Thu, 6 Sep 2001 22:51:48 -0400

-----BEGIN PGP SIGNED MESSAGE-----

> adds complexity, and complexity lessens security.

I didn't intend to *require* any ordering, only to *suggest* one,
and only for interchange.

Your principle would argue for eliminating all of the ordering rules.
Why should userIDs precede subkeys?  (For that matter, why should
signatures have to follow the key/userid/subkey to which they
refer -- an implementation *could* always try them all :-).  Ordering
helps receivers match things up.

All that said, I'll retract my suggestion.  It was just a hint,
but as we both noted, matching using the hash is pretty
straightforward, and is dwarfed by the PK verification
anyway.  Sorry for the excursion.

---

From: Werner Koch <[email-masked]>
Date: 07 Sep 2001 08:13:38 +0200

> implement it? "Yes, but not right away" is a fine answer, as are "Yes" and

No. 

I don't see a reason for the revocation target specifiers.  The only
sound handling of self-signature revocations (and that's what we are
talking about) is to use the latest valid self-signature, be it a
revocation or a real self-signature.  All other ways makes the
protocol more complex and ambiguous and is error prone.  Checking the
timestamps of valid revocations and self-signatures is sufficient in
about all cases.  There are only 2 problems I can identify with this:

  * 2 signatures done in the same second. 

Solution:  Don't do this and if you receive one, choose one of them
by whatever means.

  * Sequence of packets messed up. 

This should not happen, but if it does there is the same chance that
the UIDs or subkeys and their self-signatures are out of order and so
one would need to specify the UID in the self-signature.  Solution:
Either drop these packets because they don't comply to OpenPGP or
reorder them which might take a couple milliseconds.  From experience
I know that the reordering is only rarely needed and in most cases due
to buggy keyserver implementations.

  Werner

---

From: "Michael Young" <[email-masked]>
Date: Fri, 7 Sep 2001 17:27:52 -0400

-----BEGIN PGP SIGNED MESSAGE-----

> talking about) is to use the latest valid self-signature, be it a

If "most recent prevails" is the only sound handling, and you
want senders to depend on that, then the specification should say so.
There was some resistance to this, though.

Are multiple certifications illegal?  (If so, the spec should
recommend against doing so.)  I can see a couple of reasons
that I might want to sign the same key/name pair multiple
times:
    different types (generic, persona, etc.), possibly with
     a specific lifetime associated with each;

    different notation data;

    different trust for separate domains ("regular expressions").

Do you not believe in any of these uses?

>   * Sequence of packets messed up. 

As it stands, the ordering section doesn't say where to put
self-signatures, and it doesn't specify ordering for certificate
revocations, so there is no way for things to be "messed up" within a
given context.  [If a revocation is in the wrong context (e.g., for
userId "joe" instead of userId "bob"), then reordering is not
particularly easy.]  Jon Callas objected to adding an ordering
suggestion.

---

From: Werner Koch <[email-masked]>
Date: 08 Sep 2001 12:07:01 +0200

>      a specific lifetime associated with each;

Better use a different key.

>     different trust for separate domains ("regular expressions").

If you can do a new signatue, you can put the old notation data in as
well. 

> Do you not believe in any of these uses?

Partly.