Remove asn1crypto dependency (#4941)

* Remove non-test dependencies on asn1crypto.

cryptography.io actually contains two OpenSSL bindings right now, the
expected cffi one, and an optional one hidden in asn1crypto. asn1crypto
contains a lot of things that cryptography.io doesn't use, including a
BER parser and a hand-rolled and not constant-time EC implementation.

Instead, check in a much small DER-only parser in cryptography/hazmat. A
quick benchmark suggests this parser is also faster than asn1crypto:

  from __future__ import absolute_import, division, print_function
  import timeit

  print(timeit.timeit(
      "decode_dss_signature(sig)",
      setup=r"""
  from cryptography.hazmat.primitives.asymmetric.utils import decode_dss_signature
  sig=b"\x30\x2d\x02\x15\x00\xb5\xaf\x30\x78\x67\xfb\x8b\x54\x39\x00\x13\xcc\x67\x02\x0d\xdf\x1f\x2c\x0b\x81\x02\x14\x62\x0d\x3b\x22\xab\x50\x31\x44\x0c\x3e\x35\xea\xb6\xf4\x81\x29\x8f\x9e\x9f\x08"
  """,
      number=10000))

Python 2.7:
  asn1crypto: 0.25
  _der.py: 0.098

Python 3.5:
  asn1crypto: 0.17
  _der.py: 0.10

* Remove test dependencies on asn1crypto.

The remaining use of asn1crypto was some sanity-checking of
Certificates. Add a minimal X.509 parser to extract the relevant fields.

* Add a read_single_element helper function.

The outermost read is a little tedious.

* Address flake8 warnings

* Fix test for long-form vs short-form lengths.

Testing a zero length trips both this check and the non-minimal long
form check. Use a one-byte length to cover the missing branch.

* Remove support for negative integers.

These never come up in valid signatures. Note, however, this does
change public API.

* Update src/cryptography/hazmat/primitives/asymmetric/utils.py

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

* Review comments

* Avoid hardcoding the serialization of NULL in decode_asn1.py too.

5 files changed, 208 insertions, 34 deletions

diff --git a/src/cryptography/hazmat/_der.py b/src/cryptography/hazmat/_der.py
new file mode 100644
index 00000000..3a121a85
--- /dev/null
+++ b/src/cryptography/hazmat/_der.py
@@ -0,0 +1,150 @@
+# This file is dual licensed under the terms of the Apache License, Version
+# 2.0, and the BSD License. See the LICENSE file in the root of this repository
+# for complete details.
+
+from __future__ import absolute_import, division, print_function
+
+import six
+
+from cryptography.utils import int_from_bytes, int_to_bytes
+
+
+# This module contains a lightweight DER encoder and decoder. See X.690 for the
+# specification. This module intentionally does not implement the more complex
+# BER encoding, only DER.
+#
+# Note this implementation treats an element's constructed bit as part of the
+# tag. This is fine for DER, where the bit is always computable from the type.
+
+
+CONSTRUCTED = 0x20
+CONTEXT_SPECIFIC = 0x80
+
+INTEGER = 0x02
+BIT_STRING = 0x03
+OCTET_STRING = 0x04
+NULL = 0x05
+OBJECT_IDENTIFIER = 0x06
+SEQUENCE = 0x10 | CONSTRUCTED
+SET = 0x11 | CONSTRUCTED
+PRINTABLE_STRING = 0x13
+UTC_TIME = 0x17
+GENERALIZED_TIME = 0x18
+
+
+class DERReader(object):
+    def __init__(self, data):
+        self.data = memoryview(data)
+
+    def is_empty(self):
+        return len(self.data) == 0
+
+    def check_empty(self):
+        if not self.is_empty():
+            raise ValueError("Invalid DER input: trailing data")
+
+    def read_byte(self):
+        if len(self.data) < 1:
+            raise ValueError("Invalid DER input: insufficient data")
+        ret = six.indexbytes(self.data, 0)
+        self.data = self.data[1:]
+        return ret
+
+    def read_bytes(self, n):
+        if len(self.data) < n:
+            raise ValueError("Invalid DER input: insufficient data")
+        ret = self.data[:n]
+        self.data = self.data[n:]
+        return ret
+
+    def read_any_element(self):
+        tag = self.read_byte()
+        # Tag numbers 31 or higher are stored in multiple bytes. No supported
+        # ASN.1 types use such tags, so reject these.
+        if tag & 0x1f == 0x1f:
+            raise ValueError("Invalid DER input: unexpected high tag number")
+        length_byte = self.read_byte()
+        if length_byte & 0x80 == 0:
+            # If the high bit is clear, the first length byte is the length.
+            length = length_byte
+        else:
+            # If the high bit is set, the first length byte encodes the length
+            # of the length.
+            length_byte &= 0x7f
+            if length_byte == 0:
+                raise ValueError(
+                    "Invalid DER input: indefinite length form is not allowed "
+                    "in DER"
+                )
+            length = 0
+            for i in range(length_byte):
+                length <<= 8
+                length |= self.read_byte()
+                if length == 0:
+                    raise ValueError(
+                        "Invalid DER input: length was not minimally-encoded"
+                    )
+            if length < 0x80:
+                # If the length could have been encoded in short form, it must
+                # not use long form.
+                raise ValueError(
+                    "Invalid DER input: length was not minimally-encoded"
+                )
+        body = self.read_bytes(length)
+        return tag, DERReader(body)
+
+    def read_element(self, expected_tag):
+        tag, body = self.read_any_element()
+        if tag != expected_tag:
+            raise ValueError("Invalid DER input: unexpected tag")
+        return body
+
+    def read_single_element(self, expected_tag):
+        ret = self.read_element(expected_tag)
+        self.check_empty()
+        return ret
+
+    def read_optional_element(self, expected_tag):
+        if len(self.data) > 0 and six.indexbytes(self.data, 0) == expected_tag:
+            return self.read_element(expected_tag)
+        return None
+
+    def as_integer(self):
+        if len(self.data) == 0:
+            raise ValueError("Invalid DER input: empty integer contents")
+        first = six.indexbytes(self.data, 0)
+        if first & 0x80 == 0x80:
+            raise ValueError("Negative DER integers are not supported")
+        # The first 9 bits must not all be zero or all be ones. Otherwise, the
+        # encoding should have been one byte shorter.
+        if len(self.data) > 1:
+            second = six.indexbytes(self.data, 1)
+            if first == 0 and second & 0x80 == 0:
+                raise ValueError(
+                    "Invalid DER input: integer not minimally-encoded"
+                )
+        return int_from_bytes(self.data, "big")
+
+
+def encode_der_integer(x):
+    if not isinstance(x, six.integer_types):
+        raise ValueError("Value must be an integer")
+    if x < 0:
+        raise ValueError("Negative integers are not supported")
+    n = x.bit_length() // 8 + 1
+    return int_to_bytes(x, n)
+
+
+def encode_der(tag, *children):
+    length = 0
+    for child in children:
+        length += len(child)
+    chunks = [six.int2byte(tag)]
+    if length < 0x80:
+        chunks.append(six.int2byte(length))
+    else:
+        length_bytes = int_to_bytes(length)
+        chunks.append(six.int2byte(0x80 | len(length_bytes)))
+        chunks.append(length_bytes)
+    chunks.extend(children)
+    return b"".join(chunks)
diff --git a/src/cryptography/hazmat/backends/openssl/backend.py b/src/cryptography/hazmat/backends/openssl/backend.py
index ca8b1b62..eb6654b0 100644
--- a/src/cryptography/hazmat/backends/openssl/backend.py
+++ b/src/cryptography/hazmat/backends/openssl/backend.py
@@ -10,13 +10,14 @@ import contextlib
 import itertools
 from contextlib import contextmanager
 
-import asn1crypto.core
-
 import six
 from six.moves import range
 
 from cryptography import utils, x509
 from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
+from cryptography.hazmat._der import (
+    INTEGER, NULL, SEQUENCE, encode_der, encode_der_integer
+)
 from cryptography.hazmat.backends.interfaces import (
     CMACBackend, CipherBackend, DERSerializationBackend, DHBackend, DSABackend,
     EllipticCurveBackend, HMACBackend, HashBackend, PBKDF2HMACBackend,
@@ -26,7 +27,7 @@ from cryptography.hazmat.backends.openssl import aead
 from cryptography.hazmat.backends.openssl.ciphers import _CipherContext
 from cryptography.hazmat.backends.openssl.cmac import _CMACContext
 from cryptography.hazmat.backends.openssl.decode_asn1 import (
-    _CRL_ENTRY_REASON_ENUM_TO_CODE, _Integers
+    _CRL_ENTRY_REASON_ENUM_TO_CODE
 )
 from cryptography.hazmat.backends.openssl.dh import (
     _DHParameters, _DHPrivateKey, _DHPublicKey, _dh_params_dup
@@ -1008,12 +1009,17 @@ class Backend(object):
             value = _encode_asn1_str_gc(self, extension.value.value)
             return self._create_raw_x509_extension(extension, value)
         elif isinstance(extension.value, x509.TLSFeature):
-            asn1 = _Integers([x.value for x in extension.value]).dump()
+            asn1 = encode_der(
+                SEQUENCE,
+                *[
+                    encode_der(INTEGER, encode_der_integer(x.value))
+                    for x in extension.value
+                ]
+            )
             value = _encode_asn1_str_gc(self, asn1)
             return self._create_raw_x509_extension(extension, value)
         elif isinstance(extension.value, x509.PrecertPoison):
-            asn1 = asn1crypto.core.Null().dump()
-            value = _encode_asn1_str_gc(self, asn1)
+            value = _encode_asn1_str_gc(self, encode_der(NULL))
             return self._create_raw_x509_extension(extension, value)
         else:
             try:
diff --git a/src/cryptography/hazmat/backends/openssl/decode_asn1.py b/src/cryptography/hazmat/backends/openssl/decode_asn1.py
index 75d5844b..35295ce3 100644
--- a/src/cryptography/hazmat/backends/openssl/decode_asn1.py
+++ b/src/cryptography/hazmat/backends/openssl/decode_asn1.py
@@ -7,11 +7,10 @@ from __future__ import absolute_import, division, print_function
 import datetime
 import ipaddress
 
-import asn1crypto.core
-
 import six
 
 from cryptography import x509
+from cryptography.hazmat._der import DERReader, INTEGER, NULL, SEQUENCE
 from cryptography.x509.extensions import _TLS_FEATURE_TYPE_TO_ENUM
 from cryptography.x509.name import _ASN1_TYPE_TO_ENUM
 from cryptography.x509.oid import (
@@ -20,10 +19,6 @@ from cryptography.x509.oid import (
 )
 
 
-class _Integers(asn1crypto.core.SequenceOf):
-    _child_spec = asn1crypto.core.Integer
-
-
 def _obj2txt(backend, obj):
     # Set to 80 on the recommendation of
     # https://www.openssl.org/docs/crypto/OBJ_nid2ln.html#return_values
@@ -209,20 +204,25 @@ class _X509ExtensionParser(object):
             # to support them in all versions of OpenSSL so we decode them
             # ourselves.
             if oid == ExtensionOID.TLS_FEATURE:
+                # The extension contents are a SEQUENCE OF INTEGERs.
                 data = backend._lib.X509_EXTENSION_get_data(ext)
-                parsed = _Integers.load(_asn1_string_to_bytes(backend, data))
+                data_bytes = _asn1_string_to_bytes(backend, data)
+                features = DERReader(data_bytes).read_single_element(SEQUENCE)
+                parsed = []
+                while not features.is_empty():
+                    parsed.append(features.read_element(INTEGER).as_integer())
+                # Map the features to their enum value.
                 value = x509.TLSFeature(
-                    [_TLS_FEATURE_TYPE_TO_ENUM[x.native] for x in parsed]
+                    [_TLS_FEATURE_TYPE_TO_ENUM[x] for x in parsed]
                 )
                 extensions.append(x509.Extension(oid, critical, value))
                 seen_oids.add(oid)
                 continue
             elif oid == ExtensionOID.PRECERT_POISON:
                 data = backend._lib.X509_EXTENSION_get_data(ext)
-                parsed = asn1crypto.core.Null.load(
-                    _asn1_string_to_bytes(backend, data)
-                )
-                assert parsed == asn1crypto.core.Null()
+                # The contents of the extension must be an ASN.1 NULL.
+                reader = DERReader(_asn1_string_to_bytes(backend, data))
+                reader.read_single_element(NULL).check_empty()
                 extensions.append(x509.Extension(
                     oid, critical, x509.PrecertPoison()
                 ))
diff --git a/src/cryptography/hazmat/primitives/asymmetric/utils.py b/src/cryptography/hazmat/primitives/asymmetric/utils.py
index 274c1f41..43d5b9bf 100644
--- a/src/cryptography/hazmat/primitives/asymmetric/utils.py
+++ b/src/cryptography/hazmat/primitives/asymmetric/utils.py
@@ -4,27 +4,27 @@
 
 from __future__ import absolute_import, division, print_function
 
-from asn1crypto.algos import DSASignature
-
-import six
-
 from cryptography import utils
+from cryptography.hazmat._der import (
+    DERReader, INTEGER, SEQUENCE, encode_der, encode_der_integer
+)
 from cryptography.hazmat.primitives import hashes
 
 
 def decode_dss_signature(signature):
-    data = DSASignature.load(signature, strict=True).native
-    return data['r'], data['s']
+    seq = DERReader(signature).read_single_element(SEQUENCE)
+    r = seq.read_element(INTEGER).as_integer()
+    s = seq.read_element(INTEGER).as_integer()
+    seq.check_empty()
+    return r, s
 
 
 def encode_dss_signature(r, s):
-    if (
-        not isinstance(r, six.integer_types) or
-        not isinstance(s, six.integer_types)
-    ):
-        raise ValueError("Both r and s must be integers")
-
-    return DSASignature({'r': r, 's': s}).dump()
+    return encode_der(
+        SEQUENCE,
+        encode_der(INTEGER, encode_der_integer(r)),
+        encode_der(INTEGER, encode_der_integer(s)),
+    )
 
 
 class Prehashed(object):
diff --git a/src/cryptography/x509/extensions.py b/src/cryptography/x509/extensions.py
index d25131b8..c78c76c2 100644
--- a/src/cryptography/x509/extensions.py
+++ b/src/cryptography/x509/extensions.py
@@ -11,11 +11,12 @@ import ipaddress
 import warnings
 from enum import Enum
 
-from asn1crypto.keys import PublicKeyInfo
-
 import six
 
 from cryptography import utils
+from cryptography.hazmat._der import (
+    BIT_STRING, DERReader, OBJECT_IDENTIFIER, SEQUENCE
+)
 from cryptography.hazmat.primitives import constant_time, serialization
 from cryptography.hazmat.primitives.asymmetric.ec import EllipticCurvePublicKey
 from cryptography.hazmat.primitives.asymmetric.rsa import RSAPublicKey
@@ -47,7 +48,24 @@ def _key_identifier_from_public_key(public_key):
             serialization.PublicFormat.SubjectPublicKeyInfo
         )
 
-        data = bytes(PublicKeyInfo.load(serialized)['public_key'])
+        public_key_info = DERReader(serialized).read_single_element(SEQUENCE)
+        algorithm = public_key_info.read_element(SEQUENCE)
+        public_key = public_key_info.read_element(BIT_STRING)
+        public_key_info.check_empty()
+
+        # Double-check the algorithm structure.
+        algorithm.read_element(OBJECT_IDENTIFIER)
+        if not algorithm.is_empty():
+            # Skip the optional parameters field.
+            algorithm.read_any_element()
+        algorithm.check_empty()
+
+        # BIT STRING contents begin with the number of padding bytes added. It
+        # must be zero for SubjectPublicKeyInfo structures.
+        if public_key.read_byte() != 0:
+            raise ValueError('Invalid public key encoding')
+
+        data = public_key.data
 
     return hashlib.sha1(data).digest()