redpwnCTF 2021 - crypto challenges

crypto

brief and rushed writeups to all the crypto challenges from redpwnctf 2021

scissor

import random

key = random.randint(0, 25)
alphabet = 'abcdefghijklmnopqrstuvwxyz'
shifted = alphabet[key:] + alphabet[:key]
dictionary = dict(zip(alphabet, shifted))

print(''.join([
    dictionary[c]
    if c in dictionary
    else c
    for c in input()
]))

# output: egddagzp_ftue_rxms_iuft_rxms_radymf

the script implements a cipher (which is caesar cipher).

the keyspace is incredibly small, so we can just bruteforce the key, either using the provided script, or just using something else like cyberchef's rot13 decryptor and trying all possible keys. we can see one of these gives us a clearly readable flag.

flag: flag{surround_this_flag_with_flag_format}

warmup

n: 228430203128652625114739053365339856393
e: 65537
c: 126721104148692049427127809839057445790

we get what appears to be a set of rsa parameters, along with a ciphertext that we presumably have to decrypt.

the modulus n in this case is very small, and can be easily factored using something like alpertron. we then retrieve the prime factors, calculate the private key, and decrypt the message.

from Crypto.Util.number import long_to_bytes

n = 228430203128652625114739053365339856393
e = 65537
c = 126721104148692049427127809839057445790
p = 12546190522253739887
q = 18207136478875858439
d = pow(e, -1, (p-1) * (q-1))
pt = pow(c, d, n)
print(long_to_bytes(pt))

flag: flag{68ab82df34}

round-the-bases

we get given a file with what looks like random data. judging from the title, we can guess that it is probably a base challenge. cyberchef is once again a great tool for this, allowing us to quickly try different combinations of bases together and seeing their result. other than that, there isn't really much to this challenge, just keep trying combinations of bases, judging based on the number of unique characters in their output.

flag: flag{w0w_th4t_w4s_4ll_wr4pp3d_up}

blecc

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.

we get given a file that seems to be parameters for an ecdh exchange. our goal is to work out the private key d given curve parameters, as well as a generator point G and curve point Q, where Q = G * d. this requires solving the discrete log problem.

sage is a very useful tool for this, as it supports elliptic curves, and we just have to provide parameters.

p = 17459102747413984477
a = 2
b = 3
E = EllipticCurve(GF(p), [a,b])
G = E(15579091807671783999, 4313814846862507155)
Q = E(8859996588597792495, 2628834476186361781)

if we print the order of the generator G using G.order(), we see that it is 17459102747134002790. this number is quite smooth, having many small factors, and when the order of the generator is smooth, the discrete log problem becomes easy to solve. sage can again, conveniently, do most of the work for us.

p = 17459102747413984477
a = 2
b = 3
E = EllipticCurve(GF(p), [a,b])
G = E(15579091807671783999, 4313814846862507155)
Q = E(8859996588597792495, 2628834476186361781)
print(G.discrete_log(Q))

giving us the result: 7868191182322623331. converting this into a byte string gives us the flag.

flag: flag{m1n1_3cc}

yahtzee

#!/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)

we get access to a server that gives us encryptions of random quotes with the flag stuck in the middle somewhere using AES-CTR mode.

there are two main vulnerabilities here.

firstly, the cipher gets reset each time, leaving the implementation open to things like nonce reuse attacks, as the keystream will be the same if this is the case

secondly, the random number generator used is very insecure, as there are only 11 possible outputs. since this is used to generate nonces for the AES-CTR mode, we can perform the nonce reuse attack mentioned above.

if we get many ciphertexts from the server, and then see which ones appear to have reused nonces as well as the same plaintext (by looking at the similarity in them), then we can identify where the flag was placed in each of the ciphertexts and crib drag with known flag format.

i have grabbed some ciphertexts which appear to share a nonce and plaintext, apart from the flag position being changed.

341f317e1dccabae6f2636d571a5c3e24dd358fb0c30989c7c536c857b0c08e29443ced90e02b9d38cb0d22ebb72e8a0abcd1aeab495d149a33d67759a23dd0f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dccabae6f2636d571a5c3e24dd358fb0c30989c7c546c937d0e4baaad789b8f016da5e4bef6d029bb68cf9aea901dc7eaaaf707ed2879328b23d30f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dccabae6f2636d571b4caa347c903f6730ed881286d749a7f0748b1ad41e0e1465ca5feebf49a27c471e5e5b49f02d0fab3fa56ed2879328b23d30f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dc3b4ef7f3567c90e8592f354ed47f6492bdfc3035c4fad291b0fb0c25fd6c3555ba2acacec822ec471e5e5b49f02d0fab3fa56ed2879328b23d30f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dccabae6f2636d571a5c3e24dd358fb0c30989c7c536c857b0c08e29a4edc9e1757b4e2f7a482369367f9b6f99805d4bda1be12921e21749e05d44729ea5392575f58c146183da47498a19783124a0dfe7e4af9e0

comparing all of the ciphertexts against each other, we can guess at what point the flag starts at, as it will be different to all the other ciphertexts. in this way, we can recover a partial keystream, and then we can guess the rest to hopefully get the flag. we can again use cyberchef for this. basically, take where the ciphertext differs from the rest, xor that with flag{ as our known plaintext, and place the result into the keystream at the appropriate place

we recover the following keystream: 0000000000a5d88e184e000000d2a6c220b2000000000000003200f21a750000f22fafbe

xoring that with each of the plaintexts, we can recover slight chunks of the flag.

- 2nd ct: _W41t at index 3
- 3rd ct: _ther at index 8, _nO_3 at index 15
- 4th ct nO_3n at index 16, 0py} at index 23

our partial flag is then: flag{??_W41t_ther??_nO_3n??0py}

then, we can repeat the process above which we used to recover the partial keystream again, knowing more details of the flag.

flag: flag{0h_W41t_ther3s_nO_3ntr0py}

scrambled-elgs

#!/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)

for this challenge, we get a secret message m, which is then encrypted using the elgamal cryptosystem in a symmetric group.

the private key k is very small, and can be bruteforced.

import json
import sage.combinat.permutation as permutation

n = 25_000
Sn = SymmetricGroup(n)

a = json.loads(open("output.json").read())
g = Sn(a["g"])
h = Sn(a["h"])
t1 = Sn(a["t1"])
t2 = Sn(a["t2"])


for i in range(25000):
    if g^i == t1:
        print(i)

after this, we can recover m by dividing t2 by h^k

k = 3245
assert g^k == t1
i = h^k
t3 = t2/i
m = Sn(t3)

and then recover the original M by getting the rank of m

M = permutation.from_permutation_group_element(m)
print(hex(M.rank()))

flag: flag{1_w1ll_n0t_34t_th3m_s4m_1_4m}

Keeper of the Flag

#!/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")

in this challenge we get to sign 2 messages using DSA. our goal is to then generate a valud signature for the message give flag

the vulnerability here is the nonce generation. we see the nonces are generated by a function:

def H(s):
    x = bytes_to_long(sha1(s).digest())
    return pow(x, rot, chop)
    
#...    
    
k = (H(m) + pad + i) % q

pad, rot and chop are all hidden, however we do get the value of $H(m)$. notice that since pad remains constant, we can form a relation between two nonces.

initially, we got the difference of the two nonces to be 1 by using the two sha1 colliding pdfs from here, meaning that $H(m)$ will be the same, and the $i$ will be the only difference. then, we can just perform the related nonce attack, first recovering the nonce and then the private key.

k = (h2 - s2 - h1 * r2 / r1) / (s2 - s1 * r2 / r1)
x = (s1 * k) / r1 - (h1 / r1)

flag: flag{here_it_is_a8036d2f57ec7cecf8acc2fe6d330a71}

quaternion-revenge

#!/usr/bin/env sage
from Crypto.Util.number import getPrime, bytes_to_long
import secrets

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

with open('secret.txt','rb') as secret:
    M = secret.read().strip()
m = bytes_to_long(M)

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
Q.<i,j,k> = QuaternionAlgebra(-p,-q)

#randomize M per-instance
m ^^= secrets.randbelow(n)

#prepare leaks
n  = n
l  = m.bit_length()
c1 = pow(m,e,p)
c2 = pow(m,e,q)

#reveal leaks
print('n:',n)
print('l:',l)
print('c1:',c1)
print('c2:',c2)

#Present challenge
try:
    print("Calculate the left quaternion isomorphism of m:")
    inp = input('>>> ').strip()
    assert all([x in '1234567890 ijk*+' for x in inp])
    if eval(inp)==m:
        print(flag)
    else:
        print('Wrong!')
except AssertionError:
    print("Invalid characters.")
except Exception:
    print("Error.")

in this challenge we have to - wait hang on, just got a message that this was a troll challenge and you can just send i to get the flag.

huh.

flag: flag{00p5_1_l13d_r0fl}

retrosign

#!/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.")

in this challenge, we are given an implementation of some signature scheme, whose hardness depends on the problem of integer factorization. our goal is to find a pair of numbers, a and b, and given parameters k and n that satisfy the equation $a^{2} + k*b^{2} \equiv H(m) \mod n$

this isn't feasible due to taking square roots being mod n very difficult without knowing the factorization of n.

after doing a bit of research, i found the scheme implemented: it's the ong-schnorr-shamir signature scheme. conveniently, we also found a paper that breaks this scheme, so it's implementing time... or maybe not

after doing a bit more osint, we found another ctf challenge that has used this signature scheme before, and a writeup for the challenge here. conveniently, it has an implementation of the paper for us!

so, we steal their implementation and get the flag.

flag: flag{w0w_th4t_s1gn4tur3_w4s_pr3tty_r3tr0}

osint is just that op