Subject: RE: Comments on updated X9.42 draft

From: Robert Zuccherato <[email-masked]>
Date: Thu, 5 Nov 1998 17:34:29 -0500

Russ;

A few comments on your comments.

> ----------
> From: 	Russ Housley[SMTP:[email-masked]]
> Sent: 	Thursday, November 05, 1998 10:54 AM
> To: 	Eric Rescorla
> Cc: 	[email-masked]
> Subject: 	Comments on updated X9.42 draft
> 
> 
> >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.
> 
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).

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.

Because there is a potential patent involved here, I think we should be
careful.  If ephemeral-static DH is used and the receiver will not be
sending back any further information, public key validation is not
required for security.  We probably don't want to require it in these
situations.

> >
> >           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.
> 
Actually, this check is not sufficient.  Let h be a generator of a small
subgroup modulo p.  Assume an attacker can replace the valid public key
ya with h*ya.  Then (h*ya)^[(p-1)/q] (mod p) is not congruent to 0,1 or
g, but it can be used for a "small subgroup" attack. 

> >   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.
> 
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.

	Robert.

---

From: Dr Stephen Henson <[email-masked]>
Date: Fri, 06 Nov 1998 01:03:12 +0000

Just a minor comment. Could an example be included with some "pubInfo"
please? Just to make sure everyone does it right :-)

Steve.
-- 
Dr Stephen N. Henson. UK based freelance Cryptographic Consultant. 
For info see homepage at http://www.drh-consultancy.demon.co.uk/
Email: [email-masked]
PGP key: via homepage.