# FIDO2 Facing Kleptographic Threats By-Design
## 4 Linking Attacks with Discrete Logarithm Signatures
### Attack 2: Identity Sieve via Rejection Sampling Attack prerequisites:
It is known that the expected number of steps to recover all \(n\) bits is \(n\cdot H_{n}\), where \(H_{n}=\sum_{k=1}^{n}\frac{1}{k}\) is the \(n\)th harmonic number. Let us apply an error-correcting code. Let \(n^{\prime}\) be the number of bits of the encoded message. Of course, \(n^{\prime}>n\), so we seem to lose by necessity to leak more bits. On the other hand, we do not need to collect all bits. If the code enables us to correct up to \(t\) errors, we may replace the missing bits by zeroes and run the error correction procedure. So it suffices to leak \(n^{\prime}-t\) bits out of \(n^{\prime}\). One can calculate that the expected time becomes \(n^{\prime}\cdot(H_{n^{\prime}}-H_{t})\). Although the method seems straightforward, most error correction codes have a fixed block size and can be applied to strings with a length that is a multiple of the block size. Typically, an error-correcting code has two parameters: \(m\) is a size parameter, and \(t\) is the number of errors that can be corrected. Let \(n(m,t)\) denote the number of bits in the original string and \(n^{\prime}(m,t)\) total number of bits of its error-correcting code. So, using an error-correcting code makes sense if

\[R(m,t)=\frac{n(m,t)H_{n(m,t)}}{n^{\prime}(m,t)(H_{n^{\prime}(m,t)}-H_{t})}{>1} \tag{3}\]

Below, we discuss this problem for concrete examples where the leaked data are a Polish personal identity number (PESEL) or a phone number, both with \(11\) decimal digits. To encode each digit, we use \(4\) bits. This results in a bit string with \(44\) bits. For binary Hamming codes, the code length is typically \(n^{\prime}=2^{m}-1\), where \(m\) is a positive integer. The length of the message to be encoded is \(n=2^{m}-m-1\). Hamming codes can correct up to one error, i.e., \(t=1\). In Figure 6, we see that Hamming codes may reduce the expected time to leak a secret. However, it does not mean that we can save time for any length of the leaked message. For example, for \(n=44\), collecting all bits without error correction requires, on average, \(44\cdot H_{44}\approx 192.4\) steps. For Hamming codes, we have to take \(m=6\) and a Hamming code with \(n^{\prime}=2^{6}-1=63\) bits. Then, the expected time to recover the secret is \(n^{\prime}(H_{n^{\prime}}-H_{t})=63\cdot(H_{63}-H_{1})\approx 234.88\). In this case, the Hamming codes are useless. Bose-Chaudhuri-Hocquenghem (BCH) codes can correct more than one error. According to [43], for code length \(n^{\prime}=2^{m}-1\), a BCH code can correct up to \(t\) errors, where the input string has length \(n=2^{m}-1-r(m,t)\geq 2^{m}-1-mt\), where \(r(m,t)\) is a function bounded by \(mt\). In Figure 6, we provide plots of the ratio \(R(m,t)\) for different values of \(t\) and \(m\). These plots illustrate that the \(R\) ratio is above 1 for relatively small values of \(m\), indicating that error correction using BCH codes can be beneficial even with moderate code lengths. For our example, we consider the following configurations of the BCH codes:

* For \(n^{\prime}=63\), which corresponds to \(m=6\), we have the following:
* When correcting \(t=2\) errors, the number of information bits is \(n=63-6\cdot 2=51\);
* When correcting \(t=3\) errors, the number of information bits is \(n=63-6\cdot 3=45\). * For \(n^{\prime}=127\), which corresponds to \(m=7\), we can correct 4 errors. Thus, \(n=127-7\cdot 4=99\) bits. The expected times to recover the secret with these BCH codes and with no codes are as follows: \begin{tabular}{l l l l l} \hline \hline \(\mathbf{n^{\prime}}\) & \(\mathbf{n}\) & \(\mathbf{t}\) & \(\mathbf{n}\,\mathbf{H_{n}}\) & \(\mathbf{n^{\prime}}\,(\mathbf{H_{n^{\prime}}}-\mathbf{H_{t}})\) \\ \hline
63 & 51 & 2 & 230.46 & 203.38 \\
63 & 45 & 3 & 197.77 & 182.38 \\
127 & 99 & 4 & 512.56 & 424.43 \\ \hline \hline \end{tabular} 

In our example of an 11-digit secret, a 63-bit BCH code correcting 3 errors allows for the transmission of 45 bits of information with an expected time of 182.38, outperforming the 192.40 expected time for transmitting 44 bits without error correction.