Last updated: 2022-10-10
The program omp-brute-force.c contains a 64-Byte encrypted message stored in the array enc[]. The message has been encrypted using the XOR cryptographic algorithm, which applies the “exclusive or” (xor) operator between a plaintext and the encryption key. The XOR algorithm is not secure but on some special cases (e.g., when the key has the same length of the plaintext, and the key contains truly random bytes); however, it is certainly “good enough” for this exercise.
XOR is a symmetric encryption algorithm, meaning that the same key must be used for encrypting and decrypting a message. Indeed, the exact same algorithm can be used to encrypt or decrypt a message, as shown below.
The program contains a function xorcrypt(in, out, n, key, keylen) that can be used to encrypt or decrypt a message with a given key. To encrypt a message, then in points to the plaintext and out points to a memory buffer that will contain the ciphertext. To decrypt a message, then in points to the ciphertext and out points to a memory buffer that will contain the plaintext.
The parameters are as follows:
in points to the source message. This buffer does not need to be zero-terminated since it may contain arbitrary bytes;
out points to a memory buffer of at least \(n\) Bytes (the same length of the source message), that must be allocated by the caller. At the end, this buffer contains the source message that has been encrypted/decrypted with the encryption key;
n is the length, in Bytes, of the source message;
key points to the encryption/decryption key. The key is interpreted as a sequence of arbitrary bytes, and therefore does not need to be zero-terminated
keylen is the length of the encryption/decryption key.
The XOR algorithm will happily decrypt any message with any provided key; of course, if the key is not correct, the decrypted message will not make any sense. For this exercise the plaintext is a zero-terminated ASCII string that can be printed with the printf() function whose first ten characters are "0123456789". This information can be used to check whether you “guessed” the right encryption key.
The encryption key that has been used in this program is a sequence of 8 ASCII numeric characters; therefore, the key is a string between "00000000" and "99999999". Write a program to brute-force the key using OpenMP. The program tries every key until a valid message is eventually found, i.e., a message that begins with "0123456789". At the end, the program must print the plaintext, which is a relevant quote from an old film.
Use an omp parallel construct (not parallel for) whose body contains code that assigns a suitable subset of the key space to each OpenMP thread. Recall from the lectures that the omp parallel construct applies to a structured block, that is, a block with a single entry and a single exit point. Therefore, the thread who finds the correct key can not exit from the block using return, break or goto (the compiler should raise a compile-time error if any of these constructs are used). However, we certainly do not want to wait until all keys have been explored to terminate the program. Therefore, you should devise a clean mechanism to terminate the computation as soon as the correct key has been found. You may not terminate the program with exit(), abort() or similar.
Compile with:
gcc -std=c99 -Wall -Wpedantic -fopenmp omp-brute-force.c -o omp-brute-forceRun with:
OMP_NUM_THREADS=2 ./omp-brute-forceNote: the execution time of the parallel program might change irregularly depending on the number \(P\) of OpenMP threads. Why?
You can use the wget command to easily transfer the files on the lab server:
wget https://www.moreno.marzolla.name/teaching/HPC/handouts/omp-brute-force.c