File from Canvas
File – project_cryptography.zip is attached with the project.
Cryptography
Goals of the Project For Students
- Will get an introduction to both symmetric and asymmetric cryptographic systems
- Will gain an understanding of how these systems are implemented through examples
- Will exploit systems that have certain vulnerabilities
- Will have the opportunity to engage in discussion about advanced topics in cryptography
Information
There is no required VM for this project. All that is required is a Python development environment. Make certain that you are using Python 3. To check your version of Python, open a command prompt and run the command:
python –version (You may need to use the python3 command instead.)
For the established algorithms that you may find it necessary to use, you are allowed to reference and implement pseudocode with citation (a comment in your code will suffice). What is Pseudocode? https://en.wikipedia.org/wiki/Pseudocode
UNDER NO CIRCUMSTANCES should you copy/paste code into the project. Doing so is an honor code violation (not to mention a real world security concern) and will result in a zero (refer to the syllabus for more information).
The Final Deliverables
You will complete the provided Python file project_cryptography.py and submit it to the autograder in Gradescope.
Open Discussions
For each task we have provided prompts for further discussions. There will be threads created in Ed where students can discuss these topics. Participation is optional and will not be graded.
Good luck!
Table of contents
- Introduction
- FAQ
- Task 1: Vigenere Ciphers
- Task 2: RSA Warmup
- Task 3: Factor 64-bit Key
- Task 4: Weak Key Attack
- Task 5: Broadcast Attack
- Task 6: Parity Attack
- Task 7: Padding Attack
Project Files
You can download project files in Canvas/Assignments/Cryptography.
Important Notes:
Provided Code:
All necessary starter code and unit tests for each task is located in the corresponding folder in the provided zip file.
Python Packages:
- You may import any python packages that are part of the standard library. Some useful ones are already imported for you, and additional ones are not strictly necessary.
- For Tasks 1 through 6, you are restricted to using only the standard library.
- For Task 7, you will need to use the pycryptodome library. You can manually download it from this link https://github.com/Legrandin/pycryptodome. or install it via pip using the command below:
pip install pycryptodome
Unit Tests:
For each task you are also given a unit test file (it starts with test_)to help you develop and test your code. We encourage you to read up on Python unit tests, but in general, the syntax should resemble either:
python -m unittest test_task_rsa_encrypt_message
or:
python test_task_rsa_encrypt_message.py
However, keep in mind that passing the unit test(s) does NOT guarantee that your code will pass the autograder!
Autograder:
The autograder will timeout after 10 minutes. If your implementation is timing out, then there is very likely something wrong with your implementation. It is possible to solve each task in a few seconds. We encourage you to test locally to avoid unnecessary submissions.
Gradescope can get very busy and even potentially unavailable near submission deadlines. Please do not wait until the last minute to make your submissions to the autograder. Submit early and often. There will be no late submissions accepted, as per the syllabus.
Frequently Asked Question(s) (FAQ)
Q: Some algorithms that can be used for this project have Python code implementations that I found on the Internet. Can I use that python code?
- A: No, you may only use pseudocode, and you must cite the source of the pseudocode. Copying and pasting Python code is strictly prohibited.
Q: I’m worried that my implementation of an algorithm is going to fail a plagiarism check. Python syntax is a lot like pseudocode after all….
- A: We understand, and we are not out to get you. We just don’t want you to turn this assignment into a copy/paste adventure. Write your own code. We all have our own unique styles including formatting, variable names, etc. We are not going to hold your algorithm implementations to arbitrary MOSS thresholds.
Q: What is MOSS?
Q: Can I discuss the algorithms with my classmates in Ed Discussions?
- A: DO NOT do this, your message will be removed if this is done. Part of the project is embedded in the research of figuring out which algorithms to use.
Q: Do I need to convert from HEX to INT?
- A: Nope, you shouldn’t need to do this at all. And if you are, you are on the wrong track. It is already done for you in the skeleton code.
Q: Where is this skeleton code you speak of?
- A: You can find it in Canvas/Assignments/Cryptography.
Q: Do I need to read the paper for the RSA Weak Key Attack?
- A: Yes, read the paper first to identify the vulnerability. The code should follow.
Q: Can I include print statements, will this mess up the autograder?
- A: Please do not include print statements in your final code. Feel free to use them when debugging but remember to comment them out or delete them.
Q: Can I include comments in my program?
- A: Yes, comments are encouraged so we understand your thought process and it is also a good way to cite the source of any pseudocode that you may have consulted.
Q: Oh, I need to cite pseudocode?
- A: Yes
Q: Where?
- A: Cite it inline with a comment in your code.
Q: What setup do you recommend for this project?
- A: We typically recommend VS code or PyCharm. Georgia Tech provides a PyCharm license for you, see here. But ultimately you can use whatever you like. The VM also has a compatible version of Python 3 and a text editor installed.
Q: Speaking of VMs, do we need a VM for this project?
- A: No, it isn’t required, but you are welcome to use the course VM.
Q: How do I know which algorithms to use?
- A: With research on the related topics, it should become clear which algorithms are available to solve these problems. The key here is to first understand them, and then implement them in Python.
Q: I’m getting an error like the following shown below. How do I fix it?
msg = bytes.fromhex(hex(m).rstrip(‘L’)[2:]).decode(‘UTF-8’)
UnicodeDecodeError: ‘utf-8’ codec can’t decode byte 0xb7 in position 0: invalid start byte
- A: This error means that something has gone wrong and you most likely have a bug in your implementation.
Q: If I post my code will you tell me why it isn’t working?
- A: No. Unfortunately, with a class of this size, the teaching staff does not have enough bandwidth to review code. If you create a post asking us to look at your code, we will refer you to this message.
Q: Can you provide more test cases? I pass locally but not in the autograder.
- A: As in life, you often have to write your own test cases. At this level of graduate study, we expect some sophistication in terms of debugging code and implementing algorithms. If your code passes locally but not in the autograder, re-examine your algorithm choice and implementation. This project requires a significant amount of research to complete.
Q: Can students share test cases?
- A: Yes, we have created an Ed Discussion post to facilitate this.
Q: Can I import other libraries?
- A: Yes, as long as it is part of the standard Python distribution. The only exception is Task 7 CBC oracle, where you are allowed the use of non-standard libraries. Please refer to the Task 7 instructions for details.
Q: I see that there are two different totient functions – Carmichael’s totient and Euler’s totient. Which one should I use?
- A: Stick to Euler’s totient.
Task 1 – Vigenere Ciphers (30 points)
The Vigenere cipher is an example of a symmetric key cryptographic algorithm. In such a system, a single key is used to both encrypt and decrypt messages (this is what makes it symmetric). The first step for both encryption and decryption is to build a Vignere square like the one pictured below. In each row of the Vigenere square, the letters of the alphabet are shifted to the left by one. The second step is to extend the key to match the length of the cipher/message by repeating it, taking care to remove any spaces or punctuation from the original message. For example, if our message is GEORGIA and our key is TECH we would end up with a key TECHTEC.
To encrypt a message, we lookup each letter of the message as a row, and find its intersection with the column whose label contains the corresponding letter from the key. Using our GEORGIA/TECH example, the intersection of the first letter of the message G with the first letter of the key T is Z. Going letter-by-letter in this manner we build our cipher until we get ZIQYZMC.
To decrypt a cipher, we start with the first letter of the key and traverse that row until we reach the corresponding letter from the cipher. The label of this column is our decrypted letter. Using our same GEORGIA/TECH example, to decrypt the cipher we would start with the first letter of our key T and traverse that row until we reached the first letter of the cipher Z. The label of this column is G – the first letter in our message.
Vigenere Square [source: Wikipedia]
Armed with this information, the first two parts of this task will ask you to write the necessary code to handle the encryption and decryption functionality for a Vigenere cipher system.
For the third and final part, you will attempt to crack a Vigenere cipher using a dictionary attack. Ordinary words can make convenient keys because they are easy to remember, but this practice is far from secure. For this task, you are given a cipher and a list of some of the most common words in the English language. One of those words was used as the key to encrypt the cipher, and your job is to write the code to figure out which one it is. For simplicity, you can assume that all words in the original message are also chosen from the provided list of dictionary words.
def vigenere_decrypt_cipher(c: str, keyword: str) -> str:
# TODO: Write the necessary code to get the message (m) from the cipher ©
# using the keyword
m = ”
return m
def vigenere_encrypt_message(m: str, keyword: str) -> str:
# TODO: Write the necessary code to create a Vigenere cipher (c) of the
# message (m) using the provided keyword
c = ”
return c
def vigenere_dictionary_attack(c: str) -> str:
# TODO: Write the necessary code to get the message (m) from the cipher (c)
m = ”
return m
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Open Discussion
The Vigenere cipher improves upon the ancient Caesar cipher. Mathematically speaking, how much more complexity does it add and how does it accomplish this? What are some ways that one could add more complexity/security to the Vigenere cipher system?
Task 2 – RSA Warmup (7.5 points)
Now that we’ve reviewed a symmetric key cryptographic algorithm, we can move on to the world of asymmetric key cryptography. RSA is perhaps the best known example of asymmetric cryptography. In RSA, the public key is a pair of integers (N, e), and the private key is an integer d.
To encrypt integer m with public key (N, e), we use the formula:
To decrypt cipher integer c with private key d, we use the formula
In this task you will write the code to perform the encryption and decryption steps for the RSA cryptographic algorithm. Finally, you will write the code necessary to calculate the private key d when given the factors of the public key N (i.e. p and q).
def rsa_decrypt_cipher(n: int, d: int, c: int) -> int:
# TODO: Write the necessary code to get the message (m) from the cipher (c)
m = 0
return m
def rsa_encrypt_message(m: int, e: int, n: int) -> int:
# TODO: Write the necessary code to get the cipher (c) from the message (m)
c = 0
return c
def rsa_calculate_private_key(e: int, p: int, q: int) -> int:
# TODO: Write the necessary code to get the private key d from
# the public exponent e and the factors p and q
d = 0
return d
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Open Discussion
Did you try to decrypt a cipher by using a line of Python code something like this: m = c ** d % n? Did it work? (Hint: It did not.) Why not? After all, the math is correct.
Task 3 – RSA Factor A 64-Bit Key (10 points)
Modern day RSA keys are sufficiently large that it is impossible for attackers to traverse the entire key space with limited resources. But in this task, you’re given a unique set of RSA public keys with a relatively small key size (64 bits).
Your goal is to get the factors (p and q) of each key. You can use whatever methodology you want. Your only deliverable is a formatted json file containing p and q. To get your unique set of keys, you must update the task.py file located in the task folder with your 9-digit GT ID, and then run it. Find the section below in the provided task_factor_64_bit_key.py file:
##############################################
# Change this to your 9-digit Georgia Tech ID!
STUDENT_ID = ‘123456789’
##############################################
Running the command “python task_factor_64_bit_key.py” should output your assigned keys. Once you’ve calculated your p and q values, enter them into the function stub for this task. NOTE: It doesn’t matter which value you specify as p and which value you specify as q.
def rsa_factor_64_bit_key() -> typing.Dict[str, typing.Dict[str, int]]:
return {
‘test_1’: {
‘p’: 0,
‘q’: 1
},
‘test_2’: {
‘p’: 0,
‘q’: 1
},
‘test_3’: {
‘p’: 0,
‘q’: 1
},
‘test_4’: {
‘p’: 0,
‘q’: 1
},
‘test_5’: {
‘p’: 0,
‘q’: 1
}
}
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Open Discussion
If 64-bit keys aren’t safe, then what size is appropriate? Is there a trade-off between size and performance?
Task 4 – RSA Weak Key Attack (15 Points)
Read the paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”, which can be found at: https://factorable.net/weakkeys12.extended.pdf. The essay is essential to understanding this task. Do not skip it, do not skim it, read the whole of it.
You are given a unique RSA public key, but the RNG (random number generator) used in the key generation suffers from a vulnerability described in the paper above. In addition, you are given a list of public keys that were generated by the same RNG on the same system. Your goal is to write the code to get the unique private key (d) from your given public key (N, e) using only this provided information.
def rsa_weak_key_attack(given_public_key_N: int, given_public_key_e: int, public_key_list: typing.List[int]) -> int:
# TODO: Write the necessary code to retrieve the private key d from the given public
# key (N, e) using only the list of public keys generated using the same flawed RNG
d = 0
return d
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Open Discussion
Have you ever heard the saying, “Never roll your own crypto?” What are some ways (besides this particular attack – we don’t want you to give too much away) that doing so can cause unintended problems? Can you point to any specific examples or known exploits?
Task 5 – RSA Broadcast Attack (15 Points)
A message was encrypted with three different 1,024-bit RSA public keys N_1, N_2, and N_3, resulting in three different ciphers c_1, c_2, and c_3. All of them have the same public exponent e = 3.
You are given the three pairs of public keys and associated ciphers. Your job is to write the code to recover the original message.
def rsa_broadcast_attack(N_1: int, c_1: int, N_2: int, c_2: int, N_3: int, c_3: int) -> int:
# TODO: Write the necessary code to retrieve the decrypted message
# (m) using three different ciphers (c_1, c_2, and c_3) created
# using three different public key N’s (N_1, N_2, and N_3)
m = 0
return m
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Open Discussion
In addition to the low public exponent being used, this attack is possible because a textbook implementation of RSA is being used. In the real world, there are common mitigating tactics used. What are some examples? Why else are they important?
Task 6 – RSA Parity Oracle Attack (15 Points)
By now you have seen that RSA treats messages and ciphers as ordinary integers. This means that you can perform arbitrary math with them. And in certain situations a resourceful hacker can use this to his or her advantage. This task demonstrates one of those situations.
Along with an encrypted message (c), you are given a special function that you can call – a parity oracle. This function will accept any integer value that you send to it and decrypt it with the private key corresponding to the public key that was used to encrypt the given cipher (c). The return value of the function will indicate whether this decrypted value is even (true) or odd (false). Armed with this function and a little modular arithmetic, it is possible to crack the encrypted message. Your goal is to write the code necessary to decrypt the original message (m) from the given cipher (c).
def rsa_parity_oracle_attack(c: int, N: int, e: int, oracle: Callable[[int], bool]) -> str:
# TODO: Write the necessary code to get the plaintext message
# from the cipher (c) using the public key (N, e) and an oracle
# function – oracle(chosen_c) that will give you the parity
# of the decrypted value of a chosen cipher
#(chosen_c) value using the hidden private key (d)
m = 42
# Transform the integer value of the message into a human readable form
message = bytes.fromhex(hex(int(m_int)).rstrip(‘L’)[2:]).decode(‘utf-8’)
return message
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Open Discussion
This task is a simplified example, but can you see how some potentially useful information may be inadvertently leaked by something (i.e. a protocol)? Can you find any examples?
Task 7: Task CBC Padding Oracle (7.5 Points)
The Advanced Encryption Standard (AES) is a set of standards for encryption set by the U.S. National Institute of Standards and Technology. One of these standards is the Cipher Block Chaining (CBC). CBC uses a fixed length set of bits known as a block, a unique binary sequence known as an Initialization Vector (IV), and a key. The encryption is accomplished in the following sequence.
- Add padding to the plaintext until the appropriate block length.
- XOR the block with the IV.
- Encrypt the new block with the key.
The chaining part comes into play when encrypting multiple blocks. When working on the next block you follow similar steps with one main difference.
- Add padding to the plaintext until the appropriate block length.
- XOR the block with the previous cipher text.
- Encrypt the new block with the key.
The formula is as follows:
Decryption works in reverse.
- Decrypt the cipher text with the key.
- XOR the block with the IV
- Repeat for latter blocks using the previous plain text as the new IV.
The formula is as follows:
For this task we will be working with an attack known as the padding oracle attack. The padding oracle works under the idea that the server is leaking information about the padding. With this information it is possible to both decrypt and encrypt messages.
For this one section of the assignment you will be asked to use a library outside of the standard. In this task you will use the pycryptodome library. This can be manually downloaded from this link https://github.com/Legrandin/pycryptodome. Alternatively it can be downloaded through pip with the following command:
pip install pycryptodome
This task will be the only outside library used.
The first 2 steps will be using a simplified version of padding. In a real world application blocks will be in bits and will typically use \x00 or something similar depending on what standard is being used.
Step 1 of this task is to write a function that can encrypt a short message. You may use pycryptodome’s built in encrypt function, however you must build the padding yourself.
def cbc_encrypt_128(key: bytes, IV: bytes, m: str) -> str:
# TODO: Write the necessary code to encrypt the message
# (m) using the provided key and IV
# the necessary block length is 128 bits
# pad with the byte ‘\x00’
# Do Not modify code above this line
# Code Below Here
c = 0
return b64encode(c).decode(“utf-8”)
Step 2 of this task is to write a function that can decrypt a short message. You may use pycryptodome’s built in decrypt function.
def cbc_decrypt_128(key: bytes, IV: bytes, c: bytes) -> str:
# TODO: Write the necessary code to decrypt the cipher
# (c) using the provided key and IV
# Do Not modify code above this line
# Code Below Here
m = 0
return m
Step 3 of this task is to write one of the core functions of an oracle which will test if the padding follows pkcs guidelines. This check is often the information that the oracle can leak. For this task you must assume that there will always be at least 1 byte of padding, but there does not always have to be a message attached.
def check_padding(padding) -> bool:
# TODO: Write the necessary code to check
# if the padding matches PKCS standards
is_pkcs_padded = “This variable should be a bool value”
return is_pkcs_padded
These steps can all be tested using the test_task_cbc_ python files. You can do so with the following commands:
python test_task_cbc_decrypt.py
python test_task_cbc_encrypt.py
python test_task_cbc_pkcs.py
Resources
https://en.wikipedia.org/wiki/Padding_oracle_attack
https://www.pycryptodome.org/
Submission Details
You will write your code in the specified function stub(s) found in the provided project_cryptography.py file. When ready, submit this file to the Project Cryptography autograder in Gradescope.
Submission Instructions:
- Submit file project_cryptography.py to Project Cryptography on Gradescope.
- There is no submission limit for the Cryptography Project, but we reserve the right to change that if anyone abuses.
- You will need your GTID for this projects.
My GTID: 903656183
