Programing assignment: Breaking Insecure MACs.

September 22, 2020

Summary
You’ll be exploiting an integrity scheme that uses the SHA1 hash function which relies on the Merkle-Damg˚ard transform—a construct vulnerable to length extension attacks—for tagging messages. You must use this weakness to your advantage in order to construct arbitrary messages and bypass message validation. In other words, you will show that the integrity scheme
is not UF-CMA secure.

I. Introduction
We have provided you with several Python files that you will work with in this assignment. In particular, you will be demonstrating that a MAC is not UF-CMA secure by modifying student.py to create a forged message and a corresponding tag. Detailed explanations can be found in the Files section, below.

1.1 Scheme
The MAC prepends a secret symmetric key to an input message, then passes it to the SHA1 algorithm: tag = Sha1(password k message) You don’t know the symmetric key, but we guarantee it will be ≤ 100 bytes long.
This MAC is vulnerable to something called a length extension attack. Specifically, it’s possible to forge a valid (message, tag) pair where the message has some arbitrary data appended to the end, while only knowing the length of the password (not its actual value).
1.2 Resources
The Wikipedia page on length extension attacks and the RFC for the Sha1 algorithm are good places to get started. You will also need to carefully read over the code files we have provided you. We recommend that you read the Wikipedia page to get an idea of how the attack is going to work, while Sections 3–5 and 6.1 of the RFC will be helpful in understand the provided
implementation of Sha1.

1.3 Files
You’ve been provided the following library:
•student.py contains your exploit code that will successfully create a forged message that passes the MAC without knowing the secret key. This is the only file you will need to modify.
• crypto.py contains a custom Sha1 implementation modeled after Python’s hashlib module, but also exposes some extra parameters that might help with a length extension attack.
You will likely need to refer to the RFC to understand how to use them.
It also includes convenience functions for converting between strings and bytes. We recommend that you do NOT use Python’s str.encode and bytes.decode, as these often result in confusing errors with character encodings and Unicode. Prefer crypto.s2b and
crypto.b2s, instead.
• oracle.py simulates an UF-CMA adversarial scenario. It includes a MAC oracle that you can query to create tags for messages as well as a function to verify whether or not a tag matches a novel message.
• grader.py runs your exploit and lets you know whether or not you’ve successfully forged a message.
• secret.txt, this is a secret used by the oracle to create tags internally. Though you can view
and edit it if you wish, it will be of no use to you. The auto-grader will use a different secret,
and your solution should work with any secret.
Objective: Make student.main() return a (message, tag) pair that (at least) includes the
original message and your username, hasn’t been submitted to the oracle, and passes the
MAC.
1.4 Running the Code
You can install Python 3.8 for your system from here; there are no extra dependencies to
install. Older versions of Python 3 may work, but we cannot make guarantees. To run the local
grader, simply execute:
python grader.py [your username]
2
II. Deliverables
• student.py: Complete main() to forge messages via a length extension attack. Remember
that the messages you forge should contain at least your username and the original
message. Please keep the existing structure: nothing should run if you execute python
student.py on its own.
• report.pdf: Briefly discuss the exploit details. You should touch on, at minimum: how
reliable your attack is, its (rough) run-time complexity, the root causes of the vulnerability
in the integrity scheme at a high level, and how it could be alleviated (be sure to explain
why these fixes will remedy the problem.).
3