Add new module Crypto.Protocol.KDF with two PKCS#5 key derivation algorithms.

5 files changed, 230 insertions, 9 deletions

diff --git a/lib/Crypto/Protocol/KDF.py b/lib/Crypto/Protocol/KDF.py
new file mode 100644
index 0000000..301ae4f
--- /dev/null
+++ b/lib/Crypto/Protocol/KDF.py
@@ -0,0 +1,117 @@
+#
+#  KDF.py : a collection of Key Derivation Functions
+#
+# Part of the Python Cryptography Toolkit
+#
+# ===================================================================
+# The contents of this file are dedicated to the public domain.  To
+# the extent that dedication to the public domain is not available,
+# everyone is granted a worldwide, perpetual, royalty-free,
+# non-exclusive license to exercise all rights associated with the
+# contents of this file for any purpose whatsoever.
+# No rights are reserved.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+# ===================================================================
+
+"""This file contains a collection of standard key derivation functions.
+
+A key derivation function derives one or more secondary secret keys from
+one primary secret (a master key or a pass phrase).
+
+This is typically done to insulate the secondary keys from each other,
+to avoid that leakage of a secondary key compromises the security of the
+master key, or to thwart attacks on pass phrases (e.g. via rainbow tables).
+
+:undocumented: __revision__
+"""
+
+__revision__ = "$Id$"
+
+import math
+import struct
+
+from Crypto.Hash import SHA as SHA1, HMAC
+from Crypto.Util.strxor import strxor
+
+def PBKDF1(password, salt, dkLen, count=1000, hashAlgo=SHA1):
+    """Derive one key from a password (or passphrase).
+
+    This function performs key derivation according an old version of
+    the PKCS#5 standard (v1.5).
+    
+    This algorithm is called ``PBKDF1``. Even though it is still described
+    in the latest version of the PKCS#5 standard (version 2, or RFC2898),
+    newer applications should use the more secure and versatile `PBKDF2` instead.
+
+    :Parameters:
+     password : string
+        The secret password or pass phrase to generate the key from.
+     salt : string
+        An 8 byte string to use for better protection from dictionary attacks.
+        This value does not need to be kept secret, but it should be randomly
+        chosen for each derivation.
+     dkLen : integer
+        The length of the desired key. Default is 16 bytes, suitable for instance for `Crypto.Cipher.AES`.
+     count : integer
+        The number of iterations to carry out. It's recommended to use at least 1000.
+     hashAlgo : module
+        The hash algorithm to use, as a module or an object from the `Crypto.Hash` package.
+        The digest length must be no shorter than ``dkLen``.
+
+    :Return: A byte string of length `dkLen` that can be used as key.
+"""
+    pHash = hashAlgo.new(password+salt)
+    digest = pHash.digest_size
+    if dkLen>digest:
+        raise ValueError("Selected hash algorithm has a too short digest (%d bytes)." % len(digest))
+    if len(salt)!=8:
+        raise ValueError("Salt is not 8 bytes long.")
+    for i in xrange(count-1):
+        pHash = pHash.new(pHash.digest())
+    return pHash.digest()[:dkLen]
+
+def PBKDF2(password, salt, dkLen=16, count=1000, prf=None):
+    """Derive one or more keys from a password (or passphrase).
+
+    This performs key derivation according to the PKCS#5 standard (v2.0),
+    by means of the ``PBKDF2`` algorithm.
+
+    :Parameters:
+     password : string
+        The secret password or pass phrase to generate the key from.
+     salt : string
+        A string to use for better protection from dictionary attacks.
+        This value does not need to be kept secret, but it should be randomly
+        chosen for each derivation. It is recommended to be at least 8 bytes long.
+     dkLen : integer
+        The cumulative length of the desired keys. Default is 16 bytes, suitable for instance for `Crypto.Cipher.AES`.
+     count : integer
+        The number of iterations to carry out. It's recommended to use at least 1000.
+     prf : callable
+        A pseudorandom function. It must be a function that returns a pseudorandom string
+        from two parameters: a secret and a salt. If not specified, HMAC-SHA1 is used.
+
+    :Return: A byte string of length `dkLen` that can be used as key material.
+        If you wanted multiple keys, just break up this string into segments of the desired length.
+"""
+    if prf is None:
+        prf = lambda p,s: HMAC.new(p,s,SHA1).digest()
+    key = ''
+    i = 1
+    while len(key)<dkLen:
+        U = previousU = prf(password,salt+struct.pack(">I", i))
+        for j in xrange(count-1):
+            previousU = t = prf(password,previousU)
+            U = strxor(U,t)
+        key += U
+        i = i + 1
+    return key[:dkLen]
+
diff --git a/lib/Crypto/Protocol/__init__.py b/lib/Crypto/Protocol/__init__.py
index 7af7848..cacc685 100644
--- a/lib/Crypto/Protocol/__init__.py
+++ b/lib/Crypto/Protocol/__init__.py
@@ -23,14 +23,19 @@
 Implements various cryptographic protocols.  (Don't expect to find
 network protocols here.)
 
-Crypto.Protocol.AllOrNothing   Transforms a message into a set of message
-                               blocks, such that the blocks can be
-                               recombined to get the message back.
+Crypto.Protocol.AllOrNothing
+ Transforms a message into a set of message blocks, such that the blocks
+ can be recombined to get the message back.
 
-Crypto.Protocol.Chaffing       Takes a set of authenticated message blocks
-                               (the wheat) and adds a number of
-                               randomly generated blocks (the chaff).
+Crypto.Protocol.Chaffing
+ Takes a set of authenticated message blocks (the wheat) and adds a number
+ of randomly generated blocks (the chaff).
+
+Crypto.Protocol.KDF
+ A collection of standard key derivation functions.
+
+:undocumented: __revision__
 """
 
-__all__ = ['AllOrNothing', 'Chaffing']
+__all__ = ['AllOrNothing', 'Chaffing', 'KDF']
 __revision__ = "$Id$"
diff --git a/lib/Crypto/SelfTest/Protocol/__init__.py b/lib/Crypto/SelfTest/Protocol/__init__.py
index dba6148..5d1867c 100644
--- a/lib/Crypto/SelfTest/Protocol/__init__.py
+++ b/lib/Crypto/SelfTest/Protocol/__init__.py
@@ -30,6 +30,7 @@ def get_tests(config={}):
     tests = []
     import test_chaffing;       tests += test_chaffing.get_tests(config=config)
     import test_rfc1751;        tests += test_rfc1751.get_tests(config=config)
+    import test_KDF;            tests += test_KDF.get_tests(config=config)
     return tests
 
 if __name__ == '__main__':
diff --git a/lib/Crypto/SelfTest/Protocol/test_KDF.py b/lib/Crypto/SelfTest/Protocol/test_KDF.py
new file mode 100644
index 0000000..7b0b999
--- /dev/null
+++ b/lib/Crypto/SelfTest/Protocol/test_KDF.py
@@ -0,0 +1,98 @@
+# -*- coding: utf-8 -*-
+#
+#  SelfTest/Protocol/test_KDF.py: Self-test for key derivation functions
+#
+# ===================================================================
+# The contents of this file are dedicated to the public domain.  To
+# the extent that dedication to the public domain is not available,
+# everyone is granted a worldwide, perpetual, royalty-free,
+# non-exclusive license to exercise all rights associated with the
+# contents of this file for any purpose whatsoever.
+# No rights are reserved.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+# ===================================================================
+
+__revision__ = "$Id$"
+
+import unittest
+from binascii import unhexlify
+
+from Crypto.SelfTest.st_common import list_test_cases
+from Crypto.Hash import SHA as SHA1,HMAC
+
+from Crypto.Protocol.KDF import *
+
+def t2b(t): return unhexlify(t)
+
+class PBKDF1_Tests(unittest.TestCase):
+
+    # List of tuples with test data.
+    # Each tuple is made up by:
+    #       Item #0: a pass phrase
+    #       Item #1: salt (8 bytes encoded in hex)
+    #       Item #2: output key length
+    #       Item #3: iterations to use
+    #       Item #4: expected result (encoded in hex)
+    _testData = (
+            # From http://www.di-mgt.com.au/cryptoKDFs.html#examplespbkdf
+            ("password","78578E5A5D63CB06",16,1000,"DC19847E05C64D2FAF10EBFB4A3D2A20"),
+    )
+    
+    def test1(self):
+        v = self._testData[0]
+        res = PBKDF1(v[0], t2b(v[1]), v[2], v[3], SHA1)
+        self.assertEqual(res, t2b(v[4]))
+
+class PBKDF2_Tests(unittest.TestCase):
+
+    # List of tuples with test data.
+    # Each tuple is made up by:
+    #       Item #0: a pass phrase
+    #       Item #1: salt (encoded in hex)
+    #       Item #2: output key length
+    #       Item #3: iterations to use
+    #       Item #4: expected result (encoded in hex)
+    _testData = (
+            # From http://www.di-mgt.com.au/cryptoKDFs.html#examplespbkdf
+            ("password","78578E5A5D63CB06",24,2048,"BFDE6BE94DF7E11DD409BCE20A0255EC327CB936FFE93643"),
+            # From RFC 6050
+            ("password","73616c74", 20, 1,          "0c60c80f961f0e71f3a9b524af6012062fe037a6"),
+            ("password","73616c74", 20, 2,          "ea6c014dc72d6f8ccd1ed92ace1d41f0d8de8957"),
+            ("password","73616c74", 20, 4096,       "4b007901b765489abead49d926f721d065a429c1"),
+            ("passwordPASSWORDpassword","73616c7453414c5473616c7453414c5473616c7453414c5473616c7453414c5473616c74",
+                                    25, 4096,       "3d2eec4fe41c849b80c8d83662c0e44a8b291a964cf2f07038"),
+            ( 'pass\x00word',"7361006c74",16,4096,  "56fa6aa75548099dcc37d7f03425e0c3"),
+    )
+    
+    def test1(self):
+        # Test only for HMAC-SHA1 as PRF
+
+        def prf(p,s):
+            return HMAC.new(p,s,SHA1).digest()
+
+        for i in xrange(len(self._testData)):
+            v = self._testData[i]
+            res  = PBKDF2(v[0], t2b(v[1]), v[2], v[3])
+            res2 = PBKDF2(v[0], t2b(v[1]), v[2], v[3], prf)
+            self.assertEqual(res, t2b(v[4]))
+            self.assertEqual(res, res2)
+
+def get_tests(config={}):
+    tests = []
+    tests += list_test_cases(PBKDF1_Tests)
+    tests += list_test_cases(PBKDF2_Tests)
+    return tests
+
+if __name__ == '__main__':
+    suite = lambda: unittest.TestSuite(get_tests())
+    unittest.main(defaultTest='suite')
+
+# vim:set ts=4 sw=4 sts=4
diff --git a/lib/Crypto/__init__.py b/lib/Crypto/__init__.py
index 16315b3..c0eb9d3 100644
--- a/lib/Crypto/__init__.py
+++ b/lib/Crypto/__init__.py
@@ -27,8 +27,8 @@ Subpackages:
 Crypto.Cipher             Secret-key encryption algorithms (AES, DES, ARC4)
 Crypto.Hash               Hashing algorithms (MD5, SHA, HMAC)
 Crypto.Protocol           Cryptographic protocols (Chaffing, all-or-nothing
-                          transform).   This package does not contain any
-                          network protocols.
+                          transform, key derivation functions).
+                          This package does not contain any network protocols.
 Crypto.PublicKey          Public-key encryption and signature algorithms
                           (RSA, DSA)
 Crypto.Util               Various useful modules and functions (long-to-string