Post

Patriot CTF

solutions of some challenges in Patriot CTF

Posted
By s19ma
8 min read

Bigger is better

It is clearly a wiener attack RSA

1
2
3
4
5
6
7

N = 0xa0d9f425fe1246c25b8c3708b9f6d7747dd5b5e7f79719831c5cbe19fb7bab66ed62719b3fc6090120d2cfe1410583190cd650c32a4151550732b0fc97130e5f02aa26cb829600b6ab452b5b11373ec69d4eaae6c392d92da8bcbea85344af9d4699e36fdca075d33f58049fd0a9f6919f3003512a261a00985dc3d9843a822974df30b81732a91ce706c44bde5ff48491a45a5fa8d5d73bba5022af803ab7bd85250e71fc0254fcf078d21eaa5d38724014a85f679e8a7a1aad6ed22602465f90e6dd8ef95df287628832850af7e3628ad09ff90a6dbdf7a0e6d74f508d2a6235d4eae5a828ac95558bbdf72f39af5641dfe3edb0cdaab362805d926106e2af
e = 0x5af5dbe4af4005564908a094e0eabb0a921b7482483a753e2a4d560700cb2b2dc9399b608334e05140f54d90fcbef70cec097e3f75395d0c4799d9ec3e670aca41da0892a7b3d038acb7a518be1ced8d5224354ce39e465450c12be653639a8215afb1ba70b1f8f71fc1a0549853998e2337604fca7edac67dd1e7ddeb897308ebf26ade781710e6a2fe4c533a584566ea42068d0452c1b1ecef00a781b6d31fbab893de0c9e46fce69c71cefad3119e8ceebdab25726a96aaf02a7c4a6a38d2f75f413f89064fef14fbd5762599ca8eb3737122374c5e34a7422ea1b3d7c43a110d3209e1c5e23e4eece9e964da2c447c9e5e1c8a6038dc52d699f9324fd6b9
c = 0x731ceb0ac8f10c8ff82450b61b414c4f7265ccf9f73b8e238cc7265f83c635575a9381aa625044bde7b34ad7cce901fe7512c934b7f6729584d2a77c47e8422c8c0fe2d3dd12aceda8ef904ad5896b971f8b79048e3e2f99f600bf6bac6cad32f922899c00fdc2d21fcf3d0093216bfc5829f02c08ba5e534379cc9118c347763567251c0fe57c92efe0a96c8595bac2c759837211aac914ea3b62aae096ebb8cb384c481b086e660f0c6249c9574289fe91b683609154c066de7a94eafa749c9e92d83a9d473cc88accd9d4c5754ccdbc5aa77ba9a790bc512404a81fc566df42b652a55b9b8ffb189f734d1c007b6cbdb67e14399182016843e27e6d4e5fca
import owiener
from Crypto.Util.number import*
d = owiener.attack(e, N)
print(long_to_bytes(pow(c, d, N)))

idk_cipher

The encryption script encode.py uses a custom cipher to encrypt the flag. It splits xor’s first byte of key with both first and last byte of flag. Then, it xors the second byte of key with second and second last byte of flag and so on.

We even know what the key is so we can reverse the encryption

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

import base64

def decrypt(encoded_b64_str, srt_key='secretkey'):
    # Step 1: Base64 decode
    encoded_val = base64.b64decode(encoded_b64_str).decode()
    
    # Step 2: Initialize empty arrays for the decrypted input
    half_len = len(encoded_val) // 2
    dec_p1 = []
    dec_p2 = []

    # Step 3: XOR decryption (reverse of encryption)
    for i in range(half_len):
        # XOR the encrypted characters with the secret key to get the original characters
        c1 = chr(ord(encoded_val[i * 2]) ^ ord(srt_key[i % len(srt_key)]))
        c2 = chr(ord(encoded_val[i * 2 + 1]) ^ ord(srt_key[i % len(srt_key)]))
        dec_p1.append(c1)
        dec_p2.append(c2)
    
    # Step 4: Rebuild original input from the two halves
    original_input = ''.join(dec_p1) + ''.join(dec_p2[::-1])
    
    return original_input

# Example usage:
encoded_b64_str =  "QRVWUFdWEUpdXEVGCF8DVEoYEEIBBlEAE0dQAURFD1I="
decrypted_text = decrypt(encoded_b64_str)
print("Decrypted Text:", decrypted_text)

Hard_implement

It is byte-at-a-time ECB decryption according to this page. We can reduce by only testing on string.printable

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

from pwn import *
import string

host = 'chal.competitivecyber.club'
port = 6001

flag_charset = string.printable

flag = 'pctf{'
junk = 'A' * 16

def encrypt(io, data):
    io.sendlineafter(b'Send challenge > ', data.encode())
    io.recvuntil(b'Response > ')
    return io.recvline().strip()

io = remote(host, port)

p = log.progress('Flag: ')

while flag[-1] != '}':
    payload = junk[:-(len(flag)+1)]
    truth = encrypt(io, payload)[:32]
    for c in flag_charset:
        p.status(f'{flag}{c}')
        if truth == encrypt(io, payload + flag + c)[:32]:
            flag += c
            break

print(f"{flag = }")
io.close()

High-roller

The script used by adversary is BestEncrypt.py which uses pycryptodome library to generate RSA keypair.

BestEncrypt.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#! /usr/bin/python3.10
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
import time

random.seed(int(time.time()))
p, q = getPrime(512, random.randbytes), getPrime(512, random.randbytes)
n = p*q
e = getPrime(512)
phi = (p-1)*(q-1)

assert GCD(e, phi) == 1
d = pow(e, -1, phi)

key = RSA.construct((n, e, d, p, q))
with open("public_key.pem", "wb") as f:
    f.write(key.publickey().export_key("PEM"))

with open("private_key.pem", "wb") as f:
    f.write(key.export_key("PEM"))

The seed was used is int(time.time()) and converted into .pem file so we can use command to find time

1
2

stat -c '%n %y' public_key.pem
public_key.pem 2024-09-21 22:39:18.000000000 +0530 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
import time

pubkey = RSA.import_key(open("public_key.pem", "r").read())
c = bytes_to_long(open("flag.enc", "rb").read())
time_i = 1726938600

for i in range(time_i, 1, -1):
    print(time_i - i)
    random.seed(i)
    p, q = getPrime(512, random.randbytes), getPrime(512, random.randbytes)

    if p*q == pubkey.n:
        break

d = pow(pubkey.e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, pubkey.n)))

Bit-by-bit

transmit.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

#!/usr/bin/python3
import sys

blocksize = 16

def loadMessage():
    message = ""
    with open("message.txt","r",encoding='utf-8') as file:
        for line in file:
            message += line
    while len(message) % blocksize != 0:
        message += '0'
    return message

def encode(chunk):
    start = 120
    encoded = 0
    for c in chunk:
        encoded = encoded | (ord(c)<<start)
        start -= 8
    return encoded

def transmit():

    # Test key
    key = 0xadbeefdeadbeefdeadbeef00
    # print(key)
    iv = 0
    msg = loadMessage()
    chunks = [msg[i:i+16] for i in range(0,len(msg), 16)]

    send = ''
    for chunk in chunks:
        iv = (iv+1) % 255
        curr_k = key+iv
        encoded = encode(chunk)
        enc = encoded ^ curr_k
        foo = hex(enc)[2:]
        while len(foo) != 32:
           foo = '0'+foo
        send += foo
    print(send)
    sys.exit(0) 

if __name__=="__main__":
    transmit()

The encode fuction tranform a bytes object to a number like: ababab… -> 01100001.01100010

So the first time I think about xor between $enc$^$enc[256]$ because they will share the same keyxor which % 256 then I stuck :v. The solution is exploit key fixing and repeated so it is like this page

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

#!/usr/bin/env python3

from re import findall
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl
freq = {
    ord('a'): 0.08167, ord('A'): 0.08167,
    ord('b'): 0.01492, ord('B'): 0.01492,
    ord('c'): 0.02782, ord('C'): 0.02782,
    ord('d'): 0.04253, ord('D'): 0.04253,
    ord('e'): 0.12702, ord('E'): 0.12702,
    ord('f'): 0.02228, ord('F'): 0.02228,
    ord('g'): 0.02015, ord('G'): 0.02015,
    ord('h'): 0.06094, ord('H'): 0.06094,
    ord('i'): 0.06966, ord('I'): 0.06966,
    ord('j'): 0.00153, ord('J'): 0.00153,
    ord('k'): 0.00772, ord('K'): 0.00772,
    ord('l'): 0.04025, ord('L'): 0.04025,
    ord('m'): 0.02406, ord('M'): 0.02406,
    ord('n'): 0.06749, ord('N'): 0.06749,
    ord('o'): 0.07507, ord('O'): 0.07507,
    ord('p'): 0.01929, ord('P'): 0.01929,
    ord('q'): 0.00095, ord('Q'): 0.00095,
    ord('r'): 0.05987, ord('R'): 0.05987,
    ord('s'): 0.06327, ord('S'): 0.06327,
    ord('t'): 0.09056, ord('T'): 0.09056,
    ord('u'): 0.02758, ord('U'): 0.02758,
    ord('v'): 0.00978, ord('V'): 0.00978,
    ord('w'): 0.02360, ord('W'): 0.02360,
    ord('x'): 0.00150, ord('X'): 0.00150,
    ord('y'): 0.01974, ord('Y'): 0.01974,
    ord('z'): 0.00074, ord('Z'): 0.00074,
    ord(' '): 0.13000
}

with open("out.txt", "r") as f:
    ciphertext = bytes.fromhex(f.read())

chunks = [ciphertext[i:i+16] for i in range(0, len(ciphertext), 16)]
print(len(chunks)%16)
key = bytearray(16)

for i in range(0, 16):
    best_b = 0
    high_score = -1.0
    for j in range(256):
        key[i] = j
        score = 0.0
        for chunk in chunks:
            c = btl(chunk)
            k = btl(key)
            b = ltb(c ^ k)[i]
            try:
                score += freq[b]
            except:
                pass
        if score > high_score:
            best_b = j
            high_score = score
    key[i] = best_b

plaintext = b""
for i in range(len(chunks)):
    c = btl(chunks[i])
    k = (btl(key) + i + 1)
    plaintext += ltb(c ^ k)

plaintext = plaintext.decode("utf-8", "ignore")
print(plaintext)
# pctZ{4_th3_tw0_t1m3c4a324510356} <- the flag

Textbook Schnorr right??

The server gave me a Schnorr_signature

1
2
3
4
5
6
7

    def verify(self, message, signature):
        s, R = signature
        R_int = int(R.xy()[0] + R.xy()[1])
        h = self.compute_hash(R_int | message)
        left_side = s * self.generator
        right_side = R + h * self.public_key
        return left_side == right_side

But the difference is function compute_hash \(h = hash(R|m)\)

This gave us a potential way of bruteforcing to find $s$ and $R$ in which \((R | message) == target\)

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

separator = "FF"
payload = "7F7F7F"
io.sendlineafter(b"Enter separator as a hex value (2 digits): ", separator.encode().strip())
io.sendlineafter("Enter 3-letter word 1 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 2 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 3 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 4 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 5 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 6 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 7 as a hex value (6 digits): ",payload.encode().strip())
io.sendlineafter("Enter 3-letter word 8 as a hex value (6 digits): ",payload.encode().strip())

TARGET = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
MESSAGE_OR_MASK = int("7F7F7FFF" * 8, 16)

def compute_hash(target):
    hash_int = int(hashlib.sha256(str(target).encode()).hexdigest(), 16)
    return hash_int % n

def verify_sig(s, R_test):
    R_test_str = str(R_test).strip("()")
    R_test_parts = [part.strip() for part in R_test_str.split(":")]
    xR = R_test_parts[0]
    yR = R_test_parts[1]
    sendxR = hex(xR)[2:]
    sendyR = hex(yR)[2:]
    send_s = hex(s)[2:]
    print(f"{sendxR = }")
    print(f"{sendyR = }")
    print(f"{send_s = }")

    io.sendlineafter(b"Enter the x-coordinate of signature R (in hex):", sendxR)
    io.sendlineafter(b"Enter the y-coordinate of signature R (in hex):", sendyR)
    io.sendlineafter(b"EEnter signature s (in hex): ", send_s)
    io.interactive()

from tqdm import*
def bruforce_signature(P, G):
    print("Brute-forcing to find a valid signature...")
    h = compute_hash(TARGET)
    hP = h*P
    s = secrets.randbelow(n)
    sG = s*G
    with tqdm(total=0, unit=' iterations', unit_scale=True) as pbar:

        while True:
            R_test = sG - hP
            R_test_binary = int(R_test.xy()[0] + R_test.xy()[1])
            if (R_test_binary | MESSAGE_OR_MASK) == TARGET:
                assert s*G - h*P == R_test
                print("found")
                verify_sig(s, R_test)
                break
            s = (s*2) %n
            sG = 2*sG
            pbar.update(int(1))
bruforce_signature(P, G)
CTF-Writeups
cryptography rsa aes
This post is licensed under CC BY 4.0 by the author.