Cryptanalysis of the countermeasures using randomized binary signed digits

Recently, side channel attacks (SCA) have been recognized as menaces to public key cryptosystems. In SCA, an attacker observes side channel information during cryptographic operations, and reveals the secret scalar using the side channel information. On the other hand, elliptic curve cryptosystems (ECC) are suitable for implementing on smartcards. Since a scalar multiplication is a dominant step in ECC, we need to design an algorithm to compute scalar multiplication with the immunity to SCA. For this purpose, several scalar multiplication methods that utilize randomized binary-signed-digit (BSD) representations were proposed. This type of countermeasures includes Ha-Moon's countermeasure, Ebeid-Hasan's one, and Agagliate's one. In this paper we propose a novel general attack against "all" the countermeasures of this type. The proposed attack lists the candidates for the secret scalar, however straight-forward approach requires huge memory, thus it is infeasible. The proposed attack divides the table into small tables, which reduces the memory requirement. For example, the computational cost and the memory requirement of the proposed attack for revealing the 163-bit secret key are O(2⁸) and O(2²³), respectively, using 20 observations on the scalar multiplication with Ha-Moon's countermeasure. The computational cost and the memory requirement are O(2²¹) and O(2¹²) for Ebeid-Hasan's one, and O(2⁴⁰) and O(2⁶) for Agagliate's one. If 40 observations are used, computational cost for Agagliate's one is reduced to O(2³³). Whenever we utilize a countermeasure of BSD type, we should beware of the proposed attack. In other words, the security of BSD type is controversial.