Cryptology ePrint Archive: Report 2018/1201

Subversion in Practice: How to Efficiently Undermine Signatures

Joonsang Baek and Willy Susilo and Jongkil Kim and Yang-Wai Chow

Abstract: Algorithm substitution attack (ASA) on signatures should be treated seriously as the authentication services of numerous systems and applications rely on signature schemes and compromising them has a significant impact on the security of users. We present a somewhat alarming result in this regard: a highly efficient ASA on the Digital Signature Algorithm (DSA) and its implementation. Compared with the generic ASAs on signature schemes proposed in the literature, our attack provides fast and undetectable subversion, which will extract the user's private signing key by collecting 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. 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 ASA in practice, which shows that ASA is a real threat rather than only a theoretical speculation.

Category / Keywords: public-key cryptography / cryptanalysis, digital signatures, implementation

Date: received 12 Dec 2018

Contact author: baek at uow edu au

Available format(s): PDF | BibTeX Citation

Version: 20181218:193833 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]