# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
The only issue is to align the DRNG output with the registration moment. It may require some work and guesses, but it is still possible. Unfortunately, the secret keys created by \(\mathsf{Aut}_{U}\) before the discussed moment are also unsafe. Namely, assume that \(\mathsf{Aut}_{U}\) has registered with a service \(S^{\prime}\) before the first authentication with \(S\). In this case, \(S\) cannot derive the key \(\mathsf{sk}^{\prime\prime}\) for service \(S^{\prime}\), as it has been created before a shared seed \(T\) has been established. The key \(\mathsf{sk}^{\prime\prime}\) and its corresponding key \(\mathsf{pk}^{\prime\prime}\) cannot be changed by \(S\) since \(S\) would first have to impersonate \(\mathsf{Aut}_{U}\). Unfortunately, \(\mathsf{pk}^{\prime\prime}\) can be broken by \(\mathsf{Adv}\) in the case of standard signatures based on the discrete logarithm problem. Namely, these signatures use a one-time ephemeral value chosen at random. Typically, this ephemeral value _must not_ be revealed since, otherwise, the signing key will be leaked. However, \(S\) may derive the same ephemeral value using its clone of the DRNG used by \(\mathsf{Aut}_{U}\). So, once \(S\) learns a single signature delivered to \(S^{\prime\prime}\), it can derive \(\mathsf{sk}^{\prime\prime}\). So, the security depends solely on the secrecy of the signature returned by \(\mathsf{Aut}_{U}\). **Remark 1**. : _The element \(uid\) is not the only one to pose a threat. The random \(cid\) chosen by \(\mathsf{Aut}_{U}\) can be used similarly if the server's public key is somehow available to \(\mathsf{Aut}_{U}\)._

**Remark 2**. : _Note that if the auditor logs the first signature and can recover the secret key \(\mathsf{sk}\), then they can calculate \(T\). Indeed, for the signature \((r,s)\), where \(s=k^{-1}\cdot(h+r\cdot\mathsf{sk})\), one might define \(u_{1}=h\cdot s^{-1}\), \(u_{2}=r\cdot s^{-1}\), and then \(L^{k}=L^{u_{1}}\cdot\left(L^{\mathsf{sk}}\right)^{u_{2}}\) and the left-hand side of the equation can be recalculated. Thus, hiding requires keeping \(\mathsf{sk}\) away from an auditor. For tamper-proof authenticators, this is automatically the case._

## 6 RSA Signatures

The list of signature algorithms to be used by \(\mathsf{Aut}_{U}\) ([33], Section 3.7) also contains RSA signatures with RSA PSS and RSA PKCS v1.5 encodings. (Note, however, that according to a disclaimer, the \"list does not suggest that this algorithm is or is not allowed within any FIDO protocol\".) Both encodings are standardized in [36]. In ([33], Section 3.7), the lengths of the RSA keys are specified as follows:* 2048-bit RSA PSS;
* \(n\)-bit RSA PKCS v1.5 (\(n=2,3,4\)). That is, the RSA key length is at least 2048 bits. In the case of PSS encoding, the _salt_ field can be random. This _salt_ field is recovered by the signature verifier and thus can be used to transmit a covert message (as noted in ([36], page 36). In point 4 on page 36 of [36], we read that \"Typical salt lengths in octets are _hLen_ (the length of the output of the hash function Hash) and 0\". As a result, this channel may have a capacity of at least 256 bits. From now on, we consider that a deterministic version of the RSA signatures (RSA PKCS v1.5 or RSA PSS without random salt), makes it much harder to mount a kleptographic attack. However, a malicious manufacturer can benefit from the key generation process. The paper [37] presents aleptographic RSA key generation procedure. An accelerated version is presented in [38] (it is even faster than the OpenSSL implementation of the honest RSA key generation procedure). The papers [37; 38] use the ephemeral-static version of the DH protocol, where the ephemeral part is present in the RSA modulus. There are other ways to install a backdoor in the RSA key, cf. [39] and the references given there, but we adapt the idea presented in [37; 38] to also show the feasibility of a linking attack in the case where \(\mathsf{Aut}_{U}\) uses RSA signatures during FIDO2 execution.