codekingpro/portable-devtools

1"""passlib.utils.scrypt._builtin -- scrypt() kdf in pure-python"""2#==========================================================================3# imports4#==========================================================================5# core6import operator7import struct8# pkg9from passlib.utils.compat import izip10from passlib.crypto.digest import pbkdf2_hmac11from passlib.crypto.scrypt._salsa import salsa2012# local13__all__ =[14    "ScryptEngine",15]16 17#==========================================================================18# scrypt engine19#==========================================================================20class ScryptEngine(object):21    """22    helper class used to run scrypt kdf, see scrypt() for frontend23 24    .. warning::25        this class does NO validation of the input ranges or types.26 27        it's not intended to be used directly,28        but only as a backend for :func:`passlib.utils.scrypt.scrypt()`.29    """30    #=================================================================31    # instance attrs32    #=================================================================33 34    # primary scrypt config parameters35    n = 036    r = 037    p = 038 39    # derived values & objects40    smix_bytes = 041    iv_bytes = 042    bmix_len = 043    bmix_half_len = 044    bmix_struct = None45    integerify = None46 47    #=================================================================48    # frontend49    #=================================================================50    @classmethod51    def execute(cls, secret, salt, n, r, p, keylen):52        """create engine & run scrypt() hash calculation"""53        return cls(n, r, p).run(secret, salt, keylen)54 55    #=================================================================56    # init57    #=================================================================58    def __init__(self, n, r, p):59        # store config60        self.n = n61        self.r = r62        self.p = p63        self.smix_bytes = r << 7  # num bytes in smix input - 2*r*16*464        self.iv_bytes = self.smix_bytes * p65        self.bmix_len = bmix_len = r << 5  # length of bmix block list - 32*r integers66        self.bmix_half_len = r << 467        assert struct.calcsize("I") == 468        self.bmix_struct = struct.Struct("<" + str(bmix_len) + "I")69 70        # use optimized bmix for certain cases71        if r == 1:72            self.bmix = self._bmix_173 74        # pick best integerify function - integerify(bmix_block) should75        # take last 64 bytes of block and return a little-endian integer.76        # since it's immediately converted % n, we only have to extract77        # the first 32 bytes if n < 2**32 - which due to the current78        # internal representation, is already unpacked as a 32-bit int.79        if n <= 0xFFFFffff:80            integerify = operator.itemgetter(-16)81        else:82            assert n <= 0xFFFFffffFFFFffff83            ig1 = operator.itemgetter(-16)84            ig2 = operator.itemgetter(-17)85            def integerify(X):86                return ig1(X) | (ig2(X)<<32)87        self.integerify = integerify88 89    #=================================================================90    # frontend91    #=================================================================92    def run(self, secret, salt, keylen):93        """94        run scrypt kdf for specified secret, salt, and keylen95 96        .. note::97 98            * time cost is ``O(n * r * p)``99            * mem cost is ``O(n * r)``100        """101        # stretch salt into initial byte array via pbkdf2102        iv_bytes = self.iv_bytes103        input = pbkdf2_hmac("sha256", secret, salt, rounds=1, keylen=iv_bytes)104 105        # split initial byte array into 'p' mflen-sized chunks,106        # and run each chunk through smix() to generate output chunk.107        smix = self.smix108        if self.p == 1:109            output = smix(input)110        else:111            # XXX: *could* use threading here, if really high p values encountered,112            #      but would tradeoff for more memory usage.113            smix_bytes = self.smix_bytes114            output = b''.join(115                smix(input[offset:offset+smix_bytes])116                for offset in range(0, iv_bytes, smix_bytes)117            )118 119        # stretch final byte array into output via pbkdf2120        return pbkdf2_hmac("sha256", secret, output, rounds=1, keylen=keylen)121 122    #=================================================================123    # smix() helper124    #=================================================================125    def smix(self, input):126        """run SCrypt smix function on a single input block127 128        :arg input:129            byte string containing input data.130            interpreted as 32*r little endian 4 byte integers.131 132        :returns:133            byte string containing output data134            derived by mixing input using n & r parameters.135 136        .. note:: time & mem cost are both ``O(n * r)``137        """138        # gather locals139        bmix = self.bmix140        bmix_struct = self.bmix_struct141        integerify = self.integerify142        n = self.n143 144        # parse input into 32*r integers ('X' in scrypt source)145        # mem cost -- O(r)146        buffer = list(bmix_struct.unpack(input))147 148        # starting with initial buffer contents, derive V s.t.149        # V[0]=initial_buffer ... V[i] = bmix(V[i-1], V[i-1]) ... V[n-1] = bmix(V[n-2], V[n-2])150        # final buffer contents should equal bmix(V[n-1], V[n-1])151        #152        # time cost -- O(n * r) -- n loops, bmix is O(r)153        # mem cost -- O(n * r) -- V is n-element array of r-element tuples154        # NOTE: could do time / memory tradeoff to shrink size of V155        def vgen():156            i = 0157            while i < n:158                last = tuple(buffer)159                yield last160                bmix(last, buffer)161                i += 1162        V = list(vgen())163 164        # generate result from X & V.165        #166        # time cost -- O(n * r) -- loops n times, calls bmix() which has O(r) time cost167        # mem cost -- O(1) -- allocates nothing, calls bmix() which has O(1) mem cost168        get_v_elem = V.__getitem__169        n_mask = n - 1170        i = 0171        while i < n:172            j = integerify(buffer) & n_mask173            result = tuple(a ^ b for a, b in izip(buffer, get_v_elem(j)))174            bmix(result, buffer)175            i += 1176 177        # # NOTE: we could easily support arbitrary values of ``n``, not just powers of 2,178        # #       but very few implementations have that ability, so not enabling it for now...179        # if not n_is_log_2:180        # while i < n:181        #     j = integerify(buffer) % n182        #     tmp = tuple(a^b for a,b in izip(buffer, get_v_elem(j)))183        #     bmix(tmp,buffer)184        #     i += 1185 186        # repack tmp187        return bmix_struct.pack(*buffer)188 189    #=================================================================190    # bmix() helper191    #=================================================================192    def bmix(self, source, target):193        """194        block mixing function used by smix()195        uses salsa20/8 core to mix block contents.196 197        :arg source:198            source to read from.199            should be list of 32*r 4-byte integers200            (2*r salsa20 blocks).201 202        :arg target:203            target to write to.204            should be list with same size as source.205            the existing value of this buffer is ignored.206 207        .. warning::208 209            this operates *in place* on target,210            so source & target should NOT be same list.211 212        .. note::213 214            * time cost is ``O(r)`` -- loops 16*r times, salsa20() has ``O(1)`` cost.215 216            * memory cost is ``O(1)`` -- salsa20() uses 16 x uint4,217              all other operations done in-place.218        """219        ## assert source is not target220        # Y[-1] = B[2r-1], Y[i] = hash( Y[i-1] xor B[i])221        # B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */222        half = self.bmix_half_len # 16*r out of 32*r - start of Y_1223        tmp = source[-16:] # 'X' in scrypt source224        siter = iter(source)225        j = 0226        while j < half:227            jn = j+16228            target[j:jn] = tmp = salsa20(a ^ b for a, b in izip(tmp, siter))229            target[half+j:half+jn] = tmp = salsa20(a ^ b for a, b in izip(tmp, siter))230            j = jn231 232    def _bmix_1(self, source, target):233        """special bmix() method optimized for ``r=1`` case"""234        B = source[16:]235        target[:16] = tmp = salsa20(a ^ b for a, b in izip(B, iter(source)))236        target[16:] = salsa20(a ^ b for a, b in izip(tmp, B))237 238    #=================================================================239    # eoc240    #=================================================================241 242#==========================================================================243# eof244#==========================================================================245