0
$\begingroup$

Interested in password cracking, I thought of a concept for lookup tables that can tell if a hash can be created using a dictionary in about O(log n) time.

A simple overview of the idea is a follows: Store the first x bytes of every hash created with the word list, using unique values, sorted. When encountering a new hash, one can take the first few bytes and perform a binary search. If the bytes are not in the file, the hash can't be created using the word list.

Questions:

  1. What do you think of this idea?
  2. Does this method already exist?
  3. Are there other research fields that might benefit from this, besides password cracking?

For those who need it – a POC and further explanation is available at my related GitHub repo.
Here’s a copy of the code:

import os
import struct
class crackTree(object):
  """ class that builds a negative lookup tree for hashes for a wordlist """
  # hashmethod must be a method from Python's hashlib
  def __init__(self, hashMethod, debug = True):
    self.debug = debug
    self.hashMethod = hashMethod
    self.hashBytes = self.hashMethod().digest_size
  def createTable(self, inputFile, outputFile):
    self.printDebug("Creating table for file: " + str(inputFile))
    try:
      self.fileSize = os.path.getsize(inputFile)
      assert self.fileSize > 0
    except:
      self.printDebug("Could not get line count for file\n")
      raise
    self.printDebug("Choosing table size..")
    self.useBytes = self.chooseTableSize(self.fileSize)
    self.printDebug("Starting loading wordlist..")        
    fin = open(inputFile, 'r')
    statusCounter = 0        
    # todo: directly write to file instead of tmp parameter
    tmp = {}
    for word in fin.readlines():
      word = word.strip("\n")
      theHash = self.hashMethod(word).digest()
      theHash = theHash[:self.useBytes]          
      tmp[theHash]=0
    fin.close()
    tmp = list(tmp)
    tmp = [self.packtoInt(i) for i in tmp]
    tmp.sort()
    # todo: auto fix 3 en 4 bytes
    tmp = [struct.pack(">I", i) for i in tmp]
    fout = open(outputFile,'wb')
    for i in tmp:
      fout.write(i)
    fout.close()
    fout = open("fileInfo_"+outputFile,'w')
    fout.write("Hash byte size used: " + str(self.useBytes))
    fout.write("\nHash method used: " + str(self.hashMethod))
    fout.close()
  def printDebug(self, value):
    if self.debug:
      print value
  def calcChanceTotalCollisions(self, n, m):
    '''
      Calculate total estimated collisions of generating n items for m buckets
      See http://stackoverflow.com/questions/9104504/expected-number-of-hash-collisions
    '''
    n = float(n)
    m = float(m)
    return n - m * (1.00-((m-1.00)/m)**n)

  def chooseTableSize(self, lineCount):
    '''
      Choose size for the table
      Must fill all possible space for less than 50% to get less than 50% false positives
    '''
    for useBytes in range(1,self.hashBytes):
      space = 256**useBytes
      estimatedCollisions = self.calcChanceTotalCollisions(lineCount, space)
      estimatedSpaceUsed = lineCount - estimatedCollisions
      # this is also the chance of false positives
      fillPercentage = float(estimatedSpaceUsed) / float(space)
      if fillPercentage > 0.5:
        continue
      self.printDebug("Using " + str(useBytes) + " bytes gives me " + str(space) + " values of space")
      self.printDebug("I estimate " + str(estimatedCollisions) + " collisions")
      self.printDebug("Leaving about " + str(estimatedSpaceUsed) + " values used")
      self.printDebug("This table will be filled by about " + str(fillPercentage))
      return useBytes        
  def packtoInt(self, binary):
    while len(binary)%4!=0:
      binary = '\x00' + str(binary)
    # convert to integer
    unpackSize = len(binary) / 4
    binary = sum(struct.unpack('>'+('I'*unpackSize), binary))
    return binary
  def lookupTable(self, inputFile, value, usedBytes):
    lookupInt = self.packtoInt(value)
    fileSize = os.path.getsize(inputFile)
    devider = (fileSize / usedBytes) / 2
    start = devider
    devider = devider / 2
    fin = open(inputFile,'rb')
    while 1:
      currentPoint = start * usedBytes
      fin.seek(currentPoint)
      test = self.packtoInt(fin.read(usedBytes))
      #print str(test) + " vs " + str(lookupInt)
      if test == lookupInt:
        return True
        break
      if devider == 0:
        if test < lookupInt:
          while test < lookupInt:
            currentPoint += usedBytes
            fin.seek(currentPoint)
            test = self.packtoInt(fin.read(usedBytes))
            if test == lookupInt:
              return True
        if test > lookupInt:
          while test > lookupInt:
            currentPoint -= usedBytes
            fin.seek(currentPoint)
            test = self.packtoInt(fin.read(usedBytes))
            if test == lookupInt:
              return True
        return False
        break
      if test < lookupInt:
        start += devider
      else:
        start -= devider
      devider = devider / 2
    fin.close
from hashlib import md5
from datetime import datetime
lolCracktree = crackTree(md5)
lolCracktree.createTable('rockyou.txt', 'dumprockyou')  # comment out this line once the table has been created
print "Performing two lookups"
testword = "test"       # test is a word in the dictionary
lookupHash = md5(testword).digest()
lookupValue = lookupHash[:4]
print lolCracktree.lookupTable('dumprockyou', lookupValue, 4) # will output True
testword = "testWordNotInDict"      # testWordNotInDict is a word not in the dictionary
lookupHash = md5(testword).digest()
lookupValue = lookupHash[:4]
print lolCracktree.lookupTable('dumprockyou', lookupValue, 4) # will output False
$\endgroup$
0
$\begingroup$

Actually, the field of using data structures to do lookups is a very well studied field.

For the specific problem you are looking at ('doing a fast check to see if this hash appear somewhere in this list'), there are some cleverer things you can do:

  • You can use a hash table; using buckets and relying that doing a file access of 1kbyte (consecutive) is about as cheap as a few bytes, you can do it with 1 access per password.

  • If you feel the need to use a sorted list, an interpolation search would be the more efficient; if we assume the indicies are random, this does an expected $O(\log \log N)$ accesses (and, because what we are searching on is cryptographical hash values, we get this randomness requirement).

  • If you don't mind being right most of the time (and that very well might be acceptable, if this is used as a filter before a more expensive Rainbow-Table lookup), Bloom Filters are an obvious option.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.