# Cryptographically linkable random tokens

Are there any algorithms/protocols that let you produce a specific length of random tokens/bits in such a way that you can cryptographically determine which 2 or more tokens/bitstrings where produced using the same seed/key. Is it possible at all?

For example, if I produce these random bits: 12432, 15693, with key A and 57322, 57483 with key B. I want a third party who gets 12432 and 15693 to be able to determine they were both produced under the same key.

I thought of digital signatures as the obvious solution. However digital signatures will be to long for my requirement. I would like the token to be between 10-20 bits long, any pointers will be greatly appreciated.

Requirements:

1. The third party should be able to verify the tokens are valid.
2. Ideally, the third party should be unable to forge tokens.
3. Tokens must be unique to a single key.
• Can you provide a quick example of what you're expecting? Sep 22 '15 at 16:00
• yes so if i produce these random bits: 12432, 15693, with key A and 57322, 57483 with key b. I want a third party who gets 12432 and 15693 to be able to determine they were both produced under the same key for example. Makes any sense? thanks @RoraZ
– user3312054
Sep 22 '15 at 16:11
• Create a public/private key pair. Generate a random value and sign it with the private key. Call that the random token. Sep 22 '15 at 16:33
• OK, that would work, but it would generate a slightly longer number than five digits; it would need to be more like 300 digits to be considered secure (if RSA is used as algorithm, ECDSA would fare better) Sep 22 '15 at 16:47
• @user3312054 Just to make sure we're clear: If using symmetric cryptography only, the third party will have access to the signing key. This also means the third-party will be able to spoof a signature. Using asymmetric cryptography, the third party would have a public key while you retain a private key. Then the third-party would still be able to verify, but unable to spoof, a signature. Does it really not matter, for your purposes, which is used?
– Iszi
Sep 22 '15 at 16:58

A full solution is impossible. If the third party is able to verify the validity of tokens, they can brute force through the 10-20 bit token space and generate all valid tokens. So the third party cannot both be able to validate and not be able to forge. The below solution achieves one of the two.

Tie each secret key $k_i$ to an identifier $i$. Generate tokens of the form $i||H(k_i, x)$ where $x$ is a small value. $H$ could be e.g. HMAC-SHA256 truncated to ~16 bits. For uniqueness, the generator should discard any value that collides with one before it ($x < x'$). This is still very fast due to the small domain.

Anyone who does not know the key cannot verify if the token is valid, but can look at the first bits to see whose it is if valid. Someone who has the key can iterate values of $x$ until they find one that matches or they quit (at some defined upper bound like $2^{8}$). The upper bound and the token length determine the probability that a forgery can be generated by using a random bitstring – with 8 and 16 bits the probability is about $2^{-8}$.

If the third party is trusted and the tokens generated under different keys are allowed to collide, the identifier $i$ can be omitted. Then you cannot uniquely determine who generated a particular value, however.

With a small block cipher the collisions above could be avoided. However, implementing such a block cipher securely would in my opinion be more complex than just checking for collisions. With a larger number of tokens it might not be the case.

• your answer looks interesting, however im not very clear with some parts of it. Firstly why do we need x, is that for uniqueness? and also when you say "anyone without the key can look at the first bits to see whose it is " do you mean verifying the token by 'i', and if yes, does that mean all tokens produced with key 'ki' will have the same bits at the beginning of the token?..thank you Sep 23 '15 at 10:07
• @user3312054, the $x$ is used to generate many tokens with a single key. And correct, all tokens with $k_i$ begin with the same bits to separate the value space from other keys.
– otus
Sep 23 '15 at 10:11

I see 2 options that fit the requirement (small, verifiable within some limit).

Because the sizes are small, the probability of the collision of a random value showing linked is high, larger values will obviously help.

Option 1 is to have a random value, and encrypt or hash it, then truncate the result and concatenate to the original value. The size of the value limits the pool of available tokens, and the size of the truncated output limits the probability of a collision. For example:

$A$ is a random or sequential 14-bit value, $B = HMAC_k(A)$ truncated to 16-bits.
$A || B$ is a 30-bit (5 character base64 encoded) token that can be easily verified as being linked to $k$, with a pool of 16384 maximum tokens linkable to $k$

Option 2 is to encrypt the entire value using a block cipher, and limit the inputs to a small subset of the available plaintext space. Upon decryption, only values that fall into that space will be considered valid. The cipher must have a small enough block size for your application, which limits available choices to those designed for low resource systems, like SPECK with a 32-bit block size.

• looks good, however i don't understand how you can "easily verify" a token as been linked to k...and also how you arrived to "a pool of "16384" maximum characters..thanks a lot Sep 23 '15 at 10:30
• verification is by performing the same operation, it will generate the same token. Ideally this would be done with the help of a HSM, since the key is required. $2^{14}$ = 16384 tokens Sep 23 '15 at 18:57