Crashing Modulus Attack on Modular Squaring for Rabin Cryptosystem
This work addresses security flaws in lightweight cryptosystems used for RFID tags, presenting a novel fault attack that could compromise unique ID protection, though it is incremental in the context of existing side-channel attack research.
The authors tackled the vulnerability of the Rabin cryptosystem to side-channel attacks by introducing a crashing modulus attack, which requires only one fault in the public key and achieves over 50% success in simulations with multiple faults. They developed a complete message reconstruction algorithm and an exact formula for candidate messages, addressing cases where the message and perturbed public key are not relatively prime.
The Rabin cryptosystem has been proposed protect the unique ID (UID) in radio-frequency identification tags. The Rabin cryptosystem is a type of lightweight public key system that is theoretetically quite secure; however it is vulnerable to several side-channel attacks. In this paper, a crashing modulus attack is presented as a new fault attack on modular squaring during Rabin encryption. This attack requires only one fault in the public key if its perturbed public key can be factored. Our simulation results indicate that the attack is more than 50\% successful with several faults in practical time. A complicated situation arises when reconstrucing the message, including the UID, from ciphertext, i.e., the message and the perturbed public key are not relatively prime. We present a complete and mathematically rigorous message reconstruction algorithm for such a case. Moreover, we propose an exact formula to obtain a number of candidate messages. We show that the number is not generally equal to a power of two.