# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
Once \(P\) is found, one can compute \(\iota^{-1}(P)\in S\). The number \(q\) is chosen to be very close to \(2^{n}\) for some \(n\), e.g., \(q=2^{251}-9\) and \(q=2^{255}-19\) (see [40]). Let \(\mathcal{N}=\{0,1,2,\ldots,2^{n-1}-1\}\). Note that the probability of choosing at random an element from \(\mathcal{N}\setminus S\) when sampling from \(\mathcal{N}\) is negligible. Consequently, \(\iota^{-1}(P)\in S\) appear to be randomly sampled from \(\mathcal{N}\). The second variant of Elligator, Elligator Squared [34], can be applied to _any_ curve, particularly to standardized curves of a prime order. In fact, the construction [34] constitutes a kind of a framework, as it works for any \(f:\mathbb{F}_{q}\to E(\mathbb{F}_{q})\) with certain properties (in particular, \(f\) and \(f^{-1}\) are efficiently computable, and the number of preimages \(f^{-1}(R)\), for randomly chosen \(R\in E(\mathbb{F}_{q})\), can also be calculated efficiently). As a result, we obtain a randomized algorithm that for a given \(P\in E(\mathbb{F}_{q})\) finds \((u,v)\in\mathbb{F}_{q}\times\mathbb{F}_{q}\) such that \(P=f(u)+f(v)\). The number of iterations of the algorithm is a random variable; however, according to experimental results [41], the algorithm is efficient. It ensures that the pairs\((u,v)\in\mathbb{F}_{q}\times\mathbb{F}_{q}\) are statistically close to uniform. For the covert DH protocol, \((u,v)\) is transmitted instead of \(P=f(u)+f(v)\). Hence, the transmission is twice as long as in the case of Elligator [40]. Moreover, an additional trick is required if \(q\) is not close to \(2^{n}\) for some \(n\). Paper [34] proposes to pack \(u\) and \(v\) as an integer \(U\) in \(\{0,1,\ldots,q^{2}-1\}\) and then transmit \(V=U+k\cdot q\) for \(k\in\{0,1,\ldots,\lfloor\frac{2^{n+t}-U}{q}\rfloor\}\) as a bit string of length \(n+t\). For sufficiently large \(t\), the statistical distance between the resulting values \(V\) and uniformly distributed bit strings of length \(n+t\) is not observable. Alternatively, _if there is no space for \(t\) additional bits_, a two-stage approach can be used: in the first step, the value \(U\) mentioned above is generated. In the second step, PBRM is applied to \(U\) to yield \(V\). The last variant [41] is the Elligator Squared implemented very efficiently on the GLS254 binary curve. Since \(q\) is a power of two this time, the resulting \((u,v)\) are naturally random bit strings. Note that the arithmetic for the GLS254 has been substantially improved [45; 46]. Below, we consider two versions of the DH protocol and check which method is better in a given situation. ### Ephemeral-Static DH Protocol

This version has the advantage of having only one message to be hidden. #### 8.1.1 Discrete Logarithm Signatures Used for Authentication

As already mentioned, for standard signatures based on discrete logarithm, the verification procedure reveals ephemeral value \(g^{k}\). The point is that this \(g^{k}\) can be used for generating a shared key as described at the beginning of this section. A proof of the security of this approach (re-using \(g^{k}\) for a different purpose) is given in [30]. In the WebAuthn protocol, \(\mathsf{Auth}_{U}\) should take into account the server preferences (see Section 8.3). Assuming that most of the servers are honest, hence their preferences being unpredictable from the point of view of the Adv, the best option is to embed on the \(\mathsf{Auth}_{U}\) a separate \"public\" key \(Y\) of the adversary Adv for each domain parameter supported by the \(\mathsf{Auth}_{U}\). #### 8.1.2 RSA Signatures Used for Authentication

For RSA signatures, the choice of domain parameters for the hidden DH protocol does not depend on the underlying protocol. The primary objective of the choice of the domain parameters should be to hide the presence of the kleptographic protocol, and to generate the secret shared key efficiently. Both goals are achieved by the construction presented in [44], and the constructions from [40; 41].