HPC - Brute-force password cracking

Moreno Marzolla moreno.marzolla@unibo.it

Last updated: 2022-10-10

DES cracker board developed in 1998 by the Electronic Frontier Foundation (EFF); this device can be used to brute-force a DES key. The original uploader was Matt Crypto at English Wikipedia. Later versions were uploaded by Ed g2s at en.wikipedia - CC BY 3.0 us, https://commons.wikimedia.org/w/index.php?curid=2437815
DES cracker board developed in 1998 by the Electronic Frontier Foundation (EFF); this device can be used to brute-force a DES key. The original uploader was Matt Crypto at English Wikipedia. Later versions were uploaded by Ed g2s at en.wikipedia - CC BY 3.0 us, https://commons.wikimedia.org/w/index.php?curid=2437815

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:

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-force

Run with:

    OMP_NUM_THREADS=2 ./omp-brute-force

Note: the execution time of the parallel program might change irregularly depending on the number \(P\) of OpenMP threads. Why?

Files

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