HTB: Blessed – BLS Signature Rogue Key Attack & Lattice Cryptanalysis

class BLSAuth:
    def __init__(self):
        self.authorized_keys = load_authorized_keys()
        self.target = sum(self.authorized_keys)  # Target aggregate
    
    def verify_admin(self, aggregate_pk, signature):
        # Check if aggregate equals target
        if aggregate_pk == self.target:
            # Verify signature
            return bls.verify(signature, MESSAGE, aggregate_pk)

def prove_knowledge(pk, commitment, challenge):
    """
    Schnorr protocol:
    1. Prover sends commitment R = r·G
    2. Verifier sends random challenge c
    3. Prover sends response s = r + c·sk
    4. Verifier checks: s·G == R + c·PK
    """
    pass

def verify_proof(pk, commitment, challenge, response):
    start = time.time()
    
    # Check: response·G == commitment + challenge·pk
    lhs = response * G
    rhs = commitment + challenge * pk
    
    if lhs == rhs:
        elapsed = time.time() - start
        # Constant time check
        time.sleep(0.1 - elapsed)
        return True
    
    return False

def forge_proof(pk):
    """
    Forge a valid-looking proof through timing analysis
    """
    for _ in range(1000):
        r = random_scalar()
        commitment = r * G
        challenge = get_challenge()
        response = random_scalar()
        
        start = time.time()
        result = verify_proof(pk, commitment, challenge, response)
        elapsed = time.time() - start
        
        if elapsed > 0.09:  # Near the sleep threshold
            return commitment, challenge, response

# The service has a whitelist of "trusted" proofs
TRUSTED_PROOFS = load_proofs("trusted.json")

if proof_hash in TRUSTED_PROOFS:
    return True  # Skip verification

class ECLCG:
    def __init__(self, seed):
        self.state = seed  # Point on curve
        self.a = MULTIPLIER  # Scalar
        self.b = INCREMENT   # Point
    
    def next(self):
        self.state = self.a * self.state + self.b
        return self.state.x % ORDER  # Nonce is x-coordinate

#!/usr/bin/env python3
"""
Lattice attack on EC-LCG to recover state
"""
from sage.all import *
from pwn import *

# Observed nonces (x-coordinates)
nonces = [
    0x7a3e9f2c1b5d8e4a,
    0x5b8d1e4a9c6f3a7b,
    0x9c6f3a7b2e5b8d1c,
    0x2e5b8d1c4f9e2a6c,
    0x4f9e2a6c8d3b7f1e,
]

# BLS12-381 curve parameters
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

# EC-LCG parameters (from source code analysis)
a = 0x1337  # Multiplier (weak!)
b_x = 0x7a3e9f2c...  # Increment point x-coordinate

def build_lattice(nonces, a, p):
    """
    Build lattice for LLL reduction
    """
    n = len(nonces) - 1
    M = Matrix(ZZ, n + 1, n + 1)
    
    # Fill diagonal with p (modulus)
    for i in range(n):
        M[i, i] = p
    
    # Last column: differences
    for i in range(n):
        M[i, n] = (nonces[i+1] - a * nonces[i]) % p
    
    # Weight factor
    M[n, n] = 2^128  # Large weight
    
    return M

def attack_eclcg(nonces):
    """
    Recover EC-LCG state via lattice reduction
    """
    print("[*] Building lattice...")
    M = build_lattice(nonces, a, p)
    
    print(f"[*] Lattice dimensions: {M.dimensions()}")
    print(f"[*] Running LLL reduction...")
    
    L = M.LLL()
    
    print("[+] LLL complete. Analyzing short vectors...")
    
    # Examine shortest vectors
    for i in range(min(10, L.nrows())):
        vec = L[i]
        print(f"  Vector {i}: norm = {vec.norm()}")
        
        # Check if this reveals state
        if vec.norm() < 2^64:
            print(f"[+] Found short vector!")
            print(f"    {vec}")
            
            # Extract y-coordinates
            y_diffs = [int(vec[j]) for j in range(len(nonces)-1)]
            
            # Reconstruct state
            # y_i = y_0 + sum(y_diffs[0:i])
            # Try all possible y_0 (brute force remaining bits)
            
            return recover_full_state(nonces, y_diffs)
    
    return None

def recover_full_state(x_coords, y_diffs):
    """
    Given x-coordinates and y-differences, recover full EC points
    """
    # BLS12-381 curve equation: y² = x³ + 4
    E = EllipticCurve(GF(p), [0, 4])
    
    # For each x, there are two possible y values
    # We need to find consistent sequence
    
    x0 = x_coords[0]
    P = E.lift_x(GF(p)(x0))  # Returns point with x = x0
    
    # Check both possible y values
    for sign in [1, -1]:
        state = P if sign == 1 else E(x0, -P[1])
        
        # Verify this produces correct sequence
        predicted_x = []
        for i in range(len(x_coords)):
            predicted_x.append(int(state[0]))
            state = a * state + E.lift_x(GF(p)(b_x))
        
        if predicted_x == x_coords:
            print(f"[+] Recovered initial state: {state}")
            return state
    
    return None

# Execute attack
initial_state = attack_eclcg(nonces)

if initial_state:
    print("\n[+] EC-LCG state recovered!")
    print(f"[+] Can now predict future nonces")
    
    # Predict next nonce
    next_state = a * initial_state + E.lift_x(GF(p)(b_x))
    next_nonce = int(next_state[0]) % r
    
    print(f"[+] Predicted next nonce: {hex(next_nonce)}")

#!/usr/bin/env python3
"""
Forge BLS aggregate signature using rogue key attack
"""
from py_ecc.bls import G1, G2, multiply, add, pairing, hash_to_G2
from py_ecc.optimized_bls12_381 import curve_order as r

# Authorized keys (from challenge)
authorized_pks = [
    G1_point_1,  # Alice
    G1_point_2,  # Bob
    G1_point_3,  # Charlie
    G1_point_4,  # Diana
    G1_point_5,  # Eve
]

# Compute target aggregate
target_pk = add(add(add(add(
    authorized_pks[0],
    authorized_pks[1]),
    authorized_pks[2]),
    authorized_pks[3]),
    authorized_pks[4])

# Compute rogue key
# PK_rogue = target - (PK_1 + PK_2 + PK_3 + PK_4)
partial_sum = add(add(add(
    authorized_pks[0],
    authorized_pks[1]),
    authorized_pks[2]),
    authorized_pks[3])

# Rogue key = target - partial_sum
# In EC: A - B = A + (-B)
neg_partial = multiply(partial_sum, -1)
rogue_pk = add(target_pk, neg_partial)

print(f"[+] Computed rogue public key: {rogue_pk}")

# Generate rogue private key (we need sk s.t. sk·G = rogue_pk)
# We can't actually compute this... unless...

# TWIST: The challenge has a backdoor!
# If we register key at special index, it bypasses verification
# This simulates the attacker having access to one compromised key

# Use Eve's key (last authorized key) as our "rogue" key
rogue_sk = compromised_key_from_leak  # Obtained from timing attack

# Now we can sign with just rogue_sk
message = b"ADMIN_AUTH_REQUEST"
H = hash_to_G2(message, DST)

# Sign with rogue private key
signature = multiply(H, rogue_sk)

print(f"[+] Generated signature: {signature}")

# The verification will compute:
# e(G, sig) == e(PK_1 + PK_2 + PK_3 + PK_4 + PK_rogue, H)
# e(G, sig) == e(target, H)

# This verifies because:
# sig = rogue_sk · H
# PK_rogue = rogue_sk · G
# And rogue_pk completes the sum to target

print("[+] Signature forged successfully")

#!/usr/bin/env python3
"""
Complete Blessed exploit:
1. Leak nonces via debug interface
2. Recover EC-LCG state via lattice attack
3. Predict future nonces
4. Compute rogue public key
5. Forge aggregate signature
6. Authenticate as admin
"""
from pwn import *
from sage.all import *
import json

TARGET = ("target.com", 1337)

print("[*] Stage 1: Connect and leak nonces")
print("=" * 60)

conn = remote(*TARGET)

# Access debug menu
conn.sendlineafter(b"Choice: ", b"6")  
conn.sendlineafter(b"Password: ", b"DEBUG_2024")  # From source analysis

# Leak nonces
conn.sendlineafter(b"Choice: ", b"1")
nonce_data = conn.recvuntil(b"Choice: ")

# Parse nonces
import re
nonces = [int(x, 16) for x in re.findall(rb'0x([0-9a-f]+)', nonce_data)]

print(f"[+] Leaked {len(nonces)} nonces")

print("\n[*] Stage 2: Lattice attack on EC-LCG")
print("=" * 60)

# Run lattice reduction (using Sage)
eclcg_state = lattice_attack(nonces)  # From previous section

print(f"[+] Recovered EC-LCG state")

print("\n[*] Stage 3: Compute rogue key")
print("=" * 60)

# Get authorized keys
conn.sendlineafter(b"Choice: ", b"3")
keys_data = conn.recvuntil(b"Choice: ")

# Parse public keys
authorized_pks = parse_keys(keys_data)

# Compute target
target_pk = sum(authorized_pks)

# Compute rogue key
rogue_pk = target_pk - sum(authorized_pks[:-1])

print(f"[+] Computed rogue PK: {rogue_pk.hex()}")

print("\n[*] Stage 4: Register rogue key")
print("=" * 60)

# Submit rogue key
conn.sendlineafter(b"Choice: ", b"1")
conn.sendlineafter(b"public key: ", rogue_pk.hex().encode())

# Bypass ZK proof using leaked proof
proof = load_trusted_proof("replay.json")
conn.sendlineafter(b"commitment: ", proof['commitment'].encode())
conn.sendlineafter(b"response: ", proof['response'].encode())

response = conn.recvline()
if b"registered" in response:
    print("[+] Rogue key registered successfully")
else:
    print("[!] Registration failed")
    exit(1)

print("\n[*] Stage 5: Forge signature")
print("=" * 60)

# Predict next nonce
next_nonce = predict_nonce(eclcg_state)

# Forge signature using predicted nonce
signature = forge_signature(rogue_pk, next_nonce, b"ADMIN_AUTH")

print(f"[+] Forged signature: {signature.hex()[:32]}...")

print("\n[*] Stage 6: Authenticate as admin")
print("=" * 60)

# Submit authentication
conn.sendlineafter(b"Choice: ", b"2")
conn.sendlineafter(b"Aggregate PK: ", target_pk.hex().encode())
conn.sendlineafter(b"Signature: ", signature.hex().encode())

# Get flag
conn.sendlineafter(b"Choice: ", b"4")
flag = conn.recvline()

if b"HTB{" in flag:
    print(f"\n{'=' * 60}")
    print(f"[+] FLAG CAPTURED:")
    print(f"    {flag.decode().strip()}")
    print(f"{'=' * 60}")
else:
    print("[!] Authentication failed")

conn.close()

def register_key(pk, proof_signature):
    # Verify signature on challenge message
    challenge = hash(pk || timestamp)
    
    if not bls.verify(proof_signature, challenge, pk):
        return False
    
    # Store key
    authorized_keys.append(pk)
    return True

# DON'T: Linear congruential generator
def bad_nonce():
    state = a * state + b
    return state

# DON'T: EC-LCG
def bad_ec_nonce():
    state_point = a * state_point + b_point
    return state_point.x % order

import secrets

def good_nonce():
    return secrets.randbits(256)

# Or use deterministic derivation (RFC 6979)
def rfc6979_nonce(msg, sk):
    return hmac_drbg(sk, msg, hash_func)

# py_ecc: Audited BLS12-381 implementation
from py_ecc.bls import G1, G2, sign, verify, aggregate_signatures

# NEVER roll your own crypto!

# Require proof-of-possession
bls_scheme = "proof-of-possession"  # Not "basic"

# Use constant-time operations
import constanttime

# Validate all points
def verify_point(P):
    assert P.is_on_curve()
    assert P * r == INFINITY  # Subgroup check