Universal authentication via these methods is easily achievable as it requires only a onetime software update by the relatively miniscule number of developers of the MTA programs, email clients, and web browsers that are in common use.

---

1.     Introduction

Malicious behavior over the internet is fostered by the inability to routinely authenticate the computers involved in a transaction.  In the absence of special measures an email receiver can only be certain of the IP address of the final MTA to handle an email, and even this MTA’s identity will be obscured if a dynamic IP address is used.  An email receiver is also unable to authenticate the personal computer that sent the email.  Website operators are also unable to authenticate the personal computer used to fill out a webpage registration for a service such as a free webmail account.

This paper describes two related and synergistic techniques to authenticate all of the computers used in an internet transaction.  This system avoids the pitfalls of other techniques by meeting the following criteria:

2.1     MTAs Listed in the Header are Authenticated despite Subsequent Forwarding

To illustrate this method we will look at the scenario of three different mail servers named MTA#1, MTA#2, and MTA#3.  We will imagine that an email is sent to MTA#1, then forwarded to MTA#2, and finally forwarded to MTA#3 before reaching the email receiver.  With conventional MTA software (meaning software that does not support MTA Authentication) the receiver can only be certain that the email came via MTA#3 as every other fact about the email can be fabricated.

Now imagine that these MTAs have upgraded to versions of software that do support MTA Authentication.  After the upgrade MTA 1, 2, and 3 each autonomously generate a single public/private key pair and each MTA uses its private key to sign all outgoing email.  Absolutely no manual configuration is required for this process so the MTA administrators can remain oblivious to this entire process.

Once again an email is sent to MTA#1, forwarded to MTA#2, and finally forwarded to MTA#3 before reaching the destination email system.  This time, however, each MTA has signed the email before forwarding it to the next MTA.  The anti-spam software of the destination email system will now directly query MTA#1 to attain its public key and verify the digital signature of MTA#1 present in the email envelope.  The destination email system now has absolute certainty that the email originated from MTA#1 and that the email has not been altered since leaving MTA#1.

There actually is no need to even bother checking the signature of MTA#2 since the receiver knows that the email cannot have been modified since leaving MTA#1.  The signature of MTA#2 will only need to be checked if MTA#1 had not signed the email – in this case the integrity of the email will be judged by the reputation of MTA#2.

2.1.1     Domains with SPF Records Can Finally Be Authenticated Despite Forwarding

Currently the most commonly used domain authentication protocol is Sender Policy Framework (SPF), whereby domain administrators publish a list of all of their domain’s MTAs.  One of the great flaws of SPF is that forwarding makes it impossible to use SPF records to authenticate the domain.

By using MTA Authentication email forwarded from SPF compliant domains will always receive an SPF PASS because the receiver is now absolutely sure that email originated from the first MTA listed in the email header and that the email was not altered while in transit.

2.1.2     MTA Authentication Compliant Servers Can Never Be Spoofed

Now we will imagine that a spam email arrives with MTA#1, MTA#2, and MTA#3 in the header but this time none of the MTAs has a signature.  The receiver will still query the MTAs listed in the header about their signing policy.  If any of these MTAs confirms that it always signs its email then the email receiver will know that the absence of a signature is proof that the email is spam.

Example:  A user receives a forwarded email claiming to originate from Citibank.  The IP address of the first MTA listed in the header corresponds to a true Citibank MTA but the second MTA does not.  The email is not signed.  The user now queries the IP address of the Citibank MTA and this MTA responds with the message “All outgoing email has been signed for the last 15 months”.  The email receiver can now mark this unsigned email as spam.

 

2.2     Dynamic IP Addresses Cease To Be a Problem

IP address reputation is a fundamental anti-spam tool.  Databases such as Senderbase.org and DNS black lists are a valuable tool used by all anti-spam services.  These databases are ideal for static IP addresses but they are often frustrated by dynamic IP addresses.  A dynamic IP address may have been used by a spammer one day and an honest user the next.  It is often difficult for these databases to even know if an IP is dynamic.

MTA Authentication solves the problem of tracking the reputation of a server that uses a dynamic IP addresses since a server’s public key never changes.  Existing IP address reputation databases will assign reputation scores to public keys the same way they currently assign reputation scores to IP addresses.  For the first time these reputation databases will provide the full reputation history of a server despite its use of a dynamic IP address.

As a corollary IP address reputation databases will easily know if an IP address is dynamic because only a dynamic IP address will rotate through different public keys.

Example:  An individual uses his laptop as an MTA to send the email for his personal domain.  The laptop computer uses a new dynamic IP address every day, so consequently IP reputation databases are more likely to misclassify his email as spam.  However, the laptop’s MTA software has MTA Authentication functionality and for the past year the reputation of the laptop’s public key has been building in the Senderbase.org database.  The laptop now sends an email to a receiving mail server and this server queries the laptop for its public key (this can occur even before the receiving mail server has finished accepting the email).  The email receiver can successfully review one year’s worth of reputation data for this laptop-based MTA despite its use of a dynamic IP.

 

2.3     Reducing the Frequency of Broken Signatures due to Content Modification

Content modification to email while in transit can break a digital signature.  Legitimate advertisements or certain notifications by mailing lists or antivirus companies are sometimes added as a footer to the email while in transit; the digital signature will not match the email if the addition of these footers is not accounted for. To address this problem the length of the original message will always be designated in the header; the receiver can now exclude the footer and only check the signature against the original email.  Message length designation currently exists as an optional feature of DKIM, but it will be the default for MTA Authentication as well as for the process describe in section 3 of this paper.

Receiving mail systems, before delivering an email to a user’s inbox, should excise footers that are added after the email is signed unless it is determined that the footer itself is not spam.

2.4     A Proposal for a New SPF Designation

Many domains accurately list all of their MTAs in their SPF record.  Ideally these domains would instruct receiving email systems to reject all mail that is not from one of their listed servers by placing a ‘-all’ tag in their SPF record.  In reality most domains realize that if they use a ‘-all’ tag and if their outgoing email gets forwarded then their email will be issued an SPF FAIL.  Fear that this forwarded email will never reach the receiver forces these mail systems to apply the ambiguous tag of ‘~all’ or ‘?all’.  The receiving email system now has the burden of figuring out how to handle this ambiguity.  Fear of listing ‘-all’ results in more spam reaching the receiver and more backscatter in the form of bounces for the domain in question.

MTA Authentication ensures that forwarding will never break SPF.  In response to this improvement a new SPF tag should be established that will effectively mean the following:

“All of our servers use MTA Authentication so use ‘-all’ if you check signatures.  If you do not check signatures then use ‘?all’ (or ‘~all’).”

This will eliminate the sender’s concern that forwarded mail will be issued an SPF FAIL.  Receivers will receive less spam and less backscatter will be created because receivers will no longer send bounces to spoofed addresses.

2.4.1     MTA Authentication Combined with SPF Renders a ‘DKIM Equivalent’

Combining an SPF record with MTA Authentication reproduces the security provided by all common deployments of DKIM.  Effortlessly transforming SPF into a ‘DKIM equivalent’ is significant as the number of domains that deploy DKIM is only a fraction of the number that deploy SPF [1] [2].

2.5     Signing All Emails will not Overburden an MTA

Concerns that signing every outgoing email will result in a debilitating amount of CPU overhead for a mail server are unfounded.  It was appreciated back in 2004 when DomainKeys was launched that the additional burden on MTAs was minimal, and processors today are much faster [3].  It is nearly impossible to detect the increased burden of signing emails against the background of common mail server tasks such as anti-virus scans [4].

---

3.     personal computer Authentication

Personal Computer Authentication uses digital signatures so that email receivers can verify the reputation of the personal computer that originally sent the email.  The digital signature also guarantees that the email has not been altered while in transit.  It promises to control spam sent via botnets while remaining unnoticed by individual users.  In addition this technology will also be incorporated into web browsers to control malicious behavior on the Web; one benefit of this will be that the need for CAPTCHA will be eliminated.

Prior proposals [5] [6] to limit the amount of abusive behavior emanating from individual computers have often centered on a fixed payment for each internet transaction, typically in the form of a time-consuming computation. These proposals met with failure in part because virtually all spam is sent from botnets [7].  A per transaction payment large enough to cripple a botnet would be intolerable for legitimate users.  Personal Computer Authentication also uses a payment system to limit abuse emanating from individual computers, but critical differences that make it practical include:

This section discusses a few of the most universal and convenient ways to securely issue these secret ID numbers.  Obviously there are many possible distribution methods.

3.1.1     Transparently Retrofitting Computers with Secret ID Numbers

Most desktops are Windows computers and each already has a product key in excess of 128 bits that is known only to Microsoft.  A hash of this product key can be used as the secret ID number for Personal Computer Authentication.  Microsoft can provide the global database with a comprehensive list of these hashes to be used as secret ID numbers.

Apple can securely retrofit Macintosh computers with unique secret ID numbers generated from their unique hardware components.

Linux personal computers or personal computers with pirated versions of Microsoft Windows will acquire a new secret ID number at the time that the personal computer’s email client and/or web browser is upgraded to support Personal Computer Authentication.  The personal computer must then perform a time-consuming computation, and completion of this time-consuming computation will activate the secret ID number.  Sharp disparities across computer systems raises concerns that proof-of-work computation time will vary greatly between users with high-end and low-end systems.  The use of a memory-bound computation, as opposed to a processor-bound computation, will markedly minimize the disparity across systems [8].  Botnets will not be able to acquire large numbers of newly issued secret ID numbers (see section 3.4.1).

3.1.2     Future ID Numbers can be distributed via Network Cards

A simple addition to a hardware standard will ensure that every future computer is shipped with a secret ID number.  Every network card has a ROM chip with a unique MAC address burned into it.  Manufactures can burn a random 128 bit number into the network card ROM to serve as a secret ID.  For enhanced security the manufacturers should only maintain and release a list of the hashes of these secret ID numbers.

Network card standards are regulated by the Institute of Electrical and Electronics Engineers (IEEE) [9].  The IEEE can amend the network card standard to stipulate that all network cards include these numbers.

3.2     Second Step:  Upgraded Email Clients will Sign Every Email Sent from a Personal Computer

Personal Computer Authentication is an update to email clients that will place digital signatures on all outgoing email.  These digital signatures are unique for the following reasons:

3.2.1     The Mechanism of Personal Computer Authentication for Email Clients

Personal Computer Authentication Clients works via the following steps (see Figure 2):

Figure 2.  Personal Computer Authentication for Email Clients.  The email client creates a signature by combining the message hash and the secret ID and using a public key to encrypt them.  The Receiving Server will send this signature to the Global database and in return will receive the Personal Computer’s reputation report.

Personal Computer Authentication does not directly authenticate the ‘From’ address but rather it allows for the reputation of the sending personal computer to be assessed directly.  Spam originates from compromised computers, so authenticating the personal computer that sent an email may prove to be more useful than authenticating the ‘From’ address.

Variations of this technique (e.g. issuing each personal computer its own cryptographic key instead of a secret ID number) are also possible.  The subtle differences in function that these variations would entail do not justify exposition within the confines of this paper.

3.2.2     Near Universal Participation Requires Only a Few Major Players

Personal Computer Authentication requires an updated email client; otherwise no participation or even awareness is required by the sender.  The email client market is dominated a handful of vendors so near universal participation will be achieved with the participation of just a few major players.

3.3     Controlling Malicious Activity over the Web with Personal Computer Authentication by Web Browsers

Personal Computer Authentication will be implemented by the web browser using the same public key, secret ID number, and global database that is also used by the computer’s email client as described in sections 3.1 and 3.2.  The ability of a website’s administrator to evaluate the reputation of the personal computer accessing a free service will be of tremendous utility in controlling abuse such as spammer webmail registrations and blog spam.

3.3.1     Personal Computer Authentication via Web Browsers Will Allow for the Elimination of CAPTCHA

CAPTCHA are currently essential despite the following flaws:

The modicum of security provided by CAPTCHA will be replaced by the higher level of security provided for by Personal Computer Authentication.

3.3.2     The Mechanics of Personal Computer Authentication by Web Browsers

We will start with the premise that the small handful of vendors for the commonly used web browsers have instituted this functionality via a onetime update. A user will bypass CAPTCHA while registering for a free online service such as a webmail account via the following process (see Figure 3):

The webmail provider will continue to give feedback to the global database regarding the activity of that particular email account and the global database will continue to provide updated reputation reports upon request.  By example a zombie may have used a single ID number to slowly register a large number of webmail accounts across several providers before attempting to simultaneously send large quantities of spam from these multiple accounts – this attempt will not succeed as the central database will report this activity back to the webmail providers.

Almost every computer user in the world uses a browser developed by one of five vendors, and the most commonly used email clients are also developed by some of these same vendors.  Subsequently near universal adoption of Personal Computer Authentication will be rapidly realized with the participation of a handful of participants.

3.4     Countering Infected Computers

Spammers will inevitably infect a large number of computers and steal their secret ID numbers.  Any stolen secret ID will be deactivated soon after it is used to send spam and the computer user will be alerted to the infection because their emails sent via clients will be rejected with codes such as:

550 5.7.1 Your email is rejected because your computer may be infected with a virus.

The computer user will encounter a similar security warning when attempting to use the web browser to access web services that make use of Personal Computer Authentication.

3.4.1     Replacing a Compromised Secret ID Number

The process of replacing a secret ID number will obligatorily start with the user’s operating system downloading the most recent OS and web browser security patches – after this a new secret ID number will be downloaded.  The personal computer may be required to perform a onetime time-consuming computation to activate the secret ID.

Recall that conventional pay-per-transaction schemes to limit spam are essentially futile as botnets can easily ‘pay’ any computational ‘fee’ as the computation time must remain brief so as to remain tolerable for legitimate users.  A pay-per-identity scheme, however, is profoundly more resistant to spammer exploitation.  In a pay-per-identity scheme a computer that has been cleansed of malware will need to do a time-consuming computation only once for the lifetime of that computer (unless it is infected again).  In contrast a zombie computer will invalidate its secret ID number almost instantly after it is used to send spam, forcing the zombie to devote almost all of its time to computation instead of sending spam. The goal is not to make it absolutely impossible for a botnet to send spam, but rather to decrease by several orders of magnitude the amount of spam it can send. 

Example: A zombie computer must perform a two hour computation to generate a new secret ID.  Spam is then sent using this newly furnished secret ID.  Feedback to the global reputation database causes this secret ID number to be blacklisted after just 10 spam emails. Therefore sending one billion spam will require more than 22,000 years of computing time – it will take a botnet of more than 24 million computers running 8 hours a day to send one billion spam.  Much of this spam will still not reach the user’s inbox in part because it will also bear the suspicious stigma of being sent with a freshly minted secret ID number acquired solely via a computation, something that will be characteristic of only a miniscule amount of legitimate email.

3.5     Email from Reputable Personal Computers Residing behind Disreputable MTAs will be Safely Delivered

Some email senders with clean computers use an MTA that is also used by spammer compromised computers to send spam. Traditionally all email sent through such an MTA was tainted by the MTA’s poor reputation.  Personal Computer Authentication will help prevent a legitimate user’s email from being misclassified as spam despite the poor reputation of the user’s domain or MTA.

3.6     Privacy is Protected

The information within the reputation reports issued by the global database will be generalized enough to ensure a high degree of anonymity.  It will generally not be possible to determine that two separate emails were sent by the same computer by comparing only the reputation reports.

Users that require an unusually high level of anonymity will be able to delve into the options menus of their email clients and web browsers so that the secret ID number that was included with their computer is not used.  These users will then ‘purchase’ a new secret ID number by performing a time-consuming computation.

---

4.     A PATH TO UNIVERSAL AUTHENTICATION

MTA Authentication prevents spammers from hiding behind dynamic IP addresses and it eliminates problems induced by email forwarding.  Personal Computer Authentication uniquely provides a practical method to authenticate a personal computer’s email and web browser transactions and allows for the seamless elimination of CAPTCHA.  These two systems, by operating at two different levels, are synergistic.  A comparison of key aspects of these two systems is listed in Table 1.  They also complement, rather than replace, existing authentication methods.  Instituting these authentication methods will require a miniscule fraction of the effort that existing schemes have required.

---

5.     REFERENCES

[1]     McAfee Research Blog (July 3rd, 2008):  SPF / DKIM Use on the Decline Among Fortune 500s? http://www.trustedsource.org/blog/130/SPF-DKIM-Use-on-the-Decline-Among-Fortune-500s

[2]     Sendmail.org (2009):  Fortune 1000 DKIM Survey http://www.sendmail.org/dkim/surveyFortune1000

[3]     L. Seltzer (November 15, 2004):  The Beginning of the Crypto Era, Eweek.com http://www.eweek.com/c/a/Security/The-Beginning-of-the-Crypto-Era/

[4]     R. Guimerà: DKIM
http://www.dkim.org/Misc/DKIM-perform-en.pdf

[5]     A. Back (August 1, 2002): Hashcash - A Denial of Service Counter-Measure http://www.hashcash.org/papers/hashcash.pdf

[6]     Microsoft Research: Penny Black http://research.microsoft.com/en-us/projects/PennyBlack/

[7]     G. Cluley (January 2, 2009): Spammers defy Bill Gates's death of spam prophecy, Sophos Blog http://www.sophos.com/blogs/gc/g/2009/01/22/spammers-defy-bill-gatess-death-spam-prophecy/

[8]     M. Abadi, M. Burrows, M. Manasse, T. Wobber (May 2005): Moderately Hard, Memory-bound Functions http://research.microsoft.com/pubs/54395/memory-longer-acm.pdf

[9]     IEEE Registration Authority http://standards.ieee.org/regauth/index.html

[10]  Websense Security Labs (February 15, 2009): Microsoft's CAPTCHA revolutions busted by spammers - again and again http://securitylabs.websense.com/content/Blogs/3306.aspx

[11]  D. Danchev (August 29, 2008): Inside India's CAPTCHA solving economy
http://blogs.zdnet.com/security/?p=1835