comment on

A Message Authentication Code (MAC) is used to make sure that a given piece of data came from the proper source, and wasn't modified by an attacker. This is sometimes used, for example, by a website to make sure that users aren't messing around with their cookies. A simple strategy is to hash the cookie data with a secret piece of information ($hash = md5($secret . $data)) and then send both $hash and $data in the cookie. Unfortunately, this is insecure. The code below uses a hash chaining attack to compute the MAC of the data with some stuff tacked onto the end. The same technique works against SHA1 and RIPEMD160. To be safe from this and other attacks, you should use a MAC module such as Digest::HMAC_MD5.

Here's the sample output. "Good" is a cookie computed by the website. "Bad" is a cookie computed by the attacker and sent back to fool the website.

Good:  bc331ada0ff69cd57b90af24bf049969:this_data_is_ok
Bad:   60438c4d1f6b02c1190e205fd95c1bb4:this_data_is_ok%80%00
%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00
%00%00%00%00%00%00%00%00%C8%00%00%00%00%00%00%00this_is_bogus
Check: 60438c4d1f6b02c1190e205fd95c1bb4 valid data!

The bad cookie has a bunch of garbage in it -- that's the MD-strengthening padding applied by MD5. Will your code notice the garbage and reject the cookie? Why take that chance? Instead, just use a proper MAC algorithm that avoids this vulnerability from the start.

The attacker needs to know the length of the secret used to create the MAC. That's easy enough to find, if he can use your website as an oracle to tell him whether a particular forged MAC is valid or not.

use strict;
use warnings;
use integer;
use Digest::MD5 qw( md5 );
use URI::Escape;

# Good guys compute this
my $secret = "don't tell";
my $good_data = "this_data_is_ok";
my $good_hash = md5($secret . $good_data);
print "Good:  ", unpack("H*", $good_hash), ":",
    uri_escape($good_data), "\n";

# Bad guys compute this
my $bad_stuff = "this_is_bogus";
my $bad_data = $good_data
    . padding(length($secret) + length($good_data))
    . $bad_stuff;
my $bad_hash = md5_update( $good_hash,
    $bad_stuff . padding(64 + length($bad_stuff)) );
print "Bad:   ", unpack("H*", $bad_hash), ":",
    uri_escape($bad_data), "\n";

# Good guys get fooled
my $check_hash = md5($secret . $bad_data);
print "Check: ", unpack("H*", $check_hash), " ",
    ($check_hash eq $bad_hash ? "valid data!" : "INVALID"), "\n";

sub padding {
  my ($len)   = @_;
  my $lastblk = ($len + 9) & 63;
  my $padlen  = $lastblk ? 64 - $lastblk : 0;
  return "\x80" . ("\0" x $padlen) . pack("V2", $len*8, 0);
} # padding

BEGIN {
  my @c = (
      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,
  );
  sub md5_update {
    my ($hash, $data) = @_;
    my @h = unpack "V4", $hash;
    my @x = unpack "V16", $data;
    my ($a, $b, $c, $d) = @h;
    my ($t, $r);

    # round 1
    for (0 .. 15) {
      $t = $a + $c[$_] + $x[$_] + ((($c^$d)&$b)^$d);
      $r = (7, 12, 17, 22)[$_ & 3];
      $t = ($t<<$r) | ($t>>(32-$r)) & ~(~0<<$r);
      $a = $d; $d = $c; $c = $b; $b += $t;
    }

    # round 2
    for (16 .. 31) {
      $t = $a + $c[$_] + $x[($_*5+1)&15] + ((($b^$c)&$d)^$c);
      $r = (5, 9, 14, 20)[$_ & 3];
      $t = ($t<<$r) | ($t>>(32-$r)) & ~(~0<<$r);
      $a = $d; $d = $c; $c = $b; $b += $t;
    }

    # round 3
    for (32 .. 47) {
      $t = $a + $c[$_] + $x[($_*3+5)&15] + ($b^$c^$d);
      $r = (4, 11, 16, 23)[$_ & 3];
      $t = ($t<<$r) | ($t>>(32-$r)) & ~(~0<<$r);
      $a = $d; $d = $c; $c = $b; $b += $t;
    }

    # round 4
    for (48 .. 63) {
      $t = $a + $c[$_] + $x[($_*7)&15] + ($c^($b|~$d));
      $r = (6, 10, 15, 21)[$_ & 3];
      $t = ($t<<$r) | ($t>>(32-$r)) & ~(~0<<$r);
      $a = $d; $d = $c; $c = $b; $b += $t;
    }

    $h[0] = ($h[0] + $a) & 0xffffffff;
    $h[1] = ($h[1] + $b) & 0xffffffff;
    $h[2] = ($h[2] + $c) & 0xffffffff;
    $h[3] = ($h[3] + $d) & 0xffffffff;
    return pack "V4", @h;
  } # md5_update
}
[download]

In reply to MAC Attack by no_slogan

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Problems? Is your data what you think it is?
	PerlMonks