Writeup for Crypto Problems in SCTF 2019

warmup

Analysis

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/python
# -*- coding: utf-8 -*-

from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from Crypto.Random import get_random_bytes
from FLAG import flag

class MAC:
    def __init__(self):
        self.key = get_random_bytes(16)
        self.iv = get_random_bytes(16)

    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 code(self, msg):
        res = chr(0)*16
        for i in range(len(msg)/16):
            res = strxor(msg[i*16:(i+1)*16], res)
        aes = AES.new(self.key, AES.MODE_CBC, self.iv)
        return aes.encrypt(res).encode('hex')

    def identity(self, msg, code):
        if self.code(msg) == code:
            msg = self.unpad(msg)
            if msg == 'please send me your flag':
                print 'remote: ok, here is your flag:%s' % flag
            else:
                print 'remote: I got it'
        else:
            print 'remote: hacker!'


if __name__ == '__main__':
    mac = MAC()
    message = 'see you at three o\'clock tomorrow'
    print 'you seem to have intercepted something:{%s:%s}' %(mac.pad(message).encode('hex'), mac.code(mac.pad(message)))
    print 'so send your message:'
    msg = raw_input()
    print 'and your code:'
    code = raw_input()
    mac.identity(msg.decode('hex'), code)
    exit()

得到信息:

  1. AES_CBC模式加密

  2. 已知的1个明-密文对:pad('see you at three o\'clock tomorrow') - 从服务器收到的密文
  3. 明文长度48=16*3,AES加密的是strxor后的明文

  4. 输入msg和code,其中msg要满足unpad(msg)后是'please send me your flag',而且用同样的key和IV加密这个msg后得到的内容是自己输入的code

AES attack

由于密钥key和初始向量IV都是随机生成的,不可能爆破出来,所以key和IV是未知的。但想要用同样的key和IV重新AES加密自己输入的msg来使加密结果等于自己输入的code,这在未知key和IV的情况是是不可能的,除非只能构造跟

一样的明文和密文来验证。

注意到这边对长度超过16的明文加密前的操作:一个是pad,还有一个就是strxor

message每次都是固定的,都是‘see you at three o’clock tomorrow’,pad后就是'see you at three o'clock tomorrow\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f',然后再对这个pad后的结果进行strxor操作,也就是分成3组,每组对应位置的字符异或,然后得到一个16bytes长的res,每次pad后的结果也都是一样的,所以第一次加密的res也都是一样的,可以先算出来,是res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05',所以每次AES都是对这个加密。

这里,我们可以构造一个msg,使得:

  1. unpad(msg) = 'please send me your flag'
  2. strxor(pad(msg)) = res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'

首先又注意到这边的pad,unpad函数的一个性质:

unpad时,是按照末尾字节的值来截断尾部的。

len('please send me your flag') = 24,所以截断后的长度必须为24,且msg[:24]='please send me your flag'

再次,要使strxor(pad(msg)) = res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05',仅仅长为24的'please send me your flag'是无法满足要求的,需要至少扩充到16×3=48位。 那么如果这里我们选择的msg长度为48的话,末尾字节的值必须是3×16-24=24=0x18`,所以msg[47]=’\x18’``。

现在,只需要填充剩余的msg[24:47],使得strxor(pad(msg))后的结果是res就可以了。

下面是我的一个填充方法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def fuck()
    pad_message = 'see you at three o\'clock tomorrow' + 15 * chr(15)
    res = chr(0) * 16
    for i in range(len(pad_message) / 16):
        res = strxor(pad_message[i*16:(i+1)*16], res)
    # res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'
    msg = 'please send me your flagdeadbee' # 填充到16*2-1长,后面的用异或算出来就可以了。
    msg += chr(ord(msg[15])^ord(res[15])^(16*3-24)) # 第16*2位不能填充,需要根据第16*1位和16*3位算出来
    payload3 = ''
    for i in range(15): #第三段的前15位
        payload3 += chr(ord(msg[i]) ^ ord(msg[i + 16]) ^ ord(res[i]))
    payload3 += chr(16*3 - 24) # 最后一位
    return msg + payload3

然后就能构造出满足上面两个条件的msg,最后只要把这个msg和之前服务器发过来的密文发过去就可以了。

exp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pwn import *
from Crypto.Util.strxor import strxor

def fuck():
    pad_message = 'see you at three o\'clock tomorrow' + 15 * chr(15)
    res = chr(0) * 16
    for i in range(len(pad_message) / 16):
        res = strxor(pad_message[i*16:(i+1)*16], res)
    # res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'
    msg = 'please send me your flagdeadbee'
    msg += chr(ord(msg[15])^ord(res[15])^(16*3-24))
    payload3 = ''
    for i in range(15):
        payload3 += chr(ord(msg[i]) ^ ord(msg[i + 16]) ^ ord(res[i]))
    payload3 += chr(16*3 - 24)
    return msg + payload3
    # 'please send me your flagdeadbeed;\x1cZ\r\x0f\x06XPO\x04ER\x07\x0f]\x18'

r = remote('47.240.41.112', 12345)
context.log_level = 'debug'

code = r.recvline()[-34:-2]
r.recvuntil('message:\n')
r.sendline(fuck().encode('hex'))
r.recvuntil('code:\n')
r.sendline(code)

r.interactive()
# remote: ok, here is your flag:sctf{y0u_4r3_7h3_4p3x_ch4mp10n}

babygame

Analysis

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#!/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 ,以及另外一篇给出了方法的文章

获得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代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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”,再xorkey_stream,就得到了伪造的cipher,发过去解密,就能成功通过check,拿到flag了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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/

[2] https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Generalizations

[3] https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Hastad-Broadcast