###### tags: `writeups`

# Writeup for babygame in 2019 SCTF

## Analysis

#!/usr/bin/python
# -*- coding: utf-8 -*-

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from binascii import *
from FLAG import flag
from MESSAGE import message


class telecom:
    def __init__(self, name):
        self.name = name
        self.key = get_random_bytes(16)
        self.iv = get_random_bytes(16)

        self.e = 3

        p = getPrime(512)
        q = getPrime(512)
        self.fn = (p-1)*(q-1)

        while True:
            if GCD(self.e, self.fn) != 1:
                p = getPrime(512)
                q = getPrime(512)
                self.fn = (p - 1) * (q - 1)
            else:
                break

        self.d = inverse(self.e, self.fn)
        self.n = p * q

    def RSA_encrypt(self, plaintext):
        assert bytes_to_long(plaintext).bit_length() < 512

        a = getPrime(512)
        b = getPrime(512)
        m = bytes_to_long(plaintext)
        c = pow(a * m + b, self.e, self.n)


        message = 'admin:'+self.name+ ', your ciphertext is: c=' +hex(c)+ '\nwith some parameters:a=' +hex(a)+ ', b=' +hex(b)+'\n'
        return message

    def RSA_decrypt(self):
        pass

    def broadcast(self):
        message = self.name+':'+'my pub-key is: '+'e='+str(self.e)+','+'n='+hex(self.n)+'\n'
        return message

    def pad(self, msg):
        pad_length = 16 - len(msg) % 16
        return msg + chr(pad_length) * pad_length

    def unpad(self, msg):
        return msg[:-ord(msg[-1])]

    def AES_encrypt(self, message):
        message = self.pad(message)
        aes = AES.new(self.key, AES.MODE_OFB, self.iv)
        return aes.encrypt(message)


    def AES_decrypt(self, message):
        aes = AES.new(self.key, AES.MODE_OFB, self.iv)
        return self.unpad(aes.decrypt(message))


def proof_of_work():
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    e = 65537
    fn = (p-1)*(q-1)
    d = inverse(e, fn)

    print "pubkey:{e, n}={65537, %s}\n" %hex(n)
    print 'Give me something you want to encrypt:'
    sys.stdout.flush()
    m = int(raw_input())
    c = pow(m, e, n)

    if m == pow(c, d, n):
        return False
    return True


if __name__ == '__main__':

    if not proof_of_work():
        exit()

    while True:
        print 'You have the following options to do:\n[1]monitor\n[2]forge the message'
        choice = raw_input()

        if int(choice) == 1:

            Alpha = telecom('Alpha')
            Bravo = telecom('Bravo')
            Charlie = telecom('Charlie')

            print Alpha.broadcast()
            print Bravo.broadcast()
            print Charlie.broadcast()

            print Alpha.RSA_encrypt(message)
            print Bravo.RSA_encrypt(message)
            print Charlie.RSA_encrypt(message)
            print 'Alpha:David, make sure you\'ve read this:' + hexlify(Alpha.AES_encrypt(message))+'\n'
        elif int(choice) == 2:
            print 'you can send message to David now:'
            input_cipher = raw_input()
            if Alpha.AES_decrypt(unhexlify(input_cipher)) == message.replace('afternoon', 'morning'):
                print 'you made it, this reward is prepared for you:' + flag
                exit()
            else:
                print 'you failed'
                exit()
        else:
            exit()

得到信息：
- 对同一个message线性pad后(a*m+b)，用不同的公钥加密3次，给出了每次加密完后c,a,b。
- 注意到e=3，低加密指数。
- 需要伪造对message `AES_OFB`模式加密后的密文，使得解密后的明文中的`afternoon`被篡改为`morning`。

## RSA attack
这个RSA很像之前强网杯的Challenge4，感觉可以用广播攻击。

但是这里的m是被pad过的，每次都不一样，所以`Basic Broadcast Attack`失效。

又看到pad是一个很类似强网杯Challenge5，但`Related Message Attack`显然不可能，因为并没有用同一个公钥对线性相关的m加密多次。

陷入困境，感觉这个可能要结合上述两个方法。搜寻一番后，发现果然有一个`Broadcast Attack with Linear Padding`。

结合[wiki](https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Generalizations)，以及另外一篇给出了方法的[文章](https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Hastad-Broadcast)：


获得message，需要:
1. 计算所有n的乘积(n1×n2×n3)
2. 用CRT（中国剩余定理）计算每一个满足条件的T
3. 建立在模N下的多项式环
4. 计算每一个g=(a*x+b)^3-c，这里x就是我们想要的message
5. 计算Ti*gi的和（多项式）并赋值给g
6. 将多项式的最高次项系数化简为1
7. 寻找g的根，多半就是message了

sage代码如下：

n=[82032188601940227752297417081294226543597575504416918007449661834299359067950465277706498580089107996755263427091915970632797292872337319081745842487600650365878082117843668748166556806508008992831799872668452888180728669229746719472110704095075270054792936797172777444638714087380138926023368608670981217091L, 144790109105696916737182878418639456117731330157011040204957460047368669964683349809310287923136309839414697358993776555550819796186587083349149593331591983649252876768081158685346872502328624435541992264407180812711658502822714431271074073131726414451778163016485973268562068628815869252990930579057754896173L, 75291463839461164667469229834843531305640509692662939401339536264435630748347655598022583030492163266505500249672170695051585801149706658572170917049940314913097219983077566373502443956836685905331660776209201294705162873672584599713463731511599324513575176660760395849807244914156996168333606402035878533381L]
c=[67497575318327879887596391364750753705169316916381036313287449919879742983169383559661964321852173414328395486815887056253402772840945029491705527313929081200464807407660414760161256035556293097461881324625478369607471130614351104463500599958969159169050874869751290896066581553838854811211907890750382746511L, 61417831208102453560914910052558296402381558961421547405790778254948342894828953024945127165546949565456233519419089997499796829911888055718138539158703076265672618023467204457469261580970191667410598385021272475612274977806376487258894705386083011345682311011008867926893257606509774484971214854873119396523L, 59139963329969277014867029295568306182785272886586884034466445222852652054855577647906813408336405743993989682438127549115465873135913639429070056018223773094951946677500375796734667908820959638217714514827653064127798201054131814345268242102046781245681177963062451193062599946629137832003277003715562783676L]
a=[10690284821425810281664680252419661592694244929597744471278947260947912212068164535406286136913239607137611205694268949515679703337156206775167860560960531L, 7084608813044653312908744751862853435370315673659572445175422987292025037024211691353987001505135183178528203370140920842675898979940113026011801133323387L, 7109556811500607022678698446990028501935112258837085372401389025171854709554488399418026529159439666193759252114352506000602595045828924640827082875525761L]
b=[8978952666402441172502571446625322184642731589908616056188753886315351207063560919714949439324395532521646399347732857483571187621924964620683026077931937L, 7161265246275328861792856065576124793212521627707981245532742473215873826957088742546550304939190194348241371526295386537134008106992791660625241828335409L, 10713585141780358045259127130466271189717723982908989041527459583656559664545085864785815191726519183276131221864053677348130406321637993310732667315632693L]

from functools import reduce
import gmpy2

def modinv(a, m):
    return int(gmpy2.invert(gmpy2.mpz(a), gmpy2.mpz(m)))


def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a * b, n)
    # 并行运算
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * modinv(p, n_i) * p
    return int(sum % prod)

T = []
T.append(chinese_remainder([n[0],n[1],n[2]],[1,0,0]))
T.append(chinese_remainder([n[1],n[0],n[2]],[1,0,0]))
T.append(chinese_remainder([n[2],n[1],n[0]],[1,0,0]))

N = n[0]*n[1]*n[2]
P.<x> = PolynomialRing(Zmod(N))

g=0
for i in range(3):
    g+=((a[i]*x + b[i])^3 - c[i])*T[i]
g = g.monic()
print g.small_roots()
# [670865060925536167183341633904872636604138549784041874166444071991777516769578599095298315216573752629227374]

用`long_to_bytes`转出来得到**message**:`I will send you the ticket tomorrow afternoon`

## AES attack
这里AES用的是OFB模式，其实上就是一个`stream cipher`，只不过`key`用的是AES加密的结果。

也就是说:
`ENC: AES_cipher = key_stream ^ pad(message)`
`DEC: AES_message = key_stream ^ cipher`

现在有了message，只需要简单的*xor*一下就可以算出key_stream。

`key_stream = AES_cipher ^ pad(message)`

有了`key_stream`，基本上想干什么就能干什么了。

注意到题目里面只需要把解密后的message中的`afternoon`改成`morning`，那么只需要伪造出解密后想要的message = "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05"，再*xor*上`key_stream`，就得到了伪造的cipher，发过去解密，就能成功通过check，拿到flag了。

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


r = remote('47.240.41.112', 54321)

# context.log_level = 'debug'

r.recvuntil("encrypt:\n")
r.sendline("1"*1000)

r.recvuntil("[2]forge the message")
r.sendline("1")

# n, c, a, b = [],[],[],[]

# r.recvuntil("n=")
# n.append(int(r.recvline()[:-2],16))
# r.recvuntil("n=")
# n.append(int(r.recvline()[:-2],16))
# r.recvuntil("n=")
# n.append(int(r.recvline()[:-2],16))

# for i in range(3):
#     r.recvuntil("c=")
#     c.append(int(r.recvline()[:-2],16))
#     r.recvuntil("a=")
#     a.append(int(r.recvuntil(",")[:-2],16))
#     r.recvuntil("b=")
#     b.append(int(r.recvline()[:-2],16))

r.recvuntil("this:")
AES_cipher = r.recvline()[:-1]


# pad_message   = "I will send you the ticket tomorrow afternoon\x03\x03\x03"
# forge_message = "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05"

cipher = unhexlify(AES_cipher)
k_stream = strxor(cipher, 'I will send you the ticket tomorrow afternoon\x03\x03\x03')
forge_cipher = strxor(k_stream, "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05")
payload = hexlify(forge_cipher)


r.recvuntil("[2]forge the message")
r.sendline("2")

r.recvuntil("now:")
r.sendline(payload)

r.interactive()
# you made it, this reward is prepared for you:sctf{7h15_ch4ll3n63_15_n07_h4rd_f0r_y0u_r16h7?}

## More
注意一下`proof_of_work`这边的逻辑，是RSA解密失败了才会继续下去，不然会直接退出。


这里一开始没怎么注意到，就一直`something wrong`，看不到下面的广播信息。

那么，如何才能让RSA解密失败，多半应该只有让m大于n了。

## Reference
[1] [https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/)
[2] [https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Generalizations](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/)
[3] [https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Hastad-Broadcast](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/)