Can MFA codes be predicted if you know what their values were at a previous time? I use an app on my phone that, after scanning a QR code on a website, gives me 6-digit codes which change every 30 seconds. These codes can be used for Multi-Factor Authentication (MFA) on some websites, often in lieu of SMS codes or in-app login confirmations.

Presumably these codes are generated based on the shared secret that only I and the website provider both know - that QR code I initially scanned when setting up the MFA. The idea, as I understand it, is that without that original code you are unable to calculate the 6-digit MFA code that is valid during any given 30 second time period.

I am curious, however. What if an attacker has gained keylogger access to a device I use and is able to regularly capture the value of these 6-digit codes; is it possible over time for the attacker to use this history of codes, along with the time they were used, to derive the original QR code I was given when I set up the MFA in the first place?

Essentially, do I need to occasionally rotate my MFA accounts?
[Is] it possible over time for the attacker to use this history of codes, along with the time they were used, to derive the original QR code I was given when I set up the MFA in the first place?


To answer this one needs to understand how TOTP (the standard in question works). Namely it essentially takes the current time 1 and the pre-shared secret from registration and feeds them into HMAC (usually HMAC-SHA1, but other hash algorithms are also supported) and then takes the returned byte string, converts it into an integer and essentially reduces it $\bmod 10^6+1$ (or however many digits you configured).

Now note that the weakest attacker goal is to predict whether you are generating these numbers at random for each time interval or are using TOTP (e.g. recovering the secret lets you do that). This is called PRF-security in cryptographic terms and luckily has been studied intensively for HMAC. The current best know security estimate for this is found in this paper. It states that one can only distinguish HMAC from a random function (Theorem 1) with probability $\varepsilon'=(2q+1)\varepsilon+q^2/2^c$ when doing $q$ queries (i.e. seeing $q$ different outputs) for a $c$-bit output. The $\varepsilon$ here is the security of the underlying compression function used by the hash function, which is usually assumed to satisfy PRF-security as well. Heuristically it can be assumed that $\varepsilon=q/2^c$ for a good hash function - which includes SHA1 and MD5 even to this day. Plugging things together we get $\varepsilon'\approx q^2/2^c$ and $c$ being 512 for SHA-1 this value is negligible for more than a human lifetime. Now this means that the intermediate TOTP output is indistinguishable from a random string for distinct outputs which means in turn that the codes are indistinguishable from random codes. This is what we wanted to show.

So you might be wondering what the hell all of the above means:


Distinguishing the MFA codes from a randomly chosen code is essentially impossible while the shared secret is unknown to an adversary (even knowing the input time).
Because of the preceeding an adversary only seeing the codes (and knowing the time generating them) cannot predict any future or past unseen codes.
Because of the preceeding an adversary only seeing the codes (and knowing the time generating them) cannot predict the shared secret obtained through the QR code.



  Essentially, do I need to occasionally rotate my MFA accounts?


As explained above, no you don't.



1:Actually it takes the current time minus the unix epoch divided by the base interval duration, e.g. 30s.