Zero-Value Register Attack on Elliptic Curve Cryptosystem

摘要

Differential power analysis (DPA) might break implementations of elliptic curve cryptosystem (ECC) on memory constraint devices. Goubin proposed a variant of DPA using a point (0, y), which is not randomized in Jacobian coordinates or in an isomorphic class. This point often exists in standardized elliptic curves, and we have to care this attack. In this paper, we propose zero-value register attack as an extension of Goubin's attack. Note that even if a point has no zero-value coordinate, auxiliary registers might take zero value. We investigate these zero-value registers that cannot be randomized by the above randomization. Indeed, we have found several points P = (x, y) which cause the zero-value registers, e.g., (1) 3x~2 + a = 0, (2) 5x~4+2ax~2 - 4bx + a~2 = 0, (3) P is y-coordinate self-collision point, etc. We demonstrate the elliptic curves recommended in SECG that have these points. Interestingly, some conditions required for zero-value register attack depend on explicit implementation of addition formulae — in order to resist this type of attacks, we have to care how to implement the addition formulae. Finally, we note that Goubin's attack and the proposed attack assume that a base point P can be chosen by attackers and a secret scalar d is fixed, so that they are not applicable to ECDSA.