[Cryptography] FW: real world binary ecc

[Salz, Rich]

Forwarded with permission; Nicoli is one of the (sic) key implementors of ECC in the OpenSSL project.


On 11/15/20, 10:19 AM, "Nicola Tuveri" <nic.tuv at gmail.com> wrote:

    > suppose you want to create a new TLS library.  Should you support binary curves?

    I'd dare say, from an implementer perspective, the answer to this is
    "likely no".
    RFC 8422, in obsoleting RFC 4492, has de facto removed support of
    binary curves from TLS 1.2 and earlier.
    Someone might wonder if it is worth including support for binary
    curves, despite RFC 8422, for interoperability with older
    implementations, but as far as I can tell, popular SSL/TLS libraries
    never supported binary curves, or never used them by default.

    I can't point to studies showing how many of the TOP 500 sites for
    traffic generation would see handshakes using binary curves, but I
    would be surprised to see a significant number there (maybe Akamai has
    such data readily available to quantify this among their customers?). [R$: We don't]

    FIPS 186-4 does include binary curves among the recommendations and
    it's difficult for me to say what percentage of users subject to the
    FIPS requirements actually preferred binary curves over prime curves
    in the wild, in the SW realm: publicly available software
    implementations have been mostly driven by TLS usage, favoring
    optimized implementations of prime curves over work towards optimizing
    implementations of binary curves. Limited availability (and at lower
    performance levels) could easily have been a limiting factor in
    adoption of binary curves even for uses outside general TLS and the
    World Wide Web.

    In OpenSSL's libcrypto, for example, it is possible to access
    implementations of binary elliptic curves, but they are not supported
    in OpenSSL's libssl, thus not available for TLS handshakes (not even
    before RFC 8422), and in general, as they use generic implementations
    supporting various binary field sizes, the performance level is subpar
    compared to highly optimized implementations for specific prime curves
    (e.g. the nistz265 implementation for P-256 or the 128-bit
    implementations for P-224, P-256 and P-512).
    The notion that, in the domain of SW implementations, prime curves are
    faster than binary curves, has been repeatedly challenged by academia,
    and there has been work on optimizing and hardening the binary curve
    side of things in OpenSSL, but IMO for the time being, the next
    biggest performance (and security) improvement would likely come by
    including specialized `EC_METHOD` implementations for specific curves,
    instead of relying on the "generic" implementation that works with any
    arbitrary binary field parameter set: but a prerequisite for that
    would be selecting candidates that are widely used to justify the
    extra costs… kind of a chicken and egg problem.

    Some links about recent improvements to software binary EC
    implementations in OpenSSL I have been somewhat involved with:

    - https://github.com/openssl/openssl/pull/6690
    - https://eprint.iacr.org/2019/829.pdf 
    - https://doi.org/10.1007/978-3-319-26502-5_7

    For hardware implementations, the general assumption is that binary
    elliptic curves are faster and cheaper in area, so, in that field,
    binary curves might see some wider adoption. OTOH, recent years saw a
    surge in availability of cheap microcontrollers and coprocessors
    (either external or inside the same chip package) to accelerate and
    harden elliptic curve cryptography, specifically targeting popular
    NIST prime curves and Curve25519/448, and this might probably have
    leveled the gap by now even in the HW sector.
    Note though, that admittedly my knowledge and experience in the world
    of smart cards and embedded hw implementations is very limited, so
    take my words with extra doses of grains of salt here.

    To somewhat summarize the long description, my opinion is that while
    academia has not given up on binary curves, it seems like industry
    mostly has.

    Quickly browsing through a query on DBLP
    (https://dblp.org/search?q=binary*20curve) shows that this is still
    a quite active area of research, but I am not aware of major efforts
    by standardization bodies that are promoting the adoption of binary
    curves at the moment.
    Actually, it seems like industry committed to evaluate an excessive
    level of flexibility in the choice space of alternative cryptographic
    algorithms as an antipattern, as we can see in the directions taken
    during the development of the TLS 1.3 spec, in the mentioned RFC 8422
    and in the current FIPS 186-5 draft, which also shows similarly that
    binary curve support is likely going to be deprecated.

    Cheers,

    Nicola Tuveri