Subversion-resilient signatures: Definitions, constructions and applications
Authors: Giuseppe Ateniese, Bernardo Magri and DanieleVenturi. Theoretical Computer Science, Volume 820, 8 June 2020, Pages 91–122.
Inspired by the proliferation of software attacks (e.g., malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms, the authors provide a formal treatment of security of digital signatures against subversion attacks (SAs).
The main security requirement they put forward demands that a signature scheme should remain unforgeable even in the presence of an attacker applying SAs (within a certain class of allowed attacks) in a fully-adaptive and continuous fashion. Previous notions — e.g., the notion of security against algorithm-substitution attacks introduced by Bellare et al. (CRYPTO ’14) for symmetric encryption — were non-adaptive and non-continuous.
In this vein, the authors show both positive and negative results for the goal of constructing subversion-resilient signature schemes.
Negative results. They show that a broad class of randomized signature schemes is insecure against stateful SAs, even if using just a single bit of randomness. On the other hand, they establish that signature schemes with enough min-entropy are insecure against stateless SAs. The attacks they design are undetectable to the end-users (even if they know the signing key).
Positive results. They complement the above negative results by showing that signature schemes with unique signatures are subversion-resilient against all attacks that meet an undetectability requirement. A similar result was shown by Bellare et al. for symmetric encryption, who proved the necessity to rely on stateful schemes; in contrast unique signatures are stateless, and in fact they are among the fastest and most established digital signatures available.
As their second positive result, the authours show how to construct subversion-resilient identification schemes from subversion-resilient signature schemes. They finally show that it is possible to devise signature schemes secure against arbitrary tampering with the computation, by making use of an un-tamperable cryptographic reverse firewall (Mironov and Stephens-Davidowitz, EUROCRYPT ‘15), i.e., an algorithm that “sanitizes” any signature given as input (using only public information). The firewall they design allows them to successfully protect so-called re-randomizable signature schemes (which include unique signatures as a special case).
As an additional contribution, the authors extend the model to consider multiple users and show implications and separations among the various notions they introduced. While their study is mainly theoretical, due to its strong practical motivation, they believe that their results have important implications in practice and might influence the way digital signature schemes are selected or adopted in standards and protocols.
You can download the complete paper here.
Join Concordium in our different channels:
Twitter: https://twitter.com/ConcordiumNet
Discord: https://discord.gg/xWmQ5tp
Linkedin: https://www.linkedin.com/company/33433672/
Telegram: https://t.me/concordium_official
Reddit: https://www.reddit.com/r/Concordium_Official
Developers Hub: https://development.concordium.com/tech
Learn more: https://concordium.com
