Rating:
*For the full experience with images see the original blog post!*
**TL;DR:** parallelism was a reversing challenge using cooperative data shuffling with eight processes.
I solved it by analyzing the program and implementing its inverse in Python to reconstruct the flag.
I started out the CTF with this challenge because I just recently worked with MPI for my studies and was intrigued to find out what the author had prepared for us.
For those not familiar with MPI is short for message passing interface.
It defines protocols and methods for synchronization and data distribution over multiple processes working cooperatively on a problem in parallel.
The challenge uses a common implementation, OpenMPI, which supports C and uses the `mpirun` command we were given.
Thus, I expected a C program and quickly imported it into ghidra for analysis.
(If you're starting out with ghidra reversing, I can recommend [stacksmashing](https://www.youtube.com/@stacksmashing) for an introduction.)
Starting out, I clicked through the few functions to find the entry an main method with their common structure.
In the main method, the program initializes and MPI and gets the number of processes and the rank (the number identifying a process), which is the number of the current process.
We can see that the program always runs with 8 processes and uses three steps for probably checking the flag.
The first method I called scatter reads our input when run on the main process and expects a line with a 64-character string.
It then uses an array of 32 indices to shuffle this string by swapping the character at the given index with the one offset by 31.
Finally, it uses MPI_Scatter, a method for distributing a block of data equally between processes, to split the input in blocks of eight characters.
Next, the program implements 10.000 rounds of another shuffle.
Each round, each process sends the character at a given offset (`i % 8`) to the process before it, by the same offset to its own rank.
It then receives its character and waits for the operations to complete since the program uses the non-blocking method variants.
Then, it updates its buffer and synchronizes with the other processes at a barrier before starting the next round.
The last method of the program gathers the message parts from the processes which is the inverse of scatter.
Then, it compares the result to a string constant on the main process to determine whether it is the flag.
After looking at the program shortly, I decided I understood it enough to implement the reverse process in python (I'm pretty used to that now).
I managed to forget a zero for the round number but fixed that soon after to produce the following program:
```python
COMM_SIZE = 8
POS = [0] * 32
POS[0] = 0x1a
POS[1] = 0x20
POS[2] = 0xe
POS[3] = 0xb
POS[4] = 3
POS[5] = 1
POS[6] = 0x20
POS[7] = 0x18
POS[8] = 0xd
POS[9] = 0x11
POS[10] = 3
POS[11] = 0x11
POS[12] = 2
POS[13] = 0xd
POS[14] = 0x13
POS[15] = 6
POS[16] = 0xc
POS[17] = 0x16
POS[18] = 3
POS[19] = 0x1e
POS[20] = 10
POS[21] = 6
POS[22] = 8
POS[23] = 0x1a
POS[24] = 6
POS[25] = 0x16
POS[26] = 0xd
POS[27] = 1
POS[28] = 0x13
POS[29] = 1
POS[30] = 1
POS[31] = 0x1d
EXP = "m_ERpmfrNkekU4_4asI_Tra1e_4l_c4_GCDlryidS3{Ptsu9i}13Es4V73M4_ans"
BUFFER = [0]*8
# Inverse gather
for i in range(8):
BUFFER[i] = list(EXP[i*8:i*8+8])
# Inverse of parallel shuffle
for i in range(10000):
i = 10000 - i - 1
tmp = [0] * 8
for COMM_RANK in range(8):
offset = i % 8
dest = (COMM_SIZE + (COMM_RANK - i) % COMM_SIZE) % COMM_SIZE
tmp[COMM_RANK] = BUFFER[dest][offset]
# Splitting here to avoid loosing values
for COMM_RANK in range(8):
BUFFER[COMM_RANK][offset] = tmp[COMM_RANK]
# Inverse of scatter and start shuffle
input = []
for i in range(COMM_SIZE):
input += BUFFER[i]
for i in range(0x20):
i = 0x20 - i - 1
current = input[i]
input[i] = input[POS[i] + 31]
input[POS[i] + 31] = current
print("".join(input))
```
Of course, the challenge was pretty simple and I managed that primarily because people start with different challenges depending on their preferences.
I was happy nonetheless to be able to claim the first-blood for my team.
