Find a TOTP collision

collide.rb

#!/usr/bin/env ruby
# frozen_string_literal: true

require 'openssl'

class Base32
  ALPHABET = (('A'..'Z').to_a + ('2'..'7').to_a).map(&:freeze).freeze
  PADDING_CHAR = '='

  BITS_PER_BYTE  = 8
  BITS_PER_CHAR  = 5
  BITS_PER_CHUNK = 40 # least common mutliple

  CHARS_PER_CHUNK = BITS_PER_CHUNK / BITS_PER_CHAR  # 8
  CHUNK_LENGTH    = BITS_PER_CHUNK / BITS_PER_BYTE  # 5

  ENCODING_MASK = ALPHABET.length - 1 # 0x1f
  DECODING_MASK = 0xff

  def self.encode(str)
    str.bytes
       .each_slice(CHUNK_LENGTH)
       .map { |chunk| encode_chunk(chunk) }
       .join
  end

  def self.decode(str)
    str.delete(PADDING_CHAR)
       .each_char
       .map { |char| ALPHABET.index(char) }
       .each_slice(CHARS_PER_CHUNK)
       .map { |chunk| decode_chunk(chunk) }
       .join
  end

  private
    def self.encode_chunk(chunk)
      bits_in_chunk = chunk.length * BITS_PER_BYTE
      number_of_characters = (bits_in_chunk * CHARS_PER_CHUNK + (BITS_PER_CHUNK - 1)) / BITS_PER_CHUNK
      if bits_in_chunk < BITS_PER_CHUNK
        padding = BITS_PER_CHAR - bits_in_chunk % BITS_PER_CHAR
      else
        padding = 0
      end

      buf = chunk.reduce(0) { |buf, byte| (buf << BITS_PER_BYTE) + byte } << padding

      encoded = Array.new(CHARS_PER_CHUNK)
      j = number_of_characters - 1

      number_of_characters.times do |i|
        encoded[j] = ALPHABET[(buf >> BITS_PER_CHAR * i) & ENCODING_MASK]
        j -= 1
      end

      (CHARS_PER_CHUNK - number_of_characters).times do |i|
        encoded[number_of_characters + i] = PADDING_CHAR
      end

      encoded
    end

    def self.decode_chunk(chunk)
      number_of_original_bytes = chunk.length * BITS_PER_CHAR / BITS_PER_BYTE
      if chunk.length < CHARS_PER_CHUNK 
        padding = BITS_PER_CHAR - (number_of_original_bytes * BITS_PER_BYTE) % BITS_PER_CHAR
      else
        padding = 0
      end

      buf = chunk.reduce(0) { |buf, byte| (buf << BITS_PER_CHAR) + byte } >> padding

      decoded = Array.new(number_of_original_bytes)
      j = number_of_original_bytes - 1

      number_of_original_bytes.times do |i|
        decoded[i] = ((buf >> BITS_PER_BYTE * j) & DECODING_MASK).chr
        j -= 1
      end

      decoded
    end
end

DIGITS = 6
INTERVAL = 30 # seconds

def hotp(k, c)
  hmac = OpenSSL::HMAC.digest('SHA1', k, [c].pack('L>'))
  offset = hmac[-1].ord & 0xf
  code = (hmac[offset].ord & 0x7f) << 24 |
         (hmac[offset + 1].ord & 0xff) << 16 |
         (hmac[offset + 2].ord & 0xff) << 8 |
         (hmac[offset + 3].ord & 0xff)
  (10 ** DIGITS + (code % 10**DIGITS)).to_s()[-DIGITS..-1]
end

def totp(k, ct)
  hotp(k, ct)
end

if !ARGV[1]
  $stderr.puts 'Usage: {otp secret in base32 format} {digits of TOTP code to match}' 
  exit 1
end

key = Base32.decode(ARGV[0])
seek = ARGV[1]

c = Time.now.to_i / INTERVAL

until totp(key, c) == seek do
  c += 1
end

puts "TOTP will match #{seek} between #{Time.at(c*INTERVAL)} and #{Time.at(c*INTERVAL + INTERVAL - 1)}"