📦 vx-underground

fixed_list.csv

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 syntax

ssss_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}