Using hard mathematical problems against spam
Dec 13, 2006 by Ilya Levin
This idea is not something new exactly. I first came up with it a few years ago, and it was published and discussed many times since then. The idea is quite simple, and many people came up with the same idea all by themselves as well. I claim neither rights nor priority for this idea.
There are three major approaches to prevent spam today: content filtering, sender verification and a "proof of effort."
The last method is based on making mail send procedure slower and hence ineffective for a mass bulk spamming. It is about forcing a sender to spend some of his time and computation resources to send a message and prove such effort to a receiver.
Besides advantages, all three approaches have their drawbacks.
Content filtering is subject to false positive and false negative alarms.
Sender verification, like SenderID, requires modification of existent network infrastructure and workflow and so on.
The approach with a "proof of effort" (e.g. CPU-bound and memory-bound functions) seems to be more robust. Plus it may be simple implemented on top of the current infrastructure or even be implemented entirely as client-to-client. However, the hardware is getting better, so the effectiveness of this method has a tendency to degrade in the long term.
Hard mathematical problems such as prime factoring or computing discrete logarithm may be used instead of bound functions. The result would be simpler spam preventing schemes, transparently adjustable according to any further hardware improvements without refactoring.
Let's describe the proposed method on example of prime factoring problem.
Assume f() is a one-way function that return N-bit odd integer, for example:
f(x) = Truncate(SHA1(x), N) ∨ 1
This function recomputed for each recipient and each message. To send mail, the sender must compute f(recipient||date||message) and factorize the result to p1…pn. If the result of f() itself is a prime number then sender must alter the message and retry.
The factorization of f() is a required sending effort.
The prime factors p1…pn should be sent together with the message in an extra header tag or an additional MIME section.
When receiving the message, the recipient reject messages without prime factors or if any of these factors is less than 3.
Next, the recipient computes f(recipient||date||message) and multiplies p1*p2*…pn. If both results are same and the size of the multiplication product is N bits, then the message is accepted, else the message is rejected.
The recipient may also cache f() values of received messages for some period and reject all new incoming messages with the same f() without thorough checks. The rejection will prevent a mailbox flooding attack when an attacker replays an intercepted legitimate message to initiate out of space denial of service.
The adjusting workload factor here is N - the size of an integer. Bigger N gives heavier workload at the sender's side. We may easily change the size once we need to adjust workload in future.
Although, using hard mathematical problems to prevent spam is not a silver bullet.
The actual solution to the spam problem is beyond any technical methods.