Background

CrackMe Name: Evil CrackMe
CrackMe Author: victormeloasm

CrackMe Description:
Evil CrackMe: An Extreme challenge for the Crackers and Reverse Engineering community.
All Linux-x86-64 distros supported!!!!

Language: C++.
Difficulty: Extreme
No Packers or protections…
Run as: ./EvilCrackMe

Your mission:
🗝️ Find the correct Serial for the displayed Personal Access Key.

Behaviour:
“Access Granted” unlocks a hidden message.
“Access Denied” on incorrect input.

No fake checks, no decoys. Real logic. Real challenge.

Tools allowed:
→ Anything you want.
→ No patching for bypass. Understand it.

Goal:
Provide a valid Serial that triggers the correct message.
No further hints. The binary speaks for itself.
Release for study and challenge purposes. Respect the art. Build a KeyGen.

Execution

Attempting to execute this CrackMe in the state it was downloaded results in an error message about missing shared libraries. Being that this was developed for Linux, this is not an uncommon problem, but it is clear that the author was hoping to avoid it based on their description.

Loading the binary file into a Ghidra project reveals that the file is an AppImage, which is intended to run across all Linux distributions by packaging shared libaries. In this case, the author missed some libraries. To add the necessary libraries for successful execution, the file system for the AppImage must be extracted via ./EvilCrackMe --appimage-extract. The following files were then copied into the output directory:

• usr/lib/libfluidsynth.so.3
• usr/lib/libinstpatch-1.0.so.2
• usr/lib/libSDL2_mixer-2.0.so.0
• usr/lib/libsecp256k1.so.1
• usr/lib/libxmp.so.4

Lastly, the AppImage was rebuilt with the appimagetool:
./appimagetool-x86_64.AppImage squashfs-root/

Executing the corrected AppImage creates a window with two text boxes: a pre-popualted text box with a randomized value that can be copied by clicking a button, and a text box to enter a serial. After entering a serial, it can be validated by clicking a button. Outside of functionality, there’s a pleasant ASCII art dog and classical music playing.

Entering random input for a serial and clicking on the “validate” button displays a message indicating that the serial was incorrect.

Static Analysis

As discovered in the execution phase, this CrackMe is in the form of an AppImage. By extracting the AppImage, the executable ELF file that contains all user-written code is located in usr/bin/EvilCrackMe. This means the process of repacking the AppImage was ultimately unnecessary, but it never hurts to learn something new!

Loading the executable into a Ghidra project and opening the Code Browser reveals usual indicators of C++: mangled names beginning with _Z, the presence of a std namespace, and general patterns of try-catch in the disassembled code. However, in a pleasant turn of events, the symbols have not been stripped, making the static reverse engineering process significantly easier to begin.

Given the event-driven model of the CrackMe, function names beginning with on_ were queried in Ghidra’s Functions window. This matches 18 functions, but two specific functions are named in a way that ties them to callbacks for clicking each of the two buttons: on_validated_clicked() and on_copy_clicked().

Fortunately, these functions also do not seem to be obfuscated in anyway. The control flow is straight forward and nothing seems too outlandish at a glance

Key Derivation

As the name would suggest, on_validate_clicked() validates that the serial entered is correct. More specifically, the following steps are performed:

1. Get the string from the serial text box.
2. Convert the serial string to an unsigned long long.
3. Fill a 32-byte buffer with 0s using XMM0.
4. Copy the 8 bytes from the converted serial to the end of the same buffer.
5. Using the 32-byte buffer as a secret key, compute the public key for the Secp256k1 elliptic curve using a standardized library function.
6. Serialize the public key using a standardized library function.
7. Compare the serialized public key with the random value in the copyable text box.

This is not a great sign. The Secp256k1 elliptic curve is used in Bitcoin’s public key cryptography, which does not bode well for finding some known flaw. Furthermore, the key derivation is designed to be a one-way process; given a public key, you should not be able to derive a secret key.

Dynamic Analysis

To confirm that the code that has been statically reverse engineered is what actually executes and is being understood correctly, dynamic analysis was performed using GDB.

Note that secp256k1_ec_pubkey_create is called twice: once to generate the copyable text and again when the validation button is clicked. The idea is to set a breakpoint at this function, so that the secret key used to derive the public key can be written down and used after the fact as the serial.

This reveals the expected result of 24 zeros and a random 8 bytes being used as a secret key. In this case of the provided image, the secret key works out to be 0x5731558FAEF18B or 24542566526415243 in decimal. After deleting the breakpoint and continuing execution, the decimal number may be entered into the serial text box and validated. Sure enough, a new window pops up congratulating the user for “cracking the code.”

However, recall the challenge description. The final words are “Build a KeyGen.”
Since the copyable text is random each execution, the computed serial will not be valid the next time.

Key Generation

If the developer expects a key generator, then one must be possible… right?

Potential Targets

From a high-level, there are two potential weaknesses that may be a target:

1. Weak random number generation
2. Weak cryptographic secret

A quick look at the main function reveals that randomness is most likely seeded using std::random_device. That seed is later used in a Mersenne Twister engine to generate a batch of random numbers. There is some good news and some bad news to this. The good news is that Mersenne Twister is not cryptographically secure; it is in fact a “psuedo” random number generator. That is, given a known seed, the random numbers are also known. The bad news is that std::random_device is used to seed the engine, and is documented as being non-deterministic. In other words, the seed is unknown, thus the psuedo random numbers from Mersenne Twister are also unknown. If the current time were used as a seed, this would be the target.

This leaves a cryptographic weakness as the only viable target. One trait that stands out is that the first 24 bytes of the secret key will always be 0. In other words, there may be a partially-known-secret vulnerability that allows for the secret key to be fully recovered given the public key.

Pollard’s Kangaroo

After extensive searching online, I came across the Pollard’s Kangaroo algorithm. I won’t pretend to understand the everything about the formal proofs behind the algorithm, but for those who are mathematically inclined, a write up can be found here.

For everyone else, first note the the reason public key cryptography is secure in this case is that the discrete logarithm problem (DLP) is difficult to solve for. The general purpose of Pollard’s Kangaroo Algorithm is to perform an intelligent brute force attack when the secret key for the DLP is in a known range. By having “wild” kangaroos and “tame” kangaroos explore different paths of exponentiation, a wider field can be covered. When a wild kangaroo meets a tame kangaroo (i.e. a collision occurs), all numbers needed to solve the discrete logarithm problem are known. Of course, it’s still brute force, just in a more intelligent manner… and we won’t be using kangaroos, but threads.

Many attempts to code this from scratch and apply it to Secp256k1 were performed, but I ultimately used an open-source implementation that can be found on GitHub. Minor edits are necessary to get the code compiling, but it works well afterwards. To make this a proper key generator, a Python wrapper was used to read in a public key and parse the output and look for the private key.

import os
import subprocess
from tempfile import gettempdir
from sys import argv

KANGAROO = './Kangaroo/kangaroo'
TMP_FILE = os.path.join(gettempdir(), 'kangaroo.txt')

# Check usage
if len(argv) != 2:
    print(f'USAGE: {argv[0]} <public key>')
    exit()

# Create a file to define kangaroo search parameters
with open(TMP_FILE, 'w') as f:
    f.write('0\n')
    f.write('ffffffffffffff\n')
    f.write(f'{argv[1]}\n')

# Execute kangaroo search
output = subprocess.run([KANGAROO, TMP_FILE], capture_output=True, text=True)

# Extract the private key from the output
keyLine = output.stdout.split('\n')[-4].strip()
if('Priv' not in keyLine):
    print('Failed to get secret')
    exit()

# Print the solution
key = int(keyLine.split(' ')[-1], 16)
print(key)

On my system, a valid serial for a given public key will be generated in anywhere from 1-5 seconds using the CPU. This is significantly faster than a linear brute force search.