John, Burt;
Thanks for the comments. My replies are below.
----------
From: Linn, John[SMTP:jlinn(_at_)rsasecurity(_dot_)com]
Sent: Monday, November 29, 1999 2:34 PM
To: ietf-smime(_at_)imc(_dot_)org
Subject: RE: Working Group Last Call:
draft-ietf-smime-small-subgroup-02.t xt
Sec. 1, 1st para., after 4th line, add "Some possible non-S/MIME usages of
CMS are also considered, though with less emphasis than the cases arising
in
S/MIME." (See also comments re Sec. 2.1.)
Agreed.
Sec. 1.1: Give bounds on xa, xb.
I will add "xa is in the interval [2, (q - 2)]" to the definition of xa.
Similarly for xb.
Sec. 1.2: The case where the order r is a smooth but not necessarily small
number should also be mentioned, as it offers another avenue of attack. In
this case, the attacker needs to know the value ZZ computed from the user.
From the value the attacker can solve for the private key modulo r using
the
Pohlig-Hellman algorithm. However, it's not as practical as the cases
already presented, where information about private key is recovered from
the
*use* of ZZ, rather than ZZ itself, by exhaustive search.
Agreed. How about if I add a new paragraph at the end of the section
stating:
An attack is also possible if Party B has a public key yb of order r where r
factors into small integers but is not necessarily a small integer itself.
In this case, the attacker needs to know the value ZZ computed by Party A.
From this value Party B can solve for Party A's private key modulo r using
the Pohlig-Hellman [PH] algorithm. However, this attack is not as practical
as the cases already presented, where information about the private key is
recovered from the *use* of ZZ, rather than ZZ itself, by exhaustive search.
Sec. 1.2, para. 3: There are q-1 possible values for ZZ in the ordinary
case, not q (assuming 1 \le xa \le q-1).
Actually RFC 2631 requires 2 <=xa <= q-2, so there are only q-3 possible
values.
Sec. 2: Title says "Required," first para. says "should" -- generally it's
not clear from the terminology whether the protections are recommendations
or requirements. (See also Sec. 1, para. 1.) An alternative that avoids
the
use of "required" is to describe situations in which an implementation
"may
be vulnerable" to a small-subgroup attack, and the recommended
countermeasures in such situations.
I guess I am a little bit concerned that using "may be vulnerable" is not
quite descriptive or strong enough. However, I agree that using the word
"required" creates confusion with actual requirements. How about if I say
"situations where protection is necessary"?
Sec. 2.1, para. 3: A recipient mounting a small-subgroup attack will not
necessarily obtain the plaintext, because the recipient's public key is
invalid. However, the attacker might obtain the plaintext from another
recipient (perhaps one with a valid public key also controlled by the
attacker). Moreover, the attacker does not need to know the plaintext to
test whether a key is correct, provided that the plaintext has sufficient
redundancy (e.g., ASCII).
Yes, this paragraph should be more clearly worded. How about:
If the sender's key is static (i.e. static-static Diffie-Hellman is being
used), then protection is required because in this situation a recipient
mounting a small-subgroup attack may be able to obtain the plaintext from
another recipient (perhaps one with a valid public key also controlled by
the recipient) and therefore could obtain information about the private key.
Moreover, the attacker does not need to know the plaintext to test whether a
key is correct, provided that the plaintext has sufficient redundancy (e.g.,
ASCII). This information could then be used to attack other messages
protected with the same static key.
Also, is the static-static case relevant here? The introduction says that
the focus is on the ephemeral-static case as in S/MIME. If the
static-static
case is also relevant, then the introduction should be changed. If the
static-static case is included for completeness, then perhaps the
ephemeral-ephemeral case should be included as well (moving text from Sec.
4
into Sec. 2).
Well, CMS [RFC 2630] requires only ephemeral-static. However, RFC 2631
describes both ephemeral-static and static-static. Thus, it was felt that
the static-static case was also relevant. I will change the introduction to
include this.
Sec. 3.1, last para. (and elsewhere): The statements about patent
coverage,
while helpful to the implementer, when omitted may give an unwarranted
assurance that there is no patent coverage (e.g., in Sec. 3.3), which
would
contradict IETF's policy stated in Sec. 6. I'm not aware of patent
coverage
on Sec. 3.3, but (mindful of Sec. 6) am concerned that the absence of a
patent caveat on only this subsection could appear as actionable guidance.
I agree. How about if I add a sentence following the first paragraph of
Section 3 stating "Implementer's should note that some of the procedures
described in this section may be the subject of patents or pending patents."
On a related point, RSA Laboratories makes no patent claims on the methods
in Sec. 3.4 ("Compatible Cofactor Exponentation") as further described in
reference [KALISKI].
Sec. 3.3, para. 1: An attacker can still find the two "trivial" elements
of
small order, 1 and p-1; the statement about what is prevented should note
this.
I will change the second sentence to "This will prevent an attacker from
being able to find an element (other than 1 and p-1) of small order modulo
p, ... "
In practice, wouldn't it be enough for j to be greater than or equal to
\sqrt(q), since that would meet the security bound for exhaustive search?
(But exhaustive search might not be the only attack?)
As you mentioned in your comment on Section 1.2, if the attacker is able to
get ahold of ZZ then a Pohlig-Hellman attack (or a square-root type of
attack if r is prime) is possible. Thus, I would prefer if we left the
recommendation being j greater than q.
Sec. 3.3, para. 3: In this approach, q is large. It's worth noting that in
DSA, q is limited to 160 bits for performance reasons, but need not be the
case for DH.
I will add your note to the paragraph.
Sec. 3.4 and 3.5: To explain the names, mention that j is the "cofactor",
and that the first method is compatible with ordinary DH in the case that
both parties' public keys are valid. If a party's public key is invalid,
then the resulting ZZ will either be 1 or an element of order q; the small
subgroup elements will either be detected or cancelled. Unlike public key
validation, the methods don't always detect attacks, but detection isn't
needed, just prevention.
Perhaps note the relative costs of key validation vs. cofactor
multiplication (depends on relative size of q vs. j).
Also note that both methods require that the cofactor is relatively prime
to
the order q, i.e., gcd(j,q) = 1.
I will add this information to these sections.
Sec. 4: This section seems somewhat misleading. Sec. 2 already makes it
clear that an ephemeral key is not worth attacking to recover the private
key.
Agreed. I will delete the second sentence of the second paragraph. ("In
this situation a third party attacker could modify the other entity's public
key in order to determine the user's private key (as described in Section
1.2).")
The main problem with the ephmeral-ephemeral case is not small-subgroup
attacks, but the fact that the opponent can substitute a different public
key in an attempt to eavesdrop. But this is to be expected in the basic
ephemeral-ephemeral case, since no authentication of either party is
provided.
This isn't clear to me. For example, if an attacker modified both public
keys to be yb=ya=1 and the parties authenticated each other over a telephone
conversation in which they read out the agreed upon key. Now, they will
both agree on the same key and they will have a certain level of
authentication, but the attacker will be able to eavesdrop. Thus, it is
important that each party's *public key* be authenticated, which is the
point I was trying to make with this section. However, I agree that the
way things are presently worded may be misleading. I will change the first
sentence of the second paragraph to "In some ephemeral-ephemeral key
agreements protection may be required for both entities."
Editorial comments:
Sec. 1, para. 1, line 2: Change "are" to "is".
Agreed.
Sec. 1, para. 4 (and elsewhere): "other party" is vague, recommend
"attacker" as a more specific term
I agree that "other party" isn't a great term. However, I wanted to
emphasize the fact that the attacker was the legitimate other party in the
key agreement, not a third party attacker, which is what the term "attacker"
may imply. Thus, I would prefer to not use "attacker". I am open to other
suggestions though.
Sec. 1.2, para. 3: Suggest "properly formed" instead of "properly
formatted"
(the construction of the key is the issue, not its presentation) -- or
more
generally "valid" vs. "invalid"
Agreed. I will use "valid public key".
Sec. 3.3, para. 1: Suggest a different symbol than "j" to avoid confusion
with notation in Sec. 1.1
Agreed. I will use "k".
Appendix A: Statement about "ASN.1 modules" seems to be a cut-and-paste
error.
Agreed.
Robert.