ed25519 support in x509 certificate builder (#4937)

* ed25519 support in x509 certificate builder

This adds minimal ed25519 support. More to come.

* Apply suggestions from code review

Co-Authored-By: Alex Gaynor <alex.gaynor@gmail.com>

6 files changed, 168 insertions, 14 deletions

diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index a8ef5d22..9ece6d1d 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -12,6 +12,8 @@ Changelog
   ``cryptography`` 2.9.
 * We now ship ``manylinux2010`` wheels in addition to our ``manylinux1``
   wheels.
+* Added support for ``ed25519`` keys in the
+  :class:`~cryptography.x509.CertificateBuilder`.
 
 .. _v2-7:
 
diff --git a/docs/x509/reference.rst b/docs/x509/reference.rst
index 6333a263..38901c7c 100644
--- a/docs/x509/reference.rst
+++ b/docs/x509/reference.rst
@@ -338,7 +338,8 @@ X.509 Certificate Object
         :returns:
             :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPublicKey` or
             :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPublicKey` or
-            :class:`~cryptography.hazmat.primitives.asymmetric.ec.EllipticCurvePublicKey`
+            :class:`~cryptography.hazmat.primitives.asymmetric.ec.EllipticCurvePublicKey` or
+            :class:`~cryptography.hazmat.primitives.asymmetric.ed25519.Ed25519PublicKey`
 
         .. doctest::
 
@@ -727,8 +728,10 @@ X.509 Certificate Builder
 
         :param public_key: The subject's public key. This can be one of
             :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPublicKey`,
-            :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPublicKey` or
+            :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPublicKey`,
             :class:`~cryptography.hazmat.primitives.asymmetric.ec.EllipticCurvePublicKey`
+            or
+            :class:`~cryptography.hazmat.primitives.asymmetric.ed25519.Ed25519PublicKey`
 
     .. method:: serial_number(serial_number)
 
@@ -781,13 +784,20 @@ X.509 Certificate Builder
 
         :param private_key: The
             :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPrivateKey`,
-            :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPrivateKey` or
+            :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPrivateKey`,
             :class:`~cryptography.hazmat.primitives.asymmetric.ec.EllipticCurvePrivateKey`
+            , or
+            :class:`~cryptography.hazmat.primitives.asymmetric.ed25519.Ed25519PrivateKey`
             that will be used to sign the certificate.
 
         :param algorithm: The
             :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm` that
-            will be used to generate the signature.
+            will be used to generate the signature. This must be ``None`` if
+            the ``private_key`` is an
+            :class:`~cryptography.hazmat.primitives.asymmetric.ed25519.Ed25519PrivateKey`
+            and an instance of a
+            :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm`
+            otherwise.
 
         :param backend: Backend that will be used to build the certificate.
             Must support the
@@ -2836,6 +2846,13 @@ instances. The following common OIDs are available as constants.
         Corresponds to the dotted string ``"2.16.840.1.101.3.4.3.2"``. This is
         a SHA256 digest signed by a DSA key.
 
+    .. attribute:: ED25519
+
+        .. versionadded:: 2.8
+
+        Corresponds to the dotted string ``"1.3.101.112"``. This is a signature
+        using an ed25519 key.
+
 
 .. class:: ExtendedKeyUsageOID
 
diff --git a/src/cryptography/hazmat/backends/openssl/backend.py b/src/cryptography/hazmat/backends/openssl/backend.py
index ca0a11bd..c24d334a 100644
--- a/src/cryptography/hazmat/backends/openssl/backend.py
+++ b/src/cryptography/hazmat/backends/openssl/backend.py
@@ -798,7 +798,12 @@ class Backend(object):
     def create_x509_certificate(self, builder, private_key, algorithm):
         if not isinstance(builder, x509.CertificateBuilder):
             raise TypeError('Builder type mismatch.')
-        if not isinstance(algorithm, hashes.HashAlgorithm):
+        if isinstance(private_key, ed25519.Ed25519PrivateKey):
+            if algorithm is not None:
+                raise ValueError(
+                    "algorithm must be None when signing via ed25519"
+                )
+        elif not isinstance(algorithm, hashes.HashAlgorithm):
             raise TypeError('Algorithm must be a registered hash algorithm.')
 
         if (
@@ -806,11 +811,11 @@ class Backend(object):
             isinstance(private_key, rsa.RSAPrivateKey)
         ):
             raise ValueError(
-                "MD5 is not a supported hash algorithm for EC/DSA certificates"
+                "MD5 is only (reluctantly) supported for RSA certificates"
             )
 
         # Resolve the signature algorithm.
-        evp_md = self._evp_md_non_null_from_algorithm(algorithm)
+        evp_md = self._evp_md_x509_null_if_ed25519(private_key, algorithm)
 
         # Create an empty certificate.
         x509_cert = self._lib.X509_new()
@@ -878,6 +883,13 @@ class Backend(object):
 
         return _Certificate(self, x509_cert)
 
+    def _evp_md_x509_null_if_ed25519(self, private_key, algorithm):
+        if isinstance(private_key, ed25519.Ed25519PrivateKey):
+            # OpenSSL requires us to pass NULL for EVP_MD for ed25519 signing
+            return self._ffi.NULL
+        else:
+            return self._evp_md_non_null_from_algorithm(algorithm)
+
     def _set_asn1_time(self, asn1_time, time):
         if time.year >= 2050:
             asn1_str = time.strftime('%Y%m%d%H%M%SZ').encode('ascii')
diff --git a/src/cryptography/x509/base.py b/src/cryptography/x509/base.py
index 63c2e3c6..dc7eee94 100644
--- a/src/cryptography/x509/base.py
+++ b/src/cryptography/x509/base.py
@@ -12,7 +12,7 @@ from enum import Enum
 import six
 
 from cryptography import utils
-from cryptography.hazmat.primitives.asymmetric import dsa, ec, rsa
+from cryptography.hazmat.primitives.asymmetric import dsa, ec, ed25519, rsa
 from cryptography.x509.extensions import Extension, ExtensionType
 from cryptography.x509.name import Name
 
@@ -474,9 +474,10 @@ class CertificateBuilder(object):
         Sets the requestor's public key (as found in the signing request).
         """
         if not isinstance(key, (dsa.DSAPublicKey, rsa.RSAPublicKey,
-                                ec.EllipticCurvePublicKey)):
+                                ec.EllipticCurvePublicKey,
+                                ed25519.Ed25519PublicKey)):
             raise TypeError('Expecting one of DSAPublicKey, RSAPublicKey,'
-                            ' or EllipticCurvePublicKey.')
+                            ' EllipticCurvePublicKey, or Ed25519PublicKey.')
         if self._public_key is not None:
             raise ValueError('The public key may only be set once.')
         return CertificateBuilder(
diff --git a/src/cryptography/x509/oid.py b/src/cryptography/x509/oid.py
index 1bfe58ca..ab01d67b 100644
--- a/src/cryptography/x509/oid.py
+++ b/src/cryptography/x509/oid.py
@@ -96,6 +96,7 @@ class SignatureAlgorithmOID(object):
     DSA_WITH_SHA1 = ObjectIdentifier("1.2.840.10040.4.3")
     DSA_WITH_SHA224 = ObjectIdentifier("2.16.840.1.101.3.4.3.1")
     DSA_WITH_SHA256 = ObjectIdentifier("2.16.840.1.101.3.4.3.2")
+    ED25519 = ObjectIdentifier("1.3.101.112")
 
 
 _SIG_OIDS_TO_HASH = {
@@ -113,7 +114,8 @@ _SIG_OIDS_TO_HASH = {
     SignatureAlgorithmOID.ECDSA_WITH_SHA512: hashes.SHA512(),
     SignatureAlgorithmOID.DSA_WITH_SHA1: hashes.SHA1(),
     SignatureAlgorithmOID.DSA_WITH_SHA224: hashes.SHA224(),
-    SignatureAlgorithmOID.DSA_WITH_SHA256: hashes.SHA256()
+    SignatureAlgorithmOID.DSA_WITH_SHA256: hashes.SHA256(),
+    SignatureAlgorithmOID.ED25519: None,
 }
 
 
@@ -181,6 +183,7 @@ _OID_NAMES = {
     SignatureAlgorithmOID.DSA_WITH_SHA1: "dsa-with-sha1",
     SignatureAlgorithmOID.DSA_WITH_SHA224: "dsa-with-sha224",
     SignatureAlgorithmOID.DSA_WITH_SHA256: "dsa-with-sha256",
+    SignatureAlgorithmOID.ED25519: "ed25519",
     ExtendedKeyUsageOID.SERVER_AUTH: "serverAuth",
     ExtendedKeyUsageOID.CLIENT_AUTH: "clientAuth",
     ExtendedKeyUsageOID.CODE_SIGNING: "codeSigning",
diff --git a/tests/x509/test_x509.py b/tests/x509/test_x509.py
index a4cd70bc..27062918 100644
--- a/tests/x509/test_x509.py
+++ b/tests/x509/test_x509.py
@@ -24,7 +24,9 @@ from cryptography.hazmat.backends.interfaces import (
     DSABackend, EllipticCurveBackend, RSABackend, X509Backend
 )
 from cryptography.hazmat.primitives import hashes, serialization
-from cryptography.hazmat.primitives.asymmetric import dsa, ec, padding, rsa
+from cryptography.hazmat.primitives.asymmetric import (
+    dsa, ec, ed25519, padding, rsa
+)
 from cryptography.hazmat.primitives.asymmetric.utils import (
     decode_dss_signature
 )
@@ -2130,7 +2132,13 @@ class TestCertificateBuilder(object):
 
     @pytest.mark.requires_backend_interface(interface=RSABackend)
     @pytest.mark.requires_backend_interface(interface=X509Backend)
-    def test_sign_with_unsupported_hash(self, backend):
+    @pytest.mark.parametrize(
+        "algorithm",
+        [
+            object(), None
+        ]
+    )
+    def test_sign_with_unsupported_hash(self, algorithm, backend):
         private_key = RSA_KEY_2048.private_key(backend)
         builder = x509.CertificateBuilder()
         builder = builder.subject_name(
@@ -2148,7 +2156,7 @@ class TestCertificateBuilder(object):
         )
 
         with pytest.raises(TypeError):
-            builder.sign(private_key, object(), backend)
+            builder.sign(private_key, algorithm, backend)
 
     @pytest.mark.requires_backend_interface(interface=RSABackend)
     @pytest.mark.requires_backend_interface(interface=X509Backend)
@@ -2305,6 +2313,97 @@ class TestCertificateBuilder(object):
             x509.DNSName(u"cryptography.io"),
         ]
 
+    @pytest.mark.supported(
+        only_if=lambda backend: backend.ed25519_supported(),
+        skip_message="Requires OpenSSL with Ed25519 support"
+    )
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_build_cert_with_ed25519(self, backend):
+        issuer_private_key = ed25519.Ed25519PrivateKey.generate()
+        subject_private_key = ed25519.Ed25519PrivateKey.generate()
+
+        not_valid_before = datetime.datetime(2002, 1, 1, 12, 1)
+        not_valid_after = datetime.datetime(2030, 12, 31, 8, 30)
+
+        builder = x509.CertificateBuilder().serial_number(
+            777
+        ).issuer_name(x509.Name([
+            x509.NameAttribute(NameOID.COUNTRY_NAME, u'US'),
+        ])).subject_name(x509.Name([
+            x509.NameAttribute(NameOID.COUNTRY_NAME, u'US'),
+        ])).public_key(
+            subject_private_key.public_key()
+        ).add_extension(
+            x509.BasicConstraints(ca=False, path_length=None), True,
+        ).add_extension(
+            x509.SubjectAlternativeName([x509.DNSName(u"cryptography.io")]),
+            critical=False,
+        ).not_valid_before(
+            not_valid_before
+        ).not_valid_after(
+            not_valid_after
+        )
+
+        cert = builder.sign(issuer_private_key, None, backend)
+        issuer_private_key.public_key().verify(
+            cert.signature, cert.tbs_certificate_bytes
+        )
+        assert cert.signature_algorithm_oid == SignatureAlgorithmOID.ED25519
+        assert cert.signature_hash_algorithm is None
+        assert isinstance(cert.public_key(), ed25519.Ed25519PublicKey)
+        assert cert.version is x509.Version.v3
+        assert cert.not_valid_before == not_valid_before
+        assert cert.not_valid_after == not_valid_after
+        basic_constraints = cert.extensions.get_extension_for_oid(
+            ExtensionOID.BASIC_CONSTRAINTS
+        )
+        assert basic_constraints.value.ca is False
+        assert basic_constraints.value.path_length is None
+        subject_alternative_name = cert.extensions.get_extension_for_oid(
+            ExtensionOID.SUBJECT_ALTERNATIVE_NAME
+        )
+        assert list(subject_alternative_name.value) == [
+            x509.DNSName(u"cryptography.io"),
+        ]
+
+    @pytest.mark.supported(
+        only_if=lambda backend: backend.ed25519_supported(),
+        skip_message="Requires OpenSSL with Ed25519 support"
+    )
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    def test_build_cert_with_public_ed25519_rsa_sig(self, backend):
+        issuer_private_key = RSA_KEY_2048.private_key(backend)
+        subject_private_key = ed25519.Ed25519PrivateKey.generate()
+
+        not_valid_before = datetime.datetime(2002, 1, 1, 12, 1)
+        not_valid_after = datetime.datetime(2030, 12, 31, 8, 30)
+
+        builder = x509.CertificateBuilder().serial_number(
+            777
+        ).issuer_name(x509.Name([
+            x509.NameAttribute(NameOID.COUNTRY_NAME, u'US'),
+        ])).subject_name(x509.Name([
+            x509.NameAttribute(NameOID.COUNTRY_NAME, u'US'),
+        ])).public_key(
+            subject_private_key.public_key()
+        ).not_valid_before(
+            not_valid_before
+        ).not_valid_after(
+            not_valid_after
+        )
+
+        cert = builder.sign(issuer_private_key, hashes.SHA256(), backend)
+        issuer_private_key.public_key().verify(
+            cert.signature, cert.tbs_certificate_bytes, padding.PKCS1v15(),
+            cert.signature_hash_algorithm
+        )
+        assert cert.signature_algorithm_oid == (
+            SignatureAlgorithmOID.RSA_WITH_SHA256
+        )
+        assert isinstance(cert.signature_hash_algorithm, hashes.SHA256)
+        assert isinstance(cert.public_key(), ed25519.Ed25519PublicKey)
+
     @pytest.mark.requires_backend_interface(interface=RSABackend)
     @pytest.mark.requires_backend_interface(interface=X509Backend)
     def test_build_cert_with_rsa_key_too_small(self, backend):
@@ -4201,6 +4300,26 @@ class TestName(object):
         )
 
 
+@pytest.mark.supported(
+    only_if=lambda backend: backend.ed25519_supported(),
+    skip_message="Requires OpenSSL with Ed25519 support"
+)
+@pytest.mark.requires_backend_interface(interface=X509Backend)
+class TestEd25519Certificate(object):
+    def test_load_pem_cert(self, backend):
+        cert = _load_cert(
+            os.path.join("x509", "ed25519", "root-ed25519.pem"),
+            x509.load_pem_x509_certificate,
+            backend
+        )
+        # self-signed, so this will work
+        cert.public_key().verify(cert.signature, cert.tbs_certificate_bytes)
+        assert isinstance(cert, x509.Certificate)
+        assert cert.serial_number == 9579446940964433301
+        assert cert.signature_hash_algorithm is None
+        assert cert.signature_algorithm_oid == SignatureAlgorithmOID.ED25519
+
+
 def test_random_serial_number(monkeypatch):
     sample_data = os.urandom(20)