Assignment: Distributed password cracking - the brute force way

This interdisciplinary project covers the following subjects and key points from the curriculum:

SYM
  • The student can apply experiments systematically to investigate the technological possibilities and limitations
  • Reviews
  • Architectures
  • Project management
  • Quality management
  • Testing
SODP
  • Unit testing
  • Exception handling
  • Program documentation
  • Logging
  • Concurrency: Task etc.
  • Software architecture
CODS
  • Network protocols
  • Network programming with sockets
  • Web services

In this assignment you are going to program a distributed application to crack passwords! Using more cores or computers should make the program run faster.

The goal is to get a large speed-up: That is to see how much faster you can make the program run, compared to the centralized (non-distributed) version of the program.

The general idea is that you have a password file with (username, encrypted password). The encryption algorithm has no known decryption algorithm.

You also have a large dictionary (list of words) that users might have used as passwords. You must encrypt all the words in the dictionary and compare the encrypted word to the encrypted passwords from the password file. If you have a match, you have found a password, now in clear text.

Some users might not use an exact word from the dictionary, but may have made some kind of change to the words (transformations), like

Here are given some examples of the changes from above:

As can be seen from this list http://splashdata.com/press/PR121023.htm many users chose passwords which are more or less takes from a dictionary.

In this assignment the general idea must be implemented using a number of distributed architectures.

Each architecture can be implemented using threads (useful if the computer has more than one CPU) and by using processes with socket for communication.

Master/slave (data parallelism)

The master holds the dictionary. Each slave gets a part of the dictionary.

Pipeline (task parallelism)

  1. First task in pipeline reads from the dictionary file and sends the words on to the next process.
  2. Next task make a list of all changes of the dictionary word (the different transformations)
  3. Next task encrypts the all words.
  4. Next task compares the encrypted word to the encrypted passwords from the password file.
  5. Last task writes the cracked user's username + password to the screen (or to a file)

A number of different architectures

  1. Master / Slave where the master and the slaves are running in separated thread. They can use shared memory.
  2. Master / Slave where the master and the slaves are running in separated processes, e.g. on different computers communicating over TCP sockets.
    This comes in two variations:
    1. The master is the server. The slaves are clients.
    2. The master is a client. The slaves are servers.
  3. Pipeline where each "process" is running in a separate thread. The share memory
  4. Master / Slave with web services.
  •   Single computer / Threads Multi-computer / Sockets Web services
    Pipeline   Not available Not available
    Master / slaves  
    1. The master is the server.
      The slaves are clients.
    2. The master is a client.
      The slaves are servers.
    		  

    Group work

    The assignment must be done in groups. Teachers have formed the groups and review groups.

    Each group must make an experiment of one main architecture. Teachers have decided which architecture each group have to experimented with. Depending on the groups motivation and time they can chose a supplementary architecture to implement after the main architecture has been finished.

    The groups are as follow:

    Group Group members Main architecture
    Group A Ionut Vieru, Kevin Adeya, Nikola Conkova, Prawesh Bogati, Veselin Ivanov Architecture 3: Pipeline, threads
    Group B Bjørn Pedersen, Bogdan Dorojan, Constantino Marullo, Daniela Popescu, Xinyu Tao Architecture 1: Master/slaves, threads
    Group C Jacek Kizinski, Lukas Cech, Mads Quist, Mihai Constantin, Oliver Riborg Architecture 2a: Master/slaves, sockets. Master is the server.
    Group D Filip Germanek, Frederik Borgbjerg, Ivan Serafimov, Mass Sallah, Roshan Shresta Architecture 2b: Master/slaves, sockets. Master is the client.
    Group E Aurimas Lapinskas, Ciprian Trifescu, Morten Olsen, Philipo Molel, Zsofia Toth Architecture 4: Master/slaves, web services.

    Each group are going to present their solution and reflection over the experiment for the whole class, whereby we can have a general discussion of the four different architectures.

    Review groups

    Technical requirements

    Experiment

    In this assignment you will experiment with different architectures to solve a known problem (cracking passwords, the brute force way).

    Your assignment must be implemented and described according to "Scientific Investigation" http://www2.lv.psu.edu/jxm57/irp/sci_inv1.html

    1. The question
    2. The hypothesis
    3. The experiment

    Requirements to the experiment

    1. You must produce a project plan including baselines for the two week project period.
    2. The program must be documented using Doxygen
    3. You must develop and describe a test-plan
    4. The program must be tested using MSTest. Check that your tests have a good Code Coverage
    5. The interfaces between the different processes (what do you sent over the socket)
      OR threads (which parameters do you have) must be documented
    6. The experiment must include time metrics, and at least one other metric.
    7. The experiment must include descriptions of quality factors like performance, testability, correctness, etc. - and descriptions of how you want to measure the quality
    8. The Experiment must document the review (see schedule)
    9. You must compare your solution with the one handed out (see getting started)

    The written report is expected to be around 20 pages pr. group.

    Assignment schedule

    Rooms

    Getting started

    To get you started you must download a centralized version of the password cracker

    Run it - and see how much time it uses running on your computer(s).

    Dictionaries

    The Visual Studio project includes a dictionary.

    You are allowed to try other dictionaries.

    Password file

    The Visual Studio project includes a password file. Each line in the file contains username + encrypted password.

    The encrypted passwords are encoded using BASE64 encoding to make them into text strings storeable in a text file.