TOTP collisions

00-totp.js

const { authenticator, hotp } = require('otplib');

const SECRET = authenticator.generateSecret();

const map = new Map();
const TOTAL = 100000;
const MAX_DIFFERENT = 1000000;
const STEP = 30;
const OFFSET = (Date.now() / 1000 / STEP) | 0;

console.log(`Secret: ${SECRET}`);
console.log(`Offset: ${OFFSET}`);

let last = 0;
let duplicates = 0;

for (let i = 0; i < TOTAL; i++) {
  const token = hotp.generate(SECRET, OFFSET + i);
  if (map.has(token)) {
    const old = map.get(token);
    old.count++;
    old.deltas.push(i - old.last);
    old.last = i;

    duplicates++;
  } else {
    map.set(token, { count: 1, last: i, deltas: [] });
  }

  const percentage = (i / TOTAL) * 100;
  if (percentage - last >= 10) {
    console.log(`Percentage: ${percentage.toFixed(2)}%`);
    last = percentage;
  }
}
console.log('-----');
console.log('');

function stats(name, list, isTime = false) {
  list = list.slice();
  list.sort((a, b) => a - b);

  let min = Infinity;
  let max = 0;
  let mean = 0;
  let stddev = 0;
  for (const count of list) {
    min = Math.min(min, count);
    max = Math.max(max, count);
    mean += count;
    stddev += count ** 2;
  }

  mean /= list.length;
  stddev /= list.length;
  stddev -= mean ** 2;
  stddev = Math.sqrt(stddev);

  const fmt = isTime ? (time) => {
    return ((time * STEP) / 3600).toFixed(2) + 'h';
  } : (time) => time.toFixed(2);

  console.log(`  ===== ${name} =====`);
  console.log(`    min: ${fmt(min)}, max: ${fmt(max)}, ` +
    `mean: ${fmt(mean)}, stddev: ${fmt(stddev)}`);

  if (!isTime) {
    return;
  }

  const p1 = list[Math.floor(list.length * 0.01)];
  const p5 = list[Math.floor(list.length * 0.05)];
  const p10 = list[Math.floor(list.length * 0.1)];
  const p25 = list[Math.floor(list.length * 0.25)];
  const p50 = list[Math.floor(list.length * 0.5)];
  console.log(`    p1: ${fmt(p1)}, p5: ${fmt(p5)}, p10: ${fmt(p10)}, ` +
    `p25: ${fmt(p25)}, p50: ${fmt(p50)}`);
}


console.log('Results:');
console.log(`  Duplicates: ${(duplicates / TOTAL * 100).toFixed(2)}%`);
console.log(`  Covered: ${(map.size / MAX_DIFFERENT * 100).toFixed(2)}%`);
console.log(`  Timespan: ${(TOTAL * STEP / 3600 / 24).toFixed(2)} days`);
stats('count', Array.from(map.values()).map(({ count }) => count));
stats('deltas', Array.from(map.values()).map(({ deltas }) => deltas).flat(),
  true);

01-out.txt

Secret: OBVXMSQSGBNQCOLS
Offset: 1582909005
Percentage: 10.00%
Percentage: 20.00%
Percentage: 30.00%
Percentage: 40.00%
Percentage: 50.00%
Percentage: 60.00%
Percentage: 70.00%
Percentage: 80.00%
Percentage: 90.00%
-----

Results:
  Duplicates: 4.86%
  Covered: 9.51%
  Timespan: 34.72 days
  ===== count =====
    min: 1.00, max: 4.00, mean: 1.05, stddev: 0.23
  ===== deltas =====
    min: 0.03h, max: 823.24h, mean: 272.52h, stddev: 197.66h
    p1: 3.75h, p5: 19.09h, p10: 39.69h, p25: 106.53h, p50: 234.05h

02-long-term-out.txt

Secret: BYCW43RIF42D6H2W
Offset: 52763668
Percentage: 10.00%
Percentage: 20.00%
Percentage: 30.00%
Percentage: 40.00%
Percentage: 50.00%
Percentage: 60.00%
Percentage: 70.00%
Percentage: 80.00%
Percentage: 90.00%
-----

Results:
  Duplicates: 36.82%
  Covered: 63.18%
  Timespan: 347.22 days
  ===== count =====
    min: 1.00, max: 9.00, mean: 1.58, stddev: 0.81
  ===== deltas =====
    min: 0.01h, max: 8323.23h, mean: 2346.75h, stddev: 1818.18h
    p1: 30.70h, p5: 156.74h, p10: 317.90h, p25: 844.41h, p50: 1929.13h

package.json

{
  "name": "totp-check",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "keywords": [],
  "author": "Fedor Indutny <fedor@indutny.com>",
  "license": "MIT",
  "dependencies": {
    "otplib": "^12.0.1"
  }
}