How random are TOTP codes?
shkspr.mobi
shkspr.mobi
The 31-bit number is modulo'd by 10^6 to generate a 6-digit base-10 number. But 2^31 isn't a multiple of 10^6, so some remainders will be slightly more likely than others. Namely:
• 000000 to 483647: 2148/2147483648 ≈ 1.000240e-6 chance.
• 483648 to 999999: 2147/2147483648 ≈ 0.999774e-6 chance.
This kind of bias always happens when changing the range of random numbers and the number of possible outcomes is not a divisor of the number of incomes, and rejection sampling isn't used.
This is why, for example, java.util.Random.nextInt(int n) (which generates an integer in the range [0, n)) carefully uses rejection sampling in its algorithm: https://docs.oracle.com/javase/8/docs/api/java/util/Random.h...
Added: to be pedantic, the difference in min-entropy from a uniform distribution is about 0.000347 bits if my calculation is right (log2(2148*1e6/2**31)). Really, this is not of practical significance given how TOTP is used.
The entropy of the TOTP distribution is −log2(2148/2147483648)×483648×2148/2147483648−log2(2147/2147483648)×516352×2147/2147483648 ≈ 19.9315685303 bits.
So yes, the difference in entropy is negligible. The TOTP distribution is worse by 39 nanobits (3.906e-8) per code.
Exercise: consider a weighted, million sided die. 50% of the time when you roll it, it comes up 1. The other 50% of the time, it comes up on one of the other 999999 results, with equal likelihood. What is the min-entropy of this distribution? What is the Shannon-entropy? This should tell you why the min-entropy is preferable.
Added: hmm I think I made a calculation error further up. I'll look at it tomorrow if I can.
So you have 1 bit for the min-entropy and about 11 bits for the Shannon entropy. The Shannon-entropy pretty much hides the elephant in the room, which is the enormous bias of rolling a 1. So basically in crypto you use the min-entropy because that reflects the most vulnerable scenario in a system which is what you prioritize protecting against, rather than protecting against the average scenario.
This was very insightful, thanks for sharing.
What’s the actual likelihood of seeing the same TOTP code from different apps at different times?
What about those ones that get sent out in phone messages?
There’s only a million 6 digit TOTP codes, so I reckon you get to 50% odds of collision at ~1200 values.
With a calculator [1], we can find the exact amount. plugging in D=10^6 (# of unique codes) with P=0.5 (odds of collision) gives you 1178 values.
Sqrt(1 000 000) = 1 000, close enough to the exact number you calculated.
That's about 1.17741 times \sqrt(N).
The reasons are explained here: https://news.ycombinator.com/item?id=40886363
The standard implementation would use a hard coded set of patterns. The enhanced version would pair automatic random code generation with a public site where members of the public can decide in real time whether a given code is "nice" before it's sent along to the intended recipient.
(note @tptacek if you're reading this, I swear it's (mostly) a joke)
With a window of 30 seconds and 1e6 possibilities, the expected time it takes to get to a particular number is 347 days. Should be easy to brute force.
https://gist.github.com/skull-squadron/8f806b28abbcaa1ba9c25...
Unfortunately, it may take several years before a certain TOTP value is reached because the values are nondeterministic rather than ordered and so there will be hash collisions of other values as well.
Example: JBSWY3DPEHPK3PXP 999999
TOTP will match 999999 between 2024-11-29 16:37:00 -0600 and 2024-11-29 16:37:29 -0600Yes it could be several years, however the expected value is less than a year. Just like the expected dice rolls before rolling 6 is 6.
I also wrote a program to find CRC32 hash collisions that can be injected into a text file or script to make a text hash to that value. https://gist.github.com/skull-squadron/c85d295cf9e6124dd7e90...
Doing so MD5, SHA1, or even SHA256 would be extremely slow and expensive, but not impossible.
I wonder if something could be set up to be both more secure, and more tailored to this use-case. Be pretty sweet to embed a 2FA in users brains somehow.
> Be pretty sweet to embed a 2FA in users brains somehow.
Still, "Something that you could calculate without revealing the thing that you know" is an interesting concept.
https://open.substack.com/pub/jacobbartlett/p/building-a-2fa...
Only problem is that I don't have the algorithm. I started writing down all codes I got but since I only get 5 a week, it's a long process. I'll probably switch jobs before I have valid results.
Not that it would change anything, but I'd be really curious how biases in those codes could appear.
I've found that interoperability across diverse implementations is ironically the best protection against schemes that weaken rngs and key entropy to facilitate mass interception. independent implementations become a proof of a protocol or algorithm implementation. if there is only one functional implementation of something, it's where I would look first.
However, it would not be the first time that those being "creative" in their visible parts were also "creative" in the less visible details.
So my confidence in those just following the RFC would generally be higher.
Nitpicking: They are not supposed to be random as that would defeat the purpose. We should be able to deterministically generate the same number on both the client and server side from the same 2 seeds (secret key and the timestamp).
They should be ideally uniformly distributed, though.
This isn't enough as just counting from 000000 to 999999 is uniformly distributed over the whole range. You want the numbers to be pseudorandom so that someone without the seed cannot guess them even if they have seen previously generated numbers.
So during a short hackfest I created this to check it out: https://github.com/eras/reco . Sorry, no binaries and the font size is hardcoded for presentation, and actually the whole UI stuff is just for that reason there.. By default it scans the whole 6-digit sequence space, but you can also give it a sequence and it will show the rules it finds.
Given the rules it uses, it turns out 50% of 6-digit sequences are "easy". Because it is based on the rules I just thought would apply there are probably other "easy" rules that could cover a lot of the remaining 50%.. It also cheats in a way by trying to apply the codes to all* shapes and sizes of numpads (1x10, 2x5, 3x3+1): match in any numpad is accepted for a sequence to be "easy".
It may also be some of the rules for the sequences it finds are not "easy" after all :).
I guess the reason is the human brain can really recognize many kinds of patterns. Nothing weird about the entropy.
But if some numbers were doubled, that chunking makes short-term encoding slightly easier. Rule of 7(+/-2) and etc etc etc.
On the other hand, various decimal “random” numbers around payment cards (default PIN, authorization codes and what not) are clearly biased, because they are usually generated by taking hexadecimal representation modulo 10.
About six months ago our MFA system, which uses codes between 1 and 100, persistently started to give me codes that were odd numbers in the top half of the range (ie 51 or above). This went on for well over a month (several codes per day) before I saw the pattern cease. The rational side of me felt it was just chance but I had a nagging unease all the same!
I think you underestimate these histograms.
However this law obviously does not apply to TOTP codes (unless someone did something very wrong).
https://fy.blackhats.net.au/blog/2024-04-26-passkeys-a-shatt...
I think this is a good advice in general: if you value your freedom avoid platform controlled services even if they are slightly more convenient.
Btw, the platform authenticator apps are a privacy nightmare. Some are constantly reporting your activities to multiple services. You can verify this easily using an on-device proxy VPN such as NetGuard.
For example, Bitwarden is able to act as a passkey provider on iOS and can store the passkey secret key gunk into a password record. I tried it out on a couple of minor services that have username & password login alternatives.
This elimilates passwords altogether, but are there any pitfalls?
An easy counter-measure would be blocking consecutive TOTP logins of the same or similar codes.
The attacker has a 1 in 1 million chance of guessing right, assuming 6-digit codes. This isn't acceptable for most applications.
That's assuming there's no throttle of login requests and all authentication were made under one minute against one single user.
I think you're misreading "1 in 1 million" as "1 million in 1 million".
Actually it does change. Even if you hit the exact correct TOTP code, the system still deny your login because of throttle rules and you can't tell on the client side.
> An easy counter-measure would be blocking consecutive TOTP logins of the same or similar codes.
Which was in response to this attack:
> therefore try an attack where they attempt to log into all of the accounts in parallel with the TOTP ‘000000’
That class of attack is a legitimate threat. Your proposed mitigation (quoted above, not some other mitigation) cannot work. That's because the attacker does not actually need to try consecutive or similar codes, it'll work exaclty as well with random codes.
That you later changed to talking about a totally different attack (of trying a lot of codes on a single account) and a different mitigation (rate limiting of attempts on a single account) is irrelevant to that discussion.
1. hack into any account then call it a win
2. hack into a specific target account for a win
idk man. Maybe for some systems #1 is important.
The goal is to replace passwords. So TOTP is is about as secure as, if not better than logins that requires 6 digit PIN, no?
1 absolutely is important for real systems. Think of the account system for Google, Facebook, Steam, etc. Those accounts will have real value to an attacker even if you're only getting a random account.
And no, TOTP is not as secure as a password specifically for a single-factor use case. It's brute-forceable in a way that passwords aren't, in a way that can't be fixed without a lot of collateral damage, and in a way that a high risk user can't even protect themselves against with better password hygiene[0]. A 6-digit TOTP is a decent second factor, but a horrible single factor.
[0] The attack you described of trying out the password 123456 on all users is called password spraying. (Obviously you'd just not use that, but the top 100 to top 1000 passwords). But that's an attack that single users can guard against, and that systems can mitigate with basically no collateral damage. The mitigations for a TOTP-spraying attack would need to be quite draconian.
Hey man you don't have to be so aggressive. I was asking a question "is it secure?" or "are there any pitfalls?"
If it's not secure then naturally I am curious what can be done about it. I don't need to defend to prove anything.
I am happy to learn that such design is inefficient against #1 scenario, especially if such "account system for Google, Facebook, Steam, etc. Those accounts will have real value" were at stake.
A rate limit strategy should limit the rate of the attacker not the victim.
Rate-limiting per email address is just a DoS vector, anyone can prevent a legitimate user from logging in.
With a long enough session life and a good refresh strategy, it's less of a problem. If an app clears sessions after a week, then I would argue they are doing it wrong.
This elimilates passwords alltogether, but are there any pitfalls?
Coincidentally, I just mentioned that I did this: https://news.ycombinator.com/item?id=40878150
(of course, I leave it as a user preference: The user chooses whether to use standard passwords or to use one-time-passwords)
I have a system I use where you enter your email and get a one-time code.
The goal in that system is not to securely authenticate you, merely to identify you. "Good enough" for the use case.
So pretty insecure, but probably suitable for some systems with low security requirements or other mitigating factors.
But that's a general problem. 2FA should really mean 2 separate devices.
Can we please have customizable diceware TOTP? I'd like 8-12 words 60-90 seconds. I also wish this could be used everywhere.
The point of diceware is to make a given amount of entropy easy to remember, not more secure, and certainly not faster to input.
This was especially relevant when talking about hardware tokens that had relatively inaccurate clocks. In the RSA algorithm I seem to recall it was the second or third digit. Each clock tick was 2.5 seconds or something, so providing the last digit of the clock counter massively reduced the number of calculations the server had to do in case of a mismatch.
We most definitely had drift management. One of the differentiating features to our competitors is that our algorithm had both a "click counter" (number of times the button was pressed) and a "clock counter". The least significant digit of both counters was included in the OTP that was generated. The authentication server used the last digit of both counters to figure out what values to use, and as you say, generated codes in both time directions in order to try and identify the values of the counters (well, the click counter obviously didn't go both directions).
The server then stored the last matching click counter value and the drift of the clock value. It wasn't uncommon to have tokens that drifted by multiple minutes per month.
This being said, you're right: the clock only incremented every 28 or 32 seconds, not 2.5 seconds as I incorrectly remembered.
So it's less of a "depending on the algorithm they may do this" thing and more "some proprietary solutions do this instead".