KKK
Overview
You are given a mysterious executable named KKK.exe that hides its secret behind a custom implementation of a well-known secret sharing scheme. The program lets you split a secret into multiple shares, reconstruct it, and finally decrypt the flag — but it doesn’t make things straightforward. Instead of directly handing you all the pieces, it only provides partial shares and uses a seeded random generator tied to system time to build the polynomial behind the scheme. Your task is to carefully study how the secret is generated, how the shares interact, and how the reconstruction logic works, then use that knowledge to uncover the original secret and access the hidden flag.
flag format: flag{}
Lab Details
Prerequisites & Requirements
- Shamir's Secret Sharing (SSS) Fundamentals:
- Understanding the mathematical concept of constructing a secret using polynomials.
- Knowing the role of the Constant Term (the secret) and Coefficients (random numbers generated based on a seed).
- Familiarity with Modular Arithmetic and the use of large prime numbers (2^31 - 1) to define a finite field.
- C++ & STL Reversing:
- Ability to recognize C++ Standard Template Library (STL) structures in assembly/decompiled code (
e.g., std::vector, std::mersenne_twister_engine, std::uniform_int_distribution). - Understanding how PRNGs (Pseudo-Random Number Generators) work and how seeding affects the output sequence.
- Ability to recognize C++ Standard Template Library (STL) structures in assembly/decompiled code (
- Cryptographic Weaknesses:
- Identifying Predictable Seeds : Recognizing that using time(0) / 3600 (system time in hours) makes the "random" numbers guessable via brute-force.
What will you learn?
- Algorithmic Reverse Engineering:
- Decompiling a custom implementation of SSS to identify the exact polynomial evaluation function.
- Translating decompiled C++ logic (like the evaluate_polynomial function) back into a working source code for offline analysis.
- Time-Based Seed Brute-Forcing:
- Developing an exploit strategy to recover generated coefficients by iterating through possible time-based seeds (system hours over the past few years).
- Correlating multiple partial shares (using x1x1 and x2x2) to validate the recovered secret (
i.e., finding the seed where both shares yield the same secret). - Mathematical Reconstruction:
- Learning how to isolate the secret term ( S ) from the share equation y=S+a1x+a2x2(modP)y=S+a1x+a2x2(modP) by regenerating the random tail (a1x+a2x2a1x+a2x2) and subtracting it from the known share y.
Tools
- IDA Pro:
- Used for Static Analysis . It decompiles the binary to reveal the C++ classes (KKK, KKK_Share), the polynomial logic, and the critical seed generation line (v4 / 3600).
- Detect It Easy (DiE):
- Used for initial Reconnaissance . It identifies the compiler and linker used, confirming it is a C++ executable.
- C++ Compiler (GCC/Clang/MSVC):
- Used to write and compile the Solver Script .
- Since the target uses specific C++ PRNG classes (std::mt19937), writing the solver in C++ ensures the random number generation behaves exactly the same as the target binary, which is crucial for the brute-force attack to work.