0xL4ugh CTF V5 - SpiralFloat

Executive Summary

Challenge: SpiralFloat CTF: 0xL4ugh CTF V5 Category: Crypto Difficulty: Hard Flag: 0xL4ugh{B1naryS3archM0not0n1c}

SpiralFloat challenges us to reverse a chaotic map function applied to a flag. The transformation involves 81 iterations of a spiral function based on the golden ratio. While the function is contracting in the forward direction, it is expanding in reverse, making direct inversion difficult due to precision loss. The solution utilizes Interval Arithmetic to track possible input ranges and a Depth-First Search (DFS) with pruning based on valid ASCII constraints to recover the flag digits.

Problem Description

We are provided with a SageMath script prob.sage that implements a chaotic map function called spiral. The script takes a flag, converts it to a floating-point number, applies the spiral transformation 81 times, and marks about 13% of the resulting digits as ?.

Our goal is to recover the unknown digits and reverse the transformation to find the flag.

Analysis

The core transformation is:

x_{i+1} = r \sqrt{x_i^2 + 1} + (1-r)(x_i + \phi)

where $r = i/N$ and $\phi$ is the golden ratio.

Analysis reveals that this function is contracting in the forward direction but expanding in the reverse direction. This means that if we try to reverse the function from $x_{i+1}$ to $x_i$ , any small error in $x_{i+1}$ will be amplified.

However, the “Expansion Ratio” is not infinite. It’s finite but large. This allows us to use interval arithmetic to track the set of all possible inputs $x_0$ that could result in a given output $y$ .

Solution Strategy

Interval Arithmetic: We use the mpmath library’s interval arithmetic (iv context) to represent the unknown digits ? as intervals [0, 9].
Depth-First Search (DFS): We perform a DFS to guess the unknown digits one by one.
Pruning Conditions:
- Range Check: The starting $x_0$ must correspond to a valid flag format (30 bytes, starting with 0xL4ugh{). If the reversed interval falls outside $[x_{min}, x_{max}]$ , we prune the branch.
- ASCII Constraint: This was the critical step. Even valid numerical ranges contained “garbage” solutions. We implemented prune_interval to convert the interval of potential $x_0$ values back to bytes. If any fully determined bytes are NOT printable ASCII, we prune the branch.

Solver Script

1
from mpmath import mp, iv
2
import sys
3

4
# Configure precision
5
mp.dps = 110 # Extra precision for scalar operations
6
iv.dps = 110 # Extra precision for interval operations
7

8
def spiral_inverse_interval(y_interval, phi, r):
9
    # f(x) = r*sqrt(x^2+1) + (1-r)*(x+phi)
10
    # y = f(x)
11
    # x = f_inv(y)
12
    # Since f is monotonic increasing, f(Interval) = [f(a), f(b)]
13
    # So f_inv([y_a, y_b]) = [f_inv(y_a), f_inv(y_b)]
14
    # We just need a scalar inverse function
15

16
    def scalar_inverse(target_y):
17
        try:
18
            # guess: x ~ target_y - (1-r)phi
19
            if r == 0:
20
                return target_y - phi
21
            guess = target_y
22
            # Use mp.findroot (scalar)
23
            return mp.findroot(lambda x: r * mp.sqrt(x*x + 1) + (1 - r) * (x + phi) - target_y, guess, tol=mp.mpf('1e-105'))
24
        except:
25
            # Fallback binary search
26
            low = mp.mpf(-50)
27
            high = mp.mpf(500)
28
            for _ in range(100):
29
                mid = (low+high)/2
30
                val = r * mp.sqrt(mid*mid + 1) + (1 - r) * (mid + phi)
31
                if val < target_y:
32
                    low = mid
33
                else:
34
                    high = mid
35
            return (low+high)/2
36

37
    a = scalar_inverse(y_interval.a)
38
    b = scalar_inverse(y_interval.b)
39
    # Return new interval
40
    return iv.mpf([a, b])
41

42
# Constants
43
masked_str = "?7086013?3756162?51694057?5285516?54803756?9202316?39221780?4895755?50591029"
44

45
# Precompute target range
46
from Crypto.Util.number import bytes_to_long
47
prefix = b'0xL4ugh{'
48
suffix = b'}'
49
wildcards = 21
50
min_flag_bytes = prefix + b'\x00' * wildcards + suffix
51
max_flag_bytes = prefix + b'\xff' * wildcards + suffix
52

53
flag_min_int = bytes_to_long(min_flag_bytes)
54
flag_max_int = bytes_to_long(max_flag_bytes)
55

56
# x0 = flag * 10^-flen
57
flen_min = len(str(flag_min_int))
58
flen = flen_min
59
x0_min = mp.mpf(flag_min_int) * (mp.mpf(10) ** -flen)
60
x0_max = mp.mpf(flag_max_int) * (mp.mpf(10) ** -flen)
61

62
print(f"Target x0 range: [{x0_min}, {x0_max}]")
63

64
phi = (1 + mp.sqrt(5)) / 2
65
iterations = 81
66

67
# Indices of question marks
68
q_indices = [i for i, c in enumerate(masked_str) if c == '?']
69
print(f"Unknown indices: {q_indices}")
70

71
def prune_interval(iv_val):
72
    # Check if interval allows any valid ASCII flag
73
    scaled = iv_val * (mp.mpf(10) ** flen)
74

75
    # Get conservative integer bounds
76
    low_int = int(mp.floor(scaled.a))
77
    high_int = int(mp.ceil(scaled.b))
78

79
    from Crypto.Util.number import long_to_bytes
80

81
    try:
82
        low_b = long_to_bytes(low_int)
83
        high_b = long_to_bytes(high_int)
84
    except:
85
        return True
86

87
    if len(low_b) != len(high_b):
88
        return True
89

90
    for i in range(len(low_b)):
91
        if low_b[i] == high_b[i]:
92
            b = low_b[i]
93
            if not (32 <= b <= 126):
94
                return False # Prune!
95
        else:
96
            break
97

98
    return True
99

100
def solve(q_idx_ptr, current_masked):
101
    low_list = list(current_masked)
102
    high_list = list(current_masked)
103

104
    for i in range(len(current_masked)):
105
        if current_masked[i] == '?':
106
            low_list[i] = '0'
107
            high_list[i] = '9'
108

109
    low_s = "".join(low_list)
110
    high_s = "".join(high_list)
111

112
    potential_decimal_pos = [1, 2, 3]
113
    valid_dec_pos = []
114

115
    for dec_pos in potential_decimal_pos:
116
        def to_mpf(s, dp):
117
             return mp.mpf(s[:dp] + "." + s[dp:])
118

119
        val_iv = iv.mpf([to_mpf(low_s, dec_pos), to_mpf(high_s, dec_pos)])
120

121
        curr_iv = val_iv
122
        for i in range(iterations - 1, -1, -1):
123
             r = mp.mpf(i) / iterations
124
             curr_iv = spiral_inverse_interval(curr_iv, phi, r)
125

126
        if not prune_interval(curr_iv):
127
            continue
128

129
        if not (curr_iv.b < x0_min or curr_iv.a > x0_max):
130
            valid_dec_pos.append(dec_pos)
131

132
    if not valid_dec_pos:
133
        return None
134

135
    if q_idx_ptr == len(q_indices):
136
        dec_pos = valid_dec_pos[0]
137
        final_s = to_mpf(current_masked, dec_pos)
138

139
        x = final_s
140
        for i in range(iterations - 1, -1, -1):
141
            r = mp.mpf(i) / iterations
142
            x = spiral_inverse_interval(iv.mpf([x, x]), phi, r).a
143

144
        flag_val = x * (mp.mpf(10) ** flen)
145
        flag_int = int(mp.nint(flag_val.mid))
146

147
        from Crypto.Util.number import long_to_bytes
148
        try:
149
            flag_b = long_to_bytes(flag_int)
150
            if flag_b.startswith(prefix) and flag_b.endswith(suffix):
151
                if all(32 <= b <= 126 for b in flag_b):
152
                    print(f"FOUND ASCII FLAG: {flag_b}")
153
                    return flag_b
154
        except:
155
            pass
156
        return None
157

158
    target_idx = q_indices[q_idx_ptr]
159
    print(f"Level {q_idx_ptr}: solving index {target_idx}")
160

161
    for digit in range(10):
162
        next_masked = list(current_masked)
163
        next_masked[target_idx] = str(digit)
164
        next_masked = "".join(next_masked)
165

166
        res = solve(q_idx_ptr + 1, next_masked)
167
        if res: return res
168

169
if __name__ == "__main__":
170
    solve(0, masked_str)