diff --git a/cryptography/hazmat/backends/interfaces.py b/cryptography/hazmat/backends/interfaces.py
index 912476b..9a57096 100644
--- a/cryptography/hazmat/backends/interfaces.py
+++ b/cryptography/hazmat/backends/interfaces.py
@@ -60,6 +60,13 @@
 
 class HMACBackend(six.with_metaclass(abc.ABCMeta)):
     @abc.abstractmethod
+    def hmac_supported(self, algorithm):
+        """
+        Return True if the hash algorithm is supported for HMAC by this
+        backend.
+        """
+
+    @abc.abstractmethod
     def create_hmac_ctx(self, key, algorithm):
         """
         Create a HashContext for calculating a message authentication code.
diff --git a/cryptography/hazmat/backends/openssl/asn1.py b/cryptography/hazmat/backends/openssl/asn1.py
index 719a523..b56932f 100644
--- a/cryptography/hazmat/backends/openssl/asn1.py
+++ b/cryptography/hazmat/backends/openssl/asn1.py
@@ -41,7 +41,7 @@
 typedef struct {
     ...;
 } ASN1_TIME;
-typedef const ASN1_ITEM ASN1_ITEM_EXP;
+typedef ... ASN1_ITEM_EXP;
 
 typedef ... ASN1_UTCTIME;
 
@@ -102,7 +102,7 @@
 
 MACROS = """
 ASN1_TIME *M_ASN1_TIME_dup(void *);
-ASN1_ITEM *ASN1_ITEM_ptr(ASN1_ITEM *);
+ASN1_ITEM *ASN1_ITEM_ptr(ASN1_ITEM_EXP *);
 
 /* These aren't macros these arguments are all const X on openssl > 1.0.x */
 
@@ -122,3 +122,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/backend.py b/cryptography/hazmat/backends/openssl/backend.py
index bd092be..7b67fb0 100644
--- a/cryptography/hazmat/backends/openssl/backend.py
+++ b/cryptography/hazmat/backends/openssl/backend.py
@@ -56,7 +56,22 @@
 class Backend(object):
     """
     OpenSSL API wrapper.
+
+    Modules listed in the ``_modules`` listed should have the following
+    attributes:
+
+    * ``INCLUDES``: A string containg C includes.
+    * ``TYPES``: A string containing C declarations for types.
+    * ``FUNCTIONS``: A string containing C declarations for functions.
+    * ``MACROS``: A string containing C declarations for any macros.
+    * ``CUSTOMIZATIONS``: A string containing arbitrary top-level C code, this
+        can be used to do things like test for a define and provide an
+        alternate implementation based on that.
+    * ``CONDITIONAL_NAMES``: A dict mapping strings of condition names from the
+        library to a list of names which will not be present without the
+        condition.
     """
+    _module_prefix = "cryptography.hazmat.backends.openssl."
     _modules = [
         "asn1",
         "bignum",
@@ -102,7 +117,7 @@
         macros = []
         customizations = []
         for name in cls._modules:
-            module_name = "cryptography.hazmat.backends.openssl." + name
+            module_name = cls._module_prefix + name
             __import__(module_name)
             module = sys.modules[module_name]
 
@@ -141,6 +156,14 @@
             libraries=["crypto", "ssl"],
         )
 
+        for name in cls._modules:
+            module_name = cls._module_prefix + name
+            module = sys.modules[module_name]
+            for condition, names in module.CONDITIONAL_NAMES.items():
+                if not getattr(lib, condition):
+                    for name in names:
+                        delattr(lib, name)
+
         cls.ffi = ffi
         cls.lib = lib
         cls.lib.OpenSSL_add_all_algorithms()
@@ -161,6 +184,9 @@
         digest = self.lib.EVP_get_digestbyname(algorithm.name.encode("ascii"))
         return digest != self.ffi.NULL
 
+    def hmac_supported(self, algorithm):
+        return self.hash_supported(algorithm)
+
     def create_hash_ctx(self, algorithm):
         return _HashContext(self, algorithm)
 
@@ -276,6 +302,11 @@
         self._operation = operation
         self._tag = None
 
+        if isinstance(self._cipher, interfaces.BlockCipherAlgorithm):
+            self._block_size = self._cipher.block_size
+        else:
+            self._block_size = 1
+
         ctx = self._backend.lib.EVP_CIPHER_CTX_new()
         ctx = self._backend.ffi.gc(ctx, self._backend.lib.EVP_CIPHER_CTX_free)
 
@@ -283,11 +314,19 @@
         try:
             adapter = registry[type(cipher), type(mode)]
         except KeyError:
-            raise UnsupportedAlgorithm
+            raise UnsupportedAlgorithm(
+                "cipher {0} in {1} mode is not supported "
+                "by this backend".format(
+                    cipher.name, mode.name if mode else mode)
+            )
 
         evp_cipher = adapter(self._backend, cipher, mode)
         if evp_cipher == self._backend.ffi.NULL:
-            raise UnsupportedAlgorithm
+            raise UnsupportedAlgorithm(
+                "cipher {0} in {1} mode is not supported "
+                "by this backend".format(
+                    cipher.name, mode.name if mode else mode)
+            )
 
         if isinstance(mode, interfaces.ModeWithInitializationVector):
             iv_nonce = mode.initialization_vector
@@ -309,16 +348,16 @@
         assert res != 0
         if isinstance(mode, GCM):
             res = self._backend.lib.EVP_CIPHER_CTX_ctrl(
-                ctx, self._backend.lib.Cryptography_EVP_CTRL_GCM_SET_IVLEN,
+                ctx, self._backend.lib.EVP_CTRL_GCM_SET_IVLEN,
                 len(iv_nonce), self._backend.ffi.NULL
             )
             assert res != 0
             if operation == self._DECRYPT:
-                if not mode.tag:
-                    raise ValueError("Authentication tag must be supplied "
-                                     "when decrypting")
+                if not mode.tag or len(mode.tag) < 4:
+                    raise ValueError("Authentication tag must be provided and "
+                                     "be 4 bytes or longer when decrypting")
                 res = self._backend.lib.EVP_CIPHER_CTX_ctrl(
-                    ctx, self._backend.lib.Cryptography_EVP_CTRL_GCM_SET_TAG,
+                    ctx, self._backend.lib.EVP_CTRL_GCM_SET_TAG,
                     len(mode.tag), mode.tag
                 )
                 assert res != 0
@@ -341,7 +380,7 @@
 
     def update(self, data):
         buf = self._backend.ffi.new("unsigned char[]",
-                                    len(data) + self._cipher.block_size - 1)
+                                    len(data) + self._block_size - 1)
         outlen = self._backend.ffi.new("int *")
         res = self._backend.lib.EVP_CipherUpdate(self._ctx, buf, outlen, data,
                                                  len(data))
@@ -349,7 +388,7 @@
         return self._backend.ffi.buffer(buf)[:outlen[0]]
 
     def finalize(self):
-        buf = self._backend.ffi.new("unsigned char[]", self._cipher.block_size)
+        buf = self._backend.ffi.new("unsigned char[]", self._block_size)
         outlen = self._backend.ffi.new("int *")
         res = self._backend.lib.EVP_CipherFinal_ex(self._ctx, buf, outlen)
         if res == 0:
@@ -357,10 +396,10 @@
 
         if (isinstance(self._mode, GCM) and
            self._operation == self._ENCRYPT):
-            block_byte_size = self._cipher.block_size // 8
+            block_byte_size = self._block_size // 8
             tag_buf = self._backend.ffi.new("unsigned char[]", block_byte_size)
             res = self._backend.lib.EVP_CIPHER_CTX_ctrl(
-                self._ctx, self._backend.lib.Cryptography_EVP_CTRL_GCM_GET_TAG,
+                self._ctx, self._backend.lib.EVP_CTRL_GCM_GET_TAG,
                 block_byte_size, tag_buf
             )
             assert res != 0
@@ -395,7 +434,11 @@
                                        self._backend.lib.EVP_MD_CTX_destroy)
             evp_md = self._backend.lib.EVP_get_digestbyname(
                 algorithm.name.encode("ascii"))
-            assert evp_md != self._backend.ffi.NULL
+            if evp_md == self._backend.ffi.NULL:
+                raise UnsupportedAlgorithm(
+                    "{0} is not a supported hash on this backend".format(
+                        algorithm.name)
+                )
             res = self._backend.lib.EVP_DigestInit_ex(ctx, evp_md,
                                                       self._backend.ffi.NULL)
             assert res != 0
@@ -437,7 +480,11 @@
             ctx = self._backend.ffi.gc(ctx, self._backend.lib.HMAC_CTX_cleanup)
             evp_md = self._backend.lib.EVP_get_digestbyname(
                 algorithm.name.encode('ascii'))
-            assert evp_md != self._backend.ffi.NULL
+            if evp_md == self._backend.ffi.NULL:
+                raise UnsupportedAlgorithm(
+                    "{0} is not a supported hash on this backend".format(
+                        algorithm.name)
+                )
             res = self._backend.lib.Cryptography_HMAC_Init_ex(
                 ctx, key, len(key), evp_md, self._backend.ffi.NULL
             )
diff --git a/cryptography/hazmat/backends/openssl/bignum.py b/cryptography/hazmat/backends/openssl/bignum.py
index 1b0fe5a..68d0c3a 100644
--- a/cryptography/hazmat/backends/openssl/bignum.py
+++ b/cryptography/hazmat/backends/openssl/bignum.py
@@ -38,3 +38,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/bio.py b/cryptography/hazmat/backends/openssl/bio.py
index c23dd0d..d164804 100644
--- a/cryptography/hazmat/backends/openssl/bio.py
+++ b/cryptography/hazmat/backends/openssl/bio.py
@@ -171,3 +171,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/conf.py b/cryptography/hazmat/backends/openssl/conf.py
index 4846252..6d818cf 100644
--- a/cryptography/hazmat/backends/openssl/conf.py
+++ b/cryptography/hazmat/backends/openssl/conf.py
@@ -27,3 +27,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/crypto.py b/cryptography/hazmat/backends/openssl/crypto.py
index 773d9b1..71d32c5 100644
--- a/cryptography/hazmat/backends/openssl/crypto.py
+++ b/cryptography/hazmat/backends/openssl/crypto.py
@@ -16,6 +16,11 @@
 """
 
 TYPES = """
+static const int SSLEAY_VERSION;
+static const int SSLEAY_CFLAGS;
+static const int SSLEAY_PLATFORM;
+static const int SSLEAY_DIR;
+static const int SSLEAY_BUILT_ON;
 """
 
 FUNCTIONS = """
@@ -24,12 +29,15 @@
 int CRYPTO_is_mem_check_on();
 void CRYPTO_mem_leaks(struct bio_st *);
 void CRYPTO_cleanup_all_ex_data();
+
+void OPENSSL_free(void *);
 """
 
 MACROS = """
 void CRYPTO_add(int *, int, int);
 void CRYPTO_malloc_init();
 void CRYPTO_malloc_debug_init();
+
 #define CRYPTO_MEM_CHECK_ON ...
 #define CRYPTO_MEM_CHECK_OFF ...
 #define CRYPTO_MEM_CHECK_ENABLE ...
@@ -38,3 +46,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/dh.py b/cryptography/hazmat/backends/openssl/dh.py
index b8fbf36..56fa8b4 100644
--- a/cryptography/hazmat/backends/openssl/dh.py
+++ b/cryptography/hazmat/backends/openssl/dh.py
@@ -29,3 +29,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/dsa.py b/cryptography/hazmat/backends/openssl/dsa.py
index e6c369a..3b77d7a 100644
--- a/cryptography/hazmat/backends/openssl/dsa.py
+++ b/cryptography/hazmat/backends/openssl/dsa.py
@@ -31,3 +31,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/engine.py b/cryptography/hazmat/backends/openssl/engine.py
index 1f37766..cc214f8 100644
--- a/cryptography/hazmat/backends/openssl/engine.py
+++ b/cryptography/hazmat/backends/openssl/engine.py
@@ -63,3 +63,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/err.py b/cryptography/hazmat/backends/openssl/err.py
index f31c240..2fb8bbe 100644
--- a/cryptography/hazmat/backends/openssl/err.py
+++ b/cryptography/hazmat/backends/openssl/err.py
@@ -74,3 +74,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/evp.py b/cryptography/hazmat/backends/openssl/evp.py
index 8cb4461..8cf96b2 100644
--- a/cryptography/hazmat/backends/openssl/evp.py
+++ b/cryptography/hazmat/backends/openssl/evp.py
@@ -32,9 +32,11 @@
 } EVP_PKEY;
 static const int EVP_PKEY_RSA;
 static const int EVP_PKEY_DSA;
-static const int Cryptography_EVP_CTRL_GCM_SET_IVLEN;
-static const int Cryptography_EVP_CTRL_GCM_GET_TAG;
-static const int Cryptography_EVP_CTRL_GCM_SET_TAG;
+static const int EVP_CTRL_GCM_SET_IVLEN;
+static const int EVP_CTRL_GCM_GET_TAG;
+static const int EVP_CTRL_GCM_SET_TAG;
+
+static const int Cryptography_HAS_GCM;
 """
 
 FUNCTIONS = """
@@ -101,12 +103,19 @@
 
 CUSTOMIZATIONS = """
 #ifdef EVP_CTRL_GCM_SET_TAG
-const int Cryptography_EVP_CTRL_GCM_GET_TAG = EVP_CTRL_GCM_GET_TAG;
-const int Cryptography_EVP_CTRL_GCM_SET_TAG = EVP_CTRL_GCM_SET_TAG;
-const int Cryptography_EVP_CTRL_GCM_SET_IVLEN = EVP_CTRL_GCM_SET_IVLEN;
+const int Cryptography_HAS_GCM = 1;
 #else
-const int Cryptography_EVP_CTRL_GCM_GET_TAG = -1;
-const int Cryptography_EVP_CTRL_GCM_SET_TAG = -1;
-const int Cryptography_EVP_CTRL_GCM_SET_IVLEN = -1;
+const int Cryptography_HAS_GCM = 0;
+const int EVP_CTRL_GCM_GET_TAG = -1;
+const int EVP_CTRL_GCM_SET_TAG = -1;
+const int EVP_CTRL_GCM_SET_IVLEN = -1;
 #endif
 """
+
+CONDITIONAL_NAMES = {
+    "Cryptography_HAS_GCM": [
+        "EVP_CTRL_GCM_GET_TAG",
+        "EVP_CTRL_GCM_SET_TAG",
+        "EVP_CTRL_GCM_SET_IVLEN",
+    ]
+}
diff --git a/cryptography/hazmat/backends/openssl/hmac.py b/cryptography/hazmat/backends/openssl/hmac.py
index 10e6714..5f9e094 100644
--- a/cryptography/hazmat/backends/openssl/hmac.py
+++ b/cryptography/hazmat/backends/openssl/hmac.py
@@ -88,3 +88,5 @@
 #endif
 }
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/nid.py b/cryptography/hazmat/backends/openssl/nid.py
index 9816dde..111f82f 100644
--- a/cryptography/hazmat/backends/openssl/nid.py
+++ b/cryptography/hazmat/backends/openssl/nid.py
@@ -47,3 +47,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/opensslv.py b/cryptography/hazmat/backends/openssl/opensslv.py
index d463776..4e11032 100644
--- a/cryptography/hazmat/backends/openssl/opensslv.py
+++ b/cryptography/hazmat/backends/openssl/opensslv.py
@@ -16,6 +16,7 @@
 """
 
 TYPES = """
+static const int OPENSSL_VERSION_NUMBER;
 static char *const OPENSSL_VERSION_TEXT;
 """
 
@@ -27,3 +28,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/pem.py b/cryptography/hazmat/backends/openssl/pem.py
index cef7839..ee5552c 100644
--- a/cryptography/hazmat/backends/openssl/pem.py
+++ b/cryptography/hazmat/backends/openssl/pem.py
@@ -55,3 +55,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/pkcs12.py b/cryptography/hazmat/backends/openssl/pkcs12.py
index d91d100..b3ecd0a 100644
--- a/cryptography/hazmat/backends/openssl/pkcs12.py
+++ b/cryptography/hazmat/backends/openssl/pkcs12.py
@@ -35,3 +35,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/pkcs7.py b/cryptography/hazmat/backends/openssl/pkcs7.py
index 60ea3c5..43f9540 100644
--- a/cryptography/hazmat/backends/openssl/pkcs7.py
+++ b/cryptography/hazmat/backends/openssl/pkcs7.py
@@ -35,3 +35,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/rand.py b/cryptography/hazmat/backends/openssl/rand.py
index 848ee05..5ac36ca 100644
--- a/cryptography/hazmat/backends/openssl/rand.py
+++ b/cryptography/hazmat/backends/openssl/rand.py
@@ -19,6 +19,7 @@
 """
 
 FUNCTIONS = """
+void ERR_load_RAND_strings();
 void RAND_seed(const void *, int);
 void RAND_add(const void *, int, double);
 int RAND_status();
@@ -38,3 +39,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/rsa.py b/cryptography/hazmat/backends/openssl/rsa.py
index ad0d37b..e3a24d0 100644
--- a/cryptography/hazmat/backends/openssl/rsa.py
+++ b/cryptography/hazmat/backends/openssl/rsa.py
@@ -57,3 +57,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/ssl.py b/cryptography/hazmat/backends/openssl/ssl.py
index 0461130..3fd0bf2 100644
--- a/cryptography/hazmat/backends/openssl/ssl.py
+++ b/cryptography/hazmat/backends/openssl/ssl.py
@@ -16,6 +16,22 @@
 """
 
 TYPES = """
+/* Internally invented symbol to tell us if SSLv2 is supported */
+static const int Cryptography_HAS_SSL2;
+
+/* Internally invented symbol to tell us if SNI is supported */
+static const int Cryptography_HAS_TLSEXT_HOSTNAME;
+
+/* Internally invented symbol to tell us if SSL_MODE_RELEASE_BUFFERS is
+ * supported
+ */
+static const int Cryptography_HAS_RELEASE_BUFFERS;
+
+/* Internally invented symbol to tell us if SSL_OP_NO_COMPRESSION is
+ * supported
+ */
+static const int Cryptography_HAS_OP_NO_COMPRESSION;
+
 static const int SSL_FILETYPE_PEM;
 static const int SSL_FILETYPE_ASN1;
 static const int SSL_ERROR_NONE;
@@ -30,6 +46,7 @@
 static const int SSL_OP_NO_SSLv2;
 static const int SSL_OP_NO_SSLv3;
 static const int SSL_OP_NO_TLSv1;
+static const int SSL_OP_NO_COMPRESSION;
 static const int SSL_OP_SINGLE_DH_USE;
 static const int SSL_OP_EPHEMERAL_RSA;
 static const int SSL_OP_MICROSOFT_SESS_ID_BUG;
@@ -84,6 +101,7 @@
 static const int SSL_CB_CONNECT_EXIT;
 static const int SSL_CB_HANDSHAKE_START;
 static const int SSL_CB_HANDSHAKE_DONE;
+static const int SSL_MODE_RELEASE_BUFFERS;
 static const int SSL_MODE_ENABLE_PARTIAL_WRITE;
 static const int SSL_MODE_ACCEPT_MOVING_WRITE_BUFFER;
 static const int SSL_MODE_AUTO_RETRY;
@@ -116,7 +134,6 @@
 
 FUNCTIONS = """
 void SSL_load_error_strings();
-
 int SSL_library_init();
 
 /*  SSL */
@@ -126,6 +143,9 @@
 int SSL_get_verify_mode(const SSL *);
 void SSL_set_verify_depth(SSL *, int);
 int SSL_get_verify_depth(const SSL *);
+int (*SSL_get_verify_callback(const SSL *))(int, X509_STORE_CTX *);
+void SSL_set_info_callback(SSL *, void (*)());
+void (*SSL_get_info_callback(const SSL *))();
 SSL *SSL_new(SSL_CTX *);
 void SSL_free(SSL *);
 int SSL_set_fd(SSL *, int);
@@ -147,7 +167,11 @@
 void SSL_CTX_free(SSL_CTX *);
 long SSL_CTX_set_timeout(SSL_CTX *, long);
 int SSL_CTX_set_default_verify_paths(SSL_CTX *);
+void SSL_CTX_set_verify(SSL_CTX *, int, int (*)(int, X509_STORE_CTX *));
 void SSL_CTX_set_verify_depth(SSL_CTX *, int);
+int (*SSL_CTX_get_verify_callback(const SSL_CTX *))(int, X509_STORE_CTX *);
+void SSL_CTX_set_info_callback(SSL_CTX *, void (*)(const SSL *, int, int));
+void (*SSL_CTX_get_info_callback(SSL_CTX *))(const SSL *, int, int);
 int SSL_CTX_get_verify_mode(const SSL_CTX *);
 int SSL_CTX_get_verify_depth(const SSL_CTX *);
 int SSL_CTX_set_cipher_list(SSL_CTX *, const char *);
@@ -173,7 +197,7 @@
 void SSL_SESSION_free(SSL_SESSION *);
 """
 
-MACROS = MACROS = """
+MACROS = """
 long SSL_set_mode(SSL *, long);
 long SSL_get_mode(SSL *);
 
@@ -196,6 +220,15 @@
 
 /*- These aren't macros these functions are all const X on openssl > 1.0.x -*/
 
+/* SSLv2 support is compiled out of some versions of OpenSSL.  These will
+ * get special support when we generate the bindings so that if they are
+ * available they will be wrapped, but if they are not they won't cause
+ * problems (like link errors).
+ */
+const SSL_METHOD *SSLv2_method();
+const SSL_METHOD *SSLv2_server_method();
+const SSL_METHOD *SSLv2_client_method();
+
 /*  methods */
 const SSL_METHOD *SSLv3_method();
 const SSL_METHOD *SSLv3_server_method();
@@ -210,7 +243,71 @@
 /*- These aren't macros these arguments are all const X on openssl > 1.0.x -*/
 SSL_CTX *SSL_CTX_new(const SSL_METHOD *);
 long SSL_CTX_get_timeout(const SSL_CTX *);
+
+/* SNI APIs were introduced in OpenSSL 1.0.0.  To continue to support
+ * earlier versions some special handling of these is necessary.
+ */
+void SSL_set_tlsext_host_name(SSL *, char *);
+void SSL_CTX_set_tlsext_servername_callback(
+    SSL_CTX *,
+    int (*)(const SSL *, int *, void *));
 """
 
 CUSTOMIZATIONS = """
+#ifdef OPENSSL_NO_SSL2
+static const int Cryptography_HAS_SSL2 = 0;
+SSL_METHOD* (*SSLv2_method)() = NULL;
+SSL_METHOD* (*SSLv2_client_method)() = NULL;
+SSL_METHOD* (*SSLv2_server_method)() = NULL;
+#else
+static const int Cryptography_HAS_SSL2 = 1;
+#endif
+
+#ifdef SSL_CTRL_SET_TLSEXT_HOSTNAME
+static const int Cryptography_HAS_TLSEXT_HOSTNAME = 1;
+#else
+static const int Cryptography_HAS_TLSEXT_HOSTNAME = 0;
+void (*SSL_set_tlsext_host_name)(SSL *, char *) = NULL;
+const char* (*SSL_get_servername)(const SSL *, const int) = NULL;
+void (*SSL_CTX_set_tlsext_servername_callback)(
+    SSL_CTX *,
+    int (*)(const SSL *, int *, void *)) = NULL;
+#endif
+
+#ifdef SSL_MODE_RELEASE_BUFFERS
+static const int Cryptography_HAS_RELEASE_BUFFERS = 1;
+#else
+static const int Cryptography_HAS_RELEASE_BUFFERS = 0;
+const int SSL_MODE_RELEASE_BUFFERS = 0;
+#endif
+
+#ifdef SSL_OP_NO_COMPRESSION
+static const int Cryptography_HAS_OP_NO_COMPRESSION = 1;
+#else
+static const int Cryptography_HAS_OP_NO_COMPRESSION = 0;
+const int SSL_OP_NO_COMPRESSION = 0;
+#endif
 """
+
+CONDITIONAL_NAMES = {
+    "Cryptography_HAS_SSL2": [
+        "SSLv2_method",
+        "SSLv2_client_method",
+        "SSLv2_server_method",
+    ],
+
+    "Cryptography_HAS_TLSEXT_HOSTNAME": [
+        "SSL_set_tlsext_host_name",
+        "SSL_get_servername",
+        "SSL_CTX_set_tlsext_servername_callback",
+    ],
+
+    "Cryptography_HAS_RELEASE_BUFFERS": [
+        "SSL_MODE_RELEASE_BUFFERS",
+    ],
+
+    "Cryptography_HAS_OP_NO_COMPRESSION": [
+        "SSL_OP_NO_COMPRESSION",
+    ],
+
+}
diff --git a/cryptography/hazmat/backends/openssl/x509.py b/cryptography/hazmat/backends/openssl/x509.py
index b2ee672..dd7815f 100644
--- a/cryptography/hazmat/backends/openssl/x509.py
+++ b/cryptography/hazmat/backends/openssl/x509.py
@@ -188,3 +188,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/x509name.py b/cryptography/hazmat/backends/openssl/x509name.py
index 896f0ae..4be39b5 100644
--- a/cryptography/hazmat/backends/openssl/x509name.py
+++ b/cryptography/hazmat/backends/openssl/x509name.py
@@ -49,3 +49,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/backends/openssl/x509v3.py b/cryptography/hazmat/backends/openssl/x509v3.py
index bc26236..6d2d236 100644
--- a/cryptography/hazmat/backends/openssl/x509v3.py
+++ b/cryptography/hazmat/backends/openssl/x509v3.py
@@ -95,3 +95,5 @@
 
 CUSTOMIZATIONS = """
 """
+
+CONDITIONAL_NAMES = {}
diff --git a/cryptography/hazmat/primitives/ciphers/algorithms.py b/cryptography/hazmat/primitives/ciphers/algorithms.py
index a206b27..a5cfce9 100644
--- a/cryptography/hazmat/primitives/ciphers/algorithms.py
+++ b/cryptography/hazmat/primitives/ciphers/algorithms.py
@@ -26,6 +26,7 @@
     return key
 
 
+@utils.register_interface(interfaces.BlockCipherAlgorithm)
 @utils.register_interface(interfaces.CipherAlgorithm)
 class AES(object):
     name = "AES"
@@ -40,6 +41,7 @@
         return len(self.key) * 8
 
 
+@utils.register_interface(interfaces.BlockCipherAlgorithm)
 @utils.register_interface(interfaces.CipherAlgorithm)
 class Camellia(object):
     name = "camellia"
@@ -54,6 +56,7 @@
         return len(self.key) * 8
 
 
+@utils.register_interface(interfaces.BlockCipherAlgorithm)
 @utils.register_interface(interfaces.CipherAlgorithm)
 class TripleDES(object):
     name = "3DES"
@@ -72,6 +75,7 @@
         return len(self.key) * 8
 
 
+@utils.register_interface(interfaces.BlockCipherAlgorithm)
 @utils.register_interface(interfaces.CipherAlgorithm)
 class Blowfish(object):
     name = "Blowfish"
@@ -86,6 +90,7 @@
         return len(self.key) * 8
 
 
+@utils.register_interface(interfaces.BlockCipherAlgorithm)
 @utils.register_interface(interfaces.CipherAlgorithm)
 class CAST5(object):
     name = "CAST5"
@@ -103,7 +108,6 @@
 @utils.register_interface(interfaces.CipherAlgorithm)
 class ARC4(object):
     name = "RC4"
-    block_size = 1
     key_sizes = frozenset([40, 56, 64, 80, 128, 192, 256])
 
     def __init__(self, key):
diff --git a/cryptography/hazmat/primitives/constant_time.py b/cryptography/hazmat/primitives/constant_time.py
index a835150..6502803 100644
--- a/cryptography/hazmat/primitives/constant_time.py
+++ b/cryptography/hazmat/primitives/constant_time.py
@@ -20,17 +20,16 @@
 
 _ffi = cffi.FFI()
 _ffi.cdef("""
-bool Cryptography_constant_time_bytes_eq(uint8_t *, size_t, uint8_t *, size_t);
+uint8_t Cryptography_constant_time_bytes_eq(uint8_t *, size_t, uint8_t *,
+                                            size_t);
 """)
 _lib = _ffi.verify("""
-#include <stdbool.h>
-
-bool Cryptography_constant_time_bytes_eq(uint8_t *a, size_t len_a, uint8_t *b,
-                                         size_t len_b) {
+uint8_t Cryptography_constant_time_bytes_eq(uint8_t *a, size_t len_a,
+                                            uint8_t *b, size_t len_b) {
     size_t i = 0;
     uint8_t mismatch = 0;
     if (len_a != len_b) {
-        return false;
+        return 0;
     }
     for (i = 0; i < len_a; i++) {
         mismatch |= a[i] ^ b[i];
diff --git a/cryptography/hazmat/primitives/interfaces.py b/cryptography/hazmat/primitives/interfaces.py
index 76dc933..c6377df 100644
--- a/cryptography/hazmat/primitives/interfaces.py
+++ b/cryptography/hazmat/primitives/interfaces.py
@@ -22,13 +22,21 @@
     @abc.abstractproperty
     def name(self):
         """
-        A string naming this mode.  (e.g. AES, Camellia)
+        A string naming this mode (e.g. "AES", "Camellia").
         """
 
     @abc.abstractproperty
     def key_size(self):
         """
-        The size of the key being used as an integer in bits.  (e.g. 128, 256)
+        The size of the key being used as an integer in bits (e.g. 128, 256).
+        """
+
+
+class BlockCipherAlgorithm(six.with_metaclass(abc.ABCMeta)):
+    @abc.abstractproperty
+    def block_size(self):
+        """
+        The size of a block as an integer in bits (e.g. 64, 128).
         """
 
 
@@ -36,7 +44,7 @@
     @abc.abstractproperty
     def name(self):
         """
-        A string naming this mode.  (e.g. ECB, CBC)
+        A string naming this mode (e.g. "ECB", "CBC").
         """
 
 
@@ -68,13 +76,14 @@
     @abc.abstractmethod
     def update(self, data):
         """
-        update takes bytes and return bytes
+        Processes the provided bytes through the cipher and returns the results
+        as bytes.
         """
 
     @abc.abstractmethod
     def finalize(self):
         """
-        finalize return bytes
+        Returns the results of processing the final block as bytes.
         """
 
 
@@ -82,7 +91,7 @@
     @abc.abstractmethod
     def authenticate_additional_data(self, data):
         """
-        authenticate_additional_data takes bytes and returns nothing.
+        Authenticates the provided bytes.
         """
 
 
@@ -90,7 +99,8 @@
     @abc.abstractproperty
     def tag(self):
         """
-        Returns tag bytes after finalizing encryption.
+        Returns tag bytes. This is only available after encryption is
+        finalized.
         """
 
 
@@ -98,13 +108,13 @@
     @abc.abstractmethod
     def update(self, data):
         """
-        update takes bytes and return bytes
+        Pads the provided bytes and returns any available data as bytes.
         """
 
     @abc.abstractmethod
     def finalize(self):
         """
-        finalize return bytes
+        Finalize the padding, returns bytes.
         """
 
 
@@ -112,7 +122,7 @@
     @abc.abstractproperty
     def name(self):
         """
-        A string naming this algorithm. (e.g. sha256, md5)
+        A string naming this algorithm (e.g. "sha256", "md5").
         """
 
     @abc.abstractproperty
@@ -138,19 +148,19 @@
     @abc.abstractmethod
     def update(self, data):
         """
-        hash data as bytes
+        Processes the provided bytes through the hash.
         """
 
     @abc.abstractmethod
     def finalize(self):
         """
-        finalize this copy of the hash and return the digest as bytes.
+        Finalizes the hash context and returns the hash digest as bytes.
         """
 
     @abc.abstractmethod
     def copy(self):
         """
-        return a HashContext that is a copy of the current context.
+        Return a HashContext that is a copy of the current context.
         """
 
     @abc.abstractmethod
diff --git a/cryptography/hazmat/primitives/padding.py b/cryptography/hazmat/primitives/padding.py
index cfa90db..e517dee 100644
--- a/cryptography/hazmat/primitives/padding.py
+++ b/cryptography/hazmat/primitives/padding.py
@@ -21,11 +21,9 @@
 
 _ffi = cffi.FFI()
 _ffi.cdef("""
-bool Cryptography_check_pkcs7_padding(const uint8_t *, uint8_t);
+uint8_t Cryptography_check_pkcs7_padding(const uint8_t *, uint8_t);
 """)
 _lib = _ffi.verify("""
-#include <stdbool.h>
-
 /* Returns the value of the input with the most-significant-bit copied to all
    of the bits. */
 static uint8_t Cryptography_DUPLICATE_MSB_TO_ALL(uint8_t a) {
@@ -39,7 +37,8 @@
     return Cryptography_DUPLICATE_MSB_TO_ALL(a);
 }
 
-bool Cryptography_check_pkcs7_padding(const uint8_t *data, uint8_t block_len) {
+uint8_t Cryptography_check_pkcs7_padding(const uint8_t *data,
+                                         uint8_t block_len) {
     uint8_t i;
     uint8_t pad_size = data[block_len - 1];
     uint8_t mismatch = 0;
diff --git a/docs/api-stability.rst b/docs/api-stability.rst
new file mode 100644
index 0000000..e87cc14
--- /dev/null
+++ b/docs/api-stability.rst
@@ -0,0 +1,51 @@
+API Stability
+=============
+
+From its first release, ``cryptography`` will have a strong API stability
+policy.
+
+What does this policy cover?
+----------------------------
+
+This policy includes any API or behavior which is documented in this
+documentation.
+
+What does "stable" mean?
+------------------------
+
+* Public APIs will not be removed or renamed without providing a compatibility
+  alias.
+* The behavior of existing APIs will not change.
+
+What doesn't this policy cover?
+-------------------------------
+
+* We may add new features, things like the result of ``dir(obj))`` or the
+  contents of ``obj.__dict__`` may change.
+* Objects are not guaranteed to be pickleable, and pickled objects from one
+  version of ``cryptography`` may not be loadable in future versions.
+* Development versions of ``cryptography``. Before a feature is in a release,
+  it is not covered by this policy and may change.
+
+Security
+~~~~~~~~
+
+One exception to our API stability policy is for security. We will violate this
+policy as necessary in order to resolve a security issue or harden
+``cryptography`` against a possible attack.
+
+Deprecation
+-----------
+
+From time to time we will want to change the behavior of an API or remove it
+entirely. In that case, here's how the process will work:
+
+* In ``cryptography X.Y`` the feature exists.
+* In ``cryptography X.Y+1`` using that feature will emit a
+  ``PendingDeprecationWarning``.
+* In ``cryptography X.Y+2`` using that feature will emit a
+  ``DeprecationWarning``.
+* In ``cryptography X.Y+3`` the feature will be removed or changed.
+
+In short, code which runs without warnings will always continue to work for a
+period of two releases.
diff --git a/docs/contributing.rst b/docs/contributing.rst
index cb9c728..620e1b6 100644
--- a/docs/contributing.rst
+++ b/docs/contributing.rst
@@ -53,11 +53,10 @@
 
 Most projects' APIs are designed with a philosophy of "make easy things easy,
 and make hard things possible". One of the perils of writing cryptographic code
-is that code that is secure looks just like code that isn't, and produces
-results that are also difficult to distinguish. As a result ``cryptography``
-has, as a design philosophy: "make it hard to do insecure things". Here are a
-few strategies for API design which should be both followed, and should inspire
-other API choices:
+is that secure code looks just like insecure code, and its results are almost
+always indistinguishable. As a result ``cryptography`` has, as a design
+philosophy: "make it hard to do insecure things". Here are a few strategies for
+API design which should be both followed, and should inspire other API choices:
 
 If it is incorrect to ignore the result of a method, it should raise an
 exception, and not return a boolean ``True``/``False`` flag. For example, a
@@ -77,6 +76,10 @@
         if not is_valid:
             raise InvalidSignature
 
+Every recipe should include a version or algorithmic marker of some sort in its
+output in order to allow transparent upgrading of the algorithms in use, as
+the algorithms or parameters needed to achieve a given security margin evolve.
+
 APIs at the :doc:`/hazmat/primitives/index` layer should always take an
 explicit backend, APIs at the recipes layer should automatically use the
 :func:`~cryptography.hazmat.backends.default_backend`, but optionally allow
@@ -133,7 +136,6 @@
     // Bad
     long f(int,char *)
 
-
 Documentation
 -------------
 
@@ -163,7 +165,7 @@
 
 * When documenting a generic interface, use a strong algorithm in examples.
   (e.g. when showing a hashing example, don't use
-  :class:`cryptography.hazmat.primitives.hashes.MD5`)
+  :class:`~cryptography.hazmat.primitives.hashes.MD5`)
 * When giving prescriptive advice, always provide references and supporting
   material.
 * When there is real disagreement between cryptographic experts, represent both
@@ -206,7 +208,7 @@
 
    $ py.test
    ...
-   4294 passed in 15.24 seconds
+   62746 passed in 220.43 seconds
 
 This runs the tests with the default Python interpreter.
 
@@ -244,7 +246,8 @@
    docs: commands succeeded
    congratulations :)
 
-The HTML documentation index can now be found at ``docs/_build/html/index.html``
+The HTML documentation index can now be found at
+``docs/_build/html/index.html``.
 
 
 .. _`GitHub`: https://github.com/pyca/cryptography
diff --git a/docs/hazmat/backends/index.rst b/docs/hazmat/backends/index.rst
index a89cf0d..0695128 100644
--- a/docs/hazmat/backends/index.rst
+++ b/docs/hazmat/backends/index.rst
@@ -1,17 +1,10 @@
 .. hazmat::
 
-Bindings
+Backends
 ========
 
-.. toctree::
-    :maxdepth: 1
-
-    openssl
-    interfaces
-
-
-Getting a Backend Provider
-~~~~~~~~~~~~~~~~~~~~~~~~~~
+Getting a Backend
+-----------------
 
 .. currentmodule:: cryptography.hazmat.backends
 
@@ -19,8 +12,7 @@
 the widest number of supported cryptographic algorithms as well as supporting
 platform specific implementations.
 
-You can get the default backend by calling
-:func:`~default_backend`.
+You can get the default backend by calling :func:`~default_backend`.
 
 The default backend will change over time as we implement new backends and
 the libraries we use in those backends changes.
@@ -32,3 +24,11 @@
         :class:`~interfaces.CipherBackend`, :class:`~interfaces.HashBackend`, and
         :class:`~interfaces.HMACBackend`.
 
+Individual Backends
+-------------------
+
+.. toctree::
+    :maxdepth: 1
+
+    openssl
+    interfaces
diff --git a/docs/hazmat/backends/interfaces.rst b/docs/hazmat/backends/interfaces.rst
index b524943..5b6cd64 100644
--- a/docs/hazmat/backends/interfaces.rst
+++ b/docs/hazmat/backends/interfaces.rst
@@ -126,6 +126,17 @@
     A backend with methods for using cryptographic hash functions as message
     authentication codes.
 
+    .. method:: hmac_supported(algorithm)
+
+        Check if the specified ``algorithm`` is supported by this backend.
+
+        :param algorithm: An instance of a
+            :class:`~cryptography.hazmat.primitives.interfaces.HashAlgorithm`
+            provider.
+
+        :returns: ``True`` if the specified ``algorithm`` is supported for HMAC
+            by this backend, otherwise ``False``.
+
     .. method:: create_hmac_ctx(algorithm)
 
         Create a
diff --git a/docs/hazmat/backends/openssl.rst b/docs/hazmat/backends/openssl.rst
index 12fbff0..5e51c75 100644
--- a/docs/hazmat/backends/openssl.rst
+++ b/docs/hazmat/backends/openssl.rst
@@ -1,7 +1,7 @@
 .. hazmat::
 
-OpenSSL
-=======
+OpenSSL Backend
+===============
 
 These are `CFFI`_ bindings to the `OpenSSL`_ C library.
 
diff --git a/docs/hazmat/primitives/cryptographic-hashes.rst b/docs/hazmat/primitives/cryptographic-hashes.rst
index f6a3f7a..f00dd3f 100644
--- a/docs/hazmat/primitives/cryptographic-hashes.rst
+++ b/docs/hazmat/primitives/cryptographic-hashes.rst
@@ -28,6 +28,9 @@
         >>> digest.finalize()
         'l\xa1=R\xcap\xc8\x83\xe0\xf0\xbb\x10\x1eBZ\x89\xe8bM\xe5\x1d\xb2\xd29%\x93\xafj\x84\x11\x80\x90'
 
+    If the backend doesn't support the requested ``algorithm`` an
+    :class:`~cryptography.exceptions.UnsupportedAlgorithm` will be raised.
+
     Keep in mind that attacks against cryptographic hashes only get stronger
     with time, and that often algorithms that were once thought to be strong,
     become broken. Because of this it's important to include a plan for
diff --git a/docs/hazmat/primitives/hmac.rst b/docs/hazmat/primitives/hmac.rst
index 0c19f20..b8f94fd 100644
--- a/docs/hazmat/primitives/hmac.rst
+++ b/docs/hazmat/primitives/hmac.rst
@@ -34,6 +34,8 @@
         >>> h.finalize()
         '#F\xdaI\x8b"e\xc4\xf1\xbb\x9a\x8fc\xff\xf5\xdex.\xbc\xcd/+\x8a\x86\x1d\x84\'\xc3\xa6\x1d\xd8J'
 
+    If the backend doesn't support the requested ``algorithm`` an
+    :class:`~cryptography.exceptions.UnsupportedAlgorithm` will be raised.
 
     :param key: Secret key as ``bytes``.
     :param algorithm: A
diff --git a/docs/hazmat/primitives/interfaces.rst b/docs/hazmat/primitives/interfaces.rst
index 11cff51..361b723 100644
--- a/docs/hazmat/primitives/interfaces.rst
+++ b/docs/hazmat/primitives/interfaces.rst
@@ -36,6 +36,17 @@
         The number of bits in the key being used.
 
 
+.. class:: BlockCipherAlgorithm
+
+    A block cipher algorithm.
+
+    .. attribute:: block_size
+
+        :type: int
+
+        The number of bits in a block.
+
+
 Cipher Modes
 ------------
 
diff --git a/docs/hazmat/primitives/symmetric-encryption.rst b/docs/hazmat/primitives/symmetric-encryption.rst
index f4d0457..30896a0 100644
--- a/docs/hazmat/primitives/symmetric-encryption.rst
+++ b/docs/hazmat/primitives/symmetric-encryption.rst
@@ -61,7 +61,7 @@
             provider.
 
         If the backend doesn't support the requested combination of ``cipher``
-        and ``mode`` an :class:`cryptography.exceptions.UnsupportedAlgorithm`
+        and ``mode`` an :class:`~cryptography.exceptions.UnsupportedAlgorithm`
         will be raised.
 
     .. method:: decryptor()
@@ -352,6 +352,16 @@
                                         Do not reuse an ``initialization_vector``
                                         with a given ``key``.
 
+    .. note::
+
+        Cryptography will emit a 128-bit tag when finalizing encryption.
+        You can shorten a tag by truncating it to the desired length, but this
+        is **not recommended** as it lowers the security margins of the
+        authentication (`NIST SP-800-38D`_ recommends 96-bits or greater).
+        If you must shorten the tag the minimum allowed length is 4 bytes
+        (32-bits). Applications **must** verify the tag is the expected length
+        to guarantee the expected security margin.
+
     :param bytes tag: The tag bytes to verify during decryption. When encrypting
                       this must be None.
 
@@ -390,3 +400,4 @@
 
 .. _`described by Colin Percival`: http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html
 .. _`recommends 96-bit IV length`: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf
+.. _`NIST SP-800-38D`: http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
diff --git a/docs/index.rst b/docs/index.rst
index 381063d..70558bd 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -75,4 +75,5 @@
 
     contributing
     security
+    api-stability
     community
diff --git a/pytest.ini b/pytest.ini
index 723735a..1aeb23f 100644
--- a/pytest.ini
+++ b/pytest.ini
@@ -1,2 +1,6 @@
 [pytest]
 addopts = -r s
+markers =
+    hmac: this test requires a backend providing HMACBackend
+    cipher: this test requires a backend providing CipherBackend
+    hash: this test requires a backend providing HashBackend
diff --git a/tests/conftest.py b/tests/conftest.py
index 7166280..e059b63 100644
--- a/tests/conftest.py
+++ b/tests/conftest.py
@@ -1,5 +1,21 @@
+import pytest
+
+from cryptography.hazmat.backends.interfaces import (
+    HMACBackend, CipherBackend, HashBackend
+)
+
+from .utils import check_for_iface
+
+
 def pytest_generate_tests(metafunc):
     from cryptography.hazmat.backends import _ALL_BACKENDS
 
     if "backend" in metafunc.fixturenames:
         metafunc.parametrize("backend", _ALL_BACKENDS)
+
+
+@pytest.mark.trylast
+def pytest_runtest_setup(item):
+    check_for_iface("hmac", HMACBackend, item)
+    check_for_iface("cipher", CipherBackend, item)
+    check_for_iface("hash", HashBackend, item)
diff --git a/tests/hazmat/backends/test_openssl.py b/tests/hazmat/backends/test_openssl.py
index 962959b..543a05f 100644
--- a/tests/hazmat/backends/test_openssl.py
+++ b/tests/hazmat/backends/test_openssl.py
@@ -23,13 +23,14 @@
 from cryptography.hazmat.primitives.ciphers.modes import CBC
 
 
+@utils.register_interface(interfaces.Mode)
 class DummyMode(object):
-    pass
+    name = "dummy-mode"
 
 
 @utils.register_interface(interfaces.CipherAlgorithm)
 class DummyCipher(object):
-    pass
+    name = "dummy-cipher"
 
 
 class TestOpenSSL(object):
@@ -62,15 +63,16 @@
         assert b.ffi is backend.ffi
         assert b.lib is backend.lib
 
-    def test_nonexistent_cipher(self):
+    @pytest.mark.parametrize("mode", [DummyMode(), None])
+    def test_nonexistent_cipher(self, mode):
         b = Backend()
         b.register_cipher_adapter(
             DummyCipher,
-            DummyMode,
+            type(mode),
             lambda backend, cipher, mode: backend.ffi.NULL
         )
         cipher = Cipher(
-            DummyCipher(), DummyMode(), backend=b,
+            DummyCipher(), mode, backend=b,
         )
         with pytest.raises(UnsupportedAlgorithm):
             cipher.encryptor()
diff --git a/tests/hazmat/primitives/test_3des.py b/tests/hazmat/primitives/test_3des.py
index 69ec9c9..439ca25 100644
--- a/tests/hazmat/primitives/test_3des.py
+++ b/tests/hazmat/primitives/test_3des.py
@@ -20,12 +20,15 @@
 import binascii
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives.ciphers import algorithms, modes
 
 from .utils import generate_encrypt_test
 from ...utils import load_nist_vectors
 
 
+@pytest.mark.cipher
 class TestTripleDES_CBC(object):
     test_KAT = generate_encrypt_test(
         load_nist_vectors,
@@ -37,8 +40,12 @@
             "TCBCvarkey.rsp",
             "TCBCvartext.rsp",
         ],
-        lambda keys, iv: algorithms.TripleDES(binascii.unhexlify(keys)),
-        lambda keys, iv: modes.CBC(binascii.unhexlify(iv)),
+        lambda keys, **kwargs: algorithms.TripleDES(binascii.unhexlify(keys)),
+        lambda iv, **kwargs: modes.CBC(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.TripleDES("\x00" * 8), modes.CBC("\x00" * 8)
+        ),
+        skip_message="Does not support TripleDES CBC",
     )
 
     test_MMT = generate_encrypt_test(
@@ -49,13 +56,18 @@
             "TCBCMMT2.rsp",
             "TCBCMMT3.rsp",
         ],
-        lambda key1, key2, key3, iv: (
-            algorithms.TripleDES(binascii.unhexlify(key1 + key2 + key3))
+        lambda key1, key2, key3, **kwargs: algorithms.TripleDES(
+            binascii.unhexlify(key1 + key2 + key3)
         ),
-        lambda key1, key2, key3, iv: modes.CBC(binascii.unhexlify(iv)),
+        lambda iv, **kwargs: modes.CBC(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.TripleDES("\x00" * 8), modes.CBC("\x00" * 8)
+        ),
+        skip_message="Does not support TripleDES CBC",
     )
 
 
+@pytest.mark.cipher
 class TestTripleDES_OFB(object):
     test_KAT = generate_encrypt_test(
         load_nist_vectors,
@@ -67,8 +79,12 @@
             "TOFBvartext.rsp",
             "TOFBinvperm.rsp",
         ],
-        lambda keys, iv: algorithms.TripleDES(binascii.unhexlify(keys)),
-        lambda keys, iv: modes.OFB(binascii.unhexlify(iv)),
+        lambda keys, **kwargs: algorithms.TripleDES(binascii.unhexlify(keys)),
+        lambda iv, **kwargs: modes.OFB(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.TripleDES("\x00" * 8), modes.OFB("\x00" * 8)
+        ),
+        skip_message="Does not support TripleDES OFB",
     )
 
     test_MMT = generate_encrypt_test(
@@ -79,13 +95,18 @@
             "TOFBMMT2.rsp",
             "TOFBMMT3.rsp",
         ],
-        lambda key1, key2, key3, iv: (
-            algorithms.TripleDES(binascii.unhexlify(key1 + key2 + key3))
+        lambda key1, key2, key3, **kwargs: algorithms.TripleDES(
+            binascii.unhexlify(key1 + key2 + key3)
         ),
-        lambda key1, key2, key3, iv: modes.OFB(binascii.unhexlify(iv)),
+        lambda iv, **kwargs: modes.OFB(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.TripleDES("\x00" * 8), modes.OFB("\x00" * 8)
+        ),
+        skip_message="Does not support TripleDES OFB",
     )
 
 
+@pytest.mark.cipher
 class TestTripleDES_CFB(object):
     test_KAT = generate_encrypt_test(
         load_nist_vectors,
@@ -97,8 +118,12 @@
             "TCFB64varkey.rsp",
             "TCFB64vartext.rsp",
         ],
-        lambda keys, iv: algorithms.TripleDES(binascii.unhexlify(keys)),
-        lambda keys, iv: modes.CFB(binascii.unhexlify(iv)),
+        lambda keys, **kwargs: algorithms.TripleDES(binascii.unhexlify(keys)),
+        lambda iv, **kwargs: modes.CFB(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.TripleDES("\x00" * 8), modes.CFB("\x00" * 8)
+        ),
+        skip_message="Does not support TripleDES CFB",
     )
 
     test_MMT = generate_encrypt_test(
@@ -109,8 +134,12 @@
             "TCFB64MMT2.rsp",
             "TCFB64MMT3.rsp",
         ],
-        lambda key1, key2, key3, iv: (
-            algorithms.TripleDES(binascii.unhexlify(key1 + key2 + key3))
+        lambda key1, key2, key3, **kwargs: algorithms.TripleDES(
+            binascii.unhexlify(key1 + key2 + key3)
         ),
-        lambda key1, key2, key3, iv: modes.CFB(binascii.unhexlify(iv)),
+        lambda iv, **kwargs: modes.CFB(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.TripleDES("\x00" * 8), modes.CFB("\x00" * 8)
+        ),
+        skip_message="Does not support TripleDES CFB",
     )
diff --git a/tests/hazmat/primitives/test_aes.py b/tests/hazmat/primitives/test_aes.py
index f7b0b9a..e9ef385 100644
--- a/tests/hazmat/primitives/test_aes.py
+++ b/tests/hazmat/primitives/test_aes.py
@@ -16,6 +16,8 @@
 import binascii
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives.ciphers import algorithms, modes
 
 from .utils import generate_encrypt_test, generate_aead_test
@@ -24,6 +26,7 @@
 )
 
 
+@pytest.mark.cipher
 class TestAES(object):
     test_CBC = generate_encrypt_test(
         load_nist_vectors,
@@ -45,8 +48,12 @@
             "CBCMMT192.rsp",
             "CBCMMT256.rsp",
         ],
-        lambda key, iv: algorithms.AES(binascii.unhexlify(key)),
-        lambda key, iv: modes.CBC(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.AES(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CBC(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.AES("\x00" * 16), modes.CBC("\x00" * 16)
+        ),
+        skip_message="Does not support AES CBC",
     )
 
     test_ECB = generate_encrypt_test(
@@ -69,8 +76,12 @@
             "ECBMMT192.rsp",
             "ECBMMT256.rsp",
         ],
-        lambda key: algorithms.AES(binascii.unhexlify(key)),
-        lambda key: modes.ECB(),
+        lambda key, **kwargs: algorithms.AES(binascii.unhexlify(key)),
+        lambda **kwargs: modes.ECB(),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.AES("\x00" * 16), modes.ECB()
+        ),
+        skip_message="Does not support AES ECB",
     )
 
     test_OFB = generate_encrypt_test(
@@ -93,8 +104,12 @@
             "OFBMMT192.rsp",
             "OFBMMT256.rsp",
         ],
-        lambda key, iv: algorithms.AES(binascii.unhexlify(key)),
-        lambda key, iv: modes.OFB(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.AES(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.OFB(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.AES("\x00" * 16), modes.OFB("\x00" * 16)
+        ),
+        skip_message="Does not support AES OFB",
     )
 
     test_CFB = generate_encrypt_test(
@@ -117,16 +132,20 @@
             "CFB128MMT192.rsp",
             "CFB128MMT256.rsp",
         ],
-        lambda key, iv: algorithms.AES(binascii.unhexlify(key)),
-        lambda key, iv: modes.CFB(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.AES(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CFB(binascii.unhexlify(iv)),
+        only_if=lambda backend: backend.cipher_supported(
+            algorithms.AES("\x00" * 16), modes.CFB("\x00" * 16)
+        ),
+        skip_message="Does not support AES CFB",
     )
 
     test_CTR = generate_encrypt_test(
         load_openssl_vectors,
         os.path.join("ciphers", "AES", "CTR"),
         ["aes-128-ctr.txt", "aes-192-ctr.txt", "aes-256-ctr.txt"],
-        lambda key, iv: algorithms.AES(binascii.unhexlify(key)),
-        lambda key, iv: modes.CTR(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.AES(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CTR(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.AES("\x00" * 16), modes.CTR("\x00" * 16)
         ),
diff --git a/tests/hazmat/primitives/test_arc4.py b/tests/hazmat/primitives/test_arc4.py
index d233bec..f2e2452 100644
--- a/tests/hazmat/primitives/test_arc4.py
+++ b/tests/hazmat/primitives/test_arc4.py
@@ -16,12 +16,15 @@
 import binascii
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives.ciphers import algorithms
 
 from .utils import generate_stream_encryption_test
 from ...utils import load_nist_vectors
 
 
+@pytest.mark.cipher
 class TestARC4(object):
     test_rfc = generate_stream_encryption_test(
         load_nist_vectors,
@@ -35,7 +38,7 @@
             "rfc-6229-192.txt",
             "rfc-6229-256.txt",
         ],
-        lambda key: algorithms.ARC4(binascii.unhexlify((key))),
+        lambda key, **kwargs: algorithms.ARC4(binascii.unhexlify(key)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.ARC4("\x00" * 16), None
         ),
diff --git a/tests/hazmat/primitives/test_block.py b/tests/hazmat/primitives/test_block.py
index 02de386..22a7c02 100644
--- a/tests/hazmat/primitives/test_block.py
+++ b/tests/hazmat/primitives/test_block.py
@@ -31,11 +31,17 @@
 )
 
 
+@utils.register_interface(interfaces.Mode)
+class DummyMode(object):
+    name = "dummy-mode"
+
+
 @utils.register_interface(interfaces.CipherAlgorithm)
 class DummyCipher(object):
-    pass
+    name = "dummy-cipher"
 
 
+@pytest.mark.cipher
 class TestCipher(object):
     def test_creates_encryptor(self, backend):
         cipher = Cipher(
@@ -59,6 +65,7 @@
             Cipher(algorithm, mode=None, backend=backend)
 
 
+@pytest.mark.cipher
 class TestCipherContext(object):
     def test_use_after_finalize(self, backend):
         cipher = Cipher(
@@ -101,9 +108,10 @@
         assert pt == b"a" * 80
         decryptor.finalize()
 
-    def test_nonexistent_cipher(self, backend):
+    @pytest.mark.parametrize("mode", [DummyMode(), None])
+    def test_nonexistent_cipher(self, backend, mode):
         cipher = Cipher(
-            DummyCipher(), object(), backend
+            DummyCipher(), mode, backend
         )
         with pytest.raises(UnsupportedAlgorithm):
             cipher.encryptor()
@@ -128,6 +136,7 @@
             decryptor.finalize()
 
 
+@pytest.mark.cipher
 class TestAEADCipherContext(object):
     test_aead_exceptions = generate_aead_exception_test(
         algorithms.AES,
diff --git a/tests/hazmat/primitives/test_blowfish.py b/tests/hazmat/primitives/test_blowfish.py
index d5fbed6..79ceabe 100644
--- a/tests/hazmat/primitives/test_blowfish.py
+++ b/tests/hazmat/primitives/test_blowfish.py
@@ -16,19 +16,22 @@
 import binascii
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives.ciphers import algorithms, modes
 
 from .utils import generate_encrypt_test
 from ...utils import load_nist_vectors
 
 
+@pytest.mark.cipher
 class TestBlowfish(object):
     test_ECB = generate_encrypt_test(
         load_nist_vectors,
         os.path.join("ciphers", "Blowfish"),
         ["bf-ecb.txt"],
-        lambda key: algorithms.Blowfish(binascii.unhexlify(key)),
-        lambda key: modes.ECB(),
+        lambda key, **kwargs: algorithms.Blowfish(binascii.unhexlify(key)),
+        lambda **kwargs: modes.ECB(),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Blowfish("\x00" * 56), modes.ECB()
         ),
@@ -39,8 +42,8 @@
         load_nist_vectors,
         os.path.join("ciphers", "Blowfish"),
         ["bf-cbc.txt"],
-        lambda key, iv: algorithms.Blowfish(binascii.unhexlify(key)),
-        lambda key, iv: modes.CBC(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.Blowfish(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CBC(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Blowfish("\x00" * 56), modes.CBC("\x00" * 8)
         ),
@@ -51,8 +54,8 @@
         load_nist_vectors,
         os.path.join("ciphers", "Blowfish"),
         ["bf-ofb.txt"],
-        lambda key, iv: algorithms.Blowfish(binascii.unhexlify(key)),
-        lambda key, iv: modes.OFB(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.Blowfish(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.OFB(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Blowfish("\x00" * 56), modes.OFB("\x00" * 8)
         ),
@@ -63,8 +66,8 @@
         load_nist_vectors,
         os.path.join("ciphers", "Blowfish"),
         ["bf-cfb.txt"],
-        lambda key, iv: algorithms.Blowfish(binascii.unhexlify(key)),
-        lambda key, iv: modes.CFB(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.Blowfish(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CFB(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Blowfish("\x00" * 56), modes.CFB("\x00" * 8)
         ),
diff --git a/tests/hazmat/primitives/test_camellia.py b/tests/hazmat/primitives/test_camellia.py
index a2c935d..c376220 100644
--- a/tests/hazmat/primitives/test_camellia.py
+++ b/tests/hazmat/primitives/test_camellia.py
@@ -16,6 +16,8 @@
 import binascii
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives.ciphers import algorithms, modes
 
 from .utils import generate_encrypt_test
@@ -24,6 +26,7 @@
 )
 
 
+@pytest.mark.cipher
 class TestCamellia(object):
     test_ECB = generate_encrypt_test(
         load_cryptrec_vectors,
@@ -33,8 +36,8 @@
             "camellia-192-ecb.txt",
             "camellia-256-ecb.txt"
         ],
-        lambda key: algorithms.Camellia(binascii.unhexlify((key))),
-        lambda key: modes.ECB(),
+        lambda key, **kwargs: algorithms.Camellia(binascii.unhexlify(key)),
+        lambda **kwargs: modes.ECB(),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Camellia("\x00" * 16), modes.ECB()
         ),
@@ -45,8 +48,8 @@
         load_openssl_vectors,
         os.path.join("ciphers", "Camellia"),
         ["camellia-cbc.txt"],
-        lambda key, iv: algorithms.Camellia(binascii.unhexlify(key)),
-        lambda key, iv: modes.CBC(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.Camellia(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CBC(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Camellia("\x00" * 16), modes.CBC("\x00" * 16)
         ),
@@ -57,8 +60,8 @@
         load_openssl_vectors,
         os.path.join("ciphers", "Camellia"),
         ["camellia-ofb.txt"],
-        lambda key, iv: algorithms.Camellia(binascii.unhexlify(key)),
-        lambda key, iv: modes.OFB(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.Camellia(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.OFB(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Camellia("\x00" * 16), modes.OFB("\x00" * 16)
         ),
@@ -69,8 +72,8 @@
         load_openssl_vectors,
         os.path.join("ciphers", "Camellia"),
         ["camellia-cfb.txt"],
-        lambda key, iv: algorithms.Camellia(binascii.unhexlify(key)),
-        lambda key, iv: modes.CFB(binascii.unhexlify(iv)),
+        lambda key, **kwargs: algorithms.Camellia(binascii.unhexlify(key)),
+        lambda iv, **kwargs: modes.CFB(binascii.unhexlify(iv)),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.Camellia("\x00" * 16), modes.CFB("\x00" * 16)
         ),
diff --git a/tests/hazmat/primitives/test_cast5.py b/tests/hazmat/primitives/test_cast5.py
index a283daf..a4789c6 100644
--- a/tests/hazmat/primitives/test_cast5.py
+++ b/tests/hazmat/primitives/test_cast5.py
@@ -16,19 +16,22 @@
 import binascii
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives.ciphers import algorithms, modes
 
 from .utils import generate_encrypt_test
 from ...utils import load_nist_vectors
 
 
+@pytest.mark.cipher
 class TestCAST5(object):
     test_ECB = generate_encrypt_test(
         load_nist_vectors,
         os.path.join("ciphers", "CAST5"),
         ["cast5-ecb.txt"],
-        lambda key: algorithms.CAST5(binascii.unhexlify((key))),
-        lambda key: modes.ECB(),
+        lambda key, **kwargs: algorithms.CAST5(binascii.unhexlify((key))),
+        lambda **kwargs: modes.ECB(),
         only_if=lambda backend: backend.cipher_supported(
             algorithms.CAST5("\x00" * 16), modes.ECB()
         ),
diff --git a/tests/hazmat/primitives/test_hash_vectors.py b/tests/hazmat/primitives/test_hash_vectors.py
index a865581..d9febea 100644
--- a/tests/hazmat/primitives/test_hash_vectors.py
+++ b/tests/hazmat/primitives/test_hash_vectors.py
@@ -15,12 +15,15 @@
 
 import os
 
+import pytest
+
 from cryptography.hazmat.primitives import hashes
 
 from .utils import generate_hash_test, generate_long_string_hash_test
 from ...utils import load_hash_vectors
 
 
+@pytest.mark.hash
 class TestSHA1(object):
     test_SHA1 = generate_hash_test(
         load_hash_vectors,
@@ -35,6 +38,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA224(object):
     test_SHA224 = generate_hash_test(
         load_hash_vectors,
@@ -49,6 +53,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA256(object):
     test_SHA256 = generate_hash_test(
         load_hash_vectors,
@@ -63,6 +68,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA384(object):
     test_SHA384 = generate_hash_test(
         load_hash_vectors,
@@ -77,6 +83,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA512(object):
     test_SHA512 = generate_hash_test(
         load_hash_vectors,
@@ -91,6 +98,7 @@
     )
 
 
+@pytest.mark.hash
 class TestRIPEMD160(object):
     test_RIPEMD160 = generate_hash_test(
         load_hash_vectors,
@@ -111,6 +119,7 @@
     )
 
 
+@pytest.mark.hash
 class TestWhirlpool(object):
     test_whirlpool = generate_hash_test(
         load_hash_vectors,
@@ -133,6 +142,7 @@
     )
 
 
+@pytest.mark.hash
 class TestMD5(object):
     test_md5 = generate_hash_test(
         load_hash_vectors,
diff --git a/tests/hazmat/primitives/test_hashes.py b/tests/hazmat/primitives/test_hashes.py
index cd58b06..69d0773 100644
--- a/tests/hazmat/primitives/test_hashes.py
+++ b/tests/hazmat/primitives/test_hashes.py
@@ -19,12 +19,21 @@
 
 import six
 
-from cryptography.exceptions import AlreadyFinalized, InvalidSignature
-from cryptography.hazmat.primitives import hashes
+from cryptography import utils
+from cryptography.exceptions import (
+    AlreadyFinalized, UnsupportedAlgorithm, InvalidSignature
+)
+from cryptography.hazmat.primitives import hashes, interfaces
 
 from .utils import generate_base_hash_test
 
 
+@utils.register_interface(interfaces.HashAlgorithm)
+class UnsupportedDummyHash(object):
+    name = "unsupported-dummy-hash"
+
+
+@pytest.mark.hash
 class TestHashContext(object):
     def test_hash_reject_unicode(self, backend):
         m = hashes.Hash(hashes.SHA1(), backend=backend)
@@ -80,7 +89,12 @@
         with pytest.raises(TypeError):
             h.verify(six.u(''))
 
+    def test_unsupported_hash(self, backend):
+        with pytest.raises(UnsupportedAlgorithm):
+            hashes.Hash(UnsupportedDummyHash(), backend)
 
+
+@pytest.mark.hash
 class TestSHA1(object):
     test_SHA1 = generate_base_hash_test(
         hashes.SHA1(),
@@ -91,6 +105,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA224(object):
     test_SHA224 = generate_base_hash_test(
         hashes.SHA224(),
@@ -101,6 +116,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA256(object):
     test_SHA256 = generate_base_hash_test(
         hashes.SHA256(),
@@ -111,6 +127,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA384(object):
     test_SHA384 = generate_base_hash_test(
         hashes.SHA384(),
@@ -121,6 +138,7 @@
     )
 
 
+@pytest.mark.hash
 class TestSHA512(object):
     test_SHA512 = generate_base_hash_test(
         hashes.SHA512(),
@@ -131,6 +149,7 @@
     )
 
 
+@pytest.mark.hash
 class TestRIPEMD160(object):
     test_RIPEMD160 = generate_base_hash_test(
         hashes.RIPEMD160(),
@@ -141,6 +160,7 @@
     )
 
 
+@pytest.mark.hash
 class TestWhirlpool(object):
     test_Whirlpool = generate_base_hash_test(
         hashes.Whirlpool(),
@@ -151,6 +171,7 @@
     )
 
 
+@pytest.mark.hash
 class TestMD5(object):
     test_MD5 = generate_base_hash_test(
         hashes.MD5(),
diff --git a/tests/hazmat/primitives/test_hmac.py b/tests/hazmat/primitives/test_hmac.py
index 4836018..7acb78b 100644
--- a/tests/hazmat/primitives/test_hmac.py
+++ b/tests/hazmat/primitives/test_hmac.py
@@ -19,16 +19,25 @@
 
 import six
 
-from cryptography.exceptions import AlreadyFinalized, InvalidSignature
-from cryptography.hazmat.primitives import hashes, hmac
+from cryptography import utils
+from cryptography.exceptions import (
+    AlreadyFinalized, UnsupportedAlgorithm, InvalidSignature
+)
+from cryptography.hazmat.primitives import hashes, hmac, interfaces
 
 from .utils import generate_base_hmac_test
 
 
+@utils.register_interface(interfaces.HashAlgorithm)
+class UnsupportedDummyHash(object):
+        name = "unsupported-dummy-hash"
+
+
+@pytest.mark.hmac
 class TestHMAC(object):
     test_copy = generate_base_hmac_test(
         hashes.MD5(),
-        only_if=lambda backend: backend.hash_supported(hashes.MD5),
+        only_if=lambda backend: backend.hmac_supported(hashes.MD5),
         skip_message="Does not support MD5",
     )
 
@@ -86,3 +95,7 @@
         h = hmac.HMAC(b'', hashes.SHA1(), backend=backend)
         with pytest.raises(TypeError):
             h.verify(six.u(''))
+
+    def test_unsupported_hash(self, backend):
+        with pytest.raises(UnsupportedAlgorithm):
+            hmac.HMAC(b"key", UnsupportedDummyHash(), backend)
diff --git a/tests/hazmat/primitives/test_hmac_vectors.py b/tests/hazmat/primitives/test_hmac_vectors.py
index 7d0f156..9bc06a2 100644
--- a/tests/hazmat/primitives/test_hmac_vectors.py
+++ b/tests/hazmat/primitives/test_hmac_vectors.py
@@ -13,12 +13,15 @@
 
 from __future__ import absolute_import, division, print_function
 
+import pytest
+
 from cryptography.hazmat.primitives import hashes
 
 from .utils import generate_hmac_test
 from ...utils import load_hash_vectors
 
 
+@pytest.mark.hmac
 class TestHMAC_MD5(object):
     test_hmac_md5 = generate_hmac_test(
         load_hash_vectors,
@@ -27,11 +30,12 @@
             "rfc-2202-md5.txt",
         ],
         hashes.MD5(),
-        only_if=lambda backend: backend.hash_supported(hashes.MD5),
+        only_if=lambda backend: backend.hmac_supported(hashes.MD5),
         skip_message="Does not support MD5",
     )
 
 
+@pytest.mark.hmac
 class TestHMAC_SHA1(object):
     test_hmac_sha1 = generate_hmac_test(
         load_hash_vectors,
@@ -40,11 +44,12 @@
             "rfc-2202-sha1.txt",
         ],
         hashes.SHA1(),
-        only_if=lambda backend: backend.hash_supported(hashes.SHA1),
+        only_if=lambda backend: backend.hmac_supported(hashes.SHA1),
         skip_message="Does not support SHA1",
     )
 
 
+@pytest.mark.hmac
 class TestHMAC_SHA224(object):
     test_hmac_sha224 = generate_hmac_test(
         load_hash_vectors,
@@ -53,11 +58,12 @@
             "rfc-4231-sha224.txt",
         ],
         hashes.SHA224(),
-        only_if=lambda backend: backend.hash_supported(hashes.SHA224),
+        only_if=lambda backend: backend.hmac_supported(hashes.SHA224),
         skip_message="Does not support SHA224",
     )
 
 
+@pytest.mark.hmac
 class TestHMAC_SHA256(object):
     test_hmac_sha256 = generate_hmac_test(
         load_hash_vectors,
@@ -66,11 +72,12 @@
             "rfc-4231-sha256.txt",
         ],
         hashes.SHA256(),
-        only_if=lambda backend: backend.hash_supported(hashes.SHA256),
+        only_if=lambda backend: backend.hmac_supported(hashes.SHA256),
         skip_message="Does not support SHA256",
     )
 
 
+@pytest.mark.hmac
 class TestHMAC_SHA384(object):
     test_hmac_sha384 = generate_hmac_test(
         load_hash_vectors,
@@ -79,11 +86,12 @@
             "rfc-4231-sha384.txt",
         ],
         hashes.SHA384(),
-        only_if=lambda backend: backend.hash_supported(hashes.SHA384),
+        only_if=lambda backend: backend.hmac_supported(hashes.SHA384),
         skip_message="Does not support SHA384",
     )
 
 
+@pytest.mark.hmac
 class TestHMAC_SHA512(object):
     test_hmac_sha512 = generate_hmac_test(
         load_hash_vectors,
@@ -92,11 +100,12 @@
             "rfc-4231-sha512.txt",
         ],
         hashes.SHA512(),
-        only_if=lambda backend: backend.hash_supported(hashes.SHA512),
+        only_if=lambda backend: backend.hmac_supported(hashes.SHA512),
         skip_message="Does not support SHA512",
     )
 
 
+@pytest.mark.hmac
 class TestHMAC_RIPEMD160(object):
     test_hmac_ripemd160 = generate_hmac_test(
         load_hash_vectors,
@@ -105,6 +114,6 @@
             "rfc-2286-ripemd160.txt",
         ],
         hashes.RIPEMD160(),
-        only_if=lambda backend: backend.hash_supported(hashes.RIPEMD160),
+        only_if=lambda backend: backend.hmac_supported(hashes.RIPEMD160),
         skip_message="Does not support RIPEMD160",
     )
diff --git a/tests/hazmat/primitives/utils.py b/tests/hazmat/primitives/utils.py
index b06f9b2..e018477 100644
--- a/tests/hazmat/primitives/utils.py
+++ b/tests/hazmat/primitives/utils.py
@@ -3,7 +3,6 @@
 
 import pytest
 
-from cryptography.hazmat.backends import _ALL_BACKENDS
 from cryptography.hazmat.primitives import hashes, hmac
 from cryptography.hazmat.primitives.ciphers import Cipher
 from cryptography.exceptions import (
@@ -13,25 +12,30 @@
 from ...utils import load_vectors_from_file
 
 
+def _load_all_params(path, file_names, param_loader):
+    all_params = []
+    for file_name in file_names:
+        all_params.extend(
+            load_vectors_from_file(os.path.join(path, file_name), param_loader)
+        )
+    return all_params
+
+
 def generate_encrypt_test(param_loader, path, file_names, cipher_factory,
-                          mode_factory, only_if=lambda backend: True,
-                          skip_message=None):
-    def test_encryption(self):
-        for backend in _ALL_BACKENDS:
-            for file_name in file_names:
-                for params in load_vectors_from_file(
-                    os.path.join(path, file_name),
-                    param_loader
-                ):
-                    yield (
-                        encrypt_test,
-                        backend,
-                        cipher_factory,
-                        mode_factory,
-                        params,
-                        only_if,
-                        skip_message
-                    )
+                          mode_factory, only_if, skip_message=None):
+    all_params = _load_all_params(path, file_names, param_loader)
+
+    @pytest.mark.parametrize("params", all_params)
+    def test_encryption(self, backend, params):
+        encrypt_test(
+            backend,
+            cipher_factory,
+            mode_factory,
+            params,
+            only_if,
+            skip_message
+        )
+
     return test_encryption
 
 
@@ -39,8 +43,8 @@
                  skip_message):
     if not only_if(backend):
         pytest.skip(skip_message)
-    plaintext = params.pop("plaintext")
-    ciphertext = params.pop("ciphertext")
+    plaintext = params["plaintext"]
+    ciphertext = params["ciphertext"]
     cipher = Cipher(
         cipher_factory(**params),
         mode_factory(**params),
@@ -58,22 +62,19 @@
 
 def generate_aead_test(param_loader, path, file_names, cipher_factory,
                        mode_factory, only_if, skip_message):
-    def test_aead(self):
-        for backend in _ALL_BACKENDS:
-            for file_name in file_names:
-                for params in load_vectors_from_file(
-                    os.path.join(path, file_name),
-                    param_loader
-                ):
-                    yield (
-                        aead_test,
-                        backend,
-                        cipher_factory,
-                        mode_factory,
-                        params,
-                        only_if,
-                        skip_message
-                    )
+    all_params = _load_all_params(path, file_names, param_loader)
+
+    @pytest.mark.parametrize("params", all_params)
+    def test_aead(self, backend, params):
+        aead_test(
+            backend,
+            cipher_factory,
+            mode_factory,
+            params,
+            only_if,
+            skip_message
+        )
+
     return test_aead
 
 
@@ -82,9 +83,9 @@
     if not only_if(backend):
         pytest.skip(skip_message)
     if params.get("pt") is not None:
-        plaintext = params.pop("pt")
-    ciphertext = params.pop("ct")
-    aad = params.pop("aad")
+        plaintext = params["pt"]
+    ciphertext = params["ct"]
+    aad = params["aad"]
     if params.get("fail") is True:
         cipher = Cipher(
             cipher_factory(binascii.unhexlify(params["key"])),
@@ -125,21 +126,17 @@
 def generate_stream_encryption_test(param_loader, path, file_names,
                                     cipher_factory, only_if=None,
                                     skip_message=None):
-    def test_stream_encryption(self):
-        for backend in _ALL_BACKENDS:
-            for file_name in file_names:
-                for params in load_vectors_from_file(
-                    os.path.join(path, file_name),
-                    param_loader
-                ):
-                    yield (
-                        stream_encryption_test,
-                        backend,
-                        cipher_factory,
-                        params,
-                        only_if,
-                        skip_message
-                    )
+    all_params = _load_all_params(path, file_names, param_loader)
+
+    @pytest.mark.parametrize("params", all_params)
+    def test_stream_encryption(self, backend, params):
+        stream_encryption_test(
+            backend,
+            cipher_factory,
+            params,
+            only_if,
+            skip_message
+        )
     return test_stream_encryption
 
 
@@ -147,9 +144,9 @@
                            skip_message):
     if not only_if(backend):
         pytest.skip(skip_message)
-    plaintext = params.pop("plaintext")
-    ciphertext = params.pop("ciphertext")
-    offset = params.pop("offset")
+    plaintext = params["plaintext"]
+    ciphertext = params["ciphertext"]
+    offset = params["offset"]
     cipher = Cipher(cipher_factory(**params), None, backend=backend)
     encryptor = cipher.encryptor()
     # throw away offset bytes
@@ -166,21 +163,17 @@
 
 def generate_hash_test(param_loader, path, file_names, hash_cls,
                        only_if=None, skip_message=None):
-    def test_hash(self):
-        for backend in _ALL_BACKENDS:
-            for file_name in file_names:
-                for params in load_vectors_from_file(
-                    os.path.join(path, file_name),
-                    param_loader
-                ):
-                    yield (
-                        hash_test,
-                        backend,
-                        hash_cls,
-                        params,
-                        only_if,
-                        skip_message
-                    )
+    all_params = _load_all_params(path, file_names, param_loader)
+
+    @pytest.mark.parametrize("params", all_params)
+    def test_hash(self, backend, params):
+        hash_test(
+            backend,
+            hash_cls,
+            params,
+            only_if,
+            skip_message
+        )
     return test_hash
 
 
@@ -197,17 +190,15 @@
 
 def generate_base_hash_test(algorithm, digest_size, block_size,
                             only_if=None, skip_message=None):
-    def test_base_hash(self):
-        for backend in _ALL_BACKENDS:
-            yield (
-                base_hash_test,
-                backend,
-                algorithm,
-                digest_size,
-                block_size,
-                only_if,
-                skip_message,
-            )
+    def test_base_hash(self, backend):
+        base_hash_test(
+            backend,
+            algorithm,
+            digest_size,
+            block_size,
+            only_if,
+            skip_message,
+        )
     return test_base_hash
 
 
@@ -232,16 +223,14 @@
 
 def generate_long_string_hash_test(hash_factory, md, only_if=None,
                                    skip_message=None):
-    def test_long_string_hash(self):
-        for backend in _ALL_BACKENDS:
-            yield(
-                long_string_hash_test,
-                backend,
-                hash_factory,
-                md,
-                only_if,
-                skip_message
-            )
+    def test_long_string_hash(self, backend):
+        long_string_hash_test(
+            backend,
+            hash_factory,
+            md,
+            only_if,
+            skip_message
+        )
     return test_long_string_hash
 
 
@@ -255,21 +244,17 @@
 
 def generate_hmac_test(param_loader, path, file_names, algorithm,
                        only_if=None, skip_message=None):
-    def test_hmac(self):
-        for backend in _ALL_BACKENDS:
-            for file_name in file_names:
-                for params in load_vectors_from_file(
-                    os.path.join(path, file_name),
-                    param_loader
-                ):
-                    yield (
-                        hmac_test,
-                        backend,
-                        algorithm,
-                        params,
-                        only_if,
-                        skip_message
-                    )
+    all_params = _load_all_params(path, file_names, param_loader)
+
+    @pytest.mark.parametrize("params", all_params)
+    def test_hmac(self, backend, params):
+        hmac_test(
+            backend,
+            algorithm,
+            params,
+            only_if,
+            skip_message
+        )
     return test_hmac
 
 
@@ -285,15 +270,13 @@
 
 
 def generate_base_hmac_test(hash_cls, only_if=None, skip_message=None):
-    def test_base_hmac(self):
-        for backend in _ALL_BACKENDS:
-            yield (
-                base_hmac_test,
-                backend,
-                hash_cls,
-                only_if,
-                skip_message,
-            )
+    def test_base_hmac(self, backend):
+        base_hmac_test(
+            backend,
+            hash_cls,
+            only_if,
+            skip_message,
+        )
     return test_base_hmac
 
 
@@ -309,16 +292,14 @@
 
 def generate_aead_exception_test(cipher_factory, mode_factory,
                                  only_if, skip_message):
-    def test_aead_exception(self):
-        for backend in _ALL_BACKENDS:
-            yield (
-                aead_exception_test,
-                backend,
-                cipher_factory,
-                mode_factory,
-                only_if,
-                skip_message
-            )
+    def test_aead_exception(self, backend):
+        aead_exception_test(
+            backend,
+            cipher_factory,
+            mode_factory,
+            only_if,
+            skip_message
+        )
     return test_aead_exception
 
 
@@ -357,16 +338,14 @@
 
 def generate_aead_tag_exception_test(cipher_factory, mode_factory,
                                      only_if, skip_message):
-    def test_aead_tag_exception(self):
-        for backend in _ALL_BACKENDS:
-            yield (
-                aead_tag_exception_test,
-                backend,
-                cipher_factory,
-                mode_factory,
-                only_if,
-                skip_message
-            )
+    def test_aead_tag_exception(self, backend):
+        aead_tag_exception_test(
+            backend,
+            cipher_factory,
+            mode_factory,
+            only_if,
+            skip_message
+        )
     return test_aead_tag_exception
 
 
@@ -383,6 +362,13 @@
         cipher.decryptor()
     cipher = Cipher(
         cipher_factory(binascii.unhexlify(b"0" * 32)),
+        mode_factory(binascii.unhexlify(b"0" * 24), b"000"),
+        backend
+    )
+    with pytest.raises(ValueError):
+        cipher.decryptor()
+    cipher = Cipher(
+        cipher_factory(binascii.unhexlify(b"0" * 32)),
         mode_factory(binascii.unhexlify(b"0" * 24), b"0" * 16),
         backend
     )
diff --git a/tests/test_utils.py b/tests/test_utils.py
index 5c58fd7..a65091f 100644
--- a/tests/test_utils.py
+++ b/tests/test_utils.py
@@ -14,14 +14,33 @@
 import os
 import textwrap
 
+import pretend
+
 import pytest
 
 from .utils import (
     load_nist_vectors, load_vectors_from_file, load_cryptrec_vectors,
-    load_openssl_vectors, load_hash_vectors,
+    load_openssl_vectors, load_hash_vectors, check_for_iface
 )
 
 
+class FakeInterface(object):
+    pass
+
+
+def test_check_for_iface():
+    item = pretend.stub(keywords=["fake_name"], funcargs={"backend": True})
+    with pytest.raises(pytest.skip.Exception) as exc_info:
+        check_for_iface("fake_name", FakeInterface, item)
+    assert exc_info.value.args[0] == "True backend does not support fake_name"
+
+    item = pretend.stub(
+        keywords=["fake_name"],
+        funcargs={"backend": FakeInterface()}
+    )
+    check_for_iface("fake_name", FakeInterface, item)
+
+
 def test_load_nist_vectors():
     vector_data = textwrap.dedent("""
     # CAVS 11.1
diff --git a/tests/utils.py b/tests/utils.py
index 94f97d5..82021a5 100644
--- a/tests/utils.py
+++ b/tests/utils.py
@@ -11,7 +11,17 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-import os.path
+import os
+
+import pytest
+
+
+def check_for_iface(name, iface, item):
+    if name in item.keywords and "backend" in item.funcargs:
+        if not isinstance(item.funcargs["backend"], iface):
+            pytest.skip("{0} backend does not support {1}".format(
+                item.funcargs["backend"], name
+            ))
 
 
 def load_vectors_from_file(filename, loader):
diff --git a/tox.ini b/tox.ini
index 39fe024..6114311 100644
--- a/tox.ini
+++ b/tox.ini
@@ -7,7 +7,7 @@
     coverage
     pretend
 commands =
-    coverage run --source=cryptography/,tests/ -m pytest --strict
+    coverage run --source=cryptography/,tests/ -m pytest --capture=no --strict
     coverage report -m
 
 [testenv:docs]
@@ -24,7 +24,7 @@
 # Temporarily disable coverage on pypy because of performance problems with
 # coverage.py on pypy.
 [testenv:pypy]
-commands = py.test
+commands = py.test --capture=no
 
 [testenv:pep8]
 deps = flake8