Bitwise Transformations
When you start solving reverse engineering challenges, especially crackmes or license checkers, you'll quickly notice that binaries almost never compare your input directly to a plaintext flag like if (input == "flag{secret}"). Instead, the program will take whatever you typed, process every character through a sequence of bitwise operations (such as XORing, shifting, or rotating bits), and then compare the final scrambled array against a list of pre-calculated target bytes stored in the executable. Learning how to spot these operations and reverse them step-by-step is one of the most fundamental skills in reverse engineering!
Bits, Bytes, and Core Operations
Before jumping into bitwise operations, let me make sure we're on the same page regarding how computers store data. At the lowest level, computers don't understand text or decimal numbers like 42 or 'A'. Everything in computer memory is stored as bits, where a bit is the smallest unit of data that can only be 0 (off) or 1 (on). A byte is a group of 8 bits side-by-side. For example, the ASCII character 'A' is stored as the decimal number 65, which in 8-bit binary is 01000001 and in hexadecimal (hex) is 0x41. Bitwise operations allow us to manipulate these 8 individual 1s and 0s directly inside CPU registers!
Let me show you the truth tables and behavior for the core bitwise operators you'll encounter in compiled C code and assembly:
XOR (Exclusive OR)
The XOR Operator (written as ^ in C and Python, or xor in assembly) compares two bits and returns 1 if the bits are different, and 0 if they are the same:
| Bit A | Bit B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
For example, XORing 0x57 (01010111) with 0x3A (00111010) yields 0x6D (01101101). What makes XOR so special for reverse engineers is that it is its own inverse: if you XOR a byte with a key, and then XOR the result with the exact same key again, you get your original byte back! (A ^ B) ^ B = A. This property makes XOR extremely popular in encryption routines and license checkers because the exact same operation can encrypt and decrypt data.
AND (&)
The bitwise AND operator (&) compares two bits and returns 1 only if both bits are 1:
| Bit A | Bit B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In reverse engineering, AND is frequently used as a mask to isolate specific bits or force numbers to stay within an 8-bit byte range (value & 0xFF).
OR (|)
The bitwise OR operator (|) compares two bits and returns 1 if at least one of the bits is 1:
| Bit A | Bit B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
OR is commonly used to combine bitflags or force specific bits to become 1.
NOT (~) and Bit Shifts
The bitwise NOT operator (~) simply flips every bit in a byte (~01010111 = 10101000). Finally, Bit Shifts move all bits in a byte to the left (<<) or right (>>). Left shifting by N positions (00000101 << 2 -> 00010100) is mathematically equivalent to multiplying by 2^N, while right shifting (>>) is equivalent to integer division by 2^N.
Rotations and Nibble Swaps
Standard shifts (<< and >>) drop any bits that fall off the end. However, there are two common variations where no information is lost at all:
A Circular Shift (bit rotation) works like a circular shift: instead of throwing away the bits that fall off the edge, it wraps them right around to the opposite side! Because no bits are discarded, rotations are 100% reversible. Rotate Left (ROL) by N bits moves bits left, wrapping top bits to the bottom, while Rotate Right (ROR) by N bits undoes a left rotation. In C, an 8-bit left rotation can be written as (val << n) | (val >> (8 - n)), and in assembly the CPU provides native instructions for this: rol and ror.
An 8-bit byte is made of two 4-bit halves called nibbles: the High Nibble (0xF0) and the Low Nibble (0x0F). Swapping nibbles means swapping the high and low halves, so the hex byte 0xA5 (1010 0101) becomes 0x5A (0101 1010). In C, this is written as ((x & 0x0F) << 4) | ((x & 0xF0) >> 4). Notice that swapping the nibbles of a byte twice returns the original value, meaning nibble swapping is also self-inverse: nibble_swap(nibble_swap(x)) = x.
Reversing a Transformation Chain
Now that we understand all the basic building blocks, let me show you how they get combined in real reverse engineering challenges! Imagine you decompile a target executable in IDA or Ghidra and discover a function that takes each byte x of your user input at index i and transforms it like this:
uint8_t transform(uint8_t x, int i) {
x ^= ((i * 0x37 + 0x13) & 0xFF); // Step 1: Index-dependent XOR
x = rol8(x, 3); // Step 2: Rotate left by 3 bits
x ^= 0xCA; // Step 3: XOR with constant 0xCA
x = (x + 0x25) & 0xFF; // Step 4: Modular addition of 0x25
return x;
}
After running every character through this function, the binary compares the resulting array against an expected hardcoded byte array in .rodata: EXPECTED = [0x65, 0xF7, 0x89, 0xBA, 0x1C, 0x97, 0x37, 0xF1, 0x22, 0xDD, 0xAF, 0x78, 0x93, 0x73, 0x1D, 0x56].
To recover the original license key, we must work backwards from Step 4 up to Step 1, applying the exact inverse operation at every step:
- Invert Step 4:
(x - 0x25) & 0xFF(Subtraction undoes Addition) - Invert Step 3:
x ^= 0xCA(XOR is its own inverse) - Invert Step 2:
ROR(x, 3)(Rotate Right undoes Rotate Left) - Invert Step 1:
x ^= ((i * 0x37 + 0x13) & 0xFF)(XOR is self-inverse)
Now we can implement the inverse function in Python and pass every expected byte through it:
#!/usr/bin/env python3
# Extract the hardcoded target bytes from IDA/Ghidra (.rodata)
EXPECTED = [
0x65, 0xF7, 0x89, 0xBA, 0x1C, 0x97, 0x37, 0xF1,
0x22, 0xDD, 0xAF, 0x78, 0x93, 0x73, 0x1D, 0x56
]
def inverse_transform(y: int, i: int) -> int:
x = (y - 0x25) & 0xFF # Undo Addition
x ^= 0xCA # Undo XOR 0xCA
x = ((x >> 3) | (x << 5)) & 0xFF # Undo ROL 3 -> ROR 3
x ^= ((i * 0x37 + 0x13) & 0xFF) # Undo index XOR
return x
# Run every byte through the inverse function
license_key = bytes([inverse_transform(EXPECTED[i], i) for i in range(len(EXPECTED))])
print("[+] Recovered License Key:", license_key.decode())
# Output: BITSH1FT-L1C3NS3
When you run this script, it instantly reconstructs the valid license key BITSH1FT-L1C3NS3! Remember: if an operation preserves information (XOR, rotations, nibble swaps, modular math), you can always copy the hardcoded target bytes from IDA or Ghidra and write a short Python script to undo each step in reverse order.