# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 1: Signature Tagging Attack prerequisites:  
1. Each user \(U\) has a unique public identifier \(\mathsf{id}_{U}\) (e.g., issued by a state authority). 2. The authenticator \(\mathsf{Auth}_{U}\) of user \(U\) is aware of \(\mathsf{id}_{U}\). 3. \(\mathsf{uid}_{U}\) is the ID resulting from the registration of \(\mathsf{Auth}_{U}\) with the server \(S\). 4. \(\mathsf{Auth}_{U}\) holds the \"public\" kleptographic key \(Y\) of the attacker (see Section 8 for more details). 5. The attacker \(\mathsf{Adv}\) knows the private kleptographic key \(y\), where \(Y=g^{y}\). 6. \(\mathsf{Adv}\) knows (at least a fraction) of the signatures delivered by \(\mathsf{Auth}_{U}\) while executing FIDO2 with the server \(S\) (\(\mathsf{Adv}\) might be the target server \(S\) but it is not required). **Attack result:**: A linking attack in which \(\mathsf{Adv}\) learns \(\mathsf{id}_{U}\) of the user hidden behind identifier \(\mathsf{uid}_{U}\). **Auxiliary techniques:**:
**id expansion:**: \(\mathsf{id}_{U}\) might be compressed in the sense that its every bit is necessary to identify a user. As we will be running a Coupon Collector process, this is inefficient to learn \(n\) bits, and we have to draw at average of \(n\cdot H_{n}\) one-bit coupons. (\(H_{n}\cdot n\approx\ln(n)\)is the \(n\)th harmonic number). The idea is to apply encoding \(C(\mathsf{id}_{U})\) of \(\mathsf{id}_{U}\) such that the Coupon Collection Process can be interrupted, and the missing bits can be found by error correction. For details, see Section 7. For the sake of simplicity, we assume that \(C(\mathsf{id}_{U})\) consists of \(2^{a}\) bits. This is a technique borrowed from [30]. It enables transmitting one covert bit per signature and avoids backtracking of the rejection sampling technique. **Algorithm:**  
The attack follows the classical kleptographic trick of reusing an ephemeral value \(g^{k}\) to establish a secret shared by the authenticator and the adversary Adv. From the point of view of the authenticator, the following changes in FIDO2 execution are introduced when creating a signature. The key moment is the choice of \(k\): instead of choosing \(k\) at random, Algorithm 1 is executed. ```
Input: a \"public\" kleptographic key \(Y=g^{g}\), identifier of the user \(\mathsf{id}_{U}\) Output:\(k\) ProcedureChoose\((Y,\mathsf{id}_{U})\) \(a\leftarrow\mathsf{GetLen}(C(\mathsf{id}_{a}))\) /* a fulfills equation \(|C(\mathsf{id}_{U})|_{\text{bin}}=2^{a}*/\) \(\kappa\leftarrow\text{Rand}()\) \(Z\gets Y^{\kappa}\) \(R\leftarrow\min(\text{Hash}(Z),\text{Hash}(Z^{-1}))\) if\(R=\text{Hash}(Z)\)then \(\kappa^{\prime}\leftarrow\kappa\) else \(x^{\prime}\leftarrow-\kappa\) \(j\leftarrow\) the binary number represented by \(a\) most significant bits of \(R\) \(v\leftarrow\) the least significant bit of \(R\) \(w\leftarrow\) the \(j\)th bit of \(C(\mathsf{id}_{U})\) if\(v=w\)then \(k\gets x^{\prime}\) else \(k\leftarrow-x^{\prime}\) return\(k\)
```  
**Algorithm 1** Selection of parameter \(k\) by authenticator. From the point of view of Adv, each signature of \(\mathsf{Aut}_{U}\) leaks one bit of \(C(\mathsf{id}_{U})\). Adv executes Algorithm 2 to retrieve this bit. Recall that standard signature schemes based on the discrete logarithm problem allow either reconstructing \(g^{k}\) or directly providing it. For example, for ECDSA signatures, the scalar signature component allows to reconstruct the element needed). Thus, GetEpheneral\((sig)\) may depend on the signature scheme used.