# zer0ptsCTF 2023 writeup

- Cuối tuần vừa rồi (15/7 - 16/7) đã diễn ra giải zer0ptsCTF, mình đã đánh cho team ``m1cr0$oft 0ff1c3`` và kết thúc giải ở vị trí thứ 48.


- Giải lần này thì mình chỉ solve được 2/6 câu crypto, những câu còn lại tương đối khó (chắc là do trình chưa đủ 😥).

- Dưới đây là writeup cho các challenge mà mình đã giải được.

## writeup available for:
### Crypto:
1. [SquareRNG](#SquareRNG)
2. [easy-factoring](#easy-factoring)

## SquareRNG

>I wrote a pseudorandom number generator. You can't guess the next bit without knowing each other's secret.
>
>nc crypto.2023.zer0pts.com 10666
>
>author: ptr-yudai

Attachments:
* server.py

#!/usr/bin/env python3
import os
from Crypto.Util.number import getPrime, getRandomRange

def isSquare(a, p):
    return pow(a, (p-1)//2, p) != p-1

class SquareRNG(object):
    def __init__(self, p, sa, sb):
        assert sa != 0 and sb != 0
        (self.p, self.sa, self.sb) = (p, sa, sb)
        self.x = 0

    def int(self, nbits):
        v, s = 0, 1
        for _ in range(nbits):
            self.x = (self.x + 1) % p
            s += pow(self.sa, self.x, self.p) * pow(self.sb, self.x, self.p)
            s %= self.p
            v = (v << 1) | int(isSquare(s, self.p))
        return v

    def bool(self):
        self.x = (self.x + 1) % self.p
        t = (pow(self.sa, self.x, self.p) + pow(self.sb, self.x, self.p))
        t %= self.p
        return isSquare(t, self.p)

p = getPrime(256)


sb1 = int(input("Bob's seed 1: ")) % p
sb2 = int(input("Bob's seed 2: ")) % p
for _ in range(77):
    sa = getRandomRange(1, p)
    r1 = SquareRNG(p, sa, sb1)
    print("Random 1:", hex(r1.int(32)))
    r2 = SquareRNG(p, sa, sb2)
    print("Random 2:", hex(r2.int(32)))

    guess = int(input("Guess next bool [0 or 1]: "))
    if guess == int(r1.bool()):
        print("OK!")
    else:
        print("NG...")
        break
else:
    print("Congratz!")
    print(os.getenv("FLAG", "nek0pts{*** REDACTED ***}"))

Nhận xét:
- Đây là challenge đầu tiên xuất hiện và được gắn tag warm up.
- Tóm tắt sơ qua flow của bài:
+ Ta cần gửi đến server 2 seed **sb1** và **sb2**.
+ Khi này server sẽ nhận 2 seed ta vừa nhập modulo **p** (p là số nguyên tố) và bắt đầu random 1 số **sa** trong khoảng [1, p].
+ Tiếp theo đó server sẽ cho ta biết kết quả của method int(nbits) của 2 object **r1** và **r2** của class SquareRNG.
+ Sau đó, server yêu cầu ta đoán output của method bool của object **r1**.
- Như vậy, toàn bộ các phép tính trong bài này đều được gói gọn trong class SquareRNG. Bây giờ, ta sẽ tiến hành nghiên cứu class SquareRNG.
- Đầu tiên là method `__init__` của class, ta có thể hiểu đây là method dùng để khai báo các tham số của object trong class. Quan sát thấy **r1** và **r2** khi được khai báo đều sử dụng chung tham số **sa** và **p**, duy chỉ khác nhau ở seed đầu vào **sb1** và **sb2** do ta nhập (Điều kiện là sa và sb được nhập vô đều phải **không** ≡ 0 (mod p). (Ở đây theo kinh nghiệm của mình thì chắc chắn **r1** và **r2** sẽ có sự liên quan nhất định đến nhau).
- Tiếp theo là method `int(self, nbits)` của class, phân tích qua đoạn code ta sẽ thấy được rằng $s = 1+\sum\limits_{x = 1}^{nbits}{sa^{x} * sb^{x}}$ và output của method sẽ cho ta biết với từng x một trong công thức trên sẽ mang giá trị 0 hay 1.

- Giá trị 0 hay 1 ở trên được tính thông qua hàm isSquare(a, p) và hàm đó sẽ cho ta biết kết quả của `pow(a, (p-1)//2, p) != p-1`. Nhìn kĩ công thức trong hàm này ta lại thấy ngay đây chính là công thức của [Legendre Symbol](https://en.wikipedia.org/wiki/Legendre_symbol). Như vậy, ta có thể kết luận ngay hàm isSquare(a, p) này cho chúng ta biết số a được nhập vô có phải là 1 số [Quadratic Residues](https://en.wikipedia.org/wiki/Quadratic_residue) (QR) trên modulo p hay không.

- Cuối cùng là method `bool(self)`, output của method này sẽ check xem $sa^x + sb^x$ có phải là 1 số QR như đã nói ở trên hay không.

- Một điều cần lưu ý khác trong bài này là ta cần đoán output của r1.bool() sau khi đã gọi r1.int(32), tức là ta đang cần check xem $sa^{33} + sb1^{33}$ có phải là QR không.

- Ta có thể thấy trong công thức trên có dạng $a^n + b^n$ và n là số lẻ vừa hay thỏa công thức dưới đây.

- Như vậy, thay b = 1, n = 33 vào công thức ở trên, ta sẽ thu được
$a^{33} + 1^{33} = (a+1)(a^{32} - a^{31} + a^{30} + ... + 1)$

- Như vậy, ta đã có thể phân tích $sa^{33} + sb^{33}$ thành 2 factor và như ta đã biết rằng để $sa^{33} + sb^{33}$ là số QR thì ta cần 2 factor của nó hoặc đồng thời là QR hoặc đồng thời không là QR.


- Tiếp theo, ta sẽ để ý rằng nếu như ta nhập sb = 1, kết quả của method `int(self, nbits)` thu được sẽ có dạng $s = 1+\sum\limits_{x = 1}^{nbits}{sa^{x}} = 1 + sa^1 + sa^2 + ... + sa^{32}$
- Còn nếu ta nhập sb = -1, ta sẽ thu được $s = 1 - sa^1 + sa^2 - ... - sa^{31} + sa^{32}$

- Đối chiếu với factor thứ hai trong expansion của $a^n + b^n$, ta thấy rằng 2 bọn nó là như nhau. Vì thế nếu nhập sb = -1, thì bit cuối cùng của output của method `int(self, nbits)` sẽ cho ta một nửa dữ kiện để kết luận. Nửa dữ kiện còn lại sẽ đến từ bit đầu tiên của sb = 1.

- Như vậy, ở bài toán này, ta chỉ cần đơn giản gửi lên 2 seed 1 và -1. Khi đó dựa vào bit cuối của seed -1 và bit đầu của seed 1 là đủ dữ kiện để ta có thể kết luận số tiếp theo của seed 1 có phải là QR hay không.

Script:

from pwn import *
import time


r = remote("crypto.2023.zer0pts.com", 10666)


r.recvuntil(b"Bob's seed 1: ")
r.sendline(b"1")
r.recvuntil(b"Bob's seed 2: ")
r.sendline(b"-1")


def cal(a, b):
	# XNOR function
	"""
	based on a^n + b^n = (a+b)...
	and also legendre symbol 
	"""
	return 1 if a == b else 0

for _ in range(77):
	print(f"Try {_}")
	r.recvuntil(b"Random 1: ")
	r1 = int(r.recvline().rstrip(), 16)
	r.recvuntil(b"Random 2: ")
	r2 = int(r.recvline().rstrip(), 16)
	
	print(bin(r1), len(str(bin(r1)[2:])))
	print(bin(r2), len(str(bin(r2)[2:])))
	print(r1>>31)
	print(r2&1)
	#r.interactive()
	res = cal(r1>>31, r2&1)
	print(res)
	r.recvuntil(b"Guess next bool [0 or 1]: ")
	r.sendline(str(res).encode())
	print("~"*40)
	time.sleep(1)

r.interactive()

#zer0pts{L(a)L(b)=L(ab)}


-> Flag: `zer0pts{L(a)L(b)=L(ab)}`

## easy-factoring

>The word "decomposition" has multiple meanings.
>Can you decompose?
>
>nc crypto.2023.zer0pts.com 10333
>
>author: mitsu

Attachment:
* server.py

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)

Nhận xét:
- Bài trên là một bài mình làm khá tà đạo (mình sẽ update cách chính đạo sau 😥)
- Sơ qua về bài trên, server sẽ cho ta biết $N = p^2 + q^2$
- Nhiệm vụ của ta là từ số **N** đã cho, ta cần tính được số p, q ban đầu.
- Đây là một bài toán thuộc dạng **sum of two square**
- Và ở đây mình đã sử dụng [Alpertron](https://www.alpertron.com.ar/ECM.HTM) để tính được p, q ban đầu.
- Ta sẽ liên tục thu các số N và thử tính p, q đến khi nào thu được p, q là số nguyên tố.




## Kết luận
- Ở trên là danh sách 2 bài mảng crypto mình solve được trong giải zer0ptsCTF 2023.
- Mọi thắc mắc của các bạn xin vui lòng liên hệ với mình qua discord: ``tranminhprvt01#7535``
- Cuối cùng, cảm ơn các bạn đã đọc. Have a good day! 🥰