hitcon2016 misc writeup

hitcon遇到了很多有趣的misc,学了很多东西,所以就专门整理一个wp吧。

Beelzemon

这是一道ppc题目

1
2
3
Beelzemon gives you two integers 1 <= k <= n <= 20.
It wants to know if you can split a set {a | -(2**n) <= a <= (2**n) - 1} into two sets A, B s.t. |A| = |B| and sum({a**k | a in A}) = sum({b**k | b in B}).
Give Beelzemon either A or B to save your life. (separate the numbers by space)

简单描述下题意

大概有几点:

1、k\n在1到20之间,并且k<=n
2、a是一个从-(2**n)(2**n)的整数集合
3、A\B中元素数量相等,并且和相等

这时候我们我们需要一些理论支持了,当天在做题的时候,我找到了这样一篇文章

https://zhuanlan.zhihu.com/p/20559045

这里有一个理论

所以

但是我们又遇到了一个问题,题目中需要对包括负数的集合做处理(当时也没想明白),后看来看了wp才明白这里

https://github.com/JulesDT/ctfWriteUps/tree/master/Hitcon%20Quals%202016/Beelzemon%20-%20PPC%20-%20150%20pts

贴上解题脚本

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
import socket
import re
import operator
import time
def find_partition(int_list,n,k):
len_A=0; len_B=0; sum_A=0; sum_B=0
Aret = ""; Bret = ""
for i in range(0,len(int_list)):
int_list[i] += 2**n
int_list=int_list[::-1]
for nb in int_list:
if nb == 0:
if len_A < len_B:
len_A+=1
Aret+= str(-2**n)+ " "
else:
len_B+=1
Bret+= str(-2**n)+ " "
else:
if sum_A < sum_B:
sum_A+=(nb**k)
len_A+=1
Aret+=str(nb-(2**n))+ " "
else:
sum_B+=(nb**k)
len_B+=1
Bret+=str(nb-(2**n))+ " "
return (Aret)
def main():
begin = time.time()
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('52.198.217.117', 6666))
while True:
data = s.recv(2048)
print "Received:", data
if len(repr(data)) <=2 :
break;
mgex = re.search('([0-9]+) ([0-9]+)', repr(data))
if mgex != None:
n = long(mgex.group(1));
k = long(mgex.group(2));
mySet = range(-2**n,2**n);
partition = find_partition(mySet,n,k)
s.send(partition+'\n');
print "Connection closed."
s.close()
print "Process duration :", time.time() - begin
main()

这里我们看到列表通过了处理

1
int_list[i] += 2**n

通过这样的处理,所有本来的负数就被处理成了正数,然后再插入结果列表的时候在去掉,然后再利用刚才的理论,就可以得到结果了

hackpad

刚开始看到上来get 3次,然后就post暴力跑什么东西,错误的返回500,正确的返回200,那么看上去像是在跑cbc的iv了。

所以这里是padding oracle attack

web小白上也有提到这种攻击方式

http://blog.zhaojie.me/2010/10/padding-oracle-attack-in-detail.html

简单来说就是这个逻辑

1
2
3
接受到正确的密文之后(填充正确且包含合法的值),应用程序正常返回(200 - OK)。
接受到非法的密文之后(解密后发现填充不正确),应用程序抛出一个解密异常(500 - Internal Server Error)。
接受到合法的密文(填充正确)但解密后得到一个非法的值,应用程序显示自定义错误消息(200 - OK)。

那么我们需要把每一次跑到的xor 0x01,0x02,0x03,然后异或对应密文。

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
def xor_c(s, key):
r = ''
for c in s:
r += chr(key ^ ord(c))
return r
def xor_ss(s1, s2):
r = ''
for i in range(len(s1)):
r += chr(ord(s1[i]) ^ ord(s2[i]))
return r
def main():
bs = open('hackpad.pcap', 'rb').read()
i = 0x2634 -1
cs = []
j = 0
flag = ''
while i!=-1:
i = bs.find('POST / HTTP/1.1', i+1)
msg = bs.find('msg=', i)
res = bs.find('HTTP/1.1', msg)
if bs[res+9] == '2':
iv = bs[msg+4:msg+36]
c = bs[msg+36:msg+68]
if iv[0] != '0':
#print iv,
iv = xor_c(iv.decode('hex'), 0x10)
cs.append(c.decode('hex'))
if j != 0:
flag += xor_ss(cs[j-1], iv)
j += 1
#print iv.encode('hex'), c
print flag
if __name__ == "__main__":
main()

ps:脚本是看wp的时候拖来的,并不是自己写的Orz

RegExpert

考验正则的题目,做题目的时候由于对正则实在太不熟悉了,导致第一步都没有过,所以今天仔细研究下。

select

1
2
================= [SQL] =================
Please match string that contains "select" as a case insensitive subsequence.

上来第一步是select,条件是必须正则匹配到所有包含select的子字符串,在select中的任意位置都可以插入任意字符。

于是当时我的初版正则是长这样的

1
[Ss][A-Za-z]?[eE][A-Za-z]?[lL][A-Za-z]?[eE][A-Za-z]?[cC][A-Za-z]?[tT]

当然是有长度限制的

1
(?i)s.*e.*l.*e.*c.*t

递归正则?

1
2
=============== [a^nb^n] ================
Yes, we know it is a classical example of context free grammer.

实话实说,没有特别搞明白这个题的意思,大概是说递归语法?

这里应该需要用到ruby的语法\g<1>?

payload:

1
^(a\g<1>?b)$

素数

1
2
================= [x^p] =================
A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself.

这里需要强制所有元素为x,为了避免空的正则,所以我们需要^xx+$结尾

1
(?!(xx+)\1+$)^xx+$

回文?

1
Both "QQ" and "TAT" are palindromes, but "PPAP" is not.

看上去应该同样是类似于递归的判断方式,取回文?我们需要匹配axa的模式,a为任意字符串模式

1
2
3
4
5
^(\w?|(\w)\g<1>\k<2>)$
或者
((.)(\g<1>)\2|.?)

上下文敏感语法

1
2
============== [a^nb^nc^n] ==============
Is CFG too easy for you? How about some context SENSITIVE grammer?

网上能找到相应的语法

1
\A(?<AB>a\g<AB>b|){0}(?=\g<AB>c)a*(?<BC>b\g<BC>c|){1}\Z

可以简略到

1
^(?=(a\g<1>?b)c)a+(b\g<2>?c)$

文章目录
  1. 1. Beelzemon
  2. 2. hackpad
  3. 3. RegExpert
    1. 3.1. select
    2. 3.2. 递归正则?
    3. 3.3. 素数
    4. 3.4. 回文?
    5. 3.5. 上下文敏感语法
|