Russ;
A few comments on your comments.
----------
From: Russ Housley[SMTP:housley(_at_)spyrus(_dot_)com]
Sent: Thursday, November 05, 1998 10:54 AM
To: Eric Rescorla
Cc: ietf-smime(_at_)imc(_dot_)org
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.