HKCert20 CTF : Calm Down
===
(500 pts, 1 solve)
Solver: T0022 - HKUST Member 2

**Description:**
I am so excited having a chance talking to Alice. She told me to calm down - and sent me an encrypted secret.

nc terti</span>ary.pwn</span>able.h</span>k 50013

# Challenge written by Mystiz.

import base64
import binascii
import hashlib
import os
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

from secret import message

class RSAKey:
    def __init__(self, e, d, n):
        self.e = e
        self.d = d
        self.n = n

    def encrypt(self, message):
        message = bytes_to_long(message)
        ciphertext = pow(message, self.e, self.n)
        return long_to_bytes(ciphertext)

    def decrypt(self, ciphertext):
        ciphertext = bytes_to_long(ciphertext)
        message = pow(ciphertext, self.d, self.n)
        return long_to_bytes(message)


class Challenge:
    def __init__(self, message):
        self.generate_key()
        self.message = message

    def generate_key(self):
        key = RSA.generate(2048)
        self.key = RSAKey(key.e, key.d, key.n)

    def get_public_key(self):
        n = base64.b64encode(long_to_bytes(self.key.n)).decode()
        print(f'[pkey] {n}')

    def get_secret_message(self):
        ciphertext = self.key.encrypt(self.message)
        ciphertext = base64.b64encode(ciphertext).decode()
        print(f'[shhh] {ciphertext}')

    def send(self, ciphertext):
        ciphertext = base64.b64decode(ciphertext)
        message = self.key.decrypt(ciphertext)
        if message[-1:] != b'.':
            raise Exception('Be polite. Your message should terminate with a full-stop.')
        print('nice')

def main():
    c = Challenge(message)

    while True:
        command = input('[cmd] ').split(' ')

        try:
            if command[0] == 'send':
                c.send(command[1])
            elif command[0] == 'pkey':
                c.get_public_key()
            elif command[0] == 'read':
                c.get_secret_message()
        except:
            print('nope')

if __name__ == '__main__':
    main()

Okay. So seems that this is a RSA-2048 crypto challenge and there are few commands avaliable.

1. [pkey] => Get the public key in base64 format.
2. [read] => Get the encrypted secret message in base64 format.
3. [send (msg)] => Send the encrypted msg to Alice in base64 format.

### Kicking off

Let's see what we have for the RSA now. We could get $n$, the public key from the output of the program. We could also get $c$, the ciphertext of the flag. How about the public key exponent $e$? If we search for the function $RSA.generate()$ online, it will set $e = 65537$ as default. However, we don't have the private key exponent $d$ nor the original secret message $m$, which is the thing that we want!

What we have now is enough for doing encryption because $c \equiv m^e\ (\text{mod}\ n)$, but we can't do decryption because $m \equiv c^d\ (\text{mod}\ n)$ which we don't have $d$ in our hand.

However, there is one thing that concerns us. After sending the encrypted message, it would tells us if the decrypted message is ended with a `.`(dot). We could't get any other information about the decrypted message, but just if it ends with a dot. We could consider this as an oracle function and this would be our starting point as there is no other things in this challenge that we can use for exploit.

Also, by sending the encrypted flag back to Alice, the oracle function tells us that the original message ends with a dot too. Of course as expected, because Alice is a polite girl, right? :smile:

### Getting ideas

Knowing whether the last byte is a dot - kind of similar to RSA LSB oracle attack! (Reference: [CTF-Wiki](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_chosen_plain_cipher/#rsa-byte-oracle)) Where the difference is that for RSA LSB oracle attack, the oracle function returns the value of the last byte to us. However, this time, the function just returns whether it is a dot or not. How could we get the original message with just little information?! It seems impossible!

<br />

> Nothing is impossible.
> [name=Someone]

<br />

Ok. Well. This task should be similar to RSA LSB oracle attack though. Let's get some idea from the RSA LSB oracle attack.

What we could get is that, the first step of most of the RSA oracle attacks follow these steps.

1. This is how our ciphertext generated:
$$c \equiv m^e\ (\text{mod}\ n)$$
2. If we multiply our ciphertext with some constant $s^e$:

$$s^ec \equiv s^em^e \equiv (sm)^e\ (\text{mod}\ n)$$

Therefore, when the server tries to decrypt $s^ec$, it will get $sm\ (\text{mod}\ n)$ instead of the original message $m\ (\text{mod}\ n)$.

### One tricky part

And now we can somehow manipulate what the server will get after it decrypts a ciphertext. Let's put the encrypted secret message as the ciphertext $c$. What value of $s$ should be chosen? What are we going to do?

In fact, usually the original message $m$ is much much smaller than $n$. Therefore, $m\ (\text{mod}\ n)$ still results $m$ so that the server could get back the original message.

What if we set the value of $s$ very large, making $sm$ just slightly bigger than $n$? In another way, finding the **minimum(can be slightly larger)** $s$ that satisfies
$$sm - n > 0$$

This can be written as like the following, where $r$ is the remainder with $r < m$ and $m << n$
$$sm = n + r$$

$$sm \approx n$$

$$m = \frac{n}{s}$$

Tada! We could then find $m$ once we find the specfic $s$ that satisfies the equation!

### An important dot
Assume increasing the value of $s$ from $2$ one by one, each time sending $s^ec$ to the server, how could we know when the value of $sm$ exceeds $n$? We know that the server will do $sm\ (\text{mod}\ n)$ everytime, but the $(\text{mod}\ n)$ has no effect when $sm < n$. At the moment $sm \geq n$, the server will get $(sm - n)$ as the message. Is it possible to detect this moment? YES!

Here's the time for the oracle function works. The byte representation of `.` is `0x2e`. If we multiply `0x2e` with `0x81`, we get `0x172e`. The last byte is still `0x2e`! So this means if we set any value of $s$ with the last byte be `0x81`, the server should also get $sm\ (\text{mod}\ n)$ with the last byte be `0x2e` and the oracle function will return true. **UNLESS,** for the moment that $sm \geq n$, the last byte of $sm$ (`0x2e`) will minus the last byte of $n$. As the last byte of $n$ will never be `0x00` ($n$ is always odd), the resultant byte must not equals to `0x2e` and the orcale function will return false.

Therefore, by testing values of $s$ in ascending order that end with the byte `0x81`(E.G. `0x181`, `0xA81`, `0x12381`), at the moment that the orcale function suddenly return false, that $s$ value would be the one that we want.

### Finding the message
Before starting to find the value of $s$, there is one small problem that we have to solve, actually we could not increment the value of $s$ one by one to try (i.e. `0x181`, `0x281`, `0x381`...). As $m << n$, the target value of $s$ would be very large(more than 100 bytes) and it would take billion of years to find $s$! Luckily, this is not difficult to solve.

1. Repeatly append `0xf` to `0x81` as $s$ until the oracle function return false (e.g. `0xf81`, `0xff81`, `0xfff81`...), denote it as $s$_$0$. When the oracle function return false, it means that the value of $s$ is greater than the value you previously tried and smaller than $s$_$0$.

2. Choose $s$_$0$ as the value of $s$. Start from the leftmost digit of $s$, for a digit, decrease it by 1 until the oracle function returns true (or the digit reaches 0). If the oracle function returns true, increase the digit back by 1. Then proceed to do the same procedure for the next digit on the right. This makes $sm$ always larger then $n$, while making $s$ as minimum as possible.

Therefore, here is the final code:

import base64
import math
from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwn import *

def orcale_ifValid(msg_long):
    msg_base64 = base64.b64encode(long_to_bytes(msg_long))
    msg_full = b'send ' + msg_base64
    proc.sendline(msg_full)
    data = proc.recvuntil(b'[cmd] ')
    result = data.replace(b'\n[cmd] ', b'')
    return (result == b'nice')

proc = remote('tertiary.pwnable.hk', '50013')

data = proc.recvuntil(b'[cmd] ')
proc.sendline(b'pkey')
data = proc.recvuntil(b'[cmd] ')
data = data.replace(b'[pkey] ', b'')
n_base64 = data.replace(b'\n[cmd] ', b'')

proc.sendline(b'read')
data = proc.recvuntil(b'[cmd] ')
data = data.replace(b'[shhh] ', b'')
c_base64 = data.replace(b'\n[cmd] ', b'')

n = bytes_to_long(base64.b64decode(n_base64))
e = 65537
c = bytes_to_long(base64.b64decode(c_base64))

s = 0x81
count = 2
while True:
    s += pow(16, count) * 15
    print(hex(s))
    c1 = pow(s, e, n) * c
    valid = orcale_ifValid(c1)
    if not valid:
        break
    count += 1


times = 0
while True:
    if times < 15:
        s -= pow(16, count)
        print(hex(s))
        c1 = pow(s, e, n) * c
        if orcale_ifValid(c1):
            s += pow(16, count)
            times = 0
            count -= 1
            if count == 1:
                break
        else:
            times += 1
    else:
        times = 0
        count -= 1  
        if count == 1:
            break
print(long_to_bytes(n//s))

We finally got the secret message: `Hey, congratulations on solving the challenge. But please hkcert20{c4lm_d0wn_4nd_s0lv3_th3_ch4llen9e}.`

###### tags: `CTF`, `HKCert20CTF`