Kleptographic (algorithmic) backdoors in~the~RSA~key~generator

A. V. Markelova

Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 14-34.

Résumé

A cryptographic (algorithmic) backdoor is the ability of the backdoor key owner to gain an unauthorized access to user's secret information embedded in the cryptoalgorithm. There are two independent classifications of backdoors: by the level of cryptographic strength (weak, symmetric, asymmetric backdoor) and by the method of implementing undeclared capabilities (based on covert channel or on implicit weakening of the cryptoalgorithm). We present examples of each type of backdoor and discuss a method for constructing an asymmetric backdoor based on an implicit weakening of the algorithm in the RSA key generator. Let it be required to generate a public module of the RSA key $n=pq$, $|n|=L$. We will generate such prime numbers that $|p|=|q|={L}/{2}$. Let $D$ be the backdoor parameter, $|D|=K$; $ID$ is the identifier of the generator instance; $i$ is the key generation counter; $\psi_s(a, ID, i)$ is a one-way (trapdoor) function with the trapdoor $s$ on the first argument. Let $(a, D)=1$ and $$r'(a, D, r_0)= \begin{cases} \min\{r:r\geq r_0; (rD+a) \text{ is prime}\}, \text{if } r{} 2^{{L}/{2}-K}\text{ and }rD+a{}2^{{L}/{2}};\\ 0, \text{otherwise.} \end{cases}$$ Let's choose the function $R(x, y, z, i)$ and define $r_{ID}^{(i)}(a, D)=r'(a, D, R(a, D, ID, i))$. For any random $a_p\in\mathbb{Z}_D^*$ and $r'_0\in\mathbb{Z}$, $({2^{{L}/{2}-1}})/{D}$, the following values are uniquely determined: \begin{gather*} p = r_{ID}^{(i)}(a_p, D)D + a_p,\\ q = r'(\psi_s(a_p, ID, i) a_p^{-1}\bmod D,D,r'_0) D + \psi_s(a_p, ID, i) a_p^{-1}\bmod D. \end{gather*} At the same time, if $r_{ID}^{(i)}(\cdot)\neq 0$ and $r'(\cdot)\neq 0$, then the numbers $p$ and $q$ are prime, $|p|=|q|={L}/{2}$, $|n|=|pq|\in\{L-1, L\}$. If the numbers $p$ and $q$ are generated in this way, then, provided that the secret $s$ is known, the public module $n=pq$ can be factorized in polynomial time of the key length. Really, $p = r_{ID}^{(i)}(\psi_s^{-1}(n\bmod D, ID, i), D) D + \psi_s^{-1}(n\bmod D, ID, i)$. This approach allows to develop a cryptographically strong key generator, even if the adversary knows the methods used and has access to the source code of the key generator. This allows us to use a backdoor generator even in open source systems. Cryptographic strength depends on the choice of algorithm parameters: in particular, on the level of cryptographic strength of the function $\psi_s(a, ID, i)$.

Détail

Mots-clés : RSA
Keywords: kleptography, algorithmic backdoor, trapdoor, kleptographic backdoor, backdoor.

Bibliographie

[1] A. Young, M. Yung, “Kleptography: using cryptography against cryptography”, EUROCRYPT-97, LNCS, 1233, 1998, 62–74 | MR

[2] R. J. Anderson, “Practical RSA trapdoor”, Electronics Lett., 29:11 (1993), 995 | DOI

[3] FBI ‘planted backdoor’ in OpenBSD, , 2010 https://www.theregister.com/2010/12/15/openbsd_backdoor_claim

[4] A. E. Zhukov, “Kriptosistemy so vstroennymi lazeikami”, BYTE/Rossiya, 2007, no. 2, 45–51

[5] D. J. Bernstein, T. Lange, R. Niederhagen, “Dual EC: A standardized back door”, The New Codebreakers, LNCS, 9100, 2016, 256–281 | MR | Zbl

[6] Y. Desmedt, “Abuses in cryptography and how to fight them”, LNCS, 403, 1990, 375–389 | MR

[7] A. K. Lenstra, “Generating RSA moduli with a predetermined portion”, LNCS, 1514, 1998, 1–10 | Zbl

[8] C. Crépeau, A. Slakmon, “Simple backdoors for RSA key generation”, LNCS, 2612, 2003, 403–416 | MR | Zbl

[9] M. Blaze, “Protocol failure in the Escrowed Encryption Standard”, Proc. CCS-94, 1994 http://www.mattblaze.org/papers/eesproto.pdf

[10] 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

[11] I. Levy, C. Robinson, Principles for a More Informed Exceptional Access Debate, , 2018 https://www.lawfareblog.com/principles-more-informed-exceptional-access-debate

[12] E. Barker, J. Kelsey, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST Special Publication 800-90, June 2006 https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-90.pdf

[13] J. Menn, 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

[14] K. Thomson, “Reflection on trusting trust”, Comm. ACM, 27:8 (1984), 761–763 | DOI

[15] B. Schneier, Evaluating the GCHQ Exceptional Access Proposal, January 17, 2019 https://www.lawfareblog.com/evaluating-gchq-exceptional-access-proposal

[16] A. V. Markelova, “Embedding asymmetric backdoors into the RSA key generator”, J. Computer Virology Hacking Techniques, 17 (2021), 37–46 | DOI

[17] Metodicheskii dokument. Metodika opredeleniya ugroz bezopasnosti informatsii, Utverzhden FSTEK Rossii 5 fevralya 2021 g.

[18] B. A. Pogorelov, V. N. Sachkov (red.), Slovar kriptograficheskikh terminov, Izd-vo MTsMNO, M., 2006

[19] A. E. Zhukov, A. V. Markelova, “Kriptografiya i kleptografiya: skrytye kanaly i lazeiki v kriptoalgoritmakh”, Informatsionnaya bezopasnost, 2019, no. 1, 36–41

[20] A. Young, M. Yung, Malicious Cryptography. Exposing Cryptovirology, Wiley Publ, 2004, 392 pp. | MR

[21] GOST R 53113.1-2008. Informatsionnaya tekhnologiya. Zaschita informatsionnykh tekhnologii i avtomatizirovannykh sistem ot ugroz informatsionnoi bezopasnosti, realizuemykh s ispolzovaniem skrytykh kanalov. Ch. 1. Obschie polozheniya, Standartinform, M., 2018

[22] R. L. Rivest, A. Shamir, L. M. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM, 21 (1978), 120–126 | DOI | MR | Zbl

[23] A. E. Zhukov, A. V. Markelova, “Kriptografiya i kleptografiya. Skrytye kanaly i kleptograficheskie zakladki na ikh osnove v kriptosisteme RSA”, Zaschita informatsii. Insaid, 2020, no. 2 (92), 58–67

[24] P. Svenda, M. Nemec, P. Sekan et al., “The million-key question — investigating the origins of RSA public keys”, Proc. 25th USENIX Security-16, USENIX Association, 2016, 893–910

[25] M. Nemec, M. Sys, P. Svenda et al., “The return of Coppersmith's attack: Practical factorization of widely used RSA moduli”, Proc. CCS-17, ACM, 2017, 1631–1648

[26] B. S. Kaliski, “Anderson's RSA trapdoor can be broken”, Electronics Lett., 29:15 (1993), 1387 | DOI

[27] G. Devenport, Multiplikativnaya teoriya chisel, Nauka, M., 1971, 200 pp. | MR

[28] D. Knut, Iskusstvo programmirovaniya, v. 2, Poluchislennye algoritmy, 3-e izd., Vilyams, M., 2001, 832 pp. | MR

[29] A. Young, M. Yung, “The dark side of black-box cryptography”, CRYPTO-96, LNCS, 1109, 1997, 89–103 | MR

[30] Yu. V. Linnik, “On the least prime in an arithmetic progression I. The basic theorem”, Matem. sb., 15(57):2 (1944), 139–178 | MR | Zbl