Tags: rsa-crypto
Rating: 3.0
# Problem
Category: Cryptography Points: 400 Description:
>It's the return of everyone's favorite cryptosystem! Crack it for another flag. Help me decipher file.
```
n = 9637828843823500407917687664441327784714605952794831018467094508166140790258515855681653788687192363262499178812675284846293988948568322307302995971433129
e = 65537
c= 744372384092422293657230440929981477879274068697788092531354927993093987582083018137886004402518974542009040817374858469786477527000745005045012289929736
```
# Solution
There is no other hint for this chall, we have to factorize the N for d. N is 512 bit.
1. Try Yafu
```
factor(9637828843823500407917687664441327784714605952794831018467094508166140790258515855681653788687192363262499178812675284846293988948568322307302995971433129)
```
2. Try RsaCTFTool
```
./RsaCtfTool.py --createpub easyctf.pub --n 963... --e 65537
./RsaCtfTool.py --publickey easyctf.pub --private
```
3. Try Cado NFS
There is no luck from above tools. I thought about ROCA from NCTU Bamboofox CTF event.
Use roca-detect to identify the Public Key fingerprint. It is vulnerable.
```
roca-detect rsa400.pub
2018-02-21 21:40:20 [9808] WARNING Fingerprint found in PEM RSA key rsa400.pub
{"type": "pem-rsa-key", "fname": "rsa400.pub", "idx": 0, "pem": "-----BEGIN PUBLIC KEY-----\nMFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALgEueBl31nLqxGv7RpyUZV0S6xtjbxj\n2SBlZfrffMfLG1V+nvCczWDR7a/LV6IdPEtdtu/fAXsz8t0L36wSYqkCAwEAAQ==\n-----END PUBLIC KEY-----", "e": "0x10001", "n": "0xb804b9e065df59cbab11afed1a725195744bac6d8dbc63d9206565fadf7cc7cb1b557e9ef09ccd60d1edafcb57a21d3c4b5db6efdf017b33f2dd0bdfac1262a9", "marked": true, "time_years": 0.00013349807611760526, "price_aws_c4": 0.05851220676234639}
2018-02-21 21:40:20 [9808] INFO ### SUMMARY ####################
2018-02-21 21:40:20 [9808] INFO Records tested: 1
2018-02-21 21:40:20 [9808] INFO .. PEM certs: . . . 0
2018-02-21 21:40:20 [9808] INFO .. DER certs: . . . 0
2018-02-21 21:40:20 [9808] INFO .. RSA key files: . 1
2018-02-21 21:40:20 [9808] INFO .. PGP master keys: 0
2018-02-21 21:40:20 [9808] INFO .. PGP total keys: 0
2018-02-21 21:40:20 [9808] INFO .. SSH keys: . . . 0
2018-02-21 21:40:20 [9808] INFO .. APK keys: . . . 0
2018-02-21 21:40:20 [9808] INFO .. JSON keys: . . . 0
2018-02-21 21:40:20 [9808] INFO .. LDIFF certs: . . 0
2018-02-21 21:40:20 [9808] INFO .. JKS certs: . . . 0
2018-02-21 21:40:20 [9808] INFO .. PKCS7: . . . . . 0
2018-02-21 21:40:20 [9808] INFO Fingerprinted keys found: 1
2018-02-21 21:40:20 [9808] INFO WARNING: Potential vulnerability
2018-02-21 21:40:20 [9808] INFO ################################
```
Searching for ROCA attack tool is not easy. There is no related result but only news from Google. After surfing several pages, I found [neca](https://gitlab.com/jix/neca).
```
./neca 9637828843823500407917687664441327784714605952794831018467094508166140790258515855681653788687192363262499178812675284846293988948568322307302995971433129
NECA - Not Even Coppersmith's Attack
ROCA weak RSA key attack by Jannis Harder ([email protected])
*** Currently only 512-bit keys are supported ***
N = 9637828843823500407917687664441327784714605952794831018467094508166140790258515855681653788687192363262499178812675284846293988948568322307302995971433129
Factoring...
[====== ] 24.88% elapsed: 1205s left: 3638.37s total: 4843.43s
Factorization found:
N = 121588253559534573498320028934517990374721243335397811413129137253981502266611 * 79266117915777331935558561759105375936182700866258172021902853781249206532339
```
flag is easyctf{4b8xofjwvy4rqkbuba}
