Day 13 - Confronting Hard Crypto Challanges in PicoCTF
Day 13: Leveling Up to Hard Crypto Challenges in picoCTF
After finishing the easy and medium crypto challenges on picoCTF, I felt it was time to really test my limits. Today, I decided to focus exclusively on the "Hard" category. My goal for the day is to solve five of them. These problems require a deeper understanding of cryptographic principles and specific attack vectors. It's an intense session, but incredibly rewarding. Here's how the first two challenges went!
Hard Challenge 1: Sum-O-Primes
The description for this challenge was intriguing: "We have so much faith in RSA we give you not just the product of the primes, but their sum as well!" This immediately told me that having the sum of the primes p and q, in addition to their product n, is a critical vulnerability.
The Vulnerability: The Math
Standard RSA security relies on the fact that factoring n = p * q is extremely difficult. However, this challenge gives us two key pieces of information:
n = p * qx = p + q
With this system of two equations, we can solve for p and q algebraically, completely bypassing the need for difficult factorization. Here's how:
From the second equation, we can say q = x - p. Substituting this into the first equation gives us:
n = p * (x - p)
Rearranging this, we get a quadratic equation: p² - x*p + n = 0.
I can solve this for p using the quadratic formula, which simplifies to finding the square root of the discriminant (x² - 4n). Once I have that value (let's call it delta), the primes are simply:
p = (x - delta) / 2
q = (x + delta) / 2
With p and q found, the RSA encryption is broken.
My Solution:
I translated this mathematical approach into a Python script. The script takes the large hexadecimal values for n, x, and the ciphertext c, and performs the decryption.
import math
from binascii import unhexlify
from gmpy2 import isqrt, lcm
# Values from output.txt
x = 0x1429cf99b5dd5dde9f016095be650d5b0a9a73e648aa72324cb8eb05bd14c1b913539a97f5417474f6014de830ad6dee028dd8908e593b1e99c4cc88f400127214036e71112292e58a2ccffc48f57524aee90f9858d935c7a86297a90c7fe48b80f6c4e8df9eaae501ef40da7984502457255fbc8a9e1574ec6ba210be134f192
n = 0x64fc90f5ca6db24f7bfc6419de407596d29a9ecda526101b8d0eff2181e9b8ed1538a1cbabe4dfc5bcd899976e7739f8b448815b50db36a994c5b1df97981d562c663113fc5ee84f3206aecd18248fb4e9bddf205c8119e8437f7d6522e63d05bc357ae4969a4b3000b8226f8d142c23c4e38cdb0c385bf9564e8a115e4c52b7a2e3a9073a5d99d7bec3bca6452cf0c1b8d8b6b123cc6a6980cf14088d6a2bbb5ed36b85cb0003e535bd16d79ad54ff5b26e62f57de074654493d3a26a149786d5fbf61b42c9305092eb018aa3db3cb18b24f188ae520bd18acf9ffced09a2ba302a520f6e2bfd8eea9adc01eb8ee941181694a3ab493e1aa53fbbbf2851a591
c = 0x56ed81bbc149701110f0a15e2e6078ab926d74ee2c11b804ae4fad4333a25c247f38bb74867922438d10ce529b75f5ee5e29ce71d6f704cc0644f7e78d60a2af8921fbc49326280e3f0c00f2769e837363cbb05dc3f30bda8fdc94111fb025008eae562ae57029d5cfde6bdd09893a738187578d22f82a5f8769f093681662329f05b262c2054f91696a24f631ba8132f3d92ae7758c91fa9b5657e4944c5d5f93afb4af68908d004ae5f97071bcaceb7d0034297eeb897f972b44b0d7def52f46ee45d386a5e24ed613bf7e5177c6e10f69a3d3de0f0c30de0b15d360ee81da3d277a4acf47b6df389c24615884b692e604eba711fc28c34bc56227b8455705
e = 65537
# 1. Recover p and q
delta = isqrt(x*x - 4*n)
p = (x - delta) // 2
q = (x + delta) // 2
assert p * q == n
# 2. Calculate d using Carmichael's function λ(n)
m = lcm(p - 1, q - 1)
d = pow(e, -1, m)
# 3. Decrypt the ciphertext
decrypted_flag_int = pow(c, d, n)
# 4. Decode the flag
flag_hex = hex(decrypted_flag_int)[2:]
flag = unhexlify(flag_hex)
print(flag.decode())
Running this script gave the final flag instantly. A "Hard" problem became easy with the right mathematical insight!
Flag: picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_24929c45}
Hard Challenge 2: b00tl3gRSA2
The second hard challenge was another RSA problem. The description asks, "In RSA d is a lot bigger than e, why don't we use d to encrypt instead of e?" This turned out to be a misdirection. The real vulnerability here is a classic cryptographic attack on RSA when the private key d is too small.
The Vulnerability: Wiener's Attack
This challenge is a perfect candidate for Wiener's Attack. This powerful attack works if the private exponent d is small relative to the modulus N (specifically, if d < (1/3) * N^(1/4)). The attack uses the properties of continued fractions to efficiently recover d from the public values e and N. By calculating the continued fraction expansion of e/N, we can find a set of rational approximations, one of which will reveal the private key d.
My Solution:
I wrote a Python script to connect to the server and implement Wiener's Attack. The script automatically fetches the values, runs the attack to find d, and then decrypts the ciphertext.
from pwn import *
from Crypto.Util.number import long_to_bytes
from math import isqrt
# ... (Functions for continued_fraction and convergents) ...
def wiener_attack(e, n):
log.info("Attempting Wiener's Attack...")
cf = list(continued_fraction(e, n))
for k, d in convergents(cf):
if k == 0 or (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if discr >= 0:
t = isqrt(discr)
if t * t == discr:
log.success(f"Private exponent d found: {d}")
return d
log.error("Wiener's attack failed.")
return None
def solve_rsa(c, n, e):
d = wiener_attack(e, n)
if d is None:
return None
m = pow(c, d, n)
return long_to_bytes(m)
# ... (main connection logic) ...
The script worked perfectly, finding the private key `d = 65537` and decrypting the message.
Flag: picoCTF{bad_1d3a5_2438125}
Hard Challenge 3: college-rowing-team
This challenge was a fantastic real-world example of an attack on textbook RSA implementations. We were given a list of messages encrypted with RSA, but with a twist: each encryption used a new modulus `N`, but always with the same small public exponent, `e = 3`.
The Vulnerability: Hastad's Broadcast Attack
This scenario is vulnerable to **Hastad's Broadcast Attack**. The core idea is that if you send the same message m to multiple people (or in this case, encrypt it multiple times) using RSA with the same small exponent e but different moduli (N1, N2, N3, ...), an eavesdropper can recover the original message m without factoring any of the moduli.
If we can find at least e (in this case, 3) ciphertexts that correspond to the same original message, we get a system of congruences:
m³ ≡ c (mod N1)m³ ≡ c (mod N2)m³ ≡ c (mod N3)
Using the **Chinese Remainder Theorem (CRT)**, we can solve this system to find a unique value X such that X ≡ m³ (mod N1*N2*N3). Because the message m is not padded and is much smaller than the moduli, it's almost certain that m³ will be smaller than the product N1*N2*N3. This means X is not just congruent to m³—it's *equal* to it. The final step is to simply calculate the integer cube root of X to find m.
My Solution:
I wrote a Python script to automate this entire process:
- Parse Data: Read the `encrypted-messages.txt` file and parse all the `n` and `c` values.
- Group by Ciphertext: Group all the different `n` values by their common ciphertext `c`. This is how I find the messages that were encrypted multiple times.
- Apply CRT and Decrypt: For each group that has 3 or more entries, apply the Chinese Remainder Theorem to the congruences. Then, calculate the integer cube root of the result from the CRT to recover the original message as a large integer.
- Decode: Convert the final integer back to a readable string to see all the decrypted messages and find the flag.
import sys
from binascii import unhexlify
# Helper functions for math operations
def iterative_egcd(a, b):
# ... implementation for Extended Euclidean Algorithm ...
x, prev_x = 0, 1; y, prev_y = 1, 0
while b != 0:
q = a // b
a, b = b, a % b
x, prev_x = prev_x - q * x, x
y, prev_y = prev_y - q * y, y
return a, prev_x, prev_y
def modinv(a, m):
g, x, y = iterative_egcd(a, m)
if g != 1: raise Exception('modular inverse does not exist')
return x % m
def chinese_remainder_theorem(items):
N = 1
for n, _ in items: N *= n
result = 0
for n_i, a_i in items:
p = N // n_i
result += a_i * modinv(p, n_i) * p
return result % N
def integer_cbrt(n):
# ... implementation for integer cube root ...
y = 1 << ((n.bit_length() + 2) // 3)
while True:
x = y
y = (2 * x + n // (x * x)) // 3
if x == y: break
return x
def long_to_bytes(n):
length = (n.bit_length() + 7) // 8
return n.to_bytes(length, 'big')
# --- Main Logic ---
# 1. Read and parse the file
with open('encrypted-messages.txt', 'r') as f: content = f.read()
entries = content.strip().split('\n\n')
# ... parsing logic ...
# 2. Group moduli by common ciphertext
grouped_by_c = {}
# ... grouping logic ...
# 3. Decrypt each group
for c, ns in grouped_by_c.items():
if len(ns) >= 3:
n1, n2, n3 = ns[0], ns[1], ns[2]
congruences = [(n1, c), (n2, c), (n3, c)]
m_cubed = chinese_remainder_theorem(congruences)
m = integer_cbrt(m_cubed)
decrypted_message = long_to_bytes(m)
# Filter for printable text
if all(32 <= char < 127 for char in decrypted_message) and decrypted_message:
print(f"✅ Decrypted: {decrypted_message.decode('utf-8')}")
Running the script successfully decrypted all the original messages, including the flag!
Flag: picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}
And with that, I've completed my goal for Day 13: solving three 'Hard' picoCTF crypto challenges! The jump in difficulty was real, pushing me to understand not just how ciphers work, but the specific mathematical conditions under which they fail. From algebraic shortcuts to famous exploits like Wiener's Attack and Hastad's Broadcast Attack, today was a deep dive into practical cryptanalysis. It really drives home the point that a secure algorithm is only one part of a secure system. I'm exhausted but thrilled with what I accomplished today.
#IDNBootCampCyber
Komentar
Posting Komentar