What's the best way to prevent a dictionary attack? I've thought up several implementations but they all seem to have some flaw in them:

1. Lock out a user after X failed login attempts. Problem: easy to turn into a denial of service attack, locking out many users in a short amount of time.
2. Incrementally increase response time per failed login attempt on a username. Problem: dictionary attacks might use the same password but different usernames.
3. Incrementally increase response time per failed login attempt from an IP address. Problem: easy to get around by spoofing IP address.
4. Incrementally increase response time per failed login attempt within a session. Problem: easy to get around by creating a dictionary attack that fires up a new session on each attempt.