Subversion in Practice: How to Efficiently Undermine Signatures

Algorithm substitution attack (ASA) on signatures can have severe consequences as the authentication services of numerous systems and applications rely on signature schemes. In this paper, we present a highly efficient ASA on the widely-used digital signature algorithm (DSA). Compared with the generic ASAs on signature schemes proposed in the literature, our attack provides fast and undetectable subversion, which can extract the user's private signing key by collecting the maximum three signatures arbitrarily. Moreover, our ASA is proven to be robust against state reset. We implemented the proposed ASA by replacing the original DSA in Libgcrypt (a popular cryptographic library used in many applications) with our subverted DSA. Our experiment shows that the user's private key can readily be recovered once the subverted DSA is used to sign messages. In our implementation, various measures have been considered to significantly reduce the possibility of detection through comparing the running time of the original DSA and the subverted one (i.e. timing analysis). To our knowledge, this is the first implementation of the ASA in practice, which shows that the ASA is a real threat rather than only theoretical speculation.