work on des_crypt family

* cleaned up source of des_crypt variants and DES util functions
* DES utils functions now have tighter input validation, full UT coverage

1 files changed, 238 insertions, 115 deletions

diff --git a/passlib/utils/des.py b/passlib/utils/des.py
index 4172a2e..25f1d0d 100644
--- a/passlib/utils/des.py
+++ b/passlib/utils/des.py
@@ -1,4 +1,5 @@
-"""
+"""passlib.utils.des -- DES block encryption routines
+
 History
 =======
 These routines (which have since been drastically modified for python)
@@ -32,8 +33,7 @@ The copyright & license for that source is as follows::
     @version $Id: UnixCrypt2.txt,v 1.1.1.1 2005/09/13 22:20:13 christos Exp $
     @author Greg Wilkins (gregw)
 
-netbsd des-crypt implementation,
-which has some nice notes on how this all works -
+The netbsd des-crypt implementation has some nice notes on how this all works -
     http://fxr.googlebit.com/source/lib/libcrypt/crypt.c?v=NETBSD-CURRENT
 """
 
@@ -45,7 +45,10 @@ which has some nice notes on how this all works -
 # core
 import struct
 # pkg
-from passlib.utils.compat import bytes, join_byte_values, byte_elem_value, irange, irange
+from passlib import exc
+from passlib.utils.compat import bytes, join_byte_values, byte_elem_value, \
+                                 b, irange, irange, int_types
+from passlib.utils import deprecated_function
 # local
 __all__ = [
     "expand_des_key",
@@ -54,30 +57,29 @@ __all__ = [
 ]
 
 #=========================================================
-#precalculated iteration ranges & constants
+# constants
 #=========================================================
-R8 = irange(8)
-RR8 = irange(7, -1, -1)
-RR4 = irange(3, -1, -1)
-RR12_1 = irange(11, 1, -1)
-RR9_1 = irange(9,-1,-1)
 
-RR6_S2 = irange(6, -1, -2)
-RR14_S2 = irange(14, -1, -2)
-R16_S2 = irange(0, 16, 2)
+# masks/upper limits for various integer sizes
+INT_24_MASK = 0xffffff
+INT_56_MASK = 0xffffffffffffff
+INT_64_MASK = 0xffffffffffffffff
 
-INT_24_MAX = 0xffffff
-INT_64_MAX = 0xffffffff
-INT_64_MAX = 0xffffffffffffffff
+# mask to clear parity bits from 64-bit key
+_KDATA_MASK = 0xfefefefefefefefe
+_KPARITY_MASK = 0x0101010101010101
 
-uint64_struct = struct.Struct(">Q")
+# mask used to setup key schedule
+_KS_MASK = 0xfcfcfcfcffffffff
 
 #=========================================================
-# static tables for des
+# static DES tables
 #=========================================================
-PCXROT = IE3264 = SPE = CF6464 = None #placeholders filled in by load_tables
 
-def load_tables():
+# placeholders filled in by _load_tables()
+PCXROT = IE3264 = SPE = CF6464 = None
+
+def _load_tables():
     "delay loading tables until they are actually needed"
     global PCXROT, IE3264, SPE, CF6464
 
@@ -558,10 +560,14 @@ def load_tables():
       0x0000000004040000, 0x0000000004040004, 0x0000000004040400, 0x0000000004040404, ),
     )
     #=========================================================
-    #eof load_data
+    # eof _load_tables()
     #=========================================================
 
-def permute(c, p):
+#=========================================================
+# support
+#=========================================================
+
+def _permute(c, p):
     """Returns the permutation of the given 32-bit or 64-bit code with
     the specified permutation table."""
     #NOTE: only difference between 32 & 64 bit permutations
@@ -573,104 +579,213 @@ def permute(c, p):
     return out
 
 #=========================================================
-#des frontend
+# packing & unpacking
+#=========================================================
+_uint64_struct = struct.Struct(">Q")
+
+_BNULL = b('\x00')
+
+def _pack64(value):
+    return _uint64_struct.pack(value)
+
+def _unpack64(value):
+    return _uint64_struct.unpack(value)[0]
+
+def _pack56(value):
+    return _uint64_struct.pack(value)[1:]
+
+def _unpack56(value):
+    return _uint64_struct.unpack(_BNULL+value)[0]
+
+#=========================================================
+# 56->64 key manipulation
 #=========================================================
+
+##def expand_7bit(value):
+##    "expand 7-bit integer => 7-bits + 1 odd-parity bit"
+##    # parity calc adapted from 32-bit even parity alg found at
+##    # http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel
+##    assert 0 <= value < 0x80, "value out of range"
+##    return (value<<1) | (0x9669 >> ((value ^ (value >> 4)) & 0xf)) & 1
+
+_EXPAND_ITER = irange(49,-7,-7)
+
 def expand_des_key(key):
-    "convert 7 byte des key to 8 byte des key (by adding parity bit every 7 bits)"
-    if not isinstance(key, bytes):
-        raise TypeError("key must be bytes, not %s" % (type(key),))
+    "convert DES from 7 bytes to 8 bytes (by inserting empty parity bits)"
+    if isinstance(key, bytes):
+        if len(key) != 7:
+            raise ValueError("key must be 7 bytes in size")
+    elif isinstance(key, int_types):
+        if key < 0 or key > INT_56_MASK:
+            raise ValueError("key must be 56-bit non-negative integer")
+        return _unpack64(expand_des_key(_pack56(key)))
+    else:
+        raise exc.ExpectedTypeError(key, "bytes or int", "key")
+    key = _unpack56(key)
+    # NOTE: this function would insert correctly-valued parity bits in each key,
+    # but the parity bit would just be ignored in des_encrypt_block(),
+    # so not bothering to use it.
+    ##return join_byte_values(expand_7bit((key >> shift) & 0x7f)
+    #                         for shift in _EXPAND_ITER)
+    return join_byte_values(((key>>shift) & 0x7f)<<1 for shift in _EXPAND_ITER)
+
+def shrink_des_key(key):
+    "convert DES key from 8 bytes to 7 bytes (by discarding the parity bits)"
+    if isinstance(key, bytes):
+        if len(key) != 8:
+            raise ValueError("key must be 8 bytes in size")
+        return _pack56(shrink_des_key(_unpack64(key)))
+    elif isinstance(key, int_types):
+        if key < 0 or key > INT_64_MASK:
+            raise ValueError("key must be 64-bit non-negative integer")
+    else:
+        raise exc.ExpectedTypeError(key, "bytes or int", "key")
+    key >>= 1
+    result = 0
+    offset = 0
+    while offset < 56:
+        result |= (key & 0x7f)<<offset
+        key >>= 8
+        offset += 7
+    assert not (result & ~INT_64_MASK)
+    return result
 
-    #NOTE: could probably do this much more cleverly and efficiently,
-    # but no need really given it's use.
+#=========================================================
+# des encryption
+#=========================================================
+def des_encrypt_block(key, input, salt=0, rounds=1):
+    """encrypt single block of data using DES, operates on 8-byte strings.
 
-    #NOTE: the parity bits are generally ignored, including by des_encrypt_block below
-    assert len(key) == 7
+    :arg key:
+        DES key as 7 byte string, or 8 byte string with parity bits
+        (parity bit values are ignored).
 
-    def iter_bits(source):
-        for c in source:
-            v = byte_elem_value(c)
-            for i in irange(7,-1,-1):
-                yield (v>>i) & 1
+    :arg input:
+        plaintext block to encrypt, as 8 byte string.
 
-    out = 0
-    p = 1
-    for i, b in enumerate(iter_bits(key)):
-        out = (out<<1) + b
-        p ^= b
-        if i % 7 == 6:
-            out = (out<<1) + p
-            p = 1
-
-    return join_byte_values(
-        ((out>>s) & 0xFF)
-        for s in irange(8*7,-8,-8)
-    )
+    :arg salt:
+        optional 24-bit integer used to mutate the base DES algorithm in a
+        manner specific to :class:`~passlib.hash.des_crypt` and it's variants:
+
+        for each bit ``i`` which is set in the salt value,
+        bits ``i`` and ``i+24`` are swapped in the DES E-box output.
+        the default (``salt=0``) provides the normal DES behavior.
 
-def des_encrypt_block(key, input):
-    """do traditional encryption of a single DES block
+    :arg rounds:
+        optional number of rounds of to apply the DES key schedule.
+        the default (``rounds=1``) provides the normal DES behavior,
+        but :class:`~passlib.hash.des_crypt` and it's variants use
+        alternate rounds values.
 
-    :arg key: 8 byte des key
-    :arg input: 8 byte plaintext
-    :returns: 8 byte ciphertext
+    :raises TypeError: if any of the provided args are of the wrong type.
+    :raises ValueError:
+        if any of the input blocks are the wrong size,
+        or the salt/rounds values are out of range.
 
-    all values must be :class:`bytes`
+    :returns:
+        resulting 8-byte ciphertext block.
     """
-    if not isinstance(key, bytes):
-        raise TypeError("key must be bytes, not %s" % (type(key),))
-    if len(key) == 7:
-        key = expand_des_key(key)
-    if not isinstance(input, bytes):
-        raise TypeError("input must be bytes, not %s" % (type(input),))
-    input = uint64_struct.unpack(input)[0]
-    key = uint64_struct.unpack(key)[0]
-    out = mdes_encrypt_int_block(key, input, 0, 1)
-    return uint64_struct.pack(out)
-
-def mdes_encrypt_int_block(key, input, salt=0, rounds=1):
-    """do modified multi-round DES encryption of single DES block.
-
-    the function implements the salted, variable-round version
-    of DES used by :class:`~passlib.hash.des_crypt` and related variants.
-    it also can perform regular DES encryption
-    by using ``salt=0, rounds=1`` (the default values).
-
-    :arg key: 8 byte des key as integer
-    :arg input: 8 byte plaintext block as integer
-    :arg salt: integer 24 bit salt, used to mutate output (defaults to 0)
-    :arg rounds: number of rounds of DES encryption to apply (defaults to 1)
-
-    The salt is used to to mutate the normal DES encrypt operation
-    by swapping bits ``i`` and ``i+24`` in the DES E-Box output
-    if and only if bit ``i`` is set in the salt value. Thus,
-    if the salt is set to ``0``, normal DES encryption is performed.
+    # validate & unpack key
+    if isinstance(key, bytes):
+        if len(key) == 7:
+            key = expand_des_key(key)
+        elif len(key) != 8:
+            raise ValueError("key must be 7 or 8 bytes")
+        key = _unpack64(key)
+    else:
+        raise exc.ExpectedTypeError(key, "bytes", "key")
+
+    # validate & unpack input
+    if isinstance(input, bytes):
+        if len(input) != 8:
+            raise ValueError("input block must be 8 bytes")
+        input = _unpack64(input)
+    else:
+        raise exc.ExpectedTypeError(input, "bytes", "input")
+
+    # hand things off to other func
+    result = des_encrypt_int_block(key, input, salt, rounds)
+
+    # repack result
+    return _pack64(result)
+
+def des_encrypt_int_block(key, input, salt=0, rounds=1):
+    """encrypt single block of data using DES, operates on 64-bit integers.
+
+    this function is essentially the same as :func:`des_encrypt_block`,
+    except that it operates on integers, and will NOT automatically
+    expand 56-bit keys if provided (since there's no way to detect them).
+
+    :arg key:
+        DES key as 64-bit integer (the parity bits are ignored).
+
+    :arg input:
+        input block as 64-bit integer
+
+    :arg salt:
+        optional 24-bit integer used to mutate the base DES algorithm.
+        defaults to ``0`` (no mutation applied).
+
+    :arg rounds:
+        optional number of rounds of to apply the DES key schedule.
+        defaults to ``1``.
+
+    :raises TypeError: if any of the provided args are of the wrong type.
+    :raises ValueError:
+        if any of the input blocks are the wrong size,
+        or the salt/rounds values are out of range.
 
     :returns:
-        resulting block as 8 byte integer
+        resulting ciphertext as 64-bit integer.
     """
+    #-------------------------------------------------------------------
+    # input validation
+    #-------------------------------------------------------------------
+
+    # validate salt, rounds
+    if rounds < 1:
+        raise ValueError("rounds must be positive integer")
+    if salt < 0 or salt > INT_24_MASK:
+        raise ValueError("salt must be 24-bit non-negative integer")
+
+    # validate & unpack key
+    if not isinstance(key, int_types):
+        raise exc.ExpectedTypeError(key, "int", "key")
+    elif key < 0 or key > INT_64_MASK:
+        raise ValueError("key must be 64-bit non-negative integer")
+
+    # validate & unpack input
+    if not isinstance(input, int_types):
+        raise exc.ExpectedTypeError(input, "int", "input")
+    elif input < 0 or input > INT_64_MASK:
+        raise ValueError("input must be 64-bit non-negative integer")
+
+    #-------------------------------------------------------------------
+    # DES setup
+    #-------------------------------------------------------------------
+    # load tables if not already done
     global SPE, PCXROT, IE3264, CF6464
+    if PCXROT is None:
+        _load_tables()
 
-    #bounds check
-    assert 0 <= input <= INT_64_MAX, "input value out of range"
-    assert 0 <= salt <= INT_24_MAX, "salt value out of range"
-    assert rounds >= 0, "rounds out of range"
-    assert 0 <= key <= INT_64_MAX, "key value out of range"
+    # load SPE into local vars to speed things up and remove an array access call
+    SPE0, SPE1, SPE2, SPE3, SPE4, SPE5, SPE6, SPE7 = SPE
 
-    #load tables if not already done
-    if PCXROT is None:
-        load_tables()
+    # NOTE: parity bits are ignored completely
+    # (UTs do fuzz testing to ensure this)
 
-    #convert key int -> key schedule
-    #NOTE: generation was modified to output two elements at a time,
-    #to optimize for per-round algorithm below.
-    mask = ~0x0303030300000000
-    def _gen(K):
+    # generate key schedule
+    # NOTE: generation was modified to output two elements at a time,
+    # so that per-round loop could do two passes at once.
+    def _iter_key_schedule(ks_odd):
+        "given 64-bit key, iterates over the 8 (even,odd) key schedule pairs"
         for p_even, p_odd in PCXROT:
-            K1 = permute(K, p_even)
-            K = permute(K1, p_odd)
-            yield K1 & mask, K & mask
-    ks_list = list(_gen(key))
+            ks_even = _permute(ks_odd, p_even)
+            ks_odd = _permute(ks_even, p_odd)
+            yield ks_even & _KS_MASK, ks_odd & _KS_MASK
+    ks_list = list(_iter_key_schedule(key))
 
-    #expand 24 bit salt -> 32 bit
+    # expand 24 bit salt -> 32 bit per des_crypt & bsdi_crypt
     salt = (
         ((salt & 0x00003f) << 26) |
         ((salt & 0x000fc0) << 12) |
@@ -678,26 +793,25 @@ def mdes_encrypt_int_block(key, input, salt=0, rounds=1):
         ((salt & 0xfc0000) >> 16)
         )
 
-    #init L & R
+    # init L & R
     if input == 0:
         L = R = 0
     else:
         L = ((input >> 31) & 0xaaaaaaaa) | (input & 0x55555555)
-        L = permute(L, IE3264)
+        L = _permute(L, IE3264)
 
         R = ((input >> 32) & 0xaaaaaaaa) | ((input >> 1) & 0x55555555)
-        R = permute(R, IE3264)
-
-    #load SPE into local vars to speed things up and remove an array access call
-    SPE0, SPE1, SPE2, SPE3, SPE4, SPE5, SPE6, SPE7 = SPE
+        R = _permute(R, IE3264)
 
-    #run specified number of passed
+    #-------------------------------------------------------------------
+    # main DES loop - run for specified number of rounds
+    #-------------------------------------------------------------------
     while rounds:
         rounds -= 1
 
-        #run over each part of the schedule, 2 parts at a time
+        # run over each part of the schedule, 2 parts at a time
         for ks_even, ks_odd in ks_list:
-            k = ((R>>32) ^ R) & salt #use the salt to alter specific bits
+            k = ((R>>32) ^ R) & salt # use the salt to flip specific bits
             B = (k<<32) ^ k ^ R ^ ks_even
 
             L ^= (SPE0[(B>>58)&0x3f] ^ SPE1[(B>>50)&0x3f] ^
@@ -705,7 +819,7 @@ def mdes_encrypt_int_block(key, input, salt=0, rounds=1):
                   SPE4[(B>>26)&0x3f] ^ SPE5[(B>>18)&0x3f] ^
                   SPE6[(B>>10)&0x3f] ^ SPE7[(B>>2)&0x3f])
 
-            k = ((L>>32) ^ L) & salt #use the salt to alter specific bits
+            k = ((L>>32) ^ L) & salt # use the salt to flip specific bits
             B = (k<<32) ^ k ^ L ^ ks_odd
 
             R ^= (SPE0[(B>>58)&0x3f] ^ SPE1[(B>>50)&0x3f] ^
@@ -716,6 +830,9 @@ def mdes_encrypt_int_block(key, input, salt=0, rounds=1):
         # swap L and R
         L, R = R, L
 
+    #-------------------------------------------------------------------
+    # return final result
+    #-------------------------------------------------------------------
     C = (
             ((L>>3) &  0x0f0f0f0f00000000)
             |
@@ -725,10 +842,16 @@ def mdes_encrypt_int_block(key, input, salt=0, rounds=1):
             |
             ((R<<1) &  0x00000000f0f0f0f0)
         )
-
-    C = permute(C, CF6464)
-
-    return C
+    return _permute(C, CF6464)
+
+def mdes_encrypt_int_block(key, input, salt=0, rounds=1): # pragma: no cover
+    warn("mdes_encrypt_int_block() has been deprecated as of Passlib 1.6,"
+         "and will be removed in Passlib 1.8, use des_encrypt_int_block instead.")
+    if isinstance(key, bytes):
+        if len(key) == 7:
+            key = expand_des_key(key)
+        key = _unpack64(key)
+    return des_encrypt_int_block(key, input, salt, rounds)
 
 #=========================================================
 #eof