2025-10-17
📦 vx-underground
Notion | Where teams and agents work together
A collaborative AI workspace, built on your company context. Build and orchestrate agents right alongside your team
Challenge Solution Summary
https://www.lost-cluster.org/shattered_secrets/
Shamir's Secret Sharing Scheme (SSSS) - a cryptographic method to split a secret across multiple shares
Each cat image contained one share: position number (x-coordinate) and SHA-256 hash (y-coordinate)
Prime modulus: 0x010000000000000000000000000000000000000000000000000000000000000129
Solution Steps
Extract EXIF data from all images to get position-hash pairs
Apply Lagrange interpolation with the prime modulus to recover the secret
Recovered secret (in hex): 2a5a49502070617373776f72643a20464170656b4a21794a363959616a5773
Decoded to text: *ZIP password: FApekJ!yJ69YajWs
Extracted password: FApekJ!yJ69YajWs
Unzipped flag.zip successfully
The Flag
File contained Meow-encoded data (esoteric programming language)
flag{...} hidden in the Meow syntaxssss_recovery.py
#!/usr/bin/env python3
"""
Recover the secret using Shamir's Secret Sharing Scheme
"""
import csv
import subprocess
# Prime from prime_mod.jpg
PRIME = 0x010000000000000000000000000000000000000000000000000000000000000129
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def mod_inverse(a, m):
gcd, x, _ = extended_gcd(a % m, m)
if gcd != 1:
raise Exception('Modular inverse does not exist')
return (x % m + m) % m
def recover_secret(shares, prime):
"""
Recover secret using Lagrange interpolation
shares: dict of {x: y} where x is position, y is the share value
"""
secret = 0
for i, (x_i, y_i) in enumerate(shares.items()):
numerator = 1
denominator = 1
for j, (x_j, y_j) in enumerate(shares.items()):
if i != j:
numerator = (numerator * (-x_j)) % prime
denominator = (denominator * (x_i - x_j)) % prime
# Calculate Lagrange basis polynomial
lagrange = (numerator * mod_inverse(denominator, prime)) % prime
secret = (secret + y_i * lagrange) % prime
return secret
# Load all shares
shares = {}
with open('fixed_list.csv') as f:
for row in csv.reader(f):
if len(row) >= 2:
x = int(row[0])
y_hex = row[1]
y = int(y_hex, 16)
shares[x] = y
print("="*60)
print("Shamir's Secret Sharing Recovery")
print("="*60)
print(f"Prime: {hex(PRIME)}")
print(f"Total shares: {len(shares)}")
# Try with all shares
print("\nRecovering secret with all shares...")
secret = recover_secret(shares, PRIME)
secret_hex = hex(secret)[2:]
if len(secret_hex) % 2:
secret_hex = '0' + secret_hex
print(f"Recovered secret (hex): {secret_hex}")
# Convert to bytes and try as password
try:
secret_bytes = bytes.fromhex(secret_hex)
password = secret_bytes.decode('utf-8', errors='ignore')
print(f"As UTF-8: {password}")
except:
password = secret_hex
print(f"Using hex as password")
# Also try just the hex
passwords_to_try = [
secret_hex,
secret_bytes.hex() if 'secret_bytes' in locals() else secret_hex,
]
if 'secret_bytes' in locals():
# Try ASCII interpretation
passwords_to_try.append(''.join(chr(b) for b in secret_bytes if 32 <= b <= 126))
print("\n" + "="*60)
print("Testing passwords...")
print("="*60)
for i, pwd in enumerate(passwords_to_try):
print(f"\nAttempt {i+1}: {pwd[:60]}...")
result = subprocess.run(['7z', 'x', f'-p{pwd}', 'flag.zip', '-aoa'],
capture_output=True, text=True, timeout=5)
if 'Everything is Ok' in result.stdout:
print(f"\n{'='*60}")
print(f"✓✓✓ SUCCESS! ✓✓✓")
print(f"{'='*60}")
print(f"Password: {pwd}")
print(f"{'='*60}\n")
with open('SOLUTION.txt', 'w') as f:
f.write(pwd)
# Read the flag
print("\nFlag content:")
with open('cute-kitty-noises.txt', 'r') as f:
print(f.read())
break
else:
print("✗ Wrong password")
print("\nDone!")
def decode_meow():
with open("cute-kitty-noises.txt", "r") as f:
content = f.read().strip()
parts = content.split(';')
numbers = []
for part in parts:
if not part:
numbers.append(0)
else:
numbers.append(part.count("Meow"))
decoded_string = ""
i = 0
while i < len(numbers):
if numbers[i] == 2 and i + 3 < len(numbers) and numbers[i+2] == 1 and numbers[i+3] == 0:
char_code = numbers[i+1]
decoded_string += chr(char_code)
i += 4
else:
i += 1
print(decoded_string)
if __name__ == "__main__":
decode_meow()
flag{35dcba13033459ca799ae2d990d33dd3}g
✓ Shell python3 -c " │
│ import random │
│ │
│ PRIME = 0x010000000000000000000000000000000000000000000000000000000000000129 │
│ │
│ def _mod_inverse(a, m): │
│ if a == 0: │
│ raise ValueError('Cannot compute inverse of 0.') │
│ return pow(a, -1, m) │
│ │
│ def reconstruct_secret(shares, prime=PRIME): │
│ if not shares: │
│ raise ValueError('No shares provided for reconstruction.') │
│ │
│ k = len(shares) │
│ secret = 0 │
│ │
│ for j in range(k): │
│ xj, yj = shares[j] │
│ │
│ numerator = 1 │
│ denominator = 1 │
│ for m in range(k): │
│ if j == m: │
│ continue │
│ xm, _ = shares[m] │
│ numerator = (numerator * (-xm % prime)) % prime │
│ denominator = (denominator * ((xj - xm) % prime)) % prime │
│ │
│ term = (yj * numerator * _mod_inverse(denominator, prime)) % prime │
│ secret = (secret + term) % prime │
│ │
│ return secret │
│ │
│ with open('/mnt/tmp/CTF/2025-Huntress-CTF/17/all_user_comments.txt', 'r') as f: │
│ lines = f.readlines() │
│ │
│ shares = [] │
│ for line in lines: │
│ if '-' in line: │
│ parts = line.strip().split('-') │
│ x = int(parts[0]) │
│ y = int(parts[1], 16) │
│ shares.append((x, y)) │
│ │
│ secret = reconstruct_secret(shares) │
│ │
│ # Convert the secret to a string │
│ flag = secret.to_bytes((secret.bit_length() + 7) // 8, 'big').decode('utf-8') │
│ │
│ print(flag) │
│ " │
│ │
│ *ZIP password: FApekJ!yJ69YajWs