Конкурс заметок

Platform: duckerz | Category: Web | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-21 | Status: Solved Techniques: lcg_state_recovery, prng_prediction

Summary

URL: http://tasks.duckerz.ru:30020

Конкурс заметок — Duckerz CTF

Description

Прими участие в конкурсе! Опубликуй свою заметку и попробуй угадать её номер. Если ты назовёшь правильное число до публикации, победа будет за тобой!

URL: http://tasks.duckerz.ru:30020

Analysis

The application allows creating notes and assigns them numeric IDs. To get the flag, you need to guess the note ID before it is created.

API endpoints:

• POST /api/notes - Create a note with JSON: {"title": "...", "username": "...", "text": "...", "id": guess_id}
• GET /api/notes?id=X - Get a note by ID
• GET /api/notes/list?dir=/ - List all notes ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Vulnerability

The server uses java.util.Random to generate note IDs. This is a classic cryptographic weakness because Java Random uses a Linear Congruential Generator (LCG):

seed = (seed * 0x5DEECE66D + 0xB) mod 2^48
nextInt() = seed >> 16 (upper 32 bits)

Key insight: Given two consecutive 32-bit outputs from Java Random, we know the upper 32 bits of two consecutive 48-bit states. By brute-forcing the lower 16 bits of the first state (only 65536 possibilities), we can verify our guess by computing the next state using the LCG formula. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

Attack steps:

1. Data collection: Create two notes in a row, get two consecutive IDs
2. State recovery: Brute-force the lower 16 bits of the first state
3. Prediction: Calculate the next ID using the LCG formula
4. Exploitation: Submit a note with the predicted ID

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Java Random LCG Cracker for Note ID Prediction
"""
import requests
import time

URL = "http://tasks.duckerz.ru:30020"

# LCG constants for java.util.Random
MULTIPLIER = 0x5DEECE66D
ADDEND = 0xB
MASK = (1 << 48) - 1
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def create_note(title="test", username="user", text="content", guess_id=None):
    """Create a note and return its ID"""
    data = {
        "title": title,
        "username": username,
        "text": text
    }
    if guess_id is not None:
        data["id"] = guess_id
    
    resp = requests.post(f"{URL}/api/notes", json=data)
    return resp.json()

def get_two_consecutive_ids():
    """Get two consecutive IDs by creating two notes"""
    r1 = create_note(title="note1")
    id1 = r1.get("id")
    
    # Small delay to ensure sequential generation
    time.sleep(0.1)
    
    r2 = create_note(title="note2")
    id2 = r2.get("id")
    
    return id1, id2
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def crack_seed(id1, id2):
    """
    Crack the internal state of java.util.Random.
    
    Given two consecutive 32-bit outputs, we know the upper 32 bits
    of two consecutive 48-bit states. Brute-force the lower 16 bits.
    """
    # Convert signed int to unsigned if needed
    if id1 < 0:
        id1 = id1 + (1 << 32)
    if id2 < 0:
        id2 = id2 + (1 << 32)
    
    # Upper 32 bits of first state
    upper1 = id1 << 16
    
    # Try all possible lower 16 bits
    for lower in range(1 << 16):
        seed1 = upper1 | lower
        
        # Compute next state
        seed2 = (seed1 * MULTIPLIER + ADDEND) & MASK
        
        # Check if upper 32 bits match id2
        predicted_id2 = seed2 >> 16
        if predicted_id2 == id2:
            print(f"[+] Found seed! Lower bits: {lower}")
            return seed2
    
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def predict_next(seed):
    """Predict the next ID from current seed"""
    next_seed = (seed * MULTIPLIER + ADDEND) & MASK
    next_id = next_seed >> 16
    
    # Convert to signed 32-bit int (Java behavior)
    if next_id >= (1 << 31):
        next_id = next_id - (1 << 32)
    
    return next_id, next_seed

def main():
    print("[*] Getting two consecutive IDs...")
    id1, id2 = get_two_consecutive_ids()
    print(f"[*] ID1: {id1}, ID2: {id2}")
    
    print("[*] Cracking seed...")
    seed = crack_seed(id1, id2)
    
    if seed is None:
        print("[-] Failed to crack seed")
        return
    
    print(f"[+] Current seed: {hex(seed)}")
    
    # Predict next ID
    predicted_id, _ = predict_next(seed)
    print(f"[+] Predicted next ID: {predicted_id}")
    
    # Create note with predicted ID
    print("[*] Creating note with predicted ID...")
    result = create_note(
        title="Winner",
        username="hacker",
        text="I predicted this!",
        guess_id=predicted_id
    )
    
    print(f"[+] Result: {result}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

if __name__ == "__main__":
    main()

Alternative approach (if rate limiting is present)

If the server has rate limiting between requests, you need to account for possible skipped states:

 python read-only • copy allowed Copy
def crack_with_gap(id1, id2, max_gap=10):
    """Try to crack seed accounting for possible gaps between IDs"""
    if id1 < 0:
        id1 = id1 + (1 << 32)
    if id2 < 0:
        id2 = id2 + (1 << 32)
    
    upper1 = id1 << 16
    
    for lower in range(1 << 16):
        seed = upper1 | lower
        
        # Try different gaps
        for gap in range(1, max_gap + 1):
            test_seed = seed
            for _ in range(gap):
                test_seed = (test_seed * MULTIPLIER + ADDEND) & MASK
            
            if (test_seed >> 16) == id2:
                print(f"[+] Found! Gap: {gap}, Lower bits: {lower}")
                return test_seed, gap
    
    return None, 0

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Defense

For generating unpredictable IDs, use:

• java.security.SecureRandom instead of java.util.Random
• UUID v4 (java.util.UUID.randomUUID())
• Cryptographically secure hashes of random data

References

• Cracking Java Random
• LCG Wikipedia ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍