It still helps though, let's assume they're using MD5 without salt, if the attacker has a rainbow table, this leads to a speed up, since the attacker only has guess bit-by-bit instead of trying every possibility.
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.
What you’re talking about is more like a hash table not a rainbow table. If you’re looking for a pre-image for the first 8 bytes of MD5 that would be a table with 2^64 rows * at least 8 bytes or at least 144 exabytes of data.
Using such a table would allow you to select guesses that matched the first n bits of the stored hash and then use timing to try to guess the right choice for the n+1’th bit... up to the first 64 bits. You would then have limited the number of guesses down to just another 2^64 possibilities. So that’s not really a valid approach.
A different approach would be to try to figure out the first ~32 bits of the hash using a much smaller (34GB) table and use that knowledge to screen potential candidate passwords offline.
Again, all this works only as long as there isn’t a salt, and the value you are trying to discover is a guessable password and not a randomly generated key.
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.