Paper 2022/1163
A Third is All You Need: Extended Partial Key Exposure Attack on CRTRSA with Additive Exponent Blinding
Abstract
At Eurocrypt 2022, May et al. proposed a partial key exposure (PKE) attack on CRTRSA 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 sidechannel leakage of these exponents, while a sidechannel resistant implementation of CRTRSA often uses additively blinded exponents $d^{\prime}_p = d_p + r_p(p1)$ and $d^{\prime}_q = d_q + r_q(q1)$ 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 CRTRSA 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 twostep approach to first compute the keydependent constant $k^{\prime}$ ($ed^{\prime}_p = 1 + k^{\prime}(p1)$, $ed^{\prime}_q = 1 + l^{\prime}(q1)$), 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 Coppersmithtype assumption, while our MSB attack either runs in subexponential 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 (1024bit, 2048bit, and 3072bit) and blinding factor lengths (32bit, 64bit, and 128bit), our experiments verify the validity of the Coppersmithtype 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 CRTRSA with experimentally verified effectiveness against 128bit unknown exponent blinding factors. We also demonstrate an application of the proposed PKE attack using real partial sidechannel key leakage targeting a Montgomery Ladder exponentiation CRT implementation.
Note: This is the full version of our proceeding paper.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2022
 Keywords
 Partial Key Exposure Additive Blinding CRTRSA Coppersmith method
 Contact author(s)

zhou yuanyuan @ gmail com
csjhvdp @ my bristol ac uk
yuyu @ yuyu hk
fstandae @ uclouvain be  History
 20220906: approved
 20220906: received
 See all versions
 Short URL
 https://ia.cr/2022/1163
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1163, author = {Yuanyuan Zhou and Joop van de Pol and Yu Yu and FrançoisXavier Standaert}, title = {A Third is All You Need: Extended Partial Key Exposure Attack on {CRT}{RSA} with Additive Exponent Blinding}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1163}, year = {2022}, url = {https://eprint.iacr.org/2022/1163} }