MAC Attack!

I just finished the third project for my security class. This project has been simultaneously the most difficult and most easy lab that I have done. I wanted to describe my experience of the lab here.

The Premise

The premise is that my TA has sent a message to my professor and I was able to intercept it. The message is as follows.

No one has completed lab 2 so give them all a 0

A MAC (Message Authenticated Code) was also in the message, which we know used a 128-bit key. The MAC is as follows in hex.


I want to change the message to tell the professor that I should get full points, but I can't because there is a MAC attached to the message. If I were to change the message, the attached MAC would be invalid and I could not generate a new MAC because I don't have the secret key for the MAC.

MAC (Gemipedia) MAC (Wikipedia)

How I went about the lab

This lab was one of those projects where you just have no idea where to start. I knew what I needed to do and vaguely how it should be done, but the specifics were beyond me. The project turned mostly into analyzing library code and trying to figure out how I could modify it to do what I need, which is to say the least, very stressful.

With this in mind, I was mostly working on creating unit tests that would help me fumble my way through the lab and took many breaks.

I would say the most frustrating thing about the lab was that a big part of it was on hashes, which changes wildly with even the smallest change, so it was very difficult to know whether I was getting close or not.

In the end, I was able to figure it out and I can't describe how relieved I was.

Below is a more technical description of how the lab worked, so tread on if you dare.

Vulnerability in MAC

There is a vulnerability in MAC which took me a while to fully understand. In order to explain the vulnerability, I will have to explain how MAC works in the first place.

MAC is relatively simple. You start out with a key and a message. you concatenate them together and hash it:

Key = "0123456789abcdef"
Message = "Hello World!"
MAC = SHA("0123456789abcdefHello World!")
MAC = 36f141824e771ed3313815d82c996522d8191a99

The SHA algorithm will recursively calculate a digest from 512-bit blocks of data. Because of this, it is possible to continue calculating a hash by using the digest as the initialization vector for the SHA algorithm.

If we were to add to the end of the original message, hash that added bit with IV (initialization vector) being the original MAC, then we could pass this modified message and MAC to the professor and they would think the message was authentic.

The only problem is that SHA adds some information and padding to the end of the message internally to keep all blocks exactly 512 bits long. The solution is to simply add the padding to the end of the message, but before our added bit. One last thing to deal with is that SHA adds the length of the hashed string at the end of the last block, so we will need to know the length of the key for this to work.

The Attack

We are given pretty much everything we need for the attack. The most difficult thing will be figuring out how to modify the IV. According to my teacher, golang's API for SHA allows setting the IV, but most languages don't provide that functionality. I had to download a SHA-1 library and modify it myself to allow for setting an initialization vector. Analyzing the library and making it work for what I need was probably one of the most hair pulling things I have done.

Adding the padding to the message wasn't too difficult, particularly with the aid of unit testing.

In the end I was able to generate this message to send to my teacher; posing as my TA with a valid MAC. The message itself looks a little corrupted, but that is a problem to deal with another day.

Message: No one has completed lab 2 so give them all a 0\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\xf8P.S. Except for ttocsneb, Give him 100%

MAC: d338d12365cd75f5f13673991d9cd1359e355b2e

Prevention from this kind of attack

The best way to prevent this attack from being possible would be to use HMAC instead. It essentially performs two hashes with the key being manipulated in a way that I can not understand.

HMAC (Gemipedia) HMAC (Wikipedia)