Subject: Comments on updated X9.42 draft

From: Russ Housley <[email-masked]>
Date: Thu, 05 Nov 1998 10:54:46 -0500

>Abstract
>
>   This document standardizes one particular Diffie-Hellman variant,
>   based on the ANSI X9.42 standard, developed by the ANSI X9F1 working
>   group. An algorithm for converting the shared secret into an arbi-
>   trary amount of keying material is provided.

I think we need to expand this just a bit.  In particular, some readers may
need to know that D-H is a key agreement algorithm, used by to parties to
agree on a shared secret.  The resulting shared secret is used as a
symmetric cryptographic key.  Further, the D-H variant described requires
the recipient to have a certificate, but the originator may have a static
key pair (with the public key placed in a certificate) or an ephemeral key
pair.

>TODO
>
>   Redo the examples to match the new algorithm for computing K.

When will these be ready?  I would like to go to Working Group Last Call
shortly.

>2.  Overview Of Method
>
>   Diffie-Hellman key agreement requires that both the sender and reci-
>   pient of a message have key pairs. By combining one's private key and
>   the other party's public key, both parties can compute the same
>   shared secret number. This number can then be converted into crypto-
>   graphic keying material. That keying material is typically used as a
>   key encryption key (KEK) to encrypt (wrap) a key (a message encryp-
>   tion key -- MEK) which is in turn used to encrypt the message data.

For alignment of terminology between this document and CMS, please use
key-encryption key and content-encryption key.

>2.1.  Key Agreement
>
>   The first stage of the key agreement process is to compute a shared
>   secret number ZZ (which will be constant for any pair of Diffie-
>   Hellman keys). ZZ is then converted into a shared symmetric key. Note
>   that the symmetric key will be different for each key agreement, due
>   to the introduction of public random components.

I suggest a slight rewording:

The first stage of the key agreement process is to compute a shared secret
number, called ZZ.  When the same originator and recipient public/private
key pairs are used, the same ZZ value will result.  The ZZ value is then
converted into a shared symmetric cryptographic key. When the originator
employs a static private/public key pair, the introduction of public random
values are used to ensure that the resulting symmetric key will be
different for each key agreement.

>
>2.1.1.  Generation of ZZ
>
> [SNIP]
>   where ^ denotes exponentiation
>         ya is party a's public key; ya = g ^ xa (mod p)
>         yb is party b's public key; yb = g ^ xb (mod p)
>         xa is party a's private key
>         xb is party b's private key
>         p is a large prime
>         g is a generator for the integer group specified by p.

Please expand this list to include q as defined in X9.42.  I realize that
it does not directly impact the equations above, but this seems like the
right place to describe the relationship between p, q, and g.
 
>2.1.2.  Generation of Keying Material
>
> [SNIP]
>   algorithm is the ASN.1 algorithm OID of the symmetric algorithm with which
>     this KEK will be used.
>   counter is a 32 bit number, represented in network byte order.
>   Its initial value is 1, i.e. the byte sequence 00 00 00 01 (hex)
>   pubInfo is a random string provided by the sender. In CMS, it is provided
>   as a parameter in the UserKeyingMaterial field (a 512 bit byte string).

What is "a 512 bit byte string?"  I think you want to say 512 bit value.
>
>   Note that the only source of secret entropy in this computation is
>   ZZ, so the security of this data is limited to the size of ZZ, even
>   if more data than ZZ is generated. However, since pubInfo is dif-
>   ferent for each message, a different KEK will be generated for each
>   message.

Since PubInfo is optional, this paragraph is too strong.  I suggest that
you say that PubInfo must be present if the originator uses a static
public/private key pair.  Further, I suggest that you say that PubInfo may
be present if the originator uses a ephemeral public/private key pair.

>2.1.3.  KEK Computation
>
>   Each key encryption algorithm requires a specific size key (n). The
>   KEK is generated by mapping the left n-most bytes of KM onto the key.
>   Consequently, for a DES [FIPS-46-1] key, which requires 64 bits of
>   keying material, the algorithm is only run once, with a counter value
>   of 1.  The first 64 bits of the output are parity adjusted and con-
>   verted into a DES key.  For 3DES, which requires 192 bits of keying
>   material, the algorithm must be run twice, once with a counter value
>   of 1 (to generate K1', K2', and the first 32 bits of K3') and once
>   with a counter value of 2 (to generate the last 32 bits of K3).
>   K1',K2' and K3' are then parity adjusted to generate the 3 DES keys
>   K1,K2 and K3.

Please address the two key-encryption key algorithms discussed in CMS:
Triple-DES and RC2.  This is in line with the Working Group decisions made
in Chicago.

>2.1.5.  Public Key Validation
>
>   The following algorithm MAY be used to validate received public keys.

I think that we need to require validation at the tie the public key is
placed in a certificate OR at the time the public key is used to compute ZZ.
>
>           1. Verify that y lies within the interval [2,p-1]. If it does not,
>           the key is invalid.
>           2. Compute y^q (mod p). If the result == 1, the key is valid.
>           Otherwise the key is invalid.

There seems to be an alternative check that can be performed.  Since we do
not know what is actually claimed in the Certicom pending patent, secure
alternatives seem to be a good idea.  The alternative is:  verify that Y ^
[(p-1) / q] is not congruent to 0, 1, or g.

>   The primary purpose of public key validation is to prevent a small
>   subgroup attack [REFERENCE?] on the sender's key pair. If Ephemeral-
>   Static mode is used, this check is unnecessary. Note that this pro-
>   cedure may be subject to pending patents.

I suggest that you break this into two paragraphs.  Make the patent
statement a separant paragraph.

Also, there seem to be cases where the recipient is an automated responder
(perhaps a timestamp service) that have concerns with a small subgroup
attack too.  Any time that the attacker can determine the success/failure
of the key generation there seems to be an issue.

Enjoy,
  Russ

---

From: Russ Housley <[email-masked]>
Date: Mon, 09 Nov 1998 15:26:59 -0500

Robert:

A reply to your few comments on my document comments.

>Actually, I don't think that in a store and forward environment and
>using ephemeral-static DH, public-key validation is necessarily
>required.  Let us first consider the situation from the point of view of
>the sender.  In this situation, the sender is combining his ephemeral
>private key with the receiver's certified public key.  Because the
>receiver's public key is certified, it could not have been changed by a
>third party attacker, so the only entity that could possibly be
>performing a "small-subgroup" type of attack is the receiver.  However,
>the sender should not be concerned about this situation.  The sender
>will be agreeing on a secret key with the receiver anyway, so the
>receiver will get access to the encrypted information.  Whether or not
>the receiver also gets access to the sender's private key does not
>matter (because the key is ephemeral).

We agree that there is not an issue with the originator.

>Now let us consider the receiver.  In this situation, the receiver is
>combining it's static private key with the uncertified public key of the
>sender.  Because the public key is uncertified, it could have been
>modified by an attacker, so the threat of a "small-subgroup" type of
>attack is real.  However, because this is a store and forward
>environment, it is possible that the receiver might not respond to the
>sender if the message does not properly decrypt and the receiver
>probably won't use the shared key for any further communications.  Since
>the success of the "small-subgroup" attacks relies on the attacker being
>able to obtain information about when the decryption was successful or
>obtaining a message encrypted with the "bogus" shared key, this attack
>would not be applicable.

If the recipient is an authomated service, such as a time stamp agent or a
mail list agent, the attacker may be able to tell whether or not the
recipient could generate the shared secret allowing proper decryption.  If
the attacker can tell, then the attack seems to be a real concern.

>True.  But in cases where the attacker cannot determine the
>success/failure of the key generation this isn't an issue, and so
>shouldn't be mandated.

How do we tell implementors when this is an issue and when it is not? Do we
put it in security considertions?

Russ

---

From: Robert Zuccherato <[email-masked]>
Date: Tue, 10 Nov 1998 08:13:41 -0500

Russ;

> ----------
> From: 	Russ Housley[SMTP:[email-masked]]
> Sent: 	Monday, November 09, 1998 3:26 PM
> To: 	Robert Zuccherato
> Cc: 	Eric Rescorla; [email-masked]
> Subject: 	RE: Comments on updated X9.42 draft
> 
Agreed.  I'm just concerned with mandating other users, who will not be
responding to messages that don't decrypt properly, to use this
technique.

> put it in security considertions?
That would be my preference.  I don't see why we couldn't describe when
these attacks are a concern and it is recommended to perform public key
validation.

	Robert.

---

From: Russ Housley <[email-masked]>
Date: Tue, 10 Nov 1998 17:19:14 -0500

Eric & Robert:

Okay. I will settle for a section in security considerations that tells
when the originator and recipient need to perform validation.  Since the
draft still supports Static-Static D-H as well as Ephemeral-Static D-H,
there are times that when each party needs to be concerned.

Robert:

Can you propose some text?

Russ