Системный архитектор, криптоманьяк
5,1
рейтинг
20 января 2015 в 13:25

Разработка → Встраиваем бэкдор в публичный ключ RSA tutorial


Привет, %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_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);


Для каждой ключевой пары 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(MY_PUBLIC, priv);
		}



открытый ключ 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) Берем модуль 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' / p
4.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, а затем и вожделенный закрытый ключ.

Мы можем извлечь 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;
		}


Вычислить seed и прогнать процесс заново, чтобы получить закрытый ключ

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


Таким образом, только мы, владея закрытым ключом Сurve25519 можем вычислить закрытый ключ любого забекдоренного нами RSA ключа.

Где это можно применить? Да где угодно. Вы никогда не докажете, что в ключевых парах, выдаваемых вам банками и другими неконтролируемыми вами источниками нет таких закладок. Определить наличие такой закладки невозможно! Поэтому старайтесь генерировать их сами софтом, который знаете как работает.

Сорцы для поиграть тут

Upd:

Поправил код, теперь по-честному для внедрения нужен наш открытый ключ, а достаем мы seed с помощью закрытого
@Scratch
карма
107,7
рейтинг 5,1
Системный архитектор, криптоманьяк
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (75)

  • +9
    Интересный подход, но кажется весьма избыточным. Если банку или интеграторам, которые там развернули СКЗИ, захочется выдавать вам «слабые» ключи или ключи с «бэкдорами», почему бы просто не использовать в качестве ДСЧ тупо константы? Ну или заведомо уязвимый ДСЧ вроде ЛКГ? Если злоумышленник является разработчиком средства защиты, то описанная в статье беда не самая страшная :)
    • +3
      Слабые ГСЧ могут повлиять на качество простых чисел, какую-то корреляцию между ними навести и какой нибудь умный аналитик возьмет и догадается. А тут все честно, все генераторы стойкие, ничего никогда не доказать :)
      • +1
        Не всегда. Вон, посмотрите в сторону ДСЧ от Intel. Мы берем число из множества ничтожной мощности, суём его в AES в качестве ключа шифрования и, вуаля, получаем идеальную со статистической точки зрения последовательность. Ни один аналитик не подкопается. Тем более, если не знает, что именно за исходное множество у нас было, чтобы сузить объем материала для перебора.
        • 0
          Так делают дилетанты.
          В нормальных системах есть пул энтропии, в него сливается вся доступная энтропия, потом оно смешивается и выдаётся некий результат.
          Плюс такой схемы в том, что даже если интел плохо генерит рандомы и если другие тоже плохо генерят рандомы, но хотябы один источник энтропии нормальный то на выходе будет рандом который не предсказать.
          Для смешивания раньше использовали RC4 (потом стали отбрасывать первые 2кб, потом сбрасывать пул каждые 10 минут), а потом перешли на ChaCha.
        • 0
          Ну в таком случае в выводе ДСЧ повторы будут встречаться намного чаще, чем должны. И это можно заметить просто гоняя ДСЧ, сохраняя начала всех полученных последовательностей в сортированный массив и ища повторы. Причём если у нас, например, мощность этого множества 2^N, то для перебора злоумышленнику придётся сделать 2^(N-1) итераций, а для описанной выше проверки — 2^(N/2).
  • 0
    В том числе и поэтому ключевая пара обычно генерится на стороне клиента, а удостоверяющему центру даётся на подпись только открытая часть.
    • +9
      На стороне клиента софт далеко не всегда опенсорсный
  • 0
    Есть ли способ обнаружения такой «нагрузки»?
    • +1
      Нет, в этом весь ужас
  • +8
    > Вы никогда не докажите, что в ключевых парах, выдаваемых вам банками
    > и другими неконтролируемыми вами источниками нет таких закладок.

    Объясните для тупых, а? Банк выдает вам приватный ключ, а потом с помощью каких-то хитрых действий этот ключ восстанавливает? А почему бы банку просто не запомнить этот ключ? Или банк выдает вам алгоритм, который похож на генерацию криптографически строгого приватного ключа, но на самом деле таковым не является? Ну, тогда вы сами себе злобный буратино.
    • +5
      Банк договаривается с «органами» и без пересылания им ключей они могут расшифровывать всё, что вы зашифровываете
      • +6
        Банк «органам» по запросу и так всё о вас расскажет. Что вы спрятать то пытаетесь и от кого?
        • +10
          Это лишь пример, ситуаций можно придумать множество
          • +3
            Ждём. А то паранойя, знаете ли, разбушевалась.
            • +5
              Исходники PGP, например, у вас есть? И у меня нет, а штука популярная. Генерация сертификатов средствами винды, это навскидку.
              • +6
                Исходники OpenSSL, PolarSSL и др. реализаций есть в открытом доступе, но где гарантия, что в них нет таких же скрытых закладок или багов в реализации криптоалгоритмов, которые могут привести к раскрытию данных или еще чему то?
                Никто не проводил полный аудит открытых библиотек и посему потенциально в них тоже могут быть закладки.
                Буквально вчера в PolarSSL нашли критическую уязвимость (https://polarssl.org/tech-updates/security-advisories/polarssl-security-advisory-2014-04), которая потенциально может привести к выполнению кода злоумышленника при обработке средствами библиотеки специально оформленных последовательностей ASN.1 из сертификатов X.509. А PolarSSL используется много где, например в OpenVPN, cURL, FreeRDP, PowerDNS и т.д.
                Так что открытость кода != надежность
                • +7
                  Не путайте ошибку и закладку.
                  • 0
                    когда серьёзная компания берёт на вооружение какой-либо софт она вполне себе может сделать его аудит и пользоваться ошибкой, как закладкой ;) мне кажется, что криптография просто обязана стать популярной словно р2р сети, просто время ещё не пришло. Не достаточно прецедентов.
                  • +3
                    --Не путайте ошибку и закладку.

                    А вы их гарантированно можете различить? а результат-то один.
                    • 0
                      При наличии исходного кода я могу различить. Да и для этого есть и берутся в проекты специалисты типа: аудиторы кода, тестеры.
                      Если пишут для примера:
                      if user_name == 'root' then
                      это может быть ошибкой т.к. хотели для примера !=
                      Если ли же пишут что то типа:
                      if substing (user_name, 2,2) == 'oo' then
                      это уже закладка
                      • 0
                        следующий вопрос: вы умеете отличать аудиторов кода и тестеров от вражеских шпионов?
                        • 0
                          А еще могут быть закладки в железе и в квантовой механике. Если у нас нет возможности находить закладки в используемом нами софте — то хитроумные алгоритмы производителю софта уже не нужны.
                      • 0
                        Смешно, что мешает писать в стиле ошибок, нечаянных опечаток? Наивно как-то думать что это невозможно или даже слишком трудно.
                        • 0
                          А что если не использовать код, написанный в таком стиле?
                      • 0
                        Замаскировать закладку под ошибку ведь не сильно сложно?
                      • 0
                        Напомнило конкурс на закладки замаскированные под простые ошибки.
                        underhanded.xcott.com/
              • 0
                Я всё равно не понимаю, в чем соль.
                Отлично, мы можем сделать генератор ключей такой что мы можем по открытому ключу восстановить приватный, а остальные не могут. Чем описанный в статье способ принципиально лучше return (our_private_key, our_public_key);?
                • +1
                  Внешне не будет выглядеть, как выдача зашитого ключа
                  • 0
                    В коде это всё равно записано. А обфусцировать можно что угодно.
                • +2
                  Вот этим:
                  Отлично, мы можем сделать генератор ключей такой что мы можем по открытому ключу восстановить приватный, а остальные не могут.
                  • 0
                    Вот так и надо формулировать, а не «неопределимый бэкдор».
                    Спасибо.
                  • 0
                    ой, да такой генератор ключей сделает первокурсник.
                    например: privKey = sha1 ( «my_very_secret_constant_salt» + time ( ) )
                    никто кроме автора не подумает, что ключи брутфорсятся.
                    А спрятать этот код в сорцах не составит большого труда.
                    • 0
                      Начнем с того, что если сделать так, то потом мы не сможем найти публичный ключ для вычисленного приватного :)

                      По поводу же брутфорса… вы правда не видите разницы между брутфорсом и прямым вычислением приватного ключа по открытому?
                    • 0
                      Описанный в статье вариант, в отличии от вашего, подходит для вполне нормального применения (если публичный ключ не зашивать в софт а выдавать). Вы генерируете pgp ключ на основе моего публичного, теперь вы и я можем читать сообщения, зашифрованные сгенерированным ключом. Но вам для этого не надо предпринимать усилия по посылке мне своего приватного ключа.
                      Можно даже иерархию запилить (использовав сгенерированный тут ключ для генерации следующих).
                      • 0
                        Дело в том, что для удостоверения того, что отправленный по открытым каналам публичный ключ не подменён при передаче «человеком посередине», и только для этого «надо предпринимать усилия по посылке мне своего приватного ключа.»
      • 0
        Условно — производитель замков не рассылает всем, кому нужно связку с ключами от всех замком, а только алгоритм изготовления ключа «по адресу квартиры» (публичной информации)?
        • 0
          Саш, а когда-то в каком-то мире был по-другому? Что изменилось?
      • +1
        Зачем такие сложности? Если это может расшифровать «банк» (специально беру в кавычки, в общем случае это «вторая сторона») — то что мешает «банку» передать расшифрованный трафик «третьей стороне» (органам), либо передать алгоритм расшифровки третьей стороне?
        • +5
          Ну может потому что будет сам факт передачи, к тому же лишние люди (работники банка) узнают клиента которым интересуются органы. А так слушай кого угодно и без свидетелей!
        • +1
          Предположим, что вы купили банк и поменяли сотрудников.
          Вы никому ничего не говорите, и получаете сообщения, и участвуете в переписке с клиентом.

          Только уже и вы может не вы, и ли клиент — не клиент, а ни вы ни клиент об этом не в курсе.
        • +3
          Владея вашим закрытым ключом, «банк» может действовать от вашего имени, и «вы никогда ничего не докажете»
    • +4
      Банк может использовать чужое ПО, разработчик которого вложил туда подобную функциональность, не оповестив при этом сам банк :)
      • –2
        А если разработчик не вложил и всё чисто-законно, но где-то между (банк, клиент банка) происходит подмена третьими лицами?
        • +3
          Значит, отделу ИБ банка нужно вставить люлей за то, что используют СКЗИ, не обеспечивающее защиту от MitM :)
  • 0
    Что вы к банкам пристали?
    Для получения квалифицированной ЭЦП подавляющее большинство УЦ использует сертифицированный органами софт, соответственно и клиенты вынуждены его использовать при генерации ключей.
    Пальцев одной руки хватит (двух точно), чтобы перечислить сертфицированные СКЗИ, СКАД etc.
    Вопрос к их разработчикам, а не к УЦ.
    • +2
      Банки я взял для примера, Применить это возможно везде, где пользователь не контролирует процесс генерации ключей
      • +2
        Я обратного давно не встречал.
        Симметричное шифрование, при котором закрытый ключ знает и УЦ и клиент, практически перестали использовать после того, как объявили панацеей ассиметричное шифрование.
        Другое дело, что клиент при генерации вынужден использовать софт и криптопровайдера, навязанного ему УЦ.
        У вас есть доверие к криптопро, вербе, криптоарм etc?
        • +2
          Обратное встречается когда мы сами генерируем ключевую пару для сайтов с помощью openssl, например, ssh ключи и все такое.
          • +4
            При этом самому их скомпилировав и проверив на такие «патчи»
  • +1
    del
  • +1
    Я правильно понял, что сценарий такой  — генерируя приватный и публичный ключ (т.е. зная приватный ключ) об специализированный секрет можно сгенерить такой публичный ключ, по которому можно восстановить приватный, зная секрет?
    Итого, реальный сценарий эксплуатации уязвимости такой — подсунуть в широкий доступ библиотеку, которая генерит ключевые пары об наш зашитый в нее секрет.
    • +1
      Сценарий такой, что можно сгенерировать ключевую пару, у которой по открытому ключу можно восстановить закрытый. Остальное лишь детали реализации
  • +2
    «Здесь стоит напомнить, что основа ключей RSA — это всегда два простых числа p и q. Их произведение — открытый ключ.»

    Стоит напомнить, что произведение p и q — это модуль, а открытый ключ (публичная экспонента), это выбранное число, взаимно простое с фи(n) (как правило это 0x10001 = 65537), и обозначается оно 'e'.

    Будьте корректнее при использование терминов.

    ru.wikipedia.org/wiki/RSA
    • +1
      Открытый ключ — это все же пара из модуля и публичной экспоненты (о чем, кстати, написано по приведенной вами ссылке)
    • +1
      Поправил, спасибо
  • +1
    Я не совсем понимаю, чего тут такого. Еще более веселых вещей можно добиться манипулируя ПГСЧ. Так можно и без открытого ключа закрытый определять )
    • +4
      Для таких задач бывает несколько уровней «палевности»:
      * когда ключ можно извлечь без дополнительных знаний (довольно плохой вариант, так как позволяет сразу детектировать открытые ключи с бэкдором)
      * когда ключ можно извлечь только зная другой ключ симметричного шифрования (в этом случае человек, обнаруживший бэкдор, может сам получить созданные закрытые ключи)
      * когда ключ можно извлечь только зная другой ключ ассиметричного шифрования (получше, так как человек, обнаруживший бэкдор, не может получить закрытые ключи)
      * когда после обнаружения бэкдора невозможно отличить хорошие ключи от ключей с бэкдором

      Безусловно, можно генерировать ключи с очень слабой энтропией, но тогда они будут соответствовать первому уровню, а в идеале хотелось бы получить что-то более близкое к четвёртому.
  • –5
    Ахтунг не пройдёт.

    1) ошибка выбора ГПСЧ: «Нам нужен ГПСЧ, который инициализируется секретным значением»

    А почему не платой ГСЧ на мат.плате, или ранодомными нажатиями на клавиатуре-мышке (кто-сталкивался с PGP, поймёт)?

    2) ошибка использования криптозащиты: «Для каждой ключевой пары RSA, которую мы будем генерировать, мы так же будем генерировать случайную ключевую пару Curve25519, а потом считать общий секрет от публичного ключа этой пары и нашего приватного»

    А такой-уж ли «секретный» будет наш общий секрет? Мне кажется это все напомоинает мне способ поместить публичный и приватный ключ в один контейнер, а потом выдать его за приватный.
    • +3
      Какие ошибки? Если цель была встроить бэкдор — и в результате мы имеем бэкдор, то что вам еще надо?
  • +8
    А теперь почти то же самое, но для эллиптических кривых: Kleptographic Attacks on Elliptic Curve Cryptosystems (http://paper.ijcsns.org/07_book/201006/20100628.pdf)
    • 0
      Спасибо, читнем
  • +2
    Сдаётся мне, что несмотря на скепсис комментаторов, описанный в статье способ всё же где-то пригодится, точнее «будет использован».
    • +4
      А еще точнее — уже давно используется.
  • 0
    А из сообщения, зашифрованного RSA можно извлечь открытый ключ?
    • +1
      В общем случае — никак. Но часто можно получить сертификат (при TLS/SSL он передается в фазе рукопожатия) или сам открытый ключ (в PGP/GPG-encoded сообщении обычно лежит fingerprint получателя, по которому он ищется на серверах ключей).
  • +2
    kukuruku.co/hub/infosec/backdoor-in-a-public-rsa-key
    ― без ссылки на хабр :(
  • 0
    Если в настройках УЦ и так уже можно указать возможность сохранения копии в базе УЦ, то нафига все эти извороты?
    • 0
      Чтобы скрыть сам факт передачи закрытого ключа третьему лицу.
      • 0
        Каким образом может быть установлен факт передачи, если такая настройка включена? Её включение != передаче третьему лицу. С таким же успехом можно вообразить что сыграл человеческий фактор на стороне владельца ключа.
        • 0
          Эти извороты нужны, если мы хотим скрытно передать ключ третьему лицу.
          • –2
            Скрытно копируем ключи на флешку. Скрытно отдаем флешку третьему лицу? Так?
  • +1
    По моему система, в которой ключевая пара генерируется не клиентом, а сервером — изначально порочна

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.