This approach is overcomplicted and probably unnecessary (in the no-session case), and possibly insecure (in the session case) anyhow because it ultimately rests on SameSite, which is a defense-in-depth measure rather than a reliable protection.
First of all, you talk about CSRF protection for users without a session, but that almost certainly doesn't make sense. The usual purpose of CSRF is that it's a way for an attacker to take actions in the context of the victim's session. Sometimes it matters anyway if you are authorizing users based on something other than session - e.g. by IP address, location within a LAN/VPN/localhost, HTTPS session, HTTP Authorization (Basic or Digest), or so on - but that's extremely rare and nothing you've said suggests that is happening here. Given that, trying to prevent CSRF for sessionless users is like trying to lock a car door that isn't part of a car. There's nothing for it to secure.
Second, your whole cookie-for-sessionless-users thing is literally just re-inventing JWTs (better to just use existing systems) and then sticking this neo-JWT in a samesite cookie (reasonable thing to do with a JWT) and calling it an anti-CSRF token (it's not). For anti-CSRF purposes, this is no stronger than having a completely empty cookie called "NotCSRF" which has the same flags as the one you're using. The value of the cookie doesn't matter, because you don't have anything to compare it to. Since you don't have any way to distinguish one user from another (unless you're storing the R value on the server and in some way associating it with the user, in which case this is just a weird session token after all, albeit possibly an unauthenticated session), an attacker can trivially get their own (valid) cookie and send requests using that from their own machine (no need for CSRF, as above). In the event CSRF matters, SameSite on the "NotCSRF" cookie prevents the attacker from making CSRF requests anyhow (you just request any request without a cookie called that). If the attacker could get past the weaknesses in cookie-based CSRF protection (by planting a cookie on the victim's browser), the neoJWT complicated version still offers no more security than the blank cookie because an attacker can just go get their own (valid) cookie and plant that instead.
Third, you say "the application often uses just simple links and this can not easily be changed", with the implication that these links (resulting in simple GET requests) are state-changing. That's bad, both because it's a violation of the HTTP spec (see section 9 of https://www.ietf.org/rfc/rfc2616.txt), and because it violates the expectations of web client software (e.g. some browsers and other web clients pre-fetch links that a user can see, for reasons such as checking them for malware or making navigation to a pre-fetched link "instant"). If you really can't do without it, and can't attach JS to each link to send a client-controlled value, then SameSite is probably your only viable option for CSRF protection (and the approach you describe for users with a session makes sense), but that's a bad state to be in.
Fourth, SameSite isn't nearly as strong a protection as many people assume. Even leaving aside browsers that don't implement it (RIP IE, but some people still use it or ancient Android versions or so on), the scope of a "site" is far broader than the browser's concept of an Origin (as seen in features like same-origin policy, cross-origin resource sharing, and the Origin header). Origin requires a strict match on protocol, domain, and port. Site ignores protocol and port, and handles domain in an odd way: the "site" for a domain is determined by the first element of the domain that has a suffix on the Public Suffix List. In practice, this means that all subdomains of your site are going to be considered the same site for purposes of the SameSite flag (unless your site is itself a public suffix, as e.g. github.io is), and if an attacker can carry out a subdomain takeover attack (or get the victim to access your site over a different port or protocol), the attacker can set cookies and possibly read existing ones.
Some final notes:
- There's no need to go out of your way to do constant-time comparisons of HMACs; the computation of an HMAC (or any other cryptographically secure hash) makes iterative timing attacks impossible (the attacker can't vary the input in such a way that there's a single controllable change in the output.
- For comparing a random value in an anti-CSRF cookie against the same value in server-side state, though, you should use a constant-time check. Alternatively, hash/HMAC the value from the cookie (and store the hash/HMAC in the server-side state) to get the built-in protection against timing attacks and also provide a trivial bit of additional protection in the event of somebody getting read access on your DB.
- There exists a header called
Sec-Fetch-Site, which you can use to tell whether a request was made same-origin, cross-origin but same-site, cross-site, or by the user directly selecting a URL (by typing, opening a bookmark, etc. as opposed to navigating from another page by clicking a link, submitting a form, being navigated by script, etc.). Its even less supported than SameSite (Safari doesn't send it, and on browsers that do you need a more recent version), and opening a link from another app (e.g. a chat or email client) looks like the user entering the URL rather than like the user navigating from somewhere (which wouldn't matter, security-wise, if your GETs were safe like they're supposed to be), but for defense-in-depth it might help some?
