Maybe when 1 host is looking for the ones which have a specific secret, the protocol should systematically wait at least 1 or 2 seconds before answering to subsequent requests from the same host/IP (without distinction if it's the same or a different key), so that a brute force attack would be impossible to do without controlling all IPs of the world? It would make parts of the protocol slower, but it would greatly enhance security at a very low cost... Or maybe the use of some kind of 2-step key part exchange, with at least 1 or 2 seconds between steps originating from one host? Generally, adding some delay is a very good approach against brute force attacks and thus against guessing keys...
