Tags: xor rsa 

Rating:

**Description**

> I personally prefer Home Depot
>
> XOR Passes are the easiest way to use numbers to encrypt!
>
> By Kris Kwiatkowski, Cloudflare

**Files provided**

- [`file.enc`](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-14-CSAW-CTF-Quals/files/lowe-file.enc)
- [`key.enc`](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-14-CSAW-CTF-Quals/files/lowe-key.enc)
- [`publickey.pem`](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-14-CSAW-CTF-Quals/files/lowe-publickey.pem)

**Solution**

First of all, let's have a look at all the files.

`file.enc` is Base64-encoded data, but it looks encrypted:

$ base64 -D < file.enc > file.bin
$ xxd file.bin
0000000: 912b 68ca 798d e4b4 a78a e7b4 9c3c 658b .+h.y........<e.
0000010: d72c 4ab0 607b 167f 60ea 397b e314 91f2 .,J.`{..`.9{....
0000020: 4ac2 f86d f211 ec63 2306 558c cc94 ea7d J..m...c#.U....}
0000030: b001 41ac f09b 9b85 00e2 7ee8 32bd b396 ..A.......~.2...

`key.enc` is a 462-digit (in decimal) number.

`publickey.pem` is an ASCII-formatted public key:

$ openssl rsa -pubin -in pubkey.pem -text -noout
Public-Key: (1536 bit)
Modulus:
00:cf:70:7e:ed:97:90:17:b7:f6:f4:76:ff:3b:a6:
55:59:ad:b1:82:e0:7c:fa:23:33:b1:ec:05:6b:7f:
7b:96:12:40:54:f1:f5:74:8b:04:c3:69:4e:90:f0:
d9:9f:ee:05:84:a8:7a:70:81:75:80:d4:93:93:32:
1b:b2:08:07:ff:de:25:a4:c8:ab:d4:6d:95:c1:e3:
74:0d:9e:64:1f:e7:7f:9b:96:ce:ca:e9:18:e6:7a:
24:89:52:b5:da:81:ae:77:42:bd:ae:51:b1:29:24:
59:73:41:50:57:ae:75:df:b7:5a:78:e8:24:37:9e:
52:50:65:92:c3:75:0e:9a:1c:7e:70:1b:ee:8d:df:
c7:a9:ca:72:53:4c:d3:b0:95:79:f8:7a:4e:b3:76:
f9:26:7c:d1:a1:6e:1e:57:90:95:c5:b8:6f:4b:8f:
24:fb:61:3f:08:a7:e0:e4:75:d2:55:56:ae:41:c8:
ce:e2:48:e9:0d:ac:96:5d:c4:7d:db:b4:c5
Exponent: 3 (0x3)

It is an RSA public key. The one thing that should immediately stand out is that the exponent `e` is very low. In fact, the challenge title `lowe` must be referring to this fact. Since RSA operates on data in the form of numbers, we can guess that `key.enc` is actually the result of RSA encryption, formatted as decimal digits instead of the usual binary data.

Also, we can consult e.g. Wikipedia on [attacks against plain RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_against_plain_RSA) and see that a low exponent can mean that the exponentiated plain text will be strictly less than the modulus `n`. If this were the case, we could simply take the root (in this case the cube root) of the cipher text (i.e. the `key.enc` number) and get back the plain text.

$ python3
>>> import gmpy2
>>> e = gmpy2.mpz(3)
>>> cipher = gmpy2.mpz(219135993109607778001201845084150602227376141082195657844762662508084481089986056048532133767792600470123444605795683268047281347474499409679660783370627652563144258284648474807381611694138314352087429271128942786445607462311052442015618558352506502586843660097471748372196048269942588597722623967402749279662913442303983480435926749879440167236197705613657631022920490906911790425443191781646744542562221829319509319404420795146532861393334310385517838840775182)
>>> gmpy2.iroot(cipher, e)
(mpz(6028897571524104587358191144119083924650151660953920127739581033174354252210219577997969114849529704172847232120373331804620146706030387812427825026581462), False)

Unfortunately, this did not work - the second value in the tuple returned by `gmpy2.iroot` (integer root) indicates whether the root is exact. It is `False` in this case, so the returned number is not the actual plain text.

But `n` is fairly large, and `e` is really low, so let's not give up immediately. If `p^e`, i.e. the exponentiated plain text is not strictly smaller than `n`, then perhaps it only "overflowed" through the modulus a small number of times. We can check if `c + n` has an exact cube root, then `c + 2 * n`, and so on.

>>> n = gmpy2.mpz(0xcf707eed979017b7f6f476ff3ba65559adb182e07cfa2333b1ec056b7f7b96124054f1f5748b04c3694e90f0d99fee0584a87a70817580d49393321bb20807ffde25a4c8abd46d95c1e3740d9e641fe77f9b96cecae918e67a248952b5da81ae7742bdae51b129245973415057ae75dfb75a78e824379e52506592c3750e9a1c7e701bee8ddfc7a9ca72534cd3b09579f87a4eb376f9267cd1a16e1e579095c5b86f4b8f24fb613f08a7e0e475d25556ae41c8cee248e90dac965dc47ddbb4c5)
>>> gmpy2.iroot(cipher + n, e)
(mpz(12950973085835763560175702356704747094371821722999497961023063926142573092871510801730909790343717206777660797494675328809965345887934044682722741193527531), True)
>>> plain = int(gmpy2.iroot(cipher + n, e)[0])

And yes, `c + n` already has an exact cube root, no need to do a long and computationally heavy search. So what did we decrypt, exactly?

>>> hex(plain)
'0xf74709ad02fe85d8d3f993d5ff5716eabb5829df0d12624a048e0a4bd726a6c428a3cd5ac6248900113733effdf1dc4b8837209c92a9a3e161d0478d04dbd0eb'

It doesn't look like ASCII data. But the challenge description mentions XOR encryption. Also, the file we haven't used yet, `file.enc`, contains 64 bytes of data, and the key we just RSA-decrypted is also 64 bytes. Let's try to XOR the two:

>>> key = bytes.fromhex(hex(plain)[2:])
>>> data = open("file.bin", "rb").read()
>>> bytes([ k ^ d for (k, d) in zip(key, data) ])
b'flag{saltstacksaltcomit5dd304276ba5745ec21fc1e6686a0b28da29e6fc}'

Again an unrelated-looking flag.

`flag{saltstacksaltcomit5dd304276ba5745ec21fc1e6686a0b28da29e6fc}`

Original writeup (https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-14-CSAW-CTF-Quals/README.md#200-crypto--lowe).