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

[Watson Ladd <[e-mail]>]

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