A suggestion for limiting token "stockpiling"

[timmclean]

Token stockpiling

An attacker who wishes to bypass many CAPTCHAs in the future could intentionally trigger CAPTCHAs (e.g. by first running attacks through a particular IP) and save the resulting tokens for later.

[TODO: We don't have a great answer for this. Halp!]

One possibility is to limit how long tokens remain valid, which limits how long an attacker has to build up their stockpile.

It would be nice if this could be implemented by adding an expiry timestamp to the token, i.e. the CAPTCHA service would sign something like:

<nonce> || <expiry-timestamp>

Clearly, though, this does not work in this protocol, since the challenge service can't see what it's signing and therefore can't validate the expiry timestamp. An attacker could obtain tokens that expire in 1 year, and spend the next year collecting tokens.

Fortunately, there are other ways to bound a token's validity period. I suggest accomplishing this using multiple challenge service keys:

• The challenge service generates one new signing key pair for each day that it is online.
• When the challenge service signs tokens, it indicates to the plugin the last day of validity of this batch of tokens (so that the plugin can throw away old tokens automatically).
• When the edge validates a token, it only accepts tokens that were signed by one of the challenge service's recent key pairs.

This makes things like "only accept tokens from yesterday or today" possible. At the same time, it's straightforward to scale this scheme to higher (hourly) or lower (weekly) resolution -- just change how often the challenge service generates new key pairs.

There's an issue remaining: how does the edge obtain the challenge service's new keys? I see a few options, but assuming that there's only one (or a few) challenge services per edge, it probably just makes the most sense for the edge to query the challenge service periodically. This is made even easier by the fact that a challenge service can precompute, say, a year's worth of key pairs, and provide those public keys to the edge ahead of time.

I don't know if this is a perfect match for your threat model, but I thought I'd submit this anyway in case it's helpful!

Cheers Tim

[burdges]

If done through Taler with the auditor approach, then token lifetime is controlled by the denomination key, which largely mitigates the threat model concerns. I'd suggest lifetimes of 1 week or 1 month, but that's still much shorter than the TBB release cycle lifetime we'd get through key pinning.

[burdges]

There is however a big advantage to @gtank's approach of pinning the keys : In principle, tokens signed with a special denomination key could be used for tracking a user, so the Tor project would need to control the auditor key that controls their issuance. And that gives the Tor project a key that if stolen could possibly be used for some forms of tracking. Pinning avoids that.

Another approach : Any TBB release contains the hash of the next 24 (resp. 204) denomination keys precomputed by by the Tor project. Every month (resp. week), the Tor project gives CloudFlare their denomination key for that month (resp. week). There are variations like MQV that allow CloudFlare to be the sole possessor of the key, of course.