Homework 1

Homework 1 is due Tue Sep 13, 2022 on or before 11:59:59pm EDT. The assignment parts will be submitted via GradeScope. If your GradeScope account was not automatically created and linked, click on one of the “HW1” assignments in Moodle and it should set up. Contact the TA and Instructor if you are having trouble.

Points: HW1 has a maximum of 100 points.

Acknowledgements: Parts of this assignment was derived with permission from assignments created by Adam Doupé and Micah Sherr.

Part 1: Written Question (10 points)

The first part of this homework will require you to answer questions about confidentiality and authenticity of a simple “secure” communication protocol betwen two parties. See the Homework 1 Question 1 description The assignment solution must be a PDF and should be turned in via GradeScope.

Part 2: Breaking Classic Ciphers

In this part of the assignment, you will be breaking classic encryption ciphers. Your goal for all sub-parts is identifying the key.

Part 2.1 – Alpha Test (15 points)

As a crypto-breaking warmup, you’ll be given a ciphertext that’s been encrypted with a Caeser Cipher (also known as a ROT-X cipher, as discussed in class). You’ll be given the ciphertext, and your goal is to derived the key. Use this part of the assignment as a warmup. You’ll use these skills in later parts to break more complex Caesar ciphers. Feel free to double-check your work with online Caesar Cipher breaking tools.

Obtain ciphertext: To get your ciphertext submit a blank file to the “Alpha Test Ciphertext” assignment on GradeScope. This will give you a ciphertext that is unique to you.

Submission: Submit on GradeScope a file called README (no extension, plaintext) which contains how you broke the cipher (what approach you took). Note: You must include the following line in your README file (replace BROKEN_KEY with the letter that corresponds to the shift that you have, A-Z):

key: BROKEN_KEY

Part 2.2 – Beta Test (15 points)

As a second crypto-breaking warmup, you’ll be given a ciphertext that’s been encrypted with a Vigenère Cipher (as discussed in class). You’ll be given the ciphertext, and your goal is to derive the key. Use this part of the assignment as a warmup. You’ll use these skills in later parts to break more complex Vigenère ciphers. Feel free to double-check your work with online Vigenère Cipher breaking tools.

Obtain ciphertext: To get your ciphertext submit a blank file to the “Beta Test Ciphertext” assignment on GradeScope. This will give you a ciphertext that is unique to you.

key: BROKEN_KEY

Part 2.3 – Julius Test (30 points)

Now, let’s put those code-breaking skills to work. This new cipher is a Caesar Cipher with a twist. This cryptosystem will operate on bytes (8-bits): for an alphabet of 256 values (0-255). Text will be represented as ASCII (e.g., A is represented by hex 0x41). Instead of shift, Exclusive OR (XOR) is used. Because of this, encryption and decryption are the same operation.

Your agents have found that the following Python 3 code is the encryption algoritm (alternatively, you may wish to use the Java and C versions).

import base64

def encode(text):
    return base64.b64encode(text)

def decode(text):
    return base64.b64decode(text)

def encrypt(cleartext, key):
    to_return = bytearray(len(cleartext))
    for i in range(len(cleartext)):
        to_return[i] = cleartext[i] ^ key
    return bytes(to_return)

Analysis of the encryption function shows that it can output non-printable characters (confirm this for yourself), therefore all output is encoded using Base64 Encoding using the encode and decode functions.

For example, the string “test” encrypted with the key 0x80 (128 decimal) is:

print(encode(encrypt(b"test", 0x80)))
b'9OXz9A=='

We can verify that encrypting 90Xz9A== with the key 0x80 results in “test”:

print(encrypt(decode("9OXz9A=="), 0x80))
b'test'

Your goal is to break the encryption and recover the key.

Obtain ciphertext: To get your ciphertext submit a blank file to the “Julius Test Ciphertext” assignment on GradeScope. This will give you a Base64 Encoded ciphertext that is unique to you.

Submission: Submit on GradeScope a file called README with the key, and all the code you used to break the ciphertext. Note: You must include the following line in your README file (replace BROKEN_KEY with the hexadecimal representation of the key, prefixed by 0x):

key: BROKEN_KEY

For example, if you decide the key is 0x80 (as in the example), submit a README with the following line:

key: 0x80

Part 2.4 – Alan Test (30 points)

This cipher is a Vigenère Cipher with a twist. Similar to Part 1.3, this cryptosystem operates on bytes (8-bits): for an alphabet of 256 values (0-255). Text will be represented as ASCII (e.g., A is represented by hex 0x41). Instead of shift, Exclusive OR (XOR) is used. Because of this, encryption and decryption are the same operation.

Your agents have found that the following Python 3 code is the encryption algoritm, with the same encoding and decoding functions used in Part 1.3 (alternatively, you may wish to use the Java and C versions).

import base64

def encode(text):
    return base64.b64encode(text)

def decode(text):
    return base64.b64decode(text)

def encrypt(cleartext, key):
    to_return = bytearray(len(cleartext))
    for i in range(len(cleartext)):
        to_return[i] = cleartext[i] ^ key[i % len(key)]
    return bytes(to_return)

For example, the string “this is a test” encrypted with the key “12” is:

print(encode(encrypt(b"this is a test", b"12")))
b'RVpYQRFbQhJQEkVXQkY='

We can verify that encrypting RVpYQRFbQhJQEkVXQkY= with the key “12” results in “this is a test”:

print(encrypt(decode("RVpYQRFbQhJQEkVXQkY="), b"12"))
b'this is a test'

Your goal is to break the encryption and recover the key.

Obtain ciphertext: To get your ciphertext submit a blank file to the “Alan Test Ciphertext” assignment on GradeScope. This will give you a Base64 Encoded ciphertext that is unique to you.

key: BROKEN_KEY

For example, if you decide the key is “12” (as in the example), submit a README with the following line:

key: 12