Energy Exhaustion Attack on Barrett's Reduction

摘要

Modular reduction is an integral part of the underlying computation in several cryptographic systems. This paper identifies a potential vulnerability in one of the most well-known reduction algorithms, namely Barrett's reduction algorithm. The vulnerability lies in the algorithm's while loop which is usually unbounded in straightforward implementation. An adversary can exploit the vulnerability by tampering with the sign flag of the processor's status register. Our work reveals that attacks exploiting such weaknesses can cause a huge amount of completely unnecessary arithmetic operations, rapidly draining energy from a cryptographic device that implements this reduction. Devices running on batteries, for example laptops and smart phones, will lose energy completely when faced with such attacks. This kind of consequences might also result if the sign flag becomes faulty due to natural causes such as voltage glitches or exposure to radiations. Countermeasures for the aforementioned vulnerability are also discussed in this paper.