Subject: RE: Working Group Last Call: draft-ietf-smime-small-subgroup-02.t xt

From: Robert Zuccherato <[email-masked]>
Date: Wed, 17 Nov 1999 11:16:20 -0500

Russ;

Thanks for the comments.

> ----------
> From: 	Russ Housley[SMTP:[email-masked]]
> Sent: 	Tuesday, November 16, 1999 8:35 PM
> To: 	[email-masked]
> Cc: 	[email-masked]
> Subject: 	Re: Working Group Last Call:
> draft-ietf-smime-small-subgroup-02.txt
> 
> 1.  Section 1.2, 3rd paragraph: Please explain "r<<q".  This is the only 
> use of the "<<" symbol.
> 
I will change "r<<q" to "r is much less than q".  This should be more
explanatory/helpful.

> 2.  Section 2.2, 2nd paragraph: Please explain that any protocol event
> that 
> allows the attacker to conclude that decryption was successful is also 
> relevant.  Such events include replies and returning signed receipts.
> 
How about if I add the following to the 3rd paragraph?  "In particular,
protection is required if any protocol event allows any other party to
conclude that decryption was successful.  Such events include replies and
returning signed receipts."

> 3.  Section 2.2, 3rd paragraph: Please remove the extra space after
> "party".
> 
Okay.

> 4.  Section 4, 4th paragraph: Any integrity protection for the public keys
> 
> (not just signatures), will thwart the attack.  Please expand the text to 
> cover any integrity mechanism.
> 
How about if I change the first sentence to read:  "Protection from these
attacks is not required however if the other party's ephemeral public key
has been authenticated by the other party.  The authentication may be in the
form of a signature, MAC, or any other integrity protection mechanism."

> 5.  Section 7:  Please update the [CMS], [MSG], and [x942] references to 
> point to the RFCs.
> 
Of course.

	Robert.

---

From: "Linn, John" <[email-masked]>
Date: Mon, 29 Nov 1999 14:34:21 -0500

S/MIME WG:

Attached are a set of comments on draft-ietf-smime-small-subgroup-02, which
I've obtained and am relaying from Burt Kaliski of RSA Laboratories.

This is a useful and comprehensive treatment of "small-subgroup" attacks in
the context of S/MIME, and will be good to have as an Informational RFC.

Substantive comments:

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

Sec. 1.1: Give bounds on xa, 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.

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

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.

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

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

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.

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.

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?)

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.

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.

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

Editorial comments:

Sec. 1, para. 1, line 2: Change "are" to "is". 

Sec. 1, para. 4 (and elsewhere): "other party" is vague, recommend
"attacker" as a more specific term

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"

Sec. 3.3, para. 1: Suggest a different symbol than "j" to avoid confusion
with notation in Sec. 1.1

Appendix A: Statement about "ASN.1 modules" seems to be a cut-and-paste
error.

---

From: Robert Zuccherato <[email-masked]>
Date: Tue, 30 Nov 1999 14:23:38 -0500

John, Burt;  

Thanks for the comments.  My replies are below.

> ----------
> From: 	Linn, John[SMTP:[email-masked]]
> Sent: 	Monday, November 29, 1999 2:34 PM
> To: 	[email-masked]
> Subject: 	RE: Working Group Last Call:
> draft-ietf-smime-small-subgroup-02.t xt
> 
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.

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

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

> 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"? 

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

> ephemeral-ephemeral case should be included as well (moving text from Sec.
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.

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

> small order, 1 and p-1; the statement about what is prevented should note
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, ... "

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

> DSA, q is limited to 160 bits for performance reasons, but need not be the
I will add your note to the paragraph.

> the order q, i.e., gcd(j,q) = 1.
I will add this information to these sections. 

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

> Sec. 1, para. 1, line 2: Change "are" to "is". 
Agreed.

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

> generally "valid" vs. "invalid"
Agreed.  I will use "valid public key".

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

	Robert.