[drostie]

The first green tick apparently does not test for username existence, but only an acceptable username format.

I think there may be interactive attack models against logins where you separately report "this user does not exist" from "the password was not correct" -- somewhere in the back of my head is a "general rule" that you should just report "login failed" in both cases. However I do not recall the details. It might be worth contacting someone who has worked on real-world implementations of the Secure Remote Password protocol to know what exactly the threat model here would be. (I'm choosing SRP only because I know that I've seen SRP implementations generating deterministic 'fake keys' for users they do not recognize, since SRP requires a user-conditioned response from the very start of the protocol.)

On the other hand, you could probably create a system which allowed interactive password checking without revealing the password and without allowing for easy brute force attacks. The idea would be to combine a slow one-way memory-hard function f (like scrypt) and a zero-knowledge login system like SRP.

The idea would be that I would send you all of the detail needed for a full key negotiation except for the verifier V that you're supposed to finally get -- i.e. the quantity in the zero-knowledge proof where you go "and if that equals V then I accept the login." Instead I'd send you f(V), so that I am not revealing my hidden data, and so that it takes you, say, 100ms to try any password -- providing a sort of instant feedback for 'normal' users while suitably strengthening them against actual brute-forcing.