Abstract
In the aftermath of the Snowden revelations in 2013, concerns about the integrity and security of cryptographic systems have grown significantly. As adversaries with substantial resources might attempt to subvert cryptographic algorithms and undermine their intended security guarantees, the need for subversion-resilient cryptography has become paramount. Security properties are preserved in subversion-resilient schemes, even if the adversary implements the scheme used in the security experiment. This paper addresses this pressing concern by introducing novel constructions of subversion-resilient signatures and hash functions while proving the subversion-resilience of existing cryptographic primitives. Our main contribution is the first construction of subversion-resilient signatures under complete subversion in the offline watchdog model (with trusted amalgamation) without relying on random oracles. We demonstrate that one-way permutations naturally yield subversion-resilient one-way functions, thereby enabling us to establish the subversion-resilience of Lamport signatures, assuming a trusted comparison is available. Additionally, we develop subversion-resilient target-collision-resistant hash functions using a trusted XOR. By leveraging this approach, we expand the arsenal of cryptographic tools that can withstand potential subversion attacks. Our research builds upon previous work in the offline watchdog model with trusted amalgamation (Russell et al. ASIACRYPT’16) and subversion-resilient pseudo-random functions (Bemmann et al. ACNS’23), culminating in the formal proof of subversion-resilience for the classical Naor-Yung signature construction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Assuming universal watchdogs that do not depend on the adversary, which is the class of watchdogs we aim for in this work. For a deeper discussion on stateful subversion consider [27].
- 2.
In [2], only subverted signing algorithms are considered while both key generation and verification algorithms are assumed to be trusted.
- 3.
Unfortunately, we were not able to find an explicit reference for this construction.
- 4.
This resembles the ‘classical’ security proof of the construction.
- 5.
This prevents complications and allows us to identify each prefix uniquely.
- 6.
As is the case for tree-based signatures.
References
Armour, M., Poettering, B.: Algorithm substitution attacks against receivers. Int. J. Inf. Secur. 21(5), 1027–1050 (2022)
Ateniese, G., Magri, B., Venturi, D.: Subversion-resilient signature schemes. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015: 22nd Conference on Computer and Communications Security, pp. 364–375. ACM Press, October 2015
Baek, J., Susilo, W., Kim, J., Chow, Y.W.: Subversion in practice: how to efficiently undermine signatures. Cryptology ePrint Archive, Report 2018/1201 (2018). https://eprint.iacr.org/2018/1201
Bellare, M., Jaeger, J., Kane, D.: Mass-surveillance without the state: strongly undetectable algorithm-substitution attacks. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015: 22nd Conference on Computer and Communications Security, pp. 1431–1440. ACM Press, October 2015
Bellare, M., Paterson, K.G., Rogaway, P.: Security of symmetric encryption against mass surveillance. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology - CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 1–19. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_1
Bemmann, P., Berndt, S., Diemert, D., Eisenbarth, T., Jager, T.: Subversion-resilient authenticated encryption without random oracles. In: Tibouchi, M., Wang, X. (eds.) ACNS. LNCS, vol. 13906, pp. 460–483. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-33491-7_17
Bemmann, P., Chen, R., Jager, T.: Subversion-resilient public key encryption with practical watchdogs. In: Garay, J. (ed.) PKC 2021: 24th International Conference on Theory and Practice of Public Key Cryptography, Part I. LNCS, vol. 12710, pp. 627–658. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-75245-3_23
Berndt, S., Liskiewicz, M.: Algorithm substitution attacks from a steganographic perspective. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security, pp. 1649–1660. ACM Press, October/November 2017
Berndt, S., Wichelmann, J., Pott, C., Traving, T.H., Eisenbarth, T.: ASAP: algorithm substitution attacks on cryptographic protocols. In: Suga, Y., Sakurai, K., Ding, X., Sako, K. (eds.) ASIACCS 2022: 17th ACM Symposium on Information, Computer and Communications Security, pp. 712–726. ACM Press, May/June 2022
Chakraborty, S., Dziembowski, S., Nielsen, J.B.: Reverse firewalls for actively secure MPCs. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology - CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 732–762. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-56880-1_26
Chen, R., Huang, X., Yung, M.: Subvert KEM to break DEM: practical algorithm-substitution attacks on public-key encryption. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 98–128. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64834-3_4
Chen, R., Mu, Y., Yang, G., Susilo, W., Guo, F., Zhang, M.: Cryptographic reverse firewall via malleable smooth projective hash functions. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology - ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 844–876. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_31
Chow, S.S.M., Russell, A., Tang, Q., Yung, M., Zhao, Y., Zhou, H.S.: Let a non-barking watchdog bite: cliptographic signatures with an offline watchdog. In: Lin, D., Sako, K. (eds.) PKC 2019: 22nd International Conference on Theory and Practice of Public Key Cryptography, Part I. LNCS, vol. 11442, pp. 221–251. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-17253-4_8
Degabriele, J.P., Farshim, P., Poettering, B.: A more cautious approach to security against mass surveillance. In: Leander, G. (ed.) Fast Software Encryption - FSE 2015. LNCS, vol. 9054, pp. 579–598. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_28
Dodis, Y., Mironov, I., Stephens-Davidowitz, N.: Message transmission with reverse firewalls–secure communication on corrupted machines. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology - CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 341–372. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_13
Fischlin, M., Mazaheri, S.: Self-guarding cryptographic protocols against algorithm substitution attacks. In: Chong, S., Delaune, S. (eds.) CSF 2018: IEEE 31st Computer Security Foundations Symposium, pp. 76–90. IEEE Computer Society Press (2018)
Galteland, H., Gjøsteen, K.: Subliminal channels in post-quantum digital signature schemes. Cryptology ePrint Archive, Report 2019/574 (2019). https://eprint.iacr.org/2019/574
Katz, J., Lindell, Y.: Introduction to Modern Cryptography, 2nd edn. CRC Press, New York (2014)
Lamport, L.: Constructing digital signatures from a one-way function. Technical report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979
Liu, C., Chen, R., Wang, Y., Wang, Y.: Asymmetric subversion attacks on signature schemes. In: Susilo, W., Yang, G. (eds.) ACISP 2018: 23rd Australasian Conference on Information Security and Privacy. LNCS, vol. 10946, pp. 376–395. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-93638-3_22
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) Advances in Cryptology - CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990). https://doi.org/10.1007/0-387-34805-0_21
Mironov, I., Stephens-Davidowitz, N.: Cryptographic reverse firewalls. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 657–686. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_22
Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci. 58(2), 336–375 (1999)
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: 21st Annual ACM Symposium on Theory of Computing, pp. 33–43. ACM Press, May 1989
Perlroth, N., Larson, J., Shane, S.: Secret documents reveal NSA campaign against encryption (2013). https://archive.nytimes.com/www.nytimes.com/interactive/2013/09/05/us/documents-reveal-nsa-campaign-against-encryption.html
Discussion about Kyber’s tweaked FO transform (2023). https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/WFRDl8DqYQ4, Discussion Thread on the PQC mailing list
Russell, A., Tang, Q., Yung, M., Zhou, H.S.: Cliptography: clipping the power of kleptographic attacks. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology - ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 34–64. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_2
Russell, A., Tang, Q., Yung, M., Zhou, H.S.: Generic semantic security against a kleptographic adversary. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security, pp. 907–922. ACM Press, October/November 2017
Russell, A., Tang, Q., Yung, M., Zhou, H.S.: Correcting subverted random oracles. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology - CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 241–271. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-96881-0_9
Teseleanu, G.: Threshold kleptographic attacks on discrete logarithm based signatures. In: Lange, T., Dunkelman, O. (eds.) Progress in Cryptology - LATINCRYPT 2017: 5th International Conference on Cryptology and Information Security in Latin America. LNCS, vol. 11368, pp. 401–414. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-25283-0_21
Young, A., Yung, M.: The dark side of “black-box” cryptography, or: should we trust capstone? In: Koblitz, N. (ed.) Advances in Cryptology – CRYPTO 1996. LNCS, vol. 1109, pp. 89–103. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_8
Young, A., Yung, M.: Kleptography: using cryptography against cryptography. In: Fumy, W. (ed.) Advances in Cryptology - EUROCRYPT 1997. LNCS, vol. 1233, pp. 62–74. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_6
Acknowledgements
The authors would like to thank all anonymous reviewers for their valuable comments. The work of Rongmao Chen is supported by the National Natural Science Foundation of China (Grant No. 62122092, No. 62032005).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bemmann, P., Berndt, S., Chen, R. (2024). Subversion-Resilient Signatures Without Random Oracles. In: Pöpper, C., Batina, L. (eds) Applied Cryptography and Network Security. ACNS 2024. Lecture Notes in Computer Science, vol 14583. Springer, Cham. https://doi.org/10.1007/978-3-031-54770-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-54770-6_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-54769-0
Online ISBN: 978-3-031-54770-6
eBook Packages: Computer ScienceComputer Science (R0)