# P.W.N. CTF 2018

## City RSA - Points:557

### Challenge

I know that frank that a**hole ate the last cookie, but no one believes me.

He wrote himself a service to sign messages, I found part of the source.

It runs here:

nc rsa.uni.hctf.fun 4422

Can you get me the message "YES, I did eat the last cookie" signed by his service?

I added a verifier for you using his public key:

nc checker.uni.hctf.fun 31337

### Analysis
The sender message is signed by RSA in main.c

    printf("Enter message:");
    .....
    /* Sign via RSA */
    city_rsa_init(&cfg, p_str, q_str, p_inv_str, d_str, e_str, d_p_str, d_q_str);
    //city_print_config(&cfg);
    city_rsa_sign(&cfg, result, input_hex);
    printf("The signature of your message is: 0x%s\n", result);

The receiver verify message by main.py

#!/usr/bin/env python3

pubkey = {
        'e': 0x10001,
        'N': 0x98ac865ef6a31313e50fb37853ce96804cb2d864e2a4d14bf7cca85a444a40b453de7c3ae8416e8976cd1cac7f548a43fe8c2eb3d4cfcd3808cf9458c0c87bf4c037d515d22d1299b72e79fcd4a1d1531789cb3013031fb0e28fdfe73f090027b3b3428cacef6dbf7823d5da8d3158101e0c07e707224d451fcbb3114ab85a925bcb7faf9b317bbbddba81285ab93f0ee5f968b258f4675e9d893ec7f0e8379b67527d78fe920ab201cb3a6459d4f3902754b36e3264db7727c6d32e014593c39991f54c7b034d69b986616a39454c85d9e032afa853a6e12fea06472ed3573707da3df9ca7ce8d2c3b820e745da6e3cc523789f858d98645ea042bb54b463d3
}


def main():
        ct = int(input("Input signed message:"), 16)
        msg = pow(ct, pubkey["e"], pubkey["N"])
        msg = int.to_bytes(msg, 128, "big")

        if b"YES, I did eat the last cookie" in msg:
                flag = open("/opt/flag.txt").read()
                print(flag)
        else:
            print("Nope, sorry.")


if __name__ == '__main__':
        main()

If signed message contains 'YES, I did eat the last cookie', we can have flag. However, the service block us from getting the message signed directly by checking if 'YES' is inside the message.

### RSA Blind Attack?
Apparently, we can use RSA blind attack to forge the signed message. However, the input length and characters are restricted by c api. Only 30 characters can be input and the maximum value of character have to be under 0x7f.

The blind attack attack can bypass the check by...

$c \equiv m^d\ (\ mod\ N\ )$

$c' \equiv m^dr^d\ (\ mod\ N\ )$

$c \equiv c'r^{-1}\ (\ mod\ N\ )$

But, we cannot send $m^dr^d$ to service and get signed.

### Exploit
Since we cannot use RSA blind attack directly, we can try to factor the forged message and use modular multiplicative inverse to find all our ingredients.

#### find possible prime factors
use sage to find prime factors.

msg = 'YES, I did eat the last cookie'
import binascii
for a in string.ascii_letters:
    tmp = msg+a
    v = int(binascii.hexlify(tmp),16)
    factor(v)

after few minues, we have a good candidate.

2 * 3 * 5 * 313 * 379 * 33311 * 15239591 * 2184081073 * 454801932889 * 4706963699932381 * 18672853823680873391

then, we try to send those factors into sign service with different multiplier to control our characters are under 0x7f.

(1, 2)
(1, 3)
(1, 5)
(1, 313)
(3, 379)
(2, 33311)
(8, 15239591)
(12, 2184081073)
(73, 454801932889)
(21, 4706963699932381)
(31, 18672853823680873391L)

Here is the final exploit.

from pwn import *
import binascii
from Crypto.Util.number import *
import gmpy

msg = 'YES, I did eat the last cookie'
N = 0x98ac865ef6a31313e50fb37853ce96804cb2d864e2a4d14bf7cca85a444a40b453de7c3ae8416e8976cd1cac7f548a43fe8c2eb3d4cfcd3808cf9458c0c87bf4c037d515d22d1299b72e79fcd4a1d1531789cb3013031fb0e28fdfe73f090027b3b3428cacef6dbf7823d5da8d3158101e0c07e707224d451fcbb3114ab85a925bcb7faf9b317bbbddba81285ab93f0ee5f968b258f4675e9d893ec7f0e8379b67527d78fe920ab201cb3a6459d4f3902754b36e3264db7727c6d32e014593c39991f54c7b034d69b986616a39454c85d9e032afa853a6e12fea06472ed3573707da3df9ca7ce8d2c3b820e745da6e3cc523789f858d98645ea042bb54b463d3
def getsign(m):
    context.log_level = 'WARN'
    p = remote('rsa.uni.hctf.fun', 4422)
    dmsg = long_to_bytes(m)
    p.sendline(dmsg)
    p.recvuntil('The signature of your message is: ')
    m = int(p.recvline(), 16)
    p.close()
    return m

x100 = gmpy.invert(getsign(0x100), N)

d = [2, 3, 5, 313, 379, 33311, 15239591, 2184081073, 454801932889, 4706963699932381, 18672853823680873391]
d = [2, 3, 5, 313, 379, 33311, 15239591, 2184081073, 454801932889, 4706963699932381, 18672853823680873391]
mods = {}
flag = 1
for v in d:
    for i in range(1, 0xff):
        m = long_to_bytes(v*i)
        found = True
        for n in m:
            if ord(n) > 0x79:
                found = False
                break
        if found:
            print(i, v)
            if i == 1:
                mods[v] = (getsign(v<<8) * int(x100))%N
                flag *= mods[v]
            else:
                tmp = (getsign(v*i<<8) * int(x100))%N
                if i in mods:
                    flag *= (tmp*gmpy.invert(mods[i], N)) % N
                else:
                    iinvert = (getsign(i<<8) * int(x100))%N
                    flag *= (tmp*gmpy.invert(iinvert, N)) % N
            break
print(hex(flag%N))
print(pow(flag%N, 0x10001, N))

Send the signed message to receiver to get the flag.

% nc checker.uni.hctf.fun 31337
Input signed message:0x85a8277792bcd656724e92dad50ee5ed31de54ecf746849a0605be3afd27c75492196d5cbc35957f85d0f962aa520aab50b83025797f1f7c3f5ae84b1e66976a520d5d98c4b88eb19078ec78c7d07ad5149e382ffba52d4e9d2ad40718545c3a1296b3026324d0e6a12141363ef272e42139438cd180a94b350818cd39c24f2c6d0241d80e01febf305f0866111816ff1be8823a66eed866545d1dab69ba0748d17b5344a75ea3d340bc6b2e0ca6db3c3db2bc7e22a0ce3b8ea06851ce2be7a16ff3931d5e8cb8b01b757aa6c975e98a7fb36acd1eb8b96210affeaa638b93fa9fc68960544a3b7df88d1a496b107125465e479e99d87b47a825aed9b54095d4
flag{https://www.youtube.com/watch?v=MpMBETNC-44#C0ngr4tz}

It is an excellent challenge, good job.