MD4 implementation in C -- consistent, yet erroneous output

Question

I can't seem to get my md4 implementation working. Any ideas as to what's wrong? Also, I'm not in the class that this project was assigned to.. I'm just doing it for kicks. I would also rather you give me hints than an outright answer. Thanks!

EDIT: To be specific (as I know to be), my outputs do not match the test vectors provided by RFC1320. For Example:

From RFC -- MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d 
Mine -- DIGEST: ed763b1deb753a9d8fc7e3f1a653a954 -- 32 BYTES

I am, however, getting correct sizes from my output hashes (32 bytes)

If there is anything else that I need to clarify, please comment!

/**
  hThreat @ http://auburn.edu/~dac0007/blog/
  "MD4 hashing algorithm -- beginning project 1"
**/

// References
    //http://tools.ietf.org/html/rfc1320

#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// define 3 auxiliary functions (Copied from RFC1320)
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define ROTL(x, n) (((x) << (n)) | ((x) >> (32-(n))))

BYTE* stepOne(int bitLen, int byteLen, BYTE* pMsg)
{

    /*  STEP ONE
     *
     **/
    printf("\n\n\n STEP 1\n--------\n");

    // find amount to pad message (assuming it's not already 448 bits)
    for(int i=0; i<512 && bitLen%512!=448; i++)
     bitLen++;

    // amount of data that will be appended
    int tPad = (bitLen/8)-byteLen;

    // create a memory block of appropriate size
    BYTE* bloc = (BYTE*)malloc(tPad+byteLen); // ie 56 bytes
    memset(bloc,0,tPad+byteLen);    // zero everything out, 0x80, 0x00,...,0x00
    printf("Created %d BYTE block\n",tPad+byteLen);

    // Set elements of bloc = to elements of pMsg
    for(int i=0; i<byteLen; i++)
     bloc[i] = pMsg[i];
    printf("Set bloc <=> pMsg; bloc = \"%s\"\n",(char*)bloc);

    // Pad bloc to spec,
    bloc[byteLen] = 0x80;      // first byte should be: 1000 0000b
    // memset took care of the rest..
    printf("-> %s PADDED TO %d BYTES\n","bloc", byteLen+tPad);
    printf("-> bloc = \"%s\"\n",(char*)bloc);

    // Set pMsg = bloc
    pMsg = bloc;
    printf("Set pMsg = bloc; pMsg = \"%s\"\n",(char*)pMsg);

    return pMsg;
    // end step 1
}

BYTE* stepTwo(int bitLen, int byteLen, BYTE* pMsg)
{
    printf("\n\n\n STEP 2\n--------\n");
    printf("Set pMsg = bloc; pMsg = \"%s\"\n",(char*)pMsg);

    // Assuming that the original byteLen of message < 2^64
    int originalLen = byteLen;
    int tByteLen = (bitLen/8);

    // create 64 bit representation of byteLen (b bits)
    unsigned long long int uint64 = (unsigned long long int)originalLen*8;
    int pdSz = sizeof(uint64);

    // create a memory block of appropriate size (Multiple of 512/8)
    BYTE* bloc = (BYTE*)malloc(tByteLen + pdSz);// ie 56 + 8 = 64 bytes
    memset(bloc,0,tByteLen + pdSz);    // zero everything out
    printf("Created %d BYTE block\n",tByteLen+pdSz);

    // Set elements of bloc = to elements of pMsg
    for(int i=0; i<tByteLen; i++)
     bloc[i] = pMsg[i];
    printf("Set bloc <=> pMsg; bloc = \"%s\"\n",(char*)bloc);

    // Append low order DWORD first, as specified
    for(int i=0; i<pdSz; i++)
     bloc[i+tByteLen] = (BYTE)(uint64 >> i*pdSz);

    printf("-> %s PADDED TO %d BYTES\n","bloc", tByteLen+pdSz);
    printf("-> bloc = \"%s\"\n",(char*)bloc);

    // Set pMsg = bloc
    pMsg = bloc;
    printf("Set pMsg = bloc; pMsg = \"%s\"\n",(char*)pMsg);

    return pMsg;
    // step 2 complete
}

void stepThreeFourFive(int bitLen, BYTE* pMsg)
{
    /*  STEP THREE
     *
     **/
    printf("\n\n\n STEP 3\n--------\n");

    // Initialize 4 DWORD buffer
    DWORD A = 0x67452301;
    DWORD B = 0xefcdab89;
    DWORD C = 0x98badcfe;
    DWORD D = 0x10325476;

    DWORD AA;
    DWORD BB;
    DWORD CC;
    DWORD DD;

    printf("(Defined 4 DWORD buffer)");
    // end step 3 

    /*  STEP FOUR
     *
     **/
    printf("\n\n\n STEP 4\n--------\n");

    // process each 16-word block
    BYTE* X = (BYTE*)malloc(4*sizeof(DWORD));

    for(int i=0; i<((bitLen/8)/32)-1; i++)
    {
     // Copy block i into X
     for(int j=0; j<16; j++)
      X[j] = pMsg[i*16+j];

     // save to spec
     AA = A;
     BB = B;
     CC = C;
     DD = D;

     /* Round 1 */
     printf("ROUND 1 ");
     A = ROTL((A + F(B,C,D) + X[0]),3);
     D = ROTL((D + F(A,B,C) + X[1]),7);
     C = ROTL((C + F(D,A,B) + X[2]),11);
     B = ROTL((B + F(C,D,A) + X[3]),19);
     //
     A = ROTL((A + F(B,C,D) + X[4]),3);
     D = ROTL((D + F(A,B,C) + X[5]),7);
     C = ROTL((C + F(D,A,B) + X[6]),11);
     B = ROTL((B + F(C,D,A) + X[7]),19);
     //
     A = ROTL((A + F(B,C,D) + X[8]),3);
     D = ROTL((D + F(A,B,C) + X[9]),7);
     C = ROTL((C + F(D,A,B) + X[10]),11);
     B = ROTL((B + F(C,D,A) + X[11]),19);
     //
     A = ROTL((A + F(B,C,D) + X[12]),3);
     D = ROTL((D + F(A,B,C) + X[13]),7);
     C = ROTL((C + F(D,A,B) + X[14]),11);
     B = ROTL((B + F(C,D,A) + X[15]),19);
     printf("COMPLETE\n");

     /* Round 2 */
     printf("ROUND 2 ");
     A = ROTL((A + G(B,C,D) + X[0] + 0x5A827999),3);
     D = ROTL((D + G(A,B,C) + X[4] + 0x5A827999),5);
     C = ROTL((C + G(D,A,B) + X[8] + 0x5A827999),9);
     B = ROTL((B + G(C,D,A) + X[12] + 0x5A827999),13);
     //
     A = ROTL((A + G(B,C,D) + X[1] + 0x5A827999),3);
     D = ROTL((D + G(A,B,C) + X[5] + 0x5A827999),5);
     C = ROTL((C + G(D,A,B) + X[9] + 0x5A827999),9);
     B = ROTL((B + G(C,D,A) + X[13] + 0x5A827999),13);
     //
     A = ROTL((A + G(B,C,D) + X[2] + 0x5A827999),3);
     D = ROTL((D + G(A,B,C) + X[6] + 0x5A827999),5);
     C = ROTL((C + G(D,A,B) + X[10] + 0x5A827999),9);
     B = ROTL((B + G(C,D,A) + X[14] + 0x5A827999),13);
     //
     A = ROTL((A + G(B,C,D) + X[3] + 0x5A827999),3);
     D = ROTL((D + G(A,B,C) + X[7] + 0x5A827999),5);
     C = ROTL((C + G(D,A,B) + X[11] + 0x5A827999),9);
     B = ROTL((B + G(C,D,A) + X[15] + 0x5A827999),13);
     printf("COMPLETE\n");

      /* Round 3 */
     printf("ROUND 3 ");
     A = ROTL((A + H(B,C,D) + X[0] + 0x6ED9EBA1),3);
     D = ROTL((D + H(A,B,C) + X[8] + 0x6ED9EBA1),9);
     C = ROTL((C + H(D,A,B) + X[4] + 0x6ED9EBA1),11);
     B = ROTL((B + H(C,D,A) + X[12] + 0x6ED9EBA1),15);
     //
     A = ROTL((A + H(B,C,D) + X[2] + 0x6ED9EBA1),3);
     D = ROTL((D + H(A,B,C) + X[10] + 0x6ED9EBA1),9);
     C = ROTL((C + H(D,A,B) + X[6] + 0x6ED9EBA1),11);
     B = ROTL((B + H(C,D,A) + X[14] + 0x6ED9EBA1),15);
     //
     A = ROTL((A + H(B,C,D) + X[1] + 0x6ED9EBA1),3);
     D = ROTL((D + H(A,B,C) + X[9] + 0x6ED9EBA1),9);
     C = ROTL((C + H(D,A,B) + X[5] + 0x6ED9EBA1),11);
     B = ROTL((B + H(C,D,A) + X[13] + 0x6ED9EBA1),15);
     //
     A = ROTL((A + H(B,C,D) + X[3] + 0x6ED9EBA1),3);
     D = ROTL((D + H(A,B,C) + X[11] + 0x6ED9EBA1),9);
     C = ROTL((C + H(D,A,B) + X[7] + 0x6ED9EBA1),11);
     B = ROTL((B + H(C,D,A) + X[15] + 0x6ED9EBA1),15);
     printf("COMPLETE\n\n");

     // increment registers
     A = A + AA;
     B = B + BB;
     C = C + CC;
     D = D + DD;
    }
    // end step 4

    /*  STEP FIVE
     *
     **/
    printf("\n\n STEP 5\n--------\n");

    // Create a 16 byte buffer for the digest
    BYTE* digest = (BYTE*)malloc(4*sizeof(DWORD));
    memset(digest,0,4*sizeof(DWORD));

    /* output beginning with low order byte of A and ending with high order byte of D */

    // fill the buffer

    for(int i=0; i<sizeof(DWORD); i++)
    {
     digest[i] = (BYTE)(A >> i);
     digest[i+4] = (BYTE)(B >> i);
     digest[i+8] = (BYTE)(C >> i);
     digest[i+12] = (BYTE)(D >> i);
    } 

    // print the digest
    printf("DIGEST: ");
    for(int i=0; i<(4*sizeof(DWORD)); i++)
     printf("%x", digest[i]);

    printf(" -- %d BYTES", strlen((char*)digest));

    free(digest);
    free(X);

    // end step 5

}

int main()
{
    printf("\n STEP 0\n--------\n");

    BYTE msg[] = "abc";

    int byteLen = strlen((char*)msg);
    int bitLen = byteLen*8;

    // get a pointer to the byte containing message
    BYTE* pMsg = &msg[0];

    printf("Message to Digest: \"%s\"\n", pMsg);
    printf("Size of Message: %d", byteLen);

    pMsg = stepOne(bitLen, byteLen, pMsg);
    pMsg = stepTwo(448, byteLen, pMsg);
    stepThreeFourFive(512, pMsg);

    while(true)
        Sleep(1000);
    return 0;
}

Answer 1

Why don't you print the results of A, B, C, D at each step, and compare to the results of the standard implementation (RFC 1320) for each line.

This is what I've done in the past with MD5 when tweaking ways of generating it, or changing implementation language.

Answer 2

Hi, I'm working on MD4, and have been working with your implementation (wich is clear and understable ) but there seems to be a problem with your DWORD* X lenght: I didn't realy understand why you worked with a BYTE table... I just replaced it by a 16-DWORD table, and printed ABCD at the end of Step4: that seemed to be good with RFC 1320, and papers I m working with...