Thread: MD5 program not giving correct hashes.

  1. #1
    C lover
    Join Date
    Oct 2007
    Location
    Virginia
    Posts
    266

    MD5 program not giving correct hashes.

    So I was following the MD5 algorithm on wikipedia and when I was done, I noticed that the code doesn't produce the correct hash. Whats even more, the code doesn't even produce the same, incorrect hash each time the program is run. I figure, the onlything that changes when the program is run are the memory addresses and that maybe I misused some pointer but I fail to see that anywhere in my code. I've stepped through it a few times in GDB, I'm sure there's something I'm overlooking so I'd like to have someone here look at it. Pretty please!! It's not homework either, just something I wanted to do for fun


    Here is the algorithm from wikipedia: MD5 - Wikipedia, the free encyclopedia


    md5.c
    Code:
    #include <stdio.h>
    #include <string.h>
    #include "md5.h"
    
    int main(int argc, char ** argv){
      
      char msg_block[BLOCK_LEN], digest[DIGEST_LEN], * end;
      
      uint8 read_len = 0, curr_len = 0, msg_len = 0;
      uint4 h[4], k[64], r[64];
      
      
      end = (char *)(argv[1] + strlen(argv[1]) - 1);
      msg_len = strlen(argv[1]);
      
      /*
        while((read_len = get_block( msg_block, argv[1], end )) <= msg_len){
        do_hash( msg_block, h, k, r );
        curr_len += read_len;
        }
      */
    
      do{
        read_len = get_block( msg_block, argv[1], end );
        do_hash( msg_block, h, k, r);
        curr_len += read_len;
      }while( curr_len < msg_len );
    
      msg_block[read_len++] = 0x80;
    
      if( read_len > (BLOCK_LEN - 64) ){
        while( read_len < BLOCK_LEN ){
          msg_block[read_len++] = 0x0;
          curr_len += read_len;
        }
        
        do_hash( msg_block, h, k, r );
        read_len = 0;
      }
    
      while( read_len < BLOCK_LEN - 64 )
        msg_block[read_len++] = 0x0;
      
      curr_len += read_len;
    
      do_hash( msg_block, h, k, r );
      
      memcpy( msg_block + (BLOCK_LEN - 64), &curr_len, 64 );
    
      do_hash( msg_block, h, k, r );
    
      //  for(int i = 0; i <= 15; i++)
      //((uint4 *)digest)[i] = h[i];
    
      printf("Digest: %X%X%X%X\n", h[0], h[1], h[2], h[3]);
    
      return 0;
    }
    
    void do_hash(char * msg_block, uint4 * h, uint4 * k, uint4 * r){
    
      uint4 word[16],
        a = h[0],
        b = h[1],
        c = h[2],
        d = h[3],
        f,
        g,
        temp;
      
      char * msg_ptr = msg_block;
    
      // Break the block into 16 32bit words
      for(int i = 0; i <= 15; i++)
        word[i] =  ((uint4 *)msg_block)[i];
    
      for(int i = 0; i <= 63; i++){
        if( 0 <= i && i <= 15 ){
          f = (b & c) | ((~b) & d);
          g = i;
        }
        else if( 16 <= i && i <= 31){
          f = (d & b) | ((~d) & c);
          g = (5 * i) % 16;
        }
        else if( 32 <= i && i <= 47 ){
          f = b ^ c ^ d;
          g = (3 * i + 5) % 16;
        }
        else if( 47 <= i && i <= 63 ){
          f = c ^ (b | (~d));
          g = (7 * i) %16;
        }
    
        temp = d;
        d = c;
        c = b;
        b = b + leftrotate((a + f + k[i] + word[g]), r[i]);
        a = temp;
      }
    
      h[0] += a;
      h[1] += b;
      h[2] += c;
      h[3] += d;
    
    }
    
    /* 
       Gets a 512 block of characters from the buffer specified by input
       end denotes the final memory address of input 
    */
    
    uint4 get_block(char * msg_block, char * input, char * end){
      
      uint4 read_len;
      
      memset(msg_block, 0x0, BLOCK_LEN);
    
      for(read_len = 0; (read_len <= BLOCK_LEN) && (input <= end); read_len++)
        msg_block[read_len] = *input++;
    
      return read_len;
      
    }
    
    uint4 leftrotate(uint4 x, uint4 c){
      return (x << c) | (x >> (32 - c));
    }
    
    void md5_init( uint4 * k, uint4 * r, uint4 * h){
    
      h[0] = 0x67452301;
      h[1] = 0xefcdab89;
      h[2] = 0x98badcfe;
      h[3] = 0x10325476;
    
      uint4 temp_r[] = { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
    		    5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
    		    4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
    		    6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21};
    
      uint4 temp_k[] = { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
    		    0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
    		    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
    		    0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
    		    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
    		    0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
    		    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
    		    0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
    		    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
    		    0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
    		    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
    		    0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    		    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
    		    0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
    		    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
    		    0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};
    
      for(int i = 0; i <= 63; i++)
        r[i] = temp_r[i], k[i] = temp_k[i];
    
    }



    md5.h

    Code:
    #ifndef MD5_H
    #define MD5_h
    
    #define BLOCK_LEN 512
    #define DIGEST_LEN 16
    
    #define DEBUG(x) printf("Debug # %u\n", x);
    
    
    typedef unsigned int uint4;
    typedef unsigned long long uint8;
    typedef unsigned char ubyte;
    
    void do_hash(char * msg_block, uint4 * h, uint4 * k, uint4 * r); 
    
    uint4 get_block(char * msg_block, char * input, char * end);
    
    uint4 leftrotate(uint4 x, uint4 c);
    
    void md5_init( uint4 * k, uint4 * r, uint4 * h);
    
    #endif

  2. #2
    C lover
    Join Date
    Oct 2007
    Location
    Virginia
    Posts
    266
    Well, looking over it again, part of the problem is that I'd forgot to call md5_init() in the beginning. NOW it produces the same incorrect hash each time. But it's still an incorrect hash.

  3. #3
    C lover
    Join Date
    Oct 2007
    Location
    Virginia
    Posts
    266
    Bump...

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    See all these.
    BLOCK_LEN - 64

    > http://en.wikipedia.org/wiki/MD5
    It's supposed to be 64 BITS, not 64 BYTES

    > memcpy( msg_block + (BLOCK_LEN - 64), &curr_len, 64 );
    This assumes your machine is little endian

    Why do you call do_hash() 4 times? rather than once at the end, when the block is fully prepared?

    > for(read_len = 0; (read_len <= BLOCK_LEN)
    This is a buffer overrun, when you start processing lots of data.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    C lover
    Join Date
    Oct 2007
    Location
    Virginia
    Posts
    266
    Looks like BLOCK_LEN is wrong also then as it says the message chunk should be 512 BITS... As for why I call do_hash 4 times, per the algorithm on Wikipedia, I should be processing the message in 512bit chunks, each time doing whats in do_hash(). There are two special cases that need be accounted for where there isn't enough to tack on the 64 bit length to the end of the last chunk and where we actually append the 64 bit length. Those both require I run do_hash() also. As for the buffer overrun, unless you're talking about the "inclusiveness" of read_len == BLOCK_LEN, I fail to see how that is a buffer overrun. As for the memcpy thing, should I be implimenting my own custom memcpy function that does it in little endian? Thanks for taking a look at this, I'm make these changes and see what happens.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. output for array of pointers is not giving correct values
    By nkrao123@gmail. in forum C Programming
    Replies: 8
    Last Post: 09-03-2011, 07:40 AM
  2. Replies: 9
    Last Post: 07-15-2011, 03:22 PM
  3. Help my program is giving a problem
    By zangetsu in forum C Programming
    Replies: 72
    Last Post: 04-04-2011, 10:56 AM
  4. Program giving errors
    By andy bee in forum C Programming
    Replies: 5
    Last Post: 08-11-2010, 10:38 PM
  5. Replies: 3
    Last Post: 07-24-2002, 08:46 AM