Understanding MD4 Hashing Mechanics in C++

Implementing historical cryptographic hash functions like MD4 from scratch is an excellent exercise for learning bitwise operations, memory management, and message padding in C++. However, cryptographic algorithms require precise adhering to specification details like RFC 1320. A single misstep in block sizing or byte-ordering will result in completely different hash outputs.

If your custom MD4 implementation produces output like cb1ed24941ae0d60dc373d4f615a12a8 instead of the expected empty string hash 31d6cfe0d16ae931b73c59d7e0c089c0, a few core logic flaws are likely at play.

Key Bugs in the Flawed Implementation

By comparing the RFC 1320 specification with common initial implementation code, four main issues stand out:

1. Incorrect Block Size (64 Bytes vs. 15 Bytes)

MD4 operates on 512-bit (64-byte) message blocks split into sixteen 32-bit words. In flawed code, you will often find iterations calculated like this:

size_t iterations = input.size() / 15; // Incorrect!

Because MD4 processes chunks of 64 bytes, iterations must be calculated by dividing the total padded byte length by 64.

2. Adding Bytes Instead of 32-Bit Words

The round operations in MD4 expect 16 32-bit words ($X[0 \dots 15]$), constructed from 64 bytes in little-endian order. Using an array of single 8-bit bytes (uint8_t) inside round operations adds an 8-bit integer instead of a combined 32-bit word, drastically skewing bitwise rotators and additions.

3. Truncated 64-bit Bit Length Padding

Message padding requires appending the original bit length as a 64-bit integer (8 bytes) in little-endian representation at the end of the 512-bit padded block. Appending only 4 bytes (32-bit value) leaves the message incorrectly padded.

4. Hex Formatting for the Final Output

MD4 digest output consists of four 32-bit state variables ($A, B, C, D$) formatted as 16 hex bytes in little-endian order. Printing raw integer values with standard std::hex omits leading zeros and byte swapping required for RFC compliance.

Corrected C++ Implementation

Below is a working, clean C++ implementation of MD4 designed for educational purposes:

#include <iostream>
#include <vector>
#include <string>
#include <cstdint>
#include <iomanip>
#include <sstream>

class MD4 {
private:
    uint32_t A = 0x67452301;
    uint32_t B = 0xEFCDAB89;
    uint32_t C = 0x98BADCFE;
    uint32_t D = 0x10325476;

    static inline uint32_t F(uint32_t x, uint32_t y, uint32_t z) { return (x & y) | (~x & z); }
    static inline uint32_t G(uint32_t x, uint32_t y, uint32_t z) { return (x & y) | (x & z) | (y & z); }
    static inline uint32_t H(uint32_t x, uint32_t y, uint32_t z) { return x ^ y ^ z; }

    static inline uint32_t rotateLeft(uint32_t val, int bits) {
        return (val << bits) | (val >> (32 - bits));
    }

    void processBlock(const uint8_t* block) {
        uint32_t X[16];
        for (int i = 0; i < 16; ++i) {
            X[i] = static_cast<uint32_t>(block[i * 4]) |
                  (static_cast<uint32_t>(block[i * 4 + 1]) << 8) |
                  (static_cast<uint32_t>(block[i * 4 + 2]) << 16) |
                  (static_cast<uint32_t>(block[i * 4 + 3]) << 24);
        }

        uint32_t AA = A, BB = B, CC = C, DD = D;

        // Round 1
        auto R1 = [&](uint32_t& a, uint32_t b, uint32_t c, uint32_t d, int k, int s) {
            a = rotateLeft(a + F(b, c, d) + X[k], s);
        };
        R1(A, B, C, D, 0, 3);  R1(D, A, B, C, 1, 7);  R1(C, D, A, B, 2, 11); R1(B, C, D, A, 3, 19);
        R1(A, B, C, D, 4, 3);  R1(D, A, B, C, 5, 7);  R1(C, D, A, B, 6, 11); R1(B, C, D, A, 7, 19);
        R1(A, B, C, D, 8, 3);  R1(D, A, B, C, 9, 7);  R1(C, D, A, B, 10, 11); R1(B, C, D, A, 11, 19);
        R1(A, B, C, D, 12, 3); R1(D, A, B, C, 13, 7); R1(C, D, A, B, 14, 11); R1(B, C, D, A, 15, 19);

        // Round 2
        auto R2 = [&](uint32_t& a, uint32_t b, uint32_t c, uint32_t d, int k, int s) {
            a = rotateLeft(a + G(b, c, d) + X[k] + 0x5A827999, s);
        };
        R2(A, B, C, D, 0, 3);  R2(D, A, B, C, 4, 5);  R2(C, D, A, B, 8, 9);  R2(B, C, D, A, 12, 13);
        R2(A, B, C, D, 1, 3);  R2(D, A, B, C, 5, 5);  R2(C, D, A, B, 9, 9);  R2(B, C, D, A, 13, 13);
        R2(A, B, C, D, 2, 3);  R2(D, A, B, C, 6, 5);  R2(C, D, A, B, 10, 9); R2(B, C, D, A, 14, 13);
        R2(A, B, C, D, 3, 3);  R2(D, A, B, C, 7, 5);  R2(C, D, A, B, 11, 9); R2(B, C, D, A, 15, 13);

        // Round 3
        auto R3 = [&](uint32_t& a, uint32_t b, uint32_t c, uint32_t d, int k, int s) {
            a = rotateLeft(a + H(b, c, d) + X[k] + 0x6ED9EBA1, s);
        };
        R3(A, B, C, D, 0, 3);  R3(D, A, B, C, 8, 9);  R3(C, D, A, B, 4, 11); R3(B, C, D, A, 12, 15);
        R3(A, B, C, D, 2, 3);  R3(D, A, B, C, 10, 9); R3(C, D, A, B, 6, 11); R3(B, C, D, A, 14, 15);
        R3(A, B, C, D, 1, 3);  R3(D, A, B, C, 9, 9);  R3(C, D, A, B, 5, 11); R3(B, C, D, A, 13, 15);
        R3(A, B, C, D, 3, 3);  R3(D, A, B, C, 11, 9); R3(C, D, A, B, 7, 11); R3(B, C, D, A, 15, 15);

        A += AA;
        B += BB;
        C += CC;
        D += DD;
    }

public:
    std::string digest(const std::string& input) {
        uint64_t originalBitLen = input.size() * 8;
        std::vector<uint8_t> msg(input.begin(), input.end());

        // 1. Append padding bit '1' followed by zeros
        msg.push_back(0x80);
        while ((msg.size() % 64) != 56) {
            msg.push_back(0x00);
        }

        // 2. Append original length as 64-bit integer (Little-Endian)
        for (int i = 0; i < 8; ++i) {
            msg.push_back(static_cast<uint8_t>(originalBitLen >> (i * 8)));
        }

        // 3. Process each 64-byte block
        for (size_t i = 0; i < msg.size(); i += 64) {
            processBlock(&msg[i]);
        }

        // 4. Format digest into hex string (Little-Endian per word)
        std::ostringstream ss;
        uint32_t state[4] = { A, B, C, D };
        for (int i = 0; i < 4; ++i) {
            ss << std::hex << std::setfill('0')
               << std::setw(2) << (state[i] & 0xFF)
               << std::setw(2) << ((state[i] >> 8) & 0xFF)
               << std::setw(2) << ((state[i] >> 16) & 0xFF)
               << std::setw(2) << ((state[i] >> 24) & 0xFF);
        }
        return ss.str();
    }
};

int main() {
    MD4 md4;
    std::cout << "MD4(\"\") = " << md4.digest("") << std::endl;
    return 0;
}

Security Note

While building MD4 from scratch is an excellent way to practice C++ bitwise operations and learn RFC specification compliance, MD4 is cryptographically broken and unsafe for production use. For modern applications requiring cryptographic hash algorithms, use standardized algorithms like SHA-256 or SHA-3 via standard libraries like OpenSSL.