similar-hash.py

#!/usr/bin/python

import hashlib

original = 'Install the program the user expects and exit.'.encode('ascii')
target   = 'Install a backdoor and exit. '.encode('ascii')

def get_score(hash1, hash2):
    assert len(hash1) == len(hash2)

    start = 0
    while start < len(hash1) and hash1[start] == hash2[start]:
        start += 1

    end = 0
    while end < len(hash1) and hash1[-end-1] == hash2[-end-1]:
        end += 1

    similar = 0
    for c1, c2 in zip(hash1, hash2):
        if (c1 <= '9') == (c2 <= '9'):
            similar += 1

    score = min(start, end) + (start + end) / 4.0 + similar / 10.0

    return score

original_hash = hashlib.md5(original).hexdigest()

space = len(original) - len(target)

nonce = 0
best_score = -1

while True:
    candidate = target + str(nonce).rjust(space, '0').encode('ascii')
    candidate_hash = hashlib.md5(candidate).hexdigest()

    score = get_score(original_hash, candidate_hash)
    if score > best_score:
        best_score = score
        print('{0}: {1}'.format(original, original_hash))
        print('{0}: {1}'.format(candidate, candidate_hash))

    nonce += 1