# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
In [37], the prime \(p_{1}\) is generated in a slightly different manner: only the upper half of \(p_{1}\) is generated from the shared seed \(s_{priv}\), and the half with least significant bits is allowed to be random. According to [37], the modulus can be efficiently factorized by [PERSON]: knowledge of the \(\frac{\mathsf{bits}}{4}\) most significant bits of \(p_{1}\) suffices to run the [PERSON]'s attack [42] to find \(p_{1},q_{1}\). Accordingly, we modify the accelerated attack from [38], where the prime \(p_{1}\) is generated in the following way:

* First, a bit string of length len is obtained from a DRNG with the seed \(s_{priv}\) (so the entire number \(p_{1}\) is obtained); the two most significant bits and the least significant bit of \(p_{1}\) are set to '1'. * The next step is to increment \(p_{1}\) by 2 until \(p_{1}\) becomes a prime number. The procedure includes loops, and sometimes the execution path goes back to regenerate the number \(p_{1}\) by the DRNG seeded with \(s_{priv}\). In such a case, the next block of len pseudorandom bits is taken from the generator, and the two uppermost bits and the least significant bit of \(p_{1}\) are again set to '1'. As previously, by the Prime Number Theorem, the expected number \(t^{\prime}\) of increments by 2 of the number \(p_{1}\) is \(O(\ln(p_{1}))\). Let \(p_{1}^{\prime}\) denote the value of \(p_{1}\) immediately after taking it from the generator for the last time and setting the least significant bit and the two uppermost bits to '1'. Then, for the final \(p_{1}\), we have \[p_{1}\approx p_{1}^{\prime}+2t^{\prime}.\] (2)

We modify the above procedure. Instead of taking len bits from a generator and assigning them to \(p_{1}\) (initially, and each time when \(p_{1}\) is re-generated), we apply the following steps:We expect that the buffer \(\alpha_{3}\) is usually large enough to completely absorb all the increments (2). Knowledge of the bit string \(\alpha_{1}\) is sufficient for [PERSON] to factorize RSA modulus with the [PERSON]'s attack. Having the factor \(p_{1}\), the adversary can compare it with the output \(\alpha\) of the generator and immediately recovers \(m\). Algorithm: The shared secret established with the help of the DH protocol is used to seed the pseudorandom number generator. The first portion of the output bits from this generator is used to generate the first ciphertext, that is, the one to be embedded in the upper half of the RSA modulus. The next portions are consumed on demand to generate the bit strings \(\alpha\) needed by Algorithm 16. ```
Input: the seed \(s_{\mathit{pri}}\), message \(m\) to be encrypted of length \(\frac{\mathrm{km}}{2}-64\) ProcedureGenerate\((s_{\mathit{min}},m)\) \(\alpha\leftarrow\)DRR(\(s_{\mathit{pri}}\),len) split \(\alpha\leftarrow\alpha_{1}\|\alpha_{2}\|_{3}\) where \(\alpha_{1}\), \(\alpha_{2}\), \(\alpha_{3}\) consist of \(\frac{\mathrm{km}}{2}\), \(\frac{\mathrm{km}}{2}-64\), \(64\) bits, correspondingly \(p_{1}\gets\alpha_{1}\|_{2}\times 2\times m\|/\alpha_{3}\) return\(p_{1}\)
```

**Algorithm 16** Modified method of generating \(p_{1}\). Remark 3: _A simplified attack version can be implemented to make factorization faster for Adv. That is, exactly like in [38], the entire number \(p_{1}\) is generated from the shared seed \(s_{\mathit{priv}}\), not just its upper half. However, one ciphertext can still be embedded in the most significant area of the generated modulus, as in the case of the linking attack._

## 7 Leakage Acceleration with Error Correcting Codes

In the remaining part of the paper, we explain some technical details and ideas that have already been used but not discussed in depth. In this section, we discuss encoding \(C\) used in Section 4.1. Specifically, let us consider a secret message consisting of \(n\) bits that is leaked one bit at a time at a random position, with possible repetitions. This is an instance of the Coupon Collector's Problem.