Weak RSA

A rogue employe managed to steal a file from his work computer, he encrypted the file with RSA before he got apprehended. We only managed to recover the public key, can you help us decrypt this ciphertext?

Category: Crypto

Solvers: 3mb0, lmarschk, HTTP418, miroka

For this challenge, we had a public RSA key with 1026 Bit and a file that was encrypted with the corresponding private key.

First approach: manual generate private key

We analyzed the given public key with openssl rsa -noout -text -inform PEM -in pubkey.pem -pubin:

RSA Public-Key: (1026 bit)
Modulus:
    03:64:a5:37:f4:1c:bb:40:a1:ce:a1:d7:93:5a:f4:
    ae:25:e6:68:b9:c7:bf:3d:79:3c:d0:bc:66:55:8d:
    85:61:03:5b:46:73:9a:de:4a:c6:cd:0f:fc:ac:90:
    e2:ac:40:3d:b5:77:c2:ef:74:14:f0:10:5c:be:fc:
    29:dd:db:c8:69:bc:de:1a:37:3e:e8:58:3b:d8:6c:
    b6:cc:a6:96:fc:72:0c:fd:96:b4:7d:51:f6:c9:35:
    14:81:c8:fe:b7:12:78:d0:b2:6f:ab:87:c5:55:70:
    28:68:a6:88:53:7d:7a:e6:42:40:9d:e6:19:a7:ca:
    d3:e8:e4:47:24:90:8a:bc:df
Exponent:
    02:28:48:1c:f1:27:03:1c:41:4c:44:58:cf:05:1d:
    ad:dd:d6:1b:74:ab:0e:4b:b7:c7:32:49:85:48:ec:
    09:a2:9e:96:6e:55:6d:a8:29:53:df:0a:cc:68:02:
    fb:47:03:c1:02:af:52:58:91:fa:2e:9b:e2:9f:81:
    05:2a:d0:45:cb:b6:d7:74:bb:37:4f:cf:67:1d:e7:
    80:83:ad:da:5a:5b:3b:a4:77:23:69:d5:62:ed:cd:
    ad:4c:3e:01:6e:33:9b:26:3b:84:70:a2:07:d9:9e:
    53:7b:b1:a2:4e:57:8a:cf:29:dc:64:ff:f0:c0:08:
    0d:9f:64:c8:e7:ee:bf:51:89

The public exponent is extremly large. Normally the public exponent is chosen as 65537. lmarschk and this stack overflow question hinted that the private exponent might be small in this case which would allow us to use Wiener’s attack to determine the private key.

Wiener Attack

We used this tool to calculate p and q and this tool to find d by simply changing the values for e and n (from the public key) in the source code. We then calculated e1, e2 and coeff according to this stackoverflow post and generated the following definition:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:0x0364a537f41cbb40a1cea1d7935af4ae25e668b9c7bf3d793cd0bc66558d8561035b46739ade4ac6cd0ffcac90e2ac403db577c2ef7414f0105cbefc29dddbc869bcde1a373ee8583bd86cb6cca696fc720cfd96b47d51f6c9351481c8feb71278d0b26fab87c555702868a688537d7ae642409de619a7cad3e8e44724908abcdf
pubExp=INTEGER:0x0228481cf127031c414c4458cf051dadddd61b74ab0e4bb7c732498548ec09a29e966e556da82953df0acc6802fb4703c102af525891fa2e9be29f81052ad045cbb6d774bb374fcf671de78083adda5a5b3ba4772369d562edcdad4c3e016e339b263b8470a207d99e537bb1a24e578acf29dc64fff0c0080d9f64c8e7eebf5189
privExp=INTEGER:40127490441880177477224469176371044914847896019034308382923938039797354608313
p=INTEGER:22107961593273663554447672179167919592270857343971618325649212520279122827566022270428817505638791153667398184068987608971763363269212331920067006335889541
q=INTEGER:27591125068163886831989228774178759832120484388897183929367433612315983402979538404952530012269465045393978140179601040530392691765067542341015115680614163
e1=INTEGER:40127490441880177477224469176371044914847896019034308382923938039797354608313
e2=INTEGER:40127490441880177477224469176371044914847896019034308382923938039797354608313
coeff=INTEGER:2900555069692317042319274446489272954370031747819920729439110986128111536959362074792306683305526558588404645984991938525834191273137021212035697086598948

With openssl asn1parse -genconf def_wiener.asn1 -out newkey.der we generated a DER from which we could build the private key with openssl rsa -in newkey.der -inform der -text -check -out newkey.pem. We inspected the private key with openssl rsa -noout -text -inform PEM -in newkey.pem:

RSA Private-Key: (1026 bit, 2 primes)
modulus:
    03:64:a5:37:f4:1c:bb:40:a1:ce:a1:d7:93:5a:f4:
    ae:25:e6:68:b9:c7:bf:3d:79:3c:d0:bc:66:55:8d:
    85:61:03:5b:46:73:9a:de:4a:c6:cd:0f:fc:ac:90:
    e2:ac:40:3d:b5:77:c2:ef:74:14:f0:10:5c:be:fc:
    29:dd:db:c8:69:bc:de:1a:37:3e:e8:58:3b:d8:6c:
    b6:cc:a6:96:fc:72:0c:fd:96:b4:7d:51:f6:c9:35:
    14:81:c8:fe:b7:12:78:d0:b2:6f:ab:87:c5:55:70:
    28:68:a6:88:53:7d:7a:e6:42:40:9d:e6:19:a7:ca:
    d3:e8:e4:47:24:90:8a:bc:df
publicExponent:
    02:28:48:1c:f1:27:03:1c:41:4c:44:58:cf:05:1d:
    ad:dd:d6:1b:74:ab:0e:4b:b7:c7:32:49:85:48:ec:
    09:a2:9e:96:6e:55:6d:a8:29:53:df:0a:cc:68:02:
    fb:47:03:c1:02:af:52:58:91:fa:2e:9b:e2:9f:81:
    05:2a:d0:45:cb:b6:d7:74:bb:37:4f:cf:67:1d:e7:
    80:83:ad:da:5a:5b:3b:a4:77:23:69:d5:62:ed:cd:
    ad:4c:3e:01:6e:33:9b:26:3b:84:70:a2:07:d9:9e:
    53:7b:b1:a2:4e:57:8a:cf:29:dc:64:ff:f0:c0:08:
    0d:9f:64:c8:e7:ee:bf:51:89
privateExponent:
    58:b7:5a:cf:96:33:b8:11:11:b9:66:1f:5f:86:7f:
    09:36:ff:90:f0:be:60:15:2b:8b:6f:a9:87:c6:cc:
    36:b9
prime1:
    01:a6:1d:77:1b:f9:df:ea:1e:96:64:69:87:40:13:
    de:b0:57:f2:f6:b7:8f:39:dd:3a:ed:81:b7:4c:37:
    07:5e:98:8c:23:05:ca:39:54:fd:fa:d2:fe:9c:64:
    c9:7e:b7:81:b8:7c:f1:d0:5d:fa:9f:26:21:05:47:
    e0:fa:01:30:85
prime2:
    02:0e:ce:9c:2c:2b:27:ce:b5:1a:0b:aa:0c:ee:78:
    8e:30:41:66:6b:f9:38:79:d0:dd:4e:82:90:70:1e:
    e6:fa:f0:cf:68:78:5f:d7:99:7f:ff:53:49:3b:99:
    4b:d3:af:ea:34:96:48:af:13:85:1c:88:ae:22:fb:
    7c:df:c6:87:13
exponent1:
    58:b7:5a:cf:96:33:b8:11:11:b9:66:1f:5f:86:7f:
    09:36:ff:90:f0:be:60:15:2b:8b:6f:a9:87:c6:cc:
    36:b9
exponent2:
    58:b7:5a:cf:96:33:b8:11:11:b9:66:1f:5f:86:7f:
    09:36:ff:90:f0:be:60:15:2b:8b:6f:a9:87:c6:cc:
    36:b9
coefficient:
    37:61:9e:2b:77:f4:e6:ec:58:d8:55:88:8b:34:92:
    09:76:9b:72:0f:e0:58:58:f4:c1:20:77:1b:9d:90:
    5b:d8:3b:ff:c0:52:d7:00:d3:c5:5f:46:29:8b:93:
    e6:10:d9:5d:e8:83:77:12:66:fa:87:5f:f1:72:98:
    fc:60:8f:24

Using our private key with openssl

We generated the corresponding public key with openssl rsa -in newkey.pem -outform PEM -pubout -out newkey-pub.pem. This is exactly the same key we downloaded for the challenge. We also could encrypt files with our private key and decrypt it with the downloaded public key. But we were not able to decrypt the flag with openssl rsautl -in flag.enc -inkey newkey.pem -decrypt.

Using our private key with python

We used a python notebook to decrypt the flag with our generated key.

Second approach: Use nice tools

• Download RsaCftTool
• Run python3 RsaCtfTool.py --publickey pubkey.pem --uncipherfile flag.enc

lmm@lmm-think-05:~/Documents/htb/ctf_2020/crypto_baby/RsaCtfTool$ python3 RsaCtfTool.py --publickey ../../../crypto_rsa/pubkey.pem --uncipherfile ../../../crypto_rsa/flag.enc
private argument is not set, the private key will not be displayed, even if recovered.

[*] Testing key ../../../crypto_rsa/pubkey.pem.
[*] Performing boneh_durfee attack on ../../../crypto_rsa/pubkey.pem.

Results for ../../../crypto_rsa/pubkey.pem:

Unciphered data :
HEX : 0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004854427b6231365f655f356d346c6c5f645f337175346c355f7733316e33725f34373734636b7d
INT (big endian) : 2357392946640097540211419645858895520810208771688666037754674144921765688545923475455795751805
INT (little endian) : 22546574263662123411523113128044215139929103295256955398886722465953163007000026640058669241937130344552566514396588140080195580660405015242202668398374037246444419998235653404182362721762856885981820839225967889839162532460437518669392406390949281459764025707163465962902177848023467525069105766717294567751680
STR : b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00HTB{b16_e_5m4ll_d_3qu4l5_w31n3r_4774ck}'