# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
Let \(v\) be the \(b\)-bit sequence of \(R\) starting at position \(L+1\). For every \(\mathrm{id}_{i}\in I\), if \(\mathsf{Long}(\mathrm{id}_{i})\) contains sequence \(v\) on positions \(j\cdot b+1\) through \((j+1)\cdot b\), then \(S[\mathrm{id}_{i}]:=S[\mathrm{id}_{i}]+1\). Let us observe that for \(\mathrm{id}_{i}\
eq\mathrm{id}_{U}\), the counter \(S[\mathrm{id}_{i}]\) is incremented with the probability \(2^{-b}\), provided that we treat \(\mathsf{Long}\) as a random function (so, \(\mathsf{Long}(\mathrm{id}_{U})\) and \(\mathsf{Long}(id_{i})\) are stochastically independent). In turn, if \(\mathrm{id}_{i}=\mathrm{id}_{U}\), then \(S[\mathrm{id}_{i}]\) is incremented with probability \(1-(1-2^{-b})^{m}\). For example, for \(m=b=3\), \(S[\mathrm{id}_{U}]\) is incremented with probability \(\approx 0.33\), and with probability \(0.125\) on the remaining positions of \(S\). ### Attack 3: Signature Tagging with Permutation

This attack improves the leakage bandwidth with a technique borrowed from [31]. **Attack prerequisites:**

1. The same as in Section 4.1, except for the last condition;
2. Adv has access to all signatures created by \(\mathsf{Aut}_{U}\) in a certain fixed interval of FIDO2 executions;
3. Auth can create in advance and store \(t\) ephemeral random parameters \(k\) used for signing; \(t\) is a parameter determining the bandwidth of the covert information channel. **Attack result:**

Adv learns the \(\mathrm{id}_{U}\) of the user hidden behind identifier \(\mathrm{uid}_{U}\). **Auxiliary techniques:**

They are the same as in Section 4.1, plus the following encoding via permutation:

**Encoding via permutation:**: We convert permutations over \(\mathbb{S}_{t}\) to integers. For this purpose, one can use Algorithm P and the \"factorial number system\" (see [32], (Section 3.3.2)). **Algorithm:**

Assume that \(\mathrm{id}_{U}\) consists of \(2^{a}\) bits. The attack requires a sequence of \(t\) signatures that \(\mathsf{Aut}_{U}\) and Adv agree upon (e.g., \(t\) consecutive signatures after some triggering moment). The parameter \(t\) must be chosen so that a permutation over \(\mathbb{S}_{t}\) can be used to encode a \(b\)-bit number, where \(b+t\geq a\). In the procedure presented below, the first \(t\) bits of \(\mathrm{id}_{U}\) are leaked directly via the two rabbits trick, while the remaining \(a-t\) bits are encoded via a permutation \(\pi\in\mathbb{S}_{t}\). ```
Input: \"public\"leptographic key \(Y\), identifier \(id_{U}\) of length \(a\), number of signatures \(t\) Output: \(k_{1},\ldots,k_{t}\) ProcedurePreparingList\((Y,id_{U},t)\) \(x_{1},\ldots,x_{t}\leftarrow\text{\rm Rand}(t)\) for\(i=1\)to\(t\)do \(Z_{i}\leftarrow\gamma_{i}\) \(R_{i}\leftarrow\min(\text{\rm Hash}(Z_{i}),\text{\rm Hash}(Z_{i}^{-1}))\) if\(R_{i}=\text{\rm Hash}(Z)\)then \(x_{i}^{\prime}\gets x_{i}\) else \(x_{i}^{\prime}\leftarrow-x_{i}\) \(R_{i}(1)\) - \(\gamma_{i}\leftarrow\text{\rm Sort}(R_{i},\ldots,R_{t})\) /* sorting in ascending order */ \(\pi\leftarrow\) permutation such that \(\pi\) encodes \(a-t\) least significant bits of \(id_{U}\) for\(i=1\)to\(t\)do \(\zeta_{i}\leftarrow x_{i}^{\prime}\) /* thus \(R_{i}(t)=\text{\rm Hash}(Y^{i})*/\) iftheth most significant bit of \(id_{U}\) is 0 then \(k_{i}\leftarrow\zeta_{i(i)}\) /* \(k_{i}=\zeta_{i(i)}\) /* else \(k_{i}\leftarrow-\zeta_{i(i)}\) /* \(k_{i}=-\zeta_{i(i)}=-\kappa_{n(i)}\) /* / /* Note that \(\text{\rm Hash}(Y^{i})=\text{\rm Hash}(Y^{i}\rho(i))=R_{n(i)}\) ifand only ifthe \(i\)th most significant bit of \(id_{U}\) is 0 */ return\(k_{1},\ldots,k_{t}\)
```

**Algorithm 5** Preparing a list of parameters by the authenticator in advance. During the \(i\)th execution of FIDO2 devoted to leaking \(id_{U}\), \(\text{\rm Aut}_{U}\) uses already stored \(k_{i}\) to create the signature. Otherwise, the signature is created in the standard way.