# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
We also present an impersonation attack, in which we point at a capability of the RSA backdoor that, to our knowledge, has not been discussed in the literature so far. That is, we point to the possibility of transmitting a ciphertext in a prime factor of the RSA modulus. ### Diffie-Hellman Protocol in the RSA Modulus

Let us recall a fragment of GetPrimesFast(bits,\(e\),\(s_{pub}\),\(s_{priv}\)) procedure from [38] (Algorithm 15). ```
Input:bits--the number of bits of the resulting modulus, \(e\)--the public exponent of the RSA key, \(s_{pub}\)--the \(x\)-coordinate of an elliptic curve point being the ephemeral part of the DH protocol, \(s_{priv}\)--the shared secret, that is the \(x\)-coordinate of the elliptic curve point \(u\cdot Y_{a}\) resulting from the ephemeral-static DH protocol (for details see [38]) Output: a pair of primes \((p_{1},q_{1})\)acceptable for RSA
1 Procedure GetPrimesFast(bits,\(e,s_{pub},s_{priv}\))
2 len\(\leftarrow\) bits/2\(p_{1}\leftarrow\)GenPrimeWithOracleIncr\((s_{priv},\mathsf{len},e)\)
3\(\mu\leftarrow\) bits\(-(8+m+1)\)\(/*m+1\) is the length of \(s_{pub}\) */
4 choose \(r_{1}\in_{R}\{0,1\}^{7}\) and \(r_{2}\in_{R}\{0,1\}^{\mu}\)
5\(n_{c}\gets 1||r_{1}||s_{pub}||r_{2}\)
6 solve for \((q_{1},r)\) in \(n_{c}=q_{1}p_{1}+r\), where \(r<p_{1}\)
7...
```

**Algorithm 15** Fragment of the procedure for fast primes generation. Let us explain a few details. In line 2, the length of prime numbers is determined. In line 3, the first prime \(p_{1}\) is generated from the seed \(s_{priv}\). The exponent \(e\) must be co-prime to the order of the multiplicative group; hence, the condition \(\gcd(p_{1}-1,e)=1\) is verified when running the GenPrimeWithOracleIncr function. In line 4, the size \(\mu\) of random tail \(r_{2}\) is set: in [38], the length of \(s_{pub}\) is denoted as \(m+1\), and \(s_{pub}\) placed in the RSA modulus is prefixed with 8 bits, \(1||r_{1}\), where \(r_{1}\) is a 7-bit random string. In line 6, the first approximation \(n_{c}\) of the RSA modulus is found. In the next line, the first approximation of the second prime \(q_{1}\) is determined; however, \(q_{1}\) is probably not a prime. The next steps of the procedure, omitted above, consist of setting the least significant bit of \(q_{1}\) and incrementing \(q_{1}\) by 2 until a prime number is found. The procedure GetPrimesFast includes loops, and sometimes the execution path returns to line 5, but \(p_{1}\) and \(s_{pub}\) remain unchanged. By the Prime Number Theorem, the number \(t\) of increments by 2 of the number \(q_{1}\) has the expected value \(O(\ln(q_{1}))\). Let \(q_{1}^{\prime}\) denote the value of \(q_{1}\) just after the last execution of line 5 and after setting the least significant bit. Then, for the final \(q_{1}\), we have

\[p_{1}\cdot q_{1}\approx p_{1}\cdot(q_{1}^{\prime}+2t)\approx(n_{c}-r)+2t\cdot p _{1}=n_{c}+(2t\cdot p_{1}-r). \tag{1}\]

For a 2048-bit RSA modulus, we have \(\ln(q_{1})\leq\ln(2^{1024}-1)\approx 710\). For a 4096-bit RSA modulus, the upper bound is around 1420. Therefore, taking into account the carry bits and the variance in the search of prime \(q_{1}\), it seems that usually no more than len+64 least significant bits of the \(n_{c}\) calculated in line 6 will be affected by the component \(2t\cdot p_{1}-r\). Consequently, the value \(s_{pub}\) residing in the area of the most significant bits of \(n_{c}\) is not at risk of being changed by the component \(2t\cdot p_{1}-r\), and it will be available to Adv directly from the RSA modulus. The value \(s_{pub}\) has just 257 bits in length: in [38], a pair of twisted elliptic curves over a binary field \(\mathbb{F}_{2^{m}}\), where \(m=257\), is defined. The element \(s_{pub}\) is represented in [38] as a compressed point \((x,ybit)\): the \(x\)-coordinate and one bit of the \(y\)-coordinate. That is why \(m+1\) is used in line 4 of the procedure GetPrimesFast. However, just the \(x\)-coordinate of the point is enough; hence, the expression \(m+1\) can be replaced by the value 257.