# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
To encode a bit \(b\), the server executes Algorithm 17 to determine the next character of \(rs\):

```
Input: a bit \(b\) of \(C\) to be encoded Output: an octet corresponding to a base64 character of \(rs\) leaking \(b\) to Adv \(\mathbf{Gen}-\mathbf{rs}(b,\mathsf{TLSkey})\) \(\kappa\leftarrow\) the next octet of the TLS key stream \(\beta\leftarrow\) lsb of \(\kappa\) \(B^{\prime}\gets B_{0}\,\mathsf{xor}\,\kappa\) \(B^{\prime\prime}\gets B_{1}\,\mathsf{xor}\,\kappa\) /* xor-ing set elements with \(\kappa*\)/  choose bit \(c\) at random with \(\Pr(c=1)=p=\frac{31}{32}\) and \(\Pr(c=0)=\frac{1}{32}\) if\(c=0\)then  choose \(\zeta\) uniformly at random from \(B^{\prime\prime}\) if\(c=1\)then if\(b=0\)then  choose \(\zeta\) uniformly at random from \(B^{\prime}\) else  choose \(\zeta\) uniformly at random from \(B^{\prime\prime}\) else  choose \(\zeta\) uniformly at random from \(B^{\prime}\) return\(\zeta\)
```

**Algorithm 17** Encoding a bit of \(C\) in an octet. Let us discuss Algorithm 17. First, note that the encrypted stream is correct from the client's point of view: \(\zeta\in B^{\prime}\cup B^{\prime\prime}\), so it is a ciphertext of a base64 url code. Therefore, the client will not detect any suspicious encoding error. For each base64 url code \(\rho\), the probability that \(\zeta\) will be the ciphertext of \(\rho\) is \(\frac{1}{64}\). Indeed, if \(\rho\in B_{0}\), then it can be chosen only for \(c=1\), and then with the conditional probability \(\frac{1}{2}\cdot\frac{1}{31}\). So, the overall probability of obtaining \(\rho\) equals \(p\cdot(\frac{1}{2}\cdot\frac{1}{31})=\frac{1}{64}\). If \(\rho\in B_{1}\), then it is chosen with probability \((1-p)\cdot\frac{1}{33}+p\cdot\frac{1}{2}\cdot\frac{1}{33}=\frac{1}{64}\). Therefore, the client will detect no irregularity concerning the statistics of occurrences of the base64 url codes in \(rs\). If \(c=1\), then \(\zeta\) always encodes \(b\) from the adversary's point of view. So, the encoding of \(b\) is correct. If \(c=0\), this is no longer true, as from the adversary's point of view, the TLS ciphertext always encodes \(1\)xor \(\beta\). So, with conditional probability \(\frac{1}{2}\), this is incorrect. Hence, the overall probability that \(b\) is not encoded correctly is \(\frac{1}{32}\cdot\frac{1}{2}=\frac{1}{64}\). So, if C is a ciphertext of length \(128\), the expected number of falsely encoded bits is \(2\). There are only \((\frac{128}{2})=8128\) options to choose \(2\) error positions out of \(128\). Eliminating the encoding errors may be dealt with in two ways. The first case is that the adversary obtains a key that can be effectively tested. For example, suppose that the plaintext of C is the seed to the generator used by the server to derive the TLS parameter \(r_{S}\). In that case, the adversary may guess the error positions, recalculate \(r_{S}\) according to the guess, and test the result against \(g^{r_{S}}\) really sent by the server. Finding the right seed is relatively easy, as the number of possible guesses is small. The second option is to insert an error detection code in the plaintext of C and use a stream cipher to create C. Both techniques can be combined. ### Attack Consequences

There are many ways to exploit the hidden channel described above. From our point of view, the main one is the possibility to deactivate the protection provided by the TLS channel against the adversary: in this case, the message hidden in \(C\) is the seed for DRNG used by the server to generate the TLS ephemeral keys \(r_{S}\). In this way, the adversary gains access to the content of the TLS channel. Then, Adv can take advantage of the linking and impersonation attacks described in the earlier sections. Defending against the described attack is not possible within TLS. It is necessary to reshape FIDO2, as it is generally risky to send unstructured random strings over TLS.