20211119 Chen Junji

Task Overview

In a system that uses the MD5 hashing algorithm, an administrator generates a signature for each command by combining a secret key k and the command cmd: hash(k||cmd). You have obtained a command cmd=viewfile along with its corresponding signature h. The goal is to use a hash length extension attack to generate a new signature that allows execution of the delete file command (rm).

Attack Mechanism

Hash length extension attacks exploit weaknesses in hash functions by appending data to an existing hash value, producing a new valid hash without knowing the original input. This method leverages the padding mechanism and properties of MD5 to create a new hash.

Implementation Steps

1. Understand how MD5 handles message padding and how it can be exploited.

MD5 processes messages in 512-bit blocks, padding them to ensure the total length is congruent to 448 modulo 512. A 64-bit representation of the original message length is appended at the end.

2. Construct a new command and compute the extended hash.

Given the known command "viewfile" and its hash, we aim to append "deletefile" after appropriate padding. The process involves:

• Calculating the length of the original command.
• Generating the required padding based on the message length.
• Using this padding to extend the hash with the new command.

3. Provide a detailed explanation of the method used and the resulting command and hash.

Example Code

#include <stdio.h>
#include <string.h>
#include <openssl/md5.h>

void md5_length_extension(const char *original_hash, const char *original_data, const char *new_data) {
    unsigned char hash[MD5_DIGEST_LENGTH];
    memcpy(hash, original_hash, MD5_DIGEST_LENGTH);

    size_t original_len = strlen(original_data);
    size_t new_len = strlen(new_data);

    char padding[64] = {0};
    padding[0] = 0x80;

    long long bit_length = (original_len + new_len + 8) * 8;

    for (int i = 0; i < 8; ++i) {
        padding[63 - i] = (bit_length >> (8 * i)) & 0xFF;
    }

    MD5_CTX ctx;
    MD5_Init(&ctx);
    MD5_Update(&ctx, hash, MD5_DIGEST_LENGTH);
    MD5_Update(&ctx, padding, 64);
    MD5_Update(&ctx, new_data, new_len);
    MD5_Final(hash, &ctx);

    printf("New Signature: ");
    for (int i = 0; i < MD5_DIGEST_LENGTH; i++) {
        printf("%02x", hash[i]);
    }
    printf("\n");
}

int main() {
    const char *hash = "original_signature";
    const char *data = "viewfile";
    const char *extension = "||padding||deletefile";

    md5_length_extension(hash, data, extension);
    return 0;
}

Compile command:

gcc -o hash_attack hash_attack.c -lssl -lcrypto

Run command:

./hash_attack

Alternative Tool Usage

Tools like Hashpump can automate this process. Here's an example using Hashpump:

echo -n "viewfile" | hashpump -s h -k k -d "||padding||deletefile" -a "viewfile" | xxd -r -p