How much entropy do I need to add to passwords if they are NOT used in conjunction with logins 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 :)
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)$.