Why should double submit CSRF tokens be cryptographically strong random numbers?

Short answer: To prevent brute forcing the CSRF token.

Let's take a trivial example: let's say your token is a single digit, accepting values from 0 to 9.
Now sure, an attacker cannot read this value from the cookie or header, but she does not have to - she can just have the attack send 10 CSRF requests, one with each possible value. One of them will be correct.

Using a cryptographically strong random value will prevent this, and can prevent the attacker from trying to scale up this attack (by having the attack send e.g. 1000 requests instead of 10, or 10,000, or... )

Combining the best of both answers:

1. The token length needs to be proportional to the number of victims and the number of requests per victim. If an attacker convinces X victims to navigate to his page (by way of spam or phishing attacks) and each such page attempts Y different tokens then you need to protect yourself against 2^x*y attacks. For example, if your token length is 16 bits long, an attacker needs to send out 2¹⁶ emails that attempt 1 token each, or 2⁸ emails that attempt 2⁸ tokens each. An attacker can test multiple tokens with a single click using Javascript or by embedding multiple malicious image links per page.

2. You want to use a cryptographically-secure random number generator to prevent attackers from requesting multiple tokens themselves, then using the sequence they got to predict what tokens other users will get in the near future.

It doesn't

It just has to be pseudo random.

CSRF is not compatible with brute force attacks. Consider the attack vector:

1. Malicious user crafts a special email or web page with HTML that posts to the site of interest
2. User is logged on to the site of interest, and the session ID is passed passively (it's a cookie)
3. User is tricked into clicking the link in the specially crafted email or web page
4. Link "forges" the request. The link doesn't have to contain the session ID because it's in the cookie. And it doesn't have to pass the CSRF token found in the header (it's passed passively-- it's a cookie). But it does have to contain the CSRF token in the form post.

There is no way a hacker is going to trick anyone into clicking a link hundreds of times. Even if it's a script that sends a ton of requests on a single click (assuming the hacker has figure out how to do that-- browsers don't allow cross-domain AJAX requests, so we're probably talking about a page containing hundreds of clear GIFS or something else totally whacky), it's not going to be able to get through a whole lot of search space without timing out.

Also, there is no way for the attacker to determine if the attack worked for a particular value-- it's a "fire and forget" attack.

So the idea that the CSRF token can be brute forced is far fetched at best. The hacker would have to be personally logged on-- which is a different attack entirely.

The only reason you need any entropy at all really is because CSRF attacks tend to be delivered via spam. Let's say you're an idiot and your CSRF token only has 16 bits of entropy, and the hacker sent out 65,536 spam emails with the exact same token. 65536/2^16 = one of those attacks would actually succeed. Assuming 0% of the emails hit spam filters, 100% of the users opened them, and 100% of the users happened to be logged into your app at the moment they clicked the evil link.

Other than hoping to sucker in a ton of users, there's no way for a hacker to scale the attack large enough to call it a brute force attack with any significance to it.