md4.py

#    md4.py implements md4 hash class for Python
#    Version 1.0
#    Copyright (C) 2001-2002  Dmitry Rozmanov
#
#    based on md4.c from "the Python Cryptography Toolkit, version 1.0.0
#    Copyright (C) 1995, A.M. Kuchling"
#
#    This library is free software; you can redistribute it and/or
#    modify it under the terms of the GNU Lesser General Public
#    License as published by the Free Software Foundation; either
#    version 2.1 of the License, or (at your option) any later version.
#
#    This library is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public
#    License along with this library; if not, write to the Free Software
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#    e-mail: dima@xenon.spb.ru
#
#====================================================================
#
#
#    This version has been modified from the original. It includes U32 
#    and replaces some unused variables with _ to suppress warnings in
#    Eclipse. 
#
#====================================================================

# MD4 validation data

md4_test= [
      ('', 0x31d6cfe0d16ae931b73c59d7e0c089c0L),
      ("a",   0xbde52cb31de33e46245e05fbdbd6fb24L),
      ("abc",   0xa448017aaf21d8525fc10ae87aa6729dL),
      ("message digest",   0xd9130a8164549fe818874806e1c7014bL),
      ("abcdefghijklmnopqrstuvwxyz",   0xd79e1c308aa5bbcdeea8ed63df412da9L),
      ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
       0x043f8582f241db351ce627e153e7f0e4L),
      ("12345678901234567890123456789012345678901234567890123456789012345678901234567890",
      0xe33b4ddc9c38f2199c3e7b164fcc0536L),
     ]


def md4_hash(data, A=0x67452301L, B=0xefcdab89L, C=0x98badcfeL, D=0x10325476L, offset=0):
    h = MD4(A, B, C, D)
    h.update(data, offset)
    return h.digest()

def hexdigest(digest):
    return ''.join('%02x' % ord(i) for i in digest)

class MD4:
    A = None
    B = None
    C = None
    D = None
    count, len1, len2 = None, None, None
    buf = []

    #-----------------------------------------------------
    def __init__(self, A=0x67452301L, B=0xefcdab89L, C=0x98badcfeL, D=0x10325476L):
        self.A = U32(A)
        self.B = U32(B)
        self.C = U32(C)
        self.D = U32(D)
        self.count, self.len1, self.len2 = U32(0L), U32(0L), U32(0L)
        self.buf = [0x00] * 64

    #-----------------------------------------------------
    def __repr__(self):
        r = 'A = %s, \nB = %s, \nC = %s, \nD = %s.\n' % (self.A.__repr__(), self.B.__repr__(), self.C.__repr__(), self.D.__repr__())
        r = r + 'count = %s, \nlen1 = %s, \nlen2 = %s.\n' % (self.count.__repr__(), self.len1.__repr__(), self.len2.__repr__())
        for i in range(4):
            for j in range(16):
                r = r + '%4s ' % hex(self.buf[i+j])
            r = r + '\n'

        return r
    #-----------------------------------------------------
    def make_copy(self):

        dest = new()

        dest.len1 = self.len1
        dest.len2 = self.len2
        dest.A = self.A
        dest.B = self.B
        dest.C = self.C
        dest.D = self.D
        dest.count = self.count
        for i in range(self.count):
            dest.buf[i] = self.buf[i]

        return dest

    #-----------------------------------------------------
    def update(self, str, offset=0):

        buf = []
        for i in str: buf.append(ord(i))
        ilen = U32(len(buf))

        # check if the first length is out of range
        # as the length is measured in bits then multiplay it by 8
        if (long(self.len1 + (ilen << 3)) < long(self.len1)):
            self.len2 = self.len2 + U32(1)

        self.len1 = self.len1 + ((ilen + offset) << 3)
        self.len2 = self.len2 + ((ilen + offset) >> 29)

        L = U32(0)
        bufpos = 0
        while (long(ilen) > 0):
            if (64 - long(self.count)) < long(ilen): L = U32(64 - long(self.count))
            else: L = ilen
            for i in range(int(L)): self.buf[i + int(self.count)] = buf[i + bufpos]
            self.count = self.count + L
            ilen = ilen - L
            bufpos = bufpos + int(L)

            if (long(self.count) == 64L):
                self.count = U32(0L)
                X = []
                i = 0
                for _ in range(16):
                    X.append(U32(self.buf[i]) + (U32(self.buf[i+1]) << 8)  + \
                    (U32(self.buf[i+2]) << 16) + (U32(self.buf[i+3]) << 24))
                    i = i + 4

                A = self.A
                B = self.B
                C = self.C
                D = self.D

                A = f1(A,B,C,D, 0, 3, X)
                D = f1(D,A,B,C, 1, 7, X)
                C = f1(C,D,A,B, 2,11, X)
                B = f1(B,C,D,A, 3,19, X)
                A = f1(A,B,C,D, 4, 3, X)
                D = f1(D,A,B,C, 5, 7, X)
                C = f1(C,D,A,B, 6,11, X)
                B = f1(B,C,D,A, 7,19, X)
                A = f1(A,B,C,D, 8, 3, X)
                D = f1(D,A,B,C, 9, 7, X)
                C = f1(C,D,A,B,10,11, X)
                B = f1(B,C,D,A,11,19, X)
                A = f1(A,B,C,D,12, 3, X)
                D = f1(D,A,B,C,13, 7, X)
                C = f1(C,D,A,B,14,11, X)
                B = f1(B,C,D,A,15,19, X)

                A = f2(A,B,C,D, 0, 3, X)
                D = f2(D,A,B,C, 4, 5, X)
                C = f2(C,D,A,B, 8, 9, X)
                B = f2(B,C,D,A,12,13, X)
                A = f2(A,B,C,D, 1, 3, X)
                D = f2(D,A,B,C, 5, 5, X)
                C = f2(C,D,A,B, 9, 9, X)
                B = f2(B,C,D,A,13,13, X)
                A = f2(A,B,C,D, 2, 3, X)
                D = f2(D,A,B,C, 6, 5, X)
                C = f2(C,D,A,B,10, 9, X)
                B = f2(B,C,D,A,14,13, X)
                A = f2(A,B,C,D, 3, 3, X)
                D = f2(D,A,B,C, 7, 5, X)
                C = f2(C,D,A,B,11, 9, X)
                B = f2(B,C,D,A,15,13, X)

                A = f3(A,B,C,D, 0, 3, X)
                D = f3(D,A,B,C, 8, 9, X)
                C = f3(C,D,A,B, 4,11, X)
                B = f3(B,C,D,A,12,15, X)
                A = f3(A,B,C,D, 2, 3, X)
                D = f3(D,A,B,C,10, 9, X)
                C = f3(C,D,A,B, 6,11, X)
                B = f3(B,C,D,A,14,15, X)
                A = f3(A,B,C,D, 1, 3, X)
                D = f3(D,A,B,C, 9, 9, X)
                C = f3(C,D,A,B, 5,11, X)
                B = f3(B,C,D,A,13,15, X)
                A = f3(A,B,C,D, 3, 3, X)
                D = f3(D,A,B,C,11, 9, X)
                C = f3(C,D,A,B, 7,11, X)
                B = f3(B,C,D,A,15,15, X)

                self.A = self.A + A
                self.B = self.B + B
                self.C = self.C + C
                self.D = self.D + D

    #-----------------------------------------------------
    def digest(self):

        res = [0x00] * 16
        s = [0x00] * 8
        padding = [0x00] * 64
        padding[0] = 0x80
        padlen, _, _ = U32(0), U32(0), U32(0)

        temp = self.make_copy()

        oldlen1 = temp.len1
        oldlen2 = temp.len2
        if (56 <= long(self.count)): padlen = U32(56 - long(self.count) + 64)
        else: padlen = U32(56 - long(self.count))

        temp.update(int_array2str(padding[:int(padlen)]))

        s[0]= (oldlen1)        & U32(0xFF)
        s[1]=((oldlen1) >>  8) & U32(0xFF)
        s[2]=((oldlen1) >> 16) & U32(0xFF)
        s[3]=((oldlen1) >> 24) & U32(0xFF)
        s[4]= (oldlen2)        & U32(0xFF)
        s[5]=((oldlen2) >>  8) & U32(0xFF)
        s[6]=((oldlen2) >> 16) & U32(0xFF)
        s[7]=((oldlen2) >> 24) & U32(0xFF)
        temp.update(int_array2str(s))

        res[ 0]= temp.A        & U32(0xFF)
        res[ 1]=(temp.A >>  8) & U32(0xFF)
        res[ 2]=(temp.A >> 16) & U32(0xFF)
        res[ 3]=(temp.A >> 24) & U32(0xFF)
        res[ 4]= temp.B        & U32(0xFF)
        res[ 5]=(temp.B >>  8) & U32(0xFF)
        res[ 6]=(temp.B >> 16) & U32(0xFF)
        res[ 7]=(temp.B >> 24) & U32(0xFF)
        res[ 8]= temp.C        & U32(0xFF)
        res[ 9]=(temp.C >>  8) & U32(0xFF)
        res[10]=(temp.C >> 16) & U32(0xFF)
        res[11]=(temp.C >> 24) & U32(0xFF)
        res[12]= temp.D        & U32(0xFF)
        res[13]=(temp.D >>  8) & U32(0xFF)
        res[14]=(temp.D >> 16) & U32(0xFF)
        res[15]=(temp.D >> 24) & U32(0xFF)

        return int_array2str(res)

#====================================================================
# helpers
def F(x, y, z): return (((x) & (y)) | ((~x) & (z)))
def G(x, y, z): return (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
def H(x, y, z): return ((x) ^ (y) ^ (z))

def ROL(x, n): return (((x) << n) | ((x) >> (32-n)))

def f1(a, b, c, d, k, s, X): return ROL(a + F(b, c, d) + X[k], s)
def f2(a, b, c, d, k, s, X): return ROL(a + G(b, c, d) + X[k] + U32(0x5a827999L), s)
def f3(a, b, c, d, k, s, X): return ROL(a + H(b, c, d) + X[k] + U32(0x6ed9eba1L), s)

#--------------------------------------------------------------------
# helper function
def int_array2str(array):
        str = ''
        for i in array:
            str = str + chr(i)
        return str

#--------------------------------------------------------------------
# To be able to use md4.new() instead of md4.MD4()
new = MD4



C = 0x1000000000L

#--------------------------------------------------------------------
def norm(n):
    return n & 0xFFFFFFFFL

#====================================================================
class U32:
    v = 0L

    #--------------------------------------------------------------------
    def __init__(self, value = 0):
        self.v = C + norm(abs(long(value)))

    #--------------------------------------------------------------------
    def set(self, value = 0):
        self.v = C + norm(abs(long(value)))

    #--------------------------------------------------------------------
    def __repr__(self):
        return hex(norm(self.v))

    #--------------------------------------------------------------------
    def __long__(self): return long(norm(self.v))

    #--------------------------------------------------------------------
    def __int__(self): return int(norm(self.v))

    #--------------------------------------------------------------------
    def __chr__(self): return chr(norm(self.v))

    #--------------------------------------------------------------------
    def __add__(self, b):
        r = U32()
        b = U32(b)
        r.v = C + norm(self.v + b.v)
        return r

    #--------------------------------------------------------------------
    def __sub__(self, b):
        r = U32()
        if self.v < b.v:
            r.v = C + norm(0x100000000L - (b.v - self.v))
        else: r.v = C + norm(self.v - b.v)
        return r

    #--------------------------------------------------------------------
    def __mul__(self, b):
        r = U32()
        r.v = C + norm(self.v * b.v)
        return r

    #--------------------------------------------------------------------
    def __div__(self, b):
        r = U32()
        r.v = C + (norm(self.v) / norm(b.v))
        return r

    #--------------------------------------------------------------------
    def __mod__(self, b):
        r = U32()
        r.v = C + (norm(self.v) % norm(b.v))
        return r

    #--------------------------------------------------------------------
    def __neg__(self): return U32(self.v)

    #--------------------------------------------------------------------
    def __pos__(self): return U32(self.v)

    #--------------------------------------------------------------------
    def __abs__(self): return U32(self.v)

    #--------------------------------------------------------------------
    def __invert__(self):
        r = U32()
        r.v = C + norm(~self.v)
        return r

    #--------------------------------------------------------------------
    def __lshift__(self, b):
        r = U32()
        r.v = C + norm(self.v << b)
        return r

    #--------------------------------------------------------------------
    def __rshift__(self, b):
        r = U32()
        r.v = C + (norm(self.v) >> b)
        return r

    #--------------------------------------------------------------------
    def __and__(self, b):
        r = U32()
        r.v = C + norm(self.v & b.v)
        return r

    #--------------------------------------------------------------------
    def __or__(self, b):
        r = U32()
        r.v = C + norm(self.v | b.v)
        return r

    #--------------------------------------------------------------------
    def __xor__(self, b):
        r = U32()
        r.v = C + norm(self.v ^ b.v)
        return r

    #--------------------------------------------------------------------
    def __not__(self):
        return U32(not norm(self.v))

    #--------------------------------------------------------------------
    def truth(self):
        return norm(self.v)

    #--------------------------------------------------------------------
    def __cmp__(self, b):
        if norm(self.v) > norm(b.v): return 1
        elif norm(self.v) < norm(b.v): return -1
        else: return 0

    #--------------------------------------------------------------------
    def __nonzero__(self):
        return norm(self.v)