Must not be able to sucessfully validate a given TOTP twice

[f3ndot]

Description

From RFC 6238:

Note that a prover may send the same OTP inside a given time-step
window multiple times to a verifier. The verifier MUST NOT accept
the second attempt of the OTP after the successful validation has
been issued for the first OTP, which ensures one-time only use of an
OTP.

Once ROTP successfully verifies a TOPT, it should no longer accept subsequent verifications of the same value.

I couldn't find any reference to this requirement for HOTP in RFC 4226. Only TOPT appears to apply.

Expected

otp = ROTP::TOTP.new("base32secret3232")
value = foo.now
foo.verify(value) #=> true
foo.verify(value) #=> false
foo.verify(value) #=> false

Actual

otp = ROTP::TOTP.new("base32secret3232")
value = foo.now
foo.verify(value) #=> true
foo.verify(value) #=> true
foo.verify(value) #=> true

Security Impact

In a two-factor authentication context, an attacker could Man-in-The-Middle the connection between the verifier and provider, obtain the username, password, & OTP values, and log in with the credentials within the current time step (a 30 second window, if defaults are used). Arguably, this defeats the two-factor authentication since the OTP can be replayed multiple times.

Alternatively, an attacker could “shoulder surf” the victim’s second factor device in lieu of compromising the connection.

[f3ndot]

Note this issue has security implications:

In a two-factor authentication context, an attacker could Man-in-The-Middle the connection between the verifier and provider, obtain the username, password, & OTP values, and log in with the credentials within the current time step (a 30 second window, if defaults are used).

Alternatively, an attacker could “shoulder surf” the victim’s second factor device in lieu of compromising the connection.

[mdp]

Thanks for pointing this out. Couple issues:

I'm not sure the solution/PR proposed will work for most users. In many cases, a service is going to be running multiple processes and therefore not sharing memory state. Ideally this would need to be something that allows users of the library to plug in their own shared memory storage (MySQL, Redis, etc)

Also the code at the moment seems to have a couple issues:

1. It assumes that the current 'timestep' will only see the authentication of one person. (It's typically a 6 digit code, so it's likely in a large service that each timestep may see a 'collision' between users with different secrets)
2. The "consumed_keys" value will continue to grow indefinitely.

Looking at other OTP libraries, I can't find any that actually try and implement protection against reuse, most likely because it requires some external storage to do correctly. While I do agree that this represents a security issue, I'm not sure it's significant.

HTTPS should be in use for any authentication system, so MITM issues should be mitigated. As for shoulder surfing, it's tough to really gauge the severity in real world situations (Most 2 factor users aren't trying to mitigate against shoulder surfing, but instead provide a level of protection against phishing).

Looking at this pragmatically, in most cases the users of this library simply want to ensure that the user currently possesses a 2nd factor of authentication and nothing more. Other users may want to go the extra mile and record "used" tokens. This library should either allow users to:

a: Provide their own storage layer to store used tokens and pass that over to ROTP to handle detecting duplicate uses.
b: Create their own 'reuse' protection layer in front of this lib.

But I agree that it's an issue that should be addressed in some way. However at the moment I'm leaning towards option 'b' due to simplicity.

[f3ndot]

Thanks for your thorough reply. I tend to agree with you on every point, and please excuse the insufficient PR.

I'm somewhat hesitant to suggest option B without strong conveyance to users of the library that, without such a mechanism, their solution is RFC non-compliant. In my opinion, security software should follow the RFC spec that has identified & guarded against an attack vector, no matter how small. If it is not the responsibility or out of scope for this library, the "buck" should be passed to the users and they should be keenly aware of such a responsibility.

I'd expect the de facto library for a language that provides a cryptographic solution to provide hooks or options for those tinfoiled users (i.e. me 😉) to use the crypto feature completely, as designed, and not omit anything for the sake of simplicity.

For option A I can see an interface like:

otp = ROTP::TOTP.new("base32secret3232", {consume_totps: true})
value = foo.now
otp.verify(value) #=> NotImplementedError: You must override #is_consumed?() and #consume() see mdp/rotp#44

With signatures and example implementations of the methods looking like:

def is_consumed?(otp, time_step, uid)
  redis = Redis.new
  result = redis.get(uid)
  return false unless result
  stored_time_step, stored_otp = result.split
  stored_time_step == time_step && stored_otp == stored_otp
end

def consume(otp, time_step, uid)
  redis = Redis.new
  redis.setex(uid, @interval, "#{time_step} #{otp}")
end

uid would be some sort of unique identifier of the user attempt to two-factor authenticate and is up to the implementer of ROTP to define. It could be passed as an option to the constructor of ROTP or maybe a #uid= method.

Now an argument can be made for and against defaulting the consume_totps: true option, forcing users to pass instead consume_totps: false if they wish to not use such a feature.

Thoughts?

[reedloden]

Google Authenticator's libpam module solves this a bit differently. See invalidate_timebased_code().

[mdp]

So it would be pretty easy to add a signature like your example, but I think the best place to fundamentally address the issue is one level up where you're creating the 'is_consumed?' override. I would assume that this would be created by a library like devise-opt which has access to the storage layer along with the users details. It would also be prudent to have this library implement not only the storing of the last used token, but also things like attempts and rate limiting.

Long story short, I'm happy to implement some type of 'is_consumed?' API, but then the majority of the work needed to actually implement this heads back up the stack to the library using ROTP. So it would probably be best to loop @wmlele in and see how hard it would be to have devise-otp implement this.

On a slightly interesting side-note, since the tokens are only 6 digits, there's actually a small but realistic chance that the next token will actually be the same. One solution would be to simply store the last period that a user authenticated and never let them auth with that period/count or any before it. For example, I auth at '1435155030', instead of storing the used token, we'd actually just never let them auth again with any time on or before '1435155030'.

Collision example:

require 'rotp'

hotp = ROTP::HOTP.new("base32secretkey3233")

i = 0
last = hotp.at(i)
while true do
  i = i + 1
  if hotp.at(i) == last
    p "Collision for #{i} and #{i-1}"
    break
  end
  if i % 10_000 == 0
    p "Attempt: #{i}"
  end
end

"Attempt: 10000"
"Attempt: 20000"
"Attempt: 30000"
"Attempt: 40000"
"Attempt: 50000"
"Attempt: 60000"
"Attempt: 70000"
"Attempt: 80000"
"Attempt: 90000"
"Attempt: 100000"
"Attempt: 110000"
"Attempt: 120000"
"Collision for 125846 and 125845"

[bdewater]

+1 for the 'is_consumed?' API. We use ROTP but not devise in any way (as an authentication company we have our own) and we were thinking about a similar Redis solution to fix this issue. I'm happy to help where needed.

[sbc100]

+1 for some kind of "is_consumed?" API that can/should be implements by the consumer of the API.

+1 for using the timestamp/count rather then that OTP value to implement the check.

[jnardone]

There's an interesting PR from earlier today that looks at this problem a little differently - basically, by keeping a single value per seed (the last timestamp for a successful validate) you can use that value to reject any TOTP values that are from time windows at the given timestamp or prior. Instead of keeping a list of used numbers you just track the one time_t value. Doesn't solve the persistence part of what would be needed here (but that's outside of the library).

-> #58

[mdp]

Thanks for all the hard work on this, but I've gone with PR #58 to solve this for now. It lets the consumer of the API handle persistence which I think it outside the scope of this library for the moment.