Circumventing disadvantage of IP-based account lockout

Question

So we're trying to prevent brute-force attacks on our web server login page--currently we just do IP-based locking if x failed attempts from IP address Y occur over z time period. After a security review we realized that we might be locking out users sharing an IP, which the OWASP article on the subject confirmed is a legitimate issue. We are now considering changing the algorithm to restrict by username as well as IP address- is this a bad idea? I'm not terribly worried about an attacker on the same IP as the victim intentionally trying to lock out the victim's account, but perhaps that is easier than I realize?

psuedocode for new algorithm:

username = x
ipAddress = y
// if we're here, user has entered bad credentials

if( tooManyAttempts( x, y ) )
   lockAccount
else 
   ...
end if

def tooManyAttempts (username, ipAddress)
   attemptsPerTime = getAttempts ( username, ipAddress )
   if( attemptsPerTime > attemptsAllowedPerTime )
      return true
   else 
      return false
   end if
end

def getAttempts ( aUsername, anIpAddress)
   query database for attempts records
      where value in column username  equals aUsername AND
            value in column ipAddress equals anIpAddress
   return number of records
end

Answer 1

Any system that increases the amount of time for additional attempts will thwart brute-force attacks on your service. CAPTCHA as mentioned previously is a strong method for doing this, providing for a 5-10 second timeout period between attempts after say, the third attempt and escalating the timeout period by following some progression can easily thwart any brute force attempt. You can even have it cap at say 5 minutes, and if an attempt comes in within that period merely resets the period even IF it is a valid login. (Checking at most 12 passwords an hour for example makes brute forcing pretty much impossible.)

IP-based bans would be ineffective against a large-scale attack, like against a botnet perhaps, unless the IP-ban was account-specific.

As an idea, cookies could be used to thwart some attackers, if cookie usage is required you could generate a random hash of some sort that authenticates their /location/ as valid and any attempt that doesn't come from that location is subject to a CAPTCHA process or 2FA. (Successful authentication could allow them to add the cookie.) Following this method, you could IP ban an entire segment from authenticating for X minutes or hours UNLESS they have the cookie. Which would only result in a victim being banned if the attacker was utilizing their machine, OR stole the cookie.

Fun times.

Answer 2

Just require a CAPTCHA after X attempts from IP address Y and/or username U, that way nobody gets locked out while the attack is still prevented. A reasonable choice might be to cut out the IP address and just focus on account-specific login attempts (maybe three strikes = CAPTCHA necessary). That should mitigate any significant concerns of brute force for a web-based service since three attempts equates to virtually nothing in that context. For issues of someone who has a pretty good idea of what the password might be for U (roommates and the like), consider offering two-factor authentication (2FA). Would recommend e-mailing the user any time it is necessary to utilize a CAPTCHA under that scheme, letting them know that something is wrong while offering to reset passwords at the same time lest the attempts were in fact legitimate.