Begin the deprecation of auto-idna for x509.DNSName (#3830)

* Begin the deprecation of auto-idna for x509.DNSName

Refs #3357

* fix warning

* py3k fixes

* fix docs

* sigh

* flake8

* these are words

* words

* tests for coverage

* another test

* do idna things

* more idna things
diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index ac83092..d7f2e42 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -9,6 +9,12 @@
 * **BACKWARDS INCOMPATIBLE:** ``Whirlpool``, ``RIPEMD160``, and
   ``UnsupportedExtension`` have been removed in accordance with our
   :doc:`/api-stability` policy.
+* Deprecated passing unicode to the :class:`~cryptography.x509.DNSName`
+  constructor. Instead, users should pass DNS names as ``bytes``, with ``idna``
+  encoding if necessary. In addition, the
+  :attr:`~cryptography.x509.DNSName.value` attribute was deprecated, users
+  should use :attr:`~cryptography.x509.DNSName.bytes_value` to access the
+  raw DNS name.
 
 2.0.2 - 2017-07-27
 ~~~~~~~~~~~~~~~~~~
diff --git a/docs/spelling_wordlist.txt b/docs/spelling_wordlist.txt
index 3ebc63d..f72e0b0 100644
--- a/docs/spelling_wordlist.txt
+++ b/docs/spelling_wordlist.txt
@@ -1,3 +1,4 @@
+accessor
 affine
 Authenticator
 backend
@@ -43,6 +44,7 @@
 hazmat
 Homebrew
 hostname
+idna
 indistinguishability
 initialisms
 interoperable
diff --git a/docs/x509/reference.rst b/docs/x509/reference.rst
index 7cc7271..c2ff0ff 100644
--- a/docs/x509/reference.rst
+++ b/docs/x509/reference.rst
@@ -599,7 +599,7 @@
         >>> builder = builder.public_key(public_key)
         >>> builder = builder.add_extension(
         ...     x509.SubjectAlternativeName(
-        ...         [x509.DNSName(u'cryptography.io')]
+        ...         [x509.DNSName(b'cryptography.io')]
         ...     ),
         ...     critical=False
         ... )
@@ -1242,8 +1242,14 @@
 
     This corresponds to a domain name. For example, ``cryptography.io``.
 
+    .. attribute:: bytes_value
+
+        :type: bytes
+
     .. attribute:: value
 
+        Deprecated accessor for the idna-decoded value of :attr:`bytes_value`
+
         :type: :term:`text`
 
 .. class:: DirectoryName(value)
diff --git a/docs/x509/tutorial.rst b/docs/x509/tutorial.rst
index d34b350..0492c9a 100644
--- a/docs/x509/tutorial.rst
+++ b/docs/x509/tutorial.rst
@@ -70,9 +70,9 @@
     ... ])).add_extension(
     ...     x509.SubjectAlternativeName([
     ...         # Describe what sites we want this certificate for.
-    ...         x509.DNSName(u"mysite.com"),
-    ...         x509.DNSName(u"www.mysite.com"),
-    ...         x509.DNSName(u"subdomain.mysite.com"),
+    ...         x509.DNSName(b"mysite.com"),
+    ...         x509.DNSName(b"www.mysite.com"),
+    ...         x509.DNSName(b"subdomain.mysite.com"),
     ...     ]),
     ...     critical=False,
     ... # Sign the CSR with our private key.
@@ -142,7 +142,7 @@
     ...     # Our certificate will be valid for 10 days
     ...     datetime.datetime.utcnow() + datetime.timedelta(days=10)
     ... ).add_extension(
-    ...     x509.SubjectAlternativeName([x509.DNSName(u"localhost")]),
+    ...     x509.SubjectAlternativeName([x509.DNSName(b"localhost")]),
     ...     critical=False,
     ... # Sign our certificate with our private key
     ... ).sign(key, hashes.SHA256(), default_backend())
diff --git a/src/cryptography/hazmat/backends/openssl/decode_asn1.py b/src/cryptography/hazmat/backends/openssl/decode_asn1.py
index a55b588..a66f65f 100644
--- a/src/cryptography/hazmat/backends/openssl/decode_asn1.py
+++ b/src/cryptography/hazmat/backends/openssl/decode_asn1.py
@@ -88,23 +88,7 @@
 def _decode_general_name(backend, gn):
     if gn.type == backend._lib.GEN_DNS:
         data = _asn1_string_to_bytes(backend, gn.d.dNSName)
-        if not data:
-            decoded = u""
-        elif data.startswith(b"*."):
-            # This is a wildcard name. We need to remove the leading wildcard,
-            # IDNA decode, then re-add the wildcard. Wildcard characters should
-            # always be left-most (RFC 2595 section 2.4).
-            decoded = u"*." + idna.decode(data[2:])
-        else:
-            # Not a wildcard, decode away. If the string has a * in it anywhere
-            # invalid this will raise an InvalidCodePoint
-            decoded = idna.decode(data)
-            if data.startswith(b"."):
-                # idna strips leading periods. Name constraints can have that
-                # so we need to re-add it. Sigh.
-                decoded = u"." + decoded
-
-        return x509.DNSName(decoded)
+        return x509.DNSName(data)
     elif gn.type == backend._lib.GEN_URI:
         data = _asn1_string_to_ascii(backend, gn.d.uniformResourceIdentifier)
         parsed = urllib_parse.urlparse(data)
diff --git a/src/cryptography/hazmat/backends/openssl/encode_asn1.py b/src/cryptography/hazmat/backends/openssl/encode_asn1.py
index 399000a..77d2212 100644
--- a/src/cryptography/hazmat/backends/openssl/encode_asn1.py
+++ b/src/cryptography/hazmat/backends/openssl/encode_asn1.py
@@ -7,8 +7,6 @@
 import calendar
 import ipaddress
 
-import idna
-
 import six
 
 from cryptography import utils, x509
@@ -370,15 +368,6 @@
     return _encode_asn1_str_gc(backend, ski.digest, len(ski.digest))
 
 
-def _idna_encode(value):
-    # Retain prefixes '*.' for common/alt names and '.' for name constraints
-    for prefix in ['*.', '.']:
-        if value.startswith(prefix):
-            value = value[len(prefix):]
-            return prefix.encode('ascii') + idna.encode(value)
-    return idna.encode(value)
-
-
 def _encode_general_name(backend, name):
     if isinstance(name, x509.DNSName):
         gn = backend._lib.GENERAL_NAME_new()
@@ -387,7 +376,7 @@
 
         ia5 = backend._lib.ASN1_IA5STRING_new()
         backend.openssl_assert(ia5 != backend._ffi.NULL)
-        value = _idna_encode(name.value)
+        value = name.bytes_value
 
         res = backend._lib.ASN1_STRING_set(ia5, value, len(value))
         backend.openssl_assert(res == 1)
diff --git a/src/cryptography/utils.py b/src/cryptography/utils.py
index efb12e2..02857c0 100644
--- a/src/cryptography/utils.py
+++ b/src/cryptography/utils.py
@@ -16,6 +16,7 @@
 # cycle ends.
 PersistentlyDeprecated = DeprecationWarning
 DeprecatedIn19 = DeprecationWarning
+DeprecatedIn21 = PendingDeprecationWarning
 
 
 def _check_bytes(name, value):
diff --git a/src/cryptography/x509/general_name.py b/src/cryptography/x509/general_name.py
index 6745243..9ea1cff 100644
--- a/src/cryptography/x509/general_name.py
+++ b/src/cryptography/x509/general_name.py
@@ -6,6 +6,7 @@
 
 import abc
 import ipaddress
+import warnings
 from email.utils import parseaddr
 
 import idna
@@ -89,24 +90,81 @@
         return hash(self.value)
 
 
+def _idna_encode(value):
+    # Retain prefixes '*.' for common/alt names and '.' for name constraints
+    for prefix in ['*.', '.']:
+        if value.startswith(prefix):
+            value = value[len(prefix):]
+            return prefix.encode('ascii') + idna.encode(value)
+    return idna.encode(value)
+
+
 @utils.register_interface(GeneralName)
 class DNSName(object):
     def __init__(self, value):
-        if not isinstance(value, six.text_type):
-            raise TypeError("value must be a unicode string")
+        if isinstance(value, six.text_type):
+            try:
+                value = value.encode("ascii")
+            except UnicodeEncodeError:
+                value = _idna_encode(value)
+                warnings.warn(
+                    "DNSName values should be passed as idna-encoded bytes, "
+                    "not strings. Support for passing unicode strings will be "
+                    "removed in a future version.",
+                    utils.DeprecatedIn21,
+                    stacklevel=2,
+                )
+            else:
+                warnings.warn(
+                    "DNSName values should be passed as bytes, not strings. "
+                    "Support for passing unicode strings will be removed in a "
+                    "future version.",
+                    utils.DeprecatedIn21,
+                    stacklevel=2,
+                )
+        elif not isinstance(value, bytes):
+            raise TypeError("value must be bytes")
 
-        self._value = value
+        self._bytes_value = value
 
-    value = utils.read_only_property("_value")
+    bytes_value = utils.read_only_property("_bytes_value")
+
+    @property
+    def value(self):
+        warnings.warn(
+            "DNSName.bytes_value should be used instead of DNSName.value; it "
+            "contains the DNS name as raw bytes, instead of as an idna-decoded"
+            " unicode string. DNSName.value will be removed in a future "
+            "version.",
+            utils.DeprecatedIn21,
+            stacklevel=2
+        )
+        data = self._bytes_value
+        if not data:
+            decoded = u""
+        elif data.startswith(b"*."):
+            # This is a wildcard name. We need to remove the leading wildcard,
+            # IDNA decode, then re-add the wildcard. Wildcard characters should
+            # always be left-most (RFC 2595 section 2.4).
+            decoded = u"*." + idna.decode(data[2:])
+        else:
+            # Not a wildcard, decode away. If the string has a * in it anywhere
+            # invalid this will raise an InvalidCodePoint
+            decoded = idna.decode(data)
+            if data.startswith(b"."):
+                # idna strips leading periods. Name constraints can have that
+                # so we need to re-add it. Sigh.
+                decoded = u"." + decoded
+        return decoded
 
     def __repr__(self):
-        return "<DNSName(value={0})>".format(self.value)
+        return "<DNSName(bytes_value={0!r})>".format(self.bytes_value)
 
     def __eq__(self, other):
         if not isinstance(other, DNSName):
             return NotImplemented
 
-        return self.value == other.value
+        return self.bytes_value == other.bytes_value
 
     def __ne__(self, other):
         return not self == other
diff --git a/tests/test_x509.py b/tests/test_x509.py
index 41ccbed..661461d 100644
--- a/tests/test_x509.py
+++ b/tests/test_x509.py
@@ -225,7 +225,7 @@
         assert aia.value == x509.AuthorityInformationAccess([
             x509.AccessDescription(
                 AuthorityInformationAccessOID.CA_ISSUERS,
-                x509.DNSName(u"cryptography.io")
+                x509.DNSName(b"cryptography.io")
             )
         ])
         assert ian.value == x509.IssuerAlternativeName([
@@ -1176,8 +1176,8 @@
             ExtensionOID.SUBJECT_ALTERNATIVE_NAME
         )
         assert list(ext.value) == [
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"sub.cryptography.io"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"sub.cryptography.io"),
         ]
 
     def test_public_bytes_pem(self, backend):
@@ -1405,7 +1405,7 @@
         ).add_extension(
             x509.BasicConstraints(ca=False, path_length=None), True,
         ).add_extension(
-            x509.SubjectAlternativeName([x509.DNSName(u"cryptography.io")]),
+            x509.SubjectAlternativeName([x509.DNSName(b"cryptography.io")]),
             critical=False,
         ).not_valid_before(
             not_valid_before
@@ -1427,7 +1427,7 @@
             ExtensionOID.SUBJECT_ALTERNATIVE_NAME
         )
         assert list(subject_alternative_name.value) == [
-            x509.DNSName(u"cryptography.io"),
+            x509.DNSName(b"cryptography.io"),
         ]
 
     def test_build_cert_printable_string_country_name(self, backend):
@@ -2166,7 +2166,7 @@
         ).add_extension(
             x509.BasicConstraints(ca=False, path_length=None), True,
         ).add_extension(
-            x509.SubjectAlternativeName([x509.DNSName(u"cryptography.io")]),
+            x509.SubjectAlternativeName([x509.DNSName(b"cryptography.io")]),
             critical=False,
         ).not_valid_before(
             not_valid_before
@@ -2188,7 +2188,7 @@
             ExtensionOID.SUBJECT_ALTERNATIVE_NAME
         )
         assert list(subject_alternative_name.value) == [
-            x509.DNSName(u"cryptography.io"),
+            x509.DNSName(b"cryptography.io"),
         ]
 
     @pytest.mark.requires_backend_interface(interface=EllipticCurveBackend)
@@ -2212,7 +2212,7 @@
         ).add_extension(
             x509.BasicConstraints(ca=False, path_length=None), True,
         ).add_extension(
-            x509.SubjectAlternativeName([x509.DNSName(u"cryptography.io")]),
+            x509.SubjectAlternativeName([x509.DNSName(b"cryptography.io")]),
             critical=False,
         ).not_valid_before(
             not_valid_before
@@ -2234,7 +2234,7 @@
             ExtensionOID.SUBJECT_ALTERNATIVE_NAME
         )
         assert list(subject_alternative_name.value) == [
-            x509.DNSName(u"cryptography.io"),
+            x509.DNSName(b"cryptography.io"),
         ]
 
     @pytest.mark.requires_backend_interface(interface=RSABackend)
@@ -2375,7 +2375,7 @@
             123
         ).add_extension(
             x509.IssuerAlternativeName([
-                x509.DNSName(u"myissuer"),
+                x509.DNSName(b"myissuer"),
                 x509.RFC822Name(u"email@domain.com"),
             ]), critical=False
         ).sign(issuer_private_key, hashes.SHA256(), backend)
@@ -2385,7 +2385,7 @@
         )
         assert ext.critical is False
         assert ext.value == x509.IssuerAlternativeName([
-            x509.DNSName(u"myissuer"),
+            x509.DNSName(b"myissuer"),
             x509.RFC822Name(u"email@domain.com"),
         ])
 
@@ -2525,7 +2525,7 @@
                         ipaddress.IPv6Network(u"FF:FF:0:0:0:0:0:0/128")
                     ),
                 ],
-                excluded_subtrees=[x509.DNSName(u"name.local")]
+                excluded_subtrees=[x509.DNSName(b"name.local")]
             ),
             x509.NameConstraints(
                 permitted_subtrees=[
@@ -2535,7 +2535,7 @@
             ),
             x509.NameConstraints(
                 permitted_subtrees=None,
-                excluded_subtrees=[x509.DNSName(u"name.local")]
+                excluded_subtrees=[x509.DNSName(b"name.local")]
             ),
         ]
     )
@@ -2909,7 +2909,7 @@
                 x509.NameAttribute(NameOID.COUNTRY_NAME, u'US'),
             ])
         ).add_extension(
-            x509.SubjectAlternativeName([x509.DNSName(u"cryptography.io")]),
+            x509.SubjectAlternativeName([x509.DNSName(b"cryptography.io")]),
             critical=False,
         ).add_extension(
             DummyExtension(), False
@@ -2995,7 +2995,7 @@
         request = builder.subject_name(
             x509.Name([x509.NameAttribute(NameOID.COUNTRY_NAME, u'US')])
         ).add_extension(
-            x509.SubjectAlternativeName([x509.DNSName(u"cryptography.io")]),
+            x509.SubjectAlternativeName([x509.DNSName(b"cryptography.io")]),
             critical=False,
         ).add_extension(
             x509.BasicConstraints(ca=True, path_length=2), critical=True
@@ -3012,7 +3012,7 @@
         ext = request.extensions.get_extension_for_oid(
             ExtensionOID.SUBJECT_ALTERNATIVE_NAME
         )
-        assert list(ext.value) == [x509.DNSName(u"cryptography.io")]
+        assert list(ext.value) == [x509.DNSName(b"cryptography.io")]
 
     def test_set_subject_twice(self):
         builder = x509.CertificateSigningRequestBuilder()
@@ -3032,8 +3032,8 @@
         private_key = RSA_KEY_2048.private_key(backend)
 
         san = x509.SubjectAlternativeName([
-            x509.DNSName(u"example.com"),
-            x509.DNSName(u"*.example.com"),
+            x509.DNSName(b"example.com"),
+            x509.DNSName(b"*.example.com"),
             x509.RegisteredID(x509.ObjectIdentifier("1.2.3.4.5.6.7")),
             x509.DirectoryName(x509.Name([
                 x509.NameAttribute(NameOID.COMMON_NAME, u'PyCA'),
diff --git a/tests/test_x509_ext.py b/tests/test_x509_ext.py
index c324397..b707156 100644
--- a/tests/test_x509_ext.py
+++ b/tests/test_x509_ext.py
@@ -13,7 +13,7 @@
 
 import six
 
-from cryptography import x509
+from cryptography import utils, x509
 from cryptography.hazmat.backends.interfaces import (
     DSABackend, EllipticCurveBackend, RSABackend, X509Backend
 )
@@ -152,20 +152,20 @@
 class TestCertificateIssuer(object):
     def test_iter_names(self):
         ci = x509.CertificateIssuer([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ])
         assert len(ci) == 2
         assert list(ci) == [
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ]
 
     def test_indexing(self):
         ci = x509.CertificateIssuer([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
-            x509.DNSName(u"another.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
+            x509.DNSName(b"another.local"),
             x509.RFC822Name(u"email@another.local"),
             x509.UniformResourceIdentifier(u"http://another.local"),
         ])
@@ -173,26 +173,32 @@
         assert ci[2:6:2] == [ci[2], ci[4]]
 
     def test_eq(self):
-        ci1 = x509.CertificateIssuer([x509.DNSName(u"cryptography.io")])
-        ci2 = x509.CertificateIssuer([x509.DNSName(u"cryptography.io")])
+        ci1 = x509.CertificateIssuer([x509.DNSName(b"cryptography.io")])
+        ci2 = x509.CertificateIssuer([x509.DNSName(b"cryptography.io")])
         assert ci1 == ci2
 
     def test_ne(self):
-        ci1 = x509.CertificateIssuer([x509.DNSName(u"cryptography.io")])
-        ci2 = x509.CertificateIssuer([x509.DNSName(u"somethingelse.tld")])
+        ci1 = x509.CertificateIssuer([x509.DNSName(b"cryptography.io")])
+        ci2 = x509.CertificateIssuer([x509.DNSName(b"somethingelse.tld")])
         assert ci1 != ci2
         assert ci1 != object()
 
     def test_repr(self):
-        ci = x509.CertificateIssuer([x509.DNSName(u"cryptography.io")])
-        assert repr(ci) == (
-            "<CertificateIssuer(<GeneralNames([<DNSName(value=cryptography.io"
-            ")>])>)>"
-        )
+        ci = x509.CertificateIssuer([x509.DNSName(b"cryptography.io")])
+        if six.PY3:
+            assert repr(ci) == (
+                "<CertificateIssuer(<GeneralNames([<DNSName(bytes_value="
+                "b'cryptography.io')>])>)>"
+            )
+        else:
+            assert repr(ci) == (
+                "<CertificateIssuer(<GeneralNames([<DNSName(bytes_value="
+                "'cryptography.io')>])>)>"
+            )
 
     def test_get_values_for_type(self):
         ci = x509.CertificateIssuer(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         names = ci.get_values_for_type(x509.DNSName)
         assert names == [u"cryptography.io"]
@@ -891,7 +897,7 @@
         assert aki.authority_cert_serial_number is None
 
     def test_authority_cert_serial_zero(self):
-        dns = x509.DNSName(u"SomeIssuer")
+        dns = x509.DNSName(b"SomeIssuer")
         aki = x509.AuthorityKeyIdentifier(b"id", [dns], 0)
         assert aki.key_identifier == b"id"
         assert aki.authority_cert_issuer == [dns]
@@ -1434,7 +1440,6 @@
 @pytest.mark.parametrize(
     "name", [
         x509.RFC822Name,
-        x509.DNSName,
         x509.UniformResourceIdentifier
     ]
 )
@@ -1462,6 +1467,32 @@
         assert gn != object()
 
 
+class TestDNSName(object):
+    def test_init(self):
+        with pytest.warns(utils.DeprecatedIn21):
+            name = x509.DNSName(u"*.\xf5\xe4\xf6\xfc.example.com")
+        assert name.bytes_value == b"*.xn--4ca7aey.example.com"
+
+        with pytest.warns(utils.DeprecatedIn21):
+            name = x509.DNSName(u".\xf5\xe4\xf6\xfc.example.com")
+        assert name.bytes_value == b".xn--4ca7aey.example.com"
+        assert name.value == u".\xf5\xe4\xf6\xfc.example.com"
+
+        with pytest.warns(utils.DeprecatedIn21):
+            name = x509.DNSName(u"\xf5\xe4\xf6\xfc.example.com")
+        assert name.bytes_value == b"xn--4ca7aey.example.com"
+
+        with pytest.raises(TypeError):
+            x509.DNSName(1.3)
+
+    def test_ne(self):
+        n1 = x509.DNSName(b"test1")
+        n2 = x509.DNSName(b"test2")
+        n3 = x509.DNSName(b"test2")
+        assert n1 != n2
+        assert not (n2 != n3)
+
+
 class TestDirectoryName(object):
     def test_not_name(self):
         with pytest.raises(TypeError):
@@ -1686,35 +1717,35 @@
 class TestGeneralNames(object):
     def test_get_values_for_type(self):
         gns = x509.GeneralNames(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         names = gns.get_values_for_type(x509.DNSName)
         assert names == [u"cryptography.io"]
 
     def test_iter_names(self):
         gns = x509.GeneralNames([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ])
         assert len(gns) == 2
         assert list(gns) == [
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ]
 
     def test_iter_input(self):
         names = [
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ]
         gns = x509.GeneralNames(iter(names))
         assert list(gns) == names
 
     def test_indexing(self):
         gn = x509.GeneralNames([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
-            x509.DNSName(u"another.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
+            x509.DNSName(b"another.local"),
             x509.RFC822Name(u"email@another.local"),
             x509.UniformResourceIdentifier(u"http://another.local"),
         ])
@@ -1724,31 +1755,36 @@
     def test_invalid_general_names(self):
         with pytest.raises(TypeError):
             x509.GeneralNames(
-                [x509.DNSName(u"cryptography.io"), "invalid"]
+                [x509.DNSName(b"cryptography.io"), "invalid"]
             )
 
     def test_repr(self):
         gns = x509.GeneralNames(
             [
-                x509.DNSName(u"cryptography.io")
+                x509.DNSName(b"cryptography.io")
             ]
         )
-        assert repr(gns) == (
-            "<GeneralNames([<DNSName(value=cryptography.io)>])>"
-        )
+        if six.PY3:
+            assert repr(gns) == (
+                "<GeneralNames([<DNSName(bytes_value=b'cryptography.io')>])>"
+            )
+        else:
+            assert repr(gns) == (
+                "<GeneralNames([<DNSName(bytes_value='cryptography.io')>])>"
+            )
 
     def test_eq(self):
         gns = x509.GeneralNames(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         gns2 = x509.GeneralNames(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         assert gns == gns2
 
     def test_ne(self):
         gns = x509.GeneralNames(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         gns2 = x509.GeneralNames(
             [x509.RFC822Name(u"admin@cryptography.io")]
@@ -1760,27 +1796,27 @@
 class TestIssuerAlternativeName(object):
     def test_get_values_for_type(self):
         san = x509.IssuerAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         names = san.get_values_for_type(x509.DNSName)
         assert names == [u"cryptography.io"]
 
     def test_iter_names(self):
         san = x509.IssuerAlternativeName([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ])
         assert len(san) == 2
         assert list(san) == [
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ]
 
     def test_indexing(self):
         ian = x509.IssuerAlternativeName([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
-            x509.DNSName(u"another.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
+            x509.DNSName(b"another.local"),
             x509.RFC822Name(u"email@another.local"),
             x509.UniformResourceIdentifier(u"http://another.local"),
         ])
@@ -1790,32 +1826,38 @@
     def test_invalid_general_names(self):
         with pytest.raises(TypeError):
             x509.IssuerAlternativeName(
-                [x509.DNSName(u"cryptography.io"), "invalid"]
+                [x509.DNSName(b"cryptography.io"), "invalid"]
             )
 
     def test_repr(self):
         san = x509.IssuerAlternativeName(
             [
-                x509.DNSName(u"cryptography.io")
+                x509.DNSName(b"cryptography.io")
             ]
         )
-        assert repr(san) == (
-            "<IssuerAlternativeName("
-            "<GeneralNames([<DNSName(value=cryptography.io)>])>)>"
-        )
+        if six.PY3:
+            assert repr(san) == (
+                "<IssuerAlternativeName("
+                "<GeneralNames([<DNSName(bytes_value=b'cryptography.io')>])>)>"
+            )
+        else:
+            assert repr(san) == (
+                "<IssuerAlternativeName("
+                "<GeneralNames([<DNSName(bytes_value='cryptography.io')>])>)>"
+            )
 
     def test_eq(self):
         san = x509.IssuerAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         san2 = x509.IssuerAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         assert san == san2
 
     def test_ne(self):
         san = x509.IssuerAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         san2 = x509.IssuerAlternativeName(
             [x509.RFC822Name(u"admin@cryptography.io")]
@@ -1870,27 +1912,27 @@
 class TestSubjectAlternativeName(object):
     def test_get_values_for_type(self):
         san = x509.SubjectAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         names = san.get_values_for_type(x509.DNSName)
         assert names == [u"cryptography.io"]
 
     def test_iter_names(self):
         san = x509.SubjectAlternativeName([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ])
         assert len(san) == 2
         assert list(san) == [
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
         ]
 
     def test_indexing(self):
         san = x509.SubjectAlternativeName([
-            x509.DNSName(u"cryptography.io"),
-            x509.DNSName(u"crypto.local"),
-            x509.DNSName(u"another.local"),
+            x509.DNSName(b"cryptography.io"),
+            x509.DNSName(b"crypto.local"),
+            x509.DNSName(b"another.local"),
             x509.RFC822Name(u"email@another.local"),
             x509.UniformResourceIdentifier(u"http://another.local"),
         ])
@@ -1900,32 +1942,38 @@
     def test_invalid_general_names(self):
         with pytest.raises(TypeError):
             x509.SubjectAlternativeName(
-                [x509.DNSName(u"cryptography.io"), "invalid"]
+                [x509.DNSName(b"cryptography.io"), "invalid"]
             )
 
     def test_repr(self):
         san = x509.SubjectAlternativeName(
             [
-                x509.DNSName(u"cryptography.io")
+                x509.DNSName(b"cryptography.io")
             ]
         )
-        assert repr(san) == (
-            "<SubjectAlternativeName("
-            "<GeneralNames([<DNSName(value=cryptography.io)>])>)>"
-        )
+        if six.PY3:
+            assert repr(san) == (
+                "<SubjectAlternativeName("
+                "<GeneralNames([<DNSName(bytes_value=b'cryptography.io')>])>)>"
+            )
+        else:
+            assert repr(san) == (
+                "<SubjectAlternativeName("
+                "<GeneralNames([<DNSName(bytes_value='cryptography.io')>])>)>"
+            )
 
     def test_eq(self):
         san = x509.SubjectAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         san2 = x509.SubjectAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         assert san == san2
 
     def test_ne(self):
         san = x509.SubjectAlternativeName(
-            [x509.DNSName(u"cryptography.io")]
+            [x509.DNSName(b"cryptography.io")]
         )
         san2 = x509.SubjectAlternativeName(
             [x509.RFC822Name(u"admin@cryptography.io")]
@@ -2124,8 +2172,15 @@
             x509.load_pem_x509_certificate,
             backend
         )
+        san = cert.extensions.get_extension_for_class(
+            x509.SubjectAlternativeName
+        ).value
+
+        assert len(san) == 1
+        [name] = san
+        assert name.bytes_value == b"xn--k4h.ws"
         with pytest.raises(UnicodeError):
-            cert.extensions
+            name.value
 
     def test_unicode_rfc822_name_dns_name_uri(self, backend):
         cert = _load_cert(
@@ -2220,16 +2275,20 @@
         assert othernames == [expected]
 
     def test_certbuilder(self, backend):
-        sans = [u'*.example.org', u'*.\xf5\xe4\xf6\xfc.example.com',
-                u'foobar.example.net']
+        sans = [b'*.example.org', b'*.xn--4ca7aey.example.com',
+                b'foobar.example.net']
         private_key = RSA_KEY_2048.private_key(backend)
         builder = _make_certbuilder(private_key)
         builder = builder.add_extension(
             SubjectAlternativeName(list(map(DNSName, sans))), True)
 
         cert = builder.sign(private_key, hashes.SHA1(), backend)
-        result = [x.value for x in cert.extensions.get_extension_for_class(
-            SubjectAlternativeName).value]
+        result = [
+            x.bytes_value
+            for x in cert.extensions.get_extension_for_class(
+                SubjectAlternativeName
+            ).value
+        ]
         assert result == sans
 
 
@@ -2265,7 +2324,7 @@
 class TestAccessDescription(object):
     def test_invalid_access_method(self):
         with pytest.raises(TypeError):
-            x509.AccessDescription("notanoid", x509.DNSName(u"test"))
+            x509.AccessDescription("notanoid", x509.DNSName(b"test"))
 
     def test_invalid_access_location(self):
         with pytest.raises(TypeError):
@@ -2799,7 +2858,7 @@
             x509.NameConstraints(None, None)
 
     def test_permitted_none(self):
-        excluded = [x509.DNSName(u"name.local")]
+        excluded = [x509.DNSName(b"name.local")]
         nc = x509.NameConstraints(
             permitted_subtrees=None, excluded_subtrees=excluded
         )
@@ -2807,7 +2866,7 @@
         assert nc.excluded_subtrees is not None
 
     def test_excluded_none(self):
-        permitted = [x509.DNSName(u"name.local")]
+        permitted = [x509.DNSName(b"name.local")]
         nc = x509.NameConstraints(
             permitted_subtrees=permitted, excluded_subtrees=None
         )
@@ -2821,39 +2880,47 @@
         assert list(nc.excluded_subtrees) == subtrees
 
     def test_repr(self):
-        permitted = [x509.DNSName(u"name.local"), x509.DNSName(u"name2.local")]
+        permitted = [x509.DNSName(b"name.local"), x509.DNSName(b"name2.local")]
         nc = x509.NameConstraints(
             permitted_subtrees=permitted,
             excluded_subtrees=None
         )
-        assert repr(nc) == (
-            "<NameConstraints(permitted_subtrees=[<DNSName(value=name.local)>"
-            ", <DNSName(value=name2.local)>], excluded_subtrees=None)>"
-        )
+        if six.PY3:
+            assert repr(nc) == (
+                "<NameConstraints(permitted_subtrees=[<DNSName("
+                "bytes_value=b'name.local')>, <DNSName(bytes_value="
+                "b'name2.local')>], excluded_subtrees=None)>"
+            )
+        else:
+            assert repr(nc) == (
+                "<NameConstraints(permitted_subtrees=[<DNSName("
+                "bytes_value='name.local')>, <DNSName(bytes_value="
+                "'name2.local')>], excluded_subtrees=None)>"
+            )
 
     def test_eq(self):
         nc = x509.NameConstraints(
-            permitted_subtrees=[x509.DNSName(u"name.local")],
-            excluded_subtrees=[x509.DNSName(u"name2.local")]
+            permitted_subtrees=[x509.DNSName(b"name.local")],
+            excluded_subtrees=[x509.DNSName(b"name2.local")]
         )
         nc2 = x509.NameConstraints(
-            permitted_subtrees=[x509.DNSName(u"name.local")],
-            excluded_subtrees=[x509.DNSName(u"name2.local")]
+            permitted_subtrees=[x509.DNSName(b"name.local")],
+            excluded_subtrees=[x509.DNSName(b"name2.local")]
         )
         assert nc == nc2
 
     def test_ne(self):
         nc = x509.NameConstraints(
-            permitted_subtrees=[x509.DNSName(u"name.local")],
-            excluded_subtrees=[x509.DNSName(u"name2.local")]
+            permitted_subtrees=[x509.DNSName(b"name.local")],
+            excluded_subtrees=[x509.DNSName(b"name2.local")]
         )
         nc2 = x509.NameConstraints(
-            permitted_subtrees=[x509.DNSName(u"name.local")],
+            permitted_subtrees=[x509.DNSName(b"name.local")],
             excluded_subtrees=None
         )
         nc3 = x509.NameConstraints(
             permitted_subtrees=None,
-            excluded_subtrees=[x509.DNSName(u"name2.local")]
+            excluded_subtrees=[x509.DNSName(b"name2.local")]
         )
 
         assert nc != nc2
@@ -2877,7 +2944,7 @@
         ).value
         assert nc == x509.NameConstraints(
             permitted_subtrees=[
-                x509.DNSName(u"zombo.local"),
+                x509.DNSName(b"zombo.local"),
             ],
             excluded_subtrees=[
                 x509.DirectoryName(x509.Name([
@@ -2899,7 +2966,7 @@
         ).value
         assert nc == x509.NameConstraints(
             permitted_subtrees=[
-                x509.DNSName(u"zombo.local"),
+                x509.DNSName(b"zombo.local"),
             ],
             excluded_subtrees=None
         )
@@ -2917,7 +2984,7 @@
         ).value
         assert nc == x509.NameConstraints(
             permitted_subtrees=[
-                x509.DNSName(u".cryptography.io"),
+                x509.DNSName(b".cryptography.io"),
                 x509.UniformResourceIdentifier(u"ftp://cryptography.test")
             ],
             excluded_subtrees=None
@@ -2937,7 +3004,7 @@
         assert nc == x509.NameConstraints(
             permitted_subtrees=None,
             excluded_subtrees=[
-                x509.DNSName(u".cryptography.io"),
+                x509.DNSName(b".cryptography.io"),
                 x509.UniformResourceIdentifier(u"gopher://cryptography.test")
             ]
         )
@@ -2959,7 +3026,7 @@
                 x509.IPAddress(ipaddress.IPv6Network(u"FF:0:0:0:0:0:0:0/96")),
             ],
             excluded_subtrees=[
-                x509.DNSName(u".domain.com"),
+                x509.DNSName(b".domain.com"),
                 x509.UniformResourceIdentifier(u"http://test.local"),
             ]
         )
@@ -2997,8 +3064,8 @@
             )
 
     def test_certbuilder(self, backend):
-        permitted = [u'.example.org', u'.\xf5\xe4\xf6\xfc.example.com',
-                     u'foobar.example.net']
+        permitted = [b'.example.org', b'.xn--4ca7aey.example.com',
+                     b'foobar.example.net']
         private_key = RSA_KEY_2048.private_key(backend)
         builder = _make_certbuilder(private_key)
         builder = builder.add_extension(
@@ -3006,8 +3073,12 @@
                             excluded_subtrees=[]), True)
 
         cert = builder.sign(private_key, hashes.SHA1(), backend)
-        result = [x.value for x in cert.extensions.get_extension_for_class(
-            NameConstraints).value.permitted_subtrees]
+        result = [
+            x.bytes_value
+            for x in cert.extensions.get_extension_for_class(
+                NameConstraints
+            ).value.permitted_subtrees
+        ]
         assert result == permitted
 
 
diff --git a/tests/test_x509_revokedcertbuilder.py b/tests/test_x509_revokedcertbuilder.py
index e3a0650..9fc5eaa 100644
--- a/tests/test_x509_revokedcertbuilder.py
+++ b/tests/test_x509_revokedcertbuilder.py
@@ -146,7 +146,7 @@
             x509.InvalidityDate(datetime.datetime(2015, 1, 1, 0, 0)),
             x509.CRLReason(x509.ReasonFlags.ca_compromise),
             x509.CertificateIssuer([
-                x509.DNSName(u"cryptography.io"),
+                x509.DNSName(b"cryptography.io"),
             ])
         ]
     )
@@ -180,7 +180,7 @@
             datetime.datetime(2015, 1, 1, 0, 0)
         )
         certificate_issuer = x509.CertificateIssuer([
-            x509.DNSName(u"cryptography.io"),
+            x509.DNSName(b"cryptography.io"),
         ])
         crl_reason = x509.CRLReason(x509.ReasonFlags.aa_compromise)
         builder = x509.RevokedCertificateBuilder().serial_number(