diff --git a/cryptography/hazmat/backends/commoncrypto/hmac.py b/cryptography/hazmat/backends/commoncrypto/hmac.py
index c2b6c37..ee7e3ab 100644
--- a/cryptography/hazmat/backends/commoncrypto/hmac.py
+++ b/cryptography/hazmat/backends/commoncrypto/hmac.py
@@ -14,8 +14,10 @@
 from __future__ import absolute_import, division, print_function
 
 from cryptography import utils
-from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
-from cryptography.hazmat.primitives import interfaces
+from cryptography.exceptions import (
+    InvalidSignature, UnsupportedAlgorithm, _Reasons
+)
+from cryptography.hazmat.primitives import constant_time, interfaces
 
 
 @utils.register_interface(interfaces.MACContext)
@@ -59,3 +61,8 @@
                                      self.algorithm.digest_size)
         self._backend._lib.CCHmacFinal(self._ctx, buf)
         return self._backend._ffi.buffer(buf)[:]
+
+    def verify(self, signature):
+        digest = self.finalize()
+        if not constant_time.bytes_eq(digest, signature):
+            raise InvalidSignature("Signature did not match digest.")
diff --git a/cryptography/hazmat/backends/openssl/cmac.py b/cryptography/hazmat/backends/openssl/cmac.py
index 6a844cd..1ad6055 100644
--- a/cryptography/hazmat/backends/openssl/cmac.py
+++ b/cryptography/hazmat/backends/openssl/cmac.py
@@ -15,8 +15,10 @@
 
 
 from cryptography import utils
-from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
-from cryptography.hazmat.primitives import interfaces
+from cryptography.exceptions import (
+    InvalidSignature, UnsupportedAlgorithm, _Reasons
+)
+from cryptography.hazmat.primitives import constant_time, interfaces
 from cryptography.hazmat.primitives.ciphers.modes import CBC
 
 
@@ -80,3 +82,8 @@
         return _CMACContext(
             self._backend, self._algorithm, ctx=copied_ctx
         )
+
+    def verify(self, signature):
+        digest = self.finalize()
+        if not constant_time.bytes_eq(digest, signature):
+            raise InvalidSignature("Signature did not match digest.")
diff --git a/cryptography/hazmat/backends/openssl/hmac.py b/cryptography/hazmat/backends/openssl/hmac.py
index d5300ea..c324bd8 100644
--- a/cryptography/hazmat/backends/openssl/hmac.py
+++ b/cryptography/hazmat/backends/openssl/hmac.py
@@ -15,8 +15,10 @@
 
 
 from cryptography import utils
-from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
-from cryptography.hazmat.primitives import interfaces
+from cryptography.exceptions import (
+    InvalidSignature, UnsupportedAlgorithm, _Reasons
+)
+from cryptography.hazmat.primitives import constant_time, interfaces
 
 
 @utils.register_interface(interfaces.MACContext)
@@ -81,3 +83,8 @@
         assert outlen[0] == self.algorithm.digest_size
         self._backend._lib.HMAC_CTX_cleanup(self._ctx)
         return self._backend._ffi.buffer(buf)[:outlen[0]]
+
+    def verify(self, signature):
+        digest = self.finalize()
+        if not constant_time.bytes_eq(digest, signature):
+            raise InvalidSignature("Signature did not match digest.")
diff --git a/cryptography/hazmat/primitives/cmac.py b/cryptography/hazmat/primitives/cmac.py
index 7ae5c11..6f72203 100644
--- a/cryptography/hazmat/primitives/cmac.py
+++ b/cryptography/hazmat/primitives/cmac.py
@@ -15,10 +15,10 @@
 
 from cryptography import utils
 from cryptography.exceptions import (
-    AlreadyFinalized, InvalidSignature, UnsupportedAlgorithm, _Reasons
+    AlreadyFinalized, UnsupportedAlgorithm, _Reasons
 )
 from cryptography.hazmat.backends.interfaces import CMACBackend
-from cryptography.hazmat.primitives import constant_time, interfaces
+from cryptography.hazmat.primitives import interfaces
 
 
 @utils.register_interface(interfaces.MACContext)
@@ -59,9 +59,11 @@
     def verify(self, signature):
         if not isinstance(signature, bytes):
             raise TypeError("signature must be bytes.")
-        digest = self.finalize()
-        if not constant_time.bytes_eq(digest, signature):
-            raise InvalidSignature("Signature did not match digest.")
+        if self._ctx is None:
+            raise AlreadyFinalized("Context was already finalized.")
+
+        ctx, self._ctx = self._ctx, None
+        ctx.verify(signature)
 
     def copy(self):
         if self._ctx is None:
diff --git a/cryptography/hazmat/primitives/hmac.py b/cryptography/hazmat/primitives/hmac.py
index 22a3139..47a048f 100644
--- a/cryptography/hazmat/primitives/hmac.py
+++ b/cryptography/hazmat/primitives/hmac.py
@@ -15,10 +15,10 @@
 
 from cryptography import utils
 from cryptography.exceptions import (
-    AlreadyFinalized, InvalidSignature, UnsupportedAlgorithm, _Reasons
+    AlreadyFinalized, UnsupportedAlgorithm, _Reasons
 )
 from cryptography.hazmat.backends.interfaces import HMACBackend
-from cryptography.hazmat.primitives import constant_time, interfaces
+from cryptography.hazmat.primitives import interfaces
 
 
 @utils.register_interface(interfaces.MACContext)
@@ -71,6 +71,8 @@
     def verify(self, signature):
         if not isinstance(signature, bytes):
             raise TypeError("signature must be bytes.")
-        digest = self.finalize()
-        if not constant_time.bytes_eq(digest, signature):
-            raise InvalidSignature("Signature did not match digest.")
+        if self._ctx is None:
+            raise AlreadyFinalized("Context was already finalized.")
+
+        ctx, self._ctx = self._ctx, None
+        ctx.verify(signature)
diff --git a/cryptography/utils.py b/cryptography/utils.py
index 1deb3d1..03c8c0e 100644
--- a/cryptography/utils.py
+++ b/cryptography/utils.py
@@ -13,6 +13,8 @@
 
 from __future__ import absolute_import, division, print_function
 
+import abc
+import inspect
 import sys
 
 
@@ -21,6 +23,7 @@
 
 def register_interface(iface):
     def register_decorator(klass):
+        verify_interface(iface, klass)
         iface.register(klass)
         return klass
     return register_decorator
@@ -30,6 +33,30 @@
     return property(lambda self: getattr(self, name))
 
 
+class InterfaceNotImplemented(Exception):
+    pass
+
+
+def verify_interface(iface, klass):
+    for method in iface.__abstractmethods__:
+        if not hasattr(klass, method):
+            raise InterfaceNotImplemented(
+                "{0} is missing a {1!r} method".format(klass, method)
+            )
+        if isinstance(getattr(iface, method), abc.abstractproperty):
+            # Can't properly verify these yet.
+            continue
+        spec = inspect.getargspec(getattr(iface, method))
+        actual = inspect.getargspec(getattr(klass, method))
+        if spec != actual:
+            raise InterfaceNotImplemented(
+                "{0}.{1}'s signature differs from the expected. Expected: "
+                "{2!r}. Received: {3!r}".format(
+                    klass, method, spec, actual
+                )
+            )
+
+
 def bit_length(x):
     if sys.version_info >= (2, 7):
         return x.bit_length()
diff --git a/tests/hazmat/primitives/test_cmac.py b/tests/hazmat/primitives/test_cmac.py
index c778ebe..a2a701a 100644
--- a/tests/hazmat/primitives/test_cmac.py
+++ b/tests/hazmat/primitives/test_cmac.py
@@ -166,6 +166,9 @@
         with pytest.raises(AlreadyFinalized):
             cmac.finalize()
 
+        with pytest.raises(AlreadyFinalized):
+            cmac.verify(b"")
+
     @pytest.mark.supported(
         only_if=lambda backend: backend.cmac_algorithm_supported(
             AES(fake_key)),
diff --git a/tests/test_interfaces.py b/tests/test_interfaces.py
new file mode 100644
index 0000000..b988abe
--- /dev/null
+++ b/tests/test_interfaces.py
@@ -0,0 +1,63 @@
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#    http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+# implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+import abc
+
+import pytest
+
+import six
+
+from cryptography.utils import InterfaceNotImplemented, verify_interface
+
+
+class TestVerifyInterface(object):
+    def test_verify_missing_method(self):
+        @six.add_metaclass(abc.ABCMeta)
+        class SimpleInterface(object):
+            @abc.abstractmethod
+            def method(self):
+                """A simple method"""
+
+        class NonImplementer(object):
+            pass
+
+        with pytest.raises(InterfaceNotImplemented):
+            verify_interface(SimpleInterface, NonImplementer)
+
+    def test_different_arguments(self):
+        @six.add_metaclass(abc.ABCMeta)
+        class SimpleInterface(object):
+            @abc.abstractmethod
+            def method(self, a):
+                """Method with one argument"""
+
+        class NonImplementer(object):
+            def method(self):
+                """Method with no arguments"""
+
+        with pytest.raises(InterfaceNotImplemented):
+            verify_interface(SimpleInterface, NonImplementer)
+
+    def test_handles_abstract_property(self):
+        @six.add_metaclass(abc.ABCMeta)
+        class SimpleInterface(object):
+            @abc.abstractproperty
+            def property(self):
+                """An abstract property"""
+
+        class NonImplementer(object):
+            @property
+            def property(self):
+                """A concrete property"""
+
+        verify_interface(SimpleInterface, NonImplementer)