• View
• Edit
• History
• Print

HW3

CS 642: Computer Security - Homework Three

This homework assignment covers topics in cryptography. You may work with a partner. There are two parts labeled A and B and one extra credit part described at the end of this document.

Downloads: CS642_HW3.zip

It is due Thursday, April 11th at 9 pm

Part A: Password Cracking

A colleague has built a password hashing mechanism. It applies SHA-256 to a string of the form username,password,salt where salt is a randomly chosen value. For example, the stored value for username user and password 12345 and salt 999999 is c50603be4fedef7a260ef9181a605c27d44fe0f37b3a8c7e8dbe63b9515b8e96. For example, the Python code to generate this is:

  import hashlib;
  print hashlib.sha256("user,12345,999999").hexdigest();

The same process was used to generate the challenge hash d90b8f91e1c4befcdfdc48c7dac3bcc28cd817ae5a6ef4b1e20b7e19cecd27b1 for user swift and salt 8329942093.

• Recover the password used to generate the challenge hash above. Hint: The password is an ASCII string consisting only of numeric digits.
• Give a pseudocode description of your algorithm and the worst case running time for it.
• Discuss the merits of your colleague’s proposal. Suggest how your attack might be made intractable.
• Put your solutions in the file solutions.txt.

Part B: Encryption

Another colleague decided to build a symmetric encryption scheme. These are implemented in badencrypt.py and baddecrypt.py and are designed to encrypt a sample message to demonstrate the encryption scheme. To use these demo programs, run:

  CT=$(python badencrypt.py testkeyfile)
  echo $CT
  python baddecrypt.py testkeyfile $CT

Your job is to assess the security of this encryption scheme. Your solution will be a Python program attack.py that takes as input a ciphertext and modifies the ciphertext so that the decrypted message has a different (and more lucrative to the recipient) AMOUNT field and still passes the verification in baddecrypt.py. attack.py must do this without access to the keyfile or knowledge of the key. You can assume the ciphertext contains the sample message hardcoded in badencrypt.py.

We will test your solution with original versions of badencrypt.py and baddecrypt.py and with different encryption keys than the test key provided. To ensure that attack.py produces the correct formatted output, you can run from the command line:

  CT=$(python badencrypt.py testkeyfile)
  MODCT=$(python attack.py $CT)
  python baddecrypt.py testkeyfile $MODCT

In solutions.txt, describe what is wrong with your colleague's scheme and how it should be fixed so that it will be more secure.

Your attack script will not have direct access to the key file and should not attempt to gain access to the process memory of baddecrypt or any other files to steal the key directly.

Deliverables

• You must create a file called ID which contains, on each line: <netid of Person 1>,<CS login>,<Last Name>,<First Name>. Two lines, one for each group member.
• Put all the files (attack.py, solutions.txt, ID) in a directory named “attack” and package them into a tarball with the following command: tar -cf hw3.tar attack/*
• To submit, copy hw3.tar to your handin directory:

  cp hw3.tar ~cs642-1/handin/<cslogin>/hw3

  scp hw3.tar emperor-01.cs.wisc.edu:~cs642-1/handin/<cslogin>/hw3

• As a team, only one person should submit the homework tarfile.

Grading

• Parts A and B are worth up to 5 points for a total of 10 points for this assignment. The extra credit below is worth up to 2 additional points.

Collaboration Policy

You are encouraged to use the internet, the Piazza discussion board for this class, and classmates for information about tools and setup. Please help your fellow classmates with setup and understanding Python, but don't discuss solution specifics with anyone beyond your project partner.

Extra credit: More password cracking

The input swift,password,84829348943 processed with SHA256 iterated 256 times produces the hash 67986ddf45bd064f4c2eb63258a5269838169da9a35ebb13692a2de22e6a4768. For the username zifan with salt 8934029034 the challenge hash is 1ca6004d870d5c9dcf2ffd231046a9015072a518c708040a02bf8b5b3a4e18b2.

The password is representative of real-world passwords: something complex enough that the person that selected this password would consider using it for a website login, but easy enough to be memorable.

Find the password used to produce the challenge hash. Give a pseudocode description of your algorithm and the correct password in solutions.txt.

Hints

• The password is based on a dictionary word.
• The password has a small number (not more than 4) of common transformations, all of which are simple character substitutions. (Think: changing capitalization, swapping symbols and numbers for letters like '@' for 'a', or '1' for 'i').