[tialaramex]

Right, what you've got is an oracle that will tell you how many prefix bits of MD5(password) were correct. I suspect bytes is more realistic than bits but the same principle.

Rainbow tables don't seem like a very applicable technology for this. I think you'd want to pre-process a dictionary of passwords you want to be able to guess (either from known passwords or just obeying some rule) so that you can group and order them by MD5 prefix.

Using the oracle lets you narrow down 50% at a time, so if you've got a dictionary of 1 billion passwords, after 30 iterations you've either rejected all the possibilities or found a correct password.

NB This makes no difference against a strong random password, since a hypothetical dictionary of such passwords is far too large, it only impacts ordinary human passwords that you could brute force if you had the hash.