# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
```
Input: \(t\) consecutive signatures \(s_{1},\ldots,s_{t}\) created by Algorithm 5, private \(\text{\rm kleptographic key }y\) Procedure\(\text{\rm IdDerive}(s_{1},\ldots,s_{t},y)\) for\(i=1,\ldots,t\)do  derive \(G_{i}(=g^{k_{i}})\) from signature \(s_{i}\) for\(i=1,\ldots,t\)do \(K_{i}\leftarrow(g^{k_{i}})^{y}\) \(P_{i}\leftarrow\text{\rm Hash}(K_{i})\), \(P_{i}^{\prime}\leftarrow\text{\rm Hash}(K_{i}^{-1})\) \(\tilde{R}_{i}\leftarrow\text{\rm min}(P_{i},P_{i}^{\prime})\) /* \(\tilde{R}_{i}\) equals the corresponding \(R_{\pi(\rho(i))}\) from Alg. 5 */ if\(\tilde{R}_{i}=P_{i}\)then \(\text{\rm id}[i]\gets 0\) else \(\text{\rm id}[i]\gets 1\) \(\theta\leftarrow\) permutation that converts \(\tilde{R}_{1},\ldots,\tilde{R}_{t}\) into an ordered sequence \(\pi\leftarrow\theta^{-1}\) \(m\leftarrow\) the \(a-t\)-bit binary representation of \(\pi\) for\(j=0\)to\(a-t-1\)do \(\text{\rm id}[a-j]\gets m[j]\) return\(\text{\rm id}[1]\ldots\text{\rm id}[a]\)
```

**Algorithm 6** Deriving \(id_{U}\) by \(\text{\rm Adv}\). The number of bits that can be transmitted in this way equals \(t+\lfloor\log(t!)\rfloor\). For example, for \(t=40\), one can encode 264 bits, which is enough to leak a secret key for many standard schemes. ### Attack 4: Signature Tagging with a Proof

The attacks from Sections 4.1-4.3 can be easily converted to attack where \(\text{\rm Adv}\) can create a proof for a third party \(T\). Note that given the signatures from \(\text{\rm Aut}\), the party \(T\) can perform the same steps as \(\text{\rm Adv}\) except for rising to power \(y\). The results for these operationscan be provided by [PERSON] with non-interactive zero knowledge proofs of equality of discrete logarithms for all these operations. ### Attack 5: Correlated Secret Keys with a Shared Secret

In this attack, \(\mathsf{Auth}_{U}\) creates secret keys \(\mathsf{sk}_{0}\), \(\mathsf{sk}_{1}\) with different services so that [PERSON] may detect that the corresponding public keys \(\mathsf{pk}_{0}\) and \(\mathsf{pk}_{1}\) originate from the same device. Alternatively, \(\mathsf{sk}_{0}\) might be the main secret key assigned to user \(U\) with \(\mathsf{pk}_{0}=g^{\mathsf{sk}_{0}}\) known to Adv. **Attack prerequisites:**

* \(\mathsf{Auth}_{U}\) and Adv share a secret \(K_{U}\) (this can be achieved on-the-fly; see Section 8). * Adv knows the public keys used for FIDO2 authentication with different servers. **Attack result:**

Given a public key \(\mathsf{pk}_{1}\), created by \(\mathsf{Auth}_{U}\) for interaction with server \(S_{1}\), Adv can derive the key \(\mathsf{pk}_{2}\) that \(\mathsf{Auth}_{U}\) would create for interaction with server \(S_{2}\). This procedure will fail if \(\mathsf{pk}_{1}\) does not originate from \(\mathsf{Auth}_{U}\). **Algorithm:**

The registration procedure is modified on the side of \(\mathsf{Auth}_{U}\). Instead of choosing \(\mathsf{sk}_{2}\) at random, the following steps are executed (see Algorithm 7). ```
Input: shared secret \(K_{U}\), private key \(\mathsf{sk}_{1}\) used by Auth with server \(S_{1}\), identifiers \(id_{S_{1}}\), \(id_{S_{2}}\) of servers \(S_{1}\), \(S_{2}\) Procedure \(\mathsf{skTwo}(sk_{1},K_{U},id_{S_{1}},id_{S_{2}})\) \(z\leftarrow\mathsf{DRNG}(K_{U},id_{S_{1}},id_{S_{2}})\) \(\mathsf{sk}_{2}\leftarrow\mathsf{sk}_{1}+z\pmod{\text{\rm group order}})\) return\(\mathsf{sk}_{2}\)
```

**Algorithm 8** Deriving \(\mathsf{pk}_{2}\) dependent on \(\mathsf{pk}_{1}\) by Adv. The attack enables Adv to reproduce the public keys of \(\mathsf{Auth}_{U}\) but not the private keys, so impersonation in this way is impossible. However, for certain signature schemes, [PERSON] would be able to convert a signature over \((ad,h_{r})\) verifiable with key \(\mathsf{pk}_{1}\) to a signature over the same \((ad,h_{r})\) and verifiable with key \(\mathsf{pk}_{2}\). However, \(h_{r}\) is a random parameter chosen anew during each execution, so in practice, it should never repeat. Moreover, \(id_{S_{1}}\) is contained in the \(ad\) of the first signature, so the signature will not be valid for \(S_{2}\).