UIUCTF 2020: nookcrypt === ## Challenge Summary > Tom Nook is testing a new encryption scheme for nookphones, but it seems to be a bit faulty... can you break it? _nookcrypt_ is a netcat service that have no source code released. There are two functions exposed: 1. Gets an encrypted copy of the flag (and the message hello world). 2. Encrypts an arbitrary message. For example, this is what I had when trying out the options:  Option: 1 enc(FLAG) = (0xf31ce7cb1f2c6e7107318d76bdda50c5, 0x02d979fc3122bbaffcc1111953bc184f) enc('hello world') = (0x4cf5afcc9bc1db0118172129b713d86a, 0xe41d8761370768aa9694b164c843dde9) Option: 2 msg: hello world enc(0x68656c6c6f20776f726c64) = (0x4cf5afcc9bc1db0118172129b713d86a, 0xe41d8761370768aa9694b164c843dde9)  Since the response is consistent after reconnecting to the netcat service for multiple times, I assume that the parameters are constant. ## Solution ### Part I: Recovering the curve parameters in a stupid way Since it is mentioning elliptic curves in its services, the first thing I was doing is to recover the parameters, namely, $a$, $b$ and $p$ for the elliptic curve $y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$. My attempt is to encrypt a bunch of messages:  msg: a enc(0x61) = (0xb2d6c27a99b52aec6e243d4e4f67cb71, 0x9dfa2bd87ea1e09388493137132cc534) msg: b enc(0x62) = (0x99b8150ebf23c69ee1056f0e329496ae, 0xe1febe35a5877f00f3876c2a24fb9164) msg: c enc(0x63) = (0x3e7ef6d1106382119a0fa8c966f6d1df, 0x89d81b9fab5336a227414491881bbee8) msg: d enc(0x64) = (0x985dbb38a65f4e69bfc602d7e114cad9, 0xcad1cb62a3d30b05093575f3a22f7e3c) ...  Define $C_i = (x_i, y_i)$ be the ciphertexts of some message $m_i$. By direct substitution, we have $y_i^2 \equiv x_i^3 + ax_i + b\ (\text{mod}\ p)$ for all $i$. Assume that we have three ciphertexts. We can deduce that: 1. $a(x_1 - x_2) \equiv y_1^2 - y_2^2 - x_1^3 + x_2^3 \ (\text{mod}\ p)$ and 2. $a(x_2 - x_3) \equiv y_2^2 - y_3^2 - x_2^3 + x_3^3 \ (\text{mod}\ p)$. From above, we know $(y_1^2 - y_2^2 - x_1^3 + x_2^3)(x_2 - x_3) - (y_2^2 - y_3^2 - x_2^3 + x_3^3)(x_1 - x_2)$ is a multiple of $p$. So we have collected a bunch of "multiples of $p$" and take their gcd. We have recovered that $p = 340282366762482138434845932244680310783$. Then it is rather obvious to recover $a = 284470887156368047300405921324061011681$ and $b = 126188322377389722996253562430093625949$. :::info **Question.** What if it is not defined on a prime field? Well... I didn't think of that. But who cares? I could probably observe this if my approach doesn't work out. ::: ### Part II: A reflection on the "after-math" :::warning **Note.** I did not think of this during the game. Stupid me. ::: Knowing that the ciphertext $C$ is a multiple of the message $m$, i.e., $C = mG$, we can simply encrypt $m = 1$:  [+] Opening connection to chal.uiuc.tf on port 2006: Done [DEBUG] Received 0x123 bytes: b'\n' b'========================================\n' b'Welcome to NookCrypt! Here we use fancy\n' b'elliptic curve encryption to keep your \n' b'messages safe! Try it out!\n' b'========================================\n' b'1. get (encrypted) flag\n' b'2. encrypt message\n' b'3. quit\n' b'========================================\n' b'\n' b'Option: ' [DEBUG] Sent 0x2 bytes: b'2\n' [DEBUG] Received 0x5 bytes: b'msg: ' [DEBUG] Sent 0x2 bytes: 00000000 01 0a │··│ 00000002 [DEBUG] Received 0x178 bytes: b'enc(0x01) = (0x7b6aa5d85e572983e6fb32a7cdebc140, 0x27b6916a894d3aee7106fe805fc34b44)\n' b'\n' b'========================================\n' b'Welcome to NookCrypt! Here we use fancy\n' b'elliptic curve encryption to keep your \n' b'messages safe! Try it out!\n' b'========================================\n' b'1. get (encrypted) flag\n' b'2. encrypt message\n' b'3. quit\n' b'========================================\n' b'\n' b'Option: '  What can we do? Since this is $G$, we can simply search this on Google: ![](https://i.imgur.com/ORfhqk4.png) Ta-da :tada: - it is the generator for curve _secp128r2_. You would think this is a ta-da moment, I would say that this is a facepalm moment. I could spent much less time on recovering the parameters in such a way. Well, I was even more confused to notice that is a secure curve. I personally don't have a backdoor of _secp128r2_ (I am much appreciated if you tell me if you do) and thought the challenge isn't doable. ### Part III: "Hint for nookcrypt (crypto 500)" Fours hours later the organizers released a hint in the Discord server: ![](https://i.imgur.com/iLrD1Es.png) When I was ~~being played~~ writing an interactor with the service, I observed that there was a strange behaviour regarding to the flag encryption method:  ======================================== Welcome to NookCrypt! Here we use fancy elliptic curve encryption to keep your messages safe! Try it out! ======================================== 1. get (encrypted) flag 2. encrypt message 3. quit ======================================== Option: 1 err  Oh. So the error was caused by the cosmic ray. Okay. :::info **Did you really get it instantly when the hint is announced?** No. ::: ### Part IV: Somebody made a breakthrough Ten hours later, _somebody_ from Discord claimed that he has a strange observation: ![](https://i.imgur.com/c4QxADO.png) :::info **Who was the somebody?** Me. ::: We made a bunch of assumptions. Cutting the crap, we assumed that the same generator $G = (x_G, y_G)$ is being multipled in a same way, except that the curve is operated on new modulo $p'$. This matches the author's statement regarding on the prime being corrupted. However, obviously, it is very likely that $G$ may not be a point the above curve. Luckily (or unluckily), we can assume that it is operating on another curve $y^2 \equiv x^3 + ax + b'\ (\text{mod}\ p')$, such that $G$ is on it. For now, we are given two points on this curve (the ciphertexts of the flag $F = (x_F, y_F)$ and the message hello world $M = (x_M, y_M)$). Since $a$ is known we can easily recover $p'$ by: $$\begin{split} p' = gcd( &(y_F^2 - x_F^3 - ax_F - b') - (y_G^2 - x_G^3 - ax_G - b'), \\ & (y_M^2 - x_M^3 - ax_M - b') - (y_G^2 - x_G^3 - ax_G - b')) \end{split}$$ The order of the generator should be a large prime for an elliptic curve to be secure. Clearly this property may not hold on those new modulos struck by cosmic may. For instance, suppose that we have $p' = 340282366762482138434845932242512471141$. Since 67 is a factor of $p'$, we are indeed working on the curve $y^2 \equiv x^3 + ax + b'\ (\text{mod}\ 67)$. $G$ has a order 74, and $F = fG = 21G$. It implies that $f \equiv 21\ (\text{mod}\ 74)$. By collecting a bunch of linear congruences, we can find $f$ by the Chinese Remainder Theorem. Eventually we have the flag: uiuctf{th4t_5ur3_w4s_f4ulty_huh?}. ###### tags: CTF