How to reduce attempts  Gehe zur Blinded by the light Challenge

I guess that I have to bruteforce the random generated MD5, since I only can get a true or false out of the query (...right?). But the lowest number of attempts I needed for trying every character expected in the MD5 was about 220. So how can I bruteforce more efficiently, or is there a better way to solving this aside from bruteforcing?

Of course there is a better way, as the sequel (Blinded by the lighter) requires only 32 queries.

However you are on a good track, and 128 queries is exactly the number of bits in md5, so 128 true/false queries will work.