Math is often tricky and hard, which is why we make computers do math for us. That being said, it's important to know how to solve the math when the bidding is essential.
This is a reverse-engineering challenge designed to analyze what a C program does. In this challenge, you will reverse the encryption process that changes an input text into an output text.
Main Function
Start by looking at the C code given for the challenge. Notice that there are two functions. In the C programming language, main is the program’s entry-point function where execution starts.
int main() {
char input[64];
printf("Enter the secret sequence: ");
fgets(input, sizeof(input), stdin);
check_flag(input);
return 0;
}
Open the drop-down arrows for more explanations on what each line does!
‣
char input[64];
A buffer, called input, is declared. It can contain 64 bytes. A character is equal to 1 byte (character = letter, digit, or symbol).
This means that we can put in 64 letters/numbers, right? Not quite.
In C, strings end in something called a null terminator. This null terminator, which is \0 , tells the program that this is the end of input. This effectively means that we actually only have space in our buffer to hold 63 characters, as the 64th will contain a null terminator.
‣
printf("Enter the secret sequence: ");
This line asks the user for input, and prints out the statement to the terminal.
‣
fgets(input, sizeof(input), stdin);
This line reads the first 63 characters (size of the input buffer minus 1) of stdin, or standard input, that a player enters. Player input is stored in the input buffer.
If the input terminates earlier, using an EOF or a newline character (\n), then fgets (the input-reading function) stops reading. When you hit ‘Enter' on your keyboard, you’re typing in a \n character to the program..
‣
check_flag(input);
The check_flag function receives a pointer to the input buffer. The function can now read from and interact with what was entered by the player. Think of the pointer as the address of the memory where the input is stored.
‣
return 0;
Ends the program and communicates that it ran successfully. If an issue were to occur, an error code (something other than ‘0’) would be returned.
check_flag
Now, let’s look at the check_flag function. Every other step of the main function falls within the C standard library, and nothing has been modified to what we can see. The check_flag function is where a majority of the work is performed.
Briefly view the function as shown below:
Use the dropdown toggles to understand what a section of code does to a deeper degree:
‣
const char target_string[] = "EOC-ZBMH-5761";
This is where we start, and the string that our input must end up looking like. However, our input goes through a bunch of mathematical transformation first before it can look like this, and that is what the rest of our code does.
One variable is named letter_r_xor_key , which is interesting because our string EOC-ZBMH-5761 doesn’t contain any r characters. 0x1A doesn’t correspond to the letter r, so this is also curious.
Another buffer is created that’s equal to the length of target_string (which is EOC-ZBMH-5761 or 13 bytes), plus 1. This means transformed_text contains 14 bytes (14= 13+1).
A memset operation to converts everything in that buffer to 0.
This is a for-loop. i starts at 0, and then i will increase before going back into the loop. This is known as a pre-increment. This loop will happen as long as i is less than the length of the target_string variable. Functionally, this means that this loop walks over each position in our target_string, starting from 0 and ending with 12.
‣
if (i == 3 || i == 8) {
if (input[i] == '-') {
transformed_text[i] = '-';
continue;
}
}
If we are at the 3rd or 8th iteration, and the input is a - character, then we just keep it in our transformed_text buffer. This is another hint telling us that - characters should exist here, and this lines up with what we know about flag format (SKY-CCCC-DDDD ).
‣
if ((i >= 0 && i <= 2) || (i >= 4 && i <= 6)) {
This is the most complex part. Come back to this at the end to get a clearer picture of the entire program before diving in.
This part of the loop only occurs when we are dealing with the first 3 letters, or the next 3 letters. It takes the input characters and puts them in the current_letter_block buffer.
When the block size reaches 3, matrix multiplication is applied, and each letter is converted to the corresponding 0-25 value with (current_letter_block[col] - 'A') . After each row’s result is calculated, it is wrapped with a modulo 26 operation and shifted by a capital A so that it is shifted to a valid uppercase character.
This block will be discussed more below.
‣
else if (i == 7)transformed_text[i] = input[i] ^ letter_r_xor_key;
Here, our input character has to be XORed with the character corresponding to hex code 0x1A to get R.
‣
else if (i >= 9 && i <= 12) {transformed_text[i] = input[i] ^ digit_xor_keys[digit_index];digit_index++;
This else if block deals with characters 9 through 12 in the index, which are explicitly numbers. The process for transforming them involves XORing the input with the characters in the digit_xor_keys[] array .
Guide
The process of reverse-engineering involves taking the long, complicated, and extensive final form of an engineered piece of work (such as the code above), and breaking it apart in detail to understand how it was created. The next part is understanding how to perform the opposite of the processes used in the original code.
Questions 1-5 for this challenge can be solved by analyzing the code. Question 3 may require some outside research, but all of the answers are found in the code provided for this challenge.
Question 6 is essentially asking for the input (or the correct flag) that will return the ‘Correct…’ statement. This will take a bit more work because it will involve performing the opposite of the processes used in the code.
Solving for the Flag
How do we figure out the flag from this code? The input submitted to the program initially becomes transformed_text. At the end,transformed_text is compared to target_string (EOC-ZBMH-5761) to see that they match. Therefore, we need to use target_string and functions performed to transformed_text to get the input that will cause the function to return “Correct”
After analyzing the code, there are a few obvious places where these elements of the flag are modified.
Solving else if (i == 7)
At this portion, the code uses the 8th character in transformed_text and applies the letter_r_xor_key (which is 0x1A ). From the looking at target_string , it can be concluded that this transformation will result in the letter ‘H’.
What character will result in ‘H’ when XORed with 0x1A?
Cyberchef can show that H XOR 0x1A = R. Therefore, the input must be ‘R ’ to get ‘H’ in the final target_string.
Solving else if (i >= 9 && i <= 12)
From the last else if block, we can determine what characters 9-12 of the index should be. Recall that digit_xor_keys[] = {0x1, 0x2, 0x3, 0x4}; and the last four digits of the target_string are 5761.
Perform the functions as follows: 5 XOR 0x1, 7 XOR 0x2, 6 XOR 0x3, and 1 XOR 0x4 . You can use cyberchef to perform the XOR. The result will be 4555.
Solving for *
So far, we have ***-***R-4555 as our flag (where * corresponds to an unknown value).
Let’s go back to the ‘complicated’ portion of the code. This portion is specifically for transforming the first 3 characters of the flag and the next three characters after the first hyphen (basically, the characters marked with * that we have left to solve for).
This portion of the code is where the transform_matrix matrix is being used and block_size is utilized. After this point, all variables and arrays in the code are accounted for.
This portion of the code is performing a Hill Cipher transform on 2 separate blocks of 3 characters. Those 2 blocks are EOC (index 0, 1, and 2 of target_string) and ZBM (index 4, 5, and 6).
To decrypt a Hill Cipher, and basically ‘reverse’ the multiplication done that produced the ciphertext, the ciphertext (in this case, portions of target_string) will need to be multiplied by the inverse of the key matrix (or mod 26).
After completing this operation, we will have the entire flag string. Anything else in the code performs comparisons to make sure the transformation happened correctly, and adds a \0 null terminator character in order to end the string.
Shown in the dropdown menus below is the process that occurs on EOC. Solving for ZBM will be done is a similar process but will not be shown for brevity.
‣
Overview of the math computation in the code
We loop through the loop until block_char_index++; has incremented block_char_index to equal block_size (block_size=3, so this would result in three loops).
When the block is filled to 3, if (block_char_index == block_size) will be ‘true’, and then the operations can proceed.
The letters, EOC , are converted to numbers, using (current_letter_block[col] - 'A', which maps them to E = 4, O = 14, and C = 2.
So, y = [4, 14, 2]
The row loop computes one output letter at a time, and uses the transform_matrix to calculate this. If you recall, it was defined as
Then, each y is reduced to mod 26, and converted back to letters + 'A'
When done with EOC, the reverse function becomes x = A_inv * y mod 26 , where A_inv is the inverse modular matrix.
This can be found using math, or this calculator. Python can also be utilized using sympy library's inv_mod(). Below are a few dropdowns that show a way to use Python to solve.
‣
Creating the Inverse Modular Matrix (also shown with Python)
To create the inverse modular matrix, you can use a website similar to this one an skip ahead to using the inverse modular matrix to solve for EOC.
If you’d like to better understand how this matrix is created, or calculate it using Python, some of the calculations and concepts are demonstrated below.
Start with the matrix given below, and compute the inverse modular matrix as follows:
214319572
Find the determinant:
The formula for the determinant of a matrix can be done with the Laplace expansion, or (ONLY in the case of 3x3 matrices) Sarrus’ Rule. Sarrus’ Rule is shown here:
214319572∣∣∣214319
To get the determinant, you add the products of three downward diagonals and subtract the sum of the products of three upward diagonals.
Notice that 7, 14, and 21 don’t get clamped by our mod 26. Imagine there is an invisible mod 26 there, but we just don’t have it because a number under 26 modulo-ed by 26 is just that number.
The extended Euclidean algorithm could also be used to find the inverse determinant, but the inverse of the determinant is 15.
Next, this inverse (15) will be used to cofactor the matrix and then create the adjugate matrix. Last, the adjugate needs to be multiplied by the modular inverse of the determinant.
This can be done with the following python code:
‣
Using the Inverse Modular Matrix to solve for EOC (also shown with Python)
Last, convert the resulting number back to alphabet characters:
18 -> S
10 -> K
24 -> Y
This can be done with the following python code:
Hill Cipher Decode
Assuming you determine this function in the code is using a Hill Cipher, you would not need to complete the math by hand or using Python. You can use a hill cipher decoder and pass in the matrix.
Functionally, a Hill Cipher is a normal cipher, except that the key for the encryption is represented as a matrix. This can be any matrix with the same numbers of rows and columns.
void check_flag(const char *input) {
const char target_string[] = "EOC-ZBMH-5761";
int transform_matrix[3][3] = {
{2, 3, 5},
{1, 1, 7},
{4, 9, 2}
};
int block_size = 3;
char letter_r_xor_key = 0x1A;
char digit_xor_keys[] = {0x1, 0x2, 0x3, 0x4};
char transformed_text[strlen(target_string) + 1];
memset(transformed_text, 0, sizeof(transformed_text));
char current_letter_block[block_size];
int block_char_index = 0;
int letter_block_count = 0;
int digit_index = 0;
for (int i = 0; i < strlen(target_string); ++i) {
if (i == 3 || i == 8) {
if (input[i] == '-') {
transformed_text[i] = '-';
continue;
}
}
if ((i >= 0 && i <= 2) || (i >= 4 && i <= 6)) {
current_letter_block[block_char_index] = input[i];
block_char_index++;
if (block_char_index == block_size) {
int block_start_index = (letter_block_count == 0) ? 0 : 4;
for (int row = 0; row < block_size; ++row) {
int result = 0;
for (int col = 0; col < block_size; ++col)
result += transform_matrix[row][col] * (current_letter_block[col] - 'A');
transformed_text[block_start_index + row] = (char)(((result % 26) + 26) % 26 + 'A');
}
block_char_index = 0;
letter_block_count++;
}
}
else if (i == 7)
transformed_text[i] = input[i] ^ letter_r_xor_key;
else if (i >= 9 && i <= 12) {
transformed_text[i] = input[i] ^ digit_xor_keys[digit_index];
digit_index++;
}
else {
// :D
}
}
transformed_text[strlen(target_string)] = '\0';
if (strcmp(transformed_text, target_string) == 0) {
printf("[+] Correct! You know math!\n");
printf("[+] Flag: %s\n", input);
} else
printf("[-] Incorrect input. Try again.\n");
}
if ((i >= 0 && i <= 2) || (i >= 4 && i <= 6)) {
current_letter_block[block_char_index] = input[i];
block_char_index++;
if (block_char_index == block_size) {
int block_start_index = (letter_block_count == 0) ? 0 : 4;
for (int row = 0; row < block_size; ++row) {
int result = 0;
for (int col = 0; col < block_size; ++col)
result += transform_matrix[row][col] * (current_letter_block[col] - 'A');
transformed_text[block_start_index + row] = (char)(((result % 26) + 26) % 26 + 'A');
}
block_char_index = 0;
letter_block_count++;
}
}
def mat_inv_mod(matrix, m):
A = np.array(matrix)
A_int = A.astype(int) # Use integer type for determinant
det = int(round(np.linalg.det(A_int)))
det_inv = modInverse(det, m)
adjugate = np.zeros_like(A, dtype=int)
rows, cols = A.shape
for i in range(rows):
for j in range(cols):
minor = np.delete(np.delete(A_int, i, axis=0), j, axis=1)
cofactor = ((-1)**(i + j)) * int(round(np.linalg.det(minor)))
adjugate[j, i] = cofactor
inverse = (det_inv * (adjugate % m)) % m
return inverse.tolist()
