# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:  
They are the same as in Section 4.1 but with the following addition:  
1. The adversary [PERSON] has a set of potential identities \(I\), which may contain \(\mathsf{id}_{U}\) of \(\mathsf{Aut}_{U}\). **Attack result:**  
[PERSON] will fish out the identities from \(I\) that may correspond to \(\mathsf{Aut}_{U}\) or find that none of them corresponds to \(\mathsf{Aut}_{U}\). **Auxiliary techniques:**  
**Long pseudorandom identifier:**: Instead of \(\mathsf{id}_{U}\), a long pseudorandom identifier \(\mathsf{Long}(\mathsf{id}_{U})\) is used. Simply, use a cryptographic DRNG (deterministic random number generator, e.g., one recommended by NIST): \(\mathsf{Long}(\mathsf{id}_{U})\) are the first \(N\) output bits of \(\mathsf{DRNG}(\mathsf{id}_{U})\). **Rejection sampling with errors:**: We take into account that the authenticator must run the protocol without suspicious delays and failures. So, we use the rejection sampling technique, where the output is taken after a few trials, even if it is invalid from the information leakage point of view. **Two rabbits trick:**: This may also be used, but we skip it here for clarity of presentation. **Algorithm:**  
Assume that \(\mathsf{Long}(\mathsf{id}_{U})\) consists of \(2^{L}\)\(b\)-bit blocks. The parameter \(L\) is big enough to avoid collisions, while \(b\) is very small, like \(b=3\). In particular, \(2^{L}>L+b\). The signing algorithm run by an authenticator is modified. Instead of choosing \(k\) at random, Algorithm 3 is executed (rejection sampling with at most \(m-1\) backtracking steps). ```
Input: a \"public\" kleptographic key \(Y=\bar{g}^{\prime}\), user identifier \(\mathsf{id}_{U}\), upper bound \(m\) on the number of backtracking steps Output:\(k\) Procedure ChooseKeyRysR(\(Y,\mathsf{id}_{U},m\)) \((b,L)\leftarrow\mathsf{GetLongLen}(\mathsf{Long}(\mathsf{id}_{U}))\) \(/*\left|\mathsf{Long}(\mathsf{id}_{U})\right|_{\text{bin}}=2^{L}\cdot b*/\) \(i\gets 1\) while\(i<m\)do \(k\leftarrow\mathsf{Rand}()\) \(R\leftarrow\mathsf{Hash}(Y^{k})\) \(j\leftarrow\) the binary number represented by \(L\) most significant bits of \(R\) \(v\leftarrow\) the string of \(b\) least significant bits of \(R\) \(w\leftarrow\) the string of \(b\) bits of \(\mathsf{Long}(\mathsf{id}_{U})\) that starts at position \(j\cdot b+1\) if\(p=w\)then 1 return\(k\) \(i\gets i+1\) return\(k\)
```  
**Algorithm 3** Selection of parameter \(k\) using rejection sampling by authenticator. From the point of view of [PERSON], each obtained signature is a witness indicating whether a given \(\mathsf{id}\) may correspond to \(\mathsf{Aut}_{U}\). Due to the bound \(m\) on the number of backtracking steps, false witnesses are possible. When receiving a signature, [PERSON] executes Algorithm 4 to gather statistics for identities from \(I\). Let \(S\) be the table holding the current statistics. Initially, \(S[\mathsf{id}_{i}]=0\) for each \(\mathsf{id}_{i}\in I\)```
Input: a secret kleptographic key \(y\), signature \(sig\), table with current statistics \(S[]\), parameters \(b\) and \(L\) as used by Algorithm 3 Output: Updated table with statistics \(S[]\) Procedure UpdateStat(\(y,sig,S[]\)) \(P\leftarrow\)\(\texttt{GetSpeneral}\langle sig\rangle\) /* \(P\) equals \(g^{k}\) from signature construction */ \(K\gets Pg\) \(R\leftarrow\)Hash\((K)\) \(j\leftarrow\) the binary number represented by \(L\) most significant bits of \(R\) \(\triangleright\) (the string of \(b\) least significant bits of \(R\) for\(id_{i}\in L\)do \(\triangleright\)\(b\)-bit substring of \(\mathsf{Long}(\mathrm{id}_{i})\) starting at position \(j\) if\(w=\texttt{then}\) \(S[\mathrm{id}_{i}]\gets S[\mathrm{id}_{i}]+1\) return\(S[]\)
```

**Algorithm 4** Updating statistics. Retrieve \(g^{k}\) from the signature (\(k\) is unavailable to Adv, but standard signature schemes enable either reconstructing \(g^{k}\) or provide it directly). Calculate \(K=(g^{k})^{y}\). Compute \(R=\mathsf{Hash}(K)\). Set \(j\) to \(L\) most significant bits of \(R\).