Tags: xor rsa 



> 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)


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)
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)

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) ])

Again an unrelated-looking flag.


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