Welcome to the resource topic for 2022/1163
Title:
A Third is All You Need: Extended Partial Key Exposure Attack on CRT-RSA with Additive Exponent Blinding
Authors: Yuanyuan Zhou, Joop van de Pol, Yu Yu, François-Xavier Standaert
Abstract:At Eurocrypt 2022, May et al. proposed a partial key exposure (PKE) attack on CRT-RSA that efficiently factors N knowing only a \frac{1}{3}-fraction of either most significant bits (MSBs) or least significant bits (LSBs) of private exponents d_p and d_q for public exponent e \approx N^{\frac{1}{12}}. In practice, PKE attacks typically rely on the side-channel leakage of these exponents, while a side-channel resistant implementation of CRT-RSA often uses additively blinded exponents d^{\prime}_p = d_p + r_p(p-1) and d^{\prime}_q = d_q + r_q(q-1) with unknown random blinding factors r_p and r_q, which makes PKE attacks more challenging.
Motivated by the above, we extend the PKE attack of May et al. to CRT-RSA with additive exponent blinding. While admitting r_pe\in(0,N^{\frac{1}{4}}), our extended PKE works ideally when r_pe \approx N^{\frac{1}{12}}, in which case the entire private key can be recovered using only \frac{1}{3} known MSBs or LSBs of the blinded CRT exponents d^{\prime}_p and d^{\prime}_q. Our extended PKE follows their novel two-step approach to first compute the key-dependent constant k^{\prime} (ed^{\prime}_p = 1 + k^{\prime}(p-1), ed^{\prime}_q = 1 + l^{\prime}(q-1)), and then to factor N by computing the root of a univariate polynomial modulo k^{\prime}p.
We extend their approach as follows. For the MSB case, we propose two options for the first step of the attack, either by obtaining a single estimate k^{\prime}l^{\prime} and calculating k^{\prime} via factoring, or by obtaining multiple estimates k^{\prime}l^{\prime}_1,\ldots,k^{\prime}l^{\prime}_z and calculating k^{\prime} probabilistically via GCD.
For the LSB case, we extend their approach by constructing a different univariate polynomial in the second step of the LSB attack. A formal analysis shows that our LSB attack runs in polynomial time under the standard Coppersmith-type assumption, while our MSB attack either runs in sub-exponential time with a reduced input size (the problem is reduced to factor a number of size e^2r_pr_q\approx N^{\frac{1}{6}}) or in probabilistic polynomial time under a novel heuristic assumption. Under the settings of the most common key sizes (1024-bit, 2048-bit, and 3072-bit) and blinding factor lengths (32-bit, 64-bit, and 128-bit), our experiments verify the validity of the Coppersmith-type assumption and our own assumption, as well as the feasibility of the factoring step.
To the best of our knowledge, this is the first PKE on CRT-RSA with experimentally verified effectiveness against 128-bit unknown exponent blinding factors. We also demonstrate an application of the proposed PKE attack using real partial side-channel key leakage targeting a Montgomery Ladder exponentiation CRT implementation.
ePrint: https://eprint.iacr.org/2022/1163
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .