Curve25519 Openssl

Curve25519 The X25519 function can be used in an Elliptic Curve Diffie-Hellman (ECDH) protocol as follows: Alice generates 32 random bytes in a0 to a31 and transmits KA = X25519(a, 9) to Bob, where 9 is the u-coordinate of the base point and is encoded as a byte with value 9, followed by 31 zero bytes. Bob similarly generates 32 random.

Why Create a New Elliptic Curve Cryptography Library?

Commonly used crypto libraries like NSS and OpenSSL implement ECDH and ECDSA signing and verification for a large number of prime and non-prime curves. In order to support a wide variety of curves, these libraries internally have frameworks that abstract the general algorithms from the curve-specific details. These frameworks make sense when a wide variety of curves and algorithms need to be supported, but they add significant complexity that would be unneeded for software that only needs to deal with a small number of well-known curves, such as the NIST P-256 and P-384 curves and Curve25519.

OpenSSL exposes its internal framework as a public API for applications to use, so changing the framework risks breaking applications built on top of it. This makes it difficult to make improvements to the framework. Consequently, the implementations of curve-specific optimizations in OpenSSL generally avoid the lower-level parts of that framework, causing those implementations to have very similar but separate implementations of the generic logic. Thus, for example, one set of optimized implementations of the P-224, P-256, and P-521 curves in OpenSSL has ~1,700, ~2,300, and ~2,100 lines, respectively, of quite similar code.

With today’s C compilers, some key components need to be implemented in assembly language to give reasonable performance and to prevent side channel leaks of secret information. Assemblers usually have macros and other high-level features that make assembly-language programming convenient. However, some assemblers do not have such features, and the ones that do all have different syntaxes. OpenSSL has its own assembly language macro framework called perlasm to deal with this. Every OpenSSL assembly language source file is actually a Perl program that generates the assembly language file. The result is several large files of interleaved Perl and assembly language code. The fastest P-256 implementation in OpenSSL, ecp_nistz256, consists of ~6,000 lines of x64 perlasm + ~1,700 lines of x86 perlasm + ~1,500 lines of ARMv8 perlasm + ~1,700 lines of ARMv4 perlasm + ~1,500 lines of C code plus a ~150KB table of data.

  1. Curve25519 keys provides information on the keys used with x25519 and ed25519.The IETF has documents covering x25519, x448, ed25519 and ed448, and they are listed below. Note that draft-ietf-curdle-pkix expired on November 9, 2.
  2. Openssl genpkey -algorithm x25519 This produces a private key of the form: -BEGIN PRIVATE KEY- MC4CAQAwBQYDK2VuBCIEIDgk3GuFMIaUJd3m95jn/Z8oU+cK9FzPoidIDn/bqRlk -END PRIVATE KEY- I want to parse this key file in Go and potentially use it using golang.org/x/crypto/nacl/box.
  3. Openssl x509 -in rsacert.pem -text -noout # generate PKCS#12 container: openssl pkcs12 -export -inkey rsakey.pem -in rsacert.pem -out rsacred.p12. ECDSA # Generate self-signed certificate with ECDSA using two common curves: openssl req -x509 -nodes -days 3650 -newkey ec:openssl ecparam -name prime256v1) -keyout ecdsakey.pem -out ecdsacert.pem.

Imagine that we must find a high-performance implementation of P-256 and P-384 (the two curves generally used in TLS) ECDSA signature verification and verify its correctness. We might not find a fast enough P-384 implementation, so we might be tempted to adapt an existing fast P-256 implementation for P-384. How long would the audit and adaptation process take? How confident would we be in the result? How hard would it be for somebody else to meaningfully confirm our findings and review any changes we make? It seems likely that we would take a lot of time, end up with something we could not be very confident in, and find the result to be hard to improve later.

The fundamental problem isn't the sheer amount of code in the optimized implementations of ECC or that the techniques they use are bad. Rather, after the simple ideas used in the implementations were translated into low-level C and assembly language code, with multiple layers of repetition, it is now difficult to map the code back to the abstractions it was derived from. A small number of reasonable trade-offs of the ease of understanding by people for the ease of processing by computers accumulated quickly into a large and unreasonable such trade-off.

Curve25519 Openssl

The specialized implementations of ECC in OpenSSL are optimized for ECDH key agreement and ECDSA signing, so they use constant-time algorithms to avoid timing attacks. Hoewver, ECDSA signature verification does not need to be constant time, and the variable-time WNAF scalar elliptic curve point algorithm is significantly more efficient than constant-time algorithms. The constant-time ecp_nistz256 code in OpenSSL is much faster than OpenSSL’s variable-time P-256 code, but WNAF-based variable-time point multiplication implemented using ecp_nistz256’s implementation of P-256 field operations should be significantly faster (on average) yet.

The IETF is currently standardizing new ECC cryptosystems based on two new curves, Curve25519 and Ed448-Goldilocks. It seems likely that Curve25519 will be critically important for a variety of reasons; for example, it seems like it will be a key part of the bridge connecting the new Internet of Things (IoT) to the normal Internet of Nothings. If we were to implement Curve25519 and Ed448-Goldilocks using the same strategies that have been used for P-256 in the past, we would end up compounding the maintenance problem we already face.

Curve25519 and EdDSA (or whatever signature scheme ultimately gets standardized) will take a while to become ubiquitous. This makes it tempting to try to use P-256 and ECDSA as part of the bridge between IoT and the rest of the Internet in the short term. To have even a chance of succeeding at that, such an implementation would have to be very efficient in terms of execution time and code size. It would also have to be easy to create efficient ports of the code to highly-constrained (slow, low memory, and power-constrained) architectures.

Goals

With those motivations in mind, it is worth exploring whether it makes sense to create a new ECC implementation with the following goals:

  • We must be confident in the correctness of what we created, preferably with the assistance of automated tools for correctness checking.
  • In high-end smartphones, tablets, and computers, P-256 and P-384 signature verification should take one millisecond or less, so that all the signature verifications needed for a TLS handshake can complete in under 10ms, so that the CPU cost of the TLS handshake is not a factor in terms of latency. On more constrained devices, we will have to settle for “as efficient as the code size budget allows,” for now.
  • The code and any precomputed static data should be as compact as possible. In constrained applications the allowed code size is a parameter that can vary considerably, so it is hard to put a specific figure on this. However, informally we will aim to create something that is smaller than the ECC portions of other implementations like BoringSSL, OpenSSL, and NSS.
  • It should be straightforward to reuse large amounts of the implementation of P-256 and P-384 to implement Curve25519 and maybe other curves.
  • Without significantly sacrificing signature verification performance, the code for the arithmetic should be easy to reuse (preferably) or adapt (less preferably) for side-channel resistant implementation of signing and ECDH key agreement.
Curve25519

An Implementation Strategy

ECDSA signature verification consists of parsing inputs, doing an inversion and some multiplications modulo n (the group order), doing two scalar elliptic curve point multiplications, and then verifying that the result of the multiplication matches a value in the signature. We precompute a bunch of sums of the curve’s group generator point G and a bunch of sums of the public key, which requires multiplication, squaring, and inversion modulo q (the field modulus). We compute the WNAF representations of the scalars of the two points, and then perform a pattern of point doublings and point additions based on the pattern in the WNAF representation. The point doublings and additions are specific sequences of multiplications, additions, subtractions, and squarings modulo q. Multiplication and squaring modulo q are, by far, the most performance-sensitive operations because they are executed many times in a scalar point multiplication. In order to do all these arithmetic operations, we generally need to precompute some quantities that are functions of n or q and the word size of the machine. ECDSA signing and ECDH key agreement more-or-less involve the same kinds of operations, except they need everything to be constant time.

One way to minimize code size, at the cost of speed, is to implement all the algorithms generically. For example, there would be one modular multiplication function that takes two multiplicands and the modulus as inputs, one modular inversion function that takes the element to invert and the modulus as input, etc. We would probably find that such generic implementations work good enough in many cases, especially the operations modulo n that are not frequently executed, so that we can avoid writing curve-specific code for many of them. If we start with generic implementations of every algorithm, then we can use them as the foundation for a [2015] by Greg Maxwell.

  • [openssl-dev] ecp_nistz256 correctness/constant-timedness [2015] and RE: [openssl-dev] ecp_nistz256 correctness/constant-timedness [2015] by Brian Smith.
  • Verifying Curve25519 Software [2014] by Yu-Fang Chen, Chang-Hong Hsu, Hsin-Hung Lin, Peter Schwabe, Ming-Hsien Tsai, Bow-Yaw Wang, Bo-Yin Yang, and Shang-Yi Yang.
  • Montgomery Modular Multiplication on ARM-NEON Revisited [2014] by Hwajeong Seo, Zhe Liu, Johann Großschädl, Jongseok Choi, and Howon Kim.
  • Openssl

    Openssl/curve25519.h

  • Efficient Arithmetic on ARM-NEON and ItsApplication for High-Speed RSA Implementation [2015] by Hwajeong Seo, Zhe Liu, Johann Großschädl, andHowon Kim.
  • Curve25519: new Diffie-Hellman speed records [2006] by Daniel J. Bernstein.
  • Fast Elliptic Curve Cryptography in OpenSSL [2012] by Emilia Käsper.
  • Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography on x86-64 based Processors [2010] by Patrick Longa and Catherine Gebotys.
  • Analyzing and Comparing Montgomery Multiplication Algorithms [1996] by Çetin Kaya Koç, Tolga Acar, and Burton S. Kaliski Jr.
  • [curves] Goldilocks optimizations [2014] by Michael Hamburg (reformatted and retitled by Trevor Perrin).
  • New InstructionsSupporting Large Integer Arithmetic on Intel® Architecture Processors [2013] by Erdinc Ozturk, James Guilford, Vinodh Gopal, and Wajdi Feghali.
  • LargeInteger Squaring on Intel® Architecture Processors [2012] by Erdinc Ozturk, James Guilford, and Vinodh Gopal.
  • OpenSSL provides two command line tools for working with keys suitable for Elliptic Curve (EC) algorithms:

    The only Elliptic Curve algorithms that OpenSSL currently supports are Elliptic Curve Diffie Hellman (ECDH) for key agreement and Elliptic Curve Digital Signature Algorithm (ECDSA) for signing/verifying.

    x25519, ed25519 and ed448 aren't standard EC curves so you can't use ecparams or ec subcommands to work with them. If you need to generate x25519 or ed25519 keys then see the genpkey subcommand.

    EC Private Key File Formats[edit]

    By default OpenSSL will work with PEM files for storing EC private keys. These are text files containing base-64 encoded data. A typical traditional format private key file in PEM format will look something like the following, in a file with a '.pem' extension:

    Or, in an encrypted form like this:

    You may also encounter PKCS8 format private keys in PEM files. These look like this:

    Or, in an encrypted form like this:

    PKCS8 private key files, like the above, are capable of holding many different types of private key - not just EC keys.

    You can convert between these formats if you like. All of the conversion commands can read either the encrypted or unencrypted forms of the files however you must specify whether you want the output to be encrypted or not. To convert a PKCS8 file to a traditional encrypted EC format use:

    You can replace the first argument 'aes-128-cbc' with any other valid openssl cipher name (see Manual:enc(1) for a list of valid cipher names). To convert a PKCS8 file to a traditional unencrypted EC format, just drop the first argument:

    Or to convert from a traditional EC format to an encrypted PKCS8 format use:

    Or to a non-encrypted PKCS8 format use:

    Note that by default in the above traditional format EC Private Key files are not encrypted (you have to explicitly state that the file should be encrypted, and what cipher to use), whilst for PKCS8 files the opposite is true. The default is to encrypt - you have to explicitly state that you do not want encryption applied if appropriate using the '-nocrypt' option.

    As well as PEM format all of the above types of key file can also be stored in DER format. This is a binary format and so is not directly human readable - unlike a PEM file. A PEM file is essentially just DER data encoded using base 64 encoding rules with a header and footer added. Often it is more convenient to work with PEM files for this reason.

    The openssl commands typically have options '-inform DER' or '-outform DER' to specify that the input or output file is DER respectively. So for example the command to convert a PKCS8 file to a traditional encrypted EC format in DER is the same as above, but with the addition of '-outform DER':

    Note that you cannot encrypt a traditional format EC Private Key in DER format (and in fact if you attempt to do so the argument is silently ignored!). The same is not true for PKCS8 files - these can still be encrypted even in DER format. So for example the following will convert a traditional format key file to an ecrypted PKCS8 format DER encoded key:

    EC Public Key File Formats[edit]

    EC Public Keys are also stored in PEM files. A typical EC public key looks as follows:

    This format is used to store all types of public keys in OpenSSL not just EC keys.

    It is possible to create a public key file from a private key file (although obviously not the other way around!):

    As above a DER encoded version can be created using '-outform DER':

    Generating EC Keys and Parameters[edit]

    An EC Parameters file contains all of the information necessary to define an Elliptic Curve that can then be used for cryptographic operations (for OpenSSL this means ECDH and ECDSA). OpenSSL contains a large set of pre-defined curves that can be used. The full list of built-in curves can be obtained through the following command:

    An EC parameters file can then be generated for any of the built-in named curves as follows:

    Replace secp256k1 in the above with whichever curve you are interested in.

    Keys can be generated from the ecparam command, either through a pre-existing parameters file or directly by selecting the name of the curve. To generate a private/public key pair from a pre-eixsting parameters file use the following:

    Or to do the equivalent operation without a parameters file use the following:

    Information on the parameters that have been used to generate the key are embedded in the key file itself.

    By default, when creating a parameters file, or generating a key, openssl will only store the name of the curve in the generated parameters or key file, not the full set of explicit parameters associated with that name. For example:

    This will simply confirm the name of the curve in the parameters file by printing out the following:

    If you wish to examine the specific details of the parameters associated with a particular named curve then this can be achieved as follows:

    The above command shows the details for a built-in named curve from a file, but this can also be done directly using the '-name' argument instead of '-in'. The output will look similar to the following:

    The meaning of each of these parameters is discussed further on this page.

    Parameters and key files can be generated to include the full explicit parameters instead of just the name of the curve if desired. This might be important if, for example, not all the target systems know the details of the named curve. In OpenSSL version 1.0.2 new named curves have been added such as brainpool512t1. Attempting to use a parameters file or key file in versions of OpenSSL less than 1.0.2 with this curve will result in an error:

    This problem can be avoided if explicit parameters are used instead. So under OpenSSL 1.0.2 you could create a parameters file like this:

    Looking at the parameters file you will notice that it is now much longer:

    The full parameters are included rather than just the name. This can now be processed by versions of OpenSSL less than 1.0.2. So under 1.0.1:

    This will correctly display the parameters, even though this version of OpenSSL does not know about this curve.

    The same is true of key files. So to generate a key with explicit parameters:

    This key file can now be processed by versions of openssl that do not know about the brainpool curve.

    It should be noted however that once the parameters have been converted from the curve name format into explicit parameters it is not possible to change them back again, i.e. there is no utility to take a set of explicit parameters and work out which named curve they are associated with.

    See also[edit]

    Retrieved from 'https://wiki.openssl.org/index.php?title=Command_Line_Elliptic_Curve_Operations&oldid=2734'