Challenge: Key space division in TOTP

One of the things I'm working on right now is a 2FA solution for some professional work and it's got me thinking about TOTP again. Years ago I took a trip down the rabbit hole on TOTP after Google Authenticator launched and they started using it in the mainstream. The TOTP algorithm stands unbroken, and the cryptographic community consensus is that TOTP codes don't reveal anything about the key. That is, that you could observe thousands of them and they wouldn't help you find the shared secret. But I've always had a nagging feeling that the whole thing behaves as some sort of perpetual motion machine in the Shannon space.

I can't prove it, I'm not an academic cryptographer and my math skills just aren't at that level, but theres something very visceral that my brain 'just knows', as if on instinct. I get this feeling from time to time and I've learned to trust it. 

So with my work returning to the 2FA realm, I'm still nagged by the following intuitive assertion; 

That every observed TOTP code N at time C divides the secret key space K.

That is, the number of candidate keys that can match the actual key decreases with each observation, and the set of observations has a relationship to the key space. The greater the number of N @ C pairs, the fewer the possible Ks that can meet all the observations. I believe this relationship to be extremely divisive and that only a small number of keys will produce the same 32 TOTP codes at the given times. 

For clarity I am referring to the knowledge of the partial input C influencing the key space of K, not the number of secrets in the 16 byte space. I refer to a reduction in the set of possible keys to search based upon the set of N @ C pairs. 

As a result, I have a challenge that is setup thusly; Using a popular off the shelf PHP TOTP library ( ), i've generated 32 TOTP codes each one day apart in time, and using openssl's random pseudo bytes to create a key of 16 bytes in length. I've printed the output of the following script. 


$strong = null;

$secret = openssl_random_pseudo_bytes(16, $strong);

echo "Strong: ". var_export($strong, true) . PHP_EOL;


$totp = new TOTP;






echo "Secret: ". base64_encode($secret) . PHP_EOL;

$time = time();

echo "Run Time: ". $time . PHP_EOL;

for($i=0; $i<32; $i++) {

  $timestamp = $time + ($i * 86400);

  echo "Timestamp: ". $timestamp;

  echo " TOTP: ";

  echo $totp->at($timestamp) . PHP_EOL; 


The result is 

Strong: true

Secret: <redacted>

Run Time: 1449789268

Timestamp: 1449789268 TOTP: 291494

Timestamp: 1449875668 TOTP: 216134

Timestamp: 1449962068 TOTP: 287667

Timestamp: 1450048468 TOTP: 439154

Timestamp: 1450134868 TOTP: 930590

Timestamp: 1450221268 TOTP: 056836

Timestamp: 1450307668 TOTP: 372930

Timestamp: 1450394068 TOTP: 604009

Timestamp: 1450480468 TOTP: 907565

Timestamp: 1450566868 TOTP: 806569

Timestamp: 1450653268 TOTP: 377693

Timestamp: 1450739668 TOTP: 047923

Timestamp: 1450826068 TOTP: 207111

Timestamp: 1450912468 TOTP: 676863

Timestamp: 1450998868 TOTP: 717443

Timestamp: 1451085268 TOTP: 444988

Timestamp: 1451171668 TOTP: 480191

Timestamp: 1451258068 TOTP: 131072

Timestamp: 1451344468 TOTP: 562432

Timestamp: 1451430868 TOTP: 119421

Timestamp: 1451517268 TOTP: 807229

Timestamp: 1451603668 TOTP: 221399

Timestamp: 1451690068 TOTP: 750264

Timestamp: 1451776468 TOTP: 624718

Timestamp: 1451862868 TOTP: 120224

Timestamp: 1451949268 TOTP: 461853

Timestamp: 1452035668 TOTP: 079031

Timestamp: 1452122068 TOTP: 139722

Timestamp: 1452208468 TOTP: 590428

Timestamp: 1452294868 TOTP: 979260

Timestamp: 1452381268 TOTP: 587875

Timestamp: 1452467668 TOTP: 643794

Can you find the key that produced these codes? If you can, you've just earned some serious bragging rights in the crypto community, as this is supposed to be impossible. On the other hand, if you can you find a lot of other keys that will produce all 32 codes at these times you may prove the algorithm secure. I have the key, so prove my intuition right or wrong. 

That is the challenge.