[Cfrg] draft-harkins-pkex-04.txt

[Greg Rose <[e-mail]>]

Here are some comments on the PKEX current draft. I had already sent most of them to Dan Harkins, he asked me to share with CFRG.

At the end of the introduction section, it's worth mentioning that at the end of the process both parties have also derived a usable shared symmetric key "z". It doesn't actually say that!

1.2: "Groups can be either traditional finite field or can be based on elliptic curves." The pedant in me wants to say something like "the multiplicative group of a finite field or ...". From reading ahead I now understand that you only intend it to apply to Mod-P groups, so I would actually say "the multiplicative group of the field of integers modulo an odd prime." Also perhaps "Other groups are possible but MUST NOT be used with this specification.", or maybe I'm overstating the intent. Since there are many possible generators, maybe say "There is a distinguished generator of the group, denoted G. The order of G is q, which MUST itself be a large prime (in all the examples below, q is (P-1)/2)."

I suggest adding to "{a}b[c]" description: "The result of this is a ciphertext that includes authentication information dependent on both a and c, whether c is actually transmitted or is somehow reconstructed. The other side can decrypt a if it knows b and neither {a}b nor c has been altered during transmission, otherwise an error will be flagged."

5: Each party is assumed to know the other's identity in advance; the protocol doesn't reveal the identities.

5.1 it should be stressed that x and y (the ephemeral secret keys) SHALL be generated with high quality (pseudo-)randomness and never re-used.

5.1, maybe clarify "verified to be valid"... for elliptic curves M and N must be valid points (both coordinates) in the group.

5.1, Alice's Q is called Qa, but Bob's is called Qr. I'd prefer it to be called Qb :-). Actually, in the last paragraph of section 5.1, I believe that it IS called Qb (before being deleted).

5.2 at end, they also share "z", a high-quality shared secret that could be used for further key derivation. Is this considered ephemeral or not? In some contexts it might be extremely useful.

Appendix A, regarding validation/generation:
- For elliptic curves, given a randomly generated X coordinate, there will be two possible Y-coordinates (or none). For completeness, should you specify that one of them should be chosen? While it's astronomically unlikely, it is possible that a single byte counter would wrap without ever finding a candidate.

- You write "for FFC it is checked by seeing whether the exponentiation of the candidate to the power of the prime minus one divided by the order, modulo the prime, is one)." I find it unclear what you mean by "divided by the order" here. I guess you must mean "divided by the order of the generator G" as opposed to the group order? In the case of all the primes you use, that means x^((P-1)/2), but you're allowing for the use of other kinds of moduli, like the el-Gamal style, right? Having said all this, I think the clarification should be done up in the Notation section, after the first paragraph. Can I suggest the following words:
"It is important that public and secret keys be validated, that is that they represent valid elements of the group. For elliptic curve groups, a point is valid if the coordinates are both less than the field modulus and they jointly satisfy the curve equation. For a randomly generated X coordinate, there might not be any corresponding Y coordinate, otherwise there will be two; in this case we choose the numerically smaller (mod P) value for the Y coordinate. For Mod-P groups, the generator G usually has a smaller order than the multiplicative group itself. Groups use a generator of order q, where q is some large prime divisor of (P-1). In all the example groups shown, the order of G is q = (P-1)/2. It is important for security that the value X be checked to be in the correct subgroup, 1 < X < P, and X^q = 1 (mod P)."

That's all very well for validation, but if you try using the generation algorithm above with an el-Gamal style group, with a q that's much smaller than p, it'll almost certainly never terminate. Usually this is done by generating the random field element then raising it to the power ((p-1)/q), which will force it to be in the right subgroup (but must check that you didn't end up with 1). This process will unfortunately not generate the same values that you already have (and invalidate all the FFC test vectors :-( ), I don't know how important that might be to you.

Aside: you use the acronyms ECC and FFC extensively but don't define them.

Typos:
Appendix A "an candidate".
Your address: "avenue" should be capitalized.

Those are the comments on the draft as it is proposed. I also want to make an observation that I think makes the scheme more usable, but changes the mathematics and would invalidate the test vectors, at least for the elliptic curve variants.

Public keys are points on the specified curve, with (X,Y) coordinates modulo P, the prime defining the underlying field. “Compact form”, as expressed in RFC 6090, just means transmitting only the X coordinate. The recipient then verifies the received key, in part by calculating a corresponding Y coordinate. For Modulo-P underlying fields, there will be two possible Y coordinates for any valid point (or none if the X coordinate was invalid). As is noted in RFC 6090, the result of scalar multiplication on a compact point depends only on the X coordinate. (Note: this is not generally true for non-Modulo-P fields or other representations, but does apply to the only ones mentioned here.)

Some standards might want to specify the use of compact representation, that is, only the X coordinate is transmitted for the PKEX protocol messages themselves. A corresponding Y coordinate must have been calculated and it can either be saved or recalculated at need. One of the two Y values can be chosen essentially at random. The two possibilities are (X,Y) and (X,-Y), and are group inverses of each other.

Focusing on the first message transmitted, here is the problem:

1.     Both calculate Qa/Qb as Hash(something identifying the party and the shared password) * Pi. These are points on the curve. Both sides will calculate the same points.

2.     Alice calculates X, her ephemeral public key, also a point on the curve.

3.     Alice calculates M as X + Qa, again this is a point on the curve. But in this case, since the operation is point addition and not scalar multiplication, the Y coordinate matters!

4.     Alice transmits M, but in "compact representation", it really only transmits the X coordinate F(M).

5.     Bob receives F(M) (the X coordinate of M) and calculates a corresponding Y coordinate. With probability 0.5 it might choose a different Y coordinate than was calculated in step 3.

6.     Bob calculates X’ = M – Qi. Again, this is actually point addition of the inverse of the point Qi.

If in step 5 Bob chooses the same Y coordinate that Alice calculated, everything is fine. But what if Bob chose the other Y coordinate?
Q-P ≠ -(-P+Q) in general for points P and Q. X’ will not be equal to X. The same logic applies to the next message from Bob to Alice.

It is important for the PKEX protocol as written that the entire point (or a compressed point, which disambiguates between the positive and negative Y values, but this is not the same as compact representation) to be transmitted. The reason for this discrepancy is that appendix C of RFC6090 refers only to scalar multiplication of a point, as is used in ECDH and ECDSA; however PKEX uses addition/subtraction of two different points in its exchange phase, and then it does matter. Note that there is nothing wrong with the draft RFC as written; at no time does it mention compact representation of points, and it is very careful to use the notation F(B) to denote extraction of the X coordinate.

However an alternative is worth considering. With the following change, less information would need to be transmitted, and an elliptic curve point addition could be replaced by a simpler and faster modular addition, while yielding identical security. I believe that with this change, compact representation (well, something equivalent in size anyway) could actually be used in PKEX.

In step (3) above, one could calculate M as F(X) + F(Qa) (mod P), where P is the prime defining the underlying field of the elliptic curve. Now it’s a scalar value taking up the same space as the original F(M), although it will have a different value so the test vectors need to change. In step (6), calculate X’ as M – F(Qa) (mod P). (Similarly for Bob's response message.)

Such a change works for PKEX for either kind of group (since F(.) is the identity function for the multiplicative mod P groups).

Greg.

Phone/Signal:  [phone] 
GPG/PGP:  1081A37C  232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C