# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
```
Input: ProcedureRegisterS()  choose \(\ell\) at random \(L\gets g^{\ell}\) \(uid\leftarrow\) encoding of \(L\) return\(uid\), store \(\ell\) for the future use
```

**Algorithm 11**\(uid\) selection by \(S\). The core element of this procedure is encoding \(L\) in \(uid\). The base-point \(g\) belongs to the domain parameters used for the signature scheme. Therefore, the two-stage procedure composed from the Elligator Squared [34] and the Probabilistic Bias Removal Method [14] (see Section 8 for details) should be utilized to uniformly encode \(L\) as a bit-string \(uid\). Note that in both versions of the WebAuthm protocol, the server \(S\) may choose \(uid\) to be long enough to encode hidden \(L\) (\(uid\) is also called \"user handle\" and the specification [35] states in Section 14.6.1 that \"It is RECOMMENDED to let the user handle be 64 random bytes, and store this value in the user's account\"). Apart from sending the group element, the server \(S\) must indicate which curve has been chosen for the key agreement. The same curve must be chosen by \(\mathsf{Aut}_{U}\) as the domain parameters for the signature scheme. Therefore, the preference list that the server sends to the authenticator is a natural and legal place to indicate the curve (for details, see Section 8.3). Following the FIDO2 specification, \(uid\), \(id_{S}\), and the server's preference list are delivered to the authenticator \(\mathsf{Aut}_{U}\) by the client, unaware of the evil intent of \(S\) and \(\mathsf{Aut}_{U}\). Note that, unlike other parameters from \(S\), the identifier \(uid\) is not hashed before delivering to the authenticator. This is the key feature enabling efficient attack. \(\mathsf{Aut}_{U}\) recognizes \(id_{S}\) of the \"colluding server\" and follows the registration procedure by creating a dedicated key pair \((\mathsf{pk},\mathsf{sk})\) using the curve indicated by the server. The key \(\mathsf{sk}\) is chosen uniformly at random, and the messages are returned to the client following the FIDO2 specification. However, \(\mathsf{Aut}_{U}\) internally executes the following steps (Algorithm 12):

```
Input:\(uid\) obtained during registration from \(S\) ProcedureReset(\(uid\)) \(L\leftarrow\) the result of decoding \(uid\) choose \(k\) at random \(T\leftarrow\mathsf{Hash}(x(L^{k}))\) /* \(x(V)\) is the \(x\)-coordinate of the point \(V\) */  reset the seed of DRNG of \(\mathsf{Aut}_{U}\) with \(T\) return store \(k\) for the 1 st authentication with \(S\)
```

**Algorithm 12** Resetting DRNG by \(\mathsf{Aut}_{U}\). From now on, DRNG of \(\mathsf{Aut}_{U}\) creates all random numbers based on the seed \(T\), but \(S\) still has to learn \(T\). This is achieved during the first authentication of \(\mathsf{Aut}_{U}\) against \(S\). Namely, \(\mathsf{Aut}_{U}\) creates the signature in a specific way (Algorithm 13). ```
Input: strings \(ad,h_{r}\) to be signed according to interaction with the server, secret key \(\mathsf{sk}\) to be used for authentication with \(S\) Procedure \(\mathsf{Sign}-\mathsf{Leak}(\mathsf{sk},(ad,h_{r})\)  retrieve \(k\) stored by Algorithm 12 from internal memory execute signature creation with ephemeral \(k\) return the signature
```

**Algorithm 13** Leaking seed \(T\). During the first authentication, \(S\) can recover the seed \(T\) of the DRNG of \(\mathsf{Aut}_{U}\) in the following way (Algorithm 14). ```
Input: signature \(s\) received from \(\mathsf{Aut}_{U}\), \(\ell\) stored during registration of \(\mathsf{Aut}_{U}\) Procedure \(\mathsf{Seed}-\mathsf{Calculate}(s)\) retrieve \(\ell\) stored by Algorithm 11 when registering \(\mathsf{Aut}_{U}\) \(r\leftarrow\) the ephemeral value \(g^{k}\) from signature \(s\) \(T\leftarrow\mathsf{Hash}(x(r^{\ell}))\) return\(T\)
```

**Algorithm 14** Recalculating seed \(T\). From now on, \(S\) knows all random values generated by \(\mathsf{Aut}_{U}\), so it, in particular, may recalculate all secret keys generated during registrations that occur after the first authentication with \(S\).