diff --git a/cryptography/hazmat/backends/openssl/backend.py b/cryptography/hazmat/backends/openssl/backend.py
index 7cfdd28..1173113 100644
--- a/cryptography/hazmat/backends/openssl/backend.py
+++ b/cryptography/hazmat/backends/openssl/backend.py
@@ -556,8 +556,11 @@
         return self._ffi.buffer(buf)[:res]
 
     def cmac_algorithm_supported(self, algorithm):
-        return (backend._lib.Cryptography_HAS_CMAC == 1
-                and backend.cipher_supported(algorithm, CBC(0)))
+        return (
+            backend._lib.Cryptography_HAS_CMAC == 1
+            and backend.cipher_supported(algorithm, CBC(
+                b"\x00" * algorithm.block_size))
+        )
 
     def create_cmac_ctx(self, algorithm):
         return _CMACContext(self, algorithm)
diff --git a/tests/hazmat/primitives/test_cmac.py b/tests/hazmat/primitives/test_cmac.py
index a1c24ad..dd7f9df 100644
--- a/tests/hazmat/primitives/test_cmac.py
+++ b/tests/hazmat/primitives/test_cmac.py
@@ -49,7 +49,7 @@
 vectors_3des = load_vectors_from_file(
     "CMAC/nist-800-38b-3des.txt", load_nist_vectors)
 
-fake_key = "AAAAAAAAAAAAAAAA"
+fake_key = b"\x00" * 16
 
 
 @pytest.mark.cmac