Skip to main content
placeholder image

Subversion in Practice: How to Efficiently Undermine Signatures

Journal Article


Abstract


  • 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.

Publication Date


  • 2019

Citation


  • Baek, J., Susilo, W., Kim, J. & Chow, Y. (2019). Subversion in Practice: How to Efficiently Undermine Signatures. IEEE Access, 7 68799-68811.

Scopus Eid


  • 2-s2.0-85067182231

Number Of Pages


  • 12

Start Page


  • 68799

End Page


  • 68811

Volume


  • 7

Place Of Publication


  • United States

Abstract


  • 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.

Publication Date


  • 2019

Citation


  • Baek, J., Susilo, W., Kim, J. & Chow, Y. (2019). Subversion in Practice: How to Efficiently Undermine Signatures. IEEE Access, 7 68799-68811.

Scopus Eid


  • 2-s2.0-85067182231

Number Of Pages


  • 12

Start Page


  • 68799

End Page


  • 68811

Volume


  • 7

Place Of Publication


  • United States