Finding all numbers that reach a given sum

Little bit of background. I'm doing an audit and trying to crack user passwords. I'm pretty new to hashcat, so after exhausting the usual "take rockyou.txt and run it through every rule" I started looking for more creative ways to make passwords.

One thing I see is combinator attacks. You take dictionary A and dictionary B and you append B onto A line by line in every possible way. Hashcats wiki gives a good example.

I wanted to refine that a bit though. I know approximately what length the user passwords tend to fall (thanks pipal). So I used hashcat-utils "splitlen" to break a giant dictionary up by length. Now, if I know that my users tend towards 10 character passwords, I can combine my 8 length dictionary with my 2 length dictionary. Will I get results? Don't know yet.. 3 hits so far with an hour and a half of work. Not too bad considering I removed all the easy ones already.

Here's where a bit of scripting came in handy. I wanted to know every combination I could use to reach a certain total. For example, if I wanted 15 I could combine 10 and 5, or 12 and 3, etc. I'm much too lazy to do this by hand (yes, I know I could iterate up and down) but I found a nice little python script on Stack Overflow that does exactly what I want.

My single contribution was an additional if statement so that I would only get back arrays with length 2. In other words, I wouldn't get back 10+2+3.

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        if len(partial) == 2:
            print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 

if __name__ == "__main__":
sum([1, 14])=15
sum([2, 13])=15
sum([3, 12])=15
sum([4, 11])=15
sum([5, 10])=15
sum([6, 9])=15
sum([7, 8])=15

If you use this combinator attack method, let me know if you have good results. Don't forget every array listed above can be reversed (1,14 and 14,1) and of course if you're using an even number like 16 you will also be able to use your length 8 dictionary twice. That array won't show up though since 8 only appears once in our numbers array.

Queue up all the combinations in a bash script and start the scrip!



Infosec analyst, lover of passwords, and owner of a giant goofy puppy.

Read More
Finding all numbers that reach a given sum
Share this