a Message-ID proposal

[Edmund GRIMLEY EVANS <edmundo@xxxxxxxx>]

In filtering e-mail it can be quite useful to recognise one's own
Message-IDs. For example, you can filter out the failure report for a
message you actually sent from the hundreds of bounce messages caused
by a spammer using your address as the envelope sender; or you can
automatically whitelist people who put one of your Message-IDs in the
In-Reply-To field. (If you're very cautious you'll use a different
form of Message-ID in messages to public mailing lists.)

Recognising the format of a Mutt Message-ID is good enough in most
cases, but spammers have been known to mention "mutt" in the
User-Agent field, so it's not impossible that one day a spammer will
use Message-IDs that look like Mutt ones.

You could make it much harder to fake your Message-IDs by using a
cryptographic checksum. If you're using crypto you might as well at
the same time disguise the process ID and counter, which are
potentially a privacy problem; in a 2001 posting to mutt-dev it was
rather dramatically described as "spyware".

So, here's a proposal:

Message-ID = timestamp . uniquifier . signature

uniquifier = encrypt(secret1 . timestamp, counter. pid);

signature = checksum(secret2 . timestamp . uniqifier)

encrypt(x, y) = checksum(x) ^ y

If secret2 comes from a Mutt variable you could probably use hooks to
modify it when you're sending to a mailing list. You can generate
secret1 randomly as you don't ever need to decode the uniquifier.

Does anyone think this might be useful?

Note: If an attacker got hold of one of your Message-IDs then they
could use it for spamming you, but they couldn't easily generate any
other Message-IDs from it, so you could either blacklist the stolen
Message-ID or just wait for it to expire: the Message-ID contains a
date. Possible extension: specify an expiry date in the Message-ID ...

See below for a prototype Perl implementation. The uniquifier is
encoded in base32 because apparently some people compare Message-IDs
with a case-insensitive comparison, but the signature is encoded in
base64 to facilitate computing it with standard library functions as
the spam filter has to do this same computation.

Edmund

-----------------------------------------------------------------------

#!/usr/bin/perl -w

# Generate some Message-IDs.
# Give the SECRET as argument.

use Digest::MD5 qw(md5), qw(md5_base64);

$secret = shift(@ARGV) || "";

$Base32 = "0123456789abcdefghijklmnopqrstuvwxyz";

$rand = "";
foreach (1..5) {
    $rand .= rand(2**32) . ".";
}

$count = 0;

print &msgid(), "\n";
print &msgid(), "\n";
print &msgid(), "\n";

sub msgid {
    my ($sec,$min,$hour,$mday,$mon,$year,$wday,$yday) = gmtime(time);
    my $time = sprintf("%04d%02d%02d%02d%02d%02d",
                       $year + 1900, $mon + 1, $mday, $hour, $min, $sec);
    my $pid = $$;

    my $pad = md5("$rand$time." . int($pid / 2**32));
    my ($countx, $pidx) = unpack('CN', $pad);
    $countx ^= $count;
    $pidx ^= $pid;
    my $uniq = &base32(($countx << 2) | (($pidx >> 30) & 3));
    foreach my $i (1..6) {
        $uniq .= &base32($pidx >> (30 - $i * 5));
    }
    my $sig = substr(md5_base64("$secret.$time.$uniq"), 0, 4);
    $sig =~ tr!/!$!;
    ++$count;
    "$time.$uniq.$sig";
}

sub base32 {
    my ($x) = @_;
    substr($Base32, $x & 31, 1);
}

-----------------------------------------------------------------------

#!/usr/bin/perl -w

# Check a Message-ID.
# Usage: checkid SECRET Message-ID

use Digest::MD5 qw(md5), qw(md5_base64);

($secret, $msgid) = @ARGV;

$msgid =~ /^([0-9]{14}\.[0-9a-x]{7})\.([A-Za-z0-9\+\$]{4})$/ ||
    die "Bad Message-ID\n";

($x, $sigx) = ($1, $2);

$sig = substr(md5_base64("$secret.$x"), 0, 4);
$sig =~ tr!/!$!;

if ($sig eq $sigx) {
    print "Good Message-ID\n";
}
else {
    print "Bad signature; shoud be: $x.$sig\n";
}