Catching Spam Campaigns in 64 Bits

A spammer writes one letter and sends it to ten thousand people. Each copy gets a different first name, a different parcel number, a different tracking link. To the person who reads one of them, it is obviously a form letter. To a mail server that hashes what it sends, it is ten thousand unrelated messages, because changing one character of the input changes the whole hash.

Mailingest, my mail platform, sends mail for its accounts and receives it for Buzontemporal's anonymous inboxes. Both ends attract exactly this kind of letter. So the question I needed to answer was narrow: how do you notice that the 800 messages that just went out are one campaign, when no two of them are byte for byte the same, and you can't afford to compare each one with all the others?

The answer turned out to be small. One 64-bit number per message, four Redis keys per message, and no extra round trip on the path that delivers mail.

Ten thousand strangers

The MinHash post told this story for bot fingerprints, and mail has the same shape. A cryptographic hash such as SHA-256 is designed so that a one-character change flips about half the output bits. That is what makes it good for checking that a file arrived intact, and useless for asking whether two letters are almost the same.

Comparing every message with every other one would see it, but that is quadratic: a thousand messages an hour is half a million comparisons, and the count grows with the square of the traffic. The constraints on a mail server are also stricter than on a web page. The check has to happen while the message is being accepted, it can't add a network round trip to that path, and if it fails for any reason the mail still has to go out. A broken spam signal that drops legitimate mail is worse than no signal.

A hash where close means close

SimHash, from Moses Charikar, flips the property around: similar inputs give similar outputs. It works by voting. Split the text into words and hash each word to 64 bits. Keep 64 counters, one per bit position. For every word, add one to a counter where the word's hash has a 1, and subtract one where it has a 0. At the end, each bit of the result is 1 where its counter came out positive.

A letter of 120 words casts 120 votes on every bit. Swap one name for another and you remove one vote and add a different one, on each of the 64 counters. Most counters are far from zero and don't change sign, so most bits stay put. Only the counters that were already close to zero can flip. Two letters with nothing in common, on the other hand, get unrelated tallies, and their hashes differ in about half the bits, the same as two random numbers.

This is the whole function in Mailingest, unabridged apart from the doc comment:

pub fn simhash(text: &str) -> Option<u64> {
    let mut votes = [0i32; 64];
    let mut words = 0;
    for word in text
        .split(|c: char| !c.is_alphanumeric())
        .filter(|w| !w.is_empty())
    {
        words += 1;
        let hash = word_hash(&word.to_lowercase());
        for (bit, vote) in votes.iter_mut().enumerate() {
            *vote += if hash >> bit & 1 == 1 { 1 } else { -1 };
        }
    }
    (words > 0).then(|| {
        votes
            .iter()
            .enumerate()
            .filter(|(_, vote)| **vote > 0)
            .fold(0u64, |acc, (bit, _)| acc | 1 << bit)
    })
}

The word hash is FNV-1a finished with the splitmix64 mixer, so every output bit depends on every byte. It is not Rust's standard hasher on purpose: that one may change between Rust versions, and a SimHash computed by last month's build has to land in the same place as one computed by today's.

The voters are single words, not runs of three words (the shingles that most near-duplicate papers use). I measured both on the same 120-word letter: changing the name or the number moved the hash 0 to 3 bits with single words, and up to 8 with three-word shingles, because one changed word sits inside three different shingles and casts three changed votes. Word order is lost this way, and that is fine here: the copies of a campaign share their words.

The demo below runs the same function, ported to TypeScript and checked against the Rust build on the same inputs, bit for bit. The original is the letter from Mailingest's unit test. Edit the copy, or try the variants.

Four bands, one bucket

A small distance between two hashes is still a comparison between two hashes, and comparing each new message with everything is the quadratic cost we started with. The second step removes the comparison. Cut the 64 bits into four bands of 16, and use each band's value as the name of a bucket. Two messages that share any band land in the same bucket, and the bucket does the counting.

The guarantee comes from the pigeonhole principle. If two hashes differ in 3 bits or fewer, those differences can touch at most three of the four bands, so at least one band is identical in both. Mail-merge copies are therefore certain to share a bucket. Unrelated letters are not: for two random hashes, the chance that a given 16-bit band matches is 1 in 65,536.

That diagram is the real "New name" variant from the demo: Maria instead of "customer", 3 bits apart, two of four bands intact. Three bits is the guarantee, not the limit. With the same letter I generated 1,000 copies with a different parcel number each, and 1,000 more that changed both the name and the number. The first set landed 0 to 5 bits from the original, the second 0 to 7, and every one of the 2,000 still shared at least one band with it. Edits past the guarantee still tend to be caught, they just aren't promised.

Counting a bucket without storing it

Each bucket has to answer one question: how many different messages fell in here recently? Storing every message id would work and would grow with the campaign. A HyperLogLog answers the same question in at most 12 KB per key, with a standard error of 0.81%, however many ids go in. And because it counts distinct members, a message that is redelivered after a timeout is counted once.

So for every message that has text, Mailingest computes the SimHash and makes four PFADD calls, one per band, adding the message id to the key for that band's value. Outbound mail is scoped per account (account:<id>), so one customer's newsletter never mixes with another's. Inbound mail to Buzontemporal's domains is scoped as temp, because there the campaigns come from outside.

for (band, bucket) in bands(simhash) {
    let key = mailingest_core::keys::abuse_lsh(scope, band, bucket, self.window);
    pipe.cmd("PFADD").arg(&key).arg(message).ignore();
    pipe.cmd("EXPIRE")
        .arg(&key)
        .arg(TTL_SECS)
        .arg("NX")
        .ignore();
}

Campaigns are a recent thing, so the keys carry the hour they belong to, and each lives for two hours. A read asks for the union of this hour's key and the previous hour's (PFCOUNT over both), which gives distinct messages in the last one to two hours. No job rotates anything; old keys simply expire. A Top-K sketch next to them keeps the ten biggest buckets, so the question "which campaigns are running right now?" doesn't need a scan.

The same machinery carries the other abuse signals. HyperLogLogs count distinct recipients per account, per sender address and per inbound network, which is how a dictionary attack shows up (one network trying a thousand addresses that don't exist). A Count-Min Sketch plus a Top-K count volume per inbound network, per sender domain and per outbound account. All of it is native in Redis 8, which production already runs.

No extra round trip

The constraint from the start was that this costs the mail path nothing it didn't already pay. Every message already makes a pipelined trip to Redis: the outbound anomaly check on the way out, the per-recipient counters on the way in, the quota reservation for temporary mailboxes. The signals ride in those pipelines. On the way in, folding them in also merged the counters: from two pipelines per accepted recipient to one per message (measured with three recipients: one pipeline carrying all 18 counters plus the signals).

The sketches have to exist before they can be updated, and creating them must never break the trip they ride on. One Lua script does both, and every Redis call inside it goes through redis.pcall, which returns errors instead of raising them. A Redis without the sketch commands, or one that runs out of memory, records nothing and the message goes on. That is the rule for the whole feature: a signal that can't be recorded is lost, and the mail it describes is not.

Measuring is the easy half

As of today, none of this refuses a single message. The biggest clusters show up in an admin endpoint, GET /v1/admin/abuse/top, and as a Prometheus gauge, mailingest_abuse_top, refreshed every minute with at most ten series per signal. I can see a campaign forming. Mailingest does nothing about it yet.

That is the part I'm building now, and it is the harder one, because the numbers above were chosen for the attacker and every one of them also describes someone legitimate. The design document already proposes where the lines could go:

Look at the first row from the other side. A shop that sends its weekly newsletter to 5,000 subscribers sends 5,000 near-identical messages in an hour, by design. A SimHash can't tell a newsletter from a phishing run. It only knows they are both one letter sent many times, which is true of both. Whether that letter is a problem depends on who sends it and to whom: an account that always sends 5,000 on Thursdays is normal, the same account sending 5,000 on a Tuesday at 3 a.m. after a password reset is not.

So the order is fixed. First, warnings only: the thresholds fire into the logs and the metrics, and I look at what they would have done to real accounts. Then thresholds per account, relative to that account's own history rather than one global number. Only after that, the pause. The 451 to a network doing a dictionary attack on temporary domains is the safest of the four (a legitimate sender retries a 451 later, and no legitimate sender guesses a thousand addresses), so it is likely to go first.

There was another option on the table for this phase: t-digest, also native in Redis 8, which would merge latency percentiles across replicas instead of each one keeping its own. It is a better dashboard. Acting on these signals protects the reputation of the sending IPs, and on a mail platform that reputation is the product: once a provider starts filing your mail as spam, every customer pays for one bad account. The dashboard can wait.

What 64 bits buys

Strip it back and the trade is this. Mailingest keeps no copy of the mail it measures, compares no message with any other, and adds no trip to Redis. In exchange it learns one thing per message: how many others in the last hour or two were, word for word, nearly the same letter. That is exactly what a spammer can't avoid. They can change every name and every number, and the votes barely move, because the letter is the point of the campaign.

What the 64 bits can't tell you is whether the letter is wanted. That part needs the account's history, a few weeks of warnings and a person looking at them, and no sketch fits it into a fixed number of bytes.