Day 12 - Leveling Up with picoCTF's Medium Crypto Challenges

After warming up with the easy challenges, today I felt ready to raise the difficulty. I dove into the "Medium" category for cryptography on picoCTF. These problems required a bit more thought and combined multiple concepts, which was a great way to test my understanding.

Here’s a breakdown of the challenges I tackled!

1. credstuff

"credstuff" description

This challenge simulated a real-world scenario: a credential leak from a black market website. I was given two files, usernames.txt and passwords.txt, and my goal was to find the password for the user "cultiris". The description noted that the Nth user in the username file corresponds to the Nth password.

My Solution:

This was a two-step process involving some command-line magic and a familiar cipher.

  1. Find the Password: First, I needed to find which line the user cultiris was on. The grep command was perfect for this. It told me the user was on line 378. 
    josh@DESKTOP-E7VKRGO:~/credstuff/leak/leak$ grep -n cultiris usernames.txt
378:cultiris
    Then, I used the sed command to print only the 378th line from the passwords.txt file, which gave me the encrypted password. 
    josh@DESKTOP-E7VKRGO:~/credstuff/leak/leak$ sed -n '378p' passwords.txt
cvpbPGS{P7e1s_54I35_71Z3}
  2. Decrypt the Password: The password cvpbPGS{...} had the classic format of a ROT13 cipher. I used my ROT13 script from a previous challenge to decrypt it.

Flag: picoCTF{C7r1F_54V35_71M3}

2. basic-mod1

"basic-mod1" description

This challenge was a fun exercise in modular arithmetic and character mapping. I was given a list of numbers and a specific decryption scheme.

The Task:

For each number in the message, I had to calculate the value modulo 37. Then, I needed to map the result to a specific character set: 0-25 for uppercase letters (A-Z), 26-35 for digits (0-9), and 36 for an underscore.

My Solution:

I wrote a Python script to automate this process. It loops through the numbers, applies the mod 37 operation, and uses if/elif/else statements to map the result to the correct character before joining them all into the final flag.

# The decryption function for basic-mod1
def decrypt(ct):
    arr=[]
    angka_int=[int(a) for a in ct.split()]
    for i in angka_int:
        fi=i%37
        if 0<=fi<=25:
            arr.append(chr(fi+65))
        elif 26<=fi<=35:
            arr.append(str(fi-26))
        else:
            arr.append('_')
    return "picoCTF{" + ''.join(arr) + "}"

Flag: picoCTF{ROUND_N_ROUND_79C18FB3}

3. basic-mod2


"basic-mod2" description

This challenge built directly on the previous one, adding another mathematical step: the modular inverse.

The Task:

This time, I had to take each number modulo 41 and then find the modular inverse of that result. The final value was then mapped to a character set (1-26 for A-Z, 27-36 for 0-9, and 37 for an underscore).

My Solution:

My Python script for this was similar, but included a crucial new step. For each number, after applying mod 41, I used Python's powerful pow(number, -1, 41) function to efficiently calculate the modular multiplicative inverse.

# The core logic for basic-mod2
def decrypt(ct):
    arr=[]
    angka_int=[int(a) for a in ct.split()]
    for i in angka_int:
        fi = i%41
        try:
            # Calculate the modular inverse
            inv=pow(fi, -1, 41)
            if 1<=inv<=26:
                arr.append(chr(ord('A')+inv-1))
            elif 27<=inv<=36:
                arr.append(str(inv-27))
            else:
                arr.append('_')
        except ValueError:
            # Handle cases where inverse doesn't exist
            arr.append('?') 
            continue
    return "picoCTF{" + ''.join(arr) + "}"

Flag: picoCTF{1NV3R53LY_H4RD_8A05D939}

4. Mind your Ps and Qs

"Mind your Ps and Qs" description

This was an interesting RSA challenge. The security of RSA depends on the difficulty of factoring the modulus N. The challenge's name hinted that something was special about the prime factors p and q.

The Vulnerability:

It turns out that N was a number whose factors were already known and stored in public databases. I used an online database (factordb.com) via a Python library to instantly find p and q.

My Solution:

Once I had p and q, breaking the rest of the RSA encryption was straightforward. My script automated the following steps:

  1. Factor N: Use the factordb-py library to fetch p and q from factordb.com.
  2. Calculate φ and d: Compute phi = (p-1)*(q-1) and then the private key d = pow(e, -1, phi).
  3. Decrypt: Compute the plaintext by calculating pow(c, d, n) and converting the resulting integer to a readable string.

This challenge was a great lesson in how real-world tools and databases can be used to break implementations that might seem theoretically secure.

Flag: picoCTF{SmAll_N_g00d_45369387}

5. Mini RSA

"Mini RSA" description

My final challenge for the day was another RSA problem, this time focusing on a small public exponent (e).

The Vulnerability:

When e is small (like e=3), if the plaintext message M is also small, M**e might be smaller than the modulus N. In this case, an attacker can simply calculate the integer e-th root of the ciphertext to recover M. This challenge was slightly trickier because padding ensured M**e was just barely larger than N. This means M**e = k*N + C for some small integer k. The attack is to try small values of k (0, 1, 2, ...) and check if (k*N + C) is a perfect e-th root.

My Solution:

I wrote a script that iterated through values of k, calculated candidate = k*N + c, and used the gmpy2.iroot() function to check if the result was a perfect root. On iteration k = 3533, it found the plaintext!

# Core logic of the Mini RSA attack
# (Assuming c, n, e are already defined)
import gmpy2

for i in range(10000):
    candidate = i * n + c
    is_true_root, m = gmpy2.iroot(candidate, e)
    if is_true_root:
        print(f"Found i = {i}")
        # ... code to convert m to string and print flag ...
        break

This was a classic example of an attack on a "textbook" RSA implementation with a small e.

Flag: picoCTF{e_is_n0t_en0ugh_t0_br34k_RSA_638ce719}

It was really satisfying to see the crypto concepts I've been reading about come together in practical scripts to break these challenges. What a fantastic day of learning at picoCTF!

#IDNBootCampCyber

Komentar

Posting Komentar

Postingan Populer