Appendix F: Two methods for managing revision counters

Implementations MAY generate revision counters in any way they please, so long as they are monotonically increasing over the lifetime of each blinded public key. But to avoid fingerprinting, implementors SHOULD choose a strategy also used by other Tor implementations. Here we describe two, and additionally list some strategies that implementors should NOT use.

F.1. Increment-on-generation

This is the simplest strategy, and the one used by Tor through at least version 0.3.4.0-alpha.

Whenever using a new blinded key, the service records the highest revision counter it has used with that key. When generating a descriptor, the service uses the smallest non-negative number higher than any number it has already used.

In other words, the revision counters under this system start fresh with each blinded key as 0, 1, 2, 3, and so on.

F.2. Encrypted time in period

This scheme is what we recommend for situations when multiple service instances need to coordinate their revision counters, without an actual coordination mechanism.

Let T be the number of seconds that have elapsed since the start time of the SRV protocol run that corresponds to this descriptor, plus 1. (T must be at least 1.)

Let S be a per-time-period secret that all the service providers share. (C tor and arti use S = KS_hs_blind_id; when KS_hs_blind_id is not available, implementations may use S = KS_hs_desc_sign.)

Let K be an AES-256 key, generated as

K = H("rev-counter-generation" | S)

Use K, and AES in counter mode with IV=0, to generate a stream of T * 2 bytes. Consider these bytes as a sequence of T 16-bit little-endian words. Add these words.

Let the sum of these words, plus T, be the revision counter.

(We include T in the sum so that every increment in T adds at least one to the output.)

Cryptowiki attributes roughly this scheme to G. Bebek in:

G. Bebek. Anti-tamper database research: Inference control techniques. Technical Report EECS 433 Final Report, Case Western Reserve University, November 2002.

Although we believe it is suitable for use in this application, it is not a perfect order-preserving encryption algorithm (and all order-preserving encryption has weaknesses). Please think twice before using it for anything else.

(This scheme can be optimized pretty easily by caching the encryption of X*1, X*2, X*3, etc for some well chosen X.)

For a slow reference implementation that can generate test vectors, see src/test/ope_ref.py in the Tor source repository.

Note:

Some onion service operators have historically relied upon the behavior of this OPE scheme to provide a kind of ersatz load-balancing: they run multiple onion services, each with the the same KP_hs_id. The onion services choose different introduction points, and race each other to publish their HSDescs.

It's probably better to use Onionbalance or a similar tool for this purpose. Nonetheless, onion services implemenentations MAY choose to implement this particular OPE scheme exactly in order to provide interoperability with C tor in this use case.

F.X. Some revision-counter strategies to avoid

Though it might be tempting, implementations SHOULD NOT use the current time or the current time within the period directly as their revision counter -- doing so leaks their view of the current time, which can be used to link the onion service to other services run on the same host.

Similarly, implementations SHOULD NOT let the revision counter increase forever without resetting it -- doing so links the service across changes in the blinded public key.