Support Ed25519 certificates

Parsing and validation of server descriptors via their ed25519 certificate.
Validation requires pynacl to do the cryptographic checks (if not present
they're skipped)...

  https://trac.torproject.org/projects/tor/ticket/21558
  https://gitweb.torproject.org/torspec.git/tree/cert-spec.txt

30 files changed, 712 insertions, 132 deletions

diff --git a/docs/api.rst b/docs/api.rst
index 208450bb..0644d0b3 100644
--- a/docs/api.rst
+++ b/docs/api.rst
@@ -37,6 +37,7 @@ remotely like Tor does.
  * `stem.descriptor.router_status_entry <api/descriptor/router_status_entry.html>`_ - Relay entries within a network status document.
  * `stem.descriptor.hidden_service_descriptor <api/descriptor/hidden_service_descriptor.html>`_ - Descriptors generated for hidden services.
  * `stem.descriptor.tordnsel <api/descriptor/tordnsel.html>`_ - `TorDNSEL <https://www.torproject.org/projects/tordnsel.html.en>`_ exit lists.
+ * `stem.descriptor.tordnsel <api/descriptor/certificate.html>`_ - `Ed25519 certificates <https://gitweb.torproject.org/torspec.git/tree/cert-spec.txt>`_.
 
 * `stem.descriptor.reader <api/descriptor/reader.html>`_ - Reads and parses descriptor files from disk.
 * `stem.descriptor.remote <api/descriptor/remote.html>`_ - Downloads descriptors from directory mirrors and authorities.
diff --git a/docs/api/descriptor/certificate.rst b/docs/api/descriptor/certificate.rst
new file mode 100644
index 00000000..f4c2aa38
--- /dev/null
+++ b/docs/api/descriptor/certificate.rst
@@ -0,0 +1,5 @@
+Certificate
+===========
+
+.. automodule:: stem.descriptor.certificate
+
diff --git a/docs/change_log.rst b/docs/change_log.rst
index e7993d16..bad162bf 100644
--- a/docs/change_log.rst
+++ b/docs/change_log.rst
@@ -51,6 +51,7 @@ The following are only available within Stem's `git repository
 
  * **Descriptors**
 
+  * Support and validation for `ed25519 certificates <api/descriptor/certificate.html>`_ (`spec <https://gitweb.torproject.org/torspec.git/tree/cert-spec.txt>`_, :trac:`21558`)
   * Moved from the deprecated `pycrypto <https://www.dlitz.net/software/pycrypto/>`_ module to `cryptography <https://pypi.python.org/pypi/cryptography>`_ for validating signatures (:trac:`21086`)
   * Sped descriptor reading by ~25% by deferring defaulting when validating
   * Support for protocol descriptor fields (:spec:`eb4fb3c`)
diff --git a/docs/contents.rst b/docs/contents.rst
index 930d4cf9..5cbd5bf2 100644
--- a/docs/contents.rst
+++ b/docs/contents.rst
@@ -37,6 +37,7 @@ Contents
    api/manual
    api/version
 
+   api/descriptor/certificate
    api/descriptor/descriptor
    api/descriptor/server_descriptor
    api/descriptor/extrainfo_descriptor
diff --git a/docs/faq.rst b/docs/faq.rst
index 69033d4f..59dacfdb 100644
--- a/docs/faq.rst
+++ b/docs/faq.rst
@@ -53,7 +53,8 @@ Does Stem have any dependencies?
 **No.** All you need in order to use Stem is Python.
 
 When it is available Stem will use `cryptography
-<https://pypi.python.org/pypi/cryptography>`_ to validate descriptor signatures.
+<https://pypi.python.org/pypi/cryptography>`_ and `PyNaCl
+<https://pypi.python.org/pypi/PyNaCl/>`_ to validate descriptor signatures.
 However, there is no need to install cryptography unless you need this
 functionality.
 
@@ -65,13 +66,22 @@ Note that if cryptography installation fails with...
   compilation terminated.
   error: command 'gcc' failed with exit status 1
 
-You need python-dev. For instance on Debian and Ubuntu you can install
-cryptography with...
+... or...
 
 ::
 
-  % sudo apt-get install python-dev
+  No package 'libffi' found
+  c/_cffi_backend.c:15:17: fatal error: ffi.h: No such file or directory
+  compilation terminated.
+
+You need the python-dev and libffi-dev packages. For instance on Debian and
+Ubuntu you can install these with...
+
+::
+
+  % sudo apt-get install python-dev libffi-dev
   % sudo pip install cryptography
+  % sudo pip install pynacl
 
 .. _what_python_versions_is_stem_compatible_with:
 
diff --git a/requirements.txt b/requirements.txt
index 6dc054ca..3cd71608 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -3,3 +3,4 @@ pyflakes
 pycodestyle
 tox
 cryptography
+pynacl
diff --git a/run_tests.py b/run_tests.py
index bceade34..fc6d906d 100755
--- a/run_tests.py
+++ b/run_tests.py
@@ -161,6 +161,7 @@ def main():
     tor_version_check,
     Task('checking python version', test.util.check_python_version),
     Task('checking cryptography version', test.util.check_cryptography_version),
+    Task('checking pynacl version', test.util.check_pynacl_version),
     Task('checking mock version', test.util.check_mock_version),
     Task('checking pyflakes version', test.util.check_pyflakes_version),
     Task('checking pycodestyle version', test.util.check_pycodestyle_version),
diff --git a/stem/descriptor/certificate.py b/stem/descriptor/certificate.py
new file mode 100644
index 00000000..cd7710c2
--- /dev/null
+++ b/stem/descriptor/certificate.py
@@ -0,0 +1,268 @@
+# Copyright 2017, Damian Johnson and The Tor Project
+# See LICENSE for licensing information
+
+"""
+Parsing for `Tor Ed25519 certificates
+<https://gitweb.torproject.org/torspec.git/tree/cert-spec.txt>`_, which are
+used to validate the key used to sign server descriptors.
+
+.. versionadded:: 1.6.0
+
+**Module Overview:**
+
+::
+
+  Ed25519Certificate - Ed25519 signing key certificate
+    | +- Ed25519CertificateV1 - version 1 Ed25519 certificate
+    |      |- is_expired - checks if certificate is presently expired
+    |      +- validate - validates signature of a server descriptor
+    |
+    +- parse - reads base64 encoded certificate data
+
+  Ed25519Extension - extension included within an Ed25519Certificate
+
+.. data:: CertType (enum)
+
+  Purpose of Ed25519 certificate. As new certificate versions are added this
+  enumeration will expand.
+
+  ==============  ===========
+  CertType        Description
+  ==============  ===========
+  **SIGNING**     signing a signing key with an identity key
+  **LINK_CERT**   TLS link certificate signed with ed25519 signing key
+  **AUTH**        authentication key signed with ed25519 signing key
+  ==============  ===========
+
+.. data::ExtensionType (enum)
+
+  Recognized exception types.
+
+  ====================  ===========
+  ExtensionType         Description
+  ====================  ===========
+  HAS_SIGNING_KEY       includes key used to sign the certificate
+  ====================  ===========
+
+.. data::ExtensionFlag (enum)
+
+  Flags that can be assigned to Ed25519 certificate extensions.
+
+  ====================  ===========
+  ExtensionFlag         Description
+  ====================  ===========
+  AFFECTS_VALIDATION    extension affects whether the certificate is valid
+  UNKNOWN               extension includes flags not yet recognized by stem
+  ====================  ===========
+"""
+
+import base64
+import binascii
+import collections
+import datetime
+import hashlib
+
+import stem.prereq
+import stem.util.enum
+import stem.util.str_tools
+
+ED25519_HEADER_LENGTH = 40
+ED25519_SIGNATURE_LENGTH = 64
+ED25519_ROUTER_SIGNATURE_PREFIX = b'Tor router descriptor signature v1'
+
+CertType = stem.util.enum.UppercaseEnum('SIGNING', 'LINK_CERT', 'AUTH')
+ExtensionType = stem.util.enum.Enum(('HAS_SIGNING_KEY', 4),)
+ExtensionFlag = stem.util.enum.UppercaseEnum('AFFECTS_VALIDATION', 'UNKNOWN')
+
+
+class Ed25519Extension(collections.namedtuple('Ed25519Extension', ['type', 'flags', 'flag_int', 'data'])):
+  """
+  Extension within an Ed25519 certificate.
+
+  :var int type: extension type
+  :var list flags: extension attribute flags
+  :var int flag_int: integer encoding of the extension attribute flags
+  :var bytes data: data the extension concerns
+  """
+
+
+class Ed25519Certificate(object):
+  """
+  Base class for an Ed25519 certificate.
+
+  :var int version: certificate format version
+  :var str encoded: base64 encoded ed25519 certificate
+  """
+
+  def __init__(self, version, encoded):
+    self.version = version
+    self.encoded = encoded
+
+  @staticmethod
+  def parse(content):
+    """
+    Parses the given base64 encoded data as an Ed25519 certificate.
+
+    :param str content: base64 encoded certificate
+
+    :returns: :class:`~stem.descriptor.certificate.Ed25519Certificate` subclsss
+      for the given certificate
+
+    :raises: **ValueError** if content is malformed
+    """
+
+    try:
+      decoded = base64.b64decode(stem.util.str_tools._to_bytes(content))
+
+      if not decoded:
+        raise TypeError('empty')
+    except (TypeError, binascii.Error) as exc:
+      raise ValueError("Ed25519 certificate wasn't propoerly base64 encoded (%s):\n%s" % (exc, content))
+
+    version = stem.util.str_tools._to_int(decoded[0:1])
+
+    if version == 1:
+      return Ed25519CertificateV1(version, content, decoded)
+    else:
+      raise ValueError('Ed25519 certificate is version %i. Parser presently only supports version 1.' % version)
+
+
+class Ed25519CertificateV1(Ed25519Certificate):
+  """
+  Version 1 Ed25519 certificate, which are used for signing tor server
+  descriptors.
+
+  :var CertType type: certificate purpose
+  :var datetime expiration: expiration of the certificate
+  :var int key_type: format of the key
+  :var bytes key: key content
+  :var list extensions: :class:`~stem.descriptor.certificate.Ed25519Extension` in this certificate
+  :var bytes signature: certificate signature
+  """
+
+  def __init__(self, version, encoded, decoded):
+    super(Ed25519CertificateV1, self).__init__(version, encoded)
+
+    if len(decoded) < ED25519_HEADER_LENGTH + ED25519_SIGNATURE_LENGTH:
+      raise ValueError('Ed25519 certificate was %i bytes, but should be at least %i' % (len(decoded), ED25519_HEADER_LENGTH + ED25519_SIGNATURE_LENGTH))
+
+    cert_type = stem.util.str_tools._to_int(decoded[1:2])
+
+    if cert_type in (0, 1, 2, 3):
+      raise ValueError('Ed25519 certificate cannot have a type of %i. This is reserved to avoid conflicts with tor CERTS cells.' % cert_type)
+    elif cert_type == 4:
+      self.type = CertType.SIGNING
+    elif cert_type == 5:
+      self.type = CertType.LINK_CERT
+    elif cert_type == 6:
+      self.type = CertType.AUTH
+    elif cert_type == 7:
+      raise ValueError('Ed25519 certificate cannot have a type of 7. This is reserved for RSA identity cross-certification.')
+    else:
+      raise ValueError("BUG: Ed25519 certificate type is decoded from one byte. It shouldn't be possible to have a value of %i." % cert_type)
+
+    # expiration time is in hours since epoch
+    self.expiration = datetime.datetime.utcfromtimestamp(stem.util.str_tools._to_int(decoded[2:6]) * 3600)
+
+    self.key_type = stem.util.str_tools._to_int(decoded[6:7])
+    self.key = decoded[7:39]
+    self.signature = decoded[-ED25519_SIGNATURE_LENGTH:]
+
+    self.extensions = []
+    extension_count = stem.util.str_tools._to_int(decoded[39:40])
+    remaining_data = decoded[40:-ED25519_SIGNATURE_LENGTH]
+
+    for i in range(extension_count):
+      if len(remaining_data) < 4:
+        raise ValueError('Ed25519 extension is missing header field data')
+
+      extension_length = stem.util.str_tools._to_int(remaining_data[:2])
+      extension_type = stem.util.str_tools._to_int(remaining_data[2:3])
+      extension_flags = stem.util.str_tools._to_int(remaining_data[3:4])
+      extension_data = remaining_data[4:4 + extension_length]
+
+      if extension_length != len(extension_data):
+        raise ValueError("Ed25519 extension is truncated. It should have %i bytes of data but there's only %i." % (extension_length, len(extension_data)))
+
+      flags, remaining_flags = [], extension_flags
+
+      if remaining_flags % 2 == 1:
+        flags.append(ExtensionFlag.AFFECTS_VALIDATION)
+        remaining_flags -= 1
+
+      if remaining_flags:
+        flags.append(ExtensionFlag.UNKNOWN)
+
+      if extension_type == ExtensionType.HAS_SIGNING_KEY and len(extension_data) != 32:
+        raise ValueError('Ed25519 HAS_SIGNING_KEY extension must be 32 bytes, but was %i.' % len(extension_data))
+
+      self.extensions.append(Ed25519Extension(extension_type, flags, extension_flags, extension_data))
+      remaining_data = remaining_data[4 + extension_length:]
+
+    if remaining_data:
+      raise ValueError('Ed25519 certificate had %i bytes of unused extension data' % len(remaining_data))
+
+  def is_expired(self):
+    """
+    Checks if this certificate is presently expired or not.
+
+    :returns: **True** if the certificate has expired, **False** otherwise
+    """
+
+    return datetime.datetime.now() > self.expiration
+
+  def validate(self, server_descriptor):
+    """
+    Validates our signing key and that the given descriptor content matches its
+    Ed25519 signature.
+
+    :param stem.descriptor.server_descriptor.Ed25519 server_descriptor: relay
+      server descriptor to validate
+
+    :raises:
+      * **ValueError** if signing key or descriptor are invalid
+      * **ImportError** if pynacl module is unavailable
+    """
+
+    if not stem.prereq._is_pynacl_available():
+      raise ImportError('Certificate validation requires the pynacl module')
+
+    import nacl.signing
+    import nacl.encoding
+    from nacl.exceptions import BadSignatureError
+
+    descriptor_content = server_descriptor.get_bytes()
+    signing_key = None
+
+    if server_descriptor.ed25519_master_key:
+      signing_key = nacl.signing.VerifyKey(stem.util.str_tools._to_bytes(server_descriptor.ed25519_master_key) + b'=', encoder = nacl.encoding.Base64Encoder)
+    else:
+      for extension in self.extensions:
+        if extension.type == ExtensionType.HAS_SIGNING_KEY:
+          signing_key = nacl.signing.VerifyKey(extension.data)
+          break
+
+    if not signing_key:
+      raise ValueError('Server descriptor missing an ed25519 signing key')
+
+    try:
+      signing_key.verify(base64.b64decode(stem.util.str_tools._to_bytes(self.encoded))[:-ED25519_SIGNATURE_LENGTH], self.signature)
+    except BadSignatureError as exc:
+      raise ValueError('Ed25519KeyCertificate signing key is invalid (%s)' % exc)
+
+    # ed25519 signature validates descriptor content up until the signature itself
+
+    if b'router-sig-ed25519 ' not in descriptor_content:
+      raise ValueError("Descriptor doesn't have a router-sig-ed25519 entry.")
+
+    signed_content = descriptor_content[:descriptor_content.index(b'router-sig-ed25519 ') + 19]
+    descriptor_sha256_digest = hashlib.sha256(ED25519_ROUTER_SIGNATURE_PREFIX + signed_content).digest()
+
+    missing_padding = len(server_descriptor.ed25519_signature) % 4
+    signature_bytes = base64.b64decode(stem.util.str_tools._to_bytes(server_descriptor.ed25519_signature) + b'=' * missing_padding)
+
+    try:
+      verify_key = nacl.signing.VerifyKey(self.key)
+      verify_key.verify(descriptor_sha256_digest, signature_bytes)
+    except BadSignatureError as exc:
+      raise ValueError('Descriptor Ed25519 certificate signature invalid (%s)' % exc)
diff --git a/stem/descriptor/hidden_service_descriptor.py b/stem/descriptor/hidden_service_descriptor.py
index ce3a134f..9c875003 100644
--- a/stem/descriptor/hidden_service_descriptor.py
+++ b/stem/descriptor/hidden_service_descriptor.py
@@ -326,7 +326,7 @@ class HiddenServiceDescriptor(Descriptor):
 
       # try decrypting the session key
 
-      cipher = Cipher(algorithms.AES(authentication_cookie), modes.CTR('\x00' * len(iv)), default_backend())
+      cipher = Cipher(algorithms.AES(authentication_cookie), modes.CTR(b'\x00' * len(iv)), default_backend())
       decryptor = cipher.decryptor()
       session_key = decryptor.update(encrypted_session_key) + decryptor.finalize()
 
diff --git a/stem/descriptor/router_status_entry.py b/stem/descriptor/router_status_entry.py
index 880051b1..3cdb4ed1 100644
--- a/stem/descriptor/router_status_entry.py
+++ b/stem/descriptor/router_status_entry.py
@@ -368,7 +368,7 @@ def _base64_to_hex(identity, check_if_fingerprint = True):
   except (TypeError, binascii.Error):
     raise ValueError("Unable to decode identity string '%s'" % identity)
 
-  fingerprint = binascii.b2a_hex(identity_decoded).upper()
+  fingerprint = binascii.hexlify(identity_decoded).upper()
 
   if stem.prereq.is_python_3():
     fingerprint = stem.util.str_tools._to_unicode(fingerprint)
diff --git a/stem/descriptor/server_descriptor.py b/stem/descriptor/server_descriptor.py
index 3aa5fb0f..1cedbe5d 100644
--- a/stem/descriptor/server_descriptor.py
+++ b/stem/descriptor/server_descriptor.py
@@ -31,10 +31,13 @@ etc). This information is provided from a few sources...
     +- get_annotation_lines - lines that provided the annotations
 """
 
+import base64
+import binascii
 import functools
 import hashlib
 import re
 
+import stem.descriptor.certificate
 import stem.descriptor.extrainfo_descriptor
 import stem.exit_policy
 import stem.prereq
@@ -386,7 +389,16 @@ def _parse_exit_policy(descriptor, entries):
     del descriptor._unparsed_exit_policy
 
 
-_parse_identity_ed25519_line = _parse_key_block('identity-ed25519', 'ed25519_certificate', 'ED25519 CERT')
+def _parse_identity_ed25519_line(descriptor, entries):
+  _parse_key_block('identity-ed25519', 'ed25519_certificate', 'ED25519 CERT')(descriptor, entries)
+
+  if descriptor.ed25519_certificate:
+    cert_lines = descriptor.ed25519_certificate.split('\n')
+
+    if cert_lines[0] == '-----BEGIN ED25519 CERT-----' and cert_lines[-1] == '-----END ED25519 CERT-----':
+      descriptor.certificate = stem.descriptor.certificate.Ed25519Certificate.parse(''.join(cert_lines[1:-1]))
+
+
 _parse_master_key_ed25519_line = _parse_simple_line('master-key-ed25519', 'ed25519_master_key')
 _parse_master_key_ed25519_for_hash_line = _parse_simple_line('master-key-ed25519', 'ed25519_certificate_hash')
 _parse_contact_line = _parse_bytes_line('contact', 'contact')
@@ -662,6 +674,12 @@ class ServerDescriptor(Descriptor):
     if expected_last_keyword and expected_last_keyword != list(entries.keys())[-1]:
       raise ValueError("Descriptor must end with a '%s' entry" % expected_last_keyword)
 
+    if 'identity-ed25519' in entries.keys():
+      if 'router-sig-ed25519' not in entries.keys():
+        raise ValueError('Descriptor must have router-sig-ed25519 entry to accompany identity-ed25519')
+      elif 'router-sig-ed25519' not in list(entries.keys())[-2:]:
+        raise ValueError("Descriptor must have 'router-sig-ed25519' as the next-to-last entry")
+
     if not self.exit_policy:
       raise ValueError("Descriptor must have at least one 'accept' or 'reject' entry")
 
@@ -686,6 +704,7 @@ class RelayDescriptor(ServerDescriptor):
   Server descriptor (`descriptor specification
   <https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt>`_)
 
+  :var stem.certificate.Ed25519Certificate certificate: ed25519 certificate
   :var str ed25519_certificate: base64 encoded ed25519 certificate
   :var str ed25519_master_key: base64 encoded master key for our ed25519 certificate
   :var str ed25519_signature: signature of this document using ed25519
@@ -708,9 +727,18 @@ class RelayDescriptor(ServerDescriptor):
      Moved from the deprecated `pycrypto
      <https://www.dlitz.net/software/pycrypto/>`_ module to `cryptography
      <https://pypi.python.org/pypi/cryptography>`_ for validating signatures.
+
+  .. versionchanged:: 1.6.0
+     Added the certificate attribute.
+
+  .. deprecated:: 1.6.0
+     Our **ed25519_certificate** is deprecated in favor of our new
+     **certificate** attribute. The base64 encoded certificate is available via
+     the certificate's **encoded** attribute.
   """
 
   ATTRIBUTES = dict(ServerDescriptor.ATTRIBUTES, **{
+    'certificate': (None, _parse_identity_ed25519_line),
     'ed25519_certificate': (None, _parse_identity_ed25519_line),
     'ed25519_master_key': (None, _parse_master_key_ed25519_line),
     'ed25519_signature': (None, _parse_router_sig_ed25519_line),
@@ -750,6 +778,15 @@ class RelayDescriptor(ServerDescriptor):
         if signed_digest != self.digest():
           raise ValueError('Decrypted digest does not match local digest (calculated: %s, local: %s)' % (signed_digest, self.digest()))
 
+        if self.onion_key_crosscert:
+          onion_key_crosscert_digest = self._digest_for_signature(self.onion_key, self.onion_key_crosscert)
+
+          if onion_key_crosscert_digest != self.onion_key_crosscert_digest():
+            raise ValueError('Decrypted onion-key-crosscert digest does not match local digest (calculated: %s, local: %s)' % (onion_key_crosscert_digest, self.onion_key_crosscert_digest()))
+
+      if stem.prereq._is_pynacl_available() and self.certificate:
+        self.certificate.validate(self)
+
   @lru_cache()
   def digest(self):
     """
@@ -757,11 +794,26 @@ class RelayDescriptor(ServerDescriptor):
 
     :returns: the digest string encoded in uppercase hex
 
-    :raises: ValueError if the digest canot be calculated
+    :raises: ValueError if the digest cannot be calculated
     """
 
     return self._digest_for_content(b'router ', b'\nrouter-signature\n')
 
+  @lru_cache()
+  def onion_key_crosscert_digest(self):
+    """
+    Provides the digest of the onion-key-crosscert data. This consists of the
+    RSA identity key sha1 and ed25519 identity key.
+
+    :returns: **unicode** digest encoded in uppercase hex
+
+    :raises: ValueError if the digest cannot be calculated
+    """
+
+    signing_key_digest = hashlib.sha1(_bytes_for_block(self.signing_key)).digest()
+    data = signing_key_digest + base64.b64decode(stem.util.str_tools._to_bytes(self.ed25519_master_key) + b'=')
+    return stem.util.str_tools._to_unicode(binascii.hexlify(data).upper())
+
   def _compare(self, other, method):
     if not isinstance(other, RelayDescriptor):
       return False
diff --git a/stem/prereq.py b/stem/prereq.py
index 585b6192..e3d0051d 100644
--- a/stem/prereq.py
+++ b/stem/prereq.py
@@ -27,6 +27,7 @@ except ImportError:
   from stem.util.lru_cache import lru_cache
 
 CRYPTO_UNAVAILABLE = "Unable to import the cryptography module. Because of this we'll be unable to verify descriptor signature integrity. You can get cryptography from: https://pypi.python.org/pypi/cryptography"
+PYNACL_UNAVAILABLE = "Unable to import the pynacl module. Because of this we'll be unable to verify descriptor ed25519 certificate integrity. You can get pynacl from https://pypi.python.org/pypi/PyNaCl/"
 
 
 def check_requirements():
@@ -146,3 +147,23 @@ def is_mock_available():
     return True
   except ImportError:
     return False
+
+
+@lru_cache()
+def _is_pynacl_available():
+  """
+  Checks if the pynacl functions we use are available. This is used for
+  verifying ed25519 certificates in relay descriptor signatures.
+
+  :returns: **True** if we can use pynacl and **False** otherwise
+  """
+
+  from stem.util import log
+
+  try:
+    from nacl import encoding
+    from nacl import signing
+    return True
+  except ImportError:
+    log.log_once('stem.prereq._is_pynacl_available', log.INFO, PYNACL_UNAVAILABLE)
+    return False
diff --git a/stem/response/authchallenge.py b/stem/response/authchallenge.py
index d77fd815..94e406f1 100644
--- a/stem/response/authchallenge.py
+++ b/stem/response/authchallenge.py
@@ -41,7 +41,7 @@ class AuthChallengeResponse(stem.response.ControlMessage):
       if not stem.util.tor_tools.is_hex_digits(value, 64):
         raise stem.ProtocolError('SERVERHASH has an invalid value: %s' % value)
 
-      self.server_hash = binascii.a2b_hex(stem.util.str_tools._to_bytes(value))
+      self.server_hash = binascii.unhexlify(stem.util.str_tools._to_bytes(value))
     else:
       raise stem.ProtocolError('Missing SERVERHASH mapping: %s' % line)
 
@@ -51,6 +51,6 @@ class AuthChallengeResponse(stem.response.ControlMessage):
       if not stem.util.tor_tools.is_hex_digits(value, 64):
         raise stem.ProtocolError('SERVERNONCE has an invalid value: %s' % value)
 
-      self.server_nonce = binascii.a2b_hex(stem.util.str_tools._to_bytes(value))
+      self.server_nonce = binascii.unhexlify(stem.util.str_tools._to_bytes(value))
     else:
       raise stem.ProtocolError('Missing SERVERNONCE mapping: %s' % line)
diff --git a/stem/util/str_tools.py b/stem/util/str_tools.py
index 0fbdf384..8c6463a6 100644
--- a/stem/util/str_tools.py
+++ b/stem/util/str_tools.py
@@ -117,6 +117,22 @@ def _to_unicode(msg):
   return _to_unicode_impl(msg)
 
 
+def _to_int(msg):
+  """
+  Serializes a string to a number.
+
+  :param str msg: string to be serialized
+
+  :returns: **int** representation of the string
+  """
+
+  if stem.prereq.is_python_3() and isinstance(msg, bytes):
+    # iterating over bytes in python3 provides ints rather than characters
+    return sum([pow(256, (len(msg) - i - 1)) * c for (i, c) in enumerate(msg)])
+  else:
+    return sum([pow(256, (len(msg) - i - 1)) * ord(c) for (i, c) in enumerate(msg)])
+
+
 def _to_camel_case(label, divider = '_', joiner = ' '):
   """
   Converts the given string to camel case, ie:
diff --git a/stem/util/test_tools.py b/stem/util/test_tools.py
index 0d70dc70..b75c4d09 100644
--- a/stem/util/test_tools.py
+++ b/stem/util/test_tools.py
@@ -27,6 +27,7 @@ import re
 import time
 import unittest
 
+import stem.prereq
 import stem.util.conf
 import stem.util.system
 
@@ -70,6 +71,17 @@ class TimedTestRunner(unittest.TextTestRunner):
           TEST_RUNTIMES[self.id()] = time.time() - start_time
           return result
 
+        # TODO: remove when dropping python 2.6 support
+
+        def assertRaisesRegexp(self, exc_type, exc_msg, func, *args, **kwargs):
+          if stem.prereq._is_python_26():
+            try:
+              func(*args, **kwargs)
+            except exc_type as exc:
+              self.assertTrue(re.match(exc_msg, str(exc)))
+          else:
+            return super(original_type, self).assertRaisesRegexp(exc_type, exc_msg, func, *args, **kwargs)
+
         def id(self):
           return '%s.%s.%s' % (original_type.__module__, original_type.__name__, self._testMethodName)
 
diff --git a/test/integ/control/controller.py b/test/integ/control/controller.py
index a1f155b2..f5c91d7a 100644
--- a/test/integ/control/controller.py
+++ b/test/integ/control/controller.py
@@ -581,13 +581,11 @@ class TestController(unittest.TestCase):
     runner = test.runner.get_runner()
 
     with runner.get_tor_controller() as controller:
+      # try creating a service with an invalid ports
+
       for ports in (4567890, [4567, 4567890], {4567: '-:4567'}):
-        try:
-          # try creating a service with an invalid port
-          response = controller.create_ephemeral_hidden_service(ports)
-          self.fail("we should've raised a stem.ProtocolError")
-        except stem.ProtocolError as exc:
-          self.assertEqual("ADD_ONION response didn't have an OK status: Invalid VIRTPORT/TARGET", str(exc))
+        exc_msg = "ADD_ONION response didn't have an OK status: Invalid VIRTPORT/TARGET"
+        self.assertRaisesRegexp(stem.ProtocolError, exc_msg, controller.create_ephemeral_hidden_service, ports)
 
       response = controller.create_ephemeral_hidden_service(4567)
       self.assertEqual([response.service_id], controller.list_ephemeral_hidden_services())
@@ -654,11 +652,8 @@ class TestController(unittest.TestCase):
     runner = test.runner.get_runner()
 
     with runner.get_tor_controller() as controller:
-      try:
-        controller.create_ephemeral_hidden_service(4567, basic_auth = {})
-        self.fail('ADD_ONION should fail when using basic auth without any clients')
-      except stem.ProtocolError as exc:
-        self.assertEqual("ADD_ONION response didn't have an OK status: No auth clients specified", str(exc))
+      exc_msg = "ADD_ONION response didn't have an OK status: No auth clients specified"
+      self.assertRaisesRegexp(stem.ProtocolError, exc_msg, controller.create_ephemeral_hidden_service, 4567, basic_auth = {})
 
   @require_controller
   @require_version(Requirement.ADD_ONION)
@@ -1266,11 +1261,8 @@ class TestController(unittest.TestCase):
 
       # try to fetch something that doesn't exist
 
-      try:
-        desc = controller.get_hidden_service_descriptor('m4cfuk6qp4lpu2g3')
-        self.fail("Didn't expect m4cfuk6qp4lpu2g3.onion to exist, but provided: %s" % desc)
-      except stem.DescriptorUnavailable as exc:
-        self.assertEqual('No running hidden service at m4cfuk6qp4lpu2g3.onion', str(exc))
+      exc_msg = 'No running hidden service at m4cfuk6qp4lpu2g3.onion'
+      self.assertRaisesRegexp(stem.DescriptorUnavailable, exc_msg, controller.get_hidden_service_descriptor, 'm4cfuk6qp4lpu2g3')
 
       # ... but shouldn't fail if we have a default argument or aren't awaiting the descriptor
 
diff --git a/test/integ/process.py b/test/integ/process.py
index 19d67501..3f7ac65a 100644
--- a/test/integ/process.py
+++ b/test/integ/process.py
@@ -356,18 +356,17 @@ class TestProcess(unittest.TestCase):
     #   [warn] Failed to parse/validate config: Failed to bind one of the listener ports.
     #   [err] Reading config failed--see warnings above.
 
-    try:
-      stem.process.launch_tor_with_config(
-        tor_cmd = test.runner.get_runner().get_tor_command(),
-        config = {
-          'SocksPort': '2777',
-          'ControlPort': '2777',
-          'DataDirectory': self.data_directory,
-        },
-      )
-      self.fail("We should abort when there's an identical SocksPort and ControlPort")
-    except OSError as exc:
-      self.assertEqual('Process terminated: Failed to bind one of the listener ports.', str(exc))
+    self.assertRaisesRegexp(
+      OSError,
+      'Process terminated: Failed to bind one of the listener ports.',
+      stem.process.launch_tor_with_config,
+      tor_cmd = test.runner.get_runner().get_tor_command(),
+      config = {
+        'SocksPort': '2777',
+        'ControlPort': '2777',
+        'DataDirectory': self.data_directory,
+      },
+    )
 
   @only_run_once
   def test_launch_tor_with_timeout(self):
diff --git a/test/integ/util/system.py b/test/integ/util/system.py
index b6e66a0a..be043936 100644
--- a/test/integ/util/system.py
+++ b/test/integ/util/system.py
@@ -564,11 +564,7 @@ class TestSystem(unittest.TestCase):
     self.assertEqual(os.path.join(home_dir, 'foo'), stem.util.system.expand_path('~%s/foo' % username))
 
   def test_call_timeout(self):
-    try:
-      stem.util.system.call('sleep 1', timeout = 0.001)
-      self.fail("sleep should've timed out")
-    except stem.util.system.CallTimeoutError as exc:
-      self.assertEqual("Process didn't finish after 0.0 seconds", str(exc))
+    self.assertRaisesRegexp(stem.util.system.CallTimeoutError, "Process didn't finish after 0.0 seconds", stem.util.system.call, 'sleep 1', timeout = 0.001)
 
   def test_call_time_tracked(self):
     """
diff --git a/test/settings.cfg b/test/settings.cfg
index c8172f62..1d011f99 100644
--- a/test/settings.cfg
+++ b/test/settings.cfg
@@ -152,6 +152,10 @@ pyflakes.ignore stem/prereq.py => 'modes' imported but unused
 pyflakes.ignore stem/prereq.py => 'Cipher' imported but unused
 pyflakes.ignore stem/prereq.py => 'algorithms' imported but unused
 pyflakes.ignore stem/prereq.py => 'unittest' imported but unused
+pyflakes.ignore stem/prereq.py => 'unittest.mock' imported but unused
+pyflakes.ignore stem/prereq.py => 'long_to_bytes' imported but unused
+pyflakes.ignore stem/prereq.py => 'encoding' imported but unused
+pyflakes.ignore stem/prereq.py => 'signing' imported but unused
 pyflakes.ignore stem/interpreter/__init__.py => undefined name 'raw_input'
 pyflakes.ignore stem/util/conf.py => undefined name 'unicode'
 pyflakes.ignore stem/util/test_tools.py => 'pyflakes' imported but unused
@@ -190,6 +194,7 @@ test.unit_tests
 |test.unit.descriptor.networkstatus.document_v3.TestNetworkStatusDocument
 |test.unit.descriptor.networkstatus.bridge_document.TestBridgeNetworkStatusDocument
 |test.unit.descriptor.hidden_service_descriptor.TestHiddenServiceDescriptor
+|test.unit.descriptor.certificate.TestEd25519Certificate
 |test.unit.exit_policy.rule.TestExitPolicyRule
 |test.unit.exit_policy.policy.TestExitPolicy
 |test.unit.version.TestVersion
diff --git a/test/unit/control/controller.py b/test/unit/control/controller.py
index 0c82a940..47ac9d26 100644
--- a/test/unit/control/controller.py
+++ b/test/unit/control/controller.py
@@ -442,12 +442,8 @@ class TestControl(unittest.TestCase):
 
     get_info_mock.side_effect = ControllerError('nope, too bad')
 
-    try:
-      self.controller.get_network_status()
-      self.fail("We should've raised an exception")
-    except ControllerError as exc:
-      self.assertEqual('Unable to determine our own fingerprint: nope, too bad', str(exc))
-
+    exc_msg = 'Unable to determine our own fingerprint: nope, too bad'
+    self.assertRaisesRegexp(ControllerError, exc_msg, self.controller.get_network_status)
     self.assertEqual('boom', self.controller.get_network_status(default = 'boom'))
 
     # successful request
@@ -469,11 +465,8 @@ class TestControl(unittest.TestCase):
 
     get_info_mock.side_effect = InvalidArguments(None, 'GETINFO request contained unrecognized keywords: ns/id/5AC9C5AA75BA1F18D8459B326B4B8111A856D290')
 
-    try:
-      self.controller.get_network_status('5AC9C5AA75BA1F18D8459B326B4B8111A856D290')
-      self.fail("We should've raised an exception")
-    except DescriptorUnavailable as exc:
-      self.assertEqual("Tor was unable to provide the descriptor for '5AC9C5AA75BA1F18D8459B326B4B8111A856D290'", str(exc))
+    exc_msg = "Tor was unable to provide the descriptor for '5AC9C5AA75BA1F18D8459B326B4B8111A856D290'"
+    self.assertRaisesRegexp(DescriptorUnavailable, exc_msg, self.controller.get_network_status, '5AC9C5AA75BA1F18D8459B326B4B8111A856D290')
 
   @patch('stem.control.Controller.get_info')
   def test_get_network_status(self, get_info_mock):
diff --git a/test/unit/descriptor/certificate.py b/test/unit/descriptor/certificate.py
new file mode 100644
index 00000000..669d9ada
--- /dev/null
+++ b/test/unit/descriptor/certificate.py
@@ -0,0 +1,194 @@
+"""
+Unit tests for stem.descriptor.certificate.
+"""
+
+import base64
+import datetime
+import re
+import unittest
+
+import stem.descriptor.certificate
+import stem.util.str_tools
+import stem.prereq
+import test.runner
+
+from stem.descriptor.certificate import ED25519_SIGNATURE_LENGTH, CertType, ExtensionType, ExtensionFlag, Ed25519Certificate, Ed25519CertificateV1, Ed25519Extension
+from test.unit.descriptor import get_resource
+
+ED25519_CERT = """
+AQQABhtZAaW2GoBED1IjY3A6f6GNqBEl5A83fD2Za9upGke51JGqAQAgBABnprVR
+ptIr43bWPo2fIzo3uOywfoMrryprpbm4HhCkZMaO064LP+1KNuLvlc8sGG8lTjx1
+g4k3ELuWYgHYWU5rAia7nl4gUfBZOEfHAfKES7l3d63dBEjEX98Ljhdp2w4=
+""".strip()
+
+EXPECTED_CERT_KEY = b'\xa5\xb6\x1a\x80D\x0fR#cp:\x7f\xa1\x8d\xa8\x11%\xe4\x0f7|=\x99k\xdb\xa9\x1aG\xb9\xd4\x91\xaa'
+EXPECTED_EXTENSION_DATA = b'g\xa6\xb5Q\xa6\xd2+\xe3v\xd6>\x8d\x9f#:7\xb8\xec\xb0~\x83+\xaf*k\xa5\xb9\xb8\x1e\x10\xa4d'
+EXPECTED_SIGNATURE = b'\xc6\x8e\xd3\xae\x0b?\xedJ6\xe2\xef\x95\xcf,\x18o%N<u\x83\x897\x10\xbb\x96b\x01\xd8YNk\x02&\xbb\x9e^ Q\xf0Y8G\xc7\x01\xf2\x84K\xb9ww\xad\xdd\x04H\xc4_\xdf\x0b\x8e\x17i\xdb\x0e'
+
+
+def certificate(version = 1, cert_type = 4, extension_data = []):
+  """
+  Provides base64 encoded Ed25519 certifificate content.
+
+  :param int version: certificate version
+  :param int cert_type: certificate type
+  :param list extension_data: extensions to embed within the certificate
+  """
+
+  return base64.b64encode(b''.join([
+    stem.util.str_tools._to_bytes(chr(version)),
+    stem.util.str_tools._to_bytes(chr(cert_type)),
+    b'\x00' * 4,               # expiration date, leaving this as the epoch
+    b'\x01',                   # key type
+    b'\x03' * 32,              # key
+    stem.util.str_tools._to_bytes(chr(len(extension_data))),  # extension count
+    b''.join(extension_data),
+    b'\x01' * ED25519_SIGNATURE_LENGTH]))
+
+
+class TestEd25519Certificate(unittest.TestCase):
+  def assert_raises(self, parse_arg, exc_msg):
+    self.assertRaisesRegexp(ValueError, re.escape(exc_msg), Ed25519Certificate.parse, parse_arg)
+
+  def test_basic_parsing(self):
+    """
+    Parse a basic test certificate.
+    """
+
+    signing_key = b'\x11' * 32
+    cert_bytes = certificate(extension_data = [b'\x00\x20\x04\x07' + signing_key, b'\x00\x00\x05\x04'])
+    cert = Ed25519Certificate.parse(cert_bytes)
+
+    self.assertEqual(Ed25519CertificateV1, type(cert))
+    self.assertEqual(1, cert.version)
+    self.assertEqual(cert_bytes, cert.encoded)
+    self.assertEqual(CertType.SIGNING, cert.type)
+    self.assertEqual(datetime.datetime(1970, 1, 1, 0, 0), cert.expiration)
+    self.assertEqual(1, cert.key_type)
+    self.assertEqual(b'\x03' * 32, cert.key)
+    self.assertEqual(b'\x01' * ED25519_SIGNATURE_LENGTH, cert.signature)
+
+    self.assertEqual([
+      Ed25519Extension(type = ExtensionType.HAS_SIGNING_KEY, flags = [ExtensionFlag.AFFECTS_VALIDATION, ExtensionFlag.UNKNOWN], flag_int = 7, data = signing_key),
+      Ed25519Extension(type = 5, flags = [ExtensionFlag.UNKNOWN], flag_int = 4, data = b''),
+    ], cert.extensions)
+
+    self.assertEqual(ExtensionType.HAS_SIGNING_KEY, cert.extensions[0].type)
+    self.assertTrue(cert.is_expired())
+
+  def test_with_real_cert(self):
+    """
+    Parse a certificate from a real server descriptor.
+    """
+
+    cert = Ed25519Certificate.parse(ED25519_CERT)
+
+    self.assertEqual(Ed25519CertificateV1, type(cert))
+    self.assertEqual(1, cert.version)
+    self.assertEqual(ED25519_CERT, cert.encoded)
+    self.assertEqual(CertType.SIGNING, cert.type)
+    self.assertEqual(datetime.datetime(2015, 8, 28, 17, 0), cert.expiration)
+    self.assertEqual(1, cert.key_type)
+    self.assertEqual(EXPECTED_CERT_KEY, cert.key)
+    self.assertEqual([Ed25519Extension(type = 4, flags = [], flag_int = 0, data = EXPECTED_EXTENSION_DATA)], cert.extensions)
+    self.assertEqual(EXPECTED_SIGNATURE, cert.signature)
+
+  def test_non_base64(self):
+    """
+    Parse data that isn't base64 encoded.
+    """
+
+    self.assert_raises('\x02\x0323\x04', "Ed25519 certificate wasn't propoerly base64 encoded (Incorrect padding):")
+
+  def test_too_short(self):
+    """
+    Parse data that's too short to be a valid certificate.
+    """
+
+    self.assert_raises('', "Ed25519 certificate wasn't propoerly base64 encoded (empty):")
+    self.assert_raises('AQQABhtZAaW2GoBED1IjY3A6', 'Ed25519 certificate was 18 bytes, but should be at least 104')
+
+  def test_with_invalid_version(self):
+    """
+    We cannot support other certificate versions until they're documented.
+    Assert we raise if we don't handle a cert version yet.
+    """
+
+    self.assert_raises(certificate(version = 2), 'Ed25519 certificate is version 2. Parser presently only supports version 1.')
+
+  def test_with_invalid_cert_type(self):
+    """
+    Provide an invalid certificate version. Tor specifies a couple ranges that
+    are reserved.
+    """
+
+    self.assert_raises(certificate(cert_type = 0), 'Ed25519 certificate cannot have a type of 0. This is reserved to avoid conflicts with tor CERTS cells.')
+    self.assert_raises(certificate(cert_type = 7), 'Ed25519 certificate cannot have a type of 7. This is reserved for RSA identity cross-certification.')
+
+  def test_truncated_extension(self):
+    """
+    Include an extension without as much data as it specifies.
+    """
+
+    self.assert_raises(certificate(extension_data = [b'']), 'Ed25519 extension is missing header field data')
+    self.assert_raises(certificate(extension_data = [b'\x50\x00\x00\x00\x15\x12']), "Ed25519 extension is truncated. It should have 20480 bytes of data but there's only 2.")
+
+  def test_extra_extension_data(self):
+    """
+    Include an extension with more data than it specifies.
+    """
+
+    self.assert_raises(certificate(extension_data = [b'\x00\x01\x00\x00\x15\x12']), "Ed25519 certificate had 1 bytes of unused extension data")
+
+  def test_truncated_signing_key(self):
+    """
+    Include an extension with an incorrect signing key size.
+    """
+
+    self.assert_raises(certificate(extension_data = [b'\x00\x02\x04\x07\11\12']), "Ed25519 HAS_SIGNING_KEY extension must be 32 bytes, but was 2.")
+
+  def test_validation_with_descriptor_key(self):
+    """
+    Validate a descriptor signature using the ed25519 master key within the
+    descriptor.
+    """
+
+    if not stem.prereq._is_pynacl_available():
+      test.runner.skip(self, '(requires pynacl module)')
+      return
+
+    with open(get_resource('server_descriptor_with_ed25519'), 'rb') as descriptor_file:
+      desc = next(stem.descriptor.parse_file(descriptor_file, validate = False))
+
+    desc.certificate.validate(desc)
+
+  def test_validation_with_embedded_key(self):
+    """
+    Validate a descriptor signature using the signing key within the ed25519
+    certificate.
+    """
+
+    if not stem.prereq._is_pynacl_available():
+      test.runner.skip(self, '(requires pynacl module)')
+      return
+
+    with open(get_resource('server_descriptor_with_ed25519'), 'rb') as descriptor_file:
+      desc = next(stem.descriptor.parse_file(descriptor_file, validate = False))
+
+    desc.ed25519_master_key = None
+    desc.certificate.validate(desc)
+
+  def test_validation_with_invalid_descriptor(self):
+    """
+    Validate a descriptor without a valid signature.
+    """
+
+    if not stem.prereq._is_pynacl_available():
+      test.runner.skip(self, '(requires pynacl module)')
+      return
+
+    with open(get_resource('server_descriptor_with_ed25519'), 'rb') as descriptor_file:
+      desc = next(stem.descriptor.parse_file(descriptor_file, validate = False))
+
+    cert = Ed25519Certificate.parse(certificate())
+    self.assertRaisesRegexp(ValueError, re.escape('Ed25519KeyCertificate signing key is invalid (Signature was forged or corrupt)'), cert.validate, desc)
diff --git a/test/unit/descriptor/extrainfo_descriptor.py b/test/unit/descriptor/extrainfo_descriptor.py
index 79d0b5c2..cab34409 100644
--- a/test/unit/descriptor/extrainfo_descriptor.py
+++ b/test/unit/descriptor/extrainfo_descriptor.py
@@ -3,6 +3,7 @@ Unit tests for stem.descriptor.extrainfo_descriptor.
 """
 
 import datetime
+import re
 import unittest
 
 import stem.descriptor
@@ -172,12 +173,9 @@ k0d2aofcVbHr4fPQOSST0LXDrhFl5Fqo5um296zpJGvRUeO6S44U/EfJAGShtqWw
     """
 
     with open(get_resource('unparseable/extrainfo_nonascii_v3_reqs'), 'rb') as descriptor_file:
-      try:
-        next(stem.descriptor.parse_file(descriptor_file, 'extra-info 1.0', validate = True))
-        self.fail("validation should've raised an exception")
-      except ValueError as exc:
-        expected = "'dirreq-v3-reqs' line had non-ascii content: S?=4026597208,S?=4026597208,S?=4026597208,S?=4026597208,S?=4026597208,S?=4026597208,??=4026591624,6?=4026537520,6?=4026537520,6?=4026537520,us=8"
-        self.assertEqual(expected, str(exc))
+      desc_generator = stem.descriptor.parse_file(descriptor_file, 'extra-info 1.0', validate = True)
+      exc_msg = "'dirreq-v3-reqs' line had non-ascii content: S?=4026597208,S?=4026597208,S?=4026597208,S?=4026597208,S?=4026597208,S?=4026597208,??=4026591624,6?=4026537520,6?=4026537520,6?=4026537520,us=8"
+      self.assertRaisesRegexp(ValueError, re.escape(exc_msg), next, desc_generator)
 
   def test_minimal_extrainfo_descriptor(self):
     """
diff --git a/test/unit/descriptor/microdescriptor.py b/test/unit/descriptor/microdescriptor.py
index 9b3fb2d7..f9350d26 100644
--- a/test/unit/descriptor/microdescriptor.py
+++ b/test/unit/descriptor/microdescriptor.py
@@ -204,8 +204,5 @@ class TestMicrodescriptor(unittest.TestCase):
     desc = Microdescriptor(desc_text)
     self.assertEqual({}, desc.identifiers)
 
-    try:
-      Microdescriptor(desc_text, validate = True)
-      self.fail('constructor validation should fail')
-    except ValueError as exc:
-      self.assertEqual("There can only be one 'id' line per a key type, but 'rsa1024' appeared multiple times", str(exc))
+    exc_msg = "There can only be one 'id' line per a key type, but 'rsa1024' appeared multiple times"
+    self.assertRaisesRegexp(ValueError, exc_msg, Microdescriptor, desc_text, validate = True)
diff --git a/test/unit/descriptor/networkstatus/document_v3.py b/test/unit/descriptor/networkstatus/document_v3.py
index e6e5d76f..6a2e7845 100644
--- a/test/unit/descriptor/networkstatus/document_v3.py
+++ b/test/unit/descriptor/networkstatus/document_v3.py
@@ -4,6 +4,7 @@ Unit tests for the NetworkStatusDocumentV3 of stem.descriptor.networkstatus.
 
 import datetime
 import io
+import re
 import unittest
 
 import stem.descriptor
@@ -1239,15 +1240,9 @@ DnN5aFtYKiTc19qIC7Nmo+afPdDEf0MlJvEOP5EWl3w=
 
     for attr, expected_exception in test_values:
       content = get_directory_authority(attr, content = True)
-
-      try:
-        DirectoryAuthority(content, True)
-        self.fail("validation should've rejected malformed shared randomness attribute")
-      except ValueError as exc:
-        self.assertEqual(expected_exception, str(exc))
+      self.assertRaisesRegexp(ValueError, re.escape(expected_exception), DirectoryAuthority, content, True)
 
       authority = DirectoryAuthority(content, False)
-
       self.assertEqual([], authority.shared_randomness_commitments)
       self.assertEqual(None, authority.shared_randomness_previous_reveal_count)
       self.assertEqual(None, authority.shared_randomness_previous_value)
diff --git a/test/unit/descriptor/server_descriptor.py b/test/unit/descriptor/server_descriptor.py
index ba8271d2..42fa3928 100644
--- a/test/unit/descriptor/server_descriptor.py
+++ b/test/unit/descriptor/server_descriptor.py
@@ -6,8 +6,10 @@ import datetime
 import io
 import pickle
 import tarfile
+import time
 import unittest
 
+import stem.descriptor
 import stem.descriptor.server_descriptor
 import stem.exit_policy
 import stem.prereq
@@ -15,6 +17,7 @@ import stem.version
 import stem.util.str_tools
 
 from stem.util import str_type
+from stem.descriptor.certificate import CertType, ExtensionType
 from stem.descriptor.server_descriptor import RelayDescriptor, BridgeDescriptor
 
 from test.mocking import (
@@ -109,6 +112,7 @@ Qlx9HNCqCY877ztFRC624ja2ql6A2hBcuoYMbkHjcQ4=
     self.assertEqual(9001, desc.or_port)
     self.assertEqual(None, desc.socks_port)
     self.assertEqual(None, desc.dir_port)
+    self.assertEqual(None, desc.certificate)
     self.assertEqual(None, desc.ed25519_certificate)
     self.assertEqual(None, desc.ed25519_master_key)
     self.assertEqual(None, desc.ed25519_signature)
@@ -245,6 +249,7 @@ Qlx9HNCqCY877ztFRC624ja2ql6A2hBcuoYMbkHjcQ4=
 
     self.assertTrue(isinstance(str(desc), str))
 
+  @patch('time.time', Mock(return_value = time.mktime(datetime.date(2010, 1, 1).timetuple())))
   def test_with_ed25519(self):
     """
     Parses a descriptor with a ed25519 identity key, as added by proposal 228
@@ -261,6 +266,21 @@ Qlx9HNCqCY877ztFRC624ja2ql6A2hBcuoYMbkHjcQ4=
       '$EC116BCB80565A408CE67F8EC3FE3B0B02C3A065',
     ])
 
+    self.assertEqual(1, desc.certificate.version)
+    self.assertEqual(CertType.SIGNING, desc.certificate.type)
+    self.assertEqual(datetime.datetime(2015, 8, 28, 17, 0, 0), desc.certificate.expiration)
+    self.assertEqual(1, desc.certificate.key_type)
+    self.assertTrue(desc.certificate.key.startswith(b'\xa5\xb6\x1a\x80D\x0f'))
+    self.assertTrue(desc.certificate.signature.startswith(b'\xc6\x8e\xd3\xae\x0b'))
+    self.assertEqual(1, len(desc.certificate.extensions))
+    self.assertTrue('bWPo2fIzo3uOywfoM' in desc.certificate.encoded)
+
+    extension = desc.certificate.extensions[0]
+    self.assertEqual(ExtensionType.HAS_SIGNING_KEY, extension.type)
+    self.assertEqual([], extension.flags)
+    self.assertEqual(0, extension.flag_int)
+    self.assertTrue(extension.data.startswith(b'g\xa6\xb5Q\xa6\xd2'))
+
     self.assertEqual('destiny', desc.nickname)
     self.assertEqual('F65E0196C94DFFF48AFBF2F5F9E3E19AAE583FD0', desc.fingerprint)
     self.assertEqual('94.242.246.23', desc.address)
@@ -299,6 +319,16 @@ Qlx9HNCqCY877ztFRC624ja2ql6A2hBcuoYMbkHjcQ4=
     self.assertEqual('B5E441051D139CCD84BC765D130B01E44DAC29AD', desc.digest())
     self.assertEqual([], desc.get_unrecognized_lines())
 
+  @patch('time.time', Mock(return_value = time.mktime(datetime.date(2020, 1, 1).timetuple())))
+  def test_with_ed25519_expired_cert(self):
+    """
+    Parses a server descriptor with an expired ed25519 certificate
+    """
+
+    desc_text = open(get_resource('bridge_descriptor_with_ed25519'), 'rb').read()
+    desc_iter = stem.descriptor.server_descriptor._parse_file(io.BytesIO(desc_text), validate = True)
+    self.assertRaises(ValueError, list, desc_iter)
+
   def test_bridge_with_ed25519(self):
     """
     Parses a bridge descriptor with ed25519.
@@ -670,22 +700,16 @@ Qlx9HNCqCY877ztFRC624ja2ql6A2hBcuoYMbkHjcQ4=
     Checks a 'proto' line when it's not key=value pairs.
     """
 
-    try:
-      get_relay_server_descriptor({'proto': 'Desc Link=1-4'})
-      self.fail('Did not raise expected exception')
-    except ValueError as exc:
-      self.assertEqual("Protocol entires are expected to be a series of 'key=value' pairs but was: proto Desc Link=1-4", str(exc))
+    exc_msg = "Protocol entires are expected to be a series of 'key=value' pairs but was: proto Desc Link=1-4"
+    self.assertRaisesRegexp(ValueError, exc_msg, get_relay_server_descriptor, {'proto': 'Desc Link=1-4'})
 
   def test_parse_with_non_int_version(self):
     """
     Checks a 'proto' line with non-numeric content.
     """
 
-    try:
-      get_relay_server_descriptor({'proto': 'Desc=hi Link=1-4'})
-      self.fail('Did not raise expected exception')
-    except ValueError as exc:
-      self.assertEqual('Protocol values should be a number or number range, but was: proto Desc=hi Link=1-4', str(exc))
+    exc_msg = 'Protocol values should be a number or number range, but was: proto Desc=hi Link=1-4'
+    self.assertRaisesRegexp(ValueError, exc_msg, get_relay_server_descriptor, {'proto': 'Desc=hi Link=1-4'})
 
   def test_ntor_onion_key(self):
     """
diff --git a/test/unit/manual.py b/test/unit/manual.py
index 5f939c30..becefd59 100644
--- a/test/unit/manual.py
+++ b/test/unit/manual.py
@@ -4,6 +4,7 @@ Unit testing for the stem.manual module.
 
 import io
 import os
+import re
 import tempfile
 import unittest
 
@@ -234,30 +235,21 @@ class TestManual(unittest.TestCase):
     self.assertTrue(len(manual.config_options) > 200)
 
   def test_download_man_page_without_arguments(self):
-    try:
-      stem.manual.download_man_page()
-      self.fail('we should fail without a path or file handler')
-    except ValueError as exc:
-      self.assertEqual("Either the path or file_handle we're saving to must be provided", str(exc))
+    exc_msg = "Either the path or file_handle we're saving to must be provided"
+    self.assertRaisesRegexp(ValueError, exc_msg, stem.manual.download_man_page)
 
   @patch('stem.util.system.is_available', Mock(return_value = False))
   def test_download_man_page_requires_a2x(self):
-    try:
-      stem.manual.download_man_page('/tmp/no_such_file')
-      self.fail('we should require a2x to be available')
-    except IOError as exc:
-      self.assertEqual('We require a2x from asciidoc to provide a man page', str(exc))
+    exc_msg = 'We require a2x from asciidoc to provide a man page'
+    self.assertRaisesRegexp(IOError, exc_msg, stem.manual.download_man_page, '/tmp/no_such_file')
 
   @patch('tempfile.mkdtemp', Mock(return_value = '/no/such/path'))
   @patch('shutil.rmtree', Mock())
   @patch('stem.manual.open', Mock(side_effect = IOError('unable to write to file')), create = True)
   @patch('stem.util.system.is_available', Mock(return_value = True))
   def test_download_man_page_when_unable_to_write(self):
-    try:
-      stem.manual.download_man_page('/tmp/no_such_file')
-      self.fail("we shouldn't be able to write to /no/such/path")
-    except IOError as exc:
-      self.assertEqual("Unable to download tor's manual from https://gitweb.torproject.org/tor.git/plain/doc/tor.1.txt to /no/such/path/tor.1.txt: unable to write to file", str(exc))
+    exc_msg = "Unable to download tor's manual from https://gitweb.torproject.org/tor.git/plain/doc/tor.1.txt to /no/such/path/tor.1.txt: unable to write to file"
+    self.assertRaisesRegexp(IOError, re.escape(exc_msg), stem.manual.download_man_page, '/tmp/no_such_file')
 
   @patch('tempfile.mkdtemp', Mock(return_value = '/no/such/path'))
   @patch('shutil.rmtree', Mock())
@@ -265,11 +257,8 @@ class TestManual(unittest.TestCase):
   @patch('stem.util.system.is_available', Mock(return_value = True))
   @patch(URL_OPEN, Mock(side_effect = urllib.URLError('<urlopen error [Errno -2] Name or service not known>')))
   def test_download_man_page_when_download_fails(self):
-    try:
-      stem.manual.download_man_page('/tmp/no_such_file', url = 'https://www.atagar.com/foo/bar')
-      self.fail("downloading from test_invalid_url.org shouldn't work")
-    except IOError as exc:
-      self.assertEqual("Unable to download tor's manual from https://www.atagar.com/foo/bar to /no/such/path/tor.1.txt: <urlopen error <urlopen error [Errno -2] Name or service not known>>", str(exc))
+    exc_msg = "Unable to download tor's manual from https://www.atagar.com/foo/bar to /no/such/path/tor.1.txt: <urlopen error <urlopen error [Errno -2] Name or service not known>>"
+    self.assertRaisesRegexp(IOError, re.escape(exc_msg), stem.manual.download_man_page, '/tmp/no_such_file', url = 'https://www.atagar.com/foo/bar')
 
   @patch('tempfile.mkdtemp', Mock(return_value = '/no/such/path'))
   @patch('shutil.rmtree', Mock())
@@ -278,11 +267,8 @@ class TestManual(unittest.TestCase):
   @patch('stem.util.system.is_available', Mock(return_value = True))
   @patch(URL_OPEN, Mock(return_value = io.BytesIO(b'test content')))
   def test_download_man_page_when_a2x_fails(self):
-    try:
-      stem.manual.download_man_page('/tmp/no_such_file', url = 'https://www.atagar.com/foo/bar')
-      self.fail("downloading from test_invalid_url.org shouldn't work")
-    except IOError as exc:
-      self.assertEqual("Unable to run 'a2x -f manpage /no/such/path/tor.1.txt': call failed", str(exc))
+    exc_msg = "Unable to run 'a2x -f manpage /no/such/path/tor.1.txt': call failed"
+    self.assertRaisesRegexp(IOError, exc_msg, stem.manual.download_man_page, '/tmp/no_such_file', url = 'https://www.atagar.com/foo/bar')
 
   @patch('tempfile.mkdtemp', Mock(return_value = '/no/such/path'))
   @patch('shutil.rmtree', Mock())
@@ -307,11 +293,8 @@ class TestManual(unittest.TestCase):
   @patch('stem.util.system.is_mac', Mock(return_value = False))
   @patch('stem.util.system.call', Mock(side_effect = OSError('man --encoding=ascii -P cat tor returned exit status 16')))
   def test_from_man_when_manual_is_unavailable(self):
-    try:
-      stem.manual.Manual.from_man()
-      self.fail("fetching the manual should fail when it's unavailable")
-    except IOError as exc:
-      self.assertEqual("Unable to run 'man --encoding=ascii -P cat tor': man --encoding=ascii -P cat tor returned exit status 16", str(exc))
+    exc_msg = "Unable to run 'man --encoding=ascii -P cat tor': man --encoding=ascii -P cat tor returned exit status 16"
+    self.assertRaisesRegexp(IOError, exc_msg, stem.manual.Manual.from_man)
 
   @patch('stem.util.system.call', Mock(return_value = []))
   def test_when_man_is_empty(self):
diff --git a/test/unit/response/add_onion.py b/test/unit/response/add_onion.py
index 64e36880..1213f0c0 100644
--- a/test/unit/response/add_onion.py
+++ b/test/unit/response/add_onion.py
@@ -95,21 +95,13 @@ class TestAddOnionResponse(unittest.TestCase):
     Checks a response that lack an initial service id.
     """
 
-    try:
-      response = mocking.get_message(WRONG_FIRST_KEY)
-      stem.response.convert('ADD_ONION', response)
-      self.fail("we should've raised a ProtocolError")
-    except stem.ProtocolError as exc:
-      self.assertTrue(str(exc).startswith('ADD_ONION response should start with'))
+    response = mocking.get_message(WRONG_FIRST_KEY)
+    self.assertRaisesRegexp(stem.ProtocolError, 'ADD_ONION response should start with', stem.response.convert, 'ADD_ONION', response)
 
   def test_no_key_type(self):
     """
     Checks a response that's missing the private key type.
     """
 
-    try:
-      response = mocking.get_message(MISSING_KEY_TYPE)
-      stem.response.convert('ADD_ONION', response)
-      self.fail("we should've raised a ProtocolError")
-    except stem.ProtocolError as exc:
-      self.assertTrue(str(exc).startswith('ADD_ONION PrivateKey lines should be of the form'))
+    response = mocking.get_message(MISSING_KEY_TYPE)
+    self.assertRaisesRegexp(stem.ProtocolError, 'ADD_ONION PrivateKey lines should be of the form', stem.response.convert, 'ADD_ONION', response)
diff --git a/test/unit/util/proc.py b/test/unit/util/proc.py
index 72b71312..5f652124 100644
--- a/test/unit/util/proc.py
+++ b/test/unit/util/proc.py
@@ -3,6 +3,7 @@ Unit testing code for the stem.util.proc functions.
 """
 
 import io
+import re
 import unittest
 
 from stem.util import proc
@@ -174,12 +175,8 @@ class TestProc(unittest.TestCase):
     error_msg = "OSError: [Errno 2] No such file or directory: '/proc/2118/fd'"
     listdir_mock.side_effect = OSError(error_msg)
 
-    try:
-      proc.file_descriptors_used(2118)
-      self.fail('We should raise when listdir() fails')
-    except IOError as exc:
-      expected = 'Unable to check number of file descriptors used: %s' % error_msg
-      self.assertEqual(expected, str(exc))
+    exc_msg = 'Unable to check number of file descriptors used: %s' % error_msg
+    self.assertRaisesRegexp(IOError, re.escape(exc_msg), proc.file_descriptors_used, 2118)
 
     # successful calls
 
diff --git a/test/unit/util/str_tools.py b/test/unit/util/str_tools.py
index 3d0936ff..00e5c555 100644
--- a/test/unit/util/str_tools.py
+++ b/test/unit/util/str_tools.py
@@ -9,6 +9,23 @@ from stem.util import str_tools
 
 
 class TestStrTools(unittest.TestCase):
+  def test_to_int(self):
+    """
+    Checks the _to_int() function.
+    """
+
+    test_inputs = {
+      '': 0,
+      'h': 104,
+      'hi': 26729,
+      'hello': 448378203247,
+      str_tools._to_bytes('hello'): 448378203247,
+      str_tools._to_unicode('hello'): 448378203247,
+    }
+
+    for arg, expected in test_inputs.items():
+      self.assertEqual(expected, str_tools._to_int(arg))
+
   def test_to_camel_case(self):
     """
     Checks the _to_camel_case() function.
diff --git a/test/util.py b/test/util.py
index ce1f8e8e..092d8d67 100644
--- a/test/util.py
+++ b/test/util.py
@@ -23,6 +23,7 @@ Tasks are...
   |- check_tor_version - checks our version of tor
   |- check_python_version - checks our version of python
   |- check_cryptography_version - checks our version of cryptography
+  |- check_pynacl_version - checks our version of pynacl
   |- check_pyflakes_version - checks our version of pyflakes
   |- check_pycodestyle_version - checks our version of pycodestyle
   |- clean_orphaned_pyc - removes any *.pyc without a corresponding *.py
@@ -216,8 +217,16 @@ def check_python_version():
 
 def check_cryptography_version():
   if stem.prereq.is_crypto_available():
-    import Crypto
-    return Crypto.__version__
+    import cryptography
+    return cryptography.__version__
+  else:
+    return 'missing'
+
+
+def check_pynacl_version():
+  if stem.prereq._is_pynacl_available():
+    import nacl
+    return nacl.__version__
   else:
     return 'missing'