The main types of algorithmic bookmarks are considered. A method for constructing asymmetric kleptographic bookmarks in the RSA key generator is presented, which allows the owner of the bookmark key (the developer or an authorized intelligence agency) to access a user key generated by an infected algorithm. Theorems illustrating the performance of the described algorithms are formulated, and the computational complexity of these algorithms is estimated. The resistance of the built tabs to some classes of attacks is demonstrated even if the adversary knows the methods used and has access to the source code of the key generator.
Download file
Counter downloads: 62
- Title Kleptographic (algorithmic) backdoors in the RSA key generator
- Headline Kleptographic (algorithmic) backdoors in the RSA key generator
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 55
- Date:
- DOI 10.17223/20710410/55/2
Keywords
RSA, kleptography, algorithmic backdoor, trapdoor, kleptographic backdoor, backdoorAuthors
References
Young A. and Yung M. Kleptography: using cryptography against cryptography // EUROCRYPT’97. LNCS. 1998. V.1233. P.62-74.
Anderson R. J. Practical RSA trapdoor // Electronics Lett. 1993. V.29. No. 11. P.995.
FBI ’planted backdoor’ in OpenBSD. 2010. https://www.theregister.com/2010/12/15/openbsd\\_backdoor\\_claim.
Жуков А. Е. Криптосистемы со встроенными лазейками // BYTE/Россия. 2007. №2. С. 45-51.
Bernstein D. J, Lange T., and Niederhagen R. Dual EC: A standardized back door // The New Codebreakers. LNCS. 2016. V.9100. P.256-281.
Desmedt Y. Abuses in cryptography and how to fight them //LNCS. 1990. V. 403. P. 375-389.
Lenstra A. K. Generating RSA moduli with a predetermined portion // LNCS. 1998. V. 1514. P. 1-10.
Crepeau C. and Slakmon A. Simple backdoors for RSA key generation // LNCS. 2003. V. 2612. P. 403-416.
Blaze M. Protocol failure in the Escrowed Encryption Standard // Proc. CCS’94. 1994. http://www.mattblaze.org/papers/eesproto.pdf.
Deputy Attorney General Rod J. Rosenstein Delivers Remarks on Encryption at the United States Naval Academ. Annapolis, MD, October 10, 2017. https://www.justice.gov/opa/speech/deputy-attorney-general-rod-j-rosenstein-delivers-remarks-encryption-united-states-naval.
Levy I. and Robinson C. Principles for a More Informed Exceptional Access Debate. 2018. https://www.lawfareblog.com/principles-more-informed-exceptional-access-debate.
Barker E. and Kelsey J. NIST Special Publication 800-90. Recommendation for Random Number Generation Using Deterministic Random Bit Generators. June 2006. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-90.pdf.
Menn J. Exclusive: Secret contract tied NSA and security industry pioneer. December 21, 2013. https://www.reuters.com/article/us-usa-security-rsa/exclusive-secret-contract-tied-nsa-and-security-industry-pioneer-idUSBRE9BJ1C220131220.
Thomson K. Reflection on trusting trust // Comm. ACM. 1984. V. 27. No. 8. P. 761-763.
Schneier B. Evaluating the GCHQ Exceptional Access Proposal. January 17, 2019. https: //www.lawfareblog.com/evaluating-gchq- exceptional-access-proposal.
Markelova A. V. Embedding asymmetric backdoors into the RSA key generator //j.Computer Virology Hacking Techniques. 2021. No. 17. P.37-46.
Методический документ. Методика определения угроз безопасности информации. Утвержден ФСТЭК России 5 февраля 2021 г.
Словарь криптографических терминов / под ред. Б. А. Погорелова, В. Н. Сачкова. М.: Изд-во МЦМНО, 2006.
Жуков А. Е., Маркелова А. В. Криптография и клептография: скрытые каналы и лазейки в криптоалгоритмах // Информационная безопасность. 2019. №1. C. 36-41.
Young A. and Yung M. Malicious Cryptography. Exposing Cryptovirology. Wiley Publ., 2004. 392 p.
ГОСТ Р 53113.1-2008. Информационная технология. Защита информационных технологий и автоматизированных систем от угроз информационной безопасности, реализуемых с использованием скрытых каналов. Ч. 1. Общие положения. М.: Стандартинформ, 2018.
Rivest R. L., Shamir A., and Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems // Comm. ACM. 1978. V. 21. P.120-126.
Жуков А. Е., Маркелова А. В. Криптография и клептография. Скрытые каналы и клептографические закладки на их основе в криптосистеме RSA // Защита информации. Инсайд. 2020. №2(92). C.58-67.
Svenda P., Nemec M., Sekan P., et al. The million-key question - investigating the origins of RSA public keys // Proc. 25th USENIX Security’16. USENIX Association, 2016. P.893-910.
Nemec M., Sys M., Svenda P., et al. The return of Coppersmith’s attack: Practical factorization of widely used RSA moduli // Proc. CCS’17. ACM, 2017. P. 1631-1648.
Kaliski B. S. Anderson’s RSA trapdoor can be broken // Electronics Lett. 1993. V. 29. No. 15. P. 1387.
Дэвенпорт Г. Мультипликативная теория чисел. М.: Наука, 1971. 200с.
Кнут Д. Искусство программированя. Т. 2. Получисленные алгоритмы. 3-е изд. М.: Вильямс, 2001. 832 с.
Young A. and Yung M. The dark side of black-box cryptography // CRYPTO’96. LNCS. 1997. V. 1109. P.89-103.
Linnik Yu. V. On the least prime in an arithmetic progression I. The basic theorem // Матем. сб. 1944. Т. 15(57). №2. С. 139-178.
Kleptographic (algorithmic) backdoors in the RSA key generator | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 55. DOI: 10.17223/20710410/55/2
Download full-text version
Counter downloads: 157