# Why does an anti-forgery token need so many bits?

Why do we need so many bits? If an attacker decides to mount a brute-force attack, wouldn't you be able to detect and lock them out after a few attempts? With as little as 30-bits, you've got 1 million possible tokens for 1000 concurrent users. Guessing the token using brute force seems extremely unlikely.

My point is that 30-40 bits of data seems very hard to break using brute force. So why does Google recommend 130-bits? Isn't that just overkill?

UPDATE: Okay, say you couldn't prevent a brute force attack...

• Assuming each user makes one request per second, you've got one request per 2 microseconds.
• Therefore, we can safely assume that (as of today) the most powerful attacker will be capable of sending at most one request per 2 microseconds.
• Next, assume that we expire tokens after 5 minutes. This means that an attacker can fire 1.5*108 requests before the token expires.
• Next, assume we want the attacker to have less than a 1% chance of guessing the token. Therefore we need a pool of 1.5*1010 tokens per active token.
• So if you have 500,000 concurrent users (Facebook) you need 7.5*1015 tokens (one pool per user).
• This means you need 53 bits of data, which again is nowhere near the 130 bits which Google is asking for.
-
You want a potential attacker to have up to a 1% chance of guessing a token? Hmmm, methinks an couple orders of magnitude need to be added to your numbers for most of us to be comfortable. I haven't done the math yet but that's not a base number I would use. – Caleb Jun 3 '14 at 7:07
sorry, but your math and assumptions don't seem to make sense. For example, why do you assume an attacker can send only what Facebook receives? Why are you counting tokens for active users, and why 5 minutes? The 1% also seems a bit weird, as @Caleb mentioned. While it really is super important to look at the math of these things (more developers should do that!), I think you're going about it the wrong way. – AviD Jun 3 '14 at 7:43
At this point your question is a bit of a moving target. Please don't use questions as an ongoing discussion as your understanding of an issue progresses. I answered the original question, now you've changed it to the point were it would require an entirely different answer. It would be more helpful for everybody if you would focus the question on one issue, then if you have more questions after that in answered, ask a focused question on the new issue. – Caleb Jun 3 '14 at 7:47
@AviD: actually I think using Facebook's traffic is fairly ingenious. Most websites can't process anything like as many requests as Facebook does, so for most websites that rate of attempts would naturally cross the line from a brute-force attack on the token into a DoS ;-) That's not to say I like the rest of the analysis, though. In particular if there really were a 1% chance of an attack succeeding in 5 minutes then you'd have to expect that form of attack to succeed in about 500 minutes unless otherwise stopped. – Steve Jessop Jun 3 '14 at 9:26
The cost of using 130 bit tokens is relatively small. Why not crush that 1% chance into oblivion? What if increases in network and computing power make much larger attacks possible in the future? – Russell Borogove Jun 3 '14 at 17:45

Your question makes an assumption that should not be made in the field:

wouldn't you be able to detect and lock them out after a few attempts

Yes, in a good working environment there should be a system like this in place that rate-limits failures of various kinds. This is a good thing to do but it should never your first or only line of defense. If your security model relies on an extra layer like this for it's theoretical security you are introducing an unnecessary point of failure and possible attack vector.

By keeping the the theoretical math that needs to be done out of reach you reduce the risk posed by things which may be (or eventually end up) out of your control such as a faulty rate limiter implementation or an inside attack job.

-
Okay, but even then... 130-bits?! Where do you draw the line? Why not go up to 1024-bits while we're at it? Take a look at the numbers I posted for Facebook. Anywhere over 40-bits seems like a far stretch even for such a large company. Let's look at this another way: say I couldn't rate-limit the attacker... and say that I expire a token after 5 minutes of creation. How many attempts could an attacker make during 5 minutes? And how big does the pool have to be (relative to that number) to give him a very low probability of succeeding? – Gili Jun 3 '14 at 6:44
Correction to my last comment. I just updated the question with a concrete example which (I believe) proves that Facebook only needs 53-60 bits of data, which means the average company needs far less. – Gili Jun 3 '14 at 7:14
@Gili: 128 bits is not much at all. It's 32 hex digits. The size of an MD5 hash, or of a GUID...and your language of choice makes it trivial to generate at least one of those. And frankly, expiring a token after 5 minutes will annoy pretty much everybody who posts a form but doesn't type all that fast. :P – cHao Jun 3 '14 at 13:18

A few other factors which contribute to the need for so much entropy and why they might suggest 30 characters:

Firstly, this is to protect the application side login action – which will then create its own authenticated session independent of the Google one. The important thing is that it's up to the application to store the token and decide when to stop accepting it. If it's kept in a session or a database table then you might continue to accept that token indefinitely and Google can't ensure applications don't do this, so it's easier for them to recommend more entropy.

Secondly, they're proposing the use of rand() in PHP in that example. To be honest this surprises me, because that function doesn't produce cryptographically secure random numbers. In fact according to the docs it might only produce numbers between 0 and 32767 on some systems. This suggests to me that 30 characters isn't absolutely necessary to ensure security, but is simply a good idea.

Thirdly I think "30 characters" is mainly relevant to the context of their example, where they're using rand() pumped into md5(). Given that md5() produces hexadecimal values then there's only 16 possible values per character. Also, md5 digests are 32 characters long, but if you start truncating that then it'll be significantly easier to find a collision.

In short:

1. It's easier to suggest high entropy instead of complicated ways for application developers to ensure values are expired securely and reliably.
2. If people take their example code (ie. md5(rand())) and start truncating the 32 bit value, then an attacker may only have to find all the distinct n character prefixes of md5 hashes of the values 0 to 32767, where n is what you truncate at. This will probably produce a set of values that could be brute forced within a feasible amount of time.
-

Looking at the example code on that page:

• The PHP code uses `rand()`, which on some systems is at most 15 bits and may be even less because `rand()` isn't necessarily a good RNG.
• The Python code uses 32 characters from an alphabet of 36 (uppercase and digits), which works out to approx. 165 bits assuming that `random.choice` is perfect. Which it may well not be, but we're still looking at a lot more than 15 bits.
• The use of 130 bits in the Java code falls between the two. I can't see any obvious motivation for it: the number is output in base 32, so to follow the "about 30 characters" advice I'd expect 150 bits rather than 130. It could conceivably be a typo!
• What is constant among the different examples presented is that the string is "about 30 characters" long as advised (26 for Java, 32 for the others). This one constant piece of advice doesn't tell you much about security, only about the convenience of storing, transmitting and receiving it.

I doubt that there exists a definitive answer to this question, other than to find out how the author of the Java snippet in particular chose the number 130. If this quantity of entropy were genuinely important to Google's security advice, then the Python and PHP examples would use it too. Which they do not.

The general principle at work is that it's cheap to generate, store and transmit these amounts of data. As such there is no benefit, and some risk, to only using as much as you really need. The result is to advise "overkill", although that PHP code falls short.

You ask why not 1024 bits -- well, base-64 encoded that would require 172 characters, and perhaps you could argue that does start to approach significant in the weight of a webpage, although it would be a stretch. I'm not aware of any reason you can't use CSRF tokens that large, it's just not worth advising people to use them. Choosing between 130 and 1024 is a matter (based on experience) of the difference between a comfortable overkill and gluttony. Choosing between 130 and 64 might be more a case of the difference between comfortable overkill and a nagging feeling that maybe you're within an order of magnitude or two of not really being secure to brute force after all.

So when giving general advice about this kind of choice, it's fairly reasonable to analyse a worst-case situation, double the answer (or more), and then check that the result is within reasonable resource limits. If so, just use it. As such you wouldn't expect there to be anything very special about the numbers 30 or 130. It would perhaps have been instructive for Google to show its working.

-
I wondered if anyone would follow Google atrocious PHP recommendation, and it looks like some people went down to less than 3 bits of entropy github.com/yiqing-95/yiiSpace/blob/master/protected/extensions/… – Bruno Rohée Jun 3 '14 at 10:15
rand(1,1000) is also acceptable as a source of entropy... stackoverflow.com/questions/3673332/… – Bruno Rohée Jun 3 '14 at 10:27
@BrunoRohée: yes, at that point one suspects the purpose of the CSRF token is to pass some feeble audit rather than to improve the security of the site in an informed way. Anyway, even with better use of `rand()` a single round of md5 is not widely accepted as a key-stretching algorithm ;-) – Steve Jessop Jun 3 '14 at 13:02

The point is to make a brute-force attack infeasible, not just hard.

Yes, you could make the token barely long enough to match some arbitrarily chosen probability under certain assumptions. But why would you do that? Why gamble with the security of your users and your application? It's not like a bunch of pseudo-random bits was a huge cost factor.

Something like 128 bits is a very common choice when people simply don't want to worry about brute-force attacks (or accidental collisions). You can find this “magic number” in many different applications like symmetric keys, hash salts, UUIDs etc.

-

When you start viewing an attacker's probability of success in terms of time instead of percentage Google's recommendation becomes a lot more reasonable.

Take the formula found at https://www.owasp.org/index.php/Insufficient_Session-ID_Length and you will quickly discover that if you want to keep an attacker at bay for over a year, you will need over 100 bits of entropy. 130 bits is still crazy high but it begins to sound a bit more reasonable.

Thank you for pointing me in the right direction.

-