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.
One I remember stumbling upon some years back was the .NET Framework equivalent of that, System.Random.Next(0, int.MaxValue), which has a much greater probability of producing odd numbers than even numbers, the probability of getting odd numbers being 50.34%, because of some rather unfortunate translations between integers and floating points. https://fuglede.dk/en/blog/bias-in-net-rng/
The effect of this on the min-entropy is basically nil.
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.
Pedantry 2: normally in cryptography we use the min-entropy <https://en.wikipedia.org/wiki/Min-entropy> rather than the Shannon entropy that you linked, though in this case they are almost equal.
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.
Not being an expert, I was unaware of this and worked through it after reading the article you linked.
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.
We like to see patterns. I think the same thing with TOTP codes, I'm always noticing when they have repeated digits, or only 2 different digits, stuff like that, but that's just the nature of the human brain looking at random numbers.
I have long considered building a code generator that only serves "nice" codes.
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)
Hmm for 2 digits you only have one "nice" code (69). For three digits it's the same (069). For four digits you do get two (0069 and 6969), but I think you need a lot of digits before "nice" codes are effective.
I've always been under the impression that popular TOTP implementations were specifically designed to produce "nice" codes. They always have repeated digits, like 202838.
For those curious on how to find that ~1200 values are needed before a 50% probability of collision, this is a generalized form of the birthday problem [0].
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.
I have been thinking about a useless TOTP app that works the other way around. Instead of giving you the current code, it gives you the timestamps when the code is e.g. 000000, 123456 or 777777.
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.
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 -0600
That's neat but I'm embedding the CRC-32 hex digest itself in a TBD location rather than a chosen text. It's moot because the time savings would be premature optimization. Brute force takes only a couple of minutes and I barely use it. Thanks for the thought though.
Not so useless. A user of that could memorise the times/dates where a particular easy-recall code comes up. With that, they have effectively "transferred" 2FA for those times into their brain, and not need to use any 2FA app (at only those times).
Good luck memorising a number of 30 second windows and hitting them exactly. That would require a level of organisation, timing and self-discipline I can not fathom.
Well, the thirty second window in practice is usually a 2 - 3 minute window, as TOTP servers are set up to allow for drift, network issues, human slowness etc. For sure, memorising more than a handful may be hard but it's just "11 Nov 14:35", etc.
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.
I think it would be easier to use HOTP for that as the codes are one time use and aren't time based. The user just needs to memorize one of the next N codes.
My employer uses alphanumeric 2 factor codes and I'm so certain that they have a bias towards some letters (mostly y and z). I know I'm probably wrong and it's probably because they appear so rarely in real words, but I can't shake the feeling they aren't random.
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.
Custom logic to serialize a number as a set of symbols hardly comes near the threshold of "rolling your own crypto". So long as they follow a standard to generate the number, the serialization is basically irrelevant as long as it's reversible.
aside, the adage "don't roll your own crypto," has this funny side effect of homogenization where a weakness empowers an attacker against the maximum number of targets and makes mass interception more cost effective.
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.
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.
> 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.
I wondered about a related problem: how many of the codes are "easy"? Easy as in they are composed of "simple" patterns, such as going to adjacent digits in a number pad. Often it seems that if you are given such a sequence, there's a pattern you can use to recall it. Seems like it would make the randomness suspect, perhaps? But maybe all the sequences have easy rules, the rules just differ?
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 often have the feeling that my TOTP codes are somehow simple. Simple in the sense of containg repeated digits, some rhythm (e.g. 663183) or symmetry instead of being "purely random" (e.g. 581329).
I guess the reason is the human brain can really recognize many kinds of patterns. Nothing weird about the entropy.
Since the start of using any kind of SMS 2FA I keep noticing, that for some systems you get “nice to remember” numbers somewhat often. I didn't care enough to actually write them down and confirm whether it is a fact or just my internal bias of finding patterns where there are not any.
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.
Am reassured others see this sort of thing (even if it ends up being chance).
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!
A related issue is that TOPT security guidelines suggest using a 160 bit key. Some organizations use 20 chars with alphabet A-Za-z0-9. Easy mistake to make, a byte is 8 bit after all. However, 62 ^ 20 is only 120 bits (give or take). Way less than the recommended minimum. Does anybody know how insecure this is in practice?
Having implemented TOTP codes once I know that they're basically unbiased because of the cryptography involved. That said, I would bet money that Apple's two-factor implementation is something custom because it just seems far too likely to generate combinations that look non-random. A bet not because I have evidence I'm right, but because I want someone to explain to me how these work, if only just "oh it's literally the same algorithm everyone else uses" :)
Passkey was a great idea. A brilliant solution which could have solved authentication on the web once and for all. If only Apple, Google and Microsoft had not completely ruined it by tying it to their platforms and using it as another moat
"If you really want passkeys, put them in a password manager you control. But don't use a platform controlled passkey store, "
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.
I don't like passkeys. I'm not sure if I'm using it wrong, but it feels like entering a TOTP is so much faster and easier than using passkeys. It was always easy to enter a 6 digit code and have some back-up codes printed somewhere. Passkeys might be superior in some ways, but feel much harder to use. But then again, I'm also not an average user.
I don't like the idea of passkeys if they cannot be backed-up or are non-portable locked away in a walled garden and possibly on stored on some corporate cloud in some unknown manner. When they can be backed-up, are portable, and have an explicit security policy, then I'll consider them.
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.
Do you still think it's easier to type in a 6 digit code that is on your mobile while you're browsing with your desktop (compared to Touch ID / Face ID with passkeys)?
Not TOTP but a bunch of sites are doing this thing where they send an OTP to the registered email and have eliminated passwords altogether. I find it really annoying.
It is annoying but it generates far fewer support requests for people who can't remember a password and think resetting it is too difficult.
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.
Depending upon one's threat model, I found that the "public" version of throwaway emails still work great for that purpose, versus sites like 10minutemail which destroy the address after a time. Sure, I am cognizant that if I just went surfing around (e.g.) https://www.mailinator.com/v4/public/inboxes.jsp?to=ksynwa long enough I could probably snag any hypothetical login link to HipsterLoginLink.co but in practice I doubt it's an issue
It blows my mind that a 6 digit code is considered a secure replacement for a password on these sites. Only a 1 in 1 million chance of brute forcing. Seems rather simple for a motivated actor with a botnet targeting a large list of accounts to have some degree of success.
Any competent IPS system would lock out a botnet, and it rotates, so you need to guess the right 6 digits within 90 seconds 30 plus 30 on both sides) until it's a different set of 6 digits.
That's how I use random sites for which I can't/won't use my main browser - just set a random password and don't save it anywhere, then rely on email password resets to login.
You'll see this in CTFs sometimes. Each guess gives the attacker a one in a million chance of guessing the TOTP. If the attacker can figure out a username (usually easy) and the log in API isn't rate limited, then they can just guess codes in a loop. It take about 12 days to make one million guesses at one request per second. Most TOTP apps allow codes that are older/newer, and the attacker may be able to use a higher RPS. I guessed a TOTP in 30 minutes for one CTF, for example.
So pretty insecure, but probably suitable for some systems with low security requirements or other mitigating factors.
Totally not my field of expertise, but maybe some like “an attacker knows all usernames, and can therefore try an attack where they attempt to log into all of the accounts in parallel with the TOTP ‘000000’” yields a high enough chance of hitting one or more accounts that happen to have this TOTP at this very moment?
Because you can have a rate limit on attempts against one user. You can't have an effective rate limit on attempts against all users in aggregate. Or rather, you could have one, but the consequence is that a brute-force attack would cause all legitimate users to also be blocked by the rate limit.
No, it is assuming neither of those things. Each independent attempt pretty obviously has those odds, no matter how many accounts and how much time they're spread over. Your suggested countermeasure does not do anything to change those odds.
I think you're misreading "1 in 1 million" as "1 million in 1 million".
> Your suggested countermeasure does not do anything to change those odds.
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.
But that's not what you suggested first, and what dmurray objected to:
> 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.
I agree there is a difference between the two. The discussion was about #1, you got called out on your incorrect statements about it, and rather than admit the mistake you're pretending you were talking about #2 all along.
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.
> your incorrect statements about it, and rather than admit the mistake
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.
In similar systems I built, 123456 is never a system selected OTP. It gets guessed too often, if it was generated, we would never know if the user got the code or just guessed.
In this case you might as well send a very long token, since it's going to be copy/pasted. TOTP codes are rather short. Or better yet, send a link to login: this can be made to work cross-device (copy/paste usually doesn't).
Depending on the algorithm, one or two of the digits in the TOTP are counters to help the server figure out clock drift on the client device.
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.
No, TOTP implementations don’t compensate for clock drift, but they do compensate for moderate inaccuracy and races at the edges of the 30 second slots by typically allowing two or three codes around the current time +/- 1 minute or so.
Well, considering I was part of the implementation team of one of those hardware tokens, I'm sorry I'm going to have to disagree with you :). Please note that I'm not talking about RFC6238 / 4226. I'm talking about proprietary implementations for hardware tokens.
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.
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...