# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
For leaking longer secrets, like cryptographic keys, the gain is even bigger. ## 8 Options for Kleptographic Shared Key Agreement

Our attacks frequently require that \(\mathsf{Auth}_{U}\) and \(adv\) share a secret key. A shared key is established with the Diffie-Hellman key agreement. We use its two versions:

Figure 6: The figure show the ratio (Equation (3)) for the Hamming code and BCH code. * **Ephemeral-static version**, where an authenticator knows the \"public\" kleptographic key \(Y\) of the adversary such that \(Y=g^{y}\), where \(g\) defines a prime order (sub)group, and \(y\) is the adversary's (static) private kleptographic key. The authenticator determines the ephemeral component: it generates \(k\) at random, transmits \(g^{k}\) hidden in FIDO2 communication, and computes the master shared key as \(K=Y^{k}\). The adversary learns \(g^{k}\) and computes \((g^{k})^{y}\). The advantage of this version is that only one value must be sent hidden in the regular FIDO2 message exchange. On the other hand, leaking \(y\) exposes all authenticators where \(Y\) is used. * **Ephemeral-ephemeral version** where no public key known in advance. Both parties send freshly generated components: an authenticator picks random \(k_{A}\) and sends \(g^{k_{A}}\), and the server picks random \(k_{S}\) and sends \(g^{k_{S}}\). Both parties can compute the master shared key \(K=g^{k_{A}\cdot k_{S}}\). In this case, two messages must be hidden in FIDO2 traffic. The DH messages will be hidden in random strings sent by WebAuth. The problem is how to map group elements into binary strings so that the mapping result is uniformly distributed. There are some constructions that can achieve this:

* Probabilistic Bias Removal Method (PBRM) [14],
* Binary twisted elliptic curves [44],
* Elligator [34; 40; 41]. PBRM solves the following problem: assume that a random variable \(X\) is uniformly distributed in \(\{0,1,\ldots,B-1\}\), and this random variable is going to be transferred through a channel where it should be perceived as a random variable \(X^{\prime}\) uniformly distributed in \(\{0,1,\ldots,M-1\}\), for \(M\
eq N\). It is also assumed that \(M>B>M/2\). A typical example is that \(B\) is a prime number and \(M=2^{n}\) for some \(n\). An unpleasant property of the PBRM method is that encoding may take more than one iteration, and the runtime is random. This should not be a problem if the mapping is performed by a server. However, variances in execution time for an authenticator may reveal rogue activities. The second method, based on binary twisted elliptic curves, is fast but only works on bit strings, and is therefore not suitable for, for example, converting values from a prime field. The method is based on the observation that any bit string \(x\) of length \(n\) is either the \(x\)-coordinate of a point of an elliptic curve defined over the field \(\mathbb{F}_{2^{n}}\), or of a point in its twisted curve. This creates problems in the case of the ephemeral-ephemeral DH protocol, as Adv and Aut\({}_{U}\) may choose points on different curves, while it is required to have points on the same curve. Thus, a covert secret agreement may fail in roughly 50% of cases. The most promising is the Elligator method. Its first variant [40] utilizes an injective map \(\iota\) that maps \(S=\{0,1,2,\ldots,\frac{q-1}{2}\}\), where \(q\) is a power of an odd prime, into a single elliptic curve \(E(\mathbb{F}_{q})\). Not every curve might be utilized for this version; in particular, the order of \(E(\mathbb{F}_{q})\) must be divisible by 2. Since \(\iota\) is injective, and since about half of the field elements are taken as its arguments, by the Hasse Theorem, about half of the points of \(E(\mathbb{F}_{q})\) belong to the image of \(\iota\). Therefore, a randomly chosen point \(P\in E(\mathbb{F}_{q})\) belongs to the image of \(\iota\) with probability very close to \(\frac{1}{2}\). Luckily, \(\iota\) is easy to invert, so rejection sampling can be applied to find \(P\in E(\mathbb{F}_{q})\) that belongs to the image of \(\iota\).