Attacking Right-to-Left Modular Exponentiation with Timely Random Faults

摘要

We show that timely induction of random failures can potentially be used to mount very cost effective attacks against smartcards deploying cryptographic schemes based on (right-to-left) modular exponentiation. We introduce a model where an external perturbation, or glitch, may cause a single modular multiplication to produce a truly random result. Based on this assumption, we present a probabilistic attack against the implemented cryptosystem. Under reasonable assumptions, we prove that using a single faulty signature the attack recovers a target bit of the secret exponent with an error probability bounded by 3/7. We show the attack is effective even in the presence of message blinding.