Reduction function in Rainbow tables implementation

Question

I'm working on an implementation of Rainbow tables as part of a project. I understand the main principles behind it had have a working solution. Unfortunately the reduction function portion of my project is the slowest part I'm hoping that someone might be able to point out places that I can speed it up.

The program itself is simple enough, I read in a set of chains from a file into a NumPy array and then using a binary search see if an index is present in the list. A new index is created each binary search using the reduction function. It seems that the reduction function is the largest bottleneck in my code currently. I've attached my main function and the functions below it to preserve formatting.

The reduction function in this case is chainWalkFromPositionToEnd(). Has anyone any suggestions on how to speed this up?

if __name__ == "__main__":

with open("C:\RainbowTables\md5_loweralpha-numeric-space#1-8_0_10000x67108864_00.rt", 'rb') as file:

    dt = np.dtype([('startPoint', '<u8' ), ('endPoint', '<u8')])

    #Parse table info from table name
    rtable = RainbowChainInfo("md5_loweralpha-numeric-space#1-8_0_10000x67108864_distrrtgen[p][i]_00.rt", "/Users/scottomalley/RainbowTables/timeTest/")

    #Calculate the keyspace
    keyspace = getKeySpace(rtable.minPasswordLength, rtable.maxPasswordLength, len(charset))

    #Convert Hash to Binary for use as charset index
    index = binascii.a2b_hex("0cc175b9c0f1b6a831c399e269772661")

    #Read the chains from the file - Each chain is 16 bytes containing an 8 byte startPoint and End point"""
    rainbowChains = np.fromfile(file, dtype=dt)

    for x in reversed(range(0, rtable.chainLength -1 , 1)):
        #Reduce the index using the reduction function from chain position x till end of the chain"""
        reductionIndex = chainWalkFromPositionToEnd(index, x, rtable, keyspace)

        potenditalFound = np.searchsorted(rainbowChains['endPoint'],reductionIndex, side="left")
        if(potenditalFound != len(rainbowChains)):
            print "Do something with this array location"

        #potenditalFound = binarySearch(rainbowChains, index)"""
        #if(potenditalFound != -1)"""

---

    charset = "abcdefghijklmnopqrstuvwxyz0123456789 "

# Take an index, check if it's in the the second to last 
# position if not reduce until at the end of the chain return the last index
def chainWalkFromPositionToEnd(hash, position, rtable, keyspace):

    if position == (rtable.chainLength - 2):
        return hashToIndex(hash, position, rtable, keyspace)
    else:
        index = hashToIndex(hash, position, rtable, keyspace)
        position += 1
        while position <= rtable.chainLength -2:
            plain = indexToPlain(index)
            hash = plainToHash(plain)
            index = hashToIndex(hash,position, rtable,keyspace)

            position += 1
    return index



#Convert a long/int to it's character representation in the char set
def indexToPlain(index):
    return get_str(index)

#Convery a plaintext to MD5#
def plainToHash(plain):
    return get_md5_as_bytes(plain)

#Convert Hash to an index, Done by taking the first 8 Bytes of the hash,
#adding the tables index and chain position and modulusing the result by the keyspace
def hashToIndex(hash, chainPos, table, keyspace):
    return (struct.unpack("<Q", hash[0:8])[0] + table.tableIndex + chainPos) % keyspace

#Calculate the number of potential passwords in the keyspace
def getKeySpace(minPassLen, maxPassLen, charsetLen):
    keyspace = 0
    for x in range(minPassLen, maxPassLen + 1, 1):
        keyspace += pow(charsetLen,x)
    return keyspace

def get_md5_as_bytes(data):
    m = hashlib.md5()
    m.update(data)
    return m.digest()


#Take long/integer and convert it to a plaintext using the charset
def get_str(a):
    base = len(charset)
    if a < base:
        return charset[a]
    return get_str(int((a - a % base)/base - 1) ) + get_str(a % base)

#Binary Search the array
def binarySearch(rainbowChains, index):
    lowPoint = 0
    highpoint = len(rainbowChains) - 1

    while (lowPoint <= highpoint):
        midPoint = int((lowPoint + highpoint) / 2)

        if(index == rainbowChains[midPoint]['endPoint']):
            return midPoint

        elif(index < rainbowChains[midPoint]['endPoint']):
            highpoint = midPoint - 1

        else:
            lowPoint = midPoint + 1

    return -1

---

The results of CCrofile where the start position is 0 and the chain length is 10000:

378829 function calls (239407 primitive calls) in 0.270 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.270    0.270 <string>:1(<module>)
     9998    0.014    0.000    0.046    0.000 numpytest.py:108(get_md5_as_bytes)
149420/9998    0.160    0.000    0.175    0.000 numpytest.py:115(get_str)
        1    0.017    0.017    0.270    0.270 numpytest.py:71(chainWalkFromPositionToEnd)
     9998    0.005    0.000    0.180    0.000 numpytest.py:89(indexToPlain)
     9998    0.008    0.000    0.054    0.000 numpytest.py:93(plainToHash)
     9999    0.016    0.000    0.020    0.000 numpytest.py:98(hashToIndex)
     9998    0.009    0.000    0.009    0.000 {_hashlib.openssl_md5}
     9999    0.004    0.000    0.004    0.000 {_struct.unpack}
   149420    0.015    0.000    0.015    0.000 {len}
     9998    0.011    0.000    0.011    0.000 {method 'digest' of '_hashlib.HASH' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     9998    0.012    0.000    0.012    0.000 {method 'update' of '_hashlib.HASH' objects}

Answer 1

A few suggestions (not really a complete answer):

• Do not reinvent the wheel. Use the bisect module from the standard library to perform a binary search.

• Use a hash sign (#) to start comments. When triple quotes are used, what happens is that a string object is created and immediately dropped for garbage collection. More style-related comment, but it will improve a tiny bit the performance.

• You can still use docstrings, but note they are written after the method signature (the line with def), not before.

Answer 2

• Python code runs faster when it is inside a function. The typical thing is to define a main() function, and then call it inside of if __name__ == "__main__".

• Don't make function aliases like:

  def indexToPlain(index):
      return get_str(index)
  

  This is bad for performance because adds another layer of overhead, specially in such a small function that gets called so many times. If you really need an alias, use:

  indexToPlain = get_str
  

  But I don't condone it. It just makes debugging and understanding the code much harder.

• It seems one of your bottlenecks is get_str. Your profiling information is not very detailed, so I am just guessing here, but I am running it on my box, and 8% of the time is being spent in computing a % base, and you are doing it twice. Another 4% of the time is spent computing the length of the charset, on every call. (Everything is very fast, so the timings are not quite reliable, in fact cProfile and kernprof report quite different numbers). Last, but not least, when you call get_str(a % base), you know that the argument is going to be smaller than base, so you can avoid the call alltogether. Here is my code:

  charset = "abcdefghijklmnopqrstuvwxyz0123456789 " base = len(charset)

  def get_str(a):
      if a < base:
          return charset[a]
  
      i2 = a % base
      i1 = int((a - i2) / base - 1)
  
      return get_str(i1) + charset[i2]
  

  I am getting something between a 10 and a 25% increase in performance.

On style:

• Python functions use lowercase_with_underscores convention, CamelCase is reserved for classes declaration. Also, your names are horribly long.
• Don't use file as a variable, it is a builtin.

If performance is really an issue, you should consider porting your code to Cython, you can get hundreds or thousands times faster. The problem is that it is difficult to set up a Windows environment (it is trivial in Linux, though). I believe Continuum's Conda can do it pretty easily for you, but I have never tried.