Further Research on N-1 Attack against Exponentiation Algorithms

摘要

In 2005, Yen et al. firstly proposed the N - 1 attack against cryptosystems implemented based on BRIP and square-multiply-always algorithms. This attack uses the input message N - 1 to obtain relevant side-channel information from the attacked cryptosystem. In this paper we conduct an in-depth study on the N - 1 attack and find that two more special values taken as the input message also can be exploited by an attacker. According to this, we present our chosen-message attack against Boscher's right-to-left exponentiation algorithm which is a side-channel resistant exponentiation algorithm. Furthermore, immunity of the Montgomery Powering Ladder against the N - 1 attack is investigated. The result is that the Montgomery Powering Ladder is subjected to the N - 1 attack. But a different approach to retrieve the key is used which derives from the relative doubling attack. To validate our ideas, we implement the two algorithms in hardware and carry out the attacks on them. The experiment results show that our attacks are powerful attacks against these two algorithms and can be easily implemented with one power consumption curve.