babyCrypto

Platform: grsu | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-01-10 | Status: Solved Techniques: hmac_verification, salt_bruteforce, xor_decryption

Summary

Task: Recover 3-byte HMAC salt from 128 message/MAC pairs. Solution: Brute-force the small salt space with early filtering, then XOR-decrypt the flag.

babyCrypto - GRSU CTF

Description

We have many messages with short MAC signatures. Recover the salt and find the flag.

Given:

• dataset.json with 128 message/mac pairs
• flag_enc: encrypted flag
• params: HMAC-SHA256, truncated to 4 bytes, salt length 3 bytes
• note: "salt is secret and same for all messages; flag_enc is XOR(flag, salt repeated)"

Analysis

Cryptosystem Parameters

1. HMAC-SHA256 is used to compute MAC
2. MAC truncated to 4 bytes (32 bits) - sufficient for verification
3. Salt is only 3 bytes = 2^24 = 16,777,216 possible values
4. 128 message/MAC pairs - redundant for salt verification ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Vulnerability

The key (salt) space is too small:

• 3 bytes = 16.7 million variants
• At ~100k checks/sec = ~3 minutes of brute-force
• 128 pairs guarantee uniqueness of the found salt (collision probability ~2^(-128*32) = 0)

Brute-force Optimization

Instead of checking all 128 pairs for each candidate:

1. First check only the first 5 pairs (quick filter)
2. If passed - full verification of all 128 pairs
3. This eliminates ~99.99999% of wrong candidates early

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
GRSU CTF - babyCrypto
Brute-force 3-byte HMAC salt and decrypt XOR flag
"""
import json
import hmac
import hashlib
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Load dataset
with open('dataset.json', 'r') as f:
    data = json.load(f)

dataset = data['dataset']
flag_enc = bytes.fromhex(data['flag_enc'])

# Prepare message/MAC pairs
pairs = [(item['message'].encode(), bytes.fromhex(item['mac'])) for item in dataset]

def check_salt(salt_bytes):
    """Verify salt against all message/MAC pairs"""
    for msg, expected_mac in pairs:
        computed = hmac.new(salt_bytes, msg, hashlib.sha256).digest()[:4]
        if computed != expected_mac:
            return False
    return True
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def check_salt_first_n(salt_bytes, n=5):
    """Quick filter: check only first N pairs"""
    for msg, expected_mac in pairs[:n]:
        computed = hmac.new(salt_bytes, msg, hashlib.sha256).digest()[:4]
        if computed != expected_mac:
            return False
    return True

# Brute-force 3-byte salt (2^24 = 16,777,216 possibilities)
print("Brute-forcing 3-byte salt...")
for i in range(256**3):
    salt = i.to_bytes(3, 'big')
    
    # Quick filter on first 5 pairs
    if check_salt_first_n(salt, 5):
        # Full verification on all 128 pairs
        if check_salt(salt):
            print(f"[+] Found salt: {salt.hex()} (decimal: {i})")
            
            # Decrypt flag with repeating XOR
            flag = bytes([b ^ salt[i % 3] for i, b in enumerate(flag_enc)])
            print(f"[+] Flag: {flag.decode()}")
            break
    
    # Progress indicator
    if i % 1000000 == 0:
        print(f"    Progress: {i:,} / 16,777,216 ({100*i/16777216:.1f}%)")

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

Result

Brute-forcing 3-byte salt...
    Progress: 0 / 16,777,216 (0.0%)
[+] Found salt: 036ecb (decimal: 224971)
[+] Flag: grodno{REDACTED}

Theoretical Background

Why are 128 pairs sufficient?

Probability of random MAC match for one pair: 1/2^32

For N pairs, false positive probability: (1/2^32)^N = 1/2^(32N)

With N=128: 1/2^4096 - practically impossible

Attack Complexity

• Search space: 2^24 = 16,777,216
• HMAC-SHA256 operations per candidate: 5 (quick filter) + rarely 128 (full check)
• Total time: ~1-5 minutes on a modern CPU ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Alternative Approaches

1. Parallel brute-force - split the search space across threads
2. GPU acceleration - HMAC-SHA256 parallelizes well
3. Rainbow tables - precompute MAC for all salts (requires lots of memory)

References

• HMAC RFC 2104
• Breaking Bad reference - "Walter, put your salt away" ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍