md5.c

/*
 * Simple MD5 implementation
 *
 * Compile with: gcc -o md5 -O3 -lm md5.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
 
// leftrotate function definition
#define LEFTROTATE(x, c) (((x) << (c)) | ((x) >> (32 - (c))))
 
// These vars will contain the hash
uint32_t h0, h1, h2, h3;
 
void md5(uint8_t *initial_msg, size_t initial_len) {
 
    // Message (to prepare)
    uint8_t *msg = NULL;
 
    // Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
 
    // r specifies the per-round shift amounts
 
    uint32_t 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};

    // Use binary integer part of the sines of integers (in radians) as constants// Initialize variables:
    uint32_t 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};
 
    h0 = 0x67452301;
    h1 = 0xefcdab89;
    h2 = 0x98badcfe;
    h3 = 0x10325476;
 
    // Pre-processing: adding a single 1 bit
    //append "1" bit to message    
    /* Notice: the input bytes are considered as bits strings,
       where the first bit is the most significant bit of the byte.[37] */
 
    // Pre-processing: padding with zeros
    //append "0" bit until message length in bit ≡ 448 (mod 512)
    //append length mod (2 pow 64) to message
 
    int new_len = ((((initial_len + 8) / 64) + 1) * 64) - 8;
 
    msg = calloc(new_len + 64, 1); // also appends "0" bits 
                                   // (we alloc also 64 extra bytes...)
    memcpy(msg, initial_msg, initial_len);
    msg[initial_len] = 128; // write the "1" bit
 
    uint32_t bits_len = 8*initial_len; // note, we append the len
    memcpy(msg + new_len, &bits_len, 4);           // in bits at the end of the buffer
 
    // Process the message in successive 512-bit chunks:
    //for each 512-bit chunk of message:
    int offset;
    for(offset=0; offset<new_len; offset += (512/8)) {
 
        // break chunk into sixteen 32-bit words w[j], 0 ≤ j ≤ 15
        uint32_t *w = (uint32_t *) (msg + offset);
 
#ifdef DEBUG
        printf("offset: %d %x\n", offset, offset);
 
        int j;
        for(j =0; j < 64; j++) printf("%x ", ((uint8_t *) w)[j]);
        puts("");
#endif
 
        // Initialize hash value for this chunk:
        uint32_t a = h0;
        uint32_t b = h1;
        uint32_t c = h2;
        uint32_t d = h3;
 
        // Main loop:
        uint32_t i;
        for(i = 0; i<64; i++) {

#ifdef ROUNDS
            uint8_t *p;
            printf("%i: ", i);
            p=(uint8_t *)&a;
            printf("%2.2x%2.2x%2.2x%2.2x ", p[0], p[1], p[2], p[3], a);
         
            p=(uint8_t *)&b;
            printf("%2.2x%2.2x%2.2x%2.2x ", p[0], p[1], p[2], p[3], b);
         
            p=(uint8_t *)&c;
            printf("%2.2x%2.2x%2.2x%2.2x ", p[0], p[1], p[2], p[3], c);
         
            p=(uint8_t *)&d;
            printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], d);
            puts("");
#endif        

 
            uint32_t f, g;
 
             if (i < 16) {
                f = (b & c) | ((~b) & d);
                g = i;
            } else if (i < 32) {
                f = (d & b) | ((~d) & c);
                g = (5*i + 1) % 16;
            } else if (i < 48) {
                f = b ^ c ^ d;
                g = (3*i + 5) % 16;          
            } else {
                f = c ^ (b | (~d));
                g = (7*i) % 16;
            }

#ifdef ROUNDS
            printf("f=%x g=%d w[g]=%x\n", f, g, w[g]);
#endif 
            uint32_t temp = d;
            d = c;
            c = b;
            printf("rotateLeft(%x + %x + %x + %x, %d)\n", a, f, k[i], w[g], r[i]);
            b = b + LEFTROTATE((a + f + k[i] + w[g]), r[i]);
            a = temp;


 
        }
 
        // Add this chunk's hash to result so far:
 
        h0 += a;
        h1 += b;
        h2 += c;
        h3 += d;
 
    }
 
    // cleanup
    free(msg);
 
}
 
int main(int argc, char **argv) {
 
    if (argc < 2) {
        printf("usage: %s 'string'\n", argv[0]);
        return 1;
    }
 
    char *msg = argv[1];
    size_t len = strlen(msg);
 
    // benchmark
    // int i;
    // for (i = 0; i < 1000000; i++) {
        md5(msg, len);
    // }
 
    //var char digest[16] := h0 append h1 append h2 append h3 //(Output is in little-endian)
    uint8_t *p;
 
    // display result
 
    p=(uint8_t *)&h0;
    printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h0);
 
    p=(uint8_t *)&h1;
    printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h1);
 
    p=(uint8_t *)&h2;
    printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h2);
 
    p=(uint8_t *)&h3;
    printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h3);
    puts("");
 
    return 0;
}

Can you please explain the line

msg[initial_len] = 128; // write the "1" bit

What do you license this code as? (MIT/Apache/GPL/Public Domain/other)

Can you please explain the line

msg[initial_len] = 128; // write the "1" bit

@PrarteekJoshi the original md5 code has a "padding fill" block, used when the last of the input block does not fill the current block, which starts with 0x80 (128) and is the rest zeros, so this code has just refactored that out

original code: https://people.csail.mit.edu/rivest/Md5.c

So is this code licensed under? yes, no ???

The preprocessing of your code seems to be wrong.

If you Encrypt this message "The quick brown fox jumps over the lazy dog" and check your printed preprocessed message, from your code, you get this

54 68 65 20 71 75 69 63 6b 20 62 72 6f 77 6e 20 66 6f 78 20 6a 75 6d 70 73 20 6f 76 65 72 20 74 68 65 20 6c 61 7a 79 20 64 6f 67 80 0 0 0 0 0 0 0 0 0 0 0 0 58 1 0 0 0 0 0 0

You notice that the length (0x158) in bits of the original text messages (43 Bytes long = 344 = 0x158) is not stored correctly at the last 64 bits. Your preprocessed message had to be like this.

54 68 65 20 71 75 69 63 6b 20 62 72 6f 77 6e 20 66 6f 78 20 6a 75 6d 70 73 20 6f 76 65 72 20 74 68 65 20 6c 61 7a 79 20 64 6f 67 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 58

Or is there something i am missing in the algo?.

Why does the result is different from md5sum command? The md5sum command is at git or other application.

You notice that the length (0x158) in bits of the original text messages (43 Bytes long = 344 = 0x158) is not stored correctly at the last 64 bits. Your preprocessed message had to be like this.

@OragonDre the message length should be little-endian

how to put the message on the line ?
i mean where to put the msg there ? thanks

it is with collision program?

Hi can you resolve my mistakes in php, i am writing like this,but i not shifting the bits

> (32 - ($c))))'); $h0; $h1; $h2; $h3; $msg = NULL; $r=array(0=>7,1=>12,2=>17,3=>22,4=>7,5=>12,6=>17,7=>22,8=>7,9=>12,10=>17,11=>22,12=>7,13=>12,14=>17,15=>22,16=>5,17=>9,18=>14,19=>20,20=>5,21=>9,22=>14,23=>20,24=>5,25=>9,26=>14,27=>20,28=>5,29=>9,30=>14,31=>20,32=>4,33=>11,34=>16,35=>23,36=>4,37=>11,38=>16,39=>23,40=>4,41=>11,42=>16,43=>23,44=>4,45=>11,46=>16,47=>23,48=>6,49=>10,50=>15,51=>21,52=>6,53=>10,54=>15,55=>21,56=>6,57=>10,58=>15,59=>21,60=>6,61=>10,62=>15,63=>21); $k=array(0=>0xd76aa478,1=>0xe8c7b756,2=>0x242070db,3=>0xc1bdceee,4=>0xf57c0faf,5=>0x4787c62a,6=>0xa8304613,7=>0xfd469501,8=>0x698098d8,9=>0x8b44f7af,10=>0xffff5bb1,11=>0x895cd7be,12=>0x6b901122,13=>0xfd987193,14=>0xa679438e,15=>0x49b40821,16=>0xf61e2562,17=>0xc040b340,18=>0x265e5a51,19=>0xe9b6c7aa,20=>0xd62f105d,21=>0x02441453,22=>0xd8a1e681,23=>0xe7d3fbc8,24=>0x21e1cde6,25=>0xc33707d6,26=>0xf4d50d87,27=>0x455a14ed,28=>0xa9e3e905,29=>0xfcefa3f8,30=>0x676f02d9,31=>0x8d2a4c8a,32=>0xfffa3942,33=>0x8771f681,34=>0x6d9d6122,35=>0xfde5380c,36=>0xa4beea44,37=>0x4bdecfa9,38=>0xf6bb4b60,39=>0xbebfbc70,40=>0x289b7ec6,41=>0xeaa127fa,42=>0xd4ef3085,43=>0x04881d05,44=>0xd9d4d039,45=>0xe6db99e5,46=>0x1fa27cf8,47=>0xc4ac5665,48=>0xf4292244,49=>0x432aff97,50=>0xab9423a7,51=>0xfc93a039,52=>0x655b59c3,53=>0x8f0ccc92,54=>0xffeff47d,55=>0x85845dd1,56=>0x6fa87e4f,57=>0xfe2ce6e0,58=>0xa3014314,59=>0x4e0811a1,60=>0xf7537e82,61=>0xbd3af235,62=>0x2ad7d2bb,63=>0xeb86d391); /* for($i=0;$i<=63;$i++) { echo $k[$i]=floor(232*abs(sin($i+1)))."
"; } */ /*for($j=0;$j<=63;$j++) { echo $k[$j]."
"; }*/ $h0 = 0x67452301; //A $h1 = 0xefcdab89; //B $h2 = 0x98badcfe; //C $h3 = 0x10325476; //D $new_len; for($new_len = $initial_len*8 + 1; $new_len%512!=448; $new_len++); $new_len /= 8; // $msg = calloc($new_len + 64, 1); $msg= memory_get_usage($new_len + 64); // memcpy($msg, $initial_msg, $initial_len); memory_get_peak_usage($msg); memory_get_peak_usage($initial_msg); memory_get_peak_usage($initial_len); //$msg[$initial_len] = 128; $msg=array($initial_len); $msg= 128; $bits_len = 8*$initial_len; // memcpy($msg + $new_len, $bits_len, 4); memory_get_peak_usage($msg + $new_len); memory_get_peak_usage($bits_len); memory_get_peak_usage(4); $offset; for($offset=0; $offset<$new_len; $offset += (512/8)) { $w = ($msg + $offset); #ifdef DEBUG printf("$offset: %d %x\n",$offset,$offset); $j; for($j =0; $j < 64; $j++) printf("%x ", $w[$j]); // puts(""); echo ""; #endif $a = $h0; $b = $h1; $c = $h2; $d = $h3; $i; for($i = 0; $i<64; $i++) { #ifdef ROUNDS $p; printf("%$i: ", $i); $p=& $a; printf("%2.2$x%2.2$x%2.2$x%2.2$x ", $p[0], $p[1], $p[2], $p[3], $a); $p=& $b; printf("%2.2$x%2.2$x%2.2$x%2.2$x ", $p[0], $p[1], $p[2], $p[3], $b); $p=& $c; printf("%2.2$x%2.2$x%2.2$x%2.2$x ", $p[0], $p[1], $p[2], $p[3], $c); $p=& $d; printf("%2.2$x%2.2$x%2.2$x%2.2$x", $p[0], $p[1], $p[2], $p[3], $d); //puts(""); echo ""; #endif $f; $g; if ($i < 16) { $f = ($b & $c) | ((~$b) & $d); $g = $i; } elseif($i < 32) { $f = ($d & $b) | ((~$d) & $c); $g = (5*$i + 1) % 16; } elseif($i < 48) { $f = $b^$c^$d; $g = (3*$i + 5) % 16; } else { $f = $c^($b|(~$d)); $g = (7*$i) % 16; } #ifdef ROUNDS printf("$f=%$x $g=%$d $w[$g]=%$x \n", $f, $g, $w[$g]); #endif  $temp = $d; $d = $c; $c = $b; //printf("rotateLeft(%x + %x + %x + %x, %d)\n", $a, $f, $k[$i], $w[$g], $r[$i]); printf("%x + %x + %x + %x, %d\n", $a, $f, $k[$i], $w[$g], $r[$i]); //$b = $b + LEFTROTATE(($a + $f + $k[$i] + $w[$g]), $r[$i]); $b = $b + LEFTROTATE.($a + $f + $k[$i] + $w[$g]); $a = $temp; } $h0 += $a; $h1 += $b; $h2 += $c; $h3 += $d; } unset($msg); } function main($argc,$argv) { global $x,$w; if ($argc < 2) { printf("usage: %s 'string'\n", $argv[0]); return 1; } $msg=$argv[1]; $len = strlen($msg); md55($msg,$len); $p; $p=&$h0; printf("%2.2$x%2.2$x%2.2$x%2.2$x", $p[0], $p[1], $p[2], $p[3], $h0); $p=&$h1; printf("%2.2$x%2.2$x%2.2$x%2.2$x", $p[0], $p[1], $p[2], $p[3], $h1); $p=&$h2; printf("%2.2$x%2.2$x%2.2$x%2.2$x", $p[0], $p[1], $p[2], $p[3], $h2); $p=&$h3; printf("%2.2$x%2.2$x%2.2$x%2.2$x", $p[0], $p[1], $p[2], $p[3], $h3); //puts(""); echo ""; return 0; } echo md55('',1); ?>

This crap is not working. Don't waste your time.

it work!

uint32_t bits_len = 8*initial_len; // note, we append the len
memcpy(msg + new_len, &bits_len, 4); // in bits at the end of the buffer````

These two lines are different from MD5.
The document says

A 64-bit representation of b (the length of the message before the
padding bits were added) is appended to the result of the previous
step. In the unlikely event that b is greater than 2^64, then only
the low-order 64 bits of b are used.

It works very nice!
For "The quick brown fox jumps over the lazy dog", it gives checksum 9e107d9d372bb6826bd81d3542a419d6, which is correct.
But I noticed you bench-marked the code (in main), so I guess you wanted it to be fast.

However, the next code fragment looks like a clumsy and time consuming way to calculate new_len, since it uses a loop to iterate over (potential) many bits, just to count them:

int new_len;
for(new_len = initial_len*8 + 1; new_len%512!=448; new_len++);
new_len /= 8;

To me, it doesn't seem a good practice to use loops just to calculate something very simple like this.
So I quickly translated above code into the code below, which does exactly the same calculation, but about 320 times faster (on an STM32H7):

int new_len = ((((initial_len + 8) / 64) + 1) * 64) - 8;

Sorry for this question but how can I run this program in big endian machine?
It tested on little endian and it worked but as I mentioned above: I need to try it in big endian.

Do i need to refactor this:

       // break chunk into sixteen 32-bit words w[j], 0 ≤ j ≤ 15
        uint32_t *w = (uint32_t *) (msg + offset);

Because as I know: Big endian read byte with different order. Is this right?
Thank you!

@danielvu1994 Signedness and endiness both don't matter if you're treating values as opaque black boxes generally speaking. But if you want to take the 4 bytes out of a 32 bit integer, for example, then the order you pull them out matters.

Thanks for checking my comment.
I did find a way to pull them follow order of big endian

printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h0);

these printf functions have only 4 place holders but 5 arguments are supplied, can someone explain that???

printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h0);

these printf functions have only 4 place holders but 5 arguments are supplied, can someone explain that???

Optimized too complex 'if' block:

            switch ((i >> 4) & 3)
            {
                case 0:    // (i < 16)
                    f = (b & c) | ((~b) & d);
                    g = i;
                    break;
                case 1:    // (i < 32)
                    f = (d & b) | ((~d) & c);
                    g = (5 * i + 1) % 16;
                    break;
                case 2:    // (i < 48)
                    f = b ^ c ^ d;
                    g = (3 * i + 5) % 16;
                    break;
                case 3:    // other
                    f = c ^ (b | (~d));
                    g = (7 * i) % 16;
                    break;
            }

printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h0);

these printf functions have only 4 place holders but 5 arguments are supplied, can someone explain that???

I think, we can omit h0 here, because h0 is our 32-bit word, which we are converting to p and printing by index.

printf("%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h0);
these printf functions have only 4 place holders but 5 arguments are supplied, can someone explain that???

I think, we can omit h0 here, because h0 is our 32-bit word, which we are converting to p and printing by index.

Thanks!!

I tested in VS2019 and it works with slight modification. I had a problem with calloc() and since I needed this for a specific application, I changed *msg declaration to something fixed:

uint8_t msg[128];
memset(msg, 0, 128);

and it works.

Thanks!