Alias blacklist to prevent PIN brute-forcing by limiting the number of PIN failures

[fmarier]

As discussed in #218, we need a strategy to prevent/deter attackers wanting to crack the PIN codes used to link an alias with a real Yahoo account.

Here's a proposal based on a discussion with @ozten and @warner, as well as a similar blacklist implemented by @lloyd in the Mozilla IdP:

• When a user types in the wrong PIN, an entry is added to an in-memory data structure: (alias, counter) .
• If that alias was already in the data structure, the counter is incremented.
• Once that count reaches 5, the backend will refuse to verify PINs for that alias.
• Records in that data structure expire after 10 minutes (just like PIN codes).
• The in-memory data structure is specific to each web head, it's not shared memcache-style.
• The data structure has a fixed capacity (e.g. 1M records) and when it's full, the backend on that webhead will refuse to verify PINs for any alias until expired entries have made some room.

The implication of that last point is that if we are under attack (i.e. we get hundreds of thousands of PIN failures in a single 10-minute window), then the PIN verifier will automatically stop working (but not the rest of BigTent). The idea is that entries in the blacklist should never be evicted until their 10 minutes are up in order to enforce a maximum number of attempts per PIN.

For users, what this means is that:

• Users have 10 minutes to type their PIN in.
• Users are allowed to mistype a given PIN 5 times before it's invalidated.
• Users that have invalidated a PIN will need to wait 10 minutes before they can get another PIN for that same alias.

[ozten]

@lloyd - please review and sign off on this design.

[ozten]

@fmarier thanks for putting this together.

Why is the capacity for PIN check counters set to 1M? The reason I set it to 1M in my LRU proposal was so that we'd never hit that upper bound and it would periodically need to be pushed higher, as our usage grows.

[warner]

Sounds pretty good to me.

Let's see, that gives an attacker a guess rate of 5*num_webheads/10min, so maybe 5 guess/min (for 10 webheads)? So 7200 guesses per day, so a 6-digit PIN (with no reactive defenses) gives a single-target attacker a 50% chance of success after about two months.

In addition to preventing an out-of-memory crash (or swap-thrash, which is nearly as bad), the 1M limit could also protect against a multi-target attacker, who has a big list of email addresses and doesn't really care which one he manages to get. However, one million entries is too big for this (with a 6-digit PIN). A multi-target attacker going after just one thousand addresses can expect to break into about 7.2 per day (making 83 guesses per second, so 8.3 gps per webhead) without risking a table-overflow lockout. A 1M table maximum would let them steal about 7200 addresses per day (at 8.3k gps/webhead, which is a lot more traffic but probably still within the capacity of our hardware).

If we start with a 6-digit PIN, I'd still like to see some reactive defenses. I'd add a counter of total failed guesses (per webhead, not per-alias), if it goes above 1000 then make the PIN one digit longer (and reset the counter, and maybe multiply the threshold by 10). Once per day, reset the counter and reset the PIN length back to the default. That'll limit a multi-target attacker to roughly 1000 "easy" guesses per day (per webhead), giving them an average of one success every three months (across 10 webheads) no matter how many addresses they target.

There's an inevitable tradeoff between preventing PIN-guessing and allowing a DoS attack. A reactive defense prevents multi-target attacks at the cost of allowing the DoS attacker to force a longer PIN on legitimate users. There's still a risk of table-overflow lockouts, but if we don't rely on the table limit for multi-target attacks, we can use a much larger table.

There's still an attack where they first get PINs for a million targets, then make 5 guesses per webhead on each in a 10-minute validity window (167 gps/webhead), yielding them 50 accounts for a 6-digit PIN. This is limited by the table size, but not affected by the reactive defense (since they obtain all the PIN requests before submitting the first guess). OTOH, they'd have to complete a million create-a-PIN requests in that same window, which involves sending email, and we might be protected because our servers can't process those requests fast enough.

(oh, and we might be protected by other slowdowns: in particular, to get a PIN request you have to present some sort of OAuth/OpenID token, and we have to validate it by talking to some server, and the attacker may not be able to acquire/validate those fast enough to mount the kinds of attacks listed here. I don't yet understand the flow well enough to say whether this will protect us or not).

[fmarier]

@ozten The capacity of 1M was just an example. It should be as high as we can afford so that we never hit it (unless we're under heavy attack). If we can make it 100M, then great :)

@warner Isn't the multi-target attack also a problem with the current fallback IdP? While I think we should work towards protecting against that, we shouldn't block on it for this Big Tent fix if the PIN code is not any worse than the fallback.

[warner]

@fmarier Probably, yeah, I haven't looked at that code for a while.

[ozten]

Please be explicit if there is a change to the requirements other than the summary. Sounds like there isn't yet.

[ozten]

I think this is still the current acceptable plan.

Pull request ready for review, assigned to @fmarier : https://github.com/mozilla/browserid-bigtent/pull/237

[edwindotcom]

@ozten I believe this is fixed, closing - reopen if I'm wrong