CryptoDB
Paper: A Third is All You Need: Extended Partial Key Exposure Attack on CRTRSA with Additive Exponent Blinding
Authors: 


Download:  
Presentation:  Slides 
Conference:  ASIACRYPT 2022 
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. 
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt202232425, title={A Third is All You Need: Extended Partial Key Exposure Attack on CRTRSA with Additive Exponent Blinding}, publisher={SpringerVerlag}, author={Yuanyuan Zhou and Joop van de Pol and Yu Yu and FrançoisXavier Standaert}, year=2022 }