Subject: [Cfrg] Comments on draft-irtf-cfrg-pairing-friendly-curves

From: Watson Ladd <[email-masked]>
Date: Fri, 8 May 2020 14:18:49 -0400

Dear cfrg,

I’ve looked at draft-irtf-cfrg-pairing-friendly-curves and have a few
comments I hope can be addressed before the next version. Cloudflare
has built a number of products and experiments on top of pairing based
curves and would like to see advancement of this draft.  It’s a good
step towards standardization of type III pairings but, to be as useful
as possible for implementors as well as prevent fragmentation, I have
four issues that I think need to be addressed.

One issue that persists is the disconnect between  security levels and
recommendations. At the textual level BLS12-381 is introduced as an
alternative to BN468 at the 128 bit security level, but then the
discussion seems to indicate the security level is really 117 bits. In
practice few people care about  a factor of a thousand difficulty in
breaking, but plenty of people do care about the performance hit of
that bigger base field. It would be nice to have only one
recommendation, and I think it’s pretty clear that BLS12-381 is going
to be much more useful.

This relates to a wider trend that I think I counterproductive: using
single numbers like 128 to denote security levels. What does this
mean?  Naively one might think that the effort to conduct key recovery
on AES-128, find the discrete logarithm of P256 elliptic curves, and
compute the discrete log of a point on the curve from the draft are
the same, since they are all 128 bit security. This is true for
attackers that are only conducting one attack and who have probability
1 of succeeding. Actual attackers have multiple targets and do not
need to have probability 1 of success. For the problem of recovering k
from AES_k(0), each additional target AES_k2(0), AES_k3(0), etc, is
free, and the probability of success goes up linearly with the number
of queries.

In the multitarget scenario contrast recovering the discrete log of Q1
via a distinguished point algorithm doesn’t help with recovering Q2,
etc. By contrast AES is considerably weaker than the discrete
logarithm problem with the same bit security. The probability of
success is then quadratic in the effort: an attacker satisfied with a
success probability of ¼ has to do ¼ the work for AES, but  a full ½
of the work for ECC. These are very different levels of security, so
the use of the same number to describe them is counterproductive.

Similarly, the security of the finite field Diffie-Hellman problem in
medium size extensions is one where an attacker faced with a number of
targets can do a substantial amount of shared work, reducing the cost
of each additional broken key.  Furthermore there is substantial
uncertainty about the runtime, particularly with the sieving step and
search for good polynomials, as well as a lack of good experiments to
quantify the runtime heuristics. The draft does well to mention a few
recent papers to justify the numbers presented, but there is still
substantial uncertainty.  The benign outcome is that the single number
gives no practical insights; the worse outcome is that it guides users
towards poor choices. In light of the advent of quantum computers the
long term security of these curves is broken anyway.

Secondly, the draft presents a real opportunity to be useful to
implementors, that will be missed without additional practical advice
or recommendations. Appendix A omits a particularly efficient
algorithm due to use of affine coordinates and division, and many
applications can make use of optimizations that combine the final
exponentiation across pairings since they are computing a multipairing
product. From experience pseudocode that expresses a reasonably
efficient algorithm, together with information on avoiding side
channels and optimizations for the frequently used optimizations would
be very beneficial. That’s particularly true for handling invalid
inputs safely, a topic frequently neglected but essential for
security.

Both RFC 7748 and RFC 6090 provide this guidance to implementors and
are much more useful for it. Including these extra practical
recommendations is a lot of work, but avoids so much more effort
afterwards when needing to repeat the translation from paper into
pseudocode, as well as hopefully avoiding common security pitfalls.
Bitter experience has shown that pointing to a literature reference
has shortcomings.

Thirdly the security considerations section is woefully inadequate.
What are the considerations implementors should be aware of when
implementing this document and that those who use it should be aware
of? Are there attacks based on invalid data that need to be
considered? How does one validate group elements efficiently? All of
these are important details that I think should be addressed here. RFC
7748 does a decent job and should be looked to as a model.

Lastly there are a number of small tweaks I would make to the English
throughout the document in the interest of readability: fixes to
tense, articles, etc. I suspect the definition of nondegeneracy is
incorrect due to recorded clauses: it should read “e(S, T)=1 for all T
if and only if S=O_E”, etc. I’d be happy to submit a PR with the
changes if I knew where it lived in git.

The table of implementor and standardization choices I don’t think
adds much to the text and should be removed. Likewise, the laundry
list of applications is good motivation, but it could be shortened
without losing too much.

Thanks to the authors for advancing this draft, and I’m happy to
discuss these points further with them or others on the list/contribute text.

Sincerely,

Watson Ladd

---

From: Yumi Sakemi <[email-masked]>
Date: Mon, 18 May 2020 23:20:35 +0900

Dear Watson

Thank you for many useful comments!
I'm so sorry for my late reply.
I discussed about your comments with the co-authors.
According to the four comments you have sent, we answer as follows.

1. About equivalent security and adoption of BLS12-381
Thank you for your detailed explanation and suggestions for equivalent security!
As you pointed out, we agree that a simple expression of bit security
is misleading.
So, we will add a description of equivalent security to our draft.
Also, regarding BLS12-381, it was excluded from the candidates due to
our lack of investigation.
However, we received information from a reviewer at Expert Review and
found that BLS12-381 matches our selection policy from the perspective
of efficiency and security.
Therefore, please rest assured that BLS12-381 will be the recommended
parameters as well.

2. Description of detailed pairing algorithm
We also recognize that there are calculation methods using Affine
coordinates, projective coordinates, Jacobian coordinates, etc.
We considered, but we think that showing a specific algorithm would
reduce the flexibility of the implementers.
Therefore, we describe the most basic method as an algorithm, and
describe that there are isomorphism techniques, for example.

3. Security consideration
As you pointed out, the explanation of attacks in security
considerations is insufficient.
I appreciate your comments.
We will update the description of the security considerations by
adding the following.
- Checking whether elements exist in an appropriate group
- Checking for side channel attack resistance
- Checking whether range of coefficient is appropriate

4. About editorial comments
Regarding the English expression, we have received many comments from
the reviewer at Expert Review,
and we plan to entirely improve it in version 05.
Also, regarding Table1, one of our selection policies is that there
are multiple implementations,
 so we consider that Table1 is essential as the evidence.
On the other hand, as you pointed out, Table 1 is very large, and it
reduces the readability of the draft,
so we will consider whether we can devise an expression.
(For example, we move Table1 to Appendix and refer it)

Finally, thank you for reading our draft!
I think it will be a better draft to reflect your comments!

Best regards,
Yumi

2020年5月9日(土) 3:19 Watson Ladd <[email-masked]>:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
Yumi Sakemi
Lepidum Co. Ltd.
E-Mail: [email-masked]