MD5 -- not digest::md5

[Oromis92]

hi! this post should be in a cryptography forum, but i'm sure the problem is in my syntax.... i wrote a simple script for encoding a string in md5 (not using digest::md5)

#!/usr/bin/perl

@r = ((7,12,17,22) x 4 , (5,9,14,20) x 4 , (4,11,16,23) x 4 , (6,10,15
+,21) x 4);

$k[$_] = (int(abs(sin($_+1))*(2**32))) for 0..63;

$H0 = 0x67452301;
$H1 = 0xefcdab89;
$H2 = 0x98badcfe;
$H3 = 0x10325476;

print "> ";
@msg = map(ord, split // , <>);
pop @msg;

$msgbin .= 0 . sprintf('%b',$msg[$_]) for 0..$#msg;
$length = sprintf('%b',length $msgbin);
$length = 0 . $length while length $length < 64;
$msgbin .= 1;
$msgbin .= 0 until length $msgbin == 448 % 512;
$msgbin .= $length;

for ($i=0,$j=0;$j<16;$i+=32,$j++) {
   $w[$j] = (unpack("N", pack("B32", substr("0" x 32 . (substr($msgbin
+,$i,32)), -32)))) % (2**32); 
}

$a = $H0;
$b = $H1;
$c = $H2;
$d = $H3;

for $i (0..63) {
   if ($i >= 0 && $i <= 15) {
      $f = (($b & $c) | ((~$b) & $d)) % (2**32);
      $g = $i;
   } elsif ($i >= 16 && $i <= 31) {
      $f = (($d & $b) | ((~$d) & $c)) % (2**32);
      $g = (5*$i + 1) % 16;
   } elsif ($i >= 32 && $i <= 47) {
      $f = ($b ^ $c ^ $d) % (2**32);
      $g = (3*$i + 1) % 16;
   } elsif ($i >= 48 && $i <= 63) {
      $f = ($c ^ ($b | (~$d))) % (2**32);
      $g = (7*$i + 1) % 16;
   }

$temp = $d % (2**32);
$d = $c % (2**32);
$c = $b % (2**32);
$b = ($b + (($a + $f + $k[$i] + $w[$g]) << $r[$i])) % (2**32);
$a = $temp % (2**32);

}
$H0 = unpack("H8", pack("N", ($H0 + $a)));
$H1 = unpack("H8", pack("N", ($H1 + $b)));
$H2 = unpack("H8", pack("N", ($H2 + $c)));
$H3 = unpack("H8", pack("N", ($H3 + $d)));

$digest = $H0.$H1.$H2.$H3;
print "> $digest\n";

and... WHY THIS DOESN?T WORK ???? T_T

md5("test) = 098f6bcd4621d373cade4e832627b4f6

myscript("test") = 56fb159ad06a6e220f579f97e5b2170f

uff...

i used this pseudocode: http://en.wikipedia.org/wiki/MD5#Pseudocode

but IT DOESN'T WORK !!

any hints ?

[roboticus]

Oromis92:

In a case like this when you're teaching yourself or improving code with a known solution, it's worthwhile to go ahead and use the original code as a "check" so you can tell when you've got it right and/or wrong. Something like:

use Digest::MD5 qw(md5);

my $message = ...blah blah blah...;

my $md5_test = my_md5($message);
my $md5_chek = md5($message);

print "MESSAGE: '$message'\n"
.     "TEST:    '$md5_test'\n"
.     "CHECK:   '$md5_chek'\n";
print "*** MISMATCHED ***\n" unless $md5_test ne $md5_chek;

sub my_md5 {
   ...blah blah blah...
}

This way, you know you're passing the same thing to the test code and the reference code. Then you can have some confidence in your test code. (Especially if you use multiple values to verify corner cases, fencepost errors and the like.)

...roboticus

[JavaFan]

I'm not sure what your point is. The OP already knows "it doesn't work". Assuming that Digest::MD5::md5 does "work", I fail to see what your suggestion offers the OP in finding his problem.

[roboticus]

JavaFan:

The program in the OP doesn't show both his code and the use of the reference code. I've seen far too many cases where a tiny difference is unnoticed (perhaps an extra blank, a fat-fingered character or something) that makes the difference. By calling both the reference function and the new function in the same program it's easier to confirm that the *exact* same data is passed to both.

In fact, I had that problem occur last year. For my son's Webelos troop we were working on encryption and decryption of messages. A similar mistake I made caused a problem, and we could decrypt only half of the message I had prepared.

...roboticus

[CountZero]

I wrote a simple script for encoding a string in md5

It is strange to say that the MD5 algorithm can be used as a form of encoding. MD5 is a one-way hashing function, with no simple way of decoding the result. In essence it can only be used as a digest.

[Oromis92]

ok, i followed all your hints...

#!/usr/bin/perl

use Digest::MD5 qw(md5 md5_hex md5_base64);
use strict;
use warnings;
use diagnostics;
use integer;

my @r = ((7,12,17,22) x 4 , (5,9,14,20) x 4 , (4,11,16,23) x 4 , (6,10
+,15,21) x 4);

my @k;
$k[$_] = (int(abs(sin($_+1))*(2**32))) for 0..63;

my $H0 = 0x67452301;
my $H1 = 0xefcdab89;
my $H2 = 0x98badcfe;
my $H3 = 0x10325476;

# my $H0 = 19088743;
# my $H1 = 2300300783;
# my $H2 = 267242392;
# my $H3 = 124076833;

print "> ";
my $msg = <>;
my @msg = map(ord, split // , $msg);
pop @msg;

my $msgbin;
$msgbin .= 0 . sprintf('%b',$msg[$_]) for 0..$#msg;;
my $length = sprintf('%b',length $msgbin);
$length = 0 . $length while length $length < 64;
$msgbin .= 1;
$msgbin .= 0 until length $msgbin == 448 % 512;
$msgbin .= $length;

my @w;
for (my $i=0,my $j=0;$j<16;$i+=32,$j++) {
   $w[$j] = (unpack("V", pack("B32", substr("0" x 32 . (substr($msgbin
+,$i,32)), -32)))) % (2**32); 
}

my $a = $H0;
my $b = $H1;
my $c = $H2;
my $d = $H3;

my $f;
my $g;

for my $i (0..63) {
   if ($i >= 0 && $i <= 15) {
      $f = (($b & $c) | ((~$b) & $d)) % (2**32);
      $g = $i;
   } elsif ($i >= 16 && $i <= 31) {
      $f = (($d & $b) | ((~$d) & $c)) % (2**32);
      $g = (5*$i + 1) % 16;
   } elsif ($i >= 32 && $i <= 47) {
      $f = ($b ^ $c ^ $d) % (2**32);
      $g = (3*$i + 1) % 16;
   } elsif ($i >= 48 && $i <= 63) {
      $f = ($c ^ ($b | (~$d))) % (2**32);
      $g = (7*$i + 1) % 16;
   }

my $temp = $d % (2**32);
$d = $c % (2**32);
$c = $b % (2**32);
$b = ($b + (($a + $f + $k[$i] + $w[$g]) << $r[$i])) % (2**32);
$a = $temp % (2**32);

}
$H0 = unpack("H8", pack("V", ($H0 + $a)));
$H1 = unpack("H8", pack("V", ($H1 + $b)));
$H2 = unpack("H8", pack("V", ($H2 + $c)));
$H3 = unpack("H8", pack("V", ($H3 + $d)));

my $digest = md5_hex($msg);
print "> $H0$H1$H2$H3\n> $digest\n";

but still doesn't work...

[youlose]

my $H0 = 0x67452301;
my $H1 = 0xefcdab89;
my $H2 = 0x98badcfe;
my $H3 = 0x10325476;

i think error is there, this values must be other. Read http://www.faqs.org/rfcs/rfc1321.html

[FunkyMonk]

I know nothing about the algorithm, and I haven't looked at the reference you gave, but are you sure about this line

$msgbin .= 0 until length $msgbin == 448 % 512;

448 % 512 is always going to be 448, so what's the point?

[Anonymous Monk]

Because you forgot strict/warnings :)

Use strict warnings and diagnostics or die

[Oromis92]

lol, ok ok
here's:


#!/usr/bin/perl

use strict;
use warnings;
use diagnostics;

my @r = ((7,12,17,22) x 4 , (5,9,14,20) x 4 , (4,11,16,23) x 4 , (6,10
+,15,21) x 4);

my @k;
$k[$_] = (int(abs(sin($_+1))*(2**32))) for 0..63;

my $H0 = 0x67452301;
my $H1 = 0xefcdab89;
my $H2 = 0x98badcfe;
my $H3 = 0x10325476;

print "> ";
my @msg = map(ord, split // , <>);
pop @msg;

my $msgbin;
$msgbin .= 0 . sprintf('%b',$msg[$_]) for 0..$#msg;;
my $length = sprintf('%b',length $msgbin);
$length = 0 . $length while length $length < 64;
$msgbin .= 1;
$msgbin .= 0 until length $msgbin == 448 % 512;
$msgbin .= $length;

my @w;
for (my $i=0,my $j=0;$j<16;$i+=32,$j++) {
   $w[$j] = (unpack("N", pack("B32", substr("0" x 32 . (substr($msgbin
+,$i,32)), -32)))) % (2**32); 
}

my $a = $H0;
my $b = $H1;
my $c = $H2;
my $d = $H3;

my $f;
my $g;

for my $i (0..63) {
   if ($i >= 0 && $i <= 15) {
      $f = (($b & $c) | ((~$b) & $d)) % (2**32);
      $g = $i;
   } elsif ($i >= 16 && $i <= 31) {
      $f = (($d & $b) | ((~$d) & $c)) % (2**32);
      $g = (5*$i + 1) % 16;
   } elsif ($i >= 32 && $i <= 47) {
      $f = ($b ^ $c ^ $d) % (2**32);
      $g = (3*$i + 1) % 16;
   } elsif ($i >= 48 && $i <= 63) {
      $f = ($c ^ ($b | (~$d))) % (2**32);
      $g = (7*$i + 1) % 16;
   }

my $temp = $d % (2**32);
$d = $c % (2**32);
$c = $b % (2**32);
$b = ($b + (($a + $f + $k[$i] + $w[$g]) << $r[$i])) % (2**32);
$a = $temp % (2**32);

}
$H0 = unpack("H8", pack("N", ($H0 + $a)));
$H1 = unpack("H8", pack("N", ($H1 + $b)));
$H2 = unpack("H8", pack("N", ($H2 + $c)));
$H3 = unpack("H8", pack("N", ($H3 + $d)));

my $digest = $H0.$H1.$H2.$H3;
print "> $digest\n";

[Anonymous Monk]

Heres how i modify
Read more... (3 kB)
On my machine without use integer; sum is fffffffffffffffffffffffffc51043f but with use integer;, sum is 67452301efcdab8998badcfe10325476

I think you need to unpack more carefully

N   An unsigned long in "network" (big-endian) order.

Pseudocode mentions little endian, so i think you want

V   An unsigned long in "VAX" (little-endian) order.

Hope that helps

[ikegami]

$b = ($b + (($a + $f + $k[$i] + $w[$g]) << $r[$i])) % (2**32);

Might not give the right result. "The result of overflowing the range of the integers is undefined" according to the docs. You need to do the proper masking *before* the shift, not after.

[mtve]

you may like to check this node

[pKai]

A good candidate to study the potential differences of your implementation against a working implementation might be the source of Digest::Perl::MD5 which is the pure Perl implementation the wrapper Digest::MD5 falls back to, when it can't load the XS implementation.