Using hard mathematical problems to prevent spam

This is not something new exactly. I first came up with this idea few years ago and it was published and discussed many times since then. The idea is quite simply so a lot of people came up with it 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 “proof of effort”. The last approach is based on making mail send procedure slower thus ineffective for a mass bulk spamming. It is about forcing sender to spend some of his time and computation resources to send a message and prove such effort to receiver. Besides advantages, all three approaches have their own drawbacks. For example: content filtering is a subject to false positive and false negative alarms; sender verification (e.g. SenderID) requires modification of existent network infrastructure and workflow and so on; The approach with a proof of effort (e.g. CPU-/memory-bound functions) seems to be more robust yet may simply be implemented on top of the current infrastructure or even be implemented entirely as client-to-client. But its effectiveness has a tendency to degrade in a long term because of hardware getting better.

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 which may be transparently adjusted according to any further hardware improvements without refractory.

Let 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) OR 1

This function recomputed for each recipient and for every message. In order to send a mail, the sender computes f(recipient||date||message) and factorize the result to p₁…p_n. If result f() itself is a prime number then alter the message and retry. The factorization of f() is a required send effort. The prime factors p₁…p_n sends together with the message in an extra header tag or an additional MIME section. Upon receiving, the recipient rejects messages without prime factors or if any factor is less than 3. Next it computes f(recipient||date||message) and multiplies p₁*p₂*…p_n. 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 detailed checks. This will effectively prevent a mailbox flooding attack when an attacker simply replays intercepted legitimate message to initiate out-of-space DoS.

The adjusting workload factor here is N - the size of an integer. The bigger N gives bigger workload at the sender’s side. N may easily be changed once workload needs to be adjusted in future.

Although, using hard mathematical problems to prevent spam is not a silver bullet. The actual solution to spam problem is beyond technical methods.