diff --git a/cryptography/bindings/openssl/api.py b/cryptography/bindings/openssl/api.py
index f1a2c08..ced2cf8 100644
--- a/cryptography/bindings/openssl/api.py
+++ b/cryptography/bindings/openssl/api.py
@@ -13,11 +13,23 @@
 
 from __future__ import absolute_import, division, print_function
 
+import itertools
 import sys
 
 import cffi
 
 from cryptography.primitives import interfaces
+from cryptography.primitives.block.ciphers import AES, Camellia
+from cryptography.primitives.block.modes import CBC, ECB, OFB, CFB
+
+
+class GetCipherByName(object):
+    def __init__(self, fmt):
+        self._fmt = fmt
+
+    def __call__(self, api, cipher, mode):
+        cipher_name = self._fmt.format(cipher=cipher, mode=mode).lower()
+        return api.lib.EVP_get_cipherbyname(cipher_name)
 
 
 class API(object):
@@ -78,6 +90,9 @@
         self.lib.OpenSSL_add_all_algorithms()
         self.lib.SSL_load_error_strings()
 
+        self._cipher_registry = {}
+        self._register_default_ciphers()
+
     def openssl_version_text(self):
         """
         Friendly string name of linked OpenSSL.
@@ -86,20 +101,41 @@
         """
         return self.ffi.string(self.lib.OPENSSL_VERSION_TEXT).decode("ascii")
 
-    def supports_cipher(self, ciphername):
-        return (self.ffi.NULL !=
-                self.lib.EVP_get_cipherbyname(ciphername.encode("ascii")))
+    def supports_cipher(self, cipher, mode):
+        try:
+            adapter = self._cipher_registry[type(cipher), type(mode)]
+        except KeyError:
+            return False
+        evp_cipher = adapter(self, cipher, mode)
+        return self.ffi.NULL != evp_cipher
+
+    def register_cipher_adapter(self, cipher_cls, mode_cls, adapter):
+        if (cipher_cls, mode_cls) in self._cipher_registry:
+            raise ValueError("Duplicate registration for: {0} {1}".format(
+                cipher_cls, mode_cls)
+            )
+        self._cipher_registry[cipher_cls, mode_cls] = adapter
+
+    def _register_default_ciphers(self):
+        for cipher_cls, mode_cls in itertools.product(
+            [AES, Camellia],
+            [CBC, ECB, OFB, CFB],
+        ):
+            self.register_cipher_adapter(
+                cipher_cls,
+                mode_cls,
+                GetCipherByName("{cipher.name}-{cipher.key_size}-{mode.name}")
+            )
 
     def create_block_cipher_context(self, cipher, mode):
         ctx = self.ffi.new("EVP_CIPHER_CTX *")
         res = self.lib.EVP_CIPHER_CTX_init(ctx)
         assert res != 0
         ctx = self.ffi.gc(ctx, self.lib.EVP_CIPHER_CTX_cleanup)
-        # TODO: compute name using a better algorithm
-        ciphername = "{0}-{1}-{2}".format(
-            cipher.name, cipher.key_size, mode.name
-        ).lower()
-        evp_cipher = self.lib.EVP_get_cipherbyname(ciphername.encode("ascii"))
+        evp_cipher = self._cipher_registry[type(cipher), type(mode)](
+            self, cipher, mode
+        )
+
         assert evp_cipher != self.ffi.NULL
         if isinstance(mode, interfaces.ModeWithInitializationVector):
             iv_nonce = mode.initialization_vector
diff --git a/cryptography/primitives/block/base.py b/cryptography/primitives/block/base.py
index b84ca9c..cb68361 100644
--- a/cryptography/primitives/block/base.py
+++ b/cryptography/primitives/block/base.py
@@ -15,8 +15,6 @@
 
 from enum import Enum
 
-from cryptography.bindings import _default_api
-
 
 class _Operation(Enum):
     encrypt = 0
@@ -28,7 +26,7 @@
         super(BlockCipher, self).__init__()
 
         if api is None:
-            api = _default_api
+            from cryptography.bindings import _default_api as api
 
         self.cipher = cipher
         self.mode = mode
diff --git a/tests/bindings/test_openssl.py b/tests/bindings/test_openssl.py
index e5b78d1..2d51330 100644
--- a/tests/bindings/test_openssl.py
+++ b/tests/bindings/test_openssl.py
@@ -30,4 +30,4 @@
         assert api.openssl_version_text().startswith("OpenSSL")
 
     def test_supports_cipher(self):
-        assert api.supports_cipher("not-a-real-cipher") is False
+        assert api.supports_cipher(None, None) is False
diff --git a/tests/primitives/test_cryptrec.py b/tests/primitives/test_cryptrec.py
index edf9765..56eca3a 100644
--- a/tests/primitives/test_cryptrec.py
+++ b/tests/primitives/test_cryptrec.py
@@ -37,6 +37,6 @@
         ],
         lambda key: ciphers.Camellia(binascii.unhexlify((key))),
         lambda key: modes.ECB(),
-        only_if=lambda api: api.supports_cipher("camellia-128-ecb"),
+        only_if=lambda api: api.supports_cipher(ciphers.Camellia("\x00" * 16), modes.ECB()),
         skip_message="Does not support Camellia ECB",
     )
diff --git a/tests/primitives/test_openssl_vectors.py b/tests/primitives/test_openssl_vectors.py
index 6e32eca..f53ade8 100644
--- a/tests/primitives/test_openssl_vectors.py
+++ b/tests/primitives/test_openssl_vectors.py
@@ -32,7 +32,7 @@
         ["camellia-cbc.txt"],
         lambda key, iv: ciphers.Camellia(binascii.unhexlify(key)),
         lambda key, iv: modes.CBC(binascii.unhexlify(iv)),
-        only_if=lambda api: api.supports_cipher("camellia-128-cbc"),
+        only_if=lambda api: api.supports_cipher(ciphers.Camellia("\x00" * 16), modes.CBC("\x00" * 16)),
         skip_message="Does not support Camellia CBC",
     )
 
@@ -44,7 +44,7 @@
         ["camellia-ofb.txt"],
         lambda key, iv: ciphers.Camellia(binascii.unhexlify(key)),
         lambda key, iv: modes.OFB(binascii.unhexlify(iv)),
-        only_if=lambda api: api.supports_cipher("camellia-128-ofb"),
+        only_if=lambda api: api.supports_cipher(ciphers.Camellia("\x00" * 16), modes.OFB("\x00" * 16)),
         skip_message="Does not support Camellia OFB",
     )
 
@@ -56,6 +56,6 @@
         ["camellia-cfb.txt"],
         lambda key, iv: ciphers.Camellia(binascii.unhexlify(key)),
         lambda key, iv: modes.CFB(binascii.unhexlify(iv)),
-        only_if=lambda api: api.supports_cipher("camellia-128-cfb"),
+        only_if=lambda api: api.supports_cipher(ciphers.Camellia("\x00" * 16), modes.CFB("\x00" * 16)),
         skip_message="Does not support Camellia CFB",
     )