In this lab, you will learn the following topics and practice C programming skills.

1. Using signal handlers, signal() and sigaction()
2. Scheduling alarm signals with alarm()
3. Using siginfo_t when handling SIGCHLD

Run the following command

~aviv/bin/ic221-up

Change into the lab directory

cd ~/ic221/lab/09

All the material you need to complete the lab can be found in the lab directory. All material you will submit, you should place within the lab directory. Throughout this lab, we refer to the lab directory, which you should interpret as the above path.

For this lab, all ubmission should be placed in the following folder:

~/ic221/lab/09

You are not required to provide your own Makefiles for this lab. One is provided for you.

In the top level of the lab directory, you will find a README file. You must fill out the README file with your name and alpha. Please include a short summary of each of the tasks and any other information you want to provide to the instructor.

You are provided a test script which prints pass/fail information for a set of tests for your programs. Note that passing all the tests does not mean you will receive a perfect score: other tests will be performed on your submission. To run the test script, execute test.sh from the lab directory.

./test.sh

You can comment out individual tests while working on different parts of the lab. Open up the test script and place comments at the bottom where appropriate.

In the collision directory, you'll find a program called hash (which you can compile by typing make). This program is good for testing, and will hash a password provided on the command line.

$ ./hash navy
57c5f2

The result is the hash, which is a sequence in hexadecimal with 6 hex digits, or 3 bytes. (Two hex digits can represent one byte of information.) Assuming you only had the hash, the challenge is finding the password, e.g., "navy" or another 4 letter word that hashes to the same value, a so called collision. The basic way to do this is to search all possible passwords until you find a collision where the hashes match.

This is how we crack passwords. When passwords are leaked, usually just the hashes are leaked, and so advanced software, running with many processes, check the hashes against millions of likely passwords. If you're interested in password cracking, check out tools like John the Ripper and HashCat. In this lab, we'll do something a quite a lot simpler than those routines, but based on the same principles.

The routine for cracking a hash involves finding all the colliding ASCII printable passwords that hash to the same value. Even with a small password and small hash, this can take a long time to do, so we are going to parallize the problem using a set of child/worker processes.

The parent process will act as the coordinator, distributing "work" to each child process, and the child process will communicate back with the parent using signals to report on the progress of that work.

To divide up the work, each child will be assigned a first letter of a password to start with. The child will then exhaust the space of possible passwords that begin with that letter. For example, a child may be assigned "a" and another "b," and each will search all passwords that begin with "a" and "b" respectively.

If a child finds a match, it will send a signal to the parent, in the form of a SIGUSR1 signal, indicating that a match was found. It will also write the matched password to a pipe to be read by the parent.

Once the child/worker has finished searching the space of passwords that begin with its assigned first letter, it will stop by raising SIGSTOP signal which will generate a SIGCHLD signal to the parent, notifying the parent that the child has completed its work and more work can be sent to that child.

There will be two forms of inter-process communication: pipes and signals.

pipes: Each child will share a pipe with the parent. The pipe will be used bi-directionally.

• Parent -> Child: assigning work to the child : Parents will write to the pipe to communicate work for the child, e.g., the start letter for the child's hash collision search.
• Child -> Parent : colliding passwords : In the other direction, the children will write to the pipe to communicate passwords that match the hash.

signals: The second form of inter-process communication will be in the form of signals. There are four signals that will be used.

• SIGUSR1: Child->Parent : The child will send a SIGUSR1 signal to its parent when it finds a match. This indicates to the parent that a collisions was found and the password was written to the pipe. The parent can then read the colliding password from the pipe and print it to the screen.
• SIGSTOP: raised -> Child : When the child has completed its assigned work, that is searched all passwords that start with the assigned letter, the child will send itself (via raise) a SIGSTOP signal which will stop the child. The fact that it stops will be noticed via the parent's call to waitpid() to return.
• SIGCONT: Parent -> Child: After a successful return from waitpid(), the parent can assign more work to stopped child by writing to the shared pipe, but the parent must also continue that child from its stopped state. This is accomplished by sending a SIGCONT signal to the child. Awoke, the child reads from the shared pipe to get the next start letter to do hash matching.
• SIGKILL: Parent -> Child: If there is no more work for the child, the parent should kill the child via SIGKILL. This is useful because once there are no more children, waitpid() would return an error value, which also indicates that the search is complete. (BIG HINT!)

Unfortunately, the signal() system call is not powerful enough to make this all work because you will need to know which of the children's state change generated a SIGCHLD. To gain that information, you have to use the more powerful sigaction() system call to establish the handler. Read the manual page carefully for this, and you should consider using the SA_INFO and SA_RESTART flags to make this work. For example:

struct sigaction act;
 act.sa_sigaction = handler; //the handler to use for the signal
 act.sa_flags = SA_RESTART | SA_SIGINFO; //the flags
 sigaction(SIGUSR1, &act, NULL); //establish a signal handler for SIGUSR1

The handler function for the parent can be quite simple because the SIGUSR1 signal is only delivered when the child finds a hash collision. The only thing for the parent to do is to (a) determine which child sent the signal and (b) read from the appropriate pipe to print the password.

Unlike signal(), the prototype of the function expected for the signal handler by sigaction (if using the sa_sigaction option) is slight different.

void handler(int signum, siginfo_t * info, void * context);

The signum is the signal that was delivered such that the handler was invoked. The info is a pointer to a structure that contains information about how the signal was delivered, including which process sent the signal, info->si_pid. The context is used to manage the asynchronous execution stack, but you can ignore this variable

When the child has exhausted the search space for the first letter, it will raise(SIGSTOP) which will change the state of the child process. To identify this condition, the parent will call waitpid() to monitor the state of the children. However, by default, stopped state changes are not cause for wait to return, but we can use the WUNTRACED flag to enable this functionality.

cpid = waitpid(0,&status,WUNTRACED); // returns the pid of a child if
                                     // it was terminated OR stopped

Additionally, you will need to check the exist status to ensure that the state change of the child occurred due to being stopped and not because the parent killed it.

WIFSTOPPED(status) //returns true state change of child was STOPPED

As described above, if it was stopped, the child finished searching all the passwords with the assigned first letter. The parent should then communicate the next letter to search and continue the child. However, if there are no more start letters, the parent should kill the child with SIGKILL.

aviv@saddleback: collisions $ ./hash navy
57c5f2
aviv@saddleback: collisions $ ./collide $(./hash navy)
![X{
K==$
RjwY
navy
xp>\
ygTn
aviv@saddleback: collisions $ ./hash "RjwY"
57c5f2

aviv@saddleback: collisions $ time ./collide $(./hash navy) > /dev/null

real  0m7.763s
user  0m30.656s
sys   0m0.000s