Subject: [secdir] secdir review for draft-mcgrew-fundamental-ecc-03

From: Tina TSOU <[email-masked]>
Date: Tue, 06 Jul 2010 10:28:54 +0800

Hi,

I have reviewed this document as part of the security directorate's
ongoing effort to review all IETF documents being processed by the IESG.
These comments were written primarily for the benefit of the security
area directors.  Document editors and WG chairs should treat these
comments just like any other comments.

Abstract

1. First sentence: Should >are< rather be >were< ?

Introduction

2. Introduction (p.2): I would insert the word >finite< before >fields<.

3. Introduction (p.4): >ECDH< should be replaced by >Elliptic Curve Diffie-Hellman (ECDH) <.

Mathematical Background

4. Mathematical Background (p.1): Should >is< rather be >are< ? The same holds in Sec.~2.2 (p.1).

5. Sec.~2.2 (p.3): The term >g< is undefined. Hence, >g^N< should be replaced by >a^N<. The same holds for >Note that a^M is equal to g^ (M mod R)< in (p.9).

6. Sec.~2.3 (p.2):  From this description, it appears to me that all elements in Z_p can perform division operation. However, only non-zero elements, namely elements in the set 

Z_p^* = Z_p-{0}

can perform the division operation. Moreover, all the mathematical operations over Z_p are in the sense of mod p. In addition, a prime number p is called the characteristic of a field, if 1+…+1=0 (add p times); in this case F_q contains the prime field F_p, where q=p^n, n>=1. So I think the definition of the F_p lacks precision.

Elliptic Curve Groups

7. Elliptic Curve Groups (p.1): I think the last sentence is too abstract to understand. More precisely, the elliptic curve satisfies the equations,

y^2+cy=x^3+ax+b,

y^2=x^3+ax^2+bx+c,

when the characteristic of the field is 2 and 3, respectively.

       8. Elliptic Curve Groups (p.3): The first sentence says that >when both points are the point at Infinity<. Maybe such statement is not accurate enough due to the fundamental fact that each elliptic curve abelian group has only one infinity, i.e., the identity element.

       9. Sec.~3.1 (p.2): It seems to me that the projection space representation >x=X/Z mod p , y=Y/Z mod p< is a special case of x=X/Z^{c_1} mod p and y=Y/Z^{c_2} mod p when both c_1 and c_2 are equal to 1. If so, should it be clearly explained ?

       10. Sec.~3.3.1: I would simply state the reason for the non-zero discriminant, namely, to ensure that the elliptic curve is chosen to be a non-singular one, i.e., it has no self intersections or cusps.

Elliptic Curve Diffie-Hellman (ECDH)

       11. Elliptic Curve Groups (p.1): >an arbitrary cyclic group<  instead of >an arbitrary mathematical group< ?

Elliptic Curve ElGamal Signatures

       12. Sec.~5.1 (p.1): Insert >Galois< before >field GF(2^w)<.

       13. Sec.~5.3 (p.2): Why not denote the generator >alpha< as >g< for consistency in this draft ?

       14. Sec.~5.3.2 (4): As the symbol >*< denotes the scalar multiplication, why use such a symbol in Sec.~2.2 to represent the addition operation in a group ? Needs to be modified ?

       15. Sec.~5.3.3 (p.1): Insert >the generator g, the group order q< before >the public key Y< in that these two parameters must know in advance before the signature verification procedure.

       16. Sec.~5.3.2 (1): Should >0<s_1<q< be replaced by >s_1 in Z_q< for consistency ? The same holds for >0<s_2<q< and the sentence in Sec.~5.4.3 (1).

       17. Sec.~5.3.2 (3): As mentioned above, the symbol >*< in the equation 

>R'=alpha^{u_1} * Y^{u_2}< represents the addition operation of two points on the elliptic curve; while in >u_2=s_1 * s_2 mod q<, it means the scalar multiplication operation.

       18. Sec.~5.6 (p.2): In the equations >A=m< and >m=-r*z+s*k (mod q)<, does the symbol m represent a message digest ? If so, I think m should be replaced by h(m), although the hash function is not necessary here. If not, it should be transformed to an integer since it has been defined to be a bit string in Sec.~5.2. The same holds for the equation >m*s=-r*s*z+k (mod q)<.

Converting between integers and octet strings

19. the title >Converting between integers and octet strings<, why not >Converting between Integers and Octet Strings< for consistency ? The same goes for other titles and subtitles.

Security Considerations 
       20. Sec.~10.1 (p.3): I think it is necessary to explain the physical meaning of the cofactor and the reason that a number of attacks are possible against ECDH when the cofactor is not equal to 1.

B. R.
Tina
http://tinatsou.weebly.com/contact.html

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Jul 2010 15:58:51 -0700

Hi Tina,

thanks for your comments on the draft.

On Jul 12, 2010, at 5:07 PM, Russ Housley wrote:

> I did not see you as recipients on this note.  Forwarding ...
>
> Russ
>
> - - - - - - - - -
>
> Hi,

Changed.

> Introduction
> 2. Introduction (p.2): I would insert the word >finite< before  
> >fields<.

Changed.

> 3. Introduction (p.4): >ECDH< should be replaced by >Elliptic Curve  

Changed.

> same holds in Sec.~2.2 (p.1).

Changed.

> 5. Sec.~2.2 (p.3): The term >g< is undefined. Hence, >g^N< should be  
> replaced by >a^N<. The same holds for >Note that a^M is equal to g^  
> (M mod R)< in (p.9).

Changed.

> 6. Sec.~2.3 (p.2):  From this description, it appears to me that all  
> elements in Z_p can perform division operation. However, only non- 
> zero elements, namely elements in the set
> Z_p^* = Z_p-{0}
> can perform the division operation. Moreover, all the mathematical  
> operations over Z_p are in the sense of mod p. In addition, a prime  
> number p is called the characteristic of a field, if 1+…+1=0 (add p  
> times); in this case F_q contains the prime field F_p, where q=p^n,  
> n>=1. So I think the definition of the F_p lacks precision.

I think this explanation of finite fields is appropriate for this  
note.  It is not intending to be a general introduction to finite  
fields, but instead to provide only the background needed to  
understand the rest of the note.  The statement " When p is a prime  
number, then the set Zp, with the addition, subtraction,  
multiplication and division operations, is a finite field with  
characteristic p" is correct and precise.

I suggest that the section heading be changed from "Finite Fields" to  
"The Finite Field Fp".

> Elliptic Curve Groups
> 7. Elliptic Curve Groups (p.1): I think the last sentence is too  
> abstract to understand. More precisely, the elliptic curve satisfies  
> the equations,
> y^2+cy=x^3+ax+b,
> y^2=x^3+ax^2+bx+c,

I disagree.  If the paragraph is difficult for the non-mathematician  
to understand, I don't think adding more math will help.  Besides, the  
definitions here match [M1985] and [K1987].

>        8. Elliptic Curve Groups (p.3): The first sentence says that  
> >when both points are the point at Infinity<. Maybe such statement  
> is not accurate enough due to the fundamental fact that each  
> elliptic curve abelian group has only one infinity, i.e., the  
> identity element.

I disagree that this needs to be changed; it is clear as it stands.  I  
don't see how it could be made more accurate, since inserting "equal  
to" before "the point at infinity" would be inappropriate in a  
definition about what it means for points to be equal.

>        9. Sec.~3.1 (p.2): It seems to me that the projection space  
> representation >x=X/Z mod p , y=Y/Z mod p< is a special case of x=X/ 
> Z^{c_1} mod p and y=Y/Z^{c_2} mod p when both c_1 and c_2 are equal  
> to 1. If so, should it be clearly explained ?

The exposition in this section matches the reference, which is one of  
the goals of the draft.

>        10. Sec.~3.3.1: I would simply state the reason for the non- 
> zero discriminant, namely, to ensure that the elliptic curve is  
> chosen to be a non-singular one, i.e., it has no self intersections  
> or cusps.

I disagree; the discriminant is not used anywhere in the draft, and is  
only mentioned for consistency of the elliptic curve group  
definition.  Curve parameter generation is out of scope for this  
draft, and so the target audience has no need for the information.	

>        11. Elliptic Curve Groups (p.1): >an arbitrary cyclic group<   
> instead of >an arbitrary mathematical group< ?

Changed; I verified that [M1983] mentions cyclic groups as well.

>        12. Sec.~5.1 (p.1): Insert >Galois< before >field GF(2^w)<.

I added "finite" instead of "Galois" since the latter term is not  
defined in the document.

>        13. Sec.~5.3 (p.2): Why not denote the generator >alpha< as  
> >g< for consistency in this draft ?

In order to closely follow the original references.

>        14. Sec.~5.3.2 (4): As the symbol >*< denotes the scalar  
> multiplication, why use such a symbol in Sec.~2.2 to represent the  
> addition operation in a group ? Needs to be modified ?

The draft uses multiplicative notation throughout for consistency with  
early references; see S 2.2 par 2.

>        15. Sec.~5.3.3 (p.1): Insert >the generator g, the group  
> order q< before >the public key Y< in that these two parameters must  
> know in advance before the signature verification procedure.

Changed.

>        16. Sec.~5.3.2 (1): Should >0<s_1<q< be replaced by >s_1 in  
> Z_q< for consistency ? The same holds for >0<s_2<q< and the sentence  
> in Sec.~5.4.3 (1).

I assume that you mean S 5.3.3..  This change would be wrong because  
it would mistakenly include 0.  Besides, the sentence in the draft  
matches that in the reference [FIPS186].

> >R'=alpha^{u_1} * Y^{u_2}< represents the addition operation of two  
> points on the elliptic curve; while in >u_2=s_1 * s_2 mod q<, it  
> means the scalar multiplication operation.

The draft uses multiplicative notation throughout for consistency.

>        18. Sec.~5.6 (p.2): In the equations >A=m< and >m=-r*z+s*k  
> (mod q)<, does the symbol m represent a message digest ? If so, I  
> think m should be replaced by h(m), although the hash function is  
> not necessary here. If not, it should be transformed to an integer  
> since it has been defined to be a bit string in Sec.~5.2. The same  
> holds for the equation >m*s=-r*s*z+k (mod q)<.

S 5.6 is non-normative rationale, and the equations exactly match the  
references.  The lack of a hash function is already explained: "No  
hash function is shown in the above equations, but as described in  
Section 10.4, a hash function should be applied to the message prior  
to signing in order to prevent existential forgery attacks."

> 19. the title >Converting between integers and octet strings<, why  
> not >Converting between Integers and Octet Strings< for  
> consistency ? The same goes for other titles and subtitles.

Changed.

> Security Considerations
>        20. Sec.~10.1 (p.3): I think it is necessary to explain the  
> physical meaning of the cofactor and the reason that a number of  
> attacks are possible against ECDH when the cofactor is not equal to 1.

The term "cofactor" was introduced after 1994 and thus is not in the  
normative part of the draft. I am unsure of what explanation you think  
would be appropriate, because the definition is straightforward.  I  
disagree that detailed descriptions of the attacks are required in  
this draft.  Parameter generation is declared out of scope, cofactor=1  
is recommended, and references are provided for the attacks  
mentioned.  The intended audience is implementers, not cryptographers  
generating new elliptic curve groups.

Kevin provided a good definition of cofactor suitable for Section 2,  
if we can find a pre-1994 reference:

       in cryptographic applications, the group G typically has only a
       finite number of elements, and the ratio between the number of
       elements in G (denoted by #G) and the number of elements in the
       cyclic subgroup H (denoted by #H) is called the cofactor of H  
in G,
       that is cofactor = #G/#H. Note that the cofactor is always  
greater
       than or equal to 1, and the cofactor is 1 if and only if H = G. A
       fundamental result of group theory is that the cofactor is always
       an integer.

regards,

David

> <Attached Message Part.txt>