Palindromes and anagrams in TOTP codes

This morning, I entered yet another of those six digit TOTP codes to log into an online service. One thing that I always find interesting is when the second half of the code is similar to the first half, like say 675567. My curiosity got the best of me and I just had to know how often that happens.

The interesting cases would be a palindrome (eg. 123321), a repetition (eg. 123123), and an anagram of the first digits (eg. 123213, 123312, etc.).

The first case, palindromes, is pretty easy. For a six digit base ten number that’s zero padded, any three digit prefix has exactly 1000 possible three digit suffixes, and only one of them is the reverse of the prefix, thus for all possible six digit codes with a given three digit prefix, \(1/1000\) is a palindrome. Since there are 1000 such prefixes, and \(10^6\) possible six digit codes, the probability of getting a TOTP code that’s a palindrome is \(1000/1000000 = 1/1000\).

The second case is a repetition, which has effectively the same number of occurrences as palindromes, so the probability of getting a TOTP code like 123123 with both halves identical is \(1/1000\).

For those, we can actually generalize that for a code of length \(2n\), the probability of it being a palindrome is \(1/10^n\), for which the proof is relatively trivial. Given that there are \(10^n\) prefixes, each prefix has exactly one valid suffix to make a palindrome, and \(10^{2n}\) total numbers, we get a probability of \(10^n / 10^{2n}\) which simplifies to \(1/(10^n)\).

In other words, for a code of length 6 like a regular TOTP token, \(n\) would be 3. The length being \(2n\) makes it an even length, which is necessary in order to be able to split the code into two halves of equal length.

That leaves the case of the anagrams, which are permutations of the first half of the TOTP code.

Since that’s a bit more complicated, what we would want to do is count the number of such permutations, which would allow us to calculate the probability of them given a code of length \(2n\) for any arbitrary \(n\).

For \(n=1\), it’s pretty easy to prove that there are ten such permutations, since the first half has to equal the second, and there are ten single digits since we’re using base ten, which gives us \(1 \times 10\)

For \(n=2\), it’s a bit more complicated, since doubled digits only have one valid permutation (eg. 1111), but different digits have two valid permutations (eg. 1212 and 1221). Since we know that there are ten valid doubled digits, and \(10^2\) prefixes, we can enumerate each case:

• one valid permutation for each prefix that’s doubled digits, of which there are ten
• two valid permutations for each prefix that doesn’t have doubled digits, of which there are \(10^2-10\)

As such, we get \(1 \times 10 + 2 \times (10^2-10) = 190\).

For \(n=3\), we get different cases:

• one distinct permutation for each prefix that are three identical digits (or one distinct digit), of which there are ten
• three distinct permutations for each possible prefix with two distinct digits, of which there are \(270\) (\(10 \times 9 \times 3\), since there are three positions where the doubled number can be)
• six distinct permutations for each possible prefix with three distinct digits, of which there are \(720\) (\(10 \times 9 \times 8\))

This gives us \(1 \times 10 + 3 \times 270 + 6 \times 720 = 5140\).

Interestingly, at this point, we can start to see a pattern. For each \(n\) we have \(n\) different cases, each of which is the product of the number of distinct permutations of a prefix of length \(n\) and the number of such prefixes with \(m\) distinct digits.

However, if we try to expand the cases for \(n=4\), the pattern starts becoming more complicated. In the case of \(n=3,m=2\), there’s exactly one possible pattern \(\{a,a,b\}\) — in other words, \(a\) appearing twice and \(b\) appearing once. But for \(n=4, m=2\) means that we can get two subcases \(\{a,a,a,b\}\) and \(\{a,a,b,b\}\), each with different numbers of permutations.

Unfortunately, this is the point where I hit the limits of my combinatorics toolkit, which isn’t sufficient to continue to expand this in order to get to a closed form.

Even discussing it with Claude unfortunately only gets me to a discussion about Stirling numbers, for which I’d probably need an actual combinatorics class to understand.

What I do however have is the ability to write Python. A brute force approach is to simply count the number of items where the sorted prefix matches the sorted suffix by exhaustively enumerating them. A first stab at it would be something like this:

import time

def count_prefix(n, prefix):
    """Count the number of suffixes of length n matching a prefix of length n."""
    count = 0

    first = sorted(f'{prefix:0{n}d}')
    for suffix in range(10**n):
        if first == sorted(f'{suffix:0{n}d}'):
            count += 1
    
    return count

def count_for_n(n):
    """Count the number of suffixes of length n matching a prefixe of length n, for all prefixes of length n."""
    count = 0
    # We optimize this by only computing the prefixes that start with 0, then
    # multiplying the resulting count by 10, hence the n - 1 and count * 10
    for prefix in range(10**(n - 1)):
        count += count_prefix(n, prefix)
    return count * 10

for n in [1, 2, 3, 4]:
    start = time.time()
    count = count_for_n(n)
    elapsed = time.time() - start
    print(f'n={n} {count} ({elapsed:.1f}s)')

n=1 10 (0.0s)
n=2 190 (0.0s)
n=3 5140 (0.1s)
n=4 175870 (6.7s)

That’s pretty inefficient, but we can completely ignore the fact that doing everything as string operations doesn’t make sense and just brute force it by using more cores:

$ python3 test2.py
Using 32 cores
n=1 10 (0.0s)
n=2 190 (0.1s)
n=3 5140 (0.1s)
n=4 175870 (1.2s)
n=5 7132060 (109.5s)
n=6 329009500 (11411.3s)

Obviously, that’s not going to be very useful for \(n > 6\). A smarter approach would be to actually look at all the prefixes, and for each, we can look at the number of distinct permutations of each prefix.

Given a prefix, we can calculate the number of distinct permutations by calculating the number of total permutations and dividing by the number of permutations that are equivalent. For example, given \(\{a, b, b, c, c, d, d, d, d\}\), there is \(a \times 1, b \times 2, c \times 2, d \times 4\), which gives us \(9!\) total permutations, and \(1! \times 2! \times 2! \times 4!\) permutations that are equivalent since they would swap equivalent letters, so \(9! / (1! \times 2! \times 2! \times 4!)\) distinct permutations.

Since we can iterate over the possible prefixes of length \(n\) using product(range(10), repeat=n) in Python, we can sum the number of distinct permutations for each prefix:

from itertools import product
from collections import Counter
from math import factorial
import time

def distinct_perms(seq):
    """Number of distinct permutations of seq."""
    counts = Counter(seq)
    denom = 1
    for k in counts.values():
        denom *= factorial(k)
    return factorial(len(seq)) // denom

for n in range(1, 7):
    start = time.time()
    total = sum(distinct_perms(seq) for seq in product(range(10), repeat=n))
    elapsed = time.time() - start
    print(f'n={n} {total} ({elapsed:.1f}s)')

n=1 10 (0.0s)
n=2 190 (0.0s)
n=3 5140 (0.0s)
n=4 175870 (0.0s)
n=5 7132060 (0.2s)
n=6 329009500 (1.8s)

That’s slightly faster, but can we do better?

It turns out that we can. In practice, we don’t really need to look at all possible prefixes. We just need to look at the distinct prefixes, and for each distinct prefix, count how often it would appear as the prefix of all possible permutations and multiply it with the number of distinct suffixes for that prefix.

But the interesting thing is that any distinct prefix permutation occurs just as often as a distinct suffix permutation, therefore for a given unique prefix that occurs \(k\) times, the combination of prefix and suffix occurs \(k^2\) times.

Given that we can iterate over the number of distinct prefixes using combinations_with_replacement from itertools, we get:

from itertools import product, combinations_with_replacement
from collections import Counter
from math import factorial
import time

def distinct_perms(seq):
    """Number of distinct permutations of seq."""
    counts = Counter(seq)
    denom = 1
    for k in counts.values():
        denom *= factorial(k)
    val = factorial(len(seq)) // denom
    return val * val

for n in range(1, 15):
    start = time.time()
    total = sum(distinct_perms(seq) for seq in combinations_with_replacement(range(10), n))
    elapsed = time.time() - start
    print(f'n={n} {total} ({elapsed:.1f}s)')

n=1 10 (0.0s)
n=2 190 (0.0s)
n=3 5140 (0.0s)
n=4 175870 (0.0s)
n=5 7132060 (0.0s)
n=6 329009500 (0.0s)
n=7 16786131400 (0.0s)
n=8 928136093950 (0.0s)
n=9 54775566167500 (0.1s)
n=10 3410496772665940 (0.2s)
n=11 222005754890212600 (0.4s)
n=12 15000987483726651100 (0.6s)
n=13 1046188137708903907000 (1.2s)
n=14 74962723424363171666200 (1.9s)

Faster, but what if we don’t need to look at prefixes at all? After all, \(\{1,1,2,2\}\) and \(\{2,2,3,3\}\) are functionally the same shape, they’re both \(\{a,a,b,b\}\).

Ideally, we’d want to iterate over all possible shapes, determine how frequently they happen, and then multiply that by the number of the distinct permutations for both the prefix and suffix.

Thinking about this, all of the shapes correspond to integer partitions of \(n\), which we can enumerate.

However, how many times does a given shape occur? It’s actually not unlike the number of distinct permutations. Given a partition \((5, 2, 1)\) giving the shape \(\{a,a,a,a,a,b,b,c\}\), there are going to be \(\text{P}(10,3)\) possible permutations of values for \(a\), \(b\), and \(c\). Of those permutations, we only care about distinct ones, for which we divide by the number of equivalent permutations \(5! \times 2! \times 1!\) just like we did earlier.

Combining this with the iteration over the integer partitions, we obtain:

from itertools import product, combinations_with_replacement
from collections import Counter
from math import factorial, perm
import time

def distinct_perms(seq):
    """Number of distinct permutations of seq."""
    counts = Counter(seq)
    denom = 1
    for k in counts.values():
        denom *= factorial(k)
    val = factorial(len(seq)) // denom
    return val

def partitions(n, max_part=None):
    """Generate all integer partitions of n."""
    if max_part is None:
        max_part = n
    if n == 0:
        yield []
        return
    for first in range(min(n, max_part), 0, -1):
        for rest in partitions(n - first, first):
            yield [first] + rest

def partition_freq(p):
    """Number of distinct prefixes of length n with the shape described by partition p."""
    num = perm(10, len(p))
    group_sizes = Counter(p).values()
    denom = 1
    for g in group_sizes:
        denom *= factorial(g)
    return num // denom

def expand(p):
    """Turns a partition into a sequence, eg. [4,1,1] -> [1,1,1,1,2,3]"""
    result = []
    for i, count in enumerate(p):
        result.extend([i] * count)
    return result

for n in range(1, 36):
    start = time.time()
    total = sum(partition_freq(p) * (distinct_perms(expand(p))**2) for p in partitions(n))
    elapsed = time.time() - start
    print(f'n={n} {total} ({elapsed:.1f}s)')

n=1 10 (0.0s)
n=2 190 (0.0s)
n=3 5140 (0.0s)
n=4 175870 (0.0s)
n=5 7132060 (0.0s)
n=6 329009500 (0.0s)
n=7 16786131400 (0.0s)
n=8 928136093950 (0.0s)
n=9 54775566167500 (0.0s)
n=10 3410496772665940 (0.0s)
n=11 222005754890212600 (0.0s)
n=12 15000987483726651100 (0.0s)
n=13 1046188137708903907000 (0.0s)
n=14 74962723424363171666200 (0.0s)
n=15 5498130019391836779330640 (0.0s)
n=16 411530535654245301470621950 (0.0s)
n=17 31356088574298606320386653100 (0.0s)
n=18 2427021041017043491153965921700 (0.0s)
n=19 190503335542483372330410996741400 (0.0s)
n=20 15141611551571136170888372040881620 (0.0s)
n=21 1217139074924843939858814351399207400 (0.0s)
n=22 98842200132473370747145638230967749800 (0.0s)
n=23 8101728898006244345372661851453503553200 (0.0s)
n=24 669726723998568836522230181105574128110300 (0.0s)
n=25 55795274602503578824222289822443655978969560 (0.0s)
n=26 4681758615768072569523909519240428469710722600 (0.0s)
n=27 395453445930931409251856590032442214866187196400 (0.0s)
n=28 33608239045373840314515158913703013026652947557400 (0.0s)
n=29 2872579519173857793770273182010705032632562354001200 (0.1s)
n=30 246834326193001913394128194670639988506276343043750000 (0.1s)
n=31 21315441958224220856628571224534049914293855923654420000 (0.1s)
n=32 1849273517783123200549693566803651920890240945045791338750 (0.1s)
n=33 161139312619385360063516676533858238406393393904589277787500 (0.1s)
n=34 14098800869487764495194617126968353038429633317749280671202500 (0.1s)
n=35 1238339832632091663366565254379967711395345531463977649183181400 (0.2s)

Interestingly enough, I couldn’t find such a sequence in the OEIS, so I’ve added it as A394980.

Phew! Coming back to the original question, given a random 6 digit TOTP code, there’s a \(5140/1000000\) probability of getting an interesting TOTP with the second half being an anagram of the first half, or about a 0.5% chance. And if you ever got a 70 digit TOTP, that would occur with a probability of 0.00001238%, which is about the same probability of successfully entering a TOTP that long before it rotates.