Should I use a cryptograpically secure random number generator when I generate IDs?

Math.random() is usually seeded from the current time of day. Therefore there is a chance that collisions will happen for objects that are generated around the same time each day.

From a security perspective, this means that these "random" values will be predictable by an attacker.

Even if seeded with something else, a non cryptographically secure pseudo random number generator can reveal its state should enough values be captured. This is why it is better from a security perspective to only use values generated by a cryptographically secure pseudo random number generator (e.g. crypto.randomBytes() that you refer to).

CSPRNGs have certain properties that make them suitable for use in security:

• Every CSPRNG should satisfy the next-bit test. That is, given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success better than 50%. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.
• Every CSPRNG should withstand "state compromise extensions". In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.

Using such a generator will satisfy your security requirements:

• Prevents easy enumeration.
• Does not give away order objects were created.
• Does not give away total number of objects or growth rates.

However, you shouldn't let the fact that these are now unpredictable from protecting the first case with proper access controls (authentication and authorisation). URLs should not be considered secret and there are many ways they can leak (shoulder surfing with hidden camera, HTTP referrer header leakage, proxy and browser logs). Also, once a URL is known and you're relying on an unpredictable secret to protect it, the user accessing it will always have access and this cannot be revoked. Remember - they can easily bookmark it.

Using unpredictable values would definitely help your other requirements should they be deemed necessary for your application. I would recommend using a 128 bit random value which is more than enough entropy to prevent predictability and collisions.

Yes. A crytographically secure RNG is necessary to accomplish all the things you listed.

I don't know how Math.random works, but think of a TERRIBLE RNG we'll call 2bitRNG that's seeded with just 2 bits, but produces 128 bit numbers. I seed 2bitRNG with my 2 bits of entropy, and then produce 10,000 random numbers with it.

Since I've only seeded it with 2 bits, there's only 4 possible seeds. So an attacker only has to search through a space of 40,000 possible random numbers to find the correct seed, and position in the sequence you're currently at. That's a small number, and likely could be calculated within a fraction of a second with a modest computer. Once the attacker knows this, he knows the the next sequence, and how many RNGs you've produced.

I don't know how bad Math.random is or what other attacks it might be vulnerable to, but the general recommendation is to NOT use it for security purposes because it isn't secure. A proper secure RNG uses a large amount of entropy (~128 bits or higher) to prevent the kind of attack I just described and doesn't produce predictable results.

tl;dr: That depends, if you can, use a CSPRNG.

While often UUIDs are used which are not (bound to be) from a CSPRNG, this might not be a good idea in cases the (not CS)-PRNG is not re-seeded regularly (as in long-living server processes)

If the algorithm you use to create such identifiers is known, and it's input can be estimated with a few samples (as it's the case with C's rand() for example), you loose all those properties you enumerated in your question.

While using a predictable PRNG to generate values from a single seed is thus bad, if the bad PRNG is reseeded with good entropy before every use (as it's the regular case in most web scenarios), that should be fine.

So, if you can, use a CSPRNG. If you can't, try to reseed it with good entropy before each generation step.

This all depends on how your generation process is seeded and used.

If you have a long-running process, have it use a CSPRNG. If you are using short-lived processes, use a good entropy source and basically any PRNG.