Rating:
*For the full experience with images see the original blog post! (It contains all stages.)*
For the first stage of the series, we get the challenge binary and text file, `data.txt`.
The text file contains the parameters that were passed to the binary and the encrypted output, likely of the first flag, in python-like format.
That binary is a dynamically-liked, stripped C binary in ELF 64-bit format - nothing out of the ordinary here.
Since I am currently trying that out, I loaded the file into Binary Ninja to decompile it and analyze the program logic.
The decompiler of your choice should produce a similar output though, the program is pretty simple.
main function
The main method handles IO for a custom cryptosystem, encrypting given numbers of blocks in an endless loop.
Per block, the program expects an 8-byte key, 16 bytes shift and finally 8 bytes plaintext for the encryption.
Additionally, it allocates 8 bytes per block for the ciphertext.
All these allocated arrays are passed to the encryption function and finally the function prints the result for each block in hex encoding.
While there is nothing special happening here, you may note that we got arrays of 16 values for all parameters and the ciphertext.
That's a bit confusing if you expect the exact same format but we can later make a simple, educated guess as to what we actually got.
do_encrypt function (func_13b9)
The parameters are passed through a function that forwards it to the real encryption `func_13b9`.
We will skip that one for now though and look at it later for stage 2.
The encryption is a simple block cipher working in 16 rounds, one for each shift we pass in.
That shift, a fix permutation and an operation I simply called `combine` (`func_1229`) are used to initialize the permutation table (called `combined_shifts` in the screenshot) for the round.
Now, I don't usually play a lot of crypto challenges, so I approached the encryption from a structural standpoint.
The `get_nibble` and `set_nibble` functions get and set nibbles (half-bytes) at a given index of an 8-byte array and work inverse to each other.
We can calculate the permutation for each round and generate an inverse lookup table from that.
If we simply want to implement the encryption logic in reverse, that leaves the `combine` function with parameters `a` and `b` in range `[0..16]`.
Luckily, the mapping is unique for a given output and parameter `b` so we can precalculate that to and reverse it for our decryption.
With this approach, I implemented the decryption, testing it against a python implementation of the encryption.
That way, I could quickly find the small bugs I introduced (like not actually initializing the `COMBINED_LOOKUP` array) to produce the following solve script:
```py
# Used as decrypt.py in other stages
keys = [
[2, 3, 3, 5, 3, 3, 1, 4, 1, 1, 3, 3, 1, 2, 2, 0],
[5, 1, 5, 4, 7, 3, 2, 0, 0, 1, 7, 1, 0, 6, 2, 7],
[2, 6, 6, 0, 5, 6, 5, 1, 6, 4, 7, 1, 1, 7, 3, 1],
[4, 3, 0, 5, 2, 0, 4, 2, 7, 7, 7, 1, 1, 1, 7, 5],
[1, 0, 0, 0, 4, 5, 3, 6, 3, 4, 7, 6, 4, 0, 1, 2],
[5, 5, 7, 1, 3, 1, 7, 6, 6, 3, 1, 1, 2, 4, 6, 7],
[2, 6, 2, 4, 1, 6, 0, 3, 7, 0, 6, 3, 0, 6, 7, 3],
]
shifts = [
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
[0, 1, 3, 5, 0, 1, 1, 0, 0, 1, 3, 5, 0, 1, 1, 0],
]
ciphertexts = [
[8, 12, 10, 7, 2, 6, 3, 2, 14, 1, 8, 4, 2, 12, 9, 15],
[10, 13, 5, 2, 13, 12, 11, 5, 14, 5, 3, 12, 4, 11, 0, 9],
[10, 4, 0, 3, 9, 13, 13, 2, 2, 1, 0, 4, 3, 15, 11, 12],
[7, 13, 1, 13, 9, 9, 9, 10, 9, 12, 3, 0, 1, 10, 7, 12],
[13, 3, 10, 6, 9, 9, 2, 13, 1, 10, 13, 0, 4, 2, 1, 0],
[6, 2, 2, 2, 15, 9, 12, 4, 7, 6, 2, 15, 1, 10, 14, 7],
[10, 12, 6, 14, 14, 2, 14, 12, 15, 0, 15, 0, 8, 9, 4, 2],
]
PERMUTATION = bytes.fromhex("090a08010e03070f0b0c02000405060d")
def to_nibbles(data: bytes) -> list[int]:
return [v for pos in range(len(data)) for v in [data[pos] >> 4, data[pos] & 0xF]]
def from_nibbles(nibbles: list[int]) -> bytes:
return bytes(
[
(nibbles[2 * pos] << 4 | nibbles[2 * pos + 1])
for pos in range(len(nibbles) // 2)
]
)
def combine(shift: int, other: int):
other_bit = other & 1
shift_up = shift >> 1
other_up = other >> 1
if (shift & 1) != 1:
out = other_bit + ((other_up + shift_up) * 2)
else:
diff = (((shift_up - other_up) * 2) & 0xE) - other_bit
out = diff + 1
return out
combine_matching = {}
for s in range(2**4):
for o in range(2**4):
com = combine(s, o) & 0xF
if (o, com) in combine_matching:
print("Cannot happen!")
exit(1)
else:
combine_matching[(o, com)] = s
def reverse_combine(other: int, out: int) -> int:
return combine_matching[(other, out)]
def set_nibble(buffer: list[int], idx: int, val: int):
buffer[idx] = val
return buffer
def get_nibble(buffer: list[int], idx: int) -> int:
# list of 16 nibbles, higher order values first
return buffer[idx]
def encrypt_block(
key_nibbles: list[int], shifts: list[int], plain_nibbles: list[int]
) -> list[int]:
out_nibbles = plain_nibbles.copy()
for s in shifts:
COMBINED = [0] * 16
for i in range(16):
COMBINED[PERMUTATION[i]] = combine(s, i)
tmp = [0] * 16
for k in range(16):
plain_nibble = get_nibble(out_nibbles, k)
set_nibble(tmp, COMBINED[k], plain_nibble)
for k1 in range(16):
key_nibble = get_nibble(key_nibbles, k1)
tmp_nibble = get_nibble(tmp, k1)
com = combine(tmp_nibble, key_nibble) & 0xF
set_nibble(tmp, k1, com)
pass
for k2 in range(16):
set_nibble(out_nibbles, k2, COMBINED[COMBINED[get_nibble(tmp, k2)]])
return out_nibbles
def decrypt_block(key_nibbles: list[int], shifts: list[int], cipher_nibbles: list[int]):
out_nibbles = cipher_nibbles.copy()
for s in reversed(shifts):
COMBINED = [0] * 16
for i in range(16):
COMBINED[PERMUTATION[i]] = combine(s, i)
COMBINED_LOOKUP = [0] * 16
for i in range(16):
COMBINED_LOOKUP[COMBINED[i]] = i
tmp = [0] * 16
for k2 in reversed(range(16)):
val = get_nibble(out_nibbles, k2)
set_nibble(tmp, k2, COMBINED_LOOKUP[COMBINED_LOOKUP[val]])
for k1 in reversed(range(16)):
key_nibble = get_nibble(key_nibbles, k1)
val = get_nibble(tmp, k1)
uncom = reverse_combine(key_nibble, val)
set_nibble(tmp, k1, uncom)
for k in reversed(range(16)):
val = get_nibble(tmp, COMBINED[k])
set_nibble(out_nibbles, k, val)
return out_nibbles
flag = b""
for block in range(len(keys)):
block_nibbles = decrypt_block(keys[block], shifts[block], ciphertexts[block])
block_bytes = bytes(
[
((block_nibbles[2 * pos] << 4) | block_nibbles[2 * pos + 1])
for pos in range(len(block_nibbles) // 2)
]
)
flag += block_bytes
print(flag)
```
After the competition, it was pretty interesting for me to see the perspective of crypto players on this challenge.
For example, they saw a simple Permutation-Substitution-Network and identified `func_1229` that I naively called `combine` as multiplication in D8 (the dihedral group, I think).
This mix of perspectives makes the challenge really cool, in my opinion.
