17
$\begingroup$

Someone posted an article on Reddit a few days ago, and I haven't found much about it except for links back to the same page.

And for a brief summary, essentially, it's possible to introduce a backdoor during RSA key generation. For example, to generate a backdoored RSA-1024 key. (Assuming $\text{getPrime}(x)$ will return a random $x$-bit prime number)

\begin{align} A &= \text{genPrime}(384)\\ P^\prime &= \text{genPrime}(128)\\ Q^\prime &= \text{genPrime}(128)\\ P &= Ak_1 + P^\prime \end{align}

Where $k_1$ is incremented until $P$ is prime, starting with $k_1 = P^\prime$.

\begin{align} Q = Ak_2 + Q^\prime \end{align}

$k_2$ is is calculated similarly for $Q^\prime$.
$P$ and $Q$ are then used as the prime numbers for the rest of the key generation algorithm, and $A$ is kept as the backdoor key. $A$ can be generated based off of a predictable per-user value, like a MAC address or user ID.

To use the backdoor, the attacker (or in this case, developer) recalculates $A$ in the same way it was originally calculated (or just looks it up in a database) and then calculates $N^\prime = N \mod A$ and then factors $N^\prime$ into $P^\prime$ and $Q^\prime$. This will take the complexity of factoring a 256-bit number, which is well within reach of most organisations concerned with implementing backdoors. $P^\prime$ and $Q^\prime$ can then be used to calculate $P$ and $Q$ in the same way as above, and thus generate the entire private key.

Is there any more information about this? Possible attacks? (besides the obvious one in the case that $A$ is leaked) It seems intuitive that this would lower the security of RSA, considering it's lowering the key space from 1024-bit to 256-bit, but I don't see how it can be broken without knowing $A$.

$\endgroup$
11
  • 1
    $\begingroup$ I would suggest using two different symbols for the two $k$s, as they do not refer to the same value. $\endgroup$
    – orlp
    Jan 24, 2016 at 21:54
  • $\begingroup$ @orlp I edited the post to use $k_1$ and $k_2$, thanks for the suggestion. $\endgroup$
    – Daffy
    Jan 24, 2016 at 21:57
  • $\begingroup$ @fgrieu There are two different keyspaces here. One assuming an agent with knowledge of $A$, and one without that knowledge. Presumably, if you know $A$ the key space is $256$ bits. $\endgroup$
    – orlp
    Jan 24, 2016 at 22:16
  • 2
    $\begingroup$ @poncho There's a misunderstanding here. I mean from a purely theoretical perspective, there are $2^{256}$ possible keys per user (since the value of $A$ is fixed per user), which is less than $2^{1024}$ for normal RSA. I'm not sure what advantage this would give an attacker other than the developer of this backdoored software, but that's why I'm posting it here. I'm trying to see if there's actual work done on this or if it was just created off the top of someone's head last Tuesday. $\endgroup$
    – Daffy
    Jan 25, 2016 at 4:14
  • 1
    $\begingroup$ There's my article on RSA backdoor with working c# code here: kukuruku.co/hub/infosec/backdoor-in-a-public-rsa-key $\endgroup$
    – John dow
    Apr 13, 2016 at 14:13

3 Answers 3

13
$\begingroup$

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key.

The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve):

  • The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He keeps the EC private key secret; he'll install the EC public key into the program below.

  • To generate a key, the program selects a random 192 bit seed $R$.

  • It uses that seed to see a process that selects a random 512 bit prime $P$.

  • It encrypts the seed $R$ using the EC public value (perhaps using EC-ElGamal), resulting in a 384 bit value $E$.

  • It then selects a 512 bit prime $Q$ with the constraint that $Q \equiv P^{-1}(2E+1) \pmod{2^{385}}$

  • The product $PQ$ is the RSA modulus (and the rest of the RSA key pair is generated normally)

Then, the attacker can easily factor this RSA key (by extracting $E$ directly from the bit pattern of the RSA modulus, using the EC private key to decrypt it resulting in $R$, and then using R to recover $P$. And, no one without the EC private key has any advantage to factor this, even if they know the exact procedure used to generate the RSA key; both $P$ and $Q$ were chosen fairly, and the additional constraints on $Q$ do not help the attacker at all.

The moral of this story: if the attacker can control your RSA key generation process, you may have no security.

$\endgroup$
4
  • 6
    $\begingroup$ While this is certainly a smart alternative scheme, I do not believe this answers the question. It does not shed additional light on the scheme mentioned above. $\endgroup$
    – orlp
    Jan 24, 2016 at 23:06
  • 1
    $\begingroup$ @orlp: I know. I tried to construct an argument that the OP's scheme was provably safe, as a large fraction of random $P, Q$ values have some 384-bit value $A$ that meets the above criteria; alas, that doesn't appear to be the case. The best I can say is "it doesn't appear to help known factorization methods"; I can't say I'm happy with that statement $\endgroup$
    – poncho
    Jan 24, 2016 at 23:24
  • 2
    $\begingroup$ The backdoor you describe is detectable (Compressed ECC points are distinguishable from random data), but it can be made undetectable with minor modifications (e.g. randomly picking a point from the curve or its twist). The size of the fixed data can be halved by deriving the seed from the shared secret instead of encrypting it. $\endgroup$ Jan 25, 2016 at 9:36
  • $\begingroup$ A type of feasible highly sophisticated RSA backdoor in non-open-source software that IMHO is not detectable at all by outsiders is due to maartin many years ago and is recently elaborated by me at the end of the Epilogue section of s13.zetaboards.com/Crypto/topic/7234475/1 $\endgroup$ Jan 25, 2016 at 15:56
7
$\begingroup$

The field of cryptography that you are looking for is called Kleptography. In kleptography, we are dealing with a setting where the device performing your cryptographic tasks is potentially malicious. Now this device tries to leak information to some attacker that allows this attacker to break the used cryptographic scheme. If I am not mistaken that scheme was proposed in the original work by Young and Yung. I did not check this but this paper is definitely a good starting point to get more information and contains at least two proposals for "RSA backdoors".

$\endgroup$
4
$\begingroup$

RSA modules factoring are not hard in general case. In special cases we can factor numbers easily. One of these special cases is weak prime number, if at least one of two RSA modules primes is weak we can factor it easily. It is interesting that number of such $1024$ bit modules are at least $2^{750}$ and for $2048$ bit is $2^{1500}$. Your mentioned RSA backdoor is special form of this weak prime number. So we can easily factore this number with lattice based attack (even if we dont know $A$).

for more detail about weak prime number you can see "Factoring RSA moduli with weak prime factors".

$\endgroup$
4
  • 1
    $\begingroup$ Can you expand on how "we can easily factor this number with lattice based attack (even if we dont know $A$)" ? That is exactly what the question is about, and I find that non-trivial. $\endgroup$
    – fgrieu
    Jan 26, 2016 at 7:45
  • $\begingroup$ @fgrieu, As I mentioned, for more detail and numerical example you can see eprint.iacr.org/2015/398.pdf. I implemented this method, with this method I factored $1024$ and $2048$ bit RSA module with prime factors in secend. $\endgroup$ Jan 26, 2016 at 20:15
  • 1
    $\begingroup$ In the context of the question, $P=A(P^\prime+i)+P^\prime$ for $A$ an unknown 384-bit prime, $P^\prime$ an unknown 128-bit prime, and $i$ small (likely $0\le i<500$). I doubt that makes $P$ weak in the sense of the paper. $\endgroup$
    – fgrieu
    Jan 26, 2016 at 21:00
  • $\begingroup$ @fgrieu, $P$ is approximately is $512$ bit so $N=PQ$ is $1024$ bit and $P'+i,P' $ are $128$ bit. see table 1 of page 6. $\endgroup$ Jan 27, 2016 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.