Using your friends' hashed addressbooks to fight spam

LOAF is a novel approach to spam-filtration. The idea is that you send a one-way-hashed version of your entire address book along with every message you send. This allows all your friends to create a privacy-complete list of all the people in their friends' trusted correspondants' lists. When mail comes in, it is flagged as originating with one of your known correspondants, or one of their known correspondants, or a total stranger, helping you prioritize your inbox. The authors of the paper have written a list of known attacks against this system:

Ex-Girlfriend attack
While a LOAF file is hard to reverse-engineer, it's designed to answer the question "did this person ever send email to X?". In some cases, that's a question you don't want people to be able to ask. To avoid exposing the fact that you are corresponding with certain people, you have three options:

– Don't use LOAF.

– Create a blacklist of addresses for LOAF to pass over when generating a filter.

– Set a false positive rate high enough to give you plausible deniability: "Oh, honey, don't be ridiculous. I certainly never wrote to X, that must be a false positive" will work, but you must be sure to read the caveat about keeping a constant filter size in Dictionary attack below.

Marc Canter attack
The technique is similar to getting a perfect score on the SAT by filling in every oval on the SAT exam sheet – you provide a Bloom filter consisting entirely of ones, and every email address checked against it will match.

Sending an overloaded filter does not help you get accepted by new correspondents, but once you are added to their list, it will make you appear to know everyone. One possible solution to this spoofing problem is to impose a maximum density.


(via Kottke)