### Subversion in Practice: How to Efficiently Undermine Signatures

Joonsang Baek, Willy Susilo, 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysisdigital signaturesimplementation
Contact author(s)
baek @ uow edu au
History
Short URL
https://ia.cr/2018/1201

CC BY

BibTeX

@misc{cryptoeprint:2018/1201,
author = {Joonsang Baek and Willy Susilo and Jongkil Kim and Yang-Wai Chow},
title = {Subversion in Practice: How to Efficiently Undermine Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2018/1201},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/1201}},
url = {https://eprint.iacr.org/2018/1201}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.