Q:

Two factor brute force protection

If I implement two factor authentication using TOTP, I (obviously) have to protect against simple brute force attacks of the TOTP value.
If I ask for the TOTP value after successful password login, the attacker already knows the valid password. Since the default length for TOTP value is 6 digits, it's easy to brute force.
Possible solutions:

Block user account: Disadvantage of blocking a legitimate user with no way of unblocking.
Block IP: Might work, but might be bypassed by leveraging a botnet. Should block more than a single IP for IPv6.

Solutions that do not work:

Block current session: Doesn't work, because the attacker knows the password and can just open another session. 

How can a brute force protection be implemented so it doesn't lock out the legitimate user, but still blocks attacks as good as possible?

A:

The thing about brute forcing a TOTP token is that you have to guess right at the right time.  So, if you don't want to lock a user out after x failed attempts (which is common practice) you can slow failed attempts down to the point where the odds of getting the TOTP right are statistically insignificant.
For example: 6 digit TOTP token has 1,000,000 possibilities.  But the correct key changes every 30 seconds (in the standard implementation of TOTP) so window of success is not how long it takes to exhaust the entire token space, but how many tokens the attacker can get through in a given period divided by the tokenspace, and its still only a chance at success.  Make it impossible to get through the token space in 30 seconds and you reduce the attack to a gamble.
Example: the attacker gets one guess per second.  They can only get through 30 guesses of any given token so the odds of success are basically random.  Using the Bernoulli process of random variables (chance of failure times number of guesses), 24 hours of attacking this way (86,400 guesses) yields only an 8.2% probability of success. At 10 days, it rises to 57%.  So, simply convince your user to change their password, or find some other way to block the attacker (by IP, etc) before that percentage gets very high.

