all verify() methods now use "constant time" comparison function (see CHANGELOG for details)

6 files changed, 189 insertions, 17 deletions

diff --git a/CHANGES b/CHANGES
index 608d2af..7fb8c2c 100644
--- a/CHANGES
+++ b/CHANGES
@@ -32,6 +32,26 @@ Release History
 
     Other
 
+        .. _consteq-issue:
+
+        * All digest comparisons within Passlib are now done using
+          a "constant time" comparison function :func:`~passlib.utils.consteq`,
+          instead of ``==``.
+
+          *In detail:*
+
+              This change is motivated by an `hmac timing attack <http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/>`_
+              which exploits ``==``'s short-circuit comparison algorithm.
+              This attack is generally not applicable to password hashes,
+              as it requires the attacker to both know the salt,
+              and be able to generate digests beginning with a specific prefix.
+              However, while this task should be computationally difficult
+              against modern hashes (such as :class:`!sha512_crypt`), this
+              change should pre-emptively protect Passlib in case someone
+              constructs a such an attack in the future. Furthermore, some of
+              the legacy hashes supported by Passlib (such as
+              :class:`!mysql323`) are already weak enough to be vulnerable.
+
         * Restored builtin pure-python BCrypt implementation
           (:mod:`passlib.utils._slow_bcrypt`) that was removed in v1.3.
           This implementation is still *WAY* to slow to be suitable
@@ -54,7 +74,7 @@ Release History
     under some of the other BCrypt implementations, such as OpenBSD's
     ``/etc/master.passwd``.
 
-    *In detail:*    
+    *In detail:*
 
         BCrypt hashes contain 4 "padding" bits in the encoded salt, and Passlib
         (<= 1.5.2) generated salts in a manner which frequently set some of the
@@ -64,23 +84,23 @@ Release History
         BCrypt salt generation needed to be fixed to ensure compatibility,
         and a route provided to correct existing hashes already out in the wild
         [issue 25].
-        
+
     *Changes in this release:*
-    
+
     .. currentmodule:: passlib.context
-      
+
     * BCrypt hashes generated by Passlib now have all padding bits cleared.
-    
+
     * Passlib will continue to accept BCrypt hashes that have padding bits
       set, but when it encounters them, it will issue a :exc:`UserWarning`
       recommending that the hash should be fixed (see below).
-      
+
     * Applications which use :meth:`CryptContext.verify_and_update` will
       have any such hashes automatically re-encoded the next time the user
       logs in.
 
     *To fix existing hashes:*
-    
+
         If you have BCrypt hashes which might have their padding bits set,
         you can import :class:`!passlib.hash.bcrypt`, and
         call ``clean_hash = bcrypt.normhash(hash)``.
diff --git a/docs/lib/passlib.utils.rst b/docs/lib/passlib.utils.rst
index 63de110..0379e01 100644
--- a/docs/lib/passlib.utils.rst
+++ b/docs/lib/passlib.utils.rst
@@ -50,6 +50,7 @@ Bytes Manipulation
 .. autofunction:: bytes_to_int
 .. autofunction:: int_to_bytes
 .. autofunction:: xor_bytes
+.. autofunction:: consteq
 
 Randomness
 ==========
diff --git a/passlib/apache.py b/passlib/apache.py
index deadff0..897cdf3 100644
--- a/passlib/apache.py
+++ b/passlib/apache.py
@@ -11,7 +11,8 @@ import sys
 #site
 #libs
 from passlib.context import CryptContext
-from passlib.utils import render_bytes, bjoin, bytes, b, to_unicode, to_bytes
+from passlib.utils import render_bytes, bjoin, bytes, b, \
+                          to_unicode, to_bytes, consteq
 #pkg
 #local
 __all__ = [
@@ -523,7 +524,8 @@ class HtdigestFile(_CommonFile):
         hash = self._entry_map.get((user,realm))
         if hash is None:
             return None
-        return hash == self._calc_digest(user, realm, password)
+        result = self._calc_digest(user, realm, password)
+        return consteq(result, hash)
 
 #=========================================================
 # eof
diff --git a/passlib/tests/test_utils.py b/passlib/tests/test_utils.py
index 80db9c3..6c19679 100644
--- a/passlib/tests/test_utils.py
+++ b/passlib/tests/test_utils.py
@@ -142,6 +142,90 @@ class MiscTest(TestCase):
         #self.assertEqual(ret, (False, None))
         # end Py3k #
 
+    def test_consteq(self):
+        "test consteq()"
+        # NOTE: this test is kind of over the top, but that's only because
+        # this is used for the critical task of comparing hashes for equality.
+        consteq = utils.consteq
+
+        # ensure error raises for wrong types
+        self.assertRaises(TypeError, consteq, u'', b(''))
+        self.assertRaises(TypeError, consteq, u'', 1)
+        self.assertRaises(TypeError, consteq, u'', None)
+
+        self.assertRaises(TypeError, consteq, b(''), u'')
+        self.assertRaises(TypeError, consteq, b(''), 1)
+        self.assertRaises(TypeError, consteq, b(''), None)
+
+        self.assertRaises(TypeError, consteq, None, u'')
+        self.assertRaises(TypeError, consteq, None, b(''))
+        self.assertRaises(TypeError, consteq, 1, u'')
+        self.assertRaises(TypeError, consteq, 1, b(''))
+
+        # check equal inputs compare correctly
+        for value in [
+                u"a",
+                u"abc",
+                u"\xff\xa2\x12\x00"*10,
+            ]:
+            self.assertTrue(consteq(value, value), "value %r:" % (value,))
+            value = value.encode("latin-1")
+            self.assertTrue(consteq(value, value), "value %r:" % (value,))
+
+        # check non-equal inputs compare correctly
+        for l,r in [
+                # check same-size comparisons with differing contents fail.
+                (u"a",         u"c"),
+                (u"abcabc",    u"zbaabc"),
+                (u"abcabc",    u"abzabc"),
+                (u"abcabc",    u"abcabz"),
+                ((u"\xff\xa2\x12\x00"*10)[:-1] + u"\x01",
+                    u"\xff\xa2\x12\x00"*10),
+
+                # check different-size comparisons fail.
+                (u"",       u"a"),
+                (u"abc",    u"abcdef"),
+                (u"abc",    u"defabc"),
+                (u"qwertyuiopasdfghjklzxcvbnm", u"abc"),
+            ]:
+            self.assertFalse(consteq(l, r), "values %r %r:" % (l,r))
+            self.assertFalse(consteq(r, l), "values %r %r:" % (r,l))
+            l = l.encode("latin-1")
+            r = r.encode("latin-1")
+            self.assertFalse(consteq(l, r), "values %r %r:" % (l,r))
+            self.assertFalse(consteq(r, l), "values %r %r:" % (r,l))
+
+        # TODO: add some tests to ensure we take THETA(strlen) time.
+        # this might be hard to do reproducably.
+        # NOTE: below code was used to generate stats for analysis
+        ##from math import log as logb
+        ##import timeit
+        ##multipliers = [ 1<<s for s in range(9)]
+        ##correct =   u"abcdefgh"*(1<<4)
+        ##incorrect = u"abcdxfgh"
+        ##print
+        ##first = True
+        ##for run in xrange(1):
+        ##    times = []
+        ##    chars = []
+        ##    for m in multipliers:
+        ##        supplied = incorrect * m
+        ##        def test():
+        ##            self.assertFalse(consteq(supplied,correct))
+        ##            #self.assertFalse(supplied == correct)
+        ##        times.append(timeit.timeit(test, number=100000))
+        ##        chars.append(len(supplied))
+        ##    # output for wolfram alpha
+        ##    print ", ".join("{%r, %r}" % (c,round(t,4)) for c,t in zip(chars,times))
+        ##    def scale(c):
+        ##        return logb(c,2)
+        ##    print ", ".join("{%r, %r}" % (scale(c),round(t,4)) for c,t in zip(chars,times))
+        ##    # output for spreadsheet
+        ##    ##if first:
+        ##    ##    print "na, " + ", ".join(str(c) for c in chars)
+        ##    ##    first = False
+        ##    ##print ", ".join(str(c) for c in [run] + times)
+
 #=========================================================
 #byte/unicode helpers
 #=========================================================
@@ -488,7 +572,7 @@ class _MD4_Test(TestCase):
 
     def test_md4_update(self):
         "test md4 update"
-        md4 = self.hash        
+        md4 = self.hash
         h = md4(b(''))
         self.assertEqual(h.hexdigest(), "31d6cfe0d16ae931b73c59d7e0c089c0")
 
diff --git a/passlib/utils/__init__.py b/passlib/utils/__init__.py
index 6c897bb..1315174 100644
--- a/passlib/utils/__init__.py
+++ b/passlib/utils/__init__.py
@@ -453,6 +453,70 @@ def is_ascii_safe(source):
 #=================================================================================
 #string helpers
 #=================================================================================
+
+def consteq(left, right):
+    """check two strings/bytes for equality, taking constant time relative
+    to the size of the righthand input.
+
+    The purpose of this function is to aid in preventing timing attacks
+    during digest comparisons (see the 1.6 changelog
+    :ref:`entry <consteq-issue>` for more details).
+    """
+    # NOTE:
+    # This function attempts to take an amount of time proportional
+    # to ``THETA(len(right))``. The main loop is designed so that timing attacks
+    # against this function should reveal nothing about how much (or which
+    # parts) of the two inputs match.
+    #
+    # Why ``THETA(len(right))``?
+    # Assuming the attacker controls one of the two inputs, padding to
+    # the largest input or trimming to the smallest input both allow
+    # a timing attack to reveal the length of the controlled input.
+    # However, by fixing the runtime to be proportional to the right input:
+    # * If the right value is attacker controlled, the runtime is proportional
+    #   to their input, giving nothing away about the left value's size.
+    # * If the left value is attacker controlled, the runtime is constant
+    #   relative to their input, giving nothing away about the right value's size.
+
+    # validate types
+    if isinstance(left, unicode):
+        if not isinstance(right, unicode):
+            raise TypeError("inputs must be both unicode or bytes")
+        # Py3k #
+        #isbytes = False
+        # end Py3k #
+    elif isinstance(left, bytes):
+        if not isinstance(right, bytes):
+            raise TypeError("inputs must be both unicode or bytes")
+        # Py3k #
+        #isbytes = True
+        # end Py3k #
+    else:
+        raise TypeError("inputs must be both unicode or bytes")
+
+    # do size comparison.
+    if len(left) == len(right):
+        # if sizes are the same, setup loop to perform actual check of contents.
+        tmp = left
+        result = 0
+    else:
+        # if sizes aren't the same, set 'result' so equality will fail regardless
+        # of contents. then, to ensure we do exactly 'len(right)' iterations
+        # of the loop, just compare 'right' against itself.
+        tmp = right
+        result = 1
+
+    # run constant-time string comparision
+    # Py3k #
+    #if isbytes:
+    #    for l,r in zip(tmp, right):
+    #        result |= l ^ r
+    #    return result == 0
+    # end Py3k #
+    for l,r in zip(tmp, right):
+        result |= ord(l) ^ ord(r)
+    return result == 0
+
 def splitcomma(source, sep=","):
     "split comma-separated string into list of elements, stripping whitespace and discarding empty elements"
     return [
diff --git a/passlib/utils/handlers.py b/passlib/utils/handlers.py
index 877b4da..e555421 100644
--- a/passlib/utils/handlers.py
+++ b/passlib/utils/handlers.py
@@ -14,7 +14,7 @@ from warnings import warn
 #site
 #libs
 from passlib.registry import get_crypt_handler
-from passlib.utils import to_hash_str, bytes, b, \
+from passlib.utils import to_hash_str, bytes, b, consteq, \
         classproperty, h64, getrandstr, getrandbytes, \
         rng, is_crypt_handler, ALL_BYTE_VALUES, MissingBackendError
 #pkg
@@ -224,7 +224,7 @@ class StaticHandler(object):
             raise ValueError("no hash specified")
         hash = cls._norm_hash(hash)
         result = cls.genhash(secret, hash, *cargs, **context)
-        return cls._norm_hash(result) == hash
+        return consteq(cls._norm_hash(result), hash)
 
     @classmethod
     def _norm_hash(cls, hash):
@@ -462,7 +462,7 @@ class GenericHandler(object):
         # may wish to either override this, or override norm_checksum
         # to normalize any checksums provided by from_string()
         self = cls.from_string(hash)
-        return self.checksum == self.calc_checksum(secret)
+        return consteq(self.calc_checksum(secret), self.checksum)
 
     #=========================================================
     #eoc
@@ -778,6 +778,7 @@ class HasSalt(GenericHandler):
         if salt is None:
             if strict:
                 raise ValueError("no salt specified")
+            #XXX: should we run generated salts through norm_salt? probably.
             return cls.generate_salt(salt_size=salt_size, strict=strict)
 
         #validate input charset
@@ -994,11 +995,11 @@ class HasManyBackends(GenericHandler):
     which is using :class:`HasManyBackends` as a mixin:
 
     .. attribute:: backends
-    
+
         This attribute should be a tuple containing the names of the backends
         which are supported. Two common names are ``"os_crypt"`` (if backend
         uses :mod:`crypt`), and ``"builtin"`` (if the backend is a pure-python
-        fallback). 
+        fallback).
 
     .. attribute:: _has_backend_{name}
 
@@ -1006,9 +1007,9 @@ class HasManyBackends(GenericHandler):
         specific backend is available, it should be either ``True``
         or ``False``. One of these should be provided by
         the subclass for each backend listed in :attr:`backends`.
-        
+
     .. classmethod:: _calc_checksum_{name}
-    
+
         private class method that should implement :meth:`calc_checksum`
         for a given backend. it will only be called if the backend has
         been selected by :meth:`set_backend`. One of these should be provided