Add brute force prevention

[ghost]

12 days = 12 * 24 * 60 * 60 seconds = 1 036 800 > 1 000 000.
1 try / sec will break code in 12 days, but really in 6 days(there is some math magic, believe me :) )
If TOTP is one factor it's fatal

Lets increase it to 20 years (10 really). If we limit speed to 1 try / 600 sec it will cause problem to user.
So first 50 attempts time waits
0 min x 10 tries
0,5 min x 10 tries
1 min x 10 tries
2 min x 10 tries
5 min x 10 tries
and then 10 min.

Another way is to require double code enter after 50 tries and limit timeout to 30 seconds.
In this case user will wait only 1,5 mins but combinations count will be 1 000 000 000 000, thats more than anyone can brute force :)

[ghost]

Good idea is to make it configurable to fit user's needs to balance between comfort and security

[yeojz]

How would that fit into the library?
Do you mean to include a utility function?

[ghost]

Yes, suggest to include this functionality as utility. It's important, because connected with main part of library and hard to implement correctly by new to cryptography users.

This algorhytm isn't a part of TOTP RFC, it's self-engeneered. So if you found RFC or another standard it will be better to implement standard

[ghost]

See 7.3 RFC 4226
Another option would be to implement a delay scheme to avoid a brute force attack. After each failed attempt A, the authentication server would wait for an increased T*A number of seconds, e.g., say T = 5, then after 1 attempt, the server waits for 5 seconds, at the second failed attempt, it waits for 5*2 = 10 seconds, etc.

And it's important to not zero timer on window change (also math magic)

[ghost]

Time delay can be implemented by storing last time and fail count mapped by secret

[conorgil]

Section 7.2 of RFC 4226 is titled "Throttling at the Server". I completely agree that the server should have a throttling scheme of calling the OTP library, but the OTP library itself is just a utility that performs the correct calculations given some input. IMO, the throttling makes the most sense to be implemented by the server outside of the library so that it can take into account throttling on a per-user basis, etc.

[ghost]

@conorgil Secret key throttling is universal and reliable. Not matter, one key used by many users or many keys used by one. If TOTP connected to one secret key can be bruteforced it's cracked

[conorgil]

@cyclopentan I think we are all in agreement that preventing brute force attacks is a critical part of implementing HOTP and TOTP correctly as part of an authentication protocol. I am just having a difficult time understanding the argument to put the throttling logic into the OTP lib.

I just reread RFC 4226 - HOTP: An HMAC-Based One-Time Password Algorithm and a few things stood out to me.

Abstract

   This document describes an algorithm to generate one-time password
   values, based on Hashed Message Authentication Code (HMAC).  A
   security analysis of the algorithm is presented, and important
   parameters related to the secure deployment of the algorithm are
   discussed.

It makes a distinction between the HOTP algorithm and the deployment of the algorithm (e.g. the application and protocols).

7. Security Requirements

   Any One-Time Password algorithm is only as secure as the application
   and the authentication protocols that implement it.  Therefore, this
   section discusses the critical security requirements that our choice
   of algorithm imposes on the authentication protocol and validation
   software.

Here again it distinguishes between the HOTP algorithm and the inclusion of that algorithm in a larger application, specifically for use in an authentication protocol.

7.1.  Authentication Protocol Requirements

   We introduce in this section some requirements for a protocol P
   implementing HOTP as the authentication method between a prover and a
   verifier.
...
   RP2 - P SHOULD NOT be vulnerable to brute force attacks.  This
   implies that a throttling/lockout scheme is RECOMMENDED on the
   validation server side.

More details and recommendations on how to implement a protocol P that uses the HOTP algorithm. Notice that requirement 2 specifically mentions brute force attacks and actually only recommends it. I agree with you that it should be required, of course.

7.3.  Throttling at the Server

   Truncating the HMAC-SHA-1 value to a shorter value makes a brute
   force attack possible.  Therefore, the authentication server needs to
   detect and stop brute force attacks.

   We RECOMMEND setting a throttling parameter T, which defines the
   maximum number of possible attempts for One-Time Password validation.
   The validation server manages individual counters per HOTP device in
   order to take note of any failed attempt.  We RECOMMEND T not to be
   too large, particularly if the resynchronization method used on the
   server is window-based, and the window size is large.  T SHOULD be
   set as low as possible, while still ensuring that usability is not
   significantly impacted.

   Another option would be to implement a delay scheme to avoid a brute
   force attack.  After each failed attempt A, the authentication server
   would wait for an increased T*A number of seconds, e.g., say T = 5,
   then after 1 attempt, the server waits for 5 seconds, at the second
   failed attempt, it waits for 5*2 = 10 seconds, etc.

   The delay or lockout schemes MUST be across login sessions to prevent
   attacks based on multiple parallel guessing techniques.

I reproduced section 7.3 in its entirety because it is directly relevant to this discussion. It seems to me that this section is recommending that the application, not the HOTP algorithm, is responsible for implementing one of the brute force attack prevention mechanisms: "the authentication server needs to detect and stop brute force attacks".

The OTP library implements the HOTP algorithm, which is one important component of utilizing HOTP as part of an authentication protocol, but certainly not the only component. The rate limiting for brute force attacks needs to be contextual for each individual user of the system. Each user has a unique secret key, which should be rate limited individually as to not impact other users trying to authenticate to the system.

It makes the most sense to me to have the OTP lib only be responsible for implementing the HOTP algorithm. This makes the scope small and easier to test. Other concerns of implementing a protocol P that uses HOTP should be left to the application developer to implement.

For example, the application must store the counter C for each user, the secret K for each user, the max number of guesses T, the look-ahead window s, etc in the database. The application must also decide how to generate the secret keys (see section 7.5. Management of Shared Secrets), which brute force prevention method to implement, etc. There are many decisions related to using HOTP as part of an authentication protocol that fall outside the scope of the library that implements the HOTP algorithm.

Please let me know if I am misunderstanding your position here.

[ghost]

@conorgil thank you for high quality discussion. I am impressed in how accurate you read RFC. You are example for me to follow :)

As conclusion i agree, that brute force prevention isn't a part of HOTP and can be different in applications

Anyway i need to solve my problem with brute force. Do you know open source projects, that realize it? Or maybe i need to start own and write simple anti-brute force wrapper library?

[conorgil]

@cyclopentan Glad it was useful! I have dug deep into many things 2FA related while working on my browser based 2FA manager called Two Factor Buddy (2FB) and content website All Things Auth where I write about authentication and authorization issues. This comment thread was a really useful motivator for me to re-read most of the HOTP RFC!

Unfortunately, I do not know of any open source projects that offer the higher level of abstraction and implement HOTP/TOTP out of the box. I think it might be relatively specific to each application since there are choices about where/how to store the data, etc. Let us know if you find anything that meets your needs.

Also, realize that TOTP has a constantly changing time window (counter C), so the brute force risks are lower than HOTP (because the counter C only increases when the user successfully logs in). For TOTP, I think it would be more than reasonable security and UX tradeoff to implement a max number of guesses T to be relatively low, such as 5. No user is going to manually put in the incorrect TOTP code more than 5 times in a 30 second window, so if there are more guesses than that, its software doing something wonky and you can just block it.

Finally, I don't know what you're working on, but if the core value of your service is not providing authentication protocols, then I would definitely check out a third party that does this stuff all day every day instead of reinventing the wheel. For example, check out Duo or Authy. It is likely worth it so that you can focus on the core value of your product. Note: I am not associated with either company, but they are the big incumbents in the space and constantly come up in my research.

[yeojz]

@conorgil
Thanks for jumping in and giving such a detailed interpretation.. Haha... Reading those, makes me think I should re-read the RFC as well.. it's been quite a while.

@cyclopentan
Thanks for bringing this up. If you have any open source wrapper in the future, feel free to drop the link here.

---

From a library standpoint

I'm definitely open for additional packages or just examples / samples of common patterns or platforms (thats why I structured it in a "packages > package" format.

However, we need to be careful about adding implementations that are too specific as well (especially in core), as I am afraid that examples will end up being construed as "best practices" that need to be maintained constantly with moving standards of the industry.

[ghost]

@conorgil I mean one-off authentication brute force, not secret key brute

Math explanation: When you try random token, probability of successful auth is p = 1 / N , where N is count of possible tokens. If token is 6-digit, p = 10^-6

p = 1 / N because there is two non-connected equiprobable random values with N possible values. They can make N*N pairs, that are also equiprobable. Successful pairs count is N, for each variant it is pair of equal values. So p = N / ( N * N ) = 1 / N

Lets count probability of successful auth in case of k tries or earlier. It's P = 1 - Q where Q is probability of k fails one after one. q = 1 - p is probability of one fail. Q = q^k because it's probability of connected events

Finally P = 1 - Q = 1 - q^k = 1 - (1 - p)^k, lets plot P = P(k) graph
http://m.wolframalpha.com/input/?i=plot+y+%3D+1+-+%281+-+10%5E-6%29%5Ex+where+x+%3D+500000+to+1000000

For 500 000 attemps probability of succesfull auth is about 40%, for 1 000 000 is 60%

As you see it don't connected to window, only to tries count.

So 5 tries per 30 second TOTP window can be broken with 40% probability in about 1 month

Because 500 000 tries * 30 sec / 5 tries / (60*60*24*30) = 1,15 month

[conorgil]

@cyclopentan I do not follow. Are you worried about someone brute forcing a single OTP for a given counter C, or are you worried about someone recording multiple OTPs in a row and using cryptanalysis to try to determine the original secret K?

If you haven't already, definitely check out Appendix A of the HOTP RFC "Appendix A - HOTP Algorithm Security: Detailed Analysis". It contains the mathematical proof that the authors use to backup claim that brute force is the best possible attack on HOTP.

A.4.3. Brute force attacks are the best possible attacks.

No matter
what strategy the adversary uses, and even if it sees, and tries to
exploit, the authenticators from authentication attempts of the user,
its success probability will not be above that of the brute force
attack -- this is true as long as the number of authentications it
observes is not incredibly large.

Sorry I'm not following here. It might be easier for me if you can explain the specific brute force attack that you're trying to prevent without diving into the mathematical proof details. Thanks!

[ghost]

@conorgil attack is easy: try random token 5 times per 30 second and after month you will pass auth with 40% probability

[yeojz]

Closing this issue for now. Feel free to continue / open the discussion thread if you have any more thoughts! :)