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.