(1) Am I missing something? What is the real security provided by tokens in this case?
Suppose you shop at Home Despot and IKING and they store payment information. Suppose Home Despot is breached and evil Freedonian hackers steal all the stored payment information. What can we do?
If Home Despot was storing your long-term credit card information, then you have to get a new credit card. Worse, so do the eight million other people who used it. And until you get a new credit card, you can't buy a new longcouch at IKING—but until the breach is discovered, the pirates who breached Home Despot can!
If Home Despot was merely storing a per-site pseudorandom function of your payment information, then:
- only Home Despot has to get a new thing (in their case, a new security department)—you and the eight million other schmucks who shopped there can keep your credit cards
- presumably the Home Despot tokens work only at Home Despot, so the pirates are unable to refurnish their living quarters with new longcouches from IKING on your shilling
(2) Are tokens generated by PRFs? If a PRP is considered "secure" (so it cannot be distinguised from a "secure" PRF and its outputs look like random strings) can PRPs be used to create PRFs to generate tokens? For example, a cipher block with random keys used to generate tokens.
As long as you see well under $2^{b/2}$ input/output pairs for a PRP, a PRP is a good PRF. Of course, if the key gets leaked, all bets are off. For a keyed hash like HMAC-SHA256, which has PRF security and a little more, at least if a key gets leaked an adversary is limited to brute force search to find the input (like a credit card number) that might have gone into it to yield an output they found stored in a database. So, while a PRP is a pretty good PRF, there are qualitative differences that might lead you to want to choose something with stronger security like HMAC-SHA256 or keyed BLAKE2 or KMAC128 instead.
(3) Additionally, tokens that are 128 bits long and are never changed will operate correctly (in probability) up to $2^{64}$ generated tokens, after which we can expect the system to fail? (due to collisions)
It's unclear to me exactly how the tokens are used and I'm too lazy to read beyond the page you linked. But suppose it works as follows—a scheme I just pulled out of my cloaca on the spot:
- Home Despot is assigned a secret key $k$ known only to Squipe, Silicon Valley's hottest new payment processor.
- When Evelyn T. Shopster enters her credit card information at Home Despot's web site using Squipe's gooey webplet, Squipe stores Evelyn's name and credit card number, and computes for Home Despot the token $t = \operatorname{HMAC-SHA256/128}_k(m)$ where $m$ is the message:
The bearer of this token is authorized to charge the credit card of Evelyn T. Shopster. (Here $\operatorname{HMAC-SHA256/128}$ is the 128-bit truncation of HMAC-SHA256.)
- When Home Despot wants to charge the card, it sends the charge amount, Evelyn's name, and $t$ to Squipe.
- On receipt of a charge request with token $t$ and name
name, Squipe computes $\operatorname{HMAC-SHA256/128}_k(m')$ on the message $m'$ computed by The bearer of this token is authorized to charge the credit card of ${name}., and checks (in constant time!) whether the result is the same as $t$.
In this protocol, it doesn't matter if there is a collision between tokens, because one token cannot be used for another user; for any particular user you might try to abuse a token for, there's still only about a $1/2^{128}$ chance that it will work.
On the other hand, there are cases in which collisions could matter—for example, $2^{64}$ queries to an oracle for HMAC-MD5 under a secret key can lead to forgery with high probability. (This isn't because MD5 is broken—only MD5's collision resistance is broken; the same attack applies to HMAC with any 128-bit hash.)
