Asymmetric Subversion Attacks on Signature Schemes

Subversion attacks against cryptosystems have already received wide attentions since several decades ago, while the Snowden revelations in 2013 reemphasized the need to further exploring potential avenues for undermining the cryptography in practice. In this work, inspired by the kleptographic attacks introduced by Young and Yung in 1990s [Crypto'96], we initiate a formal study of asymmetric subversion attacks against signature schemes. Our contributions can be summarized as follows. - We provide a formal definition of asymmetric subversion model for signature schemes. Our asymmetric model improves the existing symmetric subversion model proposed by Ateniese, Magri and Venturi [CCS'15] in the sense that the undetectability is strengthened and the signing key recoverability is defined as a strong subversion attack goal. - We introduce a special type of signature schemes that are splittable and show how to universally mount the subversion attack against such signature schemes in the asymmetric subversion model. Compared with the symmetric attacks introduced by Ateniese, Magri and Venturi [CCS'15], our proposed attack enables much more efficient key recovery that is independent of the signing key size. Our asymmetric subversion framework is somewhat conceptually simple but well demonstrates that subversion attacks against signature schemes could be quite practical, and thus increases awareness and spurs the search for deterrents.