Paper 2025/977

A Novel Leakage Model in OpenSSL’s Miller-Rabin Primality Test

Abstract

At CRYPTO 2009, Heninger and Shacham presented a branch-and-prune algorithm for reconstructing an RSA private key given a random fraction of its private components. This method has been widely adopted in side-channel attacks, and its complexity is closely related to the specific leakage pattern encountered. In this work, we propose a new leakage model that enables efficient key reconstruction by exploiting a vulnerability in the modular exponentiation invoked by OpenSSL's implementation of Miller-Rabin primality test. This vulnerability reveals the least significant $b$ bits of each window. Through our proposed model, these bits form new leakage patterns, which we term aligned and misaligned. In particular, the misaligned case includes previously undocumented scenarios where full key recovery is achievable without branching. Then we analyze the global and local behavior of key reconstruction under these patterns. Our evaluation demonstrates that they yield more efficient key reconstruction and maintain this advantage even in the presence of additional erasures. Moreover, in specific scenarios, successful reconstruction remains practical even if the bits obtained are less than 50\%. Finally, we conducted a series of experiments to confirm the practicality of our work, successfully recovering the lower 4 bits from each 6-bit window and demonstrating efficient key reconstruction under our model.