Begin designing the KDF interfaces. Fixes #511
diff --git a/cryptography/exceptions.py b/cryptography/exceptions.py
index 2654b45..e2542a1 100644
--- a/cryptography/exceptions.py
+++ b/cryptography/exceptions.py
@@ -38,3 +38,7 @@
 
 class InternalError(Exception):
     pass
+
+
+class InvalidKey(Exception):
+    pass
diff --git a/cryptography/hazmat/primitives/interfaces.py b/cryptography/hazmat/primitives/interfaces.py
index 293fcd7..1a27644 100644
--- a/cryptography/hazmat/primitives/interfaces.py
+++ b/cryptography/hazmat/primitives/interfaces.py
@@ -257,3 +257,19 @@
         """
         The public exponent of the RSA key. Alias for public_exponent.
         """
+
+
+class KeyDerivationFunction(six.with_metaclass(abc.ABCMeta)):
+    @abc.abstractmethod
+    def derive(self, key_material):
+        """
+        Deterministically generates and returns a new key based on the existing
+        key material.
+        """
+
+    @abc.abstractmethod
+    def verify(self, key_material, expected_key):
+        """
+        Checks whether the key generated by the key material matches the
+        expected derived key. Raises an exception if they do not match.
+        """
diff --git a/docs/exceptions.rst b/docs/exceptions.rst
index 1fbd326..f9e29f3 100644
--- a/docs/exceptions.rst
+++ b/docs/exceptions.rst
@@ -30,3 +30,9 @@
 
     This is raised when a backend doesn't support the requested algorithm (or
     combination of algorithms).
+
+
+.. class:: InvalidKey
+
+    This is raised when the verify method of a key derivation function does not
+    compare equal.
diff --git a/docs/hazmat/primitives/interfaces.rst b/docs/hazmat/primitives/interfaces.rst
index bf78e36..ac48dd2 100644
--- a/docs/hazmat/primitives/interfaces.rst
+++ b/docs/hazmat/primitives/interfaces.rst
@@ -204,4 +204,34 @@
         The public exponent. Alias for :attr:`public_exponent`.
 
 
+Key Derivation Functions
+~~~~~~~~~~~~~~~~~~~~~~~~
+
+.. class:: KeyDerivationFunction
+
+    .. method:: derive(key_material)
+
+        :param key_material bytes: The raw key material. Depending on what key
+                                   derivation function you are using this could
+                                   be either random material, or a user
+                                   supplied password.
+        :return: The resulting key.
+
+        The generates and returns a new key from the supplied key material.
+
+    .. method:: verify(key_material, expected_key)
+
+        :param key_material bytes: The raw key material. This is the same as
+                                   ``key_material`` in :meth:`derive`.
+        :param expected_key bytes: What the expected result of deriving a new
+                                   key is.
+        :raises cryptography.exceptions.InvalidKey: This is raised when the
+                                                    derived key does not match
+                                                    the expected key.
+
+        This checks whether deriving a key from the supplied ``key_material``
+        generates the same key as the ``expected_key``, and raises an exception
+        if they do not match. This can be used for something like checking
+        whether a user's password attempt matches the stored derived key.
+
 .. _`RSA`: http://en.wikipedia.org/wiki/RSA_(cryptosystem)