Золотая середина

Platform: hackerlab | Category: Misc | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2025-12-25 | Status: Solved Techniques: Binary Search algorithm for optimal guessing, Logarithmic complexity calculation, Network automation with pwntools

Summary

Task: Guess a number from 0 to 10^24 with only 80 attempts. Solution: Binary search algorithm - log₂(10^24) ≈ 80, making it the only viable approach.

Золотая середина — hackerlab.pro

Description

Найдите оптимальный алгоритм решения задания. Хотите вручную? Удачи! Но количество попыток угадывания ограничено :)

Server: 62.173.140.174:10200

Analysis

Reconnaissance

When connecting to the server, we get a "guess the number" game:

• Range: from 0 to 10^24 (1000000000000000000000000)
• Attempt limit: 80
• Server responds with "больше" (higher) or "меньше" (lower)

Math

Key observation:

log₂(10^24) = 24 × log₂(10) ≈ 24 × 3.322 ≈ 79.7

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

80 attempts — exactly what's needed for binary search!

Hint in the Name

"Золотая середина" (Golden Middle) — a direct hint at dividing in half (binary search).

Algorithm

Binary Search:

1. Start with range [0, 10^24]
2. Guess the middle: mid = (low + high) // 2
3. If "больше" (higher) → low = mid + 1
4. If "меньше" (lower) → high = mid - 1
5. Repeat until guessed

Each iteration halves the search space.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Золотая середина - Binary Search
Guess a number from 0 to 10^24 in 80 attempts
"""
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

from pwn import *

HOST = "62.173.140.174"
PORT = 10200

def solve():
    conn = remote(HOST, PORT)
    
    # Receive greeting
    data = conn.recvuntil("Введите число: ".encode('utf-8'))
    print(data.decode('utf-8', errors='ignore'))
    
    low = 0
    high = 1000000000000000000000000  # 10^24
    
    attempt = 0
    while low <= high:
        mid = (low + high) // 2
        attempt += 1
        
        print(f"[{attempt}] Trying: {mid}")
        conn.sendline(str(mid).encode())
        
        try:
            # Try to receive response
            response = conn.recvuntil("Введите число: ".encode('utf-8'), timeout=5)
            response_text = response.decode('utf-8', errors='ignore')
        except EOFError:
            # Connection closed - possibly guessed correctly!
            print(f"\n[!] Connection closed after attempt {mid}")
            try:
                remaining = conn.recv(timeout=2)
                print(f"Remaining data: {remaining.decode('utf-8', errors='ignore')}")
            except:
                pass
            break
        except:
            # Timeout - try to get what's available
            try:
                response = conn.recv(timeout=2)
                response_text = response.decode('utf-8', errors='ignore')
            except:
                response_text = ""
        
        print(f"    Response: {response_text[:300]}")
        
        if "CODEBY" in response_text or "flag" in response_text.lower():
            print(f"\n[+] FLAG FOUND!")
            print(response_text)
            break
        elif "больше" in response_text.lower():
            # The hidden number is higher
            low = mid + 1
        elif "меньше" in response_text.lower():
            # The hidden number is lower
            high = mid - 1
        elif "угадали" in response_text.lower() or "правильно" in response_text.lower() or "верно" in response_text.lower():
            print(f"\n[+] GUESSED! Number: {mid}")
            break
    
    conn.close()
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

if __name__ == "__main__":
    solve()

Running

 bash read-only • copy allowed Copy
python3 solve.py

The script finds the number in ~80 iterations and retrieves the flag.

Theory

Algorithm Complexity

Formula

For range [0, N], ⌈log₂(N+1)⌉ attempts are needed:

• N = 10^24
• log₂(10^24) ≈ 79.7
• 80 attempts needed

Alternative Solutions

Ternary Search

Divides into 3 parts instead of 2. Requires ~126 attempts for 10^24 — not suitable. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Golden Ratio Search

Divides in proportion φ ≈ 1.618. Less efficient than binary search for this task.

Conclusions

A classic algorithmic task. The name "Золотая середина" (Golden Middle) is a direct hint at binary search. The key to the solution is understanding that 80 attempts = log₂(10^24), making binary search the only viable algorithm. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍