LACTF24 Writeups

20 February 2024 - 5 mins read time
Tags: ctf crypto rev

Here are my writeups for a few of the challenges I solved for LACTF with the OSIRIS Lab. Thank you to UCLA’s ACM Cyber for hosting, and well done on the challenges :)

very-hot

for very-hot, you’re given two files: the flag encryption python script and a .txt file with $n, e,$ and $ct$ given.

The description reads: “I didn’t think that using two primes for my RSA was sexy enough, so I used three.” Sounds like fun.

RSA

In normal RSA, you’re given two large primes $p,q$ where $n=pq, p,q$ must stay hidden. We take:

3-RSA???

In 3-RSA, you’re given 3 large primes $p,q,r$ where $n=pqr, p,q,r$ must stay hidden. Here, $q = p+6, r=p+12$ We take:

Vulnerability

Theres a huge vulnerability with this. We can actually solve for $p$, given that $n$ is part of the private key and we can write $q,r$ in terms of $p$:

$n = p(p+6)(p+12)= p^3+18p^2+72p, 0 = p^3+18p^2+72p-n$

$n =$

10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799

solve for $p$, we get $p=$

21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077

Then its just working backwards with RSA:

from sympy import mod_inverse

# Assign the real solution for p
p_val = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077

# Calculate q and r
q_val = p_val + 6
r_val = p_val + 12

# Calculate phi(n)
phi_n = (p_val - 1) * (q_val - 1) * (r_val - 1)

# Given e
e = 65537

# Calculate d
d = mod_inverse(e, phi_n)

# Given ct
ct = 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985

# Decrypt ct
flag = pow(ct, d, p_val * q_val * r_val)

# Convert the flag from long to bytes
flag_bytes = flag.to_bytes((flag.bit_length() + 7) // 8, 'big')

print(flag_bytes)

And we get our flag:

lactf{th4t_w45_n0t_so_53xY}

valentines-day

For valentines-day, you’re given two .txt files: one containing the entire encrypted text, and one that contains the first sentence of plaintext. The description mentions that the problem involves a Vigenere Cipher, with a key of 161 characters.

The plaintext reads: “On this Valentine’s day, I wanted to show my love for professor Paul Eggert. This challenge is dedicated to him. Enjoy the challenge!”

Vigenere Cipher

In a Vigenere Cipher, each letter of plaintext is encoded with its own Caesar Cipher. The increment of each characters cipher is determined by the corresponding letter in the key. For example:

Given a plaintext: ‘abc’, and a key: ‘rax’, our ciphertext will be: ‘rbz’.

Here, the individual Caesar shifts are: 18, 1, 24.

Solution

We’ll work backwards with the plaintext and $ct$ to find the first part of key and see if there’s a pattern:

# Given the encrypted and decrypted text, we can determine the Vigenère cipher's key for the first line.

encrypted_text = "Br olzy Jnyetbdrc'g xun, V avrkkr gb sssp km frja sbv kvflsffoi Jnuc Sathrg."
decrypted_text = "On this Valentine's day, I wanted to show my love for professor Paul Eggert."

# Function to find the key used in Vigenère cipher for the given encrypted and decrypted text
def find_vigenere_key(encrypted, decrypted):
    key = ''
    for e, d in zip(encrypted, decrypted):
        # Calculate the key character
        if e.isspace()!= True:
          key_char_shift = (ord(e) - ord(d)) % 26
          key_char = chr(ord('A') + key_char_shift)
          key += key_char
    return key

# Find the key for the first line
first_line_key = find_vigenere_key(encrypted_text, decrypted_text)
print(first_line_key)

And we get…….. NEVERGONNAGIVEYOUUPNEVERGONNALETYOUDOWNNEVERGONNARUNAROUNDAN

Getting rickrolled in CTF…

Anyways, we know the key is 161 characters long, so we look up the lyrics and get the first 161 characters from that point in the song:

Key:NEVERGONNAGIVEYOUUPNEVERGONNALETYOUDOWNNEVERGONNARUNAROUNDANDDESERTYOUNEVERGONNAMAKEYOUCRYNEVERGONNASAYGOODBYENEVERGONNATELLALIEANDHURTYOUWEVEKNOWNEACHOTHERFORSO

And to save us some time we use this lovely Vigenere solver tool to get our flag: lactf{known_plaintext_and_were_off_to_the_races}

shattered-memories

In this challenge, we’re given a binary shattered-memories. Running ./shattered-memories prompts: “What was the flag again?” and based on the input given it gives some replies based on input size etc…

The assumed solution would be to slowly piece it together or run some solve script that brute forces it based on the hints it gives, right?

I decided to ignore all that, open up the binary in Binary Ninja and have a look.

Presenting itself almost immediately in main() is our flag, split up into bits. Put it all together and we get:

lactf{not_what_forgive_and_forget_means}