Geekly Articles each Day
📜 ⬆️ ⬇️

We build a backdoor in the RSA public key


Hi% username%!
When I saw how it works, to say that I was in shock - to say nothing. This is a pretty simple trick, but after reading this article, you will never look at the RSA again. This is not an RSA hack, this is something that will cause your paranoia to swell very much.


So, imagine that you have access to the RSA key generator and you want to continue to give someone the opportunity to find out the private key without any factorization and other quantum computers. What do we need for this?

I will immediately rush to C # code that uses BouncyCastle and Chaos.NaCl (this library implements Curve25519 )
')
1) PRNG

We need the PRNG, which is initialized with a secret value. Will use AES s CTR mode

PRNG code
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 the wonderful Curve25519 , namely the fact that any 32-byte sequence is a valid private key for it, and the public key is also always 32 bytes.
Generate the master key in advance and write it somewhere in the constant.

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


For each RSA key pair that we will generate, we will also generate a random key pair Curve25519, and then read the shared secret from the private key of this pair and our public one. This secret will be the key for our PRNG from p.1

Generation seed 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(MY_PUBLIC, priv); }



The public key Curve25519, which we use to calculate the seed in the future, is “payload” or payload . We will try to shove it into the RSA public key.

3) Generate a key RSA pair using this 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 is worth recalling here that the basis of RSA keys is always two primes p and q. Their work is called "module" and is part of the public key. In this case, with the help of our PRNG, two numbers of 2048 bits are searched for and then a key pair is constructed from them.

4) Take the p * q module and replace some of the bytes with our payload. Take older bytes so that they are not ground in the future. An offset of 80 bytes should work.

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


4) We now have a new module n '. We need to regenerate the remaining parameters with the new n', namely:

4.1) Consider the new q '. At this stage, we will have the hell with it, but it's not scary
q '= n' / p
4.2.) From the new q 'we are looking for a new prime number. When we find it, the lower bits will be frayed. But the top will remain the same. This is what we wanted.

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


After we have a new q, we consider all the parameters of the key pair, 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); }


And in the end we get a valid key pair, in the public key of which our Payload disappeared - namely, information on how to get a seed, and then the coveted private key.

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 run the process again to get the private key

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


Thus, only we, owning the private key urve25519, can calculate the private key of any RSA key we have forgotten.

Where can this be applied? Yes, anywhere. You will never prove that there are no such bookmarks in the key pairs issued by banks and other sources uncontrolled by you. To determine the presence of such a bookmark is impossible! So try to generate them yourself with software that knows how it works.

Sorts for playing here

Upd:

Corrected the code, now, honestly, our public key is needed for the implementation, and we extract the seed using the private

Source: https://habr.com/ru/post/248269/

More articles:


All Articles