A Basic Explanation of a Novel and Easily Implemented Technique to Stop Spam by Authenticating All of the World’s Computers

This page attempts to make the core concepts expressed in my more technical paper understandable to a larger audience.

Background information is highlighted in green, so skip any highlighted section if you are already familiar with the material.  The non-highlighted original material starts about halfway down the page.

Michael G. Kaplan

How Email is Sent

Email is typically sent from a personal computer using a program called an email client such as Outlook or Thunderbird (web mail is a slightly different matter and not discussed here).  The email is sent from a personal computer to a local mail server called a Mail Transfer Agent (MTA).  The term ‘MTA’ can refer to the server that is used to send or forward mail, the software program that runs on the server, or both.

The MTA will then send the email to a receiving mail server.  The act of ‘sending’ an email between mail servers is not a one step process, but rather a multi-step conversation whereby the two servers send information back and forth multiple times before the ‘sending’ of the email is complete.  For this conversation to take place each server must know the Internet Protocol address (IP address) of the other server.  This back and forth conversation makes it impossible for an MTA to misrepresent its IP address when delivering email to another server.

Spammers are able to fabricate every single piece of information in an email message except for the IP address of the server they are using or else the multi-step back and forth conversation needed to pass an email between servers can not take place.

IP Address Reputation

IP address reputation databases have become extremely valuable in the fight against spam as the IP address of a sending server is the only email element that a spammer can never forge.  The IP address of a mail server of a large corporation that has responsibly sent mail for years will have an excellent reputation and this server will have no trouble successfully delivering its emails.  A zombie computer acting as a spammer mail server will soon find its IP address on an IP address black list.

Static and Dynamic IP Address

Internet service providers (ISPs) are allocated large blocks of IP addresses for their use.  ISPs can arbitrarily take some of these IP addresses and permanently assign them to specific servers.  Addresses that are permanently assigned to a single computer are known as static IP addresses.

The ISP can arbitrarily select other IP addresses and temporarily lend them to individual personal computers belonging to the ISP’s subscribers.  A subscriber can borrow one of these addresses for just a few hours before giving it up; these addresses are known as dynamic IP addresses.

One of the flaws of IP address reputation databases is that a dynamic IP address may be used by a legitimate user one moment and a spammer the next.  There is no way to recognize a legitimate user who keeps on rotating through dynamic IP addresses.

Dynamic IP addresses are much more likely to send spam than static IP addresses, so anti-spam services respond by heavily discriminating against all email sent via dynamic IP addresses (yes, this does block some legitimate email).  This leads to another problem – there is no intrinsic way to even know if an IP address is static or dynamic as the ISPs arbitrarily designate IP addresses as either static or dynamic.

Email Headers and Authentication

An email header contains technical information used for mail delivery, but email users only see the message body while the technical mumbo-jumbo contained in the header is not routinely shown to the user.  The header will list the IP address of every server that has handled the email.

Spammers routinely spoof the email address in the ‘From’ field.  Spam headers also routinely spoof the IP addresses so as to give a false history of the path an email has taken.

Authentication refers to a process of making sure that the person or computer who claims to have sent an email really did send it.  The goal of authentication is to prevent spoofing.

How Sender Policy Framework (SPF), the Most Commonly Used Authentication Method, Works

(Sender ID is the same as SPF except for some unimportant variations.)

How do you know if the email you just received from Accounts@BigBank.com is real or just a spammer forgery?  SPF can tell you if this email was truly sent from the BigBank.com domain.

SPF relies on the fact that the IP address of the server that sends you an email can never be forged.  The domain administrator of BigBank.com will publicly list all of BigBank’s outgoing mail servers by posting them in the Domain Name System (DNS) record.

Now when you receive the email all you have to do is check the DNS to look up BigBank’s official list of approved outgoing email servers and see if one of the listed servers matches the IP address of the server that sent the email.  A successful match is called an SPF PASS while not matching is an SPF FAIL.

Some flaws with SPF

• SPF is a purely voluntary protocol and so it relies on motivated domain administrators to manually enter all of their domain’s servers into the DNS.  Some surveys suggest that even among Fortune 500 companies less than half use SPF.
• SPF is not useful if the domain uses dynamic IP addresses for their MTAs.
• SPF authenticates the domain, but it does not guarantee that the message content was not secretly altered by a spammer while in transit.
• There are various other problems with SPF.  For instance, we have not even addressed the problem posed by email forwarding…

How Email Forwarding Works

Let us say that you enable your old university email account to forward all email to the email account you currently use.  Every time the server at your old university forwards an email it will first insert the IP address of the previous server in the header of the email – in this way an email header will list the IP address of every single server that the email passed through.  An email forwarded via multiple servers will have the IP of each forwarding server discretely listed in the header.

The Problem with Forwarding

Recall that the only element of an email that can never be forged is the IP address of the server that directly passes on an email to the recipient.  It is possible to forge the IP addresses listed in a header of the servers that the email purportedly previously passed through.

By example:  You received an email directly from server #1 and the email header gives a history that server #1 got the email from server #2.  You are positive that you received the email directly from server #1, but you don’t know if server #1 is a spammer controlled computer that is trying to fool you into believing that it received the email from server #2.

Forwarding Breaks SPF

Imagine you receive an email purportedly from Bigbank.com.  The email header reveals that the email was forwarded to you after originating from a different server.  The original server as listed in the header actually does belong to BigBank.com but the forwarding server does not.

SPF is now useless because there is no way to be sure that the ‘forwarding server’ is not a spammer operated zombie that simply fabricated both the email message and the contents of the email header.  Actually SPF can still be helpful but only if you are certain that the forwarding server is trustworthy.

To explain this innovation I will first explain what a digital signature is.  To understand digital signatures you must understand two things: hashes and public key cryptography.

Hashes

Let’s say that you have a piece of corned beef and you want to make corned beef hash.  You would take the corned beef and chop it and mince it up until you had your hash.

For computers making a hash is pretty much the same – you use a computer algorithm to chop and mince a digital file and as a result you spit out a short number that is referred to as a hash.

One aspect of hashes is that if you change a single bit of a digital file the result will be a completely different hash.  You can try out various hash algorithms with this online hash calculator.

Hashes are extremely useful.  As an example say you just downloaded a 10 MB file to your computer.  How do you know that the download went perfectly?  Without hashes you will have to download the file twice and compare the two downloads to make sure that they are identical.  If there is a discrepancy you will have to download this huge file for a third time as you will not know which file is the real file.  With hashes all you have to do is download the file and a copy of the file’s hash.  You then run your own hash on the 10 MB file and you see if your hash matches the downloaded hash.

Another example of the usefulness of hashes is with storing passwords.  It is dangerous for security purposes for a large business to keep copies of the passwords of its customers on a server.  It is much safer to keep copies of the hashes of the passwords on the server.  This way a customer can log in with their password and the server will then hash the customer-submitted password and compare the resulting hash to the stored list of password hashes.  This is obviously much safer because you can verify someone’s password without actually having to store a copy of their password.

Anyway forget about hashes for now because I want to explain public key cryptography….

Public Key Cryptography

To understand public key encryption, also called asymmetric key cryptography, I will first explain symmetric key encryption.

Symmetric Key Cryptography

Symmetric key cryptography is also known as secret-key, single key, shared key, one key and private key encryption (private key is a little confusing because public key encryption also uses something called a private key).

To encrypt a digital file you take the file and you start scrambling and substituting and altering all of the numbers so that the only way you can restore the file is by using a ‘key’ that tells the computer how to reverse the process.  With symmetric key cryptography you use the exact same key to both scramble and unscramble a message.  There is only one key.

Symmetric key cryptography is extremely useful but it has a big problem:  How do you safely send someone the key in the first place?  What if someone intercepted the key while it was in transit?  To solve this problem public key (asymmetric key) cryptography was invented.

Public Key Cryptography

With public key cryptography two different keys are created.  One of these keys is arbitrarily designated the ‘private’ key and the other is arbitrarily designated the ‘public’ key.  Data that is encrypted via one key and can only be decrypted with the other key.  You can not decrypt the data with the same key that was used to encrypt it in the first place; only the opposite key can decrypt it.

Now let’s say that I want you to encrypt and send me a document but I’m afraid that a symmetric key will be intercepted if I try to send it to you.  My computer generates two asymmetric keys and I arbitrarily pick one of them to designate as the public key and the other one is the private key.  I can post the public key on my website for the entire world to see.  You use that public key to encrypt and send the document.  I use my private key to decrypt it – success!  You were able to send me an encrypted document that only I can decipher even though I never met you before.

Now let’s say that I wanted to send you a document and I don’t care if other people see the contents of the document but I want you to be absolutely certain that it came from me.  I will use my private key to encrypt the document and I will then send it to you.  You will then use my public key and decrypt it.  You now know that it came from me since only the owner of the private key could have encrypted it to begin with.  In this case I used my private key so that you could authenticate the document.

Digital Signatures

Now we will fuse the concept of hashes and public keys to show how digital signatures work.  Suppose I send you an email from my Gmail account – how can you be sure that the email came from Gmail and not from a spammer sending a spoofed email?

Method #1 that Gmail can (but does not) do – Gmail can encrypt the entire email using its private key.  Gmail can then post its public key in the domain name system (DNS).  Now when you receive the encrypted email all that your receiving mail system has to do is retrieve Gmail’s public key from the DNS and decrypt the message.  You have successfully authenticated the email because you know that the Gmail public key is the only key that can decrypt the email!

Problem – Your email system must be able to automatically decrypt these emails or else you will be unable to read the email.

Method #2 that Gmail can (but does not) do – Gmail sends both an encrypted version of the email and a non-encrypted version.  Now all that your mail system has to do is decrypt the encrypted version and see if it perfectly matches the unencrypted version.  This is better than method #1 because now receivers whose mail systems are not updated to specifically process this type of email will still be able to read the unencrypted portion of the email.

Problem – Gmail has just doubled the size of every email message.  Also receivers with non-updated software will see the unencrypted part of the email with a lot of ugly and confusing encrypted code.

Method #3 that Gmail can (and actually does!) do – Gmail will first run a hash on the email message body and then use its private key to encrypt this hash.  It will then insert this encrypted hash into the email header.  Gmail will post its public key on a DNS server.

The receiving email system will retrieve Gmail’s public key from the DNS and use it to decrypt the hash.  The receiving email system will then run its own hash on the email message and compare it to the decrypted hash and if the two hashes match then the email has been authenticated.  The integrity of the email since departing Gmail is also guaranteed as the email message could not have been altered without altering the hash.  The encrypted hash is discretely hidden in the email header so users will never see any ugly and confusing encrypted code.

There is a specific term used to describe this kind of encrypted hash of a digital file: a digital signature.

DKIM:  The Most Sophisticated Existing Email Authentication Standard

DomainKeys Identified Mail (DKIM) is a digital signature based email authentication standard.  Method #3 as described above is DKIM.  DKIM is a slightly updated form of the original DomainKeys standard.

DKIM is better than SPF because it is unaffected by forwarding and the integrity of the email message is guaranteed (i.e. no one can alter the email contents once it has been signed).

If DKIM is so much better than SPF then why doesn’t everyone use DKIM?

SPF takes a slight amount of initiative and effort on behalf of the domain administrator, and as a consequence a huge proportion of email domains have not adopted it.

DKIM takes much more effort to deploy and maintain so as a consequence it has been adopted by a relatively trivial number of domains, although many of the most widely used email domains do employ it (e.g. Gmail, Yahoo, AOL).  Many other domains will partially deploy it – the domain of a major bank may use it for their mass mailings to their customers but they will consider it too much of a bother to use it for the routine correspondences of their employees.

Now I can explain a unique innovation that can profoundly impede spam by easily and quickly allowing for near universal authentication of every email server and personal computer in the world.

MTA Authentication

MTA Authentication is a method to authenticate every mail server listed in an email header.  It will also allow a server to be repeatedly recognized despite use of a dynamic IP address.  This method uses digital signatures so it will also guarantee that the email message remains unaltered once it has left an MTA.

It works by upgrading MTA software so that the new and improved software does the following:

1) Every server’s MTA software will autonomously generate a single private key and its corresponding public key.  The private key will forever remain hidden on the server that generated it. There is no sharing of keys, even between servers owned by a single organization.

 

No human interaction is needed as the MTA software will do this automatically.

 

2) The MTA will use its private key to digitally sign every email emanating from a single server.  This server specific digital signature will be placed in the email header.  Both MTA Authentication and DKIM place a digital signature in the header. With MTA Authentication the unique private key will be confined to the server on which it was created and it will be used to ‘blindly’ sign all email emanating from the server regardless of the sender’s domain.

 

DKIM requires manual configuration and the manual distribution and manual management of keys across multiple servers to authenticate a domain. In stark contrast MTA Authentication is an exclusively automated process whereby each server uses autonomously generated keys to sign all outgoing mail, authenticating the server instead of directly authenticating the domain.

 

3) The MTA will automatically report both its public key and the starting date when 100% of its outgoing mail was signed to any computer in the world that queries it.  DKIM, in contrast, requires domain administrators to manually enter public keys into the DNS record.

Universal Authentication Is an Impossibility For DKIM and SPF, But It Is An Inevitability For MTA Authentication

MTA Authentication is fully automated and not prone to human error.  Neither participation nor even awareness on the part of domain administrators is needed.  Universal email authentication via MTA Authentication would require a one-time software update on the part of the very small handful of developers of MTA software. 

DKIM and SPF are voluntary and must be manually initiate and manually maintained, and both are prone to human error.  Universal email authentication via DKIM and SPF would impossibly require the perfect participation of every email domain administrator in the world.

MTA Authentication Eliminates Problems Introduced by Forwarding – An Example

Imagine that an email is sent to MTA#1, forwarded to MTA#2, and finally forwarded to MTA#3 before reaching the email receiver.  Each server is upgraded with MTA Authentication functionality and so each server has signed the email before forwarding it.

The first thing the email receiver will do is to directly query MTA#1 to attain its public key and verify the digital signature of MTA#1 present in the email envelope.  After verifying the signature the receiver has absolute certainty that the email originated from MTA#1 and that the email has not been altered since leaving MTA#1.  The receiver can now treat the email as if it had been received directly from MTA#1.  MTA Authentication has effectively made it as if forwarding never happened.

There actually is no need to even bother checking the signature of MTA#2.  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 depend on the reputation of MTA#2.

Knowing that the email originated from MTA#1 does not directly authenticate the ‘From’ field, but MTA#1’s reputation can now be assessed via an IP address reputation database.

SPF Can Now Authenticate the Domain of Forwarded Email

Imagine that BigBank.com has diligently created an SPF record and that MTA#1 in the preceding example belongs to BigBank.  Normally this email would receive an SPF FAIL as the receiver has no way of knowing for sure that the email originated from MTA#1.  If BigBank uses updated MTA Authentication compliant software then this email will receive an SPF PASS because the receiver can be positive that the email came from MTA#1.

Now Servers Can Always be Recognized Even If They Use a Dynamic IP Address

IP address reputation databases are a critical tool for anti-spam services, but these databases can not recognize a reputable server if that server constantly switches between different dynamic IP addresses.  With MTA Authentication the public key used by this server will never change even if its IP address changes constantly.  Now for the first time IP address reputation databases will always be able to recognize this server by its public key.

Personal Computer Authentication

I have just described the only practical method to authenticate nearly all email by authenticating nearly every mail server, but what about the personal computers from which all email originates?  The following is a description of a practical method to authenticate nearly every personal computer.

First Step:  Every Computer Gets a Secret ID Number

Retrofitting Every Personal Computer With a Secret ID Number

All personal computers must be equipped with a secret ID number.  For security purposes the secret ID should be 128 bits in size – a number so large that it is basically impossible to figure it out by guessing.

Retrofitting all of the world’s computers with a secret ID number is surprisingly simple as almost every computer already possesses a suitable number.  95% of the worlds desktops are Windows PCs and each one already has a Product Key that is known only to Microsoft.  Apple computers can improvise a fixed ID from the software accessible hardware numbers present in each computer.

Microsoft does not need to release its list of Product Keys to a third party database as it can simply release a hash of each product key.  Remember how in the background section on hashes I detail how it is much safer to store the hash of a password than the password itself?  The same principle applies; the hash of a Product Key is just as unique as the Product Key itself and there is now way anyone can learn anything about a Product Key just by looking at its hash.

Individuals who desire perfect anonymity, users with pirated copies of Windows, and the small number of Linux desktops can acquire their secret IDs via a one-time time-consuming computation.

All Future Secret IDs Will be Distributed Via Network Cards

Every device that communicates over a network has a network card with a ROM chip that has a unique number burned into it called the MAC address.  It should effectively cost nothing for network card manufacturers to also burn into this ROM chip a 128 bit secret ID; a simple modification to the official network card standard by the one organization that issues such standards (called the IEEE) will make this a universal practice.  The network card manufacturers will then publicly release a hash of these secret IDs as a secure method of allowing an outside database to verify a secret ID that it encounters in the future.

(Review the ‘Hashes’ background section to understand why passwords are preferably stored as hashes; it will then be clear why it is safer to release the hash of a secret ID number rather than the secret ID number itself.)

Personal Computers Will ‘Blindly’ Sign All Outgoing Email

A simple one-time upgrade to email client software will result in the authentication of all future email sent by that personal computer.  This email client upgrade will equip the computer with a public key.  Note that every computer in the world can use this exact same public key.

As with MTA Authentication every email that is sent by this email client will be ‘blindly’ signed without regard to who the sender is.  It is the personal computer that is actually being authenticated; the domain or email address of the sender is not being authenticated.

Personal Computer Authentication creates a digital signature in a way that is totally unlike how any other digital signature is created.

To review how a traditional digital signature is both made and verified:

• The email is hashed.
• A private key known only to the sender is used to encrypt the hash.
• The encrypted hash is appended to the email and the email is sent and received.
• The receiver uses a public key to decrypt the digital signature thus revealing the hash.
• The receiver computes a hash of the email and verifies it against the decrypted hash.

How a Personal Computer Authentication signature is created and verified:

• The email is hashed by the email client.
• The email client groups the hash together with the computer’s secret ID number:  {hash+secret ID}
• A public key known to everyone in the world is used to encrypt the {hash+secret ID} grouping.  (Normally only a private key is used to create a digital signature.)
• The public key encrypted {hash+secret ID} is appended to the email header by the email client and the email is sent and received.
• The receiver sends the encrypted {hash+secret ID} signature to a centralized database.  This centralized database is the only entity to posses a copy of the private key.
• The centralized database decrypts the signature and sends back the decrypted hash and a reputation report for the secret ID.  The centralized database does not send back the secret ID itself – the secret ID remains secret.
• The receiver computes a hash of the email and verifies it against the decrypted hash sent back by the centralized database.

The receiver is now sure that the email came from the personal computer described in the reputation report and that the email content has not been altered.

It is advantageous to have a single global centralized database to decrypt the hashes and dispense reputation reports; having ten global databases will mean that spammers will be able to send ten times as much spam before a secret ID is neutralized.

Personal Computer Authentication Will Eliminate CAPTCHA

You can review the Wikipedia CAPTCHA article for background.

Users are often asked to solve CAPTCHA before completing webpage registrations for free email accounts and other free online services.  Unfortunately CAPTCHA discriminate against the visually impaired, it is inexpensive for spammers to automatically or manually solve them in mass, and they are at least mildly annoying for pretty much everyone.  Personal Computer Authentication will enable the elimination of CAPTCHA while providing a much higher level of security.

A one-time software update will enable web browsers with Personal Computer Authentication functionality.  When a user encounters a web page registration the following occurs:

• The website, instead of showing the user a CAPTCHA, will tell the user’s browser to transmit an encrypted copy of the computer’s secret ID number.  The website will also send the browser a unique number called an ‘episode identifier’ (don’t think about the episode identifier for now, it will be explained later).
• The web browser will use a public key to encrypt together {secret ID+episode identifier} and send it to the website.
• The website will transmit the encrypted {secret ID+episode identifier} data along with an unencrypted copy of the secret ID to the central database.
• The central database will decrypt the {secret ID+episode identifier} data and send the website the reputation report.
• The website will provide the user with the free service (e.g. a webmail account).

Personal Computer Authentication uses the same basic process on both email clients and on web browsers – encrypting the computer’s secret ID with a public key and sending it to a recipient.  The encrypted secret ID is then sent to the central database and a reputation report pertaining to a specific personal computer is sent back.

Why the Episode Identifier?

If only the secret ID were encrypted by the public key then the encrypted data would be identical for every registration done by the individual computer.  An irresponsible website could report back to the central database that an individual computer registered a thousand different times when in reality it only registered once with that website.  The episode identifier serves to make every registration session unique.  Having the website provide the episode identifier also servers as a redundant security mechanism whereby the central database can be sure that the website that provides feedback to the central database is definitely the one that interacted with the personal computer.

Near Universal Participation is Surprisingly Easy to Achieve

A onetime software upgrade instituted by Microsoft, Apple, and the Mozilla Corporation will retroactively endow almost every personal computer in the world with a secret ID number as well as Personal Computer Authentication enabled email clients and web browsers.  The willful participation of users irrelevant – actually users will be oblivious to any change other than perhaps noticing that they no long encounter CAPTCHA.

Countering Infected Computers

Personal Computer Owners Will Know If Their Secret ID is Compromised

After a receiving mail server successfully receives an email it must issue the sending server a code that effectively means “email successfully received”, otherwise the sending server will not count the email as having been delivered.  A receiving server has the opportunity to fully analyze an email and still reject it by sending back a code that effectively means “delivery of the email is rejected”.  During the rejection process the receiving server can send back customized text informing the sender of the reason why delivery of their email was rejected.

Inevitably spammers will infect a large number of personal computers and steal their secret ID numbers.  Spammer abuse of these stolen secret ID numbers will quickly corrupt the reputation reports connected to these numbers.  Users will quickly realize that their computers are infected because they will not be able to complete delivery of their emails but will instead be issued a rejection notice informing them that their computer is infected.

Users who otherwise would have bypassed CAPTCHA during online registrations will be presented with a webpage informing them that their computer is infected.  Users will need to cleanse their computers before acquiring a new fixed ID number.

Users Will Disinfect Their Computers and Then Perform a Time-Consuming Computation to Acquire a New Secret ID

In many cases the personal computer will need to complete a time-consuming computation prior to being issued a new secret ID number.  The typical duration of the time consuming computation will be the minimal time required to effectively neutralize a spammer botnet.

Example:  Imagine that a two hour computation is required to generate new secret ID for which the central database will initially authenticate 10 emails per day and that a spammer will be able to use this to send off 20 spam before negative feedback invalidates the account.  Existing filtering methods often detect 95% of spam and users manually flag much of the remaining spam, so it is generous to assume that a spammer could even send 20 spam over two a day period.  Under these circumstances a spammer will need to steal more than 11 years of desktop computing power in order to send one million spam. This spam will also bear the highly suspicious stigma of being sent with a freshly minted secret ID acquired solely via a computation, something that will be characteristic of only a miniscule amount of legitimate email.

Legitimate users almost never have their email marked as spam.  Positive feedback from reputable anti-spam services will very rapidly and very greatly increase the daily quota of authenticated email an individual computer can send.

This relatively minor one-time computational burden will almost only be borne by individuals who have allowed their computers to become infected.

Conclusion

Spam levels will be profoundly decreased and CAPTCHA will be eliminated by a one-time software update by a handful of companies.  The change will be invisible to users and server/domain administrators.