TOTP verification passes/fails randomly

[Linuus]

Hi!

I have some issues where the verification seems to pass randomly when it should fail.

Here's a minimal script to show this issue:

# frozen_string_literal: true

require "bundler/inline"

gemfile(true) do
  source "https://rubygems.org"

  git_source(:github) { |repo| "https://github.com/#{repo}.git" }

  gem "rotp"
  gem "pry"
end

class Foobar
  DRIFT = 60
  INTERVAL = 60

  attr_accessor(:key, :proof)

  def initialize
    @key = ROTP::Base32.random_base32
  end

  def generate_proof(time)
    @proof = totp_generator.at(time)
  end

  def verify_proof(time)
    !totp_generator.verify(proof, drift_behind: DRIFT, drift_ahead: DRIFT, at: time).nil?
  end

  def totp_generator
    @totp_generator ||= ROTP::TOTP.new(
      key,
      interval: INTERVAL,
      digits: 3,
      digest: "SHA256"
    )
  end
end

drift = 60 # seconds
interval = 60 # seconds
1000.times do
  # Align time at start of interval
  time = Time.at((Time.now.to_f / interval).floor * interval)
  foobar = Foobar.new

  foobar.generate_proof(time)

  raise "SHOULD BE FALSE" if foobar.verify_proof(time - drift - 2)
  raise "SHOULD BE TRUE" unless foobar.verify_proof(time - drift)
  raise "SHOULD BE TRUE" unless foobar.verify_proof(time)
  raise "SHOULD BE TRUE" unless foobar.verify_proof(time + interval + drift - 1)
  raise "SHOULD BE FALSE" if foobar.verify_proof(time + interval + drift)

  puts("All good")
end

Now, it most often fails on the last raise here. I first thought it might be some kind of small timing issue so I added even more time to it to make sure it fails, like this:

foobar.verify_proof(time + interval + drift + 1000)

It still passes sometimes, which seems very odd to me!

Is there a bug in here or am I doing something wrong? 🤔

[mdp]

Yeah, so you've selected 3 digits as the OTP, and it's possible that the next OTP is the same as the previous OTP. The OTP's are generated by HMAC, but then boil that down into x number of digits, so it's entirely possible (and likely with 3 digits) that you get a 'collision' where the next (or previous) OTP is the same.

On each iteration, you choose the same time (for the most part but depends on when you run it), but Foobar is creating a new random key for each run. At some point, out of 1000 runs, some random key at say "2021-03-18 18:31:00" gives the same OTP at "2021-03-18 18:32:00" and it's failing.

If you increase it to 6 digits it will fail less often, but it will still fail from time to time.

Let me know if that answers your question.

[Linuus]

Ah ok, I see. Thanks!

[benoittgt]

@mdp Thanks for the detailed answer. The same issue happens when you drift_behind is very long?

For example

# frozen_string_literal: true

require "bundler/inline"

gemfile(true) do
  source "https://rubygems.org"

  git_source(:github) { |repo| "https://github.com/#{repo}.git" }

  gem "rotp"
  gem 'activesupport'
end

class Otpable

  DRIFT = 864_000 # 10 days

  attr_accessor(:totp, :proof)

  def initialize
    @totp = ROTP::TOTP.new(ROTP::Base32.random, issuer: 'Club service')
  end

  def generate_otp
    @proof = totp.now
  end

  def verify_otp(drift_behind: DRIFT)
    totp.verify(proof, drift_behind: drift_behind)
  end
end

require 'active_support/testing/time_helpers'

include ActiveSupport::Testing::TimeHelpers

100000000.times do |i|
  optable = Otpable.new

  optable.generate_otp

  print "."
  raise "SHOULD NOT BE NIL" if optable.verify_otp.nil?
  travel_to(Time.now + (Otpable::DRIFT * 2)) do
    raise "SHOULD BE NIL" unless optable.verify_otp.nil?
  end

rescue => e
  puts
  puts "Failed at #{i} times"
  puts
  raise e
end

It is not very effective, but it fails the 63 times.

[mdp]

Right, so behind the scenes it's asking if you have a valid OTP and including every OTP generated for the past 10 days (28_800 OTPs or 864_000/30 intervals, which is also why this test is so slow, it's generating and comparing 28k OTPs). Then you're looking at the odds of a collision between one of those 28k OTP's and your current OTP. Your current OTP is 6 digits, so essentially 1_000_000 variations and the odds of a collision is 28_800/1_000_000(2.88%).

Anytime you use drift_behind or drift_ahead you're saying "Included every OTP in the drift time range and consider it valid". Typically you're drift behind would be something like 30 seconds, so you're now comparing the submitted OTP to two valid OTP's, which should be fine for most security situation (1/500_000 odds vs 1/1_000_000). With 10 days drift in either direction you've essentially made it much more likely that any random OTP will be considered valid.