what the fuck is a logarithm - pingCTF

Description

rev with source code? in python? with symbols? oh my....

Given a Python script generated.py that implements a stack machine using exp() and ln() operations with high-precision Decimal arithmetic. The script reads a flag and validates it through a series of stack operations.

Analysis

Stack Machine Architecture

The checker uses a simple stack machine with these primitives:

from decimal import Decimal, getcontext
CTX = getcontext()
CTX.prec = 400  # High precision

stack = []
OMEGA = Decimal("-inf")

def E():
    a = stack.pop()
    b = stack.pop()
    stack.append((Decimal(0.0) if a == OMEGA else CTX.exp(a)) - CTX.ln(b))

def s():  # swap
    stack[-1], stack[-2] = stack[-2], stack[-1]

def one():
    stack.append(Decimal('1'))

def neg_inf():
    stack.append(Decimal('-Infinity'))

def push_inp():
    global inp
    stack.append(Decimal(ord(inp[0]) - 48))
    inp = inp[1:]

The E() Operation

The core operation E() computes: exp(a) - ln(b) where a and b are popped from the stack.

Key insight: When combined with specific patterns of one(), s(), and neg_inf(), this implements multiplication using logarithm identities:

• exp(ln(a) + ln(b)) = a * b
• ln(exp(x)) = x

The repeated instruction patterns effectively chain multiplications.

Input Encoding

Each input character is encoded as ord(char) - 48:

• '0' → 0, '9' → 9
• 'A' → 17, 'Z' → 42
• 'a' → 49, 'z' → 74
• '{' → 75, '}' → 77, '_' → 47

Structure Discovery

Through tracing, the checker processes 32 characters in 4 groups of 8. Each group computes a polynomial:

P(group) = sum(73.21^(k+1) * char[k] for k in range(8))

This is essentially a base-73.21 number representation where each character contributes a weighted term.

Expected Values

The checker embeds 4 target constants and validates that each group's polynomial matches:

expected = [
    Decimal('46741716782375706.839...'),  # Group 0: chars 0-7
    Decimal('46291277424349185.554...'),  # Group 1: chars 8-15
    Decimal('42149201139278358.422...'),  # Group 2: chars 16-23
    Decimal('64147886106222656.238...'),  # Group 3: chars 24-31
]

The final check: abs(stack.pop()) < 0.1 (or stack.pop() < 0.1 in original).

Solution

Recovery Strategy

1. Identify known characters:

   • Group 0 starts with ping{ (positions 0-4)
   • Group 3 ends with } (position 7)

2. Greedy search from highest power:

   • For each unknown position, approximate: digit ≈ remaining / 73.21^(pos+1)
   • Search nearby values (±3) to find exact match

Solve Script

#!/usr/bin/env python3
from decimal import Decimal, getcontext

CTX = getcontext()
CTX.prec = 400

BASE = Decimal('73.21')

expected = [
    Decimal('46741716782375706.839...'),
    Decimal('46291277424349185.554...'),
    Decimal('42149201139278358.422...'),
    Decimal('64147886106222656.238...'),
]

def search_group(target, known_positions=None, known_values=None):
    """Search for 8 characters that encode to target."""
    if known_positions is None:
        known_positions, known_values = [], []
    
    # Calculate known contribution
    known_contribution = sum(
        BASE ** (pos + 1) * val 
        for pos, val in zip(known_positions, known_values)
    )
    remaining_target = target - known_contribution
    unknown_positions = [i for i in range(8) if i not in known_positions]
    
    def search_recursive(pos_idx, remaining, chars):
        if pos_idx == len(unknown_positions):
            return chars.copy() if abs(remaining) < 1 else None
        
        pos = unknown_positions[-(pos_idx + 1)]  # Highest power first
        power = BASE ** (pos + 1)
        approx = int(remaining / power)
        
        for c in range(max(0, approx - 3), min(80, approx + 4)):
            chars[pos] = c
            result = search_recursive(pos_idx + 1, remaining - power * c, chars)
            if result:
                return result
        return None
    
    chars = [None] * 8
    for pos, val in zip(known_positions, known_values):
        chars[pos] = val
    return search_recursive(0, remaining_target, chars)

# Known: ping{ = [64, 57, 62, 55, 75] (ord - 48)
# Known: } = 77

result_0 = search_group(expected[0], [0,1,2,3,4], [64,57,62,55,75])
result_1 = search_group(expected[1])
result_2 = search_group(expected[2])
result_3 = search_group(expected[3], [7], [77])

flag = ''.join(
    chr(v + 48) for group in [result_0, result_1, result_2, result_3] for v in group
)
print(f"Flag: {flag}")

Decoded Groups

Group	Encoded Values	Characters
0	[64,57,62,55,75,1,47,56]	ping{1_h
1	[4,55,3,47,61,4,55,56]	473_m47h
2	[47,47,47,1,55,47,5,51]	___17_5c
3	[4,66,3,5,47,61,53,77]	4r35_me}

Verification

$ echo "ping{REDACTED}" | python3 generated.py
Flag is correct!

$ echo "ping{REDACTED}" | python3 generated_fixed.py
Flag is correct!