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.

3 files changed, 298 insertions, 26 deletions

diff --git a/tests/hazmat/primitives/test_asym_utils.py b/tests/hazmat/primitives/test_asym_utils.py
index d817c651..b49ca3f2 100644
--- a/tests/hazmat/primitives/test_asym_utils.py
+++ b/tests/hazmat/primitives/test_asym_utils.py
@@ -31,10 +31,6 @@ def test_dss_signature():
     assert sig3 == b"0\x06\x02\x01\x00\x02\x01\x00"
     assert decode_dss_signature(sig3) == (0, 0)
 
-    sig4 = encode_dss_signature(-1, 0)
-    assert sig4 == b"0\x06\x02\x01\xFF\x02\x01\x00"
-    assert decode_dss_signature(sig4) == (-1, 0)
-
 
 def test_encode_dss_non_integer():
     with pytest.raises(ValueError):
@@ -53,6 +49,11 @@ def test_encode_dss_non_integer():
         encode_dss_signature("hello", "world")
 
 
+def test_encode_dss_negative():
+    with pytest.raises(ValueError):
+        encode_dss_signature(-1, 0)
+
+
 def test_decode_dss_trailing_bytes():
     with pytest.raises(ValueError):
         decode_dss_signature(b"0\x06\x02\x01\x01\x02\x01\x01\x00\x00\x00")
diff --git a/tests/hazmat/test_der.py b/tests/hazmat/test_der.py
new file mode 100644
index 00000000..d81c0d3e
--- /dev/null
+++ b/tests/hazmat/test_der.py
@@ -0,0 +1,217 @@
+# 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 pytest
+
+from cryptography.hazmat._der import (
+    DERReader, INTEGER, NULL, OCTET_STRING, SEQUENCE, encode_der,
+    encode_der_integer
+)
+
+
+def test_der_reader_basic():
+    reader = DERReader(b"123456789")
+    assert reader.read_byte() == ord(b"1")
+    assert reader.read_bytes(1).tobytes() == b"2"
+    assert reader.read_bytes(4).tobytes() == b"3456"
+
+    with pytest.raises(ValueError):
+        reader.read_bytes(4)
+
+    assert reader.read_bytes(3).tobytes() == b"789"
+
+    # The input is now empty.
+    with pytest.raises(ValueError):
+        reader.read_bytes(1)
+    with pytest.raises(ValueError):
+        reader.read_byte()
+
+
+def test_der():
+    # This input is the following structure, using
+    # https://github.com/google/der-ascii
+    #
+    # SEQUENCE {
+    #   SEQUENCE {
+    #     NULL {}
+    #     INTEGER { 42 }
+    #     OCTET_STRING { "hello" }
+    #   }
+    # }
+    der = b"\x30\x0e\x30\x0c\x05\x00\x02\x01\x2a\x04\x05\x68\x65\x6c\x6c\x6f"
+    reader = DERReader(der)
+    with pytest.raises(ValueError):
+        reader.check_empty()
+
+    # Parse the outer element.
+    outer = reader.read_element(SEQUENCE)
+    reader.check_empty()
+    assert outer.data.tobytes() == der[2:]
+
+    # Parse the outer element with read_any_element.
+    reader = DERReader(der)
+    tag, outer2 = reader.read_any_element()
+    reader.check_empty()
+    assert tag == SEQUENCE
+    assert outer2.data.tobytes() == der[2:]
+
+    # Parse the outer element with read_single_element.
+    outer3 = DERReader(der).read_single_element(SEQUENCE)
+    assert outer3.data.tobytes() == der[2:]
+
+    # read_single_element rejects trailing data.
+    with pytest.raises(ValueError):
+        DERReader(der + der).read_single_element(SEQUENCE)
+
+    # Continue parsing the structure.
+    inner = outer.read_element(SEQUENCE)
+    outer.check_empty()
+
+    # Parsing a missing optional element should work.
+    assert inner.read_optional_element(INTEGER) is None
+
+    null = inner.read_element(NULL)
+    null.check_empty()
+
+    # Parsing a present optional element should work.
+    integer = inner.read_optional_element(INTEGER)
+    assert integer.as_integer() == 42
+
+    octet_string = inner.read_element(OCTET_STRING)
+    assert octet_string.data.tobytes() == b"hello"
+
+    # Parsing a missing optional element should work when the input is empty.
+    inner.check_empty()
+    assert inner.read_optional_element(INTEGER) is None
+
+    # Re-encode the same structure.
+    der2 = encode_der(
+        SEQUENCE,
+        encode_der(
+            SEQUENCE,
+            encode_der(NULL),
+            encode_der(INTEGER, encode_der_integer(42)),
+            encode_der(OCTET_STRING, b"hello"),
+        )
+    )
+    assert der2 == der
+
+
+@pytest.mark.parametrize(
+    "length,header",
+    [
+        # Single-byte lengths.
+        (0, b"\x04\x00"),
+        (1, b"\x04\x01"),
+        (2, b"\x04\x02"),
+        (127, b"\x04\x7f"),
+        # Long-form lengths.
+        (128, b"\x04\x81\x80"),
+        (129, b"\x04\x81\x81"),
+        (255, b"\x04\x81\xff"),
+        (0x100, b"\x04\x82\x01\x00"),
+        (0x101, b"\x04\x82\x01\x01"),
+        (0xffff, b"\x04\x82\xff\xff"),
+        (0x10000, b"\x04\x83\x01\x00\x00"),
+    ]
+)
+def test_der_lengths(length, header):
+    body = length * b"a"
+    der = header + body
+
+    reader = DERReader(der)
+    element = reader.read_element(OCTET_STRING)
+    reader.check_empty()
+    assert element.data.tobytes() == body
+
+    assert encode_der(OCTET_STRING, body) == der
+
+
+@pytest.mark.parametrize(
+    "bad_input",
+    [
+        # The input ended before the tag.
+        b"",
+        # The input ended before the length.
+        b"\x30",
+        # The input ended before the second byte of the length.
+        b"\x30\x81",
+        # The input ended before the body.
+        b"\x30\x01",
+        # The length used long form when it should be short form.
+        b"\x30\x81\x01\x00",
+        # The length was not minimally-encoded.
+        b"\x30\x82\x00\x80" + (0x80 * b"a"),
+        # Indefinite-length encoding is not valid DER.
+        b"\x30\x80\x00\x00"
+        # Tag number (the bottom 5 bits) 31 indicates long form tags, which we
+        # do not support.
+        b"\x1f\x00",
+        b"\x9f\x00",
+        b"\xbf\x00",
+        b"\xff\x00",
+    ]
+)
+def test_der_reader_bad_input(bad_input):
+    reader = DERReader(bad_input)
+    with pytest.raises(ValueError):
+        reader.read_any_element()
+
+
+def test_der_reader_wrong_tag():
+    reader = DERReader(b"\x04\x00")
+    with pytest.raises(ValueError):
+        reader.read_element(SEQUENCE)
+
+
+@pytest.mark.parametrize(
+    "value,der",
+    [
+        (0, b'\x00'),
+        (1, b'\x01'),
+        (2, b'\x02'),
+        (3, b'\x03'),
+        (127, b'\x7f'),
+        (128, b'\x00\x80'),
+        (0x112233445566778899aabbccddeeff,
+         b'\x11\x22\x33\x44\x55\x66\x77\x88\x99\xaa\xbb\xcc\xdd\xee\xff'),
+    ]
+)
+def test_integer(value, der):
+    assert encode_der_integer(value) == der
+    assert DERReader(der).as_integer() == value
+
+
+@pytest.mark.parametrize(
+    "bad_input",
+    [
+        # Zero is encoded as b"\x00", not the empty string.
+        b"",
+        # Too many leading zeros.
+        b"\x00\x00",
+        b"\x00\x7f",
+        # Too many leading ones.
+        b"\xff\xff",
+        b"\xff\x80",
+        # Negative integers are not supported.
+        b"\x80",
+        b"\x81",
+        b"\x80\x00\x00",
+        b"\xff",
+    ]
+)
+def test_invalid_integer(bad_input):
+    reader = DERReader(bad_input)
+    with pytest.raises(ValueError):
+        reader.as_integer()
+
+
+def test_invalid_integer_encode():
+    with pytest.raises(ValueError):
+        encode_der_integer(-1)
+
+    with pytest.raises(ValueError):
+        encode_der_integer("not an integer")
diff --git a/tests/x509/test_x509.py b/tests/x509/test_x509.py
index 20e23d5f..bb0ad022 100644
--- a/tests/x509/test_x509.py
+++ b/tests/x509/test_x509.py
@@ -6,12 +6,11 @@
 from __future__ import absolute_import, division, print_function
 
 import binascii
+import collections
 import datetime
 import ipaddress
 import os
 
-from asn1crypto.x509 import Certificate
-
 import pytest
 
 import pytz
@@ -20,6 +19,10 @@ import six
 
 from cryptography import utils, x509
 from cryptography.exceptions import UnsupportedAlgorithm
+from cryptography.hazmat._der import (
+    BIT_STRING, CONSTRUCTED, CONTEXT_SPECIFIC, DERReader, GENERALIZED_TIME,
+    INTEGER, OBJECT_IDENTIFIER, PRINTABLE_STRING, SEQUENCE, SET, UTC_TIME
+)
 from cryptography.hazmat.backends.interfaces import (
     DSABackend, EllipticCurveBackend, RSABackend, X509Backend
 )
@@ -65,6 +68,53 @@ def _load_cert(filename, loader, backend):
     return cert
 
 
+ParsedCertificate = collections.namedtuple(
+    "ParsedCertificate",
+    ["not_before_tag", "not_after_tag", "issuer", "subject"]
+)
+
+
+def _parse_cert(der):
+    # See the Certificate structured, defined in RFC 5280.
+    cert = DERReader(der).read_single_element(SEQUENCE)
+    tbs_cert = cert.read_element(SEQUENCE)
+    # Skip outer signature algorithm
+    _ = cert.read_element(SEQUENCE)
+    # Skip signature
+    _ = cert.read_element(BIT_STRING)
+    cert.check_empty()
+
+    # Skip version
+    _ = tbs_cert.read_optional_element(CONTEXT_SPECIFIC | CONSTRUCTED | 0)
+    # Skip serialNumber
+    _ = tbs_cert.read_element(INTEGER)
+    # Skip inner signature algorithm
+    _ = tbs_cert.read_element(SEQUENCE)
+    issuer = tbs_cert.read_element(SEQUENCE)
+    validity = tbs_cert.read_element(SEQUENCE)
+    subject = tbs_cert.read_element(SEQUENCE)
+    # Skip subjectPublicKeyInfo
+    _ = tbs_cert.read_element(SEQUENCE)
+    # Skip issuerUniqueID
+    _ = tbs_cert.read_optional_element(CONTEXT_SPECIFIC | CONSTRUCTED | 1)
+    # Skip subjectUniqueID
+    _ = tbs_cert.read_optional_element(CONTEXT_SPECIFIC | CONSTRUCTED | 2)
+    # Skip extensions
+    _ = tbs_cert.read_optional_element(CONTEXT_SPECIFIC | CONSTRUCTED | 3)
+    tbs_cert.check_empty()
+
+    not_before_tag, _ = validity.read_any_element()
+    not_after_tag, _ = validity.read_any_element()
+    validity.check_empty()
+
+    return ParsedCertificate(
+        not_before_tag=not_before_tag,
+        not_after_tag=not_after_tag,
+        issuer=issuer,
+        subject=subject,
+    )
+
+
 @pytest.mark.requires_backend_interface(interface=X509Backend)
 class TestCertificateRevocationList(object):
     def test_load_pem_crl(self, backend):
@@ -1587,12 +1637,24 @@ class TestRSACertificateRequest(object):
 
         cert = builder.sign(issuer_private_key, hashes.SHA256(), backend)
 
-        parsed = Certificate.load(
-            cert.public_bytes(serialization.Encoding.DER))
+        parsed = _parse_cert(cert.public_bytes(serialization.Encoding.DER))
+        subject = parsed.subject
+        issuer = parsed.issuer
+
+        def read_next_rdn_value_tag(reader):
+            rdn = reader.read_element(SET)
+            attribute = rdn.read_element(SEQUENCE)
+            # Assume each RDN has a single attribute.
+            rdn.check_empty()
+
+            _ = attribute.read_element(OBJECT_IDENTIFIER)
+            tag, value = attribute.read_any_element()
+            attribute.check_empty()
+            return tag
 
         # Check that each value was encoded as an ASN.1 PRINTABLESTRING.
-        assert parsed.subject.chosen[0][0]['value'].chosen.tag == 19
-        assert parsed.issuer.chosen[0][0]['value'].chosen.tag == 19
+        assert read_next_rdn_value_tag(subject) == PRINTABLE_STRING
+        assert read_next_rdn_value_tag(issuer) == PRINTABLE_STRING
         if (
             # This only works correctly in OpenSSL 1.1.0f+ and 1.0.2l+
             backend._lib.CRYPTOGRAPHY_OPENSSL_110F_OR_GREATER or (
@@ -1600,8 +1662,8 @@ class TestRSACertificateRequest(object):
                 not backend._lib.CRYPTOGRAPHY_OPENSSL_110_OR_GREATER
             )
         ):
-            assert parsed.subject.chosen[1][0]['value'].chosen.tag == 19
-            assert parsed.issuer.chosen[1][0]['value'].chosen.tag == 19
+            assert read_next_rdn_value_tag(subject) == PRINTABLE_STRING
+            assert read_next_rdn_value_tag(issuer) == PRINTABLE_STRING
 
 
 class TestCertificateBuilder(object):
@@ -1738,13 +1800,9 @@ class TestCertificateBuilder(object):
         cert = builder.sign(private_key, hashes.SHA256(), backend)
         assert cert.not_valid_before == not_valid_before
         assert cert.not_valid_after == not_valid_after
-        parsed = Certificate.load(
-            cert.public_bytes(serialization.Encoding.DER)
-        )
-        not_before = parsed['tbs_certificate']['validity']['not_before']
-        not_after = parsed['tbs_certificate']['validity']['not_after']
-        assert not_before.chosen.tag == 23  # UTCTime
-        assert not_after.chosen.tag == 24  # GeneralizedTime
+        parsed = _parse_cert(cert.public_bytes(serialization.Encoding.DER))
+        assert parsed.not_before_tag == UTC_TIME
+        assert parsed.not_after_tag == GENERALIZED_TIME
 
     @pytest.mark.requires_backend_interface(interface=RSABackend)
     @pytest.mark.requires_backend_interface(interface=X509Backend)
@@ -2038,13 +2096,9 @@ class TestCertificateBuilder(object):
         cert = cert_builder.sign(private_key, hashes.SHA256(), backend)
         assert cert.not_valid_before == time
         assert cert.not_valid_after == time
-        parsed = Certificate.load(
-            cert.public_bytes(serialization.Encoding.DER)
-        )
-        not_before = parsed['tbs_certificate']['validity']['not_before']
-        not_after = parsed['tbs_certificate']['validity']['not_after']
-        assert not_before.chosen.tag == 23  # UTCTime
-        assert not_after.chosen.tag == 23  # UTCTime
+        parsed = _parse_cert(cert.public_bytes(serialization.Encoding.DER))
+        assert parsed.not_before_tag == UTC_TIME
+        assert parsed.not_after_tag == UTC_TIME
 
     def test_invalid_not_valid_after(self):
         with pytest.raises(TypeError):