3
$\begingroup$

I'm building a system to authenticate users to a website via a single use login token. This token can either be included in links OR typed in directly by the user as a code. Because of that second requirement I'm interested in the token being as short as possible in order to improve user experience.

There are plenty of guidelines regarding "regular" password strength, i.e. for a password to be used in conjunction with a login handle (email, username...). But in my case I believe the entropy needs to be higher since an attacker would essentially be targeting all users in the system at once when doing a brute force attack: if they guess any of the currently valid tokens they'll get into that random user's account.

So the solution needs to take into account how many valid tokens exist in the system.

So, if I can have up to $v$ valid tokens at any point in time in the system, how much more entropy do my tokens need to have? Do I just need to add $log_2(v)$ bits of entropy or is there something else to take into account? How can we prove that?

PS: I'm focusing here on the additional entropy required compared to "regular" password systems as a way to focus the discussion, as there are various measures that can be put in place to reduce required entropy (rate limiting, token expiration policies etc.) that could be applied, but this is not my question :)

$\endgroup$
  • $\begingroup$ This is subjective and depends on your threat model and constraints. Is there any reason you can't use 128 bits (16 bytes)? $\endgroup$ – SAI Peregrinus May 3 at 22:29
  • $\begingroup$ There's one use case where users will need to type these in, so if I can reduce the size without compromising security that's helpful. And I don't think it's subjective or depends on the threat model, I tried to make this clear in the PS: the question is really that in this case an attack is targeting multiple passwords/tokens at once and I'm not sure by how much I need to increase entropy to compensate for that. $\endgroup$ – Jules Olléon May 3 at 23:01
  • $\begingroup$ how are you verifying tokens? direct lookup against an index? or, are the tokens hashed to obtain the identifier? if the latter, any hardness-factor to obtain the hash (ie. argon2?) $\endgroup$ – brynk May 4 at 4:12
5
$\begingroup$

Summarizing the question:

I can have up to $v$ valid tokens at any point in time in the system, how much more entropy do my tokens need to have compared to "regular" password systems?

In addition to regular password entropy, $\log_2(v)$ bit extra is enough if the number of online attempts $a$ that an attacker can make is unchanged. That amount of additional entropy is necessary if you want no increase in the probability $\epsilon$ that $a$ online attempts succeed to find a working token, compared to the probability of logging into any account assuming the list of accounts is large and known to the attacker¹. Less extra entropy may be needed to maintain the probability that an adversary logs into a particular account², but how much depends on the distribution of passwords assumed in calculating password entropy.

Caution: Except when the system (rather than users) assign uniformly random password values, password entropy has almost nothing to do with the base-2 logarithm of the number of possible passwords. It varies widely with the restrictions put by the system on the choice of password, and with how dearly users care for the security of the data protected by the password. Also, that a certain password entropy is used is no proof that it is enough! And, the hypothesis of constant $a$ might not apply³.

Therefore, you can and should compute directly (without reference to a password-based system) how much entropy is needed in a token: that's $\log_2(v)+\log_2(1/\epsilon)+\log_2(a)$ bit⁴. The simplest and best is that the token is this many bits chosen independently and uniformly at random. That's assuming no information leak beyond correct/incorrect token, like getting an answer faster when the beginning of a token is correct, as notoriously occurs for comparisons using memcmp.

One may choose $\log_2(1/\epsilon)=20$ (slightly less that one chance in a million) and $a$ the number of possible attempts in a day given countermeasures³ to limit this in the server, or the sheer server capacity or link bandwidth absent such countermeasure. The estimation of $a$ should account for the possibility of concurrent attacks ($a$ is independent of network lag).


¹ Making the best attack strategy to test all accounts for the most likely password (or the few most likely ones starting from the most likely).

² Making the best attack strategy to test the account targeted for passwords approximately in decreasing order of likelihood.

³ Countermeasures to lower $a$ are easier with passwords and small user lists (or user lists assumed not to leak), because we can limit the number of login attempts per day/hour/minute and per user, something that might be impossible in the token context. Limiting the total number of attempts per second for the whole server opens to Denial of Service attacks, and limiting per attacker based on IP address is both difficult and uncertain: attackers may use multiple IP addresses using botnets, generate IPv6 addresses on the fly, or maybe spoof IP addresses if acting deep enough in the network infrastructure.

⁴ Proof for that formula: there are $k$ possible tokens, and $v$ of them are assigned uniformly at random and independently (except for being distinct). Attackers make $a$ attempts to log in by submitting a token, different at each time which maximizes their chances. Each attempt has the same probability $1/k$ to hit a particular token irrespective of the index of the attempt (for the same reason that the order in picking straws is immaterial to the probability one has to pick the shortest straw). Since these $a$ events are exclusive, the probability to hit any particular token in $a$ attempts is $a/k$. By the union bound, the probability $\epsilon$ to hit at least one of the $v$ tokens is at most $v$ times larger, that is $\epsilon\le v\,a/k$, and close to that for the low $\epsilon$ that we want in practice. Thus we want $k\ge v\,a/\epsilon$, and that only errs slightly, always on the safe side. Taking the base-2 logarithm, that gives $\log_2 k\ge\log_2(v)+\log_2(1/\epsilon)+\log_2(a)$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Awesome, I realize the formula to derive entropy needed from $v$, $\epsilon$ and $a$ is exactly what I was looking for - I was referring to "regular password strength" because I hadn't figured how to express it in terms of $a$ and $\epsilon$ like you did, even though I was looking at the right variables. Very nice way to formulate it! Now is there a somewhat more formal proof for the $log_2(v)$ part? $\endgroup$ – Jules Olléon May 4 at 10:08
  • $\begingroup$ Also yes on everything you said around it - token will be generated using a proper RNG etc. And I will likely implement a rate limit to set an upper bound on $a$, with the caveats you mentioned in mind - BTW I think you meant DOS attack, not DNS, right? $\endgroup$ – Jules Olléon May 4 at 10:13
  • 1
    $\begingroup$ @JulesOlléon: I managed to make a proof, with some help. Independently: take note of the important condition that I added after the formula. $\endgroup$ – fgrieu May 4 at 16:39
  • 1
    $\begingroup$ @JulesOlléon: I stand by exactly $a/k$ for the probability to hit at least once one particular token in $a$ attempts with the strategy of not making the same guess twice (which is best). $1-(1-1/k)^a$ would apply with the strategy of using an independent random try at each of $a$ attempts, and is a (slightly) lower probability for $a\ge2$. In both cases the probability is $1/k$ to hit that particular token at a given try, but the not-twice-the-same-guess strategy makes the hitting events exclusive, hence the different formula to compute the probability of hitting at least once. $\endgroup$ – fgrieu May 5 at 10:40
  • 1
    $\begingroup$ Oooh gotcha, yes you're absolutely right, for some reason the sentence about the probability being "irrespective of the index of the attempt" confused me and my mind went to "independent" rather than "exclusive" events... but you're right, it's like picking $a$ cards out of a deck of $k$ cards, the probability that your hand includes a specific card is $a/k$. $\endgroup$ – Jules Olléon May 5 at 10:55
1
$\begingroup$

Entropy $H$ is not only defined from the domain/alphabet/encoding. It ultimately depends on the distribution of the words chosen over this alphabet. Roughly speaking, considering a discrete variable $x_i \sim {X}$, the Shannon Entropy is defined by

$$H(X) = - \sum P(x_i) log P(x_i)$$

That is the point: if you choose these codes in an (almost) uniform and independent way, the entropy can be easily calculated. You said "~27 bits", so if you have codes over a 27 bits space, you don't need to think about entropy, because it will demand an effort proportional to $2^{27}$. This is a easy math if your probability distribution is uniform over this domain.

Here is the problem: cryptographic protocols always suppose random keys, but truly randomness is not easy. This is when Min-Entropy ($H_{min}$) is a more suitable definition: because Entropy is an average measure ("conditional"). Min-Entropy considers that your distribution is not perfectly uniform and that the adversary can guess. Take a look in this Crypto.SE discussion here.

In conclusion, you must look at the source of your randomness, because its (Min-)Entropy will be the determinant of your bit code size.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.