Homework 06: Hulk Smash

The goal of this homework assignment is to allow you to practice using functional programming to process data in Python. In this assignment, you will write a script that brute-force attacks a large collection of passwords using multiple processes. That is, we will use functional programming to construct a concurrent application, and then exploit this concurrency by using multiple CPU cores to execute the program in parallel.

For this assignment, record your scripts and any responses to the following activities in the in the homework06 folder of your assignments GitLab repository and push your work by 11:59 AM Saturday, March 7.

Activity 0: Preparation

Before starting this homework assignment, you should first perform a git pull to retrieve any changes in your remote GitLab repository:

$ cd path/to/repository                   # Go to assignments repository

$ git checkout master                     # Make sure we are in master branch

$ git pull --rebase                       # Get any remote changes not present locally

Next, create a new branch for this assignment:

$ git checkout -b homework06              # Create homework06 branch and check it out

Once this is done, download the Makefile and test scripts:

# Go to homework06 folder
$ cd homework06

# Download the Makefile
$ curl -LO https://gitlab.com/nd-cse-20289-sp20/cse-20289-sp20-assignments/raw/master/homework06/Makefile

# Add and commit Makefile
$ git add Makefile
$ git commit -m "homework06: Add Makefile"

# Download the test scripts
$ make test-scripts

Note, you do not need to add and commit the test scripts since the Makefile will automatically download them again whenever you run make.

You are now ready to work on the activities below.

Activity 1: Hulk (10 Points)

With various password leaks being announced on a weekly basis there has been a lot of discussion on password hygiene and password strength. There is even a website to check have i been pwned.

In all decent password accounting systems, the raw password is rarely stored. Instead a cryptographic hash such as MD5 or SHA1 is used to record a user's password digest or checksum and it is these hashes that are leaked to outsiders in these all too frequent breaches. Because these cryptographic hash functions are generally considered one-way functions, attackers cannot directly obtain the original input password even though they know the output of the cryptographic hash.

For instance, the MD5 digest of goirish is:

$ printf goirish | md5sum
c761cc3341c91238ba735b26874572a0 -

As you can see, the string c761cc3341c91238ba735b26874572a0 does not provide an attacker any clues about the original password goirish. To obtain the original text, attackers often employ various techniques such as brute-force cracking.

Task 1: hulk.py

For the first task, you are to create hulk.py, which is a script that uses brute-force to smash a set of MD5 hashes:

$ ./hulk.py -h
Usage: hulk.py [-a alphabet -c CORES -l LENGTH -p PREFIX -s HASHES]
    -a ALPHABET Alphabet to use in permutations
    -c CORES    CPU Cores to use
    -l LENGTH   Length of permutations
    -p PREFIX   Prefix for all permutations
    -s HASHES   Path of hashes file

Given an ALPHABET (default is abcdefghijklmnopqrstuvwxyz0123456789), hulk.py will compute the MD5 hash of every permutation of the ALPHABET for the specified LENGTH and check if it is in the set of HASHES. If a PREFIX is specified, then this should be inserted before each candidate permutation.

Examples

For instance, suppose we had a sample.hashes file that contained the following MD5 checksums:

0cc175b9c0f1b6a831c399e269772661
92eb5ffee6ae2fec3ad71c777531578f
4a8a08f09d37b73795649038408b5f33
900150983cd24fb0d6963f7d28e17f72

If we executed hulk.py with a LENGTH of 1, we should get the following result:

$ ./hulk.py -l 1 -s sample.hashes
a
b
c

That is, hulk.py determined that three of the hashes correspond to the passwords a, b, and c.

If we executed hulk.py with a LENGTH of 2 and a PREFIX of a, we should get the following result:

$ ./hulk.py -l 2 -s sample.hashes -p a
abc

That is, hulk.py determined that 1 of the hashes corresponds to the password abc. Note, we could have achieved the same results by executing:

$ ./hulk.py -l 3 -s sample.hashes
abc

The difference is the former searches each permutation in the form aXX where X is a letter from the ALPHABET due to the PREFIX of a, while the latter searches each permutation in the form XXX.

Finally, if CORES is greater than 1 and the LENGTH is greater than 1, the script will use the concurrent.futures module to brute-force passwords in parallel with the specified number of CORES:

$ ./hulk.py -l 1 -c 2 -s sample.hashes
a
b
c

Skeleton Code

To help you get started, the instructor has provided you with the following skeleton code:

# Download skeleton code
$ curl -LO https://gitlab.com/nd-cse-20289-sp20/cse-20289-sp20-assignments/raw/master/homework06/hulk.py

The skeleton code contains the following:

import concurrent.futures
import hashlib
import os
import string
import sys

# Constants

ALPHABET = string.ascii_lowercase + string.digits

# Functions

def usage(exit_code=0):
    progname = os.path.basename(sys.argv[0])
    print(f'''Usage: {progname} [-a ALPHABET -c CORES -l LENGTH -p PATH -s HASHES]
    -a ALPHABET Alphabet to use in permutations
    -c CORES    CPU Cores to use
    -l LENGTH   Length of permutations
    -p PREFIX   Prefix for all permutations
    -s HASHES   Path of hashes file''')
    sys.exit(exit_code)

def md5sum(s):
    ''' Compute md5 digest for given string. '''
    return ''

def permutations(length, alphabet=ALPHABET):
    ''' Recursively yield all permutations of the given length using the
    provided alphabet. '''
    yield None

def flatten(sequence):
    ''' Flatten sequence of iterators. '''
    yield None

def crack(hashes, length, alphabet=ALPHABET, prefix=''):
    ''' Return all password permutations of specified length that are in hashes
    by sequentially trying all permutations. '''
    return []

def cracker(arguments):
    ''' Call the crack function with the specified arguments '''
    return crack(*arguments)

def smash(hashes, length, alphabet=ALPHABET, prefix='', cores=1):
    ''' Return all password permutations of specified length that are in hashes
    by concurrently subsets of permutations concurrently.
    '''
    return []

def main():
    arguments   = sys.argv[1:]
    alphabet    = ALPHABET
    cores       = 1
    hashes_path = 'hashes.txt'
    length      = 1
    prefix      = ''

# Main Execution

if __name__ == '__main__':
    main()

You are to complete the sections marked TODO in order to complete the hulk.py script.

Task 2: Testing

To aid you in testing the hulk.py script, we are providing you with test_hulk.sh, which you can use as follows:

# Download Makefile
$ curl -LO https://gitlab.com/nd-cse-20289-sp20/cse-20289-sp20-assignments/raw/master/homework06/Makefile

# Download test script, hashes.txt, and run test
$ make

# Run test script manually
$ ./test_hulk.sh
Testing hulk.py ...
   Unit Tests                               ... 2.00 / 2.00
   Usage                                    ... Success
   Hulk LENGTH 1                            ... Success
   Hulk LENGTH 1 (ALPHABET: abc)            ... Success
   Hulk LENGTH 2                            ... Success
   Hulk LENGTH 2 (ALPHABET: uty)            ... Success
   Hulk LENGTH 3                            ... Success
   Hulk LENGTH 3 (ALPHABET: abc)            ... Success
   Hulk LENGTH 4                            ... Success
   Hulk LENGTH 4 (ALPHABET: uty)            ... Success
   Hulk LENGTH 2 (CORES: 2)                 ... Success
   Hulk LENGTH 3 (CORES: 2)                 ... Success
   Hulk LENGTH 4 (CORES: 2)                 ... Success
   Hulk LENGTH 1 (PREFIX: a)                ... Success
   Hulk LENGTH 1 (PREFIX: 1, CORES: 2)      ... Success
   Hulk LENGTH 2 (PREFIX: a)                ... Success
   Hulk LENGTH 2 (PREFIX: a, CORES: 2)      ... Success
   Hulk LENGTH 3 (PREFIX: a)                ... Success
   Hulk LENGTH 3 (PREFIX: a, CORES: 2)      ... Success

   Score 10.00

In addition to the test script, there is also hulk_test.py, which contains unit tests for most of the functions you need to implement. You can execute these tests manually as follows:

$ ./hulk_test.py -v
test_00_md5sum (__main__.HulkTestCase) ... ok
test_01_permutations (__main__.HulkTestCase) ... ok
test_02_flatten (__main__.HulkTestCase) ... ok
test_03_crack (__main__.HulkTestCase) ... ok
test_04_smash (__main__.HulkTestCase) ... ok

----------------------------------------------------------------------
Ran 5 tests in 0.199s

OK

This will test each of the five functions individually and thus allow you to build and test your program one function at a time.

Activity 2: Deadpool (1 Point)

Once you are confident that your program is correct, you are to use hulk.py to brute-force crack set of 11905 password hashes found at:

https://gitlab.com/nd-cse-20289-sp20/cse-20289-sp20-assignments/raw/master/homework06/hashes.txt

To keep track of who has cracked the most passwords, you can submit your set of discovered passwords to the deadpool:

$ cat PASSWORDS | curl --data-binary @- http://xavier.h4x0r.space:9111/NETID

Replace PASSWORDS with the name of the file with your passwords and NETID with your Notre Dame NetID:

# Generate passwords of length 1 and store them in passwords.txt
$ ./hulk.py -l 1 | tee -a passwords.txt
...

# Upload passwords.txt
$ cat passwords.txt | curl --data-binary @- http://xavier.h4x0r.space:9111/pbui
{"timestamp": 1488333215.967784, "passwords": 36}

For full credit, you must crack at least 7000 passwords. There are 11905 total hashes. Each password is no more than 8 characters long and only consists of lowercase letters and numeric digits.

$ ./hulk.py -l 6 -c 2  # Use 2 processes

$ lscpu

Activity 3: Quiz (1 Point)

Once you have completed all the activities above, you are to complete the following reflection quiz:

As with Reading 01, you will need to store your answers in a homework06/answers.json file. You can use the form above to generate the contents of this file, or you can write the JSON by hand.

To test your quiz, you can use the test_quiz.py script:

$ ./test_quiz.py
Submitting homework06 quiz ...
      Q01 0.50
      Q02 0.30
      Q03 0.20

    Score 1.00

Guru Point (2 Points)

This week there are two different opportunities for extra credit. You may choose to do one, both, or none of them.

Hash Cat

As can be seen, cracking passwords using brute-force is extremely slow, especially on CPUs. For extra credit, you are to download and use the hashcat program on your own computer:

hashcat is the world's fastest and most advanced password recovery utility, supporting five unique modes of attack for over 200 highly-optimized hashing algorithms. hashcat currently supports CPUs, GPUs, and other hardware accelerators on Linux, Windows, and macOS, and has facilities to help enable distributed password cracking.

The secret to hashcat's speed is that it can take advantage of your GPU (aka. your video card), which turns out to be a massively parallel computing system (basically a commodity supercomputer). You will learn more about the GPU's power in your Computer Architecture class, but for this extra credit, all you need to do is take advantage of it by using hashcat.

Once you have downloaded hashcat to your own computer and the password hashes file for this assignment, you should use hashcat to crack passwords of length 7 and 8:

# Brute-force MD5 hashed passwords of length 7 with lowercase letters and digits
$ hashcat -a 3 -m 0 -1 ?l?d -o passwords.7 hashes.txt ?1?1?1?1?1?1?1

# Brute-force MD5 hashed passwords of length 8 with lowercase letters and digits
$ hashcat -a 3 -m 0 -1 ?l?d -o passwords.8 hashes.txt ?1?1?1?1?1?1?1?1

Note: for macOS users, you may wish to install hashcat via Homebrew.

After executing these commands, the cracked passwords should be in the passwords.7 and passwords.8 files. You will need to use either Python or shell to extract the passwords and append them to the list of passwords of lengths 1 - 6 you found using hulk.py.

SSH Keys

Passwords are great, but what would even be better is not having to enter your password everytime you do a git pull or git push!

For extra credit, you are to setup SSH Keys and configure your GitLab account to utilize them. The following are resources on how to set this up:

• How to create your SSH Keys
• Generating an SSH Key
• How To Set Up SSH Keys

Basically, with SSH Keys properly configured, you can do things such as push and pull to GitLab without having to enter your password everytime and login to remote Unix machines without a password. This is handy for automating tasks where no human interaction is desirable.

Once you setup your SSH Keys, you will need to change your remote URL.

Submission

To submit your assignment, please commit your work to the homework06 folder of your homework06 branch in your assignments GitLab repository. Your homework06 folder should only contain the following files:

• Makefile
• README.md
• answers.json
• hulk.py
• passwords.txt

The passwords.txt should contain a list of all all the passwords you found from the password hashes collection.

#--------------------------------------------------
# BE SURE TO DO THE PREPARATION STEPS IN ACTIVITY 0
#--------------------------------------------------

$ cd homework06                           # Go to Homework 05 directory
...
$ git add Makefile                        # Mark changes for commit
$ git add hulk.py                         # Mark changes for commit
$ git commit -m "homework06: Activity 1"  # Record changes
...
$ git add passwords.txt                   # Mark changes for commit
$ git commit -m "homework06: Activity 2"  # Record changes
...
$ git add answers.json                    # Mark changes for commit
$ git commit -m "homework06: Activity 3"  # Record changes
...
$ git push -u origin homework06           # Push branch to GitLab