How secure does a session cookie have to be?

Question

For personal learning I'm developing a webapp (PHP+MySQL) with login procedure as described in this article. I'm using two (pseudo)tables for validation:

[users]
id | username | password_hashed

[sessions]
id | username | session_id | session_token_hashed | session_expired

TLDR: How random/cryptographically secure do the session_id and session_token have to be, given that the session_token will be regenerated on every revisit and invalidated on first invalid try?

Long explanation

For sake of the question the following can be assumed:

• Yes I am aware that any 'stay logged in' feature is inherently a potential security breach by itself because people
• Password and session_token are stored using php's password_hash() and validated using password_verify()
• User periodically has to re-enter password, practically expiring any previous sessions
• When user actively logs out, resets password, or does any other manual interaction, any session is invalidated
• Cookies are stored with parameters Secure and HttpOnly
• Credentials are only handled via HTML forms, PHP and cookies, not using any JS
• Cookie values are retrieved on page load via $_COOKIE
• Session_id is unique in the whole table

Rough login procedure:

• User logs in with credentials, validating according [users] table
• Create random session_id (static to identify browser) and random session_token, store in cookie and database
• User closes browser (not logging out)
• User revisits website
• Check if session_id and session_token are a match
  • If so, generate new session_token and store in cookie & database
  • If not, force logout user and invalidate session (notify user via email of cookie infringement)

What I don't understand: With this method you are basically 'faking' a username/password validation because the method is the same; you store a username (session_id) and a password (session_token) in a database and verify to grand access.

The 'only' difference is that username is unique for each browser, password is regenerated every visit and there is a one shot chance (because the session is invalidated on the first non-matching id/token) of 1 in 2¹²⁸ (or roughly 1 in 10.000 billion billion, also see this answer) to 'guess' the token for a given session_id.

Is this assumption correct? If so, why is this considered a secure method to keep users logged in?

Concern: If the cookie gets stolen, the proposed scheme of refreshing the token on every login doesn't provide any additional protection since the attacker simply uses the token to fake a login and gains full account access anyways.

Is this a valid concern? Besides the option to check if the (now stolen) token has already been used, are there any other benefits of rerolling the token on re-visit? Reading this answer and this answer, it comes across that cookies in themselves are inherently insecure.

Question: In what scenario does it really matter to use a cryptographically secure string (e.g. using bin2hex(random_bytes(16))) over just a random string (e.g. foobar_42, or 32x rand(0,9), or MD5($currentDateTime))?

Answer 1

The session ID and session token need to be cryptographically secure. Most languages make it easy to generate cryptographically secure values for these, and there's little reason not to.

A cryptographic PRNG passes the next-bit test; that is, given a certain amount of output, the probability of guessing the next bit of output from the PRNG should be negligibly better than 50-50. However, most non-cryptographic PRNGs don't pass this test, and so their output can be predicted given enough previous output.

As a consequence, it's not very difficult for someone to set up a small number of accounts, log in in an automated way back to back, and then get random data from the session ID and token, and then compute the data from the PRNG based on that. Remember that in security, we assume the attacker knows the algorithms you use, including the method you use to generate your tokens and secrets. For your code to be secure, it must be secure even if the attacker knows how it works, because usually they can figure it out.

So you'd want to use random_bytes in PHP, and bin2hex would be a fine encoding. You would not want to use the current date and time or rand, because those are easily guessable, and you should avoid using MD5 for any reason.